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