1// Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include <openssl/bn.h>
16
17#include <openssl/err.h>
18
19#include "internal.h"
20
21
22BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) {
23  // Compute a square root of |a| mod |p| using the Tonelli/Shanks algorithm
24  // (cf. Henri Cohen, "A Course in Algebraic Computational Number Theory",
25  // algorithm 1.5.1). |p| is assumed to be a prime.
26
27  BIGNUM *ret = in;
28  int err = 1;
29  int r;
30  BIGNUM *A, *b, *q, *t, *x, *y;
31  int e, i, j;
32
33  if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) {
34    if (BN_abs_is_word(p, 2)) {
35      if (ret == NULL) {
36        ret = BN_new();
37      }
38      if (ret == NULL ||
39          !BN_set_word(ret, BN_is_bit_set(a, 0))) {
40        if (ret != in) {
41          BN_free(ret);
42        }
43        return NULL;
44      }
45      return ret;
46    }
47
48    OPENSSL_PUT_ERROR(BN, BN_R_P_IS_NOT_PRIME);
49    return NULL;
50  }
51
52  if (BN_is_zero(a) || BN_is_one(a)) {
53    if (ret == NULL) {
54      ret = BN_new();
55    }
56    if (ret == NULL ||
57        !BN_set_word(ret, BN_is_one(a))) {
58      if (ret != in) {
59        BN_free(ret);
60      }
61      return NULL;
62    }
63    return ret;
64  }
65
66  bssl::BN_CTXScope scope(ctx);
67  A = BN_CTX_get(ctx);
68  b = BN_CTX_get(ctx);
69  q = BN_CTX_get(ctx);
70  t = BN_CTX_get(ctx);
71  x = BN_CTX_get(ctx);
72  y = BN_CTX_get(ctx);
73  if (y == NULL) {
74    goto end;
75  }
76
77  if (ret == NULL) {
78    ret = BN_new();
79  }
80  if (ret == NULL) {
81    goto end;
82  }
83
84  // A = a mod p
85  if (!BN_nnmod(A, a, p, ctx)) {
86    goto end;
87  }
88
89  // now write  |p| - 1  as  2^e*q  where  q  is odd
90  e = 1;
91  while (!BN_is_bit_set(p, e)) {
92    e++;
93  }
94  // we'll set  q  later (if needed)
95
96  if (e == 1) {
97    // The easy case:  (|p|-1)/2  is odd, so 2 has an inverse
98    // modulo  (|p|-1)/2,  and square roots can be computed
99    // directly by modular exponentiation.
100    // We have
101    //     2 * (|p|+1)/4 == 1   (mod (|p|-1)/2),
102    // so we can use exponent  (|p|+1)/4,  i.e.  (|p|-3)/4 + 1.
103    if (!BN_rshift(q, p, 2)) {
104      goto end;
105    }
106    q->neg = 0;
107    if (!BN_add_word(q, 1) ||
108        !BN_mod_exp_mont(ret, A, q, p, ctx, NULL)) {
109      goto end;
110    }
111    err = 0;
112    goto vrfy;
113  }
114
115  if (e == 2) {
116    // |p| == 5  (mod 8)
117    //
118    // In this case  2  is always a non-square since
119    // Legendre(2,p) = (-1)^((p^2-1)/8)  for any odd prime.
120    // So if  a  really is a square, then  2*a  is a non-square.
121    // Thus for
122    //      b := (2*a)^((|p|-5)/8),
123    //      i := (2*a)*b^2
124    // we have
125    //     i^2 = (2*a)^((1 + (|p|-5)/4)*2)
126    //         = (2*a)^((p-1)/2)
127    //         = -1;
128    // so if we set
129    //      x := a*b*(i-1),
130    // then
131    //     x^2 = a^2 * b^2 * (i^2 - 2*i + 1)
132    //         = a^2 * b^2 * (-2*i)
133    //         = a*(-i)*(2*a*b^2)
134    //         = a*(-i)*i
135    //         = a.
136    //
137    // (This is due to A.O.L. Atkin,
138    // <URL:
139    //http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>,
140    // November 1992.)
141
142    // t := 2*a
143    if (!bn_mod_lshift1_consttime(t, A, p, ctx)) {
144      goto end;
145    }
146
147    // b := (2*a)^((|p|-5)/8)
148    if (!BN_rshift(q, p, 3)) {
149      goto end;
150    }
151    q->neg = 0;
152    if (!BN_mod_exp_mont(b, t, q, p, ctx, NULL)) {
153      goto end;
154    }
155
156    // y := b^2
157    if (!BN_mod_sqr(y, b, p, ctx)) {
158      goto end;
159    }
160
161    // t := (2*a)*b^2 - 1
162    if (!BN_mod_mul(t, t, y, p, ctx) ||
163        !BN_sub_word(t, 1)) {
164      goto end;
165    }
166
167    // x = a*b*t
168    if (!BN_mod_mul(x, A, b, p, ctx) ||
169        !BN_mod_mul(x, x, t, p, ctx)) {
170      goto end;
171    }
172
173    if (!BN_copy(ret, x)) {
174      goto end;
175    }
176    err = 0;
177    goto vrfy;
178  }
179
180  // e > 2, so we really have to use the Tonelli/Shanks algorithm.
181  // First, find some  y  that is not a square.
182  if (!BN_copy(q, p)) {
183    goto end;  // use 'q' as temp
184  }
185  q->neg = 0;
186  i = 2;
187  do {
188    // For efficiency, try small numbers first;
189    // if this fails, try random numbers.
190    if (i < 22) {
191      if (!BN_set_word(y, i)) {
192        goto end;
193      }
194    } else {
195      if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0)) {
196        goto end;
197      }
198      if (BN_ucmp(y, p) >= 0) {
199        if (BN_usub(y, y, p)) {
200          goto end;
201        }
202      }
203      // now 0 <= y < |p|
204      if (BN_is_zero(y)) {
205        if (!BN_set_word(y, i)) {
206          goto end;
207        }
208      }
209    }
210
211    r = bn_jacobi(y, q, ctx);  // here 'q' is |p|
212    if (r < -1) {
213      goto end;
214    }
215    if (r == 0) {
216      // m divides p
217      OPENSSL_PUT_ERROR(BN, BN_R_P_IS_NOT_PRIME);
218      goto end;
219    }
220  } while (r == 1 && ++i < 82);
221
222  if (r != -1) {
223    // Many rounds and still no non-square -- this is more likely
224    // a bug than just bad luck.
225    // Even if  p  is not prime, we should have found some  y
226    // such that r == -1.
227    OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS);
228    goto end;
229  }
230
231  // Here's our actual 'q':
232  if (!BN_rshift(q, q, e)) {
233    goto end;
234  }
235
236  // Now that we have some non-square, we can find an element
237  // of order  2^e  by computing its q'th power.
238  if (!BN_mod_exp_mont(y, y, q, p, ctx, NULL)) {
239    goto end;
240  }
241  if (BN_is_one(y)) {
242    OPENSSL_PUT_ERROR(BN, BN_R_P_IS_NOT_PRIME);
243    goto end;
244  }
245
246  // Now we know that (if  p  is indeed prime) there is an integer
247  // k,  0 <= k < 2^e,  such that
248  //
249  //      a^q * y^k == 1   (mod p).
250  //
251  // As  a^q  is a square and  y  is not,  k  must be even.
252  // q+1  is even, too, so there is an element
253  //
254  //     X := a^((q+1)/2) * y^(k/2),
255  //
256  // and it satisfies
257  //
258  //     X^2 = a^q * a     * y^k
259  //         = a,
260  //
261  // so it is the square root that we are looking for.
262
263  // t := (q-1)/2  (note that  q  is odd)
264  if (!BN_rshift1(t, q)) {
265    goto end;
266  }
267
268  // x := a^((q-1)/2)
269  if (BN_is_zero(t)) {  // special case: p = 2^e + 1
270    if (!BN_nnmod(t, A, p, ctx)) {
271      goto end;
272    }
273    if (BN_is_zero(t)) {
274      // special case: a == 0  (mod p)
275      BN_zero(ret);
276      err = 0;
277      goto end;
278    } else if (!BN_one(x)) {
279      goto end;
280    }
281  } else {
282    if (!BN_mod_exp_mont(x, A, t, p, ctx, NULL)) {
283      goto end;
284    }
285    if (BN_is_zero(x)) {
286      // special case: a == 0  (mod p)
287      BN_zero(ret);
288      err = 0;
289      goto end;
290    }
291  }
292
293  // b := a*x^2  (= a^q)
294  if (!BN_mod_sqr(b, x, p, ctx) ||
295      !BN_mod_mul(b, b, A, p, ctx)) {
296    goto end;
297  }
298
299  // x := a*x    (= a^((q+1)/2))
300  if (!BN_mod_mul(x, x, A, p, ctx)) {
301    goto end;
302  }
303
304  while (1) {
305    // Now  b  is  a^q * y^k  for some even  k  (0 <= k < 2^E
306    // where  E  refers to the original value of  e,  which we
307    // don't keep in a variable),  and  x  is  a^((q+1)/2) * y^(k/2).
308    //
309    // We have  a*b = x^2,
310    //    y^2^(e-1) = -1,
311    //    b^2^(e-1) = 1.
312    if (BN_is_one(b)) {
313      if (!BN_copy(ret, x)) {
314        goto end;
315      }
316      err = 0;
317      goto vrfy;
318    }
319
320    // Find the smallest i, 0 < i < e, such that b^(2^i) = 1
321    for (i = 1; i < e; i++) {
322      if (i == 1) {
323        if (!BN_mod_sqr(t, b, p, ctx)) {
324          goto end;
325        }
326      } else {
327        if (!BN_mod_mul(t, t, t, p, ctx)) {
328          goto end;
329        }
330      }
331      if (BN_is_one(t)) {
332        break;
333      }
334    }
335    // If not found, a is not a square or p is not a prime.
336    if (i >= e) {
337      OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE);
338      goto end;
339    }
340
341    // t := y^2^(e - i - 1)
342    if (!BN_copy(t, y)) {
343      goto end;
344    }
345    for (j = e - i - 1; j > 0; j--) {
346      if (!BN_mod_sqr(t, t, p, ctx)) {
347        goto end;
348      }
349    }
350    if (!BN_mod_mul(y, t, t, p, ctx) ||
351        !BN_mod_mul(x, x, t, p, ctx) ||
352        !BN_mod_mul(b, b, y, p, ctx)) {
353      goto end;
354    }
355
356    // e decreases each iteration, so this loop will terminate.
357    assert(i < e);
358    e = i;
359  }
360
361vrfy:
362  if (!err) {
363    // Verify the result. The input might have been not a square.
364    if (!BN_mod_sqr(x, ret, p, ctx)) {
365      err = 1;
366    }
367
368    if (!err && 0 != BN_cmp(x, A)) {
369      OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE);
370      err = 1;
371    }
372  }
373
374end:
375  if (err) {
376    if (ret != in) {
377      BN_clear_free(ret);
378    }
379    ret = NULL;
380  }
381  return ret;
382}
383