Mercurial > dropbear

comparison libtommath/bn_mp_prime_random_ex.c @ 1655:f52919ffd3b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) * make key-generation compliant to FIPS 186.4 * fix includes in tommath_class.h * update fuzzcorpus instead of error-out * fixup fuzzing make-targets * update Makefile.in * apply necessary patches to ltm sources * clean-up not required ltm files * update to vanilla ltm 1.1.0 this already only contains the required files * remove set/get double
author Steffen Jaeckel <s_jaeckel@gmx.de>
date Mon, 16 Sep 2019 15:50:38 +0200
parents 8bba51a55704
children
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include <tommath_private.h> 1 #include "tommath_private.h"
2 #ifdef BN_MP_PRIME_RANDOM_EX_C 2 #ifdef BN_MP_PRIME_RANDOM_EX_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 * 4 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
7 * 7 *
8 * The library was designed directly after the MPI library by 8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with 9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * SPDX-License-Identifier: Unlicense
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */ 13 */
17 14
18 /* makes a truly random prime of a given size (bits), 15 /* makes a truly random prime of a given size (bits),
19 * 16 *
20 * Flags are as follows: 17 * Flags are as follows:
21 * 18 *
22 * LTM_PRIME_BBS - make prime congruent to 3 mod 4 19 * LTM_PRIME_BBS - make prime congruent to 3 mod 4
23 * LTM_PRIME_SAFE - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS) 20 * LTM_PRIME_SAFE - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS)
24 * LTM_PRIME_2MSB_ON - make the 2nd highest bit one 21 * LTM_PRIME_2MSB_ON - make the 2nd highest bit one
25 * 22 *
26 * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can 23 * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can
47 44
48 /* calc the byte size */ 45 /* calc the byte size */
49 bsize = (size>>3) + ((size&7)?1:0); 46 bsize = (size>>3) + ((size&7)?1:0);
50 47
51 /* we need a buffer of bsize bytes */ 48 /* we need a buffer of bsize bytes */
52 tmp = OPT_CAST(unsigned char) XMALLOC(bsize); 49 tmp = OPT_CAST(unsigned char) XMALLOC((size_t)bsize);
53 if (tmp == NULL) { 50 if (tmp == NULL) {
54 return MP_MEM; 51 return MP_MEM;
55 } 52 }
56 53
57 /* calc the maskAND value for the MSbyte*/ 54 /* calc the maskAND value for the MSbyte*/
60 /* calc the maskOR_msb */ 57 /* calc the maskOR_msb */
61 maskOR_msb = 0; 58 maskOR_msb = 0;
62 maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0; 59 maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0;
63 if ((flags & LTM_PRIME_2MSB_ON) != 0) { 60 if ((flags & LTM_PRIME_2MSB_ON) != 0) {
64 maskOR_msb |= 0x80 >> ((9 - size) & 7); 61 maskOR_msb |= 0x80 >> ((9 - size) & 7);
65 } 62 }
66 63
67 /* get the maskOR_lsb */ 64 /* get the maskOR_lsb */
68 maskOR_lsb = 1; 65 maskOR_lsb = 1;
69 if ((flags & LTM_PRIME_BBS) != 0) { 66 if ((flags & LTM_PRIME_BBS) != 0) {
70 maskOR_lsb |= 3; 67 maskOR_lsb |= 3;
74 /* read the bytes */ 71 /* read the bytes */
75 if (cb(tmp, bsize, dat) != bsize) { 72 if (cb(tmp, bsize, dat) != bsize) {
76 err = MP_VAL; 73 err = MP_VAL;
77 goto error; 74 goto error;
78 } 75 }
79 76
80 /* work over the MSbyte */ 77 /* work over the MSbyte */
81 tmp[0] &= maskAND; 78 tmp[0] &= maskAND;
82 tmp[0] |= 1 << ((size - 1) & 7); 79 tmp[0] |= 1 << ((size - 1) & 7);
83 80
84 /* mix in the maskORs */ 81 /* mix in the maskORs */
85 tmp[maskOR_msb_offset] |= maskOR_msb; 82 tmp[maskOR_msb_offset] |= maskOR_msb;
86 tmp[bsize-1] |= maskOR_lsb; 83 tmp[bsize-1] |= maskOR_lsb;
87 84
88 /* read it in */ 85 /* read it in */
89 if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY) { goto error; } 86 if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY) {
87 goto error;
88 }
90 89
91 /* is it prime? */ 90 /* is it prime? */
92 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; } 91 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
93 if (res == MP_NO) { 92 goto error;
93 }
94 if (res == MP_NO) {
94 continue; 95 continue;
95 } 96 }
96 97
97 if ((flags & LTM_PRIME_SAFE) != 0) { 98 if ((flags & LTM_PRIME_SAFE) != 0) {
98 /* see if (a-1)/2 is prime */ 99 /* see if (a-1)/2 is prime */
99 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { goto error; } 100 if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
100 if ((err = mp_div_2(a, a)) != MP_OKAY) { goto error; } 101 goto error;
101 102 }
103 if ((err = mp_div_2(a, a)) != MP_OKAY) {
104 goto error;
105 }
106
102 /* is it prime? */ 107 /* is it prime? */
103 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; } 108 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
109 goto error;
110 }
104 } 111 }
105 } while (res == MP_NO); 112 } while (res == MP_NO);
106 113
107 if ((flags & LTM_PRIME_SAFE) != 0) { 114 if ((flags & LTM_PRIME_SAFE) != 0) {
108 /* restore a to the original value */ 115 /* restore a to the original value */
109 if ((err = mp_mul_2(a, a)) != MP_OKAY) { goto error; } 116 if ((err = mp_mul_2(a, a)) != MP_OKAY) {
110 if ((err = mp_add_d(a, 1, a)) != MP_OKAY) { goto error; } 117 goto error;
118 }
119 if ((err = mp_add_d(a, 1uL, a)) != MP_OKAY) {
120 goto error;
121 }
111 } 122 }
112 123
113 err = MP_OKAY; 124 err = MP_OKAY;
114 error: 125 error:
115 XFREE(tmp); 126 XFREE(tmp);
117 } 128 }
118 129
119 130
120 #endif 131 #endif
121 132
122 /* ref: $Format:%D$ */ 133 /* ref: HEAD -> master, tag: v1.1.0 */
123 /* git commit: $Format:%H$ */ 134 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
124 /* commit time: $Format:%ai$ */ 135 /* commit time: 2019-01-28 20:32:32 +0100 */