Mercurial > dropbear

comparison libtommath/bn_mp_prime_miller_rabin.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 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 */