2 * dh.c: Diffie Hellman implementation.
4 * Code copied from openssl distribution and
5 * Modified just enough so that compiles and runs standalone
7 * Copyright (C) 2010, Broadcom Corporation. All Rights Reserved.
9 * Permission to use, copy, modify, and/or distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
16 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
18 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
19 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 * $Id: dh.c,v 1.9.108.1 2010-08-13 18:00:15 Exp $
23 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
24 * All rights reserved.
26 * This package is an SSL implementation written
27 * by Eric Young (eay@cryptsoft.com).
28 * The implementation was written so as to conform with Netscapes SSL.
30 * This library is free for commercial and non-commercial use as long as
31 * the following conditions are aheared to. The following conditions
32 * apply to all code found in this distribution, be it the RC4, RSA,
33 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
34 * included with this distribution is covered by the same copyright terms
35 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
37 * Copyright remains Eric Young's, and as such any Copyright notices in
38 * the code are not to be removed.
39 * If this package is used in a product, Eric Young should be given attribution
40 * as the author of the parts of the library used.
41 * This can be in the form of a textual message at program startup or
42 * in documentation (online or textual) provided with the package.
44 * Redistribution and use in source and binary forms, with or without
45 * modification, are permitted provided that the following conditions
47 * 1. Redistributions of source code must retain the copyright
48 * notice, this list of conditions and the following disclaimer.
49 * 2. Redistributions in binary form must reproduce the above copyright
50 * notice, this list of conditions and the following disclaimer in the
51 * documentation and/or other materials provided with the distribution.
52 * 3. All advertising materials mentioning features or use of this software
53 * must display the following acknowledgement:
54 * "This product includes cryptographic software written by
55 * Eric Young (eay@cryptsoft.com)"
56 * The word 'cryptographic' can be left out if the rouines from the library
57 * being used are not cryptographic related :-).
58 * 4. If you include any Windows specific code (or a derivative thereof) from
59 * the apps directory (application code) you must include an acknowledgement:
60 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
62 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
63 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
64 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
65 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
66 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
67 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
68 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
69 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
70 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
71 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
74 * The licence and distribution terms for any publically available version or
75 * derivative of this code cannot be changed. i.e. this code cannot simply be
76 * copied and put under another distribution licence
77 * [including the GNU Public Licence.]
85 /* #include <shutils.h> */
87 #include <bcmcrypto/dh.h>
89 #define OPENSSL_malloc malloc
90 #define OPENSSL_free free
93 static int dh_bn_mod_exp(const DH
*dh
, BIGNUM
*r
,
94 const BIGNUM
*a
, const BIGNUM
*p
,
95 const BIGNUM
*m
, BN_CTX
*ctx
,
102 static int bn_print(const BIGNUM
*a
);
103 static void cb(int p
, int n
, void *arg
);
105 unsigned char data192
[] = {
106 0xD4, 0xA0, 0xBA, 0x02, 0x50, 0xB6, 0xFD, 0x2E,
107 0xC6, 0x26, 0xE7, 0xEF, 0xD6, 0x37, 0xDF, 0x76,
108 0xC7, 0x16, 0xE2, 0x2D, 0x09, 0x44, 0xB8, 0x8B
111 unsigned char data512
[] = {
112 0xDA, 0x58, 0x3C, 0x16, 0xD9, 0x85, 0x22, 0x89,
113 0xD0, 0xE4, 0xAF, 0x75, 0x6F, 0x4C, 0xCA, 0x92,
114 0xDD, 0x4B, 0xE5, 0x33, 0xB8, 0x04, 0xFB, 0x0F,
115 0xED, 0x94, 0xEF, 0x9C, 0x8A, 0x44, 0x03, 0xED,
116 0x57, 0x46, 0x50, 0xD3, 0x69, 0x99, 0xDB, 0x29,
117 0xD7, 0x76, 0x27, 0x6B, 0xA2, 0xD3, 0xD4, 0x12,
118 0xE2, 0x18, 0xF4, 0xDD, 0x1E, 0x08, 0x4C, 0xF6,
119 0xD8, 0x00, 0x3E, 0x7C, 0x47, 0x74, 0xE8, 0x33
122 unsigned char data1024
[] = {
123 0x97, 0xF6, 0x42, 0x61, 0xCA, 0xB5, 0x05, 0xDD,
124 0x28, 0x28, 0xE1, 0x3F, 0x1D, 0x68, 0xB6, 0xD3,
125 0xDB, 0xD0, 0xF3, 0x13, 0x04, 0x7F, 0x40, 0xE8,
126 0x56, 0xDA, 0x58, 0xCB, 0x13, 0xB8, 0xA1, 0xBF,
127 0x2B, 0x78, 0x3A, 0x4C, 0x6D, 0x59, 0xD5, 0xF9,
128 0x2A, 0xFC, 0x6C, 0xFF, 0x3D, 0x69, 0x3F, 0x78,
129 0xB2, 0x3D, 0x4F, 0x31, 0x60, 0xA9, 0x50, 0x2E,
130 0x3E, 0xFA, 0xF7, 0xAB, 0x5E, 0x1A, 0xD5, 0xA6,
131 0x5E, 0x55, 0x43, 0x13, 0x82, 0x8D, 0xA8, 0x3B,
132 0x9F, 0xF2, 0xD9, 0x41, 0xDE, 0xE9, 0x56, 0x89,
133 0xFA, 0xDA, 0xEA, 0x09, 0x36, 0xAD, 0xDF, 0x19,
134 0x71, 0xFE, 0x63, 0x5B, 0x20, 0xAF, 0x47, 0x03,
135 0x64, 0x60, 0x3C, 0x2D, 0xE0, 0x59, 0xF5, 0x4B,
136 0x65, 0x0A, 0xD8, 0xFA, 0x0C, 0xF7, 0x01, 0x21,
137 0xC7, 0x47, 0x99, 0xD7, 0x58, 0x71, 0x32, 0xBE,
138 0x9B, 0x99, 0x9B, 0xB9, 0xB7, 0x87, 0xE8, 0xAB
141 /* uncomment this and write a matching function when testing on another OS */
143 #define BCMDH_TEST_LINUX
146 #ifdef BCMDH_TEST_LINUX
148 #define dbg(fmt, arg...) printf(fmt, ##arg)
150 #endif /* BCMDH_TEST_LINUX */
154 main(int argc
, char *argv
[])
158 unsigned char *abuf
= NULL
, *bbuf
= NULL
;
159 unsigned char *apubbuf
= NULL
, *bpubbuf
= NULL
;
160 int i
, alen
, blen
, apublen
, bpublen
, aout
, bout
, ret
= 1, size
= 0;
163 while ((opt
= getopt(argc
, argv
, "s:")) != EOF
) {
166 size
= (int)strtoul(optarg
, NULL
, 0);
169 dbg("invalid option");
174 #ifdef BCMDH_TEST_LINUX
176 extern void linux_random(uint8
*rand
, int len
);
177 BN_register_RAND(linux_random
);
182 a
= DH_init(data192
, sizeof(data192
), 3);
183 } else if (size
== 512) {
184 a
= DH_init(data512
, sizeof(data512
), 2);
185 } else if (size
== 1024) {
186 a
= DH_init(data1024
, sizeof(data1024
), 2);
188 a
= DH_generate_parameters(NULL
, 64, DH_GENERATOR_5
, cb
, NULL
);
189 if (a
== NULL
) goto err
;
192 if (!DH_check(a
, &i
)) goto err
;
193 if (i
& DH_CHECK_P_NOT_PRIME
)
194 dbg("p value is not prime\n");
195 if (i
& DH_CHECK_P_NOT_SAFE_PRIME
)
196 dbg("p value is not a safe prime\n");
197 if (i
& DH_UNABLE_TO_CHECK_GENERATOR
)
198 dbg("unable to check the generator value\n");
199 if (i
& DH_NOT_SUITABLE_GENERATOR
)
200 dbg("the g value is not a generator\n");
209 if (b
== NULL
) goto err
;
213 if ((b
->p
== NULL
) || (b
->g
== NULL
)) goto err
;
215 apubbuf
= (unsigned char *)OPENSSL_malloc(DH_size(a
));
216 /* dbg("%s\n", file2str("/proc/uptime")); */
217 if (!(apublen
= DH_generate_key(apubbuf
, a
))) goto err
;
218 /* dbg("%s\n", file2str("/proc/uptime")); */
220 bn_print(a
->priv_key
);
222 for (i
= 0; i
< apublen
; i
++) dbg("%02X", apubbuf
[i
]);
225 bpubbuf
= (unsigned char *)OPENSSL_malloc(DH_size(b
));
226 if (!(bpublen
= DH_generate_key(bpubbuf
, b
))) goto err
;
228 bn_print(b
->priv_key
);
230 for (i
= 0; i
< bpublen
; i
++) dbg("%02X", bpubbuf
[i
]);
234 abuf
= (unsigned char *)OPENSSL_malloc(alen
);
235 /* dbg("%s\n", file2str("/proc/uptime")); */
236 aout
= DH_compute_key(abuf
, bpubbuf
, bpublen
, a
);
237 /* dbg("%s\n", file2str("/proc/uptime")); */
240 for (i
= 0; i
< aout
; i
++) dbg("%02X", abuf
[i
]);
244 bbuf
= (unsigned char *)OPENSSL_malloc(blen
);
245 bout
= DH_compute_key(bbuf
, apubbuf
, apublen
, b
);
248 for (i
= 0; i
< bout
; i
++) dbg("%02X", abuf
[i
]);
251 if ((aout
< 4) || (bout
!= aout
) || (memcmp(abuf
, bbuf
, aout
) != 0))
256 if (abuf
!= NULL
) OPENSSL_free(abuf
);
257 if (bbuf
!= NULL
) OPENSSL_free(bbuf
);
258 if (b
!= NULL
) DH_free(b
);
259 if (a
!= NULL
) DH_free(a
);
260 fprintf(stderr
, "%s: %s\n", *argv
, ret
?"FAILED":"PASSED");
265 cb(int p
, int n
, void *arg
)
267 if (p
== 0) dbg(".");
268 if (p
== 1) dbg("+");
269 if (p
== 2) dbg("*");
270 if (p
== 3) dbg("\n");
273 static const char *Hex
= "0123456789ABCDEF";
276 bn_print(const BIGNUM
*a
)
281 if ((a
->neg
) && (dbg("-") != 1)) goto end
;
282 if ((a
->top
== 0) && (dbg("0") != 1)) goto end
;
283 for (i
= a
->top
- 1; i
>= 0; i
--) {
284 for (j
= BN_BITS2
- 4; j
>= 0; j
-= 4) {
285 /* strip leading zeros */
286 v
= ((int)(a
->d
[i
] >> (long)j
)) & 0x0f;
298 int DH_size(const DH
*dh
)
300 return (BN_num_bytes(dh
->p
));
303 /* We generate DH parameters as follows
304 * find a prime q which is prime_len/2 bits long.
305 * p=(2*q)+1 or (p-1)/2 = q
306 * For this case, g is a generator if
307 * g^((p-1)/q) mod p != 1 for values of q which are the factors of p-1.
308 * Since the factors of p-1 are q and 2, we just need to check
309 * g^2 mod p != 1 and g^q mod p != 1.
311 * Having said all that,
312 * there is another special case method for the generators 2, 3 and 5.
313 * for 2, p mod 24 == 11
314 * for 3, p mod 12 == 5 <<<<< does not work for safe primes.
315 * for 5, p mod 10 == 3 or 7
317 * Thanks to Phil Karn <karn@qualcomm.com> for the pointers about the
318 * special generators and for answering some of my questions.
320 * I've implemented the second simple method :-).
321 * Since DH should be using a safe prime (both p and q are prime),
322 * this generator function can take a very very long time to run.
324 /* Actually there is no reason to insist that 'generator' be a generator.
325 * It's just as OK (and in some sense better) to use a generator of the
329 DH_generate_parameters(DH
* dh
, int prime_len
, int generator
,
330 void (*callback
)(int, int, void *), void *cb_arg
)
332 BIGNUM
*p
= NULL
, *t1
, *t2
;
337 ret
= dh
? dh
: DH_new();
338 if (ret
== NULL
) goto err
;
340 if (ctx
== NULL
) goto err
;
342 t1
= BN_CTX_get(ctx
);
343 t2
= BN_CTX_get(ctx
);
344 if (t1
== NULL
|| t2
== NULL
) goto err
;
346 if (generator
<= 1) {
349 if (generator
== DH_GENERATOR_2
) {
350 if (!BN_set_word(t1
, 24)) goto err
;
351 if (!BN_set_word(t2
, 11)) goto err
;
355 else if (generator
== DH_GENERATOR_5
) {
356 if (!BN_set_word(t1
, 10)) goto err
;
357 if (!BN_set_word(t2
, 3)) goto err
;
358 /* BN_set_word(t3, 7); just have to miss
359 * out on these ones :-(
363 /* in the general case, don't worry if 'generator' is a
364 * generator or not: since we are using safe primes,
365 * it will generate either an order-q or an order-2q group,
368 if (!BN_set_word(t1
, 2)) goto err
;
369 if (!BN_set_word(t2
, 1)) goto err
;
373 p
= BN_generate_prime(NULL
, prime_len
, 1, t1
, t2
, callback
, cb_arg
);
374 if (p
== NULL
) goto err
;
375 if (callback
!= NULL
) callback(3, 0, cb_arg
);
378 if (!BN_set_word(ret
->g
, g
)) goto err
;
389 if (!ok
&& (ret
!= NULL
)) {
396 /* Check that p is a safe prime and
397 * if g is 2, 3 or 5, check that is is a suitable generator
399 * for 2, p mod 24 == 11
400 * for 3, p mod 12 == 5
401 * for 5, p mod 10 == 3 or 7
406 DH_check(const DH
*dh
, int *ret
)
415 if (ctx
== NULL
) goto err
;
417 if (q
== NULL
) goto err
;
419 if (BN_is_word(dh
->g
, DH_GENERATOR_2
)) {
420 l
= BN_mod_word(dh
->p
, 24);
421 if (l
!= 11) *ret
|= DH_NOT_SUITABLE_GENERATOR
;
424 else if (BN_is_word(dh
->g
, DH_GENERATOR_5
)) {
425 l
= BN_mod_word(dh
->p
, 10);
426 if ((l
!= 3) && (l
!= 7))
427 *ret
|= DH_NOT_SUITABLE_GENERATOR
;
429 *ret
|= DH_UNABLE_TO_CHECK_GENERATOR
;
431 if (!BN_is_prime(dh
->p
, BN_prime_checks
, NULL
, ctx
, NULL
))
432 *ret
|= DH_CHECK_P_NOT_PRIME
;
434 if (!BN_rshift1(q
, dh
->p
)) goto err
;
435 if (!BN_is_prime(q
, BN_prime_checks
, NULL
, ctx
, NULL
))
436 *ret
|= DH_CHECK_P_NOT_SAFE_PRIME
;
440 if (ctx
!= NULL
) BN_CTX_free(ctx
);
441 if (q
!= NULL
) BN_free(q
);
445 #endif /* BCMDH_TEST */
452 ret
= (DH
*)OPENSSL_malloc(sizeof(DH
));
461 ret
->priv_key
= NULL
;
467 ret
->method_mont_p
= NULL
;
468 ret
->flags
= DH_FLAG_CACHE_MONT_P
;
475 if (r
== NULL
) return;
476 if (r
->p
!= NULL
) BN_clear_free(r
->p
);
477 if (r
->g
!= NULL
) BN_clear_free(r
->g
);
478 if (r
->q
!= NULL
) BN_clear_free(r
->q
);
479 if (r
->j
!= NULL
) BN_clear_free(r
->j
);
480 if (r
->seed
) OPENSSL_free(r
->seed
);
481 if (r
->counter
!= NULL
) BN_clear_free(r
->counter
);
482 if (r
->pub_key
!= NULL
) BN_clear_free(r
->pub_key
);
483 if (r
->priv_key
!= NULL
) BN_clear_free(r
->priv_key
);
484 if (r
->method_mont_p
)
485 BN_MONT_CTX_free((BN_MONT_CTX
*)r
->method_mont_p
);
490 DH_generate_key(unsigned char *pubbuf
, DH
*dh
)
496 BIGNUM
*pub_key
= NULL
, *priv_key
= NULL
;
499 if (dh
->pub_key
!= NULL
) {
501 return BN_bn2bin(dh
->pub_key
, pubbuf
);
503 return BN_num_bytes(dh
->pub_key
);
505 /* first time in here */
507 if (priv_key
== NULL
) goto err
;
510 if (pub_key
== NULL
) goto err
;
513 if (ctx
== NULL
) goto err
;
515 if (dh
->flags
& DH_FLAG_CACHE_MONT_P
) {
516 if ((dh
->method_mont_p
= BN_MONT_CTX_new()) != NULL
)
517 if (!BN_MONT_CTX_set((BN_MONT_CTX
*)dh
->method_mont_p
,
522 mont
= (BN_MONT_CTX
*)dh
->method_mont_p
;
524 l
= dh
->length
? dh
->length
: BN_num_bits(dh
->p
)-1; /* secret exponent length */
525 if (!BN_rand(priv_key
, l
, 0, 0))
527 if (!dh_bn_mod_exp(dh
, pub_key
, dh
->g
, priv_key
, dh
->p
, ctx
, mont
))
530 dh
->pub_key
= pub_key
;
531 dh
->priv_key
= priv_key
;
533 ret
= BN_bn2bin(pub_key
, pubbuf
);
535 ret
= BN_num_bytes(dh
->pub_key
);
537 if ((pub_key
!= NULL
) && (dh
->pub_key
== NULL
))
539 if ((priv_key
!= NULL
) && (dh
->priv_key
== NULL
))
548 DH_compute_key_bn(unsigned char *key
, BIGNUM
*peer_key
, DH
*dh
)
556 if (ctx
== NULL
) goto err
;
558 tmp
= BN_CTX_get(ctx
);
560 if (dh
->priv_key
== NULL
) {
563 if ((dh
->method_mont_p
== NULL
) && (dh
->flags
& DH_FLAG_CACHE_MONT_P
)) {
564 if ((dh
->method_mont_p
= BN_MONT_CTX_new()) != NULL
)
565 if (!BN_MONT_CTX_set((BN_MONT_CTX
*)dh
->method_mont_p
,
570 mont
= (BN_MONT_CTX
*)dh
->method_mont_p
;
571 if (!dh_bn_mod_exp(dh
, tmp
, peer_key
, dh
->priv_key
, dh
->p
, ctx
, mont
)) {
575 ret
= BN_bn2bin(tmp
, key
);
578 BN_clear_free(peer_key
);
586 DH_compute_key(unsigned char *key
, unsigned char *pubbuf
, int buflen
, DH
*dh
)
588 BIGNUM
*peer_key
= NULL
;
590 peer_key
= BN_bin2bn(pubbuf
, buflen
, NULL
);
591 return DH_compute_key_bn(key
, peer_key
, dh
);
595 DH_init(unsigned char *pbuf
, int plen
, int g
)
600 dh
->p
= BN_bin2bn(pbuf
, plen
, NULL
);
602 BN_set_word(dh
->g
, g
);
607 dh_bn_mod_exp(const DH
*dh
, BIGNUM
*r
,
608 const BIGNUM
*a
, const BIGNUM
*p
,
609 const BIGNUM
*m
, BN_CTX
*ctx
,
613 BN_ULONG A
= a
->d
[0];
614 return BN_mod_exp_mont_word(r
, A
, p
, m
, ctx
, m_ctx
);
616 return BN_mod_exp_mont(r
, a
, p
, m
, ctx
, m_ctx
);