source: trunk/third/moira/util/rsaref/r_keygen.c @ 23095

Revision 23095, 5.8 KB checked in by ghudson, 16 years ago (diff)
Import the moira package from SIPB Debathena.
RevLine 
[23095]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
14static int RSAFilter PROTO_LIST
15  ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
16static 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 */
21int R_GeneratePEMKeys (publicKey, privateKey, protoKey, randomStruct)
22R_RSA_PUBLIC_KEY *publicKey;                          /* new RSA public key */
23R_RSA_PRIVATE_KEY *privateKey;                       /* new RSA private key */
24R_RSA_PROTO_KEY *protoKey;                             /* RSA prototype key */
25R_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 */
139static int RSAFilter (a, aDigits, b, bDigits)
140NN_DIGIT *a, *b;
141unsigned 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 */
163static int RelativelyPrime (a, aDigits, b, bDigits)
164NN_DIGIT *a, *b;
165unsigned 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}
Note: See TracBrowser for help on using the repository browser.