![[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.2 ! iwane 1: /* $OpenXM: OpenXM/src/ox_ntl/crypt/rsa/gmprsa.c,v 1.1 2004/08/16 03:59:58 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:
15: #define RSA_KEY_PRINT 0
16:
17:
18: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
19: * CONV
20: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
21: static void
22: rsa_uchar2mpz(mpz_ptr z, const unsigned char *buf, int len)
23: {
24: char *str;
25: int i;
26: size_t size = len * 2 * sizeof(char) + 1;
27:
28: str = __gmp_allocate_func(size);
29: for (i = 0; i < len; i++)
30: sprintf(str + 2 * i, "%02x", buf[i]);
31:
32: mpz_set_str(z, str, 16);
33:
34: __gmp_free_func(str, size);
35: }
36:
37:
38: static int
39: rsa_char2ui(int ch)
40: {
41: if (ch >= '0' && ch <= '9')
42: return (ch - '0');
43: else if (ch >= 'a' && ch <= 'z')
44: return (ch - 'a' + 10);
45: else
46: return (ch - 'A' + 10);
47: }
48:
49: static void
50: rsa_mpz2uchar(unsigned char *str, int len, const mpz_ptr z)
51: {
52: char *ptr = mpz_get_str(NULL, 16, z);
53: int length = strlen(ptr);
54: int i = 0, j = 0;
55:
56: for (j = (length + 1) / 2; j < len; j++)
57: str[i++] = '\0';
58:
59: j = 0;
60:
61: if (length % 2 != 0) {
62: str[i++] = rsa_char2ui(ptr[j++]);
63: }
64:
65: for (; i < len && j < length; i++, j += 2) {
66: str[i] = rsa_char2ui(ptr[j]) * 16 + rsa_char2ui(ptr[j + 1]);
67: }
68: str[i] = '\0';
69:
70: __gmp_free_func(ptr, length);
71: }
72:
73:
74: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
75: * INITIALIZE
76: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
77: void
78: rsa_init(rsa_key *r)
79: {
80: mpz_init(r->p);
81: mpz_init(r->q);
82: mpz_init(r->mod);
83: mpz_init(r->private_key);
84: mpz_init_set_si(r->public_key, 11);
85: }
86:
87: void
88: rsa_clear(rsa_key *r)
89: {
90: mpz_clear(r->p);
91: mpz_clear(r->q);
92: mpz_clear(r->mod);
93: mpz_clear(r->public_key);
94: mpz_clear(r->private_key);
95:
96: }
97: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
98: * PRIME
99: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
100: void
101: rsa_genprime(mpz_ptr prime, int len, const mpz_ptr seed, int rep)
102: {
103: const int LOOP = 4096;
104: const int BLOCK = 160;
105: int n, b;
106: int offset = 2;
107: int k, c, i;
108: int shalen;
109: mpz_t s, s1, sp;
110: unsigned char sha[32];
111: char *str;
112:
1.2 ! iwane 113: if (len < 2) {
! 114: mpz_set_ui(prime, 3);
! 115: return ;
! 116: }
! 117:
1.1 iwane 118: n = (len - 1) / BLOCK;
119: b = (len - 1) % BLOCK;
120:
121: mpz_init(s);
122: mpz_init(s1);
123: mpz_init(sp);
124:
125:
126: __RETRY:
127: for (c = 0; c < LOOP; c++) {
128: mpz_set_ui(prime, 0);
129: mpz_setbit(prime, len - 1);
130:
131: for (k = 0; k <= n; k++) {
132: mpz_add_ui(s1, seed, offset + c + k);
133:
134: str = mpz_get_str(NULL, 16, s1);
135: shalen = strlen(str);
136: sha1(sha, str, shalen);
137: __gmp_free_func(str, shalen);
138:
139: rsa_uchar2mpz(s, sha, 20);
140:
141: mpz_mul_2exp(sp, s, 160 * k);
142:
143: mpz_add(prime, prime, sp);
144:
145: offset += n + 1;
146: }
147:
148:
149: mpz_setbit(prime, 0);
150: mpz_setbit(prime, len - 1);
151: for (i = (n + 1) * BLOCK; i >= len; i--)
152: mpz_clrbit(prime, i);
153:
154:
155: #if RSA_KEY_PRINT
156: fprintf(stderr, "*"); fflush(stderr);
157: #endif
158: /* prime test */
159: if (mpz_probab_prime_p(prime, rep))
160: break;
161: }
162:
163: #if RSA_KEY_PRINT
164: fprintf(stderr, "+"); fflush(stderr);
165: #endif
166:
167: if (c == LOOP) {
168: offset += c + 13;
169: goto __RETRY;
170: }
171:
172: mpz_clear(s);
173: mpz_clear(s1);
174: mpz_clear(sp);
175:
176: }
177:
178:
179: static int
180: rsa_get_block_size(const mpz_ptr n)
181: {
182: return ((mpz_sizeinbase(n, 16) + 1) / 2);
183: }
184:
185:
186: /*
187: *
188: * bit >= 96 must
189: * rep >= 80 should
190: *
191: */
192: int
193: rsa_keygen(
194: rsa_key *rsa,
195: const mpz_ptr _seed1, const mpz_ptr _seed2,
196: unsigned int bit,
197: int rep)
198: {
199: int bitp, bitq;
200: mpz_t gcd;
201: mpz_t phi;
202: mpz_t seed1, seed2;
203:
204: /* 12 = PS_MIN + 3 + 1 */
205: if (bit < 12 * 8)
206: return (-1); /* too short */
207:
208:
209: bitp = bit / 2;
210: bitq = bit - bitp;
211:
212: mpz_init_set_ui(gcd, 1);
213: mpz_init(phi);
214:
215: mpz_init_set(seed1, _seed1);
216: mpz_init_set(seed2, _seed2);
217:
218: for (;;) {
219: if (mpz_cmp(seed1, seed2) == 0)
220: goto _NEXT;
221:
222: rsa_genprime(rsa->p, bitp, seed1, rep);
223: rsa_genprime(rsa->q, bitq, seed2, rep);
224:
225: mpz_clrbit(rsa->p, 0);
226: mpz_clrbit(rsa->q, 0);
227:
228: mpz_mul(phi, rsa->p, rsa->q);
229:
230: mpz_gcd(gcd, rsa->public_key, phi);
231: #if RSA_KEY_PRINT
232: fprintf(stderr, "@"); fflush(stderr);
233: #endif
234: if (mpz_cmp_ui(gcd, 1) != 0)
235: goto _NEXT;
236:
237: if (mpz_cmp(rsa->p, rsa->q) == 0)
238: goto _NEXT;
239:
240: break;
241:
242: _NEXT:
243: mpz_add(seed1, seed1, gcd);
244: mpz_sub(seed2, seed2, gcd);
245: }
246:
247: mpz_setbit(rsa->p, 0);
248: mpz_setbit(rsa->q, 0);
249:
250: mpz_invert(rsa->private_key, rsa->public_key, phi);
251:
252: mpz_mul(rsa->mod, rsa->p, rsa->q);
253:
254: rsa->k = rsa_get_block_size(rsa->mod);
255:
256: mpz_clear(gcd);
257: mpz_clear(phi);
258:
259: mpz_clear(seed1);
260: mpz_clear(seed2);
261:
262: return (0);
263: }
264:
265:
266: void
267: rsa_set_publickey(
268: rsa_key *rsa,
269: mpz_ptr public_key,
270: mpz_ptr mod)
271: {
272: mpz_set(rsa->mod, mod);
273: mpz_set(rsa->public_key, public_key);
274: rsa->k = rsa_get_block_size(rsa->mod);
275: }
276:
277: void
278: rsa_set_key(
279: rsa_key *rsa,
280: mpz_ptr public_key,
281: mpz_ptr private_key,
282: mpz_ptr mod)
283: {
284: mpz_set(rsa->private_key, private_key);
285: rsa_set_publickey(rsa, public_key, mod);
286: }
287:
288: /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
289: * ENCRYPT
290: *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
291: static int
292: rsa_encrypt(
293: unsigned char *eb,
294: const unsigned char *msg,
295: int size,
296: int k,
297: const mpz_ptr c,
298: const mpz_ptr mod,
299: int padding)
300: {
301: const int PS_MIN = 8;
302: const int OCTET_SIZE = 256;
303:
304: int i;
305: int s; /* length of data */
306: int ps; /* length of padding string */
307: const int DATA_MAX = k - PS_MIN - 3;
308: mpz_t x, y, ebz;
309:
310: if (k <= 0)
311: return (-2);
312:
313: mpz_init(x);
314: mpz_init(y);
315: mpz_init(ebz);
316:
317:
318: /* k == ps + s + 3 */
319: if (size > DATA_MAX) {
320: s = DATA_MAX;
321: ps = PS_MIN;
322: } else {
323: s = size;
324: ps = DATA_MAX - size + PS_MIN;
325: }
326:
327: /*-------------------------------------------------------------------*
328: * Encryption-block formatting
329: *-------------------------------------------------------------------*/
330: eb[0] = 0x00;
331: eb[1] = padding;
332:
333:
334: switch (padding) {
335: case RSA_PKCS_1_PADDING_PUBLIC:
336: for (i = 0; i < ps; i++) {
337: /* 0 < random number < 255 */
338: eb[i + 2] = (unsigned char)(random() % (OCTET_SIZE - 1) + 1);
339: }
340: break;
341: case RSA_PKCS_1_PADDING_PRIVATE:
342: for (i = 0; i < ps; i++) {
343: eb[i + 2] = 0xff;
344: }
345: break;
346: case RSA_PKCS_1_PADDING_PRIVATE0:
347: for (i = 0; i < ps; i++) {
348: eb[i + 2] = 0x00;
349: }
350: break;
351: default:
352: mpz_clear(x);
353: mpz_clear(y);
354: mpz_clear(ebz);
355: return (-1);
356: }
357:
358: eb[ps + 2] = 0x00;
359: for (i = 0; i < s; i++) {
360: eb[ps + 3 + i] = *msg++;
361: }
362:
363:
364: /*-------------------------------------------------------------------*
365: * Octet-string-to-integer conversion
366: *-------------------------------------------------------------------*/
367: rsa_uchar2mpz(x, eb, k);
368:
369: /*-------------------------------------------------------------------*
370: * RSA computation
371: *-------------------------------------------------------------------*/
372: mpz_powm(y, x, c, mod);
373:
374: /*-------------------------------------------------------------------*
375: * Integer-to-octet-string conversion
376: *-------------------------------------------------------------------*/
377: rsa_mpz2uchar(eb, k, y);
378:
379:
380: mpz_clear(x);
381: mpz_clear(y);
382: mpz_clear(ebz);
383:
384: return (s);
385: }
386:
387:
388: /****************************************************************************
389: * RSA decryption.
390: *
391: * MEMO: 平文が 0x00 で始まるよう瘢雹なメッセ・踉札犬陸苳詞合,
392: * 正しく復号化することができない.
393: *
394: ****************************************************************************/
395: static int
396: rsa_decrypt(
397: unsigned char *d,
398: const unsigned char *eb,
399: int k,
400: const mpz_ptr exp,
401: const mpz_ptr mod,
402: int padding)
403: {
404: const int PS_MIN = 8;
405:
406: mpz_t x, y;
407: int i, n, bt;
408: int ret = 0;
409:
410: mpz_init(x);
411: mpz_init(y);
412:
413: /*--------------------------------------------------------------------*
414: * Octet-string-to-integer
415: *--------------------------------------------------------------------*/
416: rsa_uchar2mpz(y, eb, k);
417:
418: /* error check */
419: if (mpz_cmp(y, mod) >= 0 || mpz_sgn(y) < 0) {
420: ret = -1;
421: goto _ERR;
422: }
423:
424: /*--------------------------------------------------------------------*
425: * RSA computation
426: *--------------------------------------------------------------------*/
427: mpz_powm(x, y, exp, mod);
428:
429: /*--------------------------------------------------------------------*
430: * Integer-to-octet-string
431: *--------------------------------------------------------------------*/
432: rsa_mpz2uchar(d, k, x);
433:
434:
435: /*--------------------------------------------------------------------*
436: * Encryption-block parsing
437: * EB = 00 || BT || PS || 00 || D
438: *--------------------------------------------------------------------*/
439: if (d[0] != 0x00) {
440: ret = -2;
441: goto _ERR;
442: }
443:
444:
445: if (padding == RSA_PKCS_1_PADDING_PUBLIC) { /* public key */
446: bt = d[1];
447:
448: if (bt != RSA_PKCS_1_PADDING_PRIVATE0 && bt != RSA_PKCS_1_PADDING_PRIVATE) {
449: ret = -3;
450: goto _ERR;
451: }
452:
453: if (bt == RSA_PKCS_1_PADDING_PRIVATE0) {
454: for (i = 0; i < k - 3; i++) {
455: if (d[i + 2] != 0x00) {
456: i--;
457: break;
458: }
459: }
460: } else {
461: for (i = 0; i < k - 3; i++) {
462: if (d[i + 2] != 0xff) {
463: break;
464: }
465: }
466: }
467: } else { /* private key */
468:
469: if (d[1] != RSA_PKCS_1_PADDING_PUBLIC) {
470: ret = -4;
471: goto _ERR;
472: }
473:
474: for (i = 0; i < k - 3; i++) {
475: if (d[i + 2] == 0x00) {
476: break;
477: }
478: }
479: }
480:
481: if (d[i + 2] != 0x00) {
482: ret = -5;
483: goto _ERR;
484: }
485:
486: if (i < PS_MIN) { /* too short */
487: ret = -6;
488: goto _ERR;
489: }
490:
491: if (i == k - 3) { /* parse error */
492: ret = -7;
493: goto _ERR;
494: }
495:
496: n = k - 3 - i;
497: memmove(d, d + i + 3, n); /* ........ */
498:
499: mpz_clear(x);
500: mpz_clear(y);
501:
502: return (n);
503: _ERR:
504:
505: mpz_clear(x);
506: mpz_clear(y);
507: return (ret);
508: }
509:
510: int
511: rsa_encrypt_by_public_key(rsa_key *rsa, unsigned char *eb, const unsigned char *msg, int len, int padding)
512: {
513: return (rsa_encrypt(eb, msg, len, rsa->k, rsa->public_key, rsa->mod, RSA_PKCS_1_PADDING_PUBLIC));
514: }
515:
516: int
517: rsa_encrypt_by_private_key(rsa_key *rsa, unsigned char *eb, const unsigned char *msg, int len, int padding)
518: {
519: return (rsa_encrypt(eb, msg, len, rsa->k, rsa->private_key, rsa->mod, RSA_PKCS_1_PADDING_PRIVATE));
520: }
521:
522: int
523: rsa_decrypt_by_public_key(rsa_key *rsa, unsigned char *buf, const unsigned char *eb, int padding)
524: {
525: return (rsa_decrypt(buf, eb, rsa->k, rsa->public_key, rsa->mod, RSA_PKCS_1_PADDING_PUBLIC));
526: }
527:
528: int
529: rsa_decrypt_by_private_key(rsa_key *rsa, unsigned char *buf, const unsigned char *eb, int padding)
530: {
531: return (rsa_decrypt(buf, eb, rsa->k, rsa->private_key, rsa->mod, RSA_PKCS_1_PADDING_PRIVATE));
532: }
533:
534: