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