Mercurial > dropbear

annotate libtommath/bn_mp_sqrtmod_prime.c @ 1663:c795520269f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fallback for key gen without hard link support (#89) Add a non-atomic fallback for key generation on platforms where link() is not permitted (such as most stock Android installs) or on filesystems without hard link support (such as FAT).
author Matt Robinson <git@nerdoftheherd.com>
date Sat, 14 Mar 2020 14:37:35 +0000
parents f52919ffd3b1
children 1051e4eea25a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
1 #include "tommath_private.h"
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 #ifdef BN_MP_SQRTMOD_PRIME_C
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 *
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 * LibTomMath is a library that provides multiple-precision
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * integer arithmetic as well as number theoretic functionality.
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 *
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
8 * The library was designed directly after the MPI library by
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
9 * Michael Fromberger but has been written from scratch with
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
10 * additional optimizations in place.
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
11 *
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
12 * SPDX-License-Identifier: Unlicense
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 */
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 /* Tonelli-Shanks algorithm
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 * https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 *
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 */
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
21 int mp_sqrtmod_prime(const mp_int *n, const mp_int *prime, mp_int *ret)
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 {
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
23 int res, legendre;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
24 mp_int t1, C, Q, S, Z, M, T, R, two;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
25 mp_digit i;
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
27 /* first handle the simple cases */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
28 if (mp_cmp_d(n, 0uL) == MP_EQ) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
29 mp_zero(ret);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
30 return MP_OKAY;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
31 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
32 if (mp_cmp_d(prime, 2uL) == MP_EQ) return MP_VAL; /* prime must be odd */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
33 if ((res = mp_jacobi(n, prime, &legendre)) != MP_OKAY) return res;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
34 if (legendre == -1) return MP_VAL; /* quadratic non-residue mod prime */
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
36 if ((res = mp_init_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL)) != MP_OKAY) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
37 return res;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
38 }
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
40 /* SPECIAL CASE: if prime mod 4 == 3
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
41 * compute directly: res = n^(prime+1)/4 mod prime
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
42 * Handbook of Applied Cryptography algorithm 3.36
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
43 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
44 if ((res = mp_mod_d(prime, 4uL, &i)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
45 if (i == 3u) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
46 if ((res = mp_add_d(prime, 1uL, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
47 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
48 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
49 if ((res = mp_exptmod(n, &t1, prime, ret)) != MP_OKAY) goto cleanup;
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 res = MP_OKAY;
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 goto cleanup;
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
52 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
53
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
54 /* NOW: Tonelli-Shanks algorithm */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
55
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
56 /* factor out powers of 2 from prime-1, defining Q and S as: prime-1 = Q*2^S */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
57 if ((res = mp_copy(prime, &Q)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
58 if ((res = mp_sub_d(&Q, 1uL, &Q)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
59 /* Q = prime - 1 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
60 mp_zero(&S);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
61 /* S = 0 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
62 while (mp_iseven(&Q) != MP_NO) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
63 if ((res = mp_div_2(&Q, &Q)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
64 /* Q = Q / 2 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
65 if ((res = mp_add_d(&S, 1uL, &S)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
66 /* S = S + 1 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
67 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
68
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
69 /* find a Z such that the Legendre symbol (Z|prime) == -1 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
70 if ((res = mp_set_int(&Z, 2uL)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
71 /* Z = 2 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
72 while (1) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
73 if ((res = mp_jacobi(&Z, prime, &legendre)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
74 if (legendre == -1) break;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
75 if ((res = mp_add_d(&Z, 1uL, &Z)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
76 /* Z = Z + 1 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
77 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
78
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
79 if ((res = mp_exptmod(&Z, &Q, prime, &C)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
80 /* C = Z ^ Q mod prime */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
81 if ((res = mp_add_d(&Q, 1uL, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
82 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
83 /* t1 = (Q + 1) / 2 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
84 if ((res = mp_exptmod(n, &t1, prime, &R)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
85 /* R = n ^ ((Q + 1) / 2) mod prime */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
86 if ((res = mp_exptmod(n, &Q, prime, &T)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
87 /* T = n ^ Q mod prime */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
88 if ((res = mp_copy(&S, &M)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
89 /* M = S */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
90 if ((res = mp_set_int(&two, 2uL)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
91
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
92 res = MP_VAL;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
93 while (1) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
94 if ((res = mp_copy(&T, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
95 i = 0;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
96 while (1) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
97 if (mp_cmp_d(&t1, 1uL) == MP_EQ) break;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
98 if ((res = mp_exptmod(&t1, &two, prime, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
99 i++;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
100 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
101 if (i == 0u) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
102 if ((res = mp_copy(&R, ret)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
103 res = MP_OKAY;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
104 goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
105 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
106 if ((res = mp_sub_d(&M, i, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
107 if ((res = mp_sub_d(&t1, 1uL, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
108 if ((res = mp_exptmod(&two, &t1, prime, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
109 /* t1 = 2 ^ (M - i - 1) */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
110 if ((res = mp_exptmod(&C, &t1, prime, &t1)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
111 /* t1 = C ^ (2 ^ (M - i - 1)) mod prime */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
112 if ((res = mp_sqrmod(&t1, prime, &C)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
113 /* C = (t1 * t1) mod prime */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
114 if ((res = mp_mulmod(&R, &t1, prime, &R)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
115 /* R = (R * t1) mod prime */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
116 if ((res = mp_mulmod(&T, &C, prime, &T)) != MP_OKAY) goto cleanup;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
117 /* T = (T * C) mod prime */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
118 mp_set(&M, i);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
119 /* M = i */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
120 }
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
121
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
122 cleanup:
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
123 mp_clear_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
124 return res;
1436
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
125 }
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
126
60fc6476e044 Update to libtommath v1.0
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
127 #endif
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
128
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
129 /* ref: HEAD -> master, tag: v1.1.0 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
130 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1436
diff changeset
131 /* commit time: 2019-01-28 20:32:32 +0100 */