Mercurial > dropbear
comparison libtommath/bn_mp_prime_miller_rabin.c @ 1655:f52919ffd3b1
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 | 1051e4eea25a |
comparison
equal
deleted
inserted
replaced
1654:cc0fc5131c5c | 1655:f52919ffd3b1 |
---|---|
1 #include <tommath_private.h> | 1 #include "tommath_private.h" |
2 #ifdef BN_MP_PRIME_MILLER_RABIN_C | 2 #ifdef BN_MP_PRIME_MILLER_RABIN_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 /* Miller-Rabin test of "a" to the base of "b" as described in | 15 /* Miller-Rabin test of "a" to the base of "b" as described in |
19 * HAC pp. 139 Algorithm 4.24 | 16 * HAC pp. 139 Algorithm 4.24 |
20 * | 17 * |
21 * Sets result to 0 if definitely composite or 1 if probably prime. | 18 * Sets result to 0 if definitely composite or 1 if probably prime. |
22 * Randomly the chance of error is no more than 1/4 and often | 19 * Randomly the chance of error is no more than 1/4 and often |
23 * very much lower. | 20 * very much lower. |
24 */ | 21 */ |
25 int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result) | 22 int mp_prime_miller_rabin(const mp_int *a, const mp_int *b, int *result) |
26 { | 23 { |
27 mp_int n1, y, r; | 24 mp_int n1, y, r; |
28 int s, j, err; | 25 int s, j, err; |
29 | 26 |
30 /* default */ | 27 /* default */ |
31 *result = MP_NO; | 28 *result = MP_NO; |
32 | 29 |
33 /* ensure b > 1 */ | 30 /* ensure b > 1 */ |
34 if (mp_cmp_d(b, 1) != MP_GT) { | 31 if (mp_cmp_d(b, 1uL) != MP_GT) { |
35 return MP_VAL; | 32 return MP_VAL; |
36 } | 33 } |
37 | 34 |
38 /* get n1 = a - 1 */ | 35 /* get n1 = a - 1 */ |
39 if ((err = mp_init_copy (&n1, a)) != MP_OKAY) { | 36 if ((err = mp_init_copy(&n1, a)) != MP_OKAY) { |
40 return err; | 37 return err; |
41 } | 38 } |
42 if ((err = mp_sub_d (&n1, 1, &n1)) != MP_OKAY) { | 39 if ((err = mp_sub_d(&n1, 1uL, &n1)) != MP_OKAY) { |
43 goto LBL_N1; | 40 goto LBL_N1; |
44 } | 41 } |
45 | 42 |
46 /* set 2**s * r = n1 */ | 43 /* set 2**s * r = n1 */ |
47 if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) { | 44 if ((err = mp_init_copy(&r, &n1)) != MP_OKAY) { |
48 goto LBL_N1; | 45 goto LBL_N1; |
49 } | 46 } |
50 | 47 |
51 /* count the number of least significant bits | 48 /* count the number of least significant bits |
52 * which are zero | 49 * which are zero |
53 */ | 50 */ |
54 s = mp_cnt_lsb(&r); | 51 s = mp_cnt_lsb(&r); |
55 | 52 |
56 /* now divide n - 1 by 2**s */ | 53 /* now divide n - 1 by 2**s */ |
57 if ((err = mp_div_2d (&r, s, &r, NULL)) != MP_OKAY) { | 54 if ((err = mp_div_2d(&r, s, &r, NULL)) != MP_OKAY) { |
58 goto LBL_R; | 55 goto LBL_R; |
59 } | 56 } |
60 | 57 |
61 /* compute y = b**r mod a */ | 58 /* compute y = b**r mod a */ |
62 if ((err = mp_init (&y)) != MP_OKAY) { | 59 if ((err = mp_init(&y)) != MP_OKAY) { |
63 goto LBL_R; | 60 goto LBL_R; |
64 } | 61 } |
65 if ((err = mp_exptmod (b, &r, a, &y)) != MP_OKAY) { | 62 if ((err = mp_exptmod(b, &r, a, &y)) != MP_OKAY) { |
66 goto LBL_Y; | 63 goto LBL_Y; |
67 } | 64 } |
68 | 65 |
69 /* if y != 1 and y != n1 do */ | 66 /* if y != 1 and y != n1 do */ |
70 if ((mp_cmp_d (&y, 1) != MP_EQ) && (mp_cmp (&y, &n1) != MP_EQ)) { | 67 if ((mp_cmp_d(&y, 1uL) != MP_EQ) && (mp_cmp(&y, &n1) != MP_EQ)) { |
71 j = 1; | 68 j = 1; |
72 /* while j <= s-1 and y != n1 */ | 69 /* while j <= s-1 and y != n1 */ |
73 while ((j <= (s - 1)) && (mp_cmp (&y, &n1) != MP_EQ)) { | 70 while ((j <= (s - 1)) && (mp_cmp(&y, &n1) != MP_EQ)) { |
74 if ((err = mp_sqrmod (&y, a, &y)) != MP_OKAY) { | 71 if ((err = mp_sqrmod(&y, a, &y)) != MP_OKAY) { |
72 goto LBL_Y; | |
73 } | |
74 | |
75 /* if y == 1 then composite */ | |
76 if (mp_cmp_d(&y, 1uL) == MP_EQ) { | |
77 goto LBL_Y; | |
78 } | |
79 | |
80 ++j; | |
81 } | |
82 | |
83 /* if y != n1 then composite */ | |
84 if (mp_cmp(&y, &n1) != MP_EQ) { | |
75 goto LBL_Y; | 85 goto LBL_Y; |
76 } | 86 } |
87 } | |
77 | 88 |
78 /* if y == 1 then composite */ | 89 /* probably prime now */ |
79 if (mp_cmp_d (&y, 1) == MP_EQ) { | 90 *result = MP_YES; |
80 goto LBL_Y; | 91 LBL_Y: |
81 } | 92 mp_clear(&y); |
82 | 93 LBL_R: |
83 ++j; | 94 mp_clear(&r); |
84 } | 95 LBL_N1: |
85 | 96 mp_clear(&n1); |
86 /* if y != n1 then composite */ | 97 return err; |
87 if (mp_cmp (&y, &n1) != MP_EQ) { | |
88 goto LBL_Y; | |
89 } | |
90 } | |
91 | |
92 /* probably prime now */ | |
93 *result = MP_YES; | |
94 LBL_Y:mp_clear (&y); | |
95 LBL_R:mp_clear (&r); | |
96 LBL_N1:mp_clear (&n1); | |
97 return err; | |
98 } | 98 } |
99 #endif | 99 #endif |
100 | 100 |
101 /* ref: $Format:%D$ */ | 101 /* ref: HEAD -> master, tag: v1.1.0 */ |
102 /* git commit: $Format:%H$ */ | 102 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ |
103 /* commit time: $Format:%ai$ */ | 103 /* commit time: 2019-01-28 20:32:32 +0100 */ |