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