1 #include "sc25519.h"
2
3 /*Arithmetic modulo the group order m = 2^252 + 27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */
4
5 static const crypto_uint32 m[32] = {0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58, 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14,
6 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
7
8 static const crypto_uint32 mu[33] = {0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED, 0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21,
9 0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F};
10
lt(crypto_uint32 a,crypto_uint32 b)11 static crypto_uint32 lt(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
12 {
13 unsigned int x = a;
14 x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
15 x >>= 31; /* 0: no; 1: yes */
16 return x;
17 }
18
19 /* Reduce coefficients of r before calling reduce_add_sub */
reduce_add_sub(sc25519 * r)20 static void reduce_add_sub(sc25519 *r)
21 {
22 crypto_uint32 pb = 0;
23 crypto_uint32 b;
24 crypto_uint32 mask;
25 int i;
26 unsigned char t[32];
27
28 for(i=0;i<32;i++)
29 {
30 pb += m[i];
31 b = lt(r->v[i],pb);
32 t[i] = r->v[i]-pb+(b<<8);
33 pb = b;
34 }
35 mask = b - 1;
36 for(i=0;i<32;i++)
37 r->v[i] ^= mask & (r->v[i] ^ t[i]);
38 }
39
40 /* Reduce coefficients of x before calling barrett_reduce */
barrett_reduce(sc25519 * r,const crypto_uint32 x[64])41 static void barrett_reduce(sc25519 *r, const crypto_uint32 x[64])
42 {
43 /* See HAC, Alg. 14.42 */
44 int i,j;
45 crypto_uint32 q2[66];
46 crypto_uint32 *q3 = q2 + 33;
47 crypto_uint32 r1[33];
48 crypto_uint32 r2[33];
49 crypto_uint32 carry;
50 crypto_uint32 pb = 0;
51 crypto_uint32 b;
52
53 for (i = 0;i < 66;++i) q2[i] = 0;
54 for (i = 0;i < 33;++i) r2[i] = 0;
55
56 for(i=0;i<33;i++)
57 for(j=0;j<33;j++)
58 if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
59 carry = q2[31] >> 8;
60 q2[32] += carry;
61 carry = q2[32] >> 8;
62 q2[33] += carry;
63
64 for(i=0;i<33;i++)r1[i] = x[i];
65 for(i=0;i<32;i++)
66 for(j=0;j<33;j++)
67 if(i+j < 33) r2[i+j] += m[i]*q3[j];
68
69 for(i=0;i<32;i++)
70 {
71 carry = r2[i] >> 8;
72 r2[i+1] += carry;
73 r2[i] &= 0xff;
74 }
75
76 for(i=0;i<32;i++)
77 {
78 pb += r2[i];
79 b = lt(r1[i],pb);
80 r->v[i] = r1[i]-pb+(b<<8);
81 pb = b;
82 }
83
84 /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3
85 * If so: Handle it here!
86 */
87
88 reduce_add_sub(r);
89 reduce_add_sub(r);
90 }
91
sc25519_from32bytes(sc25519 * r,const unsigned char x[32])92 void sc25519_from32bytes(sc25519 *r, const unsigned char x[32])
93 {
94 int i;
95 crypto_uint32 t[64];
96 for(i=0;i<32;i++) t[i] = x[i];
97 for(i=32;i<64;++i) t[i] = 0;
98 barrett_reduce(r, t);
99 }
100
shortsc25519_from16bytes(shortsc25519 * r,const unsigned char x[16])101 void shortsc25519_from16bytes(shortsc25519 *r, const unsigned char x[16])
102 {
103 int i;
104 for(i=0;i<16;i++) r->v[i] = x[i];
105 }
106
sc25519_from64bytes(sc25519 * r,const unsigned char x[64])107 void sc25519_from64bytes(sc25519 *r, const unsigned char x[64])
108 {
109 int i;
110 crypto_uint32 t[64];
111 for(i=0;i<64;i++) t[i] = x[i];
112 barrett_reduce(r, t);
113 }
114
sc25519_from_shortsc(sc25519 * r,const shortsc25519 * x)115 void sc25519_from_shortsc(sc25519 *r, const shortsc25519 *x)
116 {
117 int i;
118 for(i=0;i<16;i++)
119 r->v[i] = x->v[i];
120 for(i=0;i<16;i++)
121 r->v[16+i] = 0;
122 }
123
sc25519_to32bytes(unsigned char r[32],const sc25519 * x)124 void sc25519_to32bytes(unsigned char r[32], const sc25519 *x)
125 {
126 int i;
127 for(i=0;i<32;i++) r[i] = x->v[i];
128 }
129
sc25519_iszero_vartime(const sc25519 * x)130 int sc25519_iszero_vartime(const sc25519 *x)
131 {
132 int i;
133 for(i=0;i<32;i++)
134 if(x->v[i] != 0) return 0;
135 return 1;
136 }
137
sc25519_isshort_vartime(const sc25519 * x)138 int sc25519_isshort_vartime(const sc25519 *x)
139 {
140 int i;
141 for(i=31;i>15;i--)
142 if(x->v[i] != 0) return 0;
143 return 1;
144 }
145
sc25519_lt_vartime(const sc25519 * x,const sc25519 * y)146 int sc25519_lt_vartime(const sc25519 *x, const sc25519 *y)
147 {
148 int i;
149 for(i=31;i>=0;i--)
150 {
151 if(x->v[i] < y->v[i]) return 1;
152 if(x->v[i] > y->v[i]) return 0;
153 }
154 return 0;
155 }
156
sc25519_add(sc25519 * r,const sc25519 * x,const sc25519 * y)157 void sc25519_add(sc25519 *r, const sc25519 *x, const sc25519 *y)
158 {
159 int i, carry;
160 for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
161 for(i=0;i<31;i++)
162 {
163 carry = r->v[i] >> 8;
164 r->v[i+1] += carry;
165 r->v[i] &= 0xff;
166 }
167 reduce_add_sub(r);
168 }
169
sc25519_sub_nored(sc25519 * r,const sc25519 * x,const sc25519 * y)170 void sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y)
171 {
172 crypto_uint32 b = 0;
173 crypto_uint32 t;
174 int i;
175 for(i=0;i<32;i++)
176 {
177 t = x->v[i] - y->v[i] - b;
178 r->v[i] = t & 255;
179 b = (t >> 8) & 1;
180 }
181 }
182
sc25519_mul(sc25519 * r,const sc25519 * x,const sc25519 * y)183 void sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y)
184 {
185 int i,j,carry;
186 crypto_uint32 t[64];
187 for(i=0;i<64;i++)t[i] = 0;
188
189 for(i=0;i<32;i++)
190 for(j=0;j<32;j++)
191 t[i+j] += x->v[i] * y->v[j];
192
193 /* Reduce coefficients */
194 for(i=0;i<63;i++)
195 {
196 carry = t[i] >> 8;
197 t[i+1] += carry;
198 t[i] &= 0xff;
199 }
200
201 barrett_reduce(r, t);
202 }
203
sc25519_mul_shortsc(sc25519 * r,const sc25519 * x,const shortsc25519 * y)204 void sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y)
205 {
206 sc25519 t;
207 sc25519_from_shortsc(&t, y);
208 sc25519_mul(r, x, &t);
209 }
210
sc25519_window3(signed char r[85],const sc25519 * s)211 void sc25519_window3(signed char r[85], const sc25519 *s)
212 {
213 char carry;
214 int i;
215 for(i=0;i<10;i++)
216 {
217 r[8*i+0] = s->v[3*i+0] & 7;
218 r[8*i+1] = (s->v[3*i+0] >> 3) & 7;
219 r[8*i+2] = (s->v[3*i+0] >> 6) & 7;
220 r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
221 r[8*i+3] = (s->v[3*i+1] >> 1) & 7;
222 r[8*i+4] = (s->v[3*i+1] >> 4) & 7;
223 r[8*i+5] = (s->v[3*i+1] >> 7) & 7;
224 r[8*i+5] ^= (s->v[3*i+2] << 1) & 7;
225 r[8*i+6] = (s->v[3*i+2] >> 2) & 7;
226 r[8*i+7] = (s->v[3*i+2] >> 5) & 7;
227 }
228 r[8*i+0] = s->v[3*i+0] & 7;
229 r[8*i+1] = (s->v[3*i+0] >> 3) & 7;
230 r[8*i+2] = (s->v[3*i+0] >> 6) & 7;
231 r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
232 r[8*i+3] = (s->v[3*i+1] >> 1) & 7;
233 r[8*i+4] = (s->v[3*i+1] >> 4) & 7;
234
235 /* Making it signed */
236 carry = 0;
237 for(i=0;i<84;i++)
238 {
239 r[i] += carry;
240 r[i+1] += r[i] >> 3;
241 r[i] &= 7;
242 carry = r[i] >> 2;
243 r[i] -= carry<<3;
244 }
245 r[84] += carry;
246 }
247
sc25519_window5(signed char r[51],const sc25519 * s)248 void sc25519_window5(signed char r[51], const sc25519 *s)
249 {
250 char carry;
251 int i;
252 for(i=0;i<6;i++)
253 {
254 r[8*i+0] = s->v[5*i+0] & 31;
255 r[8*i+1] = (s->v[5*i+0] >> 5) & 31;
256 r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
257 r[8*i+2] = (s->v[5*i+1] >> 2) & 31;
258 r[8*i+3] = (s->v[5*i+1] >> 7) & 31;
259 r[8*i+3] ^= (s->v[5*i+2] << 1) & 31;
260 r[8*i+4] = (s->v[5*i+2] >> 4) & 31;
261 r[8*i+4] ^= (s->v[5*i+3] << 4) & 31;
262 r[8*i+5] = (s->v[5*i+3] >> 1) & 31;
263 r[8*i+6] = (s->v[5*i+3] >> 6) & 31;
264 r[8*i+6] ^= (s->v[5*i+4] << 2) & 31;
265 r[8*i+7] = (s->v[5*i+4] >> 3) & 31;
266 }
267 r[8*i+0] = s->v[5*i+0] & 31;
268 r[8*i+1] = (s->v[5*i+0] >> 5) & 31;
269 r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
270 r[8*i+2] = (s->v[5*i+1] >> 2) & 31;
271
272 /* Making it signed */
273 carry = 0;
274 for(i=0;i<50;i++)
275 {
276 r[i] += carry;
277 r[i+1] += r[i] >> 5;
278 r[i] &= 31;
279 carry = r[i] >> 4;
280 r[i] -= carry<<5;
281 }
282 r[50] += carry;
283 }
284
sc25519_2interleave2(unsigned char r[127],const sc25519 * s1,const sc25519 * s2)285 void sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2)
286 {
287 int i;
288 for(i=0;i<31;i++)
289 {
290 r[4*i] = ( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2);
291 r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2);
292 r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2);
293 r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2);
294 }
295 r[124] = ( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2);
296 r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2);
297 r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2);
298 }
299