Annotation of src/usr.bin/ssh/fe25519.c, Revision 1.3
1.3 ! markus 1: /* $OpenBSD: fe25519.c,v 1.2 2013/12/07 00:26:37 djm Exp $ */
1.1 markus 2:
1.3 ! markus 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/fe25519.c
! 7: */
1.1 markus 8:
9: #define WINDOWSIZE 1 /* Should be 1,2, or 4 */
10: #define WINDOWMASK ((1<<WINDOWSIZE)-1)
11:
12: #include "fe25519.h"
13:
14: static crypto_uint32 equal(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
15: {
16: crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */
17: x -= 1; /* 4294967295: yes; 0..65534: no */
18: x >>= 31; /* 1: yes; 0: no */
19: return x;
20: }
21:
22: static crypto_uint32 ge(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
23: {
24: unsigned int x = a;
25: x -= (unsigned int) b; /* 0..65535: yes; 4294901761..4294967295: no */
26: x >>= 31; /* 0: yes; 1: no */
27: x ^= 1; /* 1: yes; 0: no */
28: return x;
29: }
30:
31: static crypto_uint32 times19(crypto_uint32 a)
32: {
33: return (a << 4) + (a << 1) + a;
34: }
35:
36: static crypto_uint32 times38(crypto_uint32 a)
37: {
38: return (a << 5) + (a << 2) + (a << 1);
39: }
40:
41: static void reduce_add_sub(fe25519 *r)
42: {
43: crypto_uint32 t;
44: int i,rep;
45:
46: for(rep=0;rep<4;rep++)
47: {
48: t = r->v[31] >> 7;
49: r->v[31] &= 127;
50: t = times19(t);
51: r->v[0] += t;
52: for(i=0;i<31;i++)
53: {
54: t = r->v[i] >> 8;
55: r->v[i+1] += t;
56: r->v[i] &= 255;
57: }
58: }
59: }
60:
61: static void reduce_mul(fe25519 *r)
62: {
63: crypto_uint32 t;
64: int i,rep;
65:
66: for(rep=0;rep<2;rep++)
67: {
68: t = r->v[31] >> 7;
69: r->v[31] &= 127;
70: t = times19(t);
71: r->v[0] += t;
72: for(i=0;i<31;i++)
73: {
74: t = r->v[i] >> 8;
75: r->v[i+1] += t;
76: r->v[i] &= 255;
77: }
78: }
79: }
80:
81: /* reduction modulo 2^255-19 */
82: void fe25519_freeze(fe25519 *r)
83: {
84: int i;
85: crypto_uint32 m = equal(r->v[31],127);
86: for(i=30;i>0;i--)
87: m &= equal(r->v[i],255);
88: m &= ge(r->v[0],237);
89:
90: m = -m;
91:
92: r->v[31] -= m&127;
93: for(i=30;i>0;i--)
94: r->v[i] -= m&255;
95: r->v[0] -= m&237;
96: }
97:
98: void fe25519_unpack(fe25519 *r, const unsigned char x[32])
99: {
100: int i;
101: for(i=0;i<32;i++) r->v[i] = x[i];
102: r->v[31] &= 127;
103: }
104:
105: /* Assumes input x being reduced below 2^255 */
106: void fe25519_pack(unsigned char r[32], const fe25519 *x)
107: {
108: int i;
109: fe25519 y = *x;
110: fe25519_freeze(&y);
111: for(i=0;i<32;i++)
112: r[i] = y.v[i];
113: }
114:
115: int fe25519_iszero(const fe25519 *x)
116: {
117: int i;
118: int r;
119: fe25519 t = *x;
120: fe25519_freeze(&t);
121: r = equal(t.v[0],0);
122: for(i=1;i<32;i++)
123: r &= equal(t.v[i],0);
124: return r;
125: }
126:
127: int fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y)
128: {
129: int i;
130: fe25519 t1 = *x;
131: fe25519 t2 = *y;
132: fe25519_freeze(&t1);
133: fe25519_freeze(&t2);
134: for(i=0;i<32;i++)
135: if(t1.v[i] != t2.v[i]) return 0;
136: return 1;
137: }
138:
139: void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
140: {
141: int i;
142: crypto_uint32 mask = b;
143: mask = -mask;
144: for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
145: }
146:
147: unsigned char fe25519_getparity(const fe25519 *x)
148: {
149: fe25519 t = *x;
150: fe25519_freeze(&t);
151: return t.v[0] & 1;
152: }
153:
154: void fe25519_setone(fe25519 *r)
155: {
156: int i;
157: r->v[0] = 1;
158: for(i=1;i<32;i++) r->v[i]=0;
159: }
160:
161: void fe25519_setzero(fe25519 *r)
162: {
163: int i;
164: for(i=0;i<32;i++) r->v[i]=0;
165: }
166:
167: void fe25519_neg(fe25519 *r, const fe25519 *x)
168: {
169: fe25519 t;
170: int i;
171: for(i=0;i<32;i++) t.v[i]=x->v[i];
172: fe25519_setzero(r);
173: fe25519_sub(r, r, &t);
174: }
175:
176: void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y)
177: {
178: int i;
179: for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
180: reduce_add_sub(r);
181: }
182:
183: void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y)
184: {
185: int i;
186: crypto_uint32 t[32];
187: t[0] = x->v[0] + 0x1da;
188: t[31] = x->v[31] + 0xfe;
189: for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe;
190: for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i];
191: reduce_add_sub(r);
192: }
193:
194: void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y)
195: {
196: int i,j;
197: crypto_uint32 t[63];
198: for(i=0;i<63;i++)t[i] = 0;
199:
200: for(i=0;i<32;i++)
201: for(j=0;j<32;j++)
202: t[i+j] += x->v[i] * y->v[j];
203:
204: for(i=32;i<63;i++)
205: r->v[i-32] = t[i-32] + times38(t[i]);
206: r->v[31] = t[31]; /* result now in r[0]...r[31] */
207:
208: reduce_mul(r);
209: }
210:
211: void fe25519_square(fe25519 *r, const fe25519 *x)
212: {
213: fe25519_mul(r, x, x);
214: }
215:
216: void fe25519_invert(fe25519 *r, const fe25519 *x)
217: {
218: fe25519 z2;
219: fe25519 z9;
220: fe25519 z11;
221: fe25519 z2_5_0;
222: fe25519 z2_10_0;
223: fe25519 z2_20_0;
224: fe25519 z2_50_0;
225: fe25519 z2_100_0;
226: fe25519 t0;
227: fe25519 t1;
228: int i;
229:
230: /* 2 */ fe25519_square(&z2,x);
231: /* 4 */ fe25519_square(&t1,&z2);
232: /* 8 */ fe25519_square(&t0,&t1);
233: /* 9 */ fe25519_mul(&z9,&t0,x);
234: /* 11 */ fe25519_mul(&z11,&z9,&z2);
235: /* 22 */ fe25519_square(&t0,&z11);
236: /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9);
237:
238: /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0);
239: /* 2^7 - 2^2 */ fe25519_square(&t1,&t0);
240: /* 2^8 - 2^3 */ fe25519_square(&t0,&t1);
241: /* 2^9 - 2^4 */ fe25519_square(&t1,&t0);
242: /* 2^10 - 2^5 */ fe25519_square(&t0,&t1);
243: /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0);
244:
245: /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0);
246: /* 2^12 - 2^2 */ fe25519_square(&t1,&t0);
247: /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
248: /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0);
249:
250: /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0);
251: /* 2^22 - 2^2 */ fe25519_square(&t1,&t0);
252: /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
253: /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0);
254:
255: /* 2^41 - 2^1 */ fe25519_square(&t1,&t0);
256: /* 2^42 - 2^2 */ fe25519_square(&t0,&t1);
257: /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
258: /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0);
259:
260: /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0);
261: /* 2^52 - 2^2 */ fe25519_square(&t1,&t0);
262: /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
263: /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0);
264:
265: /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0);
266: /* 2^102 - 2^2 */ fe25519_square(&t0,&t1);
267: /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
268: /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0);
269:
270: /* 2^201 - 2^1 */ fe25519_square(&t0,&t1);
271: /* 2^202 - 2^2 */ fe25519_square(&t1,&t0);
272: /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
273: /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0);
274:
275: /* 2^251 - 2^1 */ fe25519_square(&t1,&t0);
276: /* 2^252 - 2^2 */ fe25519_square(&t0,&t1);
277: /* 2^253 - 2^3 */ fe25519_square(&t1,&t0);
278: /* 2^254 - 2^4 */ fe25519_square(&t0,&t1);
279: /* 2^255 - 2^5 */ fe25519_square(&t1,&t0);
280: /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11);
281: }
282:
283: void fe25519_pow2523(fe25519 *r, const fe25519 *x)
284: {
285: fe25519 z2;
286: fe25519 z9;
287: fe25519 z11;
288: fe25519 z2_5_0;
289: fe25519 z2_10_0;
290: fe25519 z2_20_0;
291: fe25519 z2_50_0;
292: fe25519 z2_100_0;
293: fe25519 t;
294: int i;
295:
296: /* 2 */ fe25519_square(&z2,x);
297: /* 4 */ fe25519_square(&t,&z2);
298: /* 8 */ fe25519_square(&t,&t);
299: /* 9 */ fe25519_mul(&z9,&t,x);
300: /* 11 */ fe25519_mul(&z11,&z9,&z2);
301: /* 22 */ fe25519_square(&t,&z11);
302: /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t,&z9);
303:
304: /* 2^6 - 2^1 */ fe25519_square(&t,&z2_5_0);
305: /* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); }
306: /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t,&z2_5_0);
307:
308: /* 2^11 - 2^1 */ fe25519_square(&t,&z2_10_0);
309: /* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
310: /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t,&z2_10_0);
311:
312: /* 2^21 - 2^1 */ fe25519_square(&t,&z2_20_0);
313: /* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); }
314: /* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0);
315:
316: /* 2^41 - 2^1 */ fe25519_square(&t,&t);
317: /* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
318: /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t,&z2_10_0);
319:
320: /* 2^51 - 2^1 */ fe25519_square(&t,&z2_50_0);
321: /* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
322: /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t,&z2_50_0);
323:
324: /* 2^101 - 2^1 */ fe25519_square(&t,&z2_100_0);
325: /* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); }
326: /* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0);
327:
328: /* 2^201 - 2^1 */ fe25519_square(&t,&t);
329: /* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
330: /* 2^250 - 2^0 */ fe25519_mul(&t,&t,&z2_50_0);
331:
332: /* 2^251 - 2^1 */ fe25519_square(&t,&t);
333: /* 2^252 - 2^2 */ fe25519_square(&t,&t);
334: /* 2^252 - 3 */ fe25519_mul(r,&t,x);
335: }
![[BACK]](/icons/back.gif){kind=icon}
Return to fe25519.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ssh