Mercurial > dropbear

comparison libtommath/bn_mp_is_square.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_IS_SQUARE_C 2 #ifdef BN_MP_IS_SQUARE_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 /* Check if remainders are possible squares - fast exclude non-squares */ 15 /* Check if remainders are possible squares - fast exclude non-squares */
19 static const char rem_128[128] = { 16 static const char rem_128[128] = {
20 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 17 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
21 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 18 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
22 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 19 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
23 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 20 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
24 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 21 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
25 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 22 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
26 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 23 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
27 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 24 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1
28 }; 25 };
29 26
30 static const char rem_105[105] = { 27 static const char rem_105[105] = {
31 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 28 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
32 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 29 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
33 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 30 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
34 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 31 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
35 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 32 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
36 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 33 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1,
37 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1 34 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1
38 }; 35 };
39 36
40 /* Store non-zero to ret if arg is square, and zero if not */ 37 /* Store non-zero to ret if arg is square, and zero if not */
41 int mp_is_square(mp_int *arg,int *ret) 38 int mp_is_square(const mp_int *arg, int *ret)
42 { 39 {
43 int res; 40 int res;
44 mp_digit c; 41 mp_digit c;
45 mp_int t; 42 mp_int t;
46 unsigned long r; 43 unsigned long r;
47 44
48 /* Default to Non-square :) */ 45 /* Default to Non-square :) */
49 *ret = MP_NO; 46 *ret = MP_NO;
50 47
51 if (arg->sign == MP_NEG) { 48 if (arg->sign == MP_NEG) {
52 return MP_VAL; 49 return MP_VAL;
53 } 50 }
54 51
55 /* digits used? (TSD) */ 52 /* digits used? (TSD) */
56 if (arg->used == 0) { 53 if (arg->used == 0) {
57 return MP_OKAY; 54 return MP_OKAY;
58 } 55 }
59 56
60 /* First check mod 128 (suppose that DIGIT_BIT is at least 7) */ 57 /* First check mod 128 (suppose that DIGIT_BIT is at least 7) */
61 if (rem_128[127 & DIGIT(arg,0)] == 1) { 58 if (rem_128[127u & DIGIT(arg, 0)] == (char)1) {
62 return MP_OKAY; 59 return MP_OKAY;
63 } 60 }
64 61
65 /* Next check mod 105 (3*5*7) */ 62 /* Next check mod 105 (3*5*7) */
66 if ((res = mp_mod_d(arg,105,&c)) != MP_OKAY) { 63 if ((res = mp_mod_d(arg, 105uL, &c)) != MP_OKAY) {
67 return res; 64 return res;
68 } 65 }
69 if (rem_105[c] == 1) { 66 if (rem_105[c] == (char)1) {
70 return MP_OKAY; 67 return MP_OKAY;
71 } 68 }
72 69
73 70
74 if ((res = mp_init_set_int(&t,11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) { 71 if ((res = mp_init_set_int(&t, 11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) {
75 return res; 72 return res;
76 } 73 }
77 if ((res = mp_mod(arg,&t,&t)) != MP_OKAY) { 74 if ((res = mp_mod(arg, &t, &t)) != MP_OKAY) {
78 goto ERR; 75 goto LBL_ERR;
79 } 76 }
80 r = mp_get_int(&t); 77 r = mp_get_int(&t);
81 /* Check for other prime modules, note it's not an ERROR but we must 78 /* Check for other prime modules, note it's not an ERROR but we must
82 * free "t" so the easiest way is to goto ERR. We know that res 79 * free "t" so the easiest way is to goto LBL_ERR. We know that res
83 * is already equal to MP_OKAY from the mp_mod call 80 * is already equal to MP_OKAY from the mp_mod call
84 */ 81 */
85 if (((1L<<(r%11)) & 0x5C4L) != 0L) goto ERR; 82 if (((1uL<<(r%11uL)) & 0x5C4uL) != 0uL) goto LBL_ERR;
86 if (((1L<<(r%13)) & 0x9E4L) != 0L) goto ERR; 83 if (((1uL<<(r%13uL)) & 0x9E4uL) != 0uL) goto LBL_ERR;
87 if (((1L<<(r%17)) & 0x5CE8L) != 0L) goto ERR; 84 if (((1uL<<(r%17uL)) & 0x5CE8uL) != 0uL) goto LBL_ERR;
88 if (((1L<<(r%19)) & 0x4F50CL) != 0L) goto ERR; 85 if (((1uL<<(r%19uL)) & 0x4F50CuL) != 0uL) goto LBL_ERR;
89 if (((1L<<(r%23)) & 0x7ACCA0L) != 0L) goto ERR; 86 if (((1uL<<(r%23uL)) & 0x7ACCA0uL) != 0uL) goto LBL_ERR;
90 if (((1L<<(r%29)) & 0xC2EDD0CL) != 0L) goto ERR; 87 if (((1uL<<(r%29uL)) & 0xC2EDD0CuL) != 0uL) goto LBL_ERR;
91 if (((1L<<(r%31)) & 0x6DE2B848L) != 0L) goto ERR; 88 if (((1uL<<(r%31uL)) & 0x6DE2B848uL) != 0uL) goto LBL_ERR;
92 89
93 /* Final check - is sqr(sqrt(arg)) == arg ? */ 90 /* Final check - is sqr(sqrt(arg)) == arg ? */
94 if ((res = mp_sqrt(arg,&t)) != MP_OKAY) { 91 if ((res = mp_sqrt(arg, &t)) != MP_OKAY) {
95 goto ERR; 92 goto LBL_ERR;
96 } 93 }
97 if ((res = mp_sqr(&t,&t)) != MP_OKAY) { 94 if ((res = mp_sqr(&t, &t)) != MP_OKAY) {
98 goto ERR; 95 goto LBL_ERR;
99 } 96 }
100 97
101 *ret = (mp_cmp_mag(&t,arg) == MP_EQ) ? MP_YES : MP_NO; 98 *ret = (mp_cmp_mag(&t, arg) == MP_EQ) ? MP_YES : MP_NO;
102 ERR:mp_clear(&t); 99 LBL_ERR:
103 return res; 100 mp_clear(&t);
101 return res;
104 } 102 }
105 #endif 103 #endif
106 104
107 /* ref: $Format:%D$ */ 105 /* ref: HEAD -> master, tag: v1.1.0 */
108 /* git commit: $Format:%H$ */ 106 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
109 /* commit time: $Format:%ai$ */ 107 /* commit time: 2019-01-28 20:32:32 +0100 */