Develop and Download Open Source Software

Tera Term

Browse Subversion Repository

/[ttssh2]/trunk/ttssh2/ttxssh/ed25519_fe25519.c

Contents of /trunk/ttssh2/ttxssh/ed25519_fe25519.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 5545 - (show annotations) (download) (as text)
Mon Mar 17 16:06:58 2014 UTC (10 years ago) by yutakapon
File MIME type: text/x-csrc
File size: 8639 byte(s) 
チケット #33263
Curve25519楕円曲線DH（Diffe Hellman）アルゴリズムを使った鍵交換をサポートした。

svn+ssh://svn.sourceforge.jp/svnroot/ttssh2/branches/ssh_ed25519
ブランチからマージ。

現時点でサポートしている機能は下記の通り。

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