util/rsaref/r_keygen.c

   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 }