1 #include "cube.h"
2
3 ///////////////////////// cryptography /////////////////////////////////
4
5 /* Based off the reference implementation of Tiger, a cryptographically
6 * secure 192 bit hash function by Ross Anderson and Eli Biham. More info at:
7 * http://www.cs.technion.ac.il/~biham/Reports/Tiger/
8 */
9
10 #define TIGER_PASSES 3
11
12 namespace tiger
13 {
14 typedef unsigned long long int chunk;
15
16 union hashval
17 {
18 uchar bytes[3*8];
19 chunk chunks[3];
20 };
21
22 chunk sboxes[4*256];
23
compress(const chunk * str,chunk state[3])24 void compress(const chunk *str, chunk state[3])
25 {
26 chunk a, b, c;
27 chunk aa, bb, cc;
28 chunk x0, x1, x2, x3, x4, x5, x6, x7;
29
30 a = state[0];
31 b = state[1];
32 c = state[2];
33
34 x0=str[0]; x1=str[1]; x2=str[2]; x3=str[3];
35 x4=str[4]; x5=str[5]; x6=str[6]; x7=str[7];
36
37 aa = a;
38 bb = b;
39 cc = c;
40
41 loop(pass_no, TIGER_PASSES)
42 {
43 if(pass_no)
44 {
45 x0 -= x7 ^ 0xA5A5A5A5A5A5A5A5ULL; x1 ^= x0; x2 += x1; x3 -= x2 ^ ((~x1)<<19);
46 x4 ^= x3; x5 += x4; x6 -= x5 ^ ((~x4)>>23); x7 ^= x6;
47 x0 += x7; x1 -= x0 ^ ((~x7)<<19); x2 ^= x1; x3 += x2;
48 x4 -= x3 ^ ((~x2)>>23); x5 ^= x4; x6 += x5; x7 -= x6 ^ 0x0123456789ABCDEFULL;
49 }
50
51 #define sb1 (sboxes)
52 #define sb2 (sboxes+256)
53 #define sb3 (sboxes+256*2)
54 #define sb4 (sboxes+256*3)
55
56 #define round(a, b, c, x) \
57 c ^= x; \
58 a -= sb1[((c)>>(0*8))&0xFF] ^ sb2[((c)>>(2*8))&0xFF] ^ \
59 sb3[((c)>>(4*8))&0xFF] ^ sb4[((c)>>(6*8))&0xFF] ; \
60 b += sb4[((c)>>(1*8))&0xFF] ^ sb3[((c)>>(3*8))&0xFF] ^ \
61 sb2[((c)>>(5*8))&0xFF] ^ sb1[((c)>>(7*8))&0xFF] ; \
62 b *= mul;
63
64 uint mul = !pass_no ? 5 : (pass_no==1 ? 7 : 9);
65 round(a, b, c, x0) round(b, c, a, x1) round(c, a, b, x2) round(a, b, c, x3)
66 round(b, c, a, x4) round(c, a, b, x5) round(a, b, c, x6) round(b, c, a, x7)
67
68 chunk tmp = a; a = c; c = b; b = tmp;
69 }
70
71 a ^= aa;
72 b -= bb;
73 c += cc;
74
75 state[0] = a;
76 state[1] = b;
77 state[2] = c;
78 }
79
gensboxes()80 void gensboxes()
81 {
82 const char *str = "Tiger - A Fast New Hash Function, by Ross Anderson and Eli Biham";
83 chunk state[3] = { 0x0123456789ABCDEFULL, 0xFEDCBA9876543210ULL, 0xF096A5B4C3B2E187ULL };
84 uchar temp[64];
85
86 if(!islittleendian()) loopj(64) temp[j^7] = str[j];
87 else loopj(64) temp[j] = str[j];
88 loopi(1024) loop(col, 8) ((uchar *)&sboxes[i])[col] = i&0xFF;
89
90 int abc = 2;
91 loop(pass, 5) loopi(256) for(int sb = 0; sb < 1024; sb += 256)
92 {
93 abc++;
94 if(abc >= 3) { abc = 0; compress((chunk *)temp, state); }
95 loop(col, 8)
96 {
97 uchar val = ((uchar *)&sboxes[sb+i])[col];
98 ((uchar *)&sboxes[sb+i])[col] = ((uchar *)&sboxes[sb + ((uchar *)&state[abc])[col]])[col];
99 ((uchar *)&sboxes[sb + ((uchar *)&state[abc])[col]])[col] = val;
100 }
101 }
102 }
103
hash(const uchar * str,int length,hashval & val)104 void hash(const uchar *str, int length, hashval &val)
105 {
106 static bool init = false;
107 if(!init) { gensboxes(); init = true; }
108
109 uchar temp[64];
110
111 val.chunks[0] = 0x0123456789ABCDEFULL;
112 val.chunks[1] = 0xFEDCBA9876543210ULL;
113 val.chunks[2] = 0xF096A5B4C3B2E187ULL;
114
115 int i = length;
116 for(; i >= 64; i -= 64, str += 64)
117 {
118 if(!islittleendian())
119 {
120 loopj(64) temp[j^7] = str[j];
121 compress((chunk *)temp, val.chunks);
122 }
123 else compress((chunk *)str, val.chunks);
124 }
125
126 int j;
127 if(!islittleendian())
128 {
129 for(j = 0; j < i; j++) temp[j^7] = str[j];
130 temp[j^7] = 0x01;
131 while(++j&7) temp[j^7] = 0;
132 }
133 else
134 {
135 for(j = 0; j < i; j++) temp[j] = str[j];
136 temp[j] = 0x01;
137 while(++j&7) temp[j] = 0;
138 }
139
140 if(j > 56)
141 {
142 while(j < 64) temp[j++] = 0;
143 compress((chunk *)temp, val.chunks);
144 j = 0;
145 }
146 while(j < 56) temp[j++] = 0;
147 *(chunk *)(temp+56) = (chunk)length<<3;
148 compress((chunk *)temp, val.chunks);
149 if(!islittleendian())
150 {
151 loopk(3)
152 {
153 uchar *c = &val.bytes[k*sizeof(chunk)];
154 loopl(sizeof(chunk)/2) swap(c[l], c[sizeof(chunk)-1-l]);
155 }
156 }
157 }
158 }
159
160 /* Elliptic curve cryptography based on NIST DSS prime curves. */
161
162 #define BI_DIGIT_BITS 16
163 #define BI_DIGIT_MASK ((1<<BI_DIGIT_BITS)-1)
164
165 template<int BI_DIGITS> struct bigint
166 {
167 typedef ushort digit;
168 typedef uint dbldigit;
169
170 int len;
171 digit digits[BI_DIGITS];
172
bigintbigint173 bigint() {}
bigintbigint174 bigint(digit n) { if(n) { len = 1; digits[0] = n; } else len = 0; }
bigintbigint175 bigint(const char *s) { parse(s); }
bigintbigint176 template<int Y_DIGITS> bigint(const bigint<Y_DIGITS> &y) { *this = y; }
177
parsedigitsbigint178 static int parsedigits(ushort *digits, int maxlen, const char *s)
179 {
180 int slen = 0;
181 while(isxdigit(s[slen])) slen++;
182 int len = (slen+2*sizeof(ushort)-1)/(2*sizeof(ushort));
183 if(len>maxlen) return 0;
184 memset(digits, 0, len*sizeof(ushort));
185 loopi(slen)
186 {
187 int c = s[slen-i-1];
188 if(isalpha(c)) c = toupper(c) - 'A' + 10;
189 else if(isdigit(c)) c -= '0';
190 else return 0;
191 digits[i/(2*sizeof(ushort))] |= c<<(4*(i%(2*sizeof(ushort))));
192 }
193 return len;
194 }
195
parsebigint196 void parse(const char *s)
197 {
198 len = parsedigits(digits, BI_DIGITS, s);
199 shrink();
200 }
201
zerobigint202 void zero() { len = 0; }
203
printbigint204 void print(stream *out) const
205 {
206 vector<char> buf;
207 printdigits(buf);
208 out->write(buf.getbuf(), buf.length());
209 }
210
printdigitsbigint211 void printdigits(vector<char> &buf) const
212 {
213 loopi(len)
214 {
215 digit d = digits[len-i-1];
216 loopj(BI_DIGIT_BITS/4)
217 {
218 uint shift = BI_DIGIT_BITS - (j+1)*4;
219 int val = (d >> shift) & 0xF;
220 if(val < 10) buf.add('0' + val);
221 else buf.add('a' + val - 10);
222 }
223 }
224 }
225
operator =bigint226 template<int Y_DIGITS> bigint &operator=(const bigint<Y_DIGITS> &y)
227 {
228 len = y.len;
229 memcpy(digits, y.digits, len*sizeof(digit));
230 return *this;
231 }
232
iszerobigint233 bool iszero() const { return !len; }
isonebigint234 bool isone() const { return len==1 && digits[0]==1; }
235
numbitsbigint236 int numbits() const
237 {
238 if(!len) return 0;
239 int bits = len*BI_DIGIT_BITS;
240 digit last = digits[len-1], mask = 1<<(BI_DIGIT_BITS-1);
241 while(mask)
242 {
243 if(last&mask) return bits;
244 bits--;
245 mask >>= 1;
246 }
247 return 0;
248 }
249
hasbitbigint250 bool hasbit(int n) const { return n/BI_DIGIT_BITS < len && ((digits[n/BI_DIGIT_BITS]>>(n%BI_DIGIT_BITS))&1); }
251
morebitsbigint252 bool morebits(int n) const { return len > n/BI_DIGIT_BITS; }
253
addbigint254 template<int X_DIGITS, int Y_DIGITS> bigint &add(const bigint<X_DIGITS> &x, const bigint<Y_DIGITS> &y)
255 {
256 dbldigit carry = 0;
257 int maxlen = max(x.len, y.len), i;
258 for(i = 0; i < y.len || carry; i++)
259 {
260 carry += (i < x.len ? (dbldigit)x.digits[i] : 0) + (i < y.len ? (dbldigit)y.digits[i] : 0);
261 digits[i] = (digit)carry;
262 carry >>= BI_DIGIT_BITS;
263 }
264 if(i < x.len && this != &x) memcpy(&digits[i], &x.digits[i], (x.len - i)*sizeof(digit));
265 len = max(i, maxlen);
266 return *this;
267 }
addbigint268 template<int Y_DIGITS> bigint &add(const bigint<Y_DIGITS> &y) { return add(*this, y); }
269
subbigint270 template<int X_DIGITS, int Y_DIGITS> bigint &sub(const bigint<X_DIGITS> &x, const bigint<Y_DIGITS> &y)
271 {
272 ASSERT(x >= y);
273 dbldigit borrow = 0;
274 int i;
275 for(i = 0; i < y.len || borrow; i++)
276 {
277 borrow = (1<<BI_DIGIT_BITS) + (dbldigit)x.digits[i] - (i<y.len ? (dbldigit)y.digits[i] : 0) - borrow;
278 digits[i] = (digit)borrow;
279 borrow = (borrow>>BI_DIGIT_BITS)^1;
280 }
281 if(i < x.len && this != &x) memcpy(&digits[i], &x.digits[i], (x.len - i)*sizeof(digit));
282 len = x.len;
283 shrink();
284 return *this;
285 }
subbigint286 template<int Y_DIGITS> bigint &sub(const bigint<Y_DIGITS> &y) { return sub(*this, y); }
287
shrinkbigint288 void shrink() { while(len && !digits[len-1]) len--; }
shrinkdigitsbigint289 void shrinkdigits(int n) { len = n; shrink(); }
shrinkbitsbigint290 void shrinkbits(int n) { shrinkdigits(n/BI_DIGIT_BITS); }
291
copyshrinkdigitsbigint292 template<int Y_DIGITS> void copyshrinkdigits(const bigint<Y_DIGITS> &y, int n)
293 {
294 len = min(y.len, n);
295 memcpy(digits, y.digits, len*sizeof(digit));
296 shrink();
297 }
copyshrinkbitsbigint298 template<int Y_DIGITS> void copyshrinkbits(const bigint<Y_DIGITS> &y, int n)
299 {
300 copyshrinkdigits(y, n/BI_DIGIT_BITS);
301 }
302
mulbigint303 template<int X_DIGITS, int Y_DIGITS> bigint &mul(const bigint<X_DIGITS> &x, const bigint<Y_DIGITS> &y)
304 {
305 if(!x.len || !y.len) { len = 0; return *this; }
306 memset(digits, 0, y.len*sizeof(digit));
307 loopi(x.len)
308 {
309 dbldigit carry = 0;
310 loopj(y.len)
311 {
312 carry += (dbldigit)x.digits[i] * (dbldigit)y.digits[j] + (dbldigit)digits[i+j];
313 digits[i+j] = (digit)carry;
314 carry >>= BI_DIGIT_BITS;
315 }
316 digits[i+y.len] = carry;
317 }
318 len = x.len + y.len;
319 shrink();
320 return *this;
321 }
322
rshiftbigint323 bigint &rshift(int n)
324 {
325 if(!len || n<=0) return *this;
326 if(n >= len*BI_DIGIT_BITS) { len = 0; return *this; }
327 int dig = (n-1)/BI_DIGIT_BITS;
328 n = ((n-1) % BI_DIGIT_BITS)+1;
329 digit carry = digit(digits[dig]>>n);
330 for(int i = dig+1; i < len; i++)
331 {
332 digit tmp = digits[i];
333 digits[i-dig-1] = digit((tmp<<(BI_DIGIT_BITS-n)) | carry);
334 carry = digit(tmp>>n);
335 }
336 digits[len-dig-1] = carry;
337 len -= dig + (n/BI_DIGIT_BITS);
338 shrink();
339 return *this;
340 }
341
lshiftbigint342 bigint &lshift(int n)
343 {
344 if(!len || n<=0) return *this;
345 int dig = n/BI_DIGIT_BITS;
346 n %= BI_DIGIT_BITS;
347 digit carry = 0;
348 loopirev(len)
349 {
350 digit tmp = digits[i];
351 digits[i+dig] = digit((tmp<<n) | carry);
352 carry = digit(tmp>>(BI_DIGIT_BITS-n));
353 }
354 len += dig;
355 if(carry) digits[len++] = carry;
356 if(dig) memset(digits, 0, dig*sizeof(digit));
357 return *this;
358 }
359
zerodigitsbigint360 void zerodigits(int i, int n)
361 {
362 memset(&digits[i], 0, n*sizeof(digit));
363 }
zerobitsbigint364 void zerobits(int i, int n)
365 {
366 zerodigits(i/BI_DIGIT_BITS, n/BI_DIGIT_BITS);
367 }
368
copydigitsbigint369 template<int Y_DIGITS> void copydigits(int to, const bigint<Y_DIGITS> &y, int from, int n)
370 {
371 int avail = min(y.len-from, n);
372 memcpy(&digits[to], &y.digits[from], avail*sizeof(digit));
373 if(avail < n) memset(&digits[to+avail], 0, (n-avail)*sizeof(digit));
374 }
copybitsbigint375 template<int Y_DIGITS> void copybits(int to, const bigint<Y_DIGITS> &y, int from, int n)
376 {
377 copydigits(to/BI_DIGIT_BITS, y, from/BI_DIGIT_BITS, n/BI_DIGIT_BITS);
378 }
379
dupdigitsbigint380 void dupdigits(int to, int from, int n)
381 {
382 memcpy(&digits[to], &digits[from], n*sizeof(digit));
383 }
dupbitsbigint384 void dupbits(int to, int from, int n)
385 {
386 dupdigits(to/BI_DIGIT_BITS, from/BI_DIGIT_BITS, n/BI_DIGIT_BITS);
387 }
388
operator ==bigint389 template<int Y_DIGITS> bool operator==(const bigint<Y_DIGITS> &y) const
390 {
391 if(len!=y.len) return false;
392 loopirev(len) if(digits[i]!=y.digits[i]) return false;
393 return true;
394 }
operator !=bigint395 template<int Y_DIGITS> bool operator!=(const bigint<Y_DIGITS> &y) const { return !(*this==y); }
operator <bigint396 template<int Y_DIGITS> bool operator<(const bigint<Y_DIGITS> &y) const
397 {
398 if(len<y.len) return true;
399 if(len>y.len) return false;
400 loopirev(len)
401 {
402 if(digits[i]<y.digits[i]) return true;
403 if(digits[i]>y.digits[i]) return false;
404 }
405 return false;
406 }
operator >bigint407 template<int Y_DIGITS> bool operator>(const bigint<Y_DIGITS> &y) const { return y<*this; }
operator <=bigint408 template<int Y_DIGITS> bool operator<=(const bigint<Y_DIGITS> &y) const { return !(y<*this); }
operator >=bigint409 template<int Y_DIGITS> bool operator>=(const bigint<Y_DIGITS> &y) const { return !(*this<y); }
410 };
411
412 #define GF_BITS 192
413 #define GF_DIGITS ((GF_BITS+BI_DIGIT_BITS-1)/BI_DIGIT_BITS)
414
415 typedef bigint<GF_DIGITS+1> gfint;
416
417 /* NIST prime Galois fields.
418 * Currently only supports NIST P-192, where P=2^192-2^64-1, and P-256, where P=2^256-2^224+2^192+2^96-1.
419 */
420 struct gfield : gfint
421 {
422 static const gfield P;
423
gfieldgfield424 gfield() {}
gfieldgfield425 gfield(digit n) : gfint(n) {}
gfieldgfield426 gfield(const char *s) : gfint(s) {}
427
gfieldgfield428 template<int Y_DIGITS> gfield(const bigint<Y_DIGITS> &y) : gfint(y) {}
429
operator =gfield430 template<int Y_DIGITS> gfield &operator=(const bigint<Y_DIGITS> &y)
431 {
432 gfint::operator=(y);
433 return *this;
434 }
435
addgfield436 template<int X_DIGITS, int Y_DIGITS> gfield &add(const bigint<X_DIGITS> &x, const bigint<Y_DIGITS> &y)
437 {
438 gfint::add(x, y);
439 if(*this >= P) gfint::sub(*this, P);
440 return *this;
441 }
addgfield442 template<int Y_DIGITS> gfield &add(const bigint<Y_DIGITS> &y) { return add(*this, y); }
443
mul2gfield444 template<int X_DIGITS> gfield &mul2(const bigint<X_DIGITS> &x) { return add(x, x); }
mul2gfield445 gfield &mul2() { return mul2(*this); }
446
div2gfield447 gfield &div2()
448 {
449 if(hasbit(0)) gfint::add(*this, P);
450 rshift(1);
451 return *this;
452 }
453
subgfield454 template<int X_DIGITS, int Y_DIGITS> gfield &sub(const bigint<X_DIGITS> &x, const bigint<Y_DIGITS> &y)
455 {
456 if(x < y)
457 {
458 gfint tmp; /* necessary if this==&y, using this instead would clobber y */
459 tmp.add(x, P);
460 gfint::sub(tmp, y);
461 }
462 else gfint::sub(x, y);
463 return *this;
464 }
subgfield465 template<int Y_DIGITS> gfield &sub(const bigint<Y_DIGITS> &y) { return sub(*this, y); }
466
neggfield467 template<int X_DIGITS> gfield &neg(const bigint<X_DIGITS> &x)
468 {
469 gfint::sub(P, x);
470 return *this;
471 }
neggfield472 gfield &neg() { return neg(*this); }
473
squaregfield474 template<int X_DIGITS> gfield &square(const bigint<X_DIGITS> &x) { return mul(x, x); }
squaregfield475 gfield &square() { return square(*this); }
476
mulgfield477 template<int X_DIGITS, int Y_DIGITS> gfield &mul(const bigint<X_DIGITS> &x, const bigint<Y_DIGITS> &y)
478 {
479 bigint<X_DIGITS+Y_DIGITS> result;
480 result.mul(x, y);
481 reduce(result);
482 return *this;
483 }
mulgfield484 template<int Y_DIGITS> gfield &mul(const bigint<Y_DIGITS> &y) { return mul(*this, y); }
485
reducegfield486 template<int RESULT_DIGITS> void reduce(const bigint<RESULT_DIGITS> &result)
487 {
488 #if GF_BITS==192
489 // B = T + S1 + S2 + S3 mod p
490 copyshrinkdigits(result, GF_DIGITS); // T
491
492 if(result.morebits(192))
493 {
494 gfield s;
495 s.copybits(0, result, 192, 64);
496 s.dupbits(64, 0, 64);
497 s.shrinkbits(128);
498 add(s); // S1
499
500 if(result.morebits(256))
501 {
502 s.zerobits(0, 64);
503 s.copybits(64, result, 256, 64);
504 s.dupbits(128, 64, 64);
505 s.shrinkdigits(GF_DIGITS);
506 add(s); // S2
507
508 if(result.morebits(320))
509 {
510 s.copybits(0, result, 320, 64);
511 s.dupbits(64, 0, 64);
512 s.dupbits(128, 0, 64);
513 s.shrinkdigits(GF_DIGITS);
514 add(s); // S3
515 }
516 }
517 }
518 else if(*this >= P) gfint::sub(*this, P);
519 #elif GF_BITS==256
520 // B = T + 2*S1 + 2*S2 + S3 + S4 - D1 - D2 - D3 - D4 mod p
521 copyshrinkdigits(result, GF_DIGITS); // T
522
523 if(result.morebits(256))
524 {
525 gfield s;
526 if(result.morebits(352))
527 {
528 s.zerobits(0, 96);
529 s.copybits(96, result, 352, 160);
530 s.shrinkdigits(GF_DIGITS);
531 add(s); add(s); // S1
532
533 if(result.morebits(384))
534 {
535 //s.zerobits(0, 96);
536 s.copybits(96, result, 384, 128);
537 s.shrinkbits(224);
538 add(s); add(s); // S2
539 }
540 }
541
542 s.copybits(0, result, 256, 96);
543 s.zerobits(96, 96);
544 s.copybits(192, result, 448, 64);
545 s.shrinkdigits(GF_DIGITS);
546 add(s); // S3
547
548 s.copybits(0, result, 288, 96);
549 s.copybits(96, result, 416, 96);
550 s.dupbits(192, 96, 32);
551 s.copybits(224, result, 256, 32);
552 s.shrinkdigits(GF_DIGITS);
553 add(s); // S4
554
555 s.copybits(0, result, 352, 96);
556 s.zerobits(96, 96);
557 s.copybits(192, result, 256, 32);
558 s.copybits(224, result, 320, 32);
559 s.shrinkdigits(GF_DIGITS);
560 sub(s); // D1
561
562 s.copybits(0, result, 384, 128);
563 //s.zerobits(128, 64);
564 s.copybits(192, result, 288, 32);
565 s.copybits(224, result, 352, 32);
566 s.shrinkdigits(GF_DIGITS);
567 sub(s); // D2
568
569 s.copybits(0, result, 416, 96);
570 s.copybits(96, result, 256, 96);
571 s.zerobits(192, 32);
572 s.copybits(224, result, 384, 32);
573 s.shrinkdigits(GF_DIGITS);
574 sub(s); // D3
575
576 s.copybits(0, result, 448, 64);
577 s.zerobits(64, 32);
578 s.copybits(96, result, 288, 96);
579 //s.zerobits(192, 32);
580 s.copybits(224, result, 416, 32);
581 s.shrinkdigits(GF_DIGITS);
582 sub(s); // D4
583 }
584 else if(*this >= P) gfint::sub(*this, P);
585 #else
586 #error Unsupported GF
587 #endif
588 }
589
powgfield590 template<int X_DIGITS, int Y_DIGITS> gfield &pow(const bigint<X_DIGITS> &x, const bigint<Y_DIGITS> &y)
591 {
592 gfield a(x);
593 if(y.hasbit(0)) *this = a;
594 else
595 {
596 len = 1;
597 digits[0] = 1;
598 if(!y.len) return *this;
599 }
600 for(int i = 1, j = y.numbits(); i < j; i++)
601 {
602 a.square();
603 if(y.hasbit(i)) mul(a);
604 }
605 return *this;
606 }
powgfield607 template<int Y_DIGITS> gfield &pow(const bigint<Y_DIGITS> &y) { return pow(*this, y); }
608
invertgfield609 bool invert(const gfield &x)
610 {
611 if(!x.len) return false;
612 gfint u(x), v(P), A((gfint::digit)1), C((gfint::digit)0);
613 while(!u.iszero())
614 {
615 int ushift = 0, ashift = 0;
616 while(!u.hasbit(ushift))
617 {
618 ushift++;
619 if(A.hasbit(ashift))
620 {
621 if(ashift) { A.rshift(ashift); ashift = 0; }
622 A.add(P);
623 }
624 ashift++;
625 }
626 if(ushift) u.rshift(ushift);
627 if(ashift) A.rshift(ashift);
628 int vshift = 0, cshift = 0;
629 while(!v.hasbit(vshift))
630 {
631 vshift++;
632 if(C.hasbit(cshift))
633 {
634 if(cshift) { C.rshift(cshift); cshift = 0; }
635 C.add(P);
636 }
637 cshift++;
638 }
639 if(vshift) v.rshift(vshift);
640 if(cshift) C.rshift(cshift);
641 if(u >= v)
642 {
643 u.sub(v);
644 if(A < C) A.add(P);
645 A.sub(C);
646 }
647 else
648 {
649 v.sub(v, u);
650 if(C < A) C.add(P);
651 C.sub(A);
652 }
653 }
654 if(C >= P) gfint::sub(C, P);
655 else { len = C.len; memcpy(digits, C.digits, len*sizeof(digit)); }
656 ASSERT(*this < P);
657 return true;
658 }
invertgfield659 void invert() { invert(*this); }
660
legendregfield661 template<int X_DIGITS> static int legendre(const bigint<X_DIGITS> &x)
662 {
663 static const gfint Psub1div2(gfint(P).sub(bigint<1>(1)).rshift(1));
664 gfield L;
665 L.pow(x, Psub1div2);
666 if(!L.len) return 0;
667 if(L.len==1) return 1;
668 return -1;
669 }
legendregfield670 int legendre() const { return legendre(*this); }
671
sqrtgfield672 bool sqrt(const gfield &x)
673 {
674 if(!x.len) { len = 0; return true; }
675 #if GF_BITS==224
676 #error Unsupported GF
677 #else
678 ASSERT((P.digits[0]%4)==3);
679 static const gfint Padd1div4(gfint(P).add(bigint<1>(1)).rshift(2));
680 switch(legendre(x))
681 {
682 case 0: len = 0; return true;
683 case -1: return false;
684 default: pow(x, Padd1div4); return true;
685 }
686 #endif
687 }
sqrtgfield688 bool sqrt() { return sqrt(*this); }
689 };
690
691 struct ecjacobian
692 {
693 static const gfield B;
694 static const ecjacobian base;
695 static const ecjacobian origin;
696
697 gfield x, y, z;
698
ecjacobianecjacobian699 ecjacobian() {}
ecjacobianecjacobian700 ecjacobian(const gfield &x, const gfield &y) : x(x), y(y), z(bigint<1>(1)) {}
ecjacobianecjacobian701 ecjacobian(const gfield &x, const gfield &y, const gfield &z) : x(x), y(y), z(z) {}
702
mul2ecjacobian703 void mul2()
704 {
705 if(z.iszero()) return;
706 else if(y.iszero()) { *this = origin; return; }
707 gfield a, b, c, d;
708 d.sub(x, c.square(z));
709 d.mul(c.add(x));
710 c.mul2(d).add(d);
711 z.mul(y).add(z);
712 a.square(y);
713 b.mul2(a);
714 d.mul2(x).mul(b);
715 x.square(c).sub(d).sub(d);
716 a.square(b).add(a);
717 y.sub(d, x).mul(c).sub(a);
718 }
719
addecjacobian720 void add(const ecjacobian &q)
721 {
722 if(q.z.iszero()) return;
723 else if(z.iszero()) { *this = q; return; }
724 gfield a, b, c, d, e, f;
725 a.square(z);
726 b.mul(q.y, a).mul(z);
727 a.mul(q.x);
728 if(q.z.isone())
729 {
730 c.add(x, a);
731 d.add(y, b);
732 a.sub(x, a);
733 b.sub(y, b);
734 }
735 else
736 {
737 f.mul(y, e.square(q.z)).mul(q.z);
738 e.mul(x);
739 c.add(e, a);
740 d.add(f, b);
741 a.sub(e, a);
742 b.sub(f, b);
743 }
744 if(a.iszero()) { if(b.iszero()) mul2(); else *this = origin; return; }
745 if(!q.z.isone()) z.mul(q.z);
746 z.mul(a);
747 x.square(b).sub(f.mul(c, e.square(a)));
748 y.sub(f, x).sub(x).mul(b).sub(e.mul(a).mul(d)).div2();
749 }
750
mulecjacobian751 template<int Q_DIGITS> void mul(const ecjacobian &p, const bigint<Q_DIGITS> &q)
752 {
753 *this = origin;
754 loopirev(q.numbits())
755 {
756 mul2();
757 if(q.hasbit(i)) add(p);
758 }
759 }
mulecjacobian760 template<int Q_DIGITS> void mul(const bigint<Q_DIGITS> &q) { ecjacobian tmp(*this); mul(tmp, q); }
761
normalizeecjacobian762 void normalize()
763 {
764 if(z.iszero() || z.isone()) return;
765 gfield tmp;
766 z.invert();
767 tmp.square(z);
768 x.mul(tmp);
769 y.mul(tmp).mul(z);
770 z = bigint<1>(1);
771 }
772
calcyecjacobian773 bool calcy(bool ybit)
774 {
775 gfield y2, tmp;
776 y2.square(x).mul(x).sub(tmp.add(x, x).add(x)).add(B);
777 if(!y.sqrt(y2)) { y.zero(); return false; }
778 if(y.hasbit(0) != ybit) y.neg();
779 return true;
780 }
781
printecjacobian782 void print(vector<char> &buf)
783 {
784 normalize();
785 buf.add(y.hasbit(0) ? '-' : '+');
786 x.printdigits(buf);
787 }
788
parseecjacobian789 void parse(const char *s)
790 {
791 bool ybit = *s++ == '-';
792 x.parse(s);
793 calcy(ybit);
794 z = bigint<1>(1);
795 }
796 };
797
798 const ecjacobian ecjacobian::origin(gfield((gfield::digit)1), gfield((gfield::digit)1), gfield((gfield::digit)0));
799
800 #if GF_BITS==192
801 const gfield gfield::P("fffffffffffffffffffffffffffffffeffffffffffffffff");
802 const gfield ecjacobian::B("64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1");
803 const ecjacobian ecjacobian::base(
804 gfield("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012"),
805 gfield("07192b95ffc8da78631011ed6b24cdd573f977a11e794811")
806 );
807 #elif GF_BITS==224
808 const gfield gfield::P("ffffffffffffffffffffffffffffffff000000000000000000000001");
809 const gfield ecjacobian::B("b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4");
810 const ecjacobian ecjacobian::base(
811 gfield("b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21"),
812 gfield("bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34")
813 );
814 #elif GF_BITS==256
815 const gfield gfield::P("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff");
816 const gfield ecjacobian::B("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b");
817 const ecjacobian ecjacobian::base(
818 gfield("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"),
819 gfield("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5")
820 );
821 #elif GF_BITS==384
822 const gfield gfield::P("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff");
823 const gfield ecjacobian::B("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef");
824 const ecjacobian ecjacobian::base(
825 gfield("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7"),
826 gfield("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f")
827 );
828 #elif GF_BITS==521
829 const gfield gfield::P("1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff");
830 const gfield ecjacobian::B("051953eb968e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00");
831 const ecjacobian ecjacobian::base(
832 gfield("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66"),
833 gfield("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650")
834 );
835 #else
836 #error Unsupported GF
837 #endif
838
genprivkey(const char * seed,vector<char> & privstr,vector<char> & pubstr)839 void genprivkey(const char *seed, vector<char> &privstr, vector<char> &pubstr)
840 {
841 tiger::hashval hash;
842 tiger::hash((const uchar *)seed, (int)strlen(seed), hash);
843 bigint<8*sizeof(hash.bytes)/BI_DIGIT_BITS> privkey;
844 memcpy(privkey.digits, hash.bytes, sizeof(hash.bytes));
845 privkey.len = 8*sizeof(hash.bytes)/BI_DIGIT_BITS;
846 privkey.shrink();
847 privkey.printdigits(privstr);
848 privstr.add('\0');
849
850 ecjacobian c(ecjacobian::base);
851 c.mul(privkey);
852 c.normalize();
853 c.print(pubstr);
854 pubstr.add('\0');
855 }
856
hashstring(const char * str,char * result,int maxlen)857 bool hashstring(const char *str, char *result, int maxlen)
858 {
859 tiger::hashval hv;
860 if(maxlen < 2*(int)sizeof(hv.bytes) + 1) return false;
861 tiger::hash((uchar *)str, strlen(str), hv);
862 loopi(sizeof(hv.bytes))
863 {
864 uchar c = hv.bytes[i];
865 *result++ = "0123456789abcdef"[c>>4];
866 *result++ = "0123456789abcdef"[c&0xF];
867 }
868 *result = '\0';
869 return true;
870 }
871
answerchallenge(const char * privstr,const char * challenge,vector<char> & answerstr)872 void answerchallenge(const char *privstr, const char *challenge, vector<char> &answerstr)
873 {
874 gfint privkey;
875 privkey.parse(privstr);
876 ecjacobian answer;
877 answer.parse(challenge);
878 answer.mul(privkey);
879 answer.normalize();
880 answer.x.printdigits(answerstr);
881 answerstr.add('\0');
882 }
883
parsepubkey(const char * pubstr)884 void *parsepubkey(const char *pubstr)
885 {
886 ecjacobian *pubkey = new ecjacobian;
887 pubkey->parse(pubstr);
888 return pubkey;
889 }
890
freepubkey(void * pubkey)891 void freepubkey(void *pubkey)
892 {
893 delete (ecjacobian *)pubkey;
894 }
895
genchallenge(void * pubkey,const void * seed,int seedlen,vector<char> & challengestr)896 void *genchallenge(void *pubkey, const void *seed, int seedlen, vector<char> &challengestr)
897 {
898 tiger::hashval hash;
899 tiger::hash((const uchar *)seed, seedlen, hash);
900 gfint challenge;
901 memcpy(challenge.digits, hash.bytes, sizeof(hash.bytes));
902 challenge.len = 8*sizeof(hash.bytes)/BI_DIGIT_BITS;
903 challenge.shrink();
904
905 ecjacobian answer(*(ecjacobian *)pubkey);
906 answer.mul(challenge);
907 answer.normalize();
908
909 ecjacobian secret(ecjacobian::base);
910 secret.mul(challenge);
911 secret.normalize();
912
913 secret.print(challengestr);
914 challengestr.add('\0');
915
916 return new gfield(answer.x);
917 }
918
freechallenge(void * answer)919 void freechallenge(void *answer)
920 {
921 delete (gfint *)answer;
922 }
923
checkchallenge(const char * answerstr,void * correct)924 bool checkchallenge(const char *answerstr, void *correct)
925 {
926 gfint answer(answerstr);
927 return answer == *(gfint *)correct;
928 }
929
930