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

Revision 23095, 5.8 KB checked in by ghudson, 16 years ago (diff) |
---|

Rev | Line | |
---|---|---|

[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 | ||

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 | } |

**Note:**See TracBrowser for help on using the repository browser.