1 /* 2 Ignores top bit of h. 3 */ 4 5 void 6 fe25519_frombytes(fe25519 h, const unsigned char *s) 7 { 8 int64_t h0 = load_4(s); 9 int64_t h1 = load_3(s + 4) << 6; 10 int64_t h2 = load_3(s + 7) << 5; 11 int64_t h3 = load_3(s + 10) << 3; 12 int64_t h4 = load_3(s + 13) << 2; 13 int64_t h5 = load_4(s + 16); 14 int64_t h6 = load_3(s + 20) << 7; 15 int64_t h7 = load_3(s + 23) << 5; 16 int64_t h8 = load_3(s + 26) << 4; 17 int64_t h9 = (load_3(s + 29) & 8388607) << 2; 18 19 int64_t carry0; 20 int64_t carry1; 21 int64_t carry2; 22 int64_t carry3; 23 int64_t carry4; 24 int64_t carry5; 25 int64_t carry6; 26 int64_t carry7; 27 int64_t carry8; 28 int64_t carry9; 29 30 carry9 = (h9 + (int64_t)(1L << 24)) >> 25; 31 h0 += carry9 * 19; 32 h9 -= carry9 * ((uint64_t) 1L << 25); 33 carry1 = (h1 + (int64_t)(1L << 24)) >> 25; 34 h2 += carry1; 35 h1 -= carry1 * ((uint64_t) 1L << 25); 36 carry3 = (h3 + (int64_t)(1L << 24)) >> 25; 37 h4 += carry3; 38 h3 -= carry3 * ((uint64_t) 1L << 25); 39 carry5 = (h5 + (int64_t)(1L << 24)) >> 25; 40 h6 += carry5; 41 h5 -= carry5 * ((uint64_t) 1L << 25); 42 carry7 = (h7 + (int64_t)(1L << 24)) >> 25; 43 h8 += carry7; 44 h7 -= carry7 * ((uint64_t) 1L << 25); 45 46 carry0 = (h0 + (int64_t)(1L << 25)) >> 26; 47 h1 += carry0; 48 h0 -= carry0 * ((uint64_t) 1L << 26); 49 carry2 = (h2 + (int64_t)(1L << 25)) >> 26; 50 h3 += carry2; 51 h2 -= carry2 * ((uint64_t) 1L << 26); 52 carry4 = (h4 + (int64_t)(1L << 25)) >> 26; 53 h5 += carry4; 54 h4 -= carry4 * ((uint64_t) 1L << 26); 55 carry6 = (h6 + (int64_t)(1L << 25)) >> 26; 56 h7 += carry6; 57 h6 -= carry6 * ((uint64_t) 1L << 26); 58 carry8 = (h8 + (int64_t)(1L << 25)) >> 26; 59 h9 += carry8; 60 h8 -= carry8 * ((uint64_t) 1L << 26); 61 62 h[0] = (int32_t) h0; 63 h[1] = (int32_t) h1; 64 h[2] = (int32_t) h2; 65 h[3] = (int32_t) h3; 66 h[4] = (int32_t) h4; 67 h[5] = (int32_t) h5; 68 h[6] = (int32_t) h6; 69 h[7] = (int32_t) h7; 70 h[8] = (int32_t) h8; 71 h[9] = (int32_t) h9; 72 } 73 74 /* 75 Preconditions: 76 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. 77 78 Write p=2^255-19; q=floor(h/p). 79 Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))). 80 81 Proof: 82 Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4. 83 Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4. 84 85 Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9). 86 Then 0<y<1. 87 88 Write r=h-pq. 89 Have 0<=r<=p-1=2^255-20. 90 Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1. 91 92 Write x=r+19(2^-255)r+y. 93 Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q. 94 95 Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1)) 96 so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q. 97 */ 98 99 static void 100 fe25519_reduce(fe25519 h, const fe25519 f) 101 { 102 int32_t h0 = f[0]; 103 int32_t h1 = f[1]; 104 int32_t h2 = f[2]; 105 int32_t h3 = f[3]; 106 int32_t h4 = f[4]; 107 int32_t h5 = f[5]; 108 int32_t h6 = f[6]; 109 int32_t h7 = f[7]; 110 int32_t h8 = f[8]; 111 int32_t h9 = f[9]; 112 113 int32_t q; 114 int32_t carry0, carry1, carry2, carry3, carry4, carry5, carry6, carry7, carry8, carry9; 115 116 q = (19 * h9 + ((uint32_t) 1L << 24)) >> 25; 117 q = (h0 + q) >> 26; 118 q = (h1 + q) >> 25; 119 q = (h2 + q) >> 26; 120 q = (h3 + q) >> 25; 121 q = (h4 + q) >> 26; 122 q = (h5 + q) >> 25; 123 q = (h6 + q) >> 26; 124 q = (h7 + q) >> 25; 125 q = (h8 + q) >> 26; 126 q = (h9 + q) >> 25; 127 128 /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */ 129 h0 += 19 * q; 130 /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */ 131 132 carry0 = h0 >> 26; 133 h1 += carry0; 134 h0 -= carry0 * ((uint32_t) 1L << 26); 135 carry1 = h1 >> 25; 136 h2 += carry1; 137 h1 -= carry1 * ((uint32_t) 1L << 25); 138 carry2 = h2 >> 26; 139 h3 += carry2; 140 h2 -= carry2 * ((uint32_t) 1L << 26); 141 carry3 = h3 >> 25; 142 h4 += carry3; 143 h3 -= carry3 * ((uint32_t) 1L << 25); 144 carry4 = h4 >> 26; 145 h5 += carry4; 146 h4 -= carry4 * ((uint32_t) 1L << 26); 147 carry5 = h5 >> 25; 148 h6 += carry5; 149 h5 -= carry5 * ((uint32_t) 1L << 25); 150 carry6 = h6 >> 26; 151 h7 += carry6; 152 h6 -= carry6 * ((uint32_t) 1L << 26); 153 carry7 = h7 >> 25; 154 h8 += carry7; 155 h7 -= carry7 * ((uint32_t) 1L << 25); 156 carry8 = h8 >> 26; 157 h9 += carry8; 158 h8 -= carry8 * ((uint32_t) 1L << 26); 159 carry9 = h9 >> 25; 160 h9 -= carry9 * ((uint32_t) 1L << 25); 161 162 h[0] = h0; 163 h[1] = h1; 164 h[2] = h2; 165 h[3] = h3; 166 h[4] = h4; 167 h[5] = h5; 168 h[6] = h6; 169 h[7] = h7; 170 h[8] = h8; 171 h[9] = h9; 172 } 173 174 /* 175 Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20. 176 Have h0+...+2^230 h9 between 0 and 2^255-1; 177 evidently 2^255 h10-2^255 q = 0. 178 179 Goal: Output h0+...+2^230 h9. 180 */ 181 182 void 183 fe25519_tobytes(unsigned char *s, const fe25519 h) 184 { 185 fe25519 t; 186 187 fe25519_reduce(t, h); 188 s[0] = t[0] >> 0; 189 s[1] = t[0] >> 8; 190 s[2] = t[0] >> 16; 191 s[3] = (t[0] >> 24) | (t[1] * ((uint32_t) 1 << 2)); 192 s[4] = t[1] >> 6; 193 s[5] = t[1] >> 14; 194 s[6] = (t[1] >> 22) | (t[2] * ((uint32_t) 1 << 3)); 195 s[7] = t[2] >> 5; 196 s[8] = t[2] >> 13; 197 s[9] = (t[2] >> 21) | (t[3] * ((uint32_t) 1 << 5)); 198 s[10] = t[3] >> 3; 199 s[11] = t[3] >> 11; 200 s[12] = (t[3] >> 19) | (t[4] * ((uint32_t) 1 << 6)); 201 s[13] = t[4] >> 2; 202 s[14] = t[4] >> 10; 203 s[15] = t[4] >> 18; 204 s[16] = t[5] >> 0; 205 s[17] = t[5] >> 8; 206 s[18] = t[5] >> 16; 207 s[19] = (t[5] >> 24) | (t[6] * ((uint32_t) 1 << 1)); 208 s[20] = t[6] >> 7; 209 s[21] = t[6] >> 15; 210 s[22] = (t[6] >> 23) | (t[7] * ((uint32_t) 1 << 3)); 211 s[23] = t[7] >> 5; 212 s[24] = t[7] >> 13; 213 s[25] = (t[7] >> 21) | (t[8] * ((uint32_t) 1 << 4)); 214 s[26] = t[8] >> 4; 215 s[27] = t[8] >> 12; 216 s[28] = (t[8] >> 20) | (t[9] * ((uint32_t) 1 << 6)); 217 s[29] = t[9] >> 2; 218 s[30] = t[9] >> 10; 219 s[31] = t[9] >> 18; 220 } 221