Mercurial > dropbear
annotate libtommath/bn_s_mp_karatsuba_sqr.c @ 1861:2b3a8026a6ce
Add re-exec for server
This allows ASLR to re-randomize the address
space for every connection, preventing some
vulnerabilities from being exploitable by
repeated probing.
Overhead (memory and time) is yet to be confirmed.
At present this is only enabled on Linux. Other BSD platforms
with fexecve() would probably also work though have not been tested.
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Sun, 30 Jan 2022 10:14:56 +0800 |
parents | 1051e4eea25a |
children |
rev | line source |
---|---|
1692
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
1 #include "tommath_private.h" |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
2 #ifdef BN_S_MP_KARATSUBA_SQR_C |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
4 /* SPDX-License-Identifier: Unlicense */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
5 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
6 /* Karatsuba squaring, computes b = a*a using three |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
7 * half size squarings |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
8 * |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
9 * See comments of karatsuba_mul for details. It |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
10 * is essentially the same algorithm but merely |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
11 * tuned to perform recursive squarings. |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
12 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
13 mp_err s_mp_karatsuba_sqr(const mp_int *a, mp_int *b) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
14 { |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
15 mp_int x0, x1, t1, t2, x0x0, x1x1; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
16 int B; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
17 mp_err err = MP_MEM; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
18 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
19 /* min # of digits */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
20 B = a->used; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
21 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
22 /* now divide in two */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
23 B = B >> 1; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
24 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
25 /* init copy all the temps */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
26 if (mp_init_size(&x0, B) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
27 goto LBL_ERR; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
28 if (mp_init_size(&x1, a->used - B) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
29 goto X0; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
30 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
31 /* init temps */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
32 if (mp_init_size(&t1, a->used * 2) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
33 goto X1; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
34 if (mp_init_size(&t2, a->used * 2) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
35 goto T1; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
36 if (mp_init_size(&x0x0, B * 2) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
37 goto T2; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
38 if (mp_init_size(&x1x1, (a->used - B) * 2) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
39 goto X0X0; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
40 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
41 { |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
42 int x; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
43 mp_digit *dst, *src; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
44 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
45 src = a->dp; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
46 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
47 /* now shift the digits */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
48 dst = x0.dp; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
49 for (x = 0; x < B; x++) { |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
50 *dst++ = *src++; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
51 } |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
52 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
53 dst = x1.dp; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
54 for (x = B; x < a->used; x++) { |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
55 *dst++ = *src++; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
56 } |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
57 } |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
58 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
59 x0.used = B; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
60 x1.used = a->used - B; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
61 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
62 mp_clamp(&x0); |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
63 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
64 /* now calc the products x0*x0 and x1*x1 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
65 if (mp_sqr(&x0, &x0x0) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
66 goto X1X1; /* x0x0 = x0*x0 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
67 if (mp_sqr(&x1, &x1x1) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
68 goto X1X1; /* x1x1 = x1*x1 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
69 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
70 /* now calc (x1+x0)**2 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
71 if (s_mp_add(&x1, &x0, &t1) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
72 goto X1X1; /* t1 = x1 - x0 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
73 if (mp_sqr(&t1, &t1) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
74 goto X1X1; /* t1 = (x1 - x0) * (x1 - x0) */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
75 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
76 /* add x0y0 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
77 if (s_mp_add(&x0x0, &x1x1, &t2) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
78 goto X1X1; /* t2 = x0x0 + x1x1 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
79 if (s_mp_sub(&t1, &t2, &t1) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
80 goto X1X1; /* t1 = (x1+x0)**2 - (x0x0 + x1x1) */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
81 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
82 /* shift by B */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
83 if (mp_lshd(&t1, B) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
84 goto X1X1; /* t1 = (x0x0 + x1x1 - (x1-x0)*(x1-x0))<<B */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
85 if (mp_lshd(&x1x1, B * 2) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
86 goto X1X1; /* x1x1 = x1x1 << 2*B */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
87 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
88 if (mp_add(&x0x0, &t1, &t1) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
89 goto X1X1; /* t1 = x0x0 + t1 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
90 if (mp_add(&t1, &x1x1, b) != MP_OKAY) |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
91 goto X1X1; /* t1 = x0x0 + t1 + x1x1 */ |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
92 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
93 err = MP_OKAY; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
94 |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
95 X1X1: |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
96 mp_clear(&x1x1); |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
97 X0X0: |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
98 mp_clear(&x0x0); |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
99 T2: |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
100 mp_clear(&t2); |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
101 T1: |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
102 mp_clear(&t1); |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
103 X1: |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
104 mp_clear(&x1); |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
105 X0: |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
106 mp_clear(&x0); |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
107 LBL_ERR: |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
108 return err; |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
109 } |
1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
Steffen Jaeckel <s@jaeckel.eu>
parents:
diff
changeset
|
110 #endif |