]>
Commit | Line | Data |
---|---|---|
bd940221 | 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 | } |