Return to r_keygen.c CVS log

Up to [PGP] / pgp / rsaref / source

Annotation of pgp/rsaref/source/r_keygen.c, revision 1.1

1.1     ! root        1: /* R_KEYGEN.C - key-pair generation for RSAREF
        !             2:  */
        !             3: 
        !             4: /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
        !             5:      Inc., created 1991. All rights reserved.
        !             6:  */
        !             7: 
        !             8: #include "global.h"
        !             9: #include "rsaref.h"
        !            10: #include "r_random.h"
        !            11: #include "nn.h"
        !            12: #include "prime.h"
        !            13: 
        !            14: static int RSAFilter PROTO_LIST
        !            15:   ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
        !            16: static int RelativelyPrime PROTO_LIST
        !            17:   ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
        !            18: 
        !            19: /* Generates an RSA key pair with a given length and public exponent.
        !            20:  */
        !            21: int R_GeneratePEMKeys (publicKey, privateKey, protoKey, randomStruct)
        !            22: R_RSA_PUBLIC_KEY *publicKey;                          /* new RSA public key */
        !            23: R_RSA_PRIVATE_KEY *privateKey;                       /* new RSA private key */
        !            24: R_RSA_PROTO_KEY *protoKey;                             /* RSA prototype key */
        !            25: R_RANDOM_STRUCT *randomStruct;                          /* random structure */
        !            26: {
        !            27:   NN_DIGIT d[MAX_NN_DIGITS], dP[MAX_NN_DIGITS], dQ[MAX_NN_DIGITS],
        !            28:     e[MAX_NN_DIGITS], n[MAX_NN_DIGITS], p[MAX_NN_DIGITS], phiN[MAX_NN_DIGITS],
        !            29:     pMinus1[MAX_NN_DIGITS], q[MAX_NN_DIGITS], qInv[MAX_NN_DIGITS],
        !            30:     qMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS], u[MAX_NN_DIGITS],
        !            31:     v[MAX_NN_DIGITS];
        !            32:   int status;
        !            33:   unsigned int nDigits, pBits, pDigits, qBits;
        !            34:   
        !            35:   if ((protoKey->bits < MIN_RSA_MODULUS_BITS) || 
        !            36:       (protoKey->bits > MAX_RSA_MODULUS_BITS))
        !            37:     return (RE_MODULUS_LEN);
        !            38:   nDigits = (protoKey->bits + NN_DIGIT_BITS - 1) / NN_DIGIT_BITS;
        !            39:   pDigits = (nDigits + 1) / 2;
        !            40:   pBits = (protoKey->bits + 1) / 2;
        !            41:   qBits = protoKey->bits - pBits;
        !            42: 
        !            43:   /* NOTE: for 65537, this assumes NN_DIGIT is at least 17 bits. */
        !            44:   NN_ASSIGN_DIGIT
        !            45:     (e, protoKey->useFermat4 ? (NN_DIGIT)65537 : (NN_DIGIT)3, nDigits);
        !            46: 
        !            47:   /* Generate prime p between 3*2^(pBits-2) and 2^pBits-1, searching
        !            48:        in steps of 2, until one satisfies gcd (p-1, e) = 1.
        !            49:    */
        !            50:   NN_Assign2Exp (t, pBits-1, pDigits);
        !            51:   NN_Assign2Exp (u, pBits-2, pDigits);
        !            52:   NN_Add (t, t, u, pDigits);
        !            53:   NN_ASSIGN_DIGIT (v, 1, pDigits);
        !            54:   NN_Sub (v, t, v, pDigits);
        !            55:   NN_Add (u, u, v, pDigits);
        !            56:   NN_ASSIGN_DIGIT (v, 2, pDigits);
        !            57:   do {
        !            58:     if (status = GeneratePrime (p, t, u, v, pDigits, randomStruct))
        !            59:       return (status);
        !            60:   }
        !            61:   while (! RSAFilter (p, pDigits, e, 1));
        !            62:   
        !            63:   /* Generate prime q between 3*2^(qBits-2) and 2^qBits-1, searching
        !            64:        in steps of 2, until one satisfies gcd (q-1, e) = 1.
        !            65:    */
        !            66:   NN_Assign2Exp (t, qBits-1, pDigits);
        !            67:   NN_Assign2Exp (u, qBits-2, pDigits);
        !            68:   NN_Add (t, t, u, pDigits);
        !            69:   NN_ASSIGN_DIGIT (v, 1, pDigits);
        !            70:   NN_Sub (v, t, v, pDigits);
        !            71:   NN_Add (u, u, v, pDigits);
        !            72:   NN_ASSIGN_DIGIT (v, 2, pDigits);
        !            73:   do {
        !            74:     if (status = GeneratePrime (q, t, u, v, pDigits, randomStruct))
        !            75:       return (status);
        !            76:   }
        !            77:   while (! RSAFilter (q, pDigits, e, 1));
        !            78:   
        !            79:   /* Sort so that p > q. (p = q case is extremely unlikely.)
        !            80:    */
        !            81:   if (NN_Cmp (p, q, pDigits) < 0) {
        !            82:     NN_Assign (t, p, pDigits);
        !            83:     NN_Assign (p, q, pDigits);
        !            84:     NN_Assign (q, t, pDigits);
        !            85:   }
        !            86: 
        !            87:   /* Compute n = pq, qInv = q^{-1} mod p, d = e^{-1} mod (p-1)(q-1),
        !            88:      dP = d mod p-1, dQ = d mod q-1.
        !            89:    */
        !            90:   NN_Mult (n, p, q, pDigits);
        !            91:   NN_ModInv (qInv, q, p, pDigits);
        !            92:   
        !            93:   NN_ASSIGN_DIGIT (t, 1, pDigits);
        !            94:   NN_Sub (pMinus1, p, t, pDigits);
        !            95:   NN_Sub (qMinus1, q, t, pDigits);
        !            96:   NN_Mult (phiN, pMinus1, qMinus1, pDigits);
        !            97: 
        !            98:   NN_ModInv (d, e, phiN, nDigits);
        !            99:   NN_Mod (dP, d, nDigits, pMinus1, pDigits);
        !           100:   NN_Mod (dQ, d, nDigits, qMinus1, pDigits);
        !           101:   
        !           102:   publicKey->bits = privateKey->bits = protoKey->bits;
        !           103:   NN_Encode (publicKey->modulus, MAX_RSA_MODULUS_LEN, n, nDigits);
        !           104:   NN_Encode (publicKey->exponent, MAX_RSA_MODULUS_LEN, e, 1);
        !           105:   R_memcpy 
        !           106:     ((POINTER)privateKey->modulus, (POINTER)publicKey->modulus,
        !           107:      MAX_RSA_MODULUS_LEN);
        !           108:   R_memcpy
        !           109:     ((POINTER)privateKey->publicExponent, (POINTER)publicKey->exponent,
        !           110:      MAX_RSA_MODULUS_LEN);
        !           111:   NN_Encode (privateKey->exponent, MAX_RSA_MODULUS_LEN, d, nDigits);
        !           112:   NN_Encode (privateKey->prime[0], MAX_RSA_PRIME_LEN, p, pDigits);
        !           113:   NN_Encode (privateKey->prime[1], MAX_RSA_PRIME_LEN, q, pDigits);
        !           114:   NN_Encode (privateKey->primeExponent[0], MAX_RSA_PRIME_LEN, dP, pDigits);
        !           115:   NN_Encode (privateKey->primeExponent[1], MAX_RSA_PRIME_LEN, dQ, pDigits);
        !           116:   NN_Encode (privateKey->coefficient, MAX_RSA_PRIME_LEN, qInv, pDigits);
        !           117:    
        !           118:   /* Zeroize sensitive information.
        !           119:    */
        !           120:   R_memset ((POINTER)d, 0, sizeof (d));
        !           121:   R_memset ((POINTER)dP, 0, sizeof (dP));
        !           122:   R_memset ((POINTER)dQ, 0, sizeof (dQ));
        !           123:   R_memset ((POINTER)p, 0, sizeof (p));
        !           124:   R_memset ((POINTER)phiN, 0, sizeof (phiN));
        !           125:   R_memset ((POINTER)pMinus1, 0, sizeof (pMinus1));
        !           126:   R_memset ((POINTER)q, 0, sizeof (q));
        !           127:   R_memset ((POINTER)qInv, 0, sizeof (qInv));
        !           128:   R_memset ((POINTER)qMinus1, 0, sizeof (qMinus1));
        !           129:   R_memset ((POINTER)t, 0, sizeof (t));
        !           130:   
        !           131:   return (0);
        !           132: }
        !           133: 
        !           134: /* Returns nonzero iff GCD (a-1, b) = 1.
        !           135: 
        !           136:    Lengths: a[aDigits], b[bDigits].
        !           137:    Assumes aDigits < MAX_NN_DIGITS, bDigits < MAX_NN_DIGITS.
        !           138:  */
        !           139: static int RSAFilter (a, aDigits, b, bDigits)
        !           140: NN_DIGIT *a, *b;
        !           141: unsigned int aDigits, bDigits;
        !           142: {
        !           143:   int status;
        !           144:   NN_DIGIT aMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS];
        !           145:   
        !           146:   NN_ASSIGN_DIGIT (t, 1, aDigits);
        !           147:   NN_Sub (aMinus1, a, t, aDigits);
        !           148:   
        !           149:   status = RelativelyPrime (aMinus1, aDigits, b, bDigits);
        !           150: 
        !           151:   /* Zeroize sensitive information.
        !           152:    */
        !           153:   R_memset ((POINTER)aMinus1, 0, sizeof (aMinus1));
        !           154:   
        !           155:   return (status);
        !           156: }
        !           157: 
        !           158: /* Returns nonzero iff a and b are relatively prime.
        !           159: 
        !           160:    Lengths: a[aDigits], b[bDigits].
        !           161:    Assumes aDigits >= bDigits, aDigits < MAX_NN_DIGITS.
        !           162:  */
        !           163: static int RelativelyPrime (a, aDigits, b, bDigits)
        !           164: NN_DIGIT *a, *b;
        !           165: unsigned int aDigits, bDigits;
        !           166: {
        !           167:   int status;
        !           168:   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
        !           169:   
        !           170:   NN_AssignZero (t, aDigits);
        !           171:   NN_Assign (t, b, bDigits);
        !           172:   NN_Gcd (t, a, t, aDigits);
        !           173:   NN_ASSIGN_DIGIT (u, 1, aDigits);
        !           174: 
        !           175:   status = NN_EQUAL (t, u, aDigits);
        !           176:   
        !           177:   /* Zeroize sensitive information.
        !           178:    */
        !           179:   R_memset ((POINTER)t, 0, sizeof (t));
        !           180:   
        !           181:   return (status);
        !           182: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.