![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to r_keygen.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [rsaref] / rsaref / source|
Return to r_keygen.c CVS log | Up to [rsaref] / rsaref / source |
1.1 root 1: /* R_KEYGEN.C - key-pair generation for RSAREF
2: */
3:
1.1.1.2 ! root 4: /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
! 5: Inc., created 1991. All rights reserved.
1.1 root 6: */
7:
8: #include "global.h"
9: #include "rsaref.h"
10: #include "r_random.h"
11: #include "nn.h"
12: #include "prime.h"
13:
1.1.1.2 ! root 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));
1.1 root 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],
1.1.1.2 ! root 30: qMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS], u[MAX_NN_DIGITS],
! 31: v[MAX_NN_DIGITS];
1.1 root 32: int status;
1.1.1.2 ! root 33: unsigned int nDigits, pBits, pDigits, qBits;
1.1 root 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;
1.1.1.2 ! root 40: pBits = (protoKey->bits + 1) / 2;
! 41: qBits = protoKey->bits - pBits;
1.1 root 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);
1.1.1.2 ! root 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));
1.1 root 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:
1.1.1.2 ! root 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;
1.1 root 166: {
167: int status;
1.1.1.2 ! root 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);
1.1 root 174:
1.1.1.2 ! root 175: status = NN_EQUAL (t, u, aDigits);
1.1 root 176:
177: /* Zeroize sensitive information.
178: */
179: R_memset ((POINTER)t, 0, sizeof (t));
180:
1.1.1.2 ! root 181: return (status);
1.1 root 182: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.