Mercurial > dropbear

comparison libtommath/bn_mp_prime_frobenius_underwood.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
children 1051e4eea25a
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include "tommath_private.h"
2 #ifdef BN_MP_PRIME_FROBENIUS_UNDERWOOD_C
3
4 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5 *
6 * LibTomMath is a library that provides multiple-precision
7 * integer arithmetic as well as number theoretic functionality.
8 *
9 * The library was designed directly after the MPI library by
10 * Michael Fromberger but has been written from scratch with
11 * additional optimizations in place.
12 *
13 * SPDX-License-Identifier: Unlicense
14 */
15
16 /*
17 * See file bn_mp_prime_is_prime.c or the documentation in doc/bn.tex for the details
18 */
19 #ifndef LTM_USE_FIPS_ONLY
20
21 #ifdef MP_8BIT
22 /*
23 * floor of positive solution of
24 * (2^16)-1 = (a+4)*(2*a+5)
25 * TODO: Both values are smaller than N^(1/4), would have to use a bigint
26 * for a instead but any a biger than about 120 are already so rare that
27 * it is possible to ignore them and still get enough pseudoprimes.
28 * But it is still a restriction of the set of available pseudoprimes
29 * which makes this implementation less secure if used stand-alone.
30 */
31 #define LTM_FROBENIUS_UNDERWOOD_A 177
32 #else
33 #define LTM_FROBENIUS_UNDERWOOD_A 32764
34 #endif
35 int mp_prime_frobenius_underwood(const mp_int *N, int *result)
36 {
37 mp_int T1z, T2z, Np1z, sz, tz;
38
39 int a, ap2, length, i, j, isset;
40 int e;
41
42 *result = MP_NO;
43
44 if ((e = mp_init_multi(&T1z, &T2z, &Np1z, &sz, &tz, NULL)) != MP_OKAY) {
45 return e;
46 }
47
48 for (a = 0; a < LTM_FROBENIUS_UNDERWOOD_A; a++) {
49 /* TODO: That's ugly! No, really, it is! */
50 if ((a==2) || (a==4) || (a==7) || (a==8) || (a==10) ||
51 (a==14) || (a==18) || (a==23) || (a==26) || (a==28)) {
52 continue;
53 }
54 /* (32764^2 - 4) < 2^31, no bigint for >MP_8BIT needed) */
55 if ((e = mp_set_long(&T1z, (unsigned long)a)) != MP_OKAY) {
56 goto LBL_FU_ERR;
57 }
58
59 if ((e = mp_sqr(&T1z, &T1z)) != MP_OKAY) {
60 goto LBL_FU_ERR;
61 }
62
63 if ((e = mp_sub_d(&T1z, 4uL, &T1z)) != MP_OKAY) {
64 goto LBL_FU_ERR;
65 }
66
67 if ((e = mp_kronecker(&T1z, N, &j)) != MP_OKAY) {
68 goto LBL_FU_ERR;
69 }
70
71 if (j == -1) {
72 break;
73 }
74
75 if (j == 0) {
76 /* composite */
77 goto LBL_FU_ERR;
78 }
79 }
80 /* Tell it a composite and set return value accordingly */
81 if (a >= LTM_FROBENIUS_UNDERWOOD_A) {
82 e = MP_ITER;
83 goto LBL_FU_ERR;
84 }
85 /* Composite if N and (a+4)*(2*a+5) are not coprime */
86 if ((e = mp_set_long(&T1z, (unsigned long)((a+4)*((2*a)+5)))) != MP_OKAY) {
87 goto LBL_FU_ERR;
88 }
89
90 if ((e = mp_gcd(N, &T1z, &T1z)) != MP_OKAY) {
91 goto LBL_FU_ERR;
92 }
93
94 if (!((T1z.used == 1) && (T1z.dp[0] == 1u))) {
95 goto LBL_FU_ERR;
96 }
97
98 ap2 = a + 2;
99 if ((e = mp_add_d(N, 1uL, &Np1z)) != MP_OKAY) {
100 goto LBL_FU_ERR;
101 }
102
103 mp_set(&sz, 1uL);
104 mp_set(&tz, 2uL);
105 length = mp_count_bits(&Np1z);
106
107 for (i = length - 2; i >= 0; i--) {
108 /*
109 * temp = (sz*(a*sz+2*tz))%N;
110 * tz = ((tz-sz)*(tz+sz))%N;
111 * sz = temp;
112 */
113 if ((e = mp_mul_2(&tz, &T2z)) != MP_OKAY) {
114 goto LBL_FU_ERR;
115 }
116
117 /* a = 0 at about 50% of the cases (non-square and odd input) */
118 if (a != 0) {
119 if ((e = mp_mul_d(&sz, (mp_digit)a, &T1z)) != MP_OKAY) {
120 goto LBL_FU_ERR;
121 }
122 if ((e = mp_add(&T1z, &T2z, &T2z)) != MP_OKAY) {
123 goto LBL_FU_ERR;
124 }
125 }
126
127 if ((e = mp_mul(&T2z, &sz, &T1z)) != MP_OKAY) {
128 goto LBL_FU_ERR;
129 }
130 if ((e = mp_sub(&tz, &sz, &T2z)) != MP_OKAY) {
131 goto LBL_FU_ERR;
132 }
133 if ((e = mp_add(&sz, &tz, &sz)) != MP_OKAY) {
134 goto LBL_FU_ERR;
135 }
136 if ((e = mp_mul(&sz, &T2z, &tz)) != MP_OKAY) {
137 goto LBL_FU_ERR;
138 }
139 if ((e = mp_mod(&tz, N, &tz)) != MP_OKAY) {
140 goto LBL_FU_ERR;
141 }
142 if ((e = mp_mod(&T1z, N, &sz)) != MP_OKAY) {
143 goto LBL_FU_ERR;
144 }
145 if ((isset = mp_get_bit(&Np1z, i)) == MP_VAL) {
146 e = isset;
147 goto LBL_FU_ERR;
148 }
149 if (isset == MP_YES) {
150 /*
151 * temp = (a+2) * sz + tz
152 * tz = 2 * tz - sz
153 * sz = temp
154 */
155 if (a == 0) {
156 if ((e = mp_mul_2(&sz, &T1z)) != MP_OKAY) {
157 goto LBL_FU_ERR;
158 }
159 } else {
160 if ((e = mp_mul_d(&sz, (mp_digit)ap2, &T1z)) != MP_OKAY) {
161 goto LBL_FU_ERR;
162 }
163 }
164 if ((e = mp_add(&T1z, &tz, &T1z)) != MP_OKAY) {
165 goto LBL_FU_ERR;
166 }
167 if ((e = mp_mul_2(&tz, &T2z)) != MP_OKAY) {
168 goto LBL_FU_ERR;
169 }
170 if ((e = mp_sub(&T2z, &sz, &tz)) != MP_OKAY) {
171 goto LBL_FU_ERR;
172 }
173 mp_exch(&sz, &T1z);
174 }
175 }
176
177 if ((e = mp_set_long(&T1z, (unsigned long)((2 * a) + 5))) != MP_OKAY) {
178 goto LBL_FU_ERR;
179 }
180 if ((e = mp_mod(&T1z, N, &T1z)) != MP_OKAY) {
181 goto LBL_FU_ERR;
182 }
183 if ((mp_iszero(&sz) != MP_NO) && (mp_cmp(&tz, &T1z) == MP_EQ)) {
184 *result = MP_YES;
185 goto LBL_FU_ERR;
186 }
187
188 LBL_FU_ERR:
189 mp_clear_multi(&tz, &sz, &Np1z, &T2z, &T1z, NULL);
190 return e;
191 }
192
193 #endif
194 #endif
195
196 /* ref: HEAD -> master, tag: v1.1.0 */
197 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
198 /* commit time: 2019-01-28 20:32:32 +0100 */