diff options
author | Damien Miller <djm@mindrot.org> | 2013-12-07 11:24:01 +1100 |
---|---|---|
committer | Damien Miller <djm@mindrot.org> | 2013-12-07 11:24:01 +1100 |
commit | 5be9d9e3cbd9c66f24745d25bf2e809c1d158ee0 (patch) | |
tree | d2086d37436014ea44f0f024396a1a8638640b00 /sc25519.c | |
parent | bcd00abd8451f36142ae2ee10cc657202149201e (diff) |
- markus@cvs.openbsd.org 2013/12/06 13:39:49
[authfd.c authfile.c key.c key.h myproposal.h pathnames.h readconf.c]
[servconf.c ssh-agent.c ssh-keygen.c ssh-keyscan.1 ssh-keyscan.c]
[ssh-keysign.c ssh.c ssh_config.5 sshd.8 sshd.c verify.c ssh-ed25519.c]
[sc25519.h sc25519.c hash.c ge25519_base.data ge25519.h ge25519.c]
[fe25519.h fe25519.c ed25519.c crypto_api.h blocks.c]
support ed25519 keys (hostkeys and user identities) using the public
domain ed25519 reference code from SUPERCOP, see
http://ed25519.cr.yp.to/software.html
feedback, help & ok djm@
Diffstat (limited to 'sc25519.c')
-rw-r--r-- | sc25519.c | 302 |
1 files changed, 302 insertions, 0 deletions
diff --git a/sc25519.c b/sc25519.c new file mode 100644 index 000000000..1daefd11d --- /dev/null +++ b/sc25519.c | |||
@@ -0,0 +1,302 @@ | |||
1 | /* $OpenBSD: */ | ||
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 | } | ||