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