![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gmprsa.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / ox_ntl / crypt / rsa|
Return to gmprsa.c CVS log | Up to [local] / OpenXM / src / ox_ntl / crypt / rsa |
1.3 ! iwane 1: /* $OpenXM: OpenXM/src/ox_ntl/crypt/rsa/gmprsa.c,v 1.2 2004/09/20 00:10:24 iwane Exp $ */
1.1 iwane 2:
3: #include <stdio.h>
4: #include <stdlib.h>
5: #include <string.h>
6: #include <gmp.h>
7:
8: #include "gmprsa.h"
9: #include "sha1.h"
10:
11:
12: #define STR_PRT(STR, N) do { int _xxx; printf(#STR "[%d]=", N); for (_xxx = 0; _xxx < (N); _xxx++) printf("%02x", STR[_xxx]); printf("\n"); fflush(stdout); } while (0)
13:
14:
1.3 ! iwane 15: #ifndef RSA_KEY_PRINT
1.1 iwane 16: #define RSA_KEY_PRINT 0
1.3 ! iwane 17: #endif
1.1 iwane 18:
1.3 ! iwane 19: /*
! 20: * '*' prime test
! 21: * '#' sgen prime at genprime_strong
! 22: * '+' loop
! 23: * '@' keygen
! 24: */
1.1 iwane 25:
26: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
27: * CONV
28: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
29: static void
30: rsa_uchar2mpz(mpz_ptr z, const unsigned char *buf, int len)
31: {
32: char *str;
33: int i;
34: size_t size = len * 2 * sizeof(char) + 1;
35:
36: str = __gmp_allocate_func(size);
37: for (i = 0; i < len; i++)
38: sprintf(str + 2 * i, "%02x", buf[i]);
39:
40: mpz_set_str(z, str, 16);
41:
42: __gmp_free_func(str, size);
43: }
44:
45:
46: static int
47: rsa_char2ui(int ch)
48: {
49: if (ch >= '0' && ch <= '9')
50: return (ch - '0');
51: else if (ch >= 'a' && ch <= 'z')
52: return (ch - 'a' + 10);
53: else
54: return (ch - 'A' + 10);
55: }
56:
57: static void
58: rsa_mpz2uchar(unsigned char *str, int len, const mpz_ptr z)
59: {
60: char *ptr = mpz_get_str(NULL, 16, z);
61: int length = strlen(ptr);
62: int i = 0, j = 0;
63:
64: for (j = (length + 1) / 2; j < len; j++)
65: str[i++] = '\0';
66:
67: j = 0;
68:
69: if (length % 2 != 0) {
70: str[i++] = rsa_char2ui(ptr[j++]);
71: }
72:
73: for (; i < len && j < length; i++, j += 2) {
74: str[i] = rsa_char2ui(ptr[j]) * 16 + rsa_char2ui(ptr[j + 1]);
75: }
76: str[i] = '\0';
77:
78: __gmp_free_func(ptr, length);
79: }
80:
81:
82: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
83: * INITIALIZE
84: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
85: void
86: rsa_init(rsa_key *r)
87: {
88: mpz_init(r->p);
89: mpz_init(r->q);
90: mpz_init(r->mod);
91: mpz_init(r->private_key);
92: mpz_init_set_si(r->public_key, 11);
93: }
94:
95: void
96: rsa_clear(rsa_key *r)
97: {
98: mpz_clear(r->p);
99: mpz_clear(r->q);
100: mpz_clear(r->mod);
101: mpz_clear(r->public_key);
102: mpz_clear(r->private_key);
103:
104: }
105: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
106: * PRIME
107: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
108: void
109: rsa_genprime(mpz_ptr prime, int len, const mpz_ptr seed, int rep)
110: {
111: const int LOOP = 4096;
112: const int BLOCK = 160;
113: int n, b;
114: int offset = 2;
115: int k, c, i;
116: int shalen;
117: mpz_t s, s1, sp;
118: unsigned char sha[32];
119: char *str;
120:
1.2 iwane 121: if (len < 2) {
122: mpz_set_ui(prime, 3);
123: return ;
124: }
125:
1.1 iwane 126: n = (len - 1) / BLOCK;
127: b = (len - 1) % BLOCK;
128:
129: mpz_init(s);
130: mpz_init(s1);
131: mpz_init(sp);
132:
133:
134: __RETRY:
135: for (c = 0; c < LOOP; c++) {
136: mpz_set_ui(prime, 0);
137: mpz_setbit(prime, len - 1);
138:
139: for (k = 0; k <= n; k++) {
140: mpz_add_ui(s1, seed, offset + c + k);
141: str = mpz_get_str(NULL, 16, s1);
142: shalen = strlen(str);
143: sha1(sha, str, shalen);
144: __gmp_free_func(str, shalen);
145:
146: rsa_uchar2mpz(s, sha, 20);
147:
148: mpz_mul_2exp(sp, s, 160 * k);
149:
150: mpz_add(prime, prime, sp);
151:
152: offset += n + 1;
153: }
154:
155: mpz_setbit(prime, 0);
156: mpz_setbit(prime, len - 1);
157: for (i = (n + 1) * BLOCK; i >= len; i--)
158: mpz_clrbit(prime, i);
159:
160:
161: #if RSA_KEY_PRINT
162: fprintf(stderr, "*"); fflush(stderr);
163: #endif
164: /* prime test */
165: if (mpz_probab_prime_p(prime, rep))
166: break;
167: }
168:
1.3 ! iwane 169:
! 170: if (c == LOOP) {
1.1 iwane 171: #if RSA_KEY_PRINT
1.3 ! iwane 172: fprintf(stderr, "+"); fflush(stderr);
1.1 iwane 173: #endif
174: offset += c + 13;
175: goto __RETRY;
176: }
177:
178: mpz_clear(s);
179: mpz_clear(s1);
180: mpz_clear(sp);
181:
182: }
183:
184:
1.3 ! iwane 185: /****************************************************************************
! 186: * generate prime value
! 187: *
! 188: * INPUT : (O) prime : prime number
! 189: * : (I) len : bit-length of prime number
! 190: * : (I) seed : seed
! 191: * : (I) rep :
! 192: * @see rsa_genprime
! 193: * @see gmp#mpz_probab_prime_p
! 194: ****************************************************************************/
! 195: void
! 196: rsa_genprime_strong(mpz_ptr prime, int len, const mpz_ptr seed, int rep)
! 197: {
! 198: mpz_t p, q, t, s, r;
! 199: int i, j;
! 200: const int N = 1000;
! 201:
! 202: /* prime NONE NONE NONE ALL PART10 30 100
! 203: * 3500 --> 17.46.09
! 204: * 3000 --> 15:55.25
! 205: * 2500 --> 16.15.25
! 206: * 2000 --> 2.05.57 2.04.47 18.07.85 4.09.51
! 207: * 1500 --> 2.27.44 2.22.61 22.16.35 3.33.73 1.34.42
! 208: * 1000 --> 1.32.73 2.11.29 19.42.53 2.53.34 1.30.22 57.46.47 1:06:19
! 209: * 500 --> 2.07.46 1.53.18 19.36.95 2.11.15 1.25.22 1.22.51
! 210: */
! 211:
! 212: mpz_init(s);
! 213: mpz_init_set_ui(p, 0);
! 214: mpz_init(q);
! 215: mpz_init(r);
! 216: mpz_init(t);
! 217:
! 218: for (i = 0;; i++) {
! 219: #if RSA_KEY_PRINT
! 220: fprintf(stderr, "#"); fflush(stderr);
! 221: #endif
! 222: mpz_add(s, seed, p);
! 223: rsa_genprime(prime, len, s, rep);
! 224:
! 225:
! 226: if (len < 100) {
! 227: break;
! 228: }
! 229:
! 230: /* for p-1 method */
! 231: mpz_set(p, prime);
! 232:
! 233: /* remove factor 2 */
! 234: for (j = 1;; j++) {
! 235: if (mpz_tstbit(p, j)) {
! 236: mpz_tdiv_q_2exp(p, p, j);
! 237: break;
! 238: }
! 239: }
! 240:
! 241: /* remove small factor */
! 242: for (mpz_set_ui(q, 3); mpz_cmp_ui(q, N) < 0; mpz_nextprime(q, q)) {
! 243: for (;;) {
! 244: mpz_tdiv_qr(t, r, p, q);
! 245: if (mpz_cmp_ui(r, 0) != 0)
! 246: break;
! 247:
! 248: mpz_swap(t, p);
! 249: }
! 250:
! 251: if (mpz_cmp_ui(p, 1) == 0)
! 252: break;
! 253: }
! 254:
! 255: /* check */
! 256: if (mpz_sizeinbase(p, 2) < 20) {
! 257: continue;
! 258: }
! 259:
! 260: if (mpz_probab_prime_p(p, rep))
! 261: break;
! 262: }
! 263:
! 264: mpz_clear(p);
! 265: mpz_clear(q);
! 266: mpz_clear(r);
! 267: mpz_clear(s);
! 268: mpz_clear(t);
! 269: }
! 270:
! 271:
! 272:
1.1 iwane 273: static int
274: rsa_get_block_size(const mpz_ptr n)
275: {
276: return ((mpz_sizeinbase(n, 16) + 1) / 2);
277: }
278:
1.3 ! iwane 279: /****************************************************************************
! 280: * weak key check.
! 281: *
! 282: * |p - q| >> 0 for fermat factorizing method
! 283: *
! 284: * INPUT : (I) p : prime number
! 285: * : (I) q : prime number
! 286: * : (I) bit : bit-length of prime number $p and $q
! 287: * OUTPUT:
! 288: ****************************************************************************/
! 289: static int
! 290: check_rsakey_strength(const mpz_ptr p, const mpz_ptr q, int bit)
! 291: {
! 292: mpz_t diff;
! 293: int b;
! 294:
! 295: mpz_init(diff);
! 296:
! 297:
! 298: /*
! 299: * for fermat factorizing method
! 300: * |p-q| >> 0
! 301: * && compare p != q
! 302: */
! 303: mpz_sub(diff, p, q);
! 304: if (bit > 200) {
! 305: b = bit - 40;
! 306: } else {
! 307: b = bit / 3;
! 308: }
! 309:
! 310: for (; b < bit / 2 + 1; b++) {
! 311: if (mpz_tstbit(diff, b))
! 312: break;
! 313: }
! 314: mpz_clear(diff);
1.1 iwane 315:
1.3 ! iwane 316: return (b != bit / 2 + 1);
! 317: }
! 318:
! 319: /****************************************************************************
! 320: * generate ras key pair.
1.1 iwane 321: *
322: * bit >= 96 must
323: * rep >= 80 should
324: *
1.3 ! iwane 325: ****************************************************************************/
1.1 iwane 326: int
327: rsa_keygen(
328: rsa_key *rsa,
329: const mpz_ptr _seed1, const mpz_ptr _seed2,
330: unsigned int bit,
331: int rep)
332: {
333: int bitp, bitq;
334: mpz_t gcd;
335: mpz_t phi;
336: mpz_t seed1, seed2;
337:
338: /* 12 = PS_MIN + 3 + 1 */
339: if (bit < 12 * 8)
340: return (-1); /* too short */
341:
342:
343: bitp = bit / 2;
344: bitq = bit - bitp;
345:
346: mpz_init_set_ui(gcd, 1);
347: mpz_init(phi);
348:
349: mpz_init_set(seed1, _seed1);
350: mpz_init_set(seed2, _seed2);
351:
352: for (;;) {
1.3 ! iwane 353: #if RSA_KEY_PRINT
! 354: fprintf(stderr, "@"); fflush(stderr);
! 355: #endif
! 356:
1.1 iwane 357: if (mpz_cmp(seed1, seed2) == 0)
358: goto _NEXT;
359:
1.3 ! iwane 360: rsa_genprime_strong(rsa->p, bitp, seed1, rep);
! 361:
! 362: for (;;) {
! 363: rsa_genprime_strong(rsa->q, bitq, seed2, rep);
! 364: if (check_rsakey_strength(rsa->p, rsa->q, bit)) {
! 365: break;
! 366: }
! 367: mpz_add_ui(seed2, seed2, 0x1234567);
! 368: }
1.1 iwane 369:
370: mpz_clrbit(rsa->p, 0);
371: mpz_clrbit(rsa->q, 0);
372:
1.3 ! iwane 373: /* phi = (p - 1) * (q - 1) */
1.1 iwane 374: mpz_mul(phi, rsa->p, rsa->q);
375:
1.3 ! iwane 376: /* gcd = \gcd(public_key, phi) */
1.1 iwane 377: mpz_gcd(gcd, rsa->public_key, phi);
1.3 ! iwane 378:
1.1 iwane 379: if (mpz_cmp_ui(gcd, 1) != 0)
380: goto _NEXT;
381:
382: break;
383:
384: _NEXT:
385: mpz_add(seed1, seed1, gcd);
386: mpz_sub(seed2, seed2, gcd);
387: }
388:
389: mpz_setbit(rsa->p, 0);
390: mpz_setbit(rsa->q, 0);
391:
392: mpz_invert(rsa->private_key, rsa->public_key, phi);
393:
394: mpz_mul(rsa->mod, rsa->p, rsa->q);
395:
396: rsa->k = rsa_get_block_size(rsa->mod);
397:
398: mpz_clear(gcd);
399: mpz_clear(phi);
400:
401: mpz_clear(seed1);
402: mpz_clear(seed2);
403:
404: return (0);
405: }
406:
407:
408: void
409: rsa_set_publickey(
410: rsa_key *rsa,
411: mpz_ptr public_key,
412: mpz_ptr mod)
413: {
414: mpz_set(rsa->mod, mod);
415: mpz_set(rsa->public_key, public_key);
416: rsa->k = rsa_get_block_size(rsa->mod);
417: }
418:
419: void
420: rsa_set_key(
421: rsa_key *rsa,
422: mpz_ptr public_key,
423: mpz_ptr private_key,
424: mpz_ptr mod)
425: {
426: mpz_set(rsa->private_key, private_key);
427: rsa_set_publickey(rsa, public_key, mod);
428: }
429:
430: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
431: * ENCRYPT
432: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
433: static int
434: rsa_encrypt(
435: unsigned char *eb,
436: const unsigned char *msg,
437: int size,
438: int k,
439: const mpz_ptr c,
440: const mpz_ptr mod,
441: int padding)
442: {
443: const int PS_MIN = 8;
444: const int OCTET_SIZE = 256;
445:
446: int i;
447: int s; /* length of data */
448: int ps; /* length of padding string */
449: const int DATA_MAX = k - PS_MIN - 3;
450: mpz_t x, y, ebz;
451:
452: if (k <= 0)
453: return (-2);
454:
455: mpz_init(x);
456: mpz_init(y);
457: mpz_init(ebz);
458:
459:
460: /* k == ps + s + 3 */
461: if (size > DATA_MAX) {
462: s = DATA_MAX;
463: ps = PS_MIN;
464: } else {
465: s = size;
466: ps = DATA_MAX - size + PS_MIN;
467: }
468:
469: /*-------------------------------------------------------------------*
470: * Encryption-block formatting
471: *-------------------------------------------------------------------*/
472: eb[0] = 0x00;
473: eb[1] = padding;
474:
475:
476: switch (padding) {
477: case RSA_PKCS_1_PADDING_PUBLIC:
478: for (i = 0; i < ps; i++) {
479: /* 0 < random number < 255 */
480: eb[i + 2] = (unsigned char)(random() % (OCTET_SIZE - 1) + 1);
481: }
482: break;
483: case RSA_PKCS_1_PADDING_PRIVATE:
484: for (i = 0; i < ps; i++) {
485: eb[i + 2] = 0xff;
486: }
487: break;
488: case RSA_PKCS_1_PADDING_PRIVATE0:
489: for (i = 0; i < ps; i++) {
490: eb[i + 2] = 0x00;
491: }
492: break;
493: default:
494: mpz_clear(x);
495: mpz_clear(y);
496: mpz_clear(ebz);
497: return (-1);
498: }
499:
500: eb[ps + 2] = 0x00;
501: for (i = 0; i < s; i++) {
502: eb[ps + 3 + i] = *msg++;
503: }
504:
505:
506: /*-------------------------------------------------------------------*
507: * Octet-string-to-integer conversion
508: *-------------------------------------------------------------------*/
509: rsa_uchar2mpz(x, eb, k);
510:
511: /*-------------------------------------------------------------------*
512: * RSA computation
513: *-------------------------------------------------------------------*/
514: mpz_powm(y, x, c, mod);
515:
516: /*-------------------------------------------------------------------*
517: * Integer-to-octet-string conversion
518: *-------------------------------------------------------------------*/
519: rsa_mpz2uchar(eb, k, y);
520:
521:
522: mpz_clear(x);
523: mpz_clear(y);
524: mpz_clear(ebz);
525:
526: return (s);
527: }
528:
529:
530: /****************************************************************************
531: * RSA decryption.
532: *
533: * MEMO: 平文が 0x00 で始まるよう瘢雹なメッセ・踉札犬陸苳詞合,
534: * 正しく復号化することができない.
535: *
536: ****************************************************************************/
537: static int
538: rsa_decrypt(
539: unsigned char *d,
540: const unsigned char *eb,
541: int k,
542: const mpz_ptr exp,
543: const mpz_ptr mod,
544: int padding)
545: {
546: const int PS_MIN = 8;
547:
548: mpz_t x, y;
549: int i, n, bt;
550: int ret = 0;
551:
552: mpz_init(x);
553: mpz_init(y);
554:
555: /*--------------------------------------------------------------------*
556: * Octet-string-to-integer
557: *--------------------------------------------------------------------*/
558: rsa_uchar2mpz(y, eb, k);
559:
560: /* error check */
561: if (mpz_cmp(y, mod) >= 0 || mpz_sgn(y) < 0) {
562: ret = -1;
563: goto _ERR;
564: }
565:
566: /*--------------------------------------------------------------------*
567: * RSA computation
568: *--------------------------------------------------------------------*/
569: mpz_powm(x, y, exp, mod);
570:
571: /*--------------------------------------------------------------------*
572: * Integer-to-octet-string
573: *--------------------------------------------------------------------*/
574: rsa_mpz2uchar(d, k, x);
575:
576:
577: /*--------------------------------------------------------------------*
578: * Encryption-block parsing
579: * EB = 00 || BT || PS || 00 || D
580: *--------------------------------------------------------------------*/
581: if (d[0] != 0x00) {
582: ret = -2;
583: goto _ERR;
584: }
585:
586:
587: if (padding == RSA_PKCS_1_PADDING_PUBLIC) { /* public key */
588: bt = d[1];
589:
590: if (bt != RSA_PKCS_1_PADDING_PRIVATE0 && bt != RSA_PKCS_1_PADDING_PRIVATE) {
591: ret = -3;
592: goto _ERR;
593: }
594:
595: if (bt == RSA_PKCS_1_PADDING_PRIVATE0) {
596: for (i = 0; i < k - 3; i++) {
597: if (d[i + 2] != 0x00) {
598: i--;
599: break;
600: }
601: }
602: } else {
603: for (i = 0; i < k - 3; i++) {
604: if (d[i + 2] != 0xff) {
605: break;
606: }
607: }
608: }
609: } else { /* private key */
610:
611: if (d[1] != RSA_PKCS_1_PADDING_PUBLIC) {
612: ret = -4;
613: goto _ERR;
614: }
615:
616: for (i = 0; i < k - 3; i++) {
617: if (d[i + 2] == 0x00) {
618: break;
619: }
620: }
621: }
622:
623: if (d[i + 2] != 0x00) {
624: ret = -5;
625: goto _ERR;
626: }
627:
628: if (i < PS_MIN) { /* too short */
629: ret = -6;
630: goto _ERR;
631: }
632:
633: if (i == k - 3) { /* parse error */
634: ret = -7;
635: goto _ERR;
636: }
637:
638: n = k - 3 - i;
639: memmove(d, d + i + 3, n); /* ........ */
640:
641: mpz_clear(x);
642: mpz_clear(y);
643:
644: return (n);
645: _ERR:
646:
647: mpz_clear(x);
648: mpz_clear(y);
649: return (ret);
650: }
651:
652: int
653: rsa_encrypt_by_public_key(rsa_key *rsa, unsigned char *eb, const unsigned char *msg, int len, int padding)
654: {
655: return (rsa_encrypt(eb, msg, len, rsa->k, rsa->public_key, rsa->mod, RSA_PKCS_1_PADDING_PUBLIC));
656: }
657:
658: int
659: rsa_encrypt_by_private_key(rsa_key *rsa, unsigned char *eb, const unsigned char *msg, int len, int padding)
660: {
661: return (rsa_encrypt(eb, msg, len, rsa->k, rsa->private_key, rsa->mod, RSA_PKCS_1_PADDING_PRIVATE));
662: }
663:
664: int
665: rsa_decrypt_by_public_key(rsa_key *rsa, unsigned char *buf, const unsigned char *eb, int padding)
666: {
667: return (rsa_decrypt(buf, eb, rsa->k, rsa->public_key, rsa->mod, RSA_PKCS_1_PADDING_PUBLIC));
668: }
669:
670: int
671: rsa_decrypt_by_private_key(rsa_key *rsa, unsigned char *buf, const unsigned char *eb, int padding)
672: {
673: return (rsa_decrypt(buf, eb, rsa->k, rsa->private_key, rsa->mod, RSA_PKCS_1_PADDING_PRIVATE));
674: }
675:
676: