dsa_gen.c 8.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315
  1. /* crypto/dsa/dsa_gen.c */
  2. /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  3. * All rights reserved.
  4. *
  5. * This package is an SSL implementation written
  6. * by Eric Young (eay@cryptsoft.com).
  7. * The implementation was written so as to conform with Netscapes SSL.
  8. *
  9. * This library is free for commercial and non-commercial use as long as
  10. * the following conditions are aheared to. The following conditions
  11. * apply to all code found in this distribution, be it the RC4, RSA,
  12. * lhash, DES, etc., code; not just the SSL code. The SSL documentation
  13. * included with this distribution is covered by the same copyright terms
  14. * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15. *
  16. * Copyright remains Eric Young's, and as such any Copyright notices in
  17. * the code are not to be removed.
  18. * If this package is used in a product, Eric Young should be given attribution
  19. * as the author of the parts of the library used.
  20. * This can be in the form of a textual message at program startup or
  21. * in documentation (online or textual) provided with the package.
  22. *
  23. * Redistribution and use in source and binary forms, with or without
  24. * modification, are permitted provided that the following conditions
  25. * are met:
  26. * 1. Redistributions of source code must retain the copyright
  27. * notice, this list of conditions and the following disclaimer.
  28. * 2. Redistributions in binary form must reproduce the above copyright
  29. * notice, this list of conditions and the following disclaimer in the
  30. * documentation and/or other materials provided with the distribution.
  31. * 3. All advertising materials mentioning features or use of this software
  32. * must display the following acknowledgement:
  33. * "This product includes cryptographic software written by
  34. * Eric Young (eay@cryptsoft.com)"
  35. * The word 'cryptographic' can be left out if the rouines from the library
  36. * being used are not cryptographic related :-).
  37. * 4. If you include any Windows specific code (or a derivative thereof) from
  38. * the apps directory (application code) you must include an acknowledgement:
  39. * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40. *
  41. * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44. * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51. * SUCH DAMAGE.
  52. *
  53. * The licence and distribution terms for any publically available version or
  54. * derivative of this code cannot be changed. i.e. this code cannot simply be
  55. * copied and put under another distribution licence
  56. * [including the GNU Public Licence.]
  57. */
  58. #undef GENUINE_DSA
  59. #ifdef GENUINE_DSA
  60. /* Parameter generation follows the original release of FIPS PUB 186,
  61. * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180) */
  62. #define HASH EVP_sha()
  63. #else
  64. /* Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
  65. * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in
  66. * FIPS PUB 180-1) */
  67. #define HASH EVP_sha1()
  68. #endif
  69. #include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */
  70. #ifndef OPENSSL_NO_SHA
  71. #include <stdio.h>
  72. #include <time.h>
  73. #include "cryptlib.h"
  74. #include <openssl/evp.h>
  75. #include <openssl/bn.h>
  76. #include <openssl/dsa.h>
  77. #include <openssl/rand.h>
  78. #include <openssl/sha.h>
  79. static int dsa_builtin_paramgen(DSA *ret, int bits,
  80. unsigned char *seed_in, int seed_len,
  81. int *counter_ret, unsigned long *h_ret, BN_GENCB *cb);
  82. int DSA_generate_parameters_ex(DSA *ret, int bits,
  83. unsigned char *seed_in, int seed_len,
  84. int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
  85. {
  86. if(ret->meth->dsa_paramgen)
  87. return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
  88. counter_ret, h_ret, cb);
  89. return dsa_builtin_paramgen(ret, bits, seed_in, seed_len,
  90. counter_ret, h_ret, cb);
  91. }
  92. static int dsa_builtin_paramgen(DSA *ret, int bits,
  93. unsigned char *seed_in, int seed_len,
  94. int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
  95. {
  96. int ok=0;
  97. unsigned char seed[SHA_DIGEST_LENGTH];
  98. unsigned char md[SHA_DIGEST_LENGTH];
  99. unsigned char buf[SHA_DIGEST_LENGTH],buf2[SHA_DIGEST_LENGTH];
  100. BIGNUM *r0,*W,*X,*c,*test;
  101. BIGNUM *g=NULL,*q=NULL,*p=NULL;
  102. BN_MONT_CTX *mont=NULL;
  103. int k,n=0,i,b,m=0;
  104. int counter=0;
  105. int r=0;
  106. BN_CTX *ctx=NULL;
  107. unsigned int h=2;
  108. if (bits < 512) bits=512;
  109. bits=(bits+63)/64*64;
  110. if (seed_len < 20)
  111. seed_in = NULL; /* seed buffer too small -- ignore */
  112. if (seed_len > 20)
  113. seed_len = 20; /* App. 2.2 of FIPS PUB 186 allows larger SEED,
  114. * but our internal buffers are restricted to 160 bits*/
  115. if ((seed_in != NULL) && (seed_len == 20))
  116. memcpy(seed,seed_in,seed_len);
  117. if ((ctx=BN_CTX_new()) == NULL) goto err;
  118. if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
  119. BN_CTX_start(ctx);
  120. r0 = BN_CTX_get(ctx);
  121. g = BN_CTX_get(ctx);
  122. W = BN_CTX_get(ctx);
  123. q = BN_CTX_get(ctx);
  124. X = BN_CTX_get(ctx);
  125. c = BN_CTX_get(ctx);
  126. p = BN_CTX_get(ctx);
  127. test = BN_CTX_get(ctx);
  128. if (!BN_lshift(test,BN_value_one(),bits-1))
  129. goto err;
  130. for (;;)
  131. {
  132. for (;;) /* find q */
  133. {
  134. int seed_is_random;
  135. /* step 1 */
  136. if(!BN_GENCB_call(cb, 0, m++))
  137. goto err;
  138. if (!seed_len)
  139. {
  140. RAND_pseudo_bytes(seed,SHA_DIGEST_LENGTH);
  141. seed_is_random = 1;
  142. }
  143. else
  144. {
  145. seed_is_random = 0;
  146. seed_len=0; /* use random seed if 'seed_in' turns out to be bad*/
  147. }
  148. memcpy(buf,seed,SHA_DIGEST_LENGTH);
  149. memcpy(buf2,seed,SHA_DIGEST_LENGTH);
  150. /* precompute "SEED + 1" for step 7: */
  151. for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
  152. {
  153. buf[i]++;
  154. if (buf[i] != 0) break;
  155. }
  156. /* step 2 */
  157. EVP_Digest(seed,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
  158. EVP_Digest(buf,SHA_DIGEST_LENGTH,buf2,NULL,HASH, NULL);
  159. for (i=0; i<SHA_DIGEST_LENGTH; i++)
  160. md[i]^=buf2[i];
  161. /* step 3 */
  162. md[0]|=0x80;
  163. md[SHA_DIGEST_LENGTH-1]|=0x01;
  164. if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,q)) goto err;
  165. /* step 4 */
  166. r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
  167. seed_is_random, cb);
  168. if (r > 0)
  169. break;
  170. if (r != 0)
  171. goto err;
  172. /* do a callback call */
  173. /* step 5 */
  174. }
  175. if(!BN_GENCB_call(cb, 2, 0)) goto err;
  176. if(!BN_GENCB_call(cb, 3, 0)) goto err;
  177. /* step 6 */
  178. counter=0;
  179. /* "offset = 2" */
  180. n=(bits-1)/160;
  181. b=(bits-1)-n*160;
  182. for (;;)
  183. {
  184. if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
  185. goto err;
  186. /* step 7 */
  187. BN_zero(W);
  188. /* now 'buf' contains "SEED + offset - 1" */
  189. for (k=0; k<=n; k++)
  190. {
  191. /* obtain "SEED + offset + k" by incrementing: */
  192. for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
  193. {
  194. buf[i]++;
  195. if (buf[i] != 0) break;
  196. }
  197. EVP_Digest(buf,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
  198. /* step 8 */
  199. if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0))
  200. goto err;
  201. if (!BN_lshift(r0,r0,160*k)) goto err;
  202. if (!BN_add(W,W,r0)) goto err;
  203. }
  204. /* more of step 8 */
  205. if (!BN_mask_bits(W,bits-1)) goto err;
  206. if (!BN_copy(X,W)) goto err;
  207. if (!BN_add(X,X,test)) goto err;
  208. /* step 9 */
  209. if (!BN_lshift1(r0,q)) goto err;
  210. if (!BN_mod(c,X,r0,ctx)) goto err;
  211. if (!BN_sub(r0,c,BN_value_one())) goto err;
  212. if (!BN_sub(p,X,r0)) goto err;
  213. /* step 10 */
  214. if (BN_cmp(p,test) >= 0)
  215. {
  216. /* step 11 */
  217. r = BN_is_prime_fasttest_ex(p, DSS_prime_checks,
  218. ctx, 1, cb);
  219. if (r > 0)
  220. goto end; /* found it */
  221. if (r != 0)
  222. goto err;
  223. }
  224. /* step 13 */
  225. counter++;
  226. /* "offset = offset + n + 1" */
  227. /* step 14 */
  228. if (counter >= 4096) break;
  229. }
  230. }
  231. end:
  232. if(!BN_GENCB_call(cb, 2, 1))
  233. goto err;
  234. /* We now need to generate g */
  235. /* Set r0=(p-1)/q */
  236. if (!BN_sub(test,p,BN_value_one())) goto err;
  237. if (!BN_div(r0,NULL,test,q,ctx)) goto err;
  238. if (!BN_set_word(test,h)) goto err;
  239. if (!BN_MONT_CTX_set(mont,p,ctx)) goto err;
  240. for (;;)
  241. {
  242. /* g=test^r0%p */
  243. if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err;
  244. if (!BN_is_one(g)) break;
  245. if (!BN_add(test,test,BN_value_one())) goto err;
  246. h++;
  247. }
  248. if(!BN_GENCB_call(cb, 3, 1))
  249. goto err;
  250. ok=1;
  251. err:
  252. if (ok)
  253. {
  254. if(ret->p) BN_free(ret->p);
  255. if(ret->q) BN_free(ret->q);
  256. if(ret->g) BN_free(ret->g);
  257. ret->p=BN_dup(p);
  258. ret->q=BN_dup(q);
  259. ret->g=BN_dup(g);
  260. if (ret->p == NULL || ret->q == NULL || ret->g == NULL)
  261. {
  262. ok=0;
  263. goto err;
  264. }
  265. if ((m > 1) && (seed_in != NULL)) memcpy(seed_in,seed,20);
  266. if (counter_ret != NULL) *counter_ret=counter;
  267. if (h_ret != NULL) *h_ret=h;
  268. }
  269. if(ctx)
  270. {
  271. BN_CTX_end(ctx);
  272. BN_CTX_free(ctx);
  273. }
  274. if (mont != NULL) BN_MONT_CTX_free(mont);
  275. return ok;
  276. }
  277. #endif