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