1 files changed, 142 insertions, 134 deletions
diff --git a/src/lib/libcrypto/bn/bn_sqrt.c b/src/lib/libcrypto/bn/bn_sqrt.c
index 6beaf9e5e5..89bb067d88 100644
--- a/src/lib/libcrypto/bn/bn_sqrt.c
+++ b/src/lib/libcrypto/bn/bn_sqrt.c
@@ -9,7 +9,7 @@
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer. 
+ *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
@@ -59,57 +59,53 @@
 #include "bn_lcl.h"
-BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 
+BIGNUM *
+BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 /* Returns 'ret' such that
 *      ret^2 == a (mod p),
 * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course
 * in Algebraic Computational Number Theory", algorithm 1.5.1).
 * 'p' must be prime!
 */
-        {
+{
        BIGNUM *ret = in;
        int err = 1;
        int r;
        BIGNUM *A, *b, *q, *t, *x, *y;
        int e, i, j;
-        
-        if (!BN_is_odd(p) || BN_abs_is_word(p, 1))
+        if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) {
-                {
+                if (BN_abs_is_word(p, 2)) {
-                if (BN_abs_is_word(p, 2))
-                        {
                        if (ret == NULL)
                                ret = BN_new();
                        if (ret == NULL)
                                goto end;
-                        if (!BN_set_word(ret, BN_is_bit_set(a, 0)))
+                        if (!BN_set_word(ret, BN_is_bit_set(a, 0))) {
-                                {
                                if (ret != in)
                                        BN_free(ret);
                                return NULL;
-                                }
+                        }
                        bn_check_top(ret);
                        return ret;
-                        }
+                }
                BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);
-                return(NULL);
+                return (NULL);
-                }
+        }
-        if (BN_is_zero(a) || BN_is_one(a))
+        if (BN_is_zero(a) || BN_is_one(a)) {
-                {
                if (ret == NULL)
                        ret = BN_new();
                if (ret == NULL)
                        goto end;
-                if (!BN_set_word(ret, BN_is_one(a)))
+                if (!BN_set_word(ret, BN_is_one(a))) {
-                        {
                        if (ret != in)
                                BN_free(ret);
                        return NULL;
-                        }
+                }
                bn_check_top(ret);
                return ret;
-                }
+        }
        BN_CTX_start(ctx);
        A = BN_CTX_get(ctx);
@@ -118,14 +114,17 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
        t = BN_CTX_get(ctx);
        x = BN_CTX_get(ctx);
        y = BN_CTX_get(ctx);
-        if (y == NULL) goto end;
+        if (y == NULL)
-        
+                goto end;
        if (ret == NULL)
                ret = BN_new();
-        if (ret == NULL) goto end;
+        if (ret == NULL)
+                goto end;
        /* A = a mod p */
-        if (!BN_nnmod(A, a, p, ctx)) goto end;
+        if (!BN_nnmod(A, a, p, ctx))
+                goto end;
        /* now write  |p| - 1  as  2^e*q  where  q  is odd */
        e = 1;
@@ -133,8 +132,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
                e++;
        /* we'll set  q  later (if needed) */
-        if (e == 1)
+        if (e == 1) {
-                {
                /* The easy case:  (|p|-1)/2  is odd, so 2 has an inverse
                 * modulo  (|p|-1)/2,  and square roots can be computed
                 * directly by modular exponentiation.
@@ -142,16 +140,18 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
                 *     2 * (|p|+1)/4 == 1   (mod (|p|-1)/2),
                 * so we can use exponent  (|p|+1)/4,  i.e.  (|p|-3)/4 + 1.
                 */
-                if (!BN_rshift(q, p, 2)) goto end;
+                if (!BN_rshift(q, p, 2))
+                        goto end;
                q->neg = 0;
-                if (!BN_add_word(q, 1)) goto end;
+                if (!BN_add_word(q, 1))
-                if (!BN_mod_exp(ret, A, q, p, ctx)) goto end;
+                        goto end;
+                if (!BN_mod_exp(ret, A, q, p, ctx))
+                        goto end;
                err = 0;
                goto vrfy;
-                }
+        }
-        
-        if (e == 2)
+        if (e == 2) {
-                {
                /* |p| == 5  (mod 8)
                 *
                 * In this case  2  is always a non-square since
@@ -173,74 +173,81 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
                 *         = a*(-i)*i
                 *         = a.
                 *
-                 * (This is due to A.O.L. Atkin, 
+                 * (This is due to A.O.L. Atkin,
                 * <URL: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>,
                 * November 1992.)
                 */
                /* t := 2*a */
-                if (!BN_mod_lshift1_quick(t, A, p)) goto end;
+                if (!BN_mod_lshift1_quick(t, A, p))
+                        goto end;
                /* b := (2*a)^((|p|-5)/8) */
-                if (!BN_rshift(q, p, 3)) goto end;
+                if (!BN_rshift(q, p, 3))
+                        goto end;
                q->neg = 0;
-                if (!BN_mod_exp(b, t, q, p, ctx)) goto end;
+                if (!BN_mod_exp(b, t, q, p, ctx))
+                        goto end;
                /* y := b^2 */
-                if (!BN_mod_sqr(y, b, p, ctx)) goto end;
+                if (!BN_mod_sqr(y, b, p, ctx))
+                        goto end;
                /* t := (2*a)*b^2 - 1*/
-                if (!BN_mod_mul(t, t, y, p, ctx)) goto end;
+                if (!BN_mod_mul(t, t, y, p, ctx))
-                if (!BN_sub_word(t, 1)) goto end;
+                        goto end;
+                if (!BN_sub_word(t, 1))
+                        goto end;
                /* x = a*b*t */
-                if (!BN_mod_mul(x, A, b, p, ctx)) goto end;
+                if (!BN_mod_mul(x, A, b, p, ctx))
-                if (!BN_mod_mul(x, x, t, p, ctx)) goto end;
+                        goto end;
+                if (!BN_mod_mul(x, x, t, p, ctx))
+                        goto end;
-                if (!BN_copy(ret, x)) goto end;
+                if (!BN_copy(ret, x))
+                        goto end;
                err = 0;
                goto vrfy;
-                }
+        }
-        
        /* e > 2, so we really have to use the Tonelli/Shanks algorithm.
         * First, find some  y  that is not a square. */
        if (!BN_copy(q, p)) goto end; /* use 'q' as temp */
-        q->neg = 0;
+                q->neg = 0;
        i = 2;
-        do
+        do {
-                {
                /* For efficiency, try small numbers first;
                 * if this fails, try random numbers.
                 */
-                if (i < 22)
+                if (i < 22) {
-                        {
+                        if (!BN_set_word(y, i))
-                        if (!BN_set_word(y, i)) goto end;
+                                goto end;
+                } else {
+                        if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0))
+                                goto end;
+                        if (BN_ucmp(y, p) >= 0) {
+                                if (!(p->neg ? BN_add : BN_sub)(y, y, p))
+                                        goto end;
                        }
-                else
-                        {
-                        if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0)) goto end;
-                        if (BN_ucmp(y, p) >= 0)
-                                {
-                                if (!(p->neg ? BN_add : BN_sub)(y, y, p)) goto end;
-                                }
                        /* now 0 <= y < |p| */
                        if (BN_is_zero(y))
-                                if (!BN_set_word(y, i)) goto end;
+                                if (!BN_set_word(y, i))
-                        }
+                                        goto end;
-                
+                }
                r = BN_kronecker(y, q, ctx); /* here 'q' is |p| */
-                if (r < -1) goto end;
+                if (r < -1)
-                if (r == 0)
+                        goto end;
-                        {
+                if (r == 0) {
                        /* m divides p */
                        BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);
                        goto end;
-                        }
                }
+        }
        while (r == 1 && ++i < 82);
-        
-        if (r != -1)
+                if (r != -1) {
-                {
                /* Many rounds and still no non-square -- this is more likely
                 * a bug than just bad luck.
                 * Even if  p  is not prime, we should have found some  y
@@ -248,19 +255,20 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
                 */
                BNerr(BN_F_BN_MOD_SQRT, BN_R_TOO_MANY_ITERATIONS);
                goto end;
-                }
+        }
        /* Here's our actual 'q': */
-        if (!BN_rshift(q, q, e)) goto end;
+        if (!BN_rshift(q, q, e))
+                goto end;
        /* Now that we have some non-square, we can find an element
         * of order  2^e  by computing its q'th power. */
-        if (!BN_mod_exp(y, y, q, p, ctx)) goto end;
+        if (!BN_mod_exp(y, y, q, p, ctx))
-        if (BN_is_one(y))
+                goto end;
-                {
+        if (BN_is_one(y)) {
                BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);
                goto end;
-                }
+        }
        /* Now we know that (if  p  is indeed prime) there is an integer
         * k,  0 <= k < 2^e,  such that
@@ -279,45 +287,45 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
         *
         * so it is the square root that we are looking for.
         */
-        
        /* t := (q-1)/2  (note that  q  is odd) */
-        if (!BN_rshift1(t, q)) goto end;
+        if (!BN_rshift1(t, q))
-        
+                goto end;
        /* x := a^((q-1)/2) */
        if (BN_is_zero(t)) /* special case: p = 2^e + 1 */
-                {
+        {
-                if (!BN_nnmod(t, A, p, ctx)) goto end;
+                if (!BN_nnmod(t, A, p, ctx))
-                if (BN_is_zero(t))
+                        goto end;
-                        {
+                if (BN_is_zero(t)) {
                        /* special case: a == 0  (mod p) */
                        BN_zero(ret);
                        err = 0;
                        goto end;
-                        }
+                } else if (!BN_one(x))
-                else
+                        goto end;
-                        if (!BN_one(x)) goto end;
+        } else {
-                }
+                if (!BN_mod_exp(x, A, t, p, ctx))
-        else
+                        goto end;
-                {
+                if (BN_is_zero(x)) {
-                if (!BN_mod_exp(x, A, t, p, ctx)) goto end;
-                if (BN_is_zero(x))
-                        {
                        /* special case: a == 0  (mod p) */
                        BN_zero(ret);
                        err = 0;
                        goto end;
-                        }
                }
+        }
        /* b := a*x^2  (= a^q) */
-        if (!BN_mod_sqr(b, x, p, ctx)) goto end;
+        if (!BN_mod_sqr(b, x, p, ctx))
-        if (!BN_mod_mul(b, b, A, p, ctx)) goto end;
+                goto end;
-        
+        if (!BN_mod_mul(b, b, A, p, ctx))
+                goto end;
        /* x := a*x    (= a^((q+1)/2)) */
-        if (!BN_mod_mul(x, x, A, p, ctx)) goto end;
+        if (!BN_mod_mul(x, x, A, p, ctx))
+                goto end;
-        while (1)
+        while (1) {
-                {
                /* Now  b  is  a^q * y^k  for some even  k  (0 <= k < 2^E
                 * where  E  refers to the original value of  e,  which we
                 * don't keep in a variable),  and  x  is  a^((q+1)/2) * y^(k/2).
@@ -327,67 +335,67 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
                 *    b^2^(e-1) = 1.
                 */
-                if (BN_is_one(b))
+                if (BN_is_one(b)) {
-                        {
+                        if (!BN_copy(ret, x))
-                        if (!BN_copy(ret, x)) goto end;
+                                goto end;
                        err = 0;
                        goto vrfy;
-                        }
+                }
                /* find smallest  i  such that  b^(2^i) = 1 */
                i = 1;
-                if (!BN_mod_sqr(t, b, p, ctx)) goto end;
+                if (!BN_mod_sqr(t, b, p, ctx))
-                while (!BN_is_one(t))
+                        goto end;
-                        {
+                while (!BN_is_one(t)) {
                        i++;
-                        if (i == e)
+                        if (i == e) {
-                                {
                                BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
                                goto end;
-                                }
-                        if (!BN_mod_mul(t, t, t, p, ctx)) goto end;
                        }
-                
+                        if (!BN_mod_mul(t, t, t, p, ctx))
+                                goto end;
+                }
                /* t := y^2^(e - i - 1) */
-                if (!BN_copy(t, y)) goto end;
+                if (!BN_copy(t, y))
-                for (j = e - i - 1; j > 0; j--)
+                        goto end;
-                        {
+                for (j = e - i - 1; j > 0; j--) {
-                        if (!BN_mod_sqr(t, t, p, ctx)) goto end;
+                        if (!BN_mod_sqr(t, t, p, ctx))
-                        }
+                                goto end;
-                if (!BN_mod_mul(y, t, t, p, ctx)) goto end;
-                if (!BN_mod_mul(x, x, t, p, ctx)) goto end;
-                if (!BN_mod_mul(b, b, y, p, ctx)) goto end;
-                e = i;
                }
+                if (!BN_mod_mul(y, t, t, p, ctx))
+                        goto end;
+                if (!BN_mod_mul(x, x, t, p, ctx))
+                        goto end;
+                if (!BN_mod_mul(b, b, y, p, ctx))
+                        goto end;
+                e = i;
+        }
- vrfy:
+vrfy:
-        if (!err)
+        if (!err) {
-                {
                /* verify the result -- the input might have been not a square
                 * (test added in 0.9.8) */
-                
                if (!BN_mod_sqr(x, ret, p, ctx))
                        err = 1;
-                
-                if (!err && 0 != BN_cmp(x, A))
+                if (!err && 0 != BN_cmp(x, A)) {
-                        {
                        BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
                        err = 1;
-                        }
                }
+        }
- end:
+end:
-        if (err)
+        if (err) {
-                {
+                if (ret != NULL && ret != in) {
-                if (ret != NULL && ret != in)
-                        {
                        BN_clear_free(ret);
-                        }
-                ret = NULL;
                }
+                ret = NULL;
+        }
        BN_CTX_end(ctx);
        bn_check_top(ret);
        return ret;
-        }
+}

diff --git a/src/lib/libcrypto/bn/bn_sqrt.c b/src/lib/libcrypto/bn/bn_sqrt.c index 6beaf9e5e5..89bb067d88 100644 --- a/src/lib/libcrypto/bn/bn_sqrt.c +++ b/src/lib/libcrypto/bn/bn_sqrt.c
@@ -9,7 +9,7 @@
9	* are met:	9	* are met:
10	*	10	*
11	* 1. Redistributions of source code must retain the above copyright	11	* 1. Redistributions of source code must retain the above copyright
12	* notice, this list of conditions and the following disclaimer.	12	* notice, this list of conditions and the following disclaimer.
13	*	13	*
14	* 2. Redistributions in binary form must reproduce the above copyright	14	* 2. Redistributions in binary form must reproduce the above copyright
15	* notice, this list of conditions and the following disclaimer in	15	* notice, this list of conditions and the following disclaimer in
@@ -59,57 +59,53 @@
59	#include "bn_lcl.h"	59	#include "bn_lcl.h"
60		60
61		61
62	BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)	62	BIGNUM *
		63	BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX ctx)
63	/* Returns 'ret' such that	64	/* Returns 'ret' such that
64	* ret^2 == a (mod p),	65	* ret^2 == a (mod p),
65	* using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course	66	* using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course
66	* in Algebraic Computational Number Theory", algorithm 1.5.1).	67	* in Algebraic Computational Number Theory", algorithm 1.5.1).
67	* 'p' must be prime!	68	* 'p' must be prime!
68	*/	69	*/
69	{	70	{
70	BIGNUM *ret = in;	71	BIGNUM *ret = in;
71	int err = 1;	72	int err = 1;
72	int r;	73	int r;
73	BIGNUM A, b, q, t, x, y;	74	BIGNUM A, b, q, t, x, y;
74	int e, i, j;	75	int e, i, j;
75		76
76	if (!BN_is_odd(p) \|\| BN_abs_is_word(p, 1))	77	if (!BN_is_odd(p) \|\| BN_abs_is_word(p, 1)) {
77	{	78	if (BN_abs_is_word(p, 2)) {
78	if (BN_abs_is_word(p, 2))
79	{
80	if (ret == NULL)	79	if (ret == NULL)
81	ret = BN_new();	80	ret = BN_new();
82	if (ret == NULL)	81	if (ret == NULL)
83	goto end;	82	goto end;
84	if (!BN_set_word(ret, BN_is_bit_set(a, 0)))	83	if (!BN_set_word(ret, BN_is_bit_set(a, 0))) {
85	{
86	if (ret != in)	84	if (ret != in)
87	BN_free(ret);	85	BN_free(ret);
88	return NULL;	86	return NULL;
89	}	87	}
90	bn_check_top(ret);	88	bn_check_top(ret);
91	return ret;	89	return ret;
92	}	90	}
93		91
94	BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);	92	BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);
95	return(NULL);	93	return (NULL);
96	}	94	}
97		95
98	if (BN_is_zero(a) \|\| BN_is_one(a))	96	if (BN_is_zero(a) \|\| BN_is_one(a)) {
99	{
100	if (ret == NULL)	97	if (ret == NULL)
101	ret = BN_new();	98	ret = BN_new();
102	if (ret == NULL)	99	if (ret == NULL)
103	goto end;	100	goto end;
104	if (!BN_set_word(ret, BN_is_one(a)))	101	if (!BN_set_word(ret, BN_is_one(a))) {
105	{
106	if (ret != in)	102	if (ret != in)
107	BN_free(ret);	103	BN_free(ret);
108	return NULL;	104	return NULL;
109	}	105	}
110	bn_check_top(ret);	106	bn_check_top(ret);
111	return ret;	107	return ret;
112	}	108	}
113		109
114	BN_CTX_start(ctx);	110	BN_CTX_start(ctx);
115	A = BN_CTX_get(ctx);	111	A = BN_CTX_get(ctx);
@@ -118,14 +114,17 @@ BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)
118	t = BN_CTX_get(ctx);	114	t = BN_CTX_get(ctx);
119	x = BN_CTX_get(ctx);	115	x = BN_CTX_get(ctx);
120	y = BN_CTX_get(ctx);	116	y = BN_CTX_get(ctx);
121	if (y == NULL) goto end;	117	if (y == NULL)
122		118	goto end;
		119
123	if (ret == NULL)	120	if (ret == NULL)
124	ret = BN_new();	121	ret = BN_new();
125	if (ret == NULL) goto end;	122	if (ret == NULL)
		123	goto end;
126		124
127	/* A = a mod p */	125	/* A = a mod p */
128	if (!BN_nnmod(A, a, p, ctx)) goto end;	126	if (!BN_nnmod(A, a, p, ctx))
		127	goto end;
129		128
130	/* now write \|p\| - 1 as 2^eq where q is odd /	129	/* now write \|p\| - 1 as 2^eq where q is odd /
131	e = 1;	130	e = 1;
@@ -133,8 +132,7 @@ BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)
133	e++;	132	e++;
134	/* we'll set q later (if needed) */	133	/* we'll set q later (if needed) */
135		134
136	if (e == 1)	135	if (e == 1) {
137	{
138	/* The easy case: (\|p\|-1)/2 is odd, so 2 has an inverse	136	/* The easy case: (\|p\|-1)/2 is odd, so 2 has an inverse
139	* modulo (\|p\|-1)/2, and square roots can be computed	137	* modulo (\|p\|-1)/2, and square roots can be computed
140	* directly by modular exponentiation.	138	* directly by modular exponentiation.
@@ -142,16 +140,18 @@ BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)
142	* 2 * (\|p\|+1)/4 == 1 (mod (\|p\|-1)/2),	140	* 2 * (\|p\|+1)/4 == 1 (mod (\|p\|-1)/2),
143	* so we can use exponent (\|p\|+1)/4, i.e. (\|p\|-3)/4 + 1.	141	* so we can use exponent (\|p\|+1)/4, i.e. (\|p\|-3)/4 + 1.
144	*/	142	*/
145	if (!BN_rshift(q, p, 2)) goto end;	143	if (!BN_rshift(q, p, 2))
		144	goto end;
146	q->neg = 0;	145	q->neg = 0;
147	if (!BN_add_word(q, 1)) goto end;	146	if (!BN_add_word(q, 1))
148	if (!BN_mod_exp(ret, A, q, p, ctx)) goto end;	147	goto end;
		148	if (!BN_mod_exp(ret, A, q, p, ctx))
		149	goto end;
149	err = 0;	150	err = 0;
150	goto vrfy;	151	goto vrfy;
151	}	152	}
152		153
153	if (e == 2)	154	if (e == 2) {
154	{
155	/* \|p\| == 5 (mod 8)	155	/* \|p\| == 5 (mod 8)
156	*	156	*
157	* In this case 2 is always a non-square since	157	* In this case 2 is always a non-square since
@@ -173,74 +173,81 @@ BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)
173	* = a(-i)i	173	* = a(-i)i
174	* = a.	174	* = a.
175	*	175	*
176	* (This is due to A.O.L. Atkin,	176	* (This is due to A.O.L. Atkin,
177	* <URL: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>,	177	* <URL: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>,
178	* November 1992.)	178	* November 1992.)
179	*/	179	*/
180		180
181	/* t := 2a /	181	/* t := 2a /
182	if (!BN_mod_lshift1_quick(t, A, p)) goto end;	182	if (!BN_mod_lshift1_quick(t, A, p))
		183	goto end;
183		184
184	/* b := (2a)^((\|p\|-5)/8) /	185	/* b := (2a)^((\|p\|-5)/8) /
185	if (!BN_rshift(q, p, 3)) goto end;	186	if (!BN_rshift(q, p, 3))
		187	goto end;
186	q->neg = 0;	188	q->neg = 0;
187	if (!BN_mod_exp(b, t, q, p, ctx)) goto end;	189	if (!BN_mod_exp(b, t, q, p, ctx))
		190	goto end;
188		191
189	/* y := b^2 */	192	/* y := b^2 */
190	if (!BN_mod_sqr(y, b, p, ctx)) goto end;	193	if (!BN_mod_sqr(y, b, p, ctx))
		194	goto end;
191		195
192	/* t := (2a)b^2 - 1*/	196	/* t := (2a)b^2 - 1*/
193	if (!BN_mod_mul(t, t, y, p, ctx)) goto end;	197	if (!BN_mod_mul(t, t, y, p, ctx))
194	if (!BN_sub_word(t, 1)) goto end;	198	goto end;
		199	if (!BN_sub_word(t, 1))
		200	goto end;
195		201
196	/* x = abt */	202	/* x = abt */
197	if (!BN_mod_mul(x, A, b, p, ctx)) goto end;	203	if (!BN_mod_mul(x, A, b, p, ctx))
198	if (!BN_mod_mul(x, x, t, p, ctx)) goto end;	204	goto end;
		205	if (!BN_mod_mul(x, x, t, p, ctx))
		206	goto end;
199		207
200	if (!BN_copy(ret, x)) goto end;	208	if (!BN_copy(ret, x))
		209	goto end;
201	err = 0;	210	err = 0;
202	goto vrfy;	211	goto vrfy;
203	}	212	}
204		213
205	/* e > 2, so we really have to use the Tonelli/Shanks algorithm.	214	/* e > 2, so we really have to use the Tonelli/Shanks algorithm.
206	* First, find some y that is not a square. */	215	* First, find some y that is not a square. */
207	if (!BN_copy(q, p)) goto end; /* use 'q' as temp */	216	if (!BN_copy(q, p)) goto end; /* use 'q' as temp */
208	q->neg = 0;	217	q->neg = 0;
209	i = 2;	218	i = 2;
210	do	219	do {
211	{
212	/* For efficiency, try small numbers first;	220	/* For efficiency, try small numbers first;
213	* if this fails, try random numbers.	221	* if this fails, try random numbers.
214	*/	222	*/
215	if (i < 22)	223	if (i < 22) {
216	{	224	if (!BN_set_word(y, i))
217	if (!BN_set_word(y, i)) goto end;	225	goto end;
		226	} else {
		227	if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0))
		228	goto end;
		229	if (BN_ucmp(y, p) >= 0) {
		230	if (!(p->neg ? BN_add : BN_sub)(y, y, p))
		231	goto end;
218	}	232	}
219	else
220	{
221	if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0)) goto end;
222	if (BN_ucmp(y, p) >= 0)
223	{
224	if (!(p->neg ? BN_add : BN_sub)(y, y, p)) goto end;
225	}
226	/* now 0 <= y < \|p\| */	233	/* now 0 <= y < \|p\| */
227	if (BN_is_zero(y))	234	if (BN_is_zero(y))
228	if (!BN_set_word(y, i)) goto end;	235	if (!BN_set_word(y, i))
229	}	236	goto end;
230		237	}
		238
231	r = BN_kronecker(y, q, ctx); /* here 'q' is \|p\| */	239	r = BN_kronecker(y, q, ctx); /* here 'q' is \|p\| */
232	if (r < -1) goto end;	240	if (r < -1)
233	if (r == 0)	241	goto end;
234	{	242	if (r == 0) {
235	/* m divides p */	243	/* m divides p */
236	BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);	244	BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);
237	goto end;	245	goto end;
238	}
239	}	246	}
		247	}
240	while (r == 1 && ++i < 82);	248	while (r == 1 && ++i < 82);
241		249
242	if (r != -1)	250	if (r != -1) {
243	{
244	/* Many rounds and still no non-square -- this is more likely	251	/* Many rounds and still no non-square -- this is more likely
245	* a bug than just bad luck.	252	* a bug than just bad luck.
246	* Even if p is not prime, we should have found some y	253	* Even if p is not prime, we should have found some y
@@ -248,19 +255,20 @@ BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)
248	*/	255	*/
249	BNerr(BN_F_BN_MOD_SQRT, BN_R_TOO_MANY_ITERATIONS);	256	BNerr(BN_F_BN_MOD_SQRT, BN_R_TOO_MANY_ITERATIONS);
250	goto end;	257	goto end;
251	}	258	}
252		259
253	/* Here's our actual 'q': */	260	/* Here's our actual 'q': */
254	if (!BN_rshift(q, q, e)) goto end;	261	if (!BN_rshift(q, q, e))
		262	goto end;
255		263
256	/* Now that we have some non-square, we can find an element	264	/* Now that we have some non-square, we can find an element
257	* of order 2^e by computing its q'th power. */	265	* of order 2^e by computing its q'th power. */
258	if (!BN_mod_exp(y, y, q, p, ctx)) goto end;	266	if (!BN_mod_exp(y, y, q, p, ctx))
259	if (BN_is_one(y))	267	goto end;
260	{	268	if (BN_is_one(y)) {
261	BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);	269	BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);
262	goto end;	270	goto end;
263	}	271	}
264		272
265	/* Now we know that (if p is indeed prime) there is an integer	273	/* Now we know that (if p is indeed prime) there is an integer
266	* k, 0 <= k < 2^e, such that	274	* k, 0 <= k < 2^e, such that
@@ -279,45 +287,45 @@ BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)
279	*	287	*
280	* so it is the square root that we are looking for.	288	* so it is the square root that we are looking for.
281	*/	289	*/
282		290
283	/* t := (q-1)/2 (note that q is odd) */	291	/* t := (q-1)/2 (note that q is odd) */
284	if (!BN_rshift1(t, q)) goto end;	292	if (!BN_rshift1(t, q))
285		293	goto end;
		294
286	/* x := a^((q-1)/2) */	295	/* x := a^((q-1)/2) */
287	if (BN_is_zero(t)) /* special case: p = 2^e + 1 */	296	if (BN_is_zero(t)) /* special case: p = 2^e + 1 */
288	{	297	{
289	if (!BN_nnmod(t, A, p, ctx)) goto end;	298	if (!BN_nnmod(t, A, p, ctx))
290	if (BN_is_zero(t))	299	goto end;
291	{	300	if (BN_is_zero(t)) {
292	/* special case: a == 0 (mod p) */	301	/* special case: a == 0 (mod p) */
293	BN_zero(ret);	302	BN_zero(ret);
294	err = 0;	303	err = 0;
295	goto end;	304	goto end;
296	}	305	} else if (!BN_one(x))
297	else	306	goto end;
298	if (!BN_one(x)) goto end;	307	} else {
299	}	308	if (!BN_mod_exp(x, A, t, p, ctx))
300	else	309	goto end;
301	{	310	if (BN_is_zero(x)) {
302	if (!BN_mod_exp(x, A, t, p, ctx)) goto end;
303	if (BN_is_zero(x))
304	{
305	/* special case: a == 0 (mod p) */	311	/* special case: a == 0 (mod p) */
306	BN_zero(ret);	312	BN_zero(ret);
307	err = 0;	313	err = 0;
308	goto end;	314	goto end;
309	}
310	}	315	}
		316	}
311		317
312	/* b := ax^2 (= a^q) /	318	/* b := ax^2 (= a^q) /
313	if (!BN_mod_sqr(b, x, p, ctx)) goto end;	319	if (!BN_mod_sqr(b, x, p, ctx))
314	if (!BN_mod_mul(b, b, A, p, ctx)) goto end;	320	goto end;
315		321	if (!BN_mod_mul(b, b, A, p, ctx))
		322	goto end;
		323
316	/* x := ax (= a^((q+1)/2)) /	324	/* x := ax (= a^((q+1)/2)) /
317	if (!BN_mod_mul(x, x, A, p, ctx)) goto end;	325	if (!BN_mod_mul(x, x, A, p, ctx))
		326	goto end;
318		327
319	while (1)	328	while (1) {
320	{
321	/* Now b is a^q * y^k for some even k (0 <= k < 2^E	329	/* Now b is a^q * y^k for some even k (0 <= k < 2^E
322	* where E refers to the original value of e, which we	330	* where E refers to the original value of e, which we
323	* don't keep in a variable), and x is a^((q+1)/2) * y^(k/2).	331	* don't keep in a variable), and x is a^((q+1)/2) * y^(k/2).
@@ -327,67 +335,67 @@ BIGNUM BN_mod_sqrt(BIGNUM in, const BIGNUM a, const BIGNUM p, BN_CTX *ctx)
327	* b^2^(e-1) = 1.	335	* b^2^(e-1) = 1.
328	*/	336	*/
329		337
330	if (BN_is_one(b))	338	if (BN_is_one(b)) {
331	{	339	if (!BN_copy(ret, x))
332	if (!BN_copy(ret, x)) goto end;	340	goto end;
333	err = 0;	341	err = 0;
334	goto vrfy;	342	goto vrfy;
335	}	343	}
336		344
337		345
338	/* find smallest i such that b^(2^i) = 1 */	346	/* find smallest i such that b^(2^i) = 1 */
339	i = 1;	347	i = 1;
340	if (!BN_mod_sqr(t, b, p, ctx)) goto end;	348	if (!BN_mod_sqr(t, b, p, ctx))
341	while (!BN_is_one(t))	349	goto end;
342	{	350	while (!BN_is_one(t)) {
343	i++;	351	i++;
344	if (i == e)	352	if (i == e) {
345	{
346	BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);	353	BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
347	goto end;	354	goto end;
348	}
349	if (!BN_mod_mul(t, t, t, p, ctx)) goto end;
350	}	355	}
351		356	if (!BN_mod_mul(t, t, t, p, ctx))
		357	goto end;
		358	}
		359
352		360
353	/* t := y^2^(e - i - 1) */	361	/* t := y^2^(e - i - 1) */
354	if (!BN_copy(t, y)) goto end;	362	if (!BN_copy(t, y))
355	for (j = e - i - 1; j > 0; j--)	363	goto end;
356	{	364	for (j = e - i - 1; j > 0; j--) {
357	if (!BN_mod_sqr(t, t, p, ctx)) goto end;	365	if (!BN_mod_sqr(t, t, p, ctx))
358	}	366	goto end;
359	if (!BN_mod_mul(y, t, t, p, ctx)) goto end;
360	if (!BN_mod_mul(x, x, t, p, ctx)) goto end;
361	if (!BN_mod_mul(b, b, y, p, ctx)) goto end;
362	e = i;
363	}	367	}
		368	if (!BN_mod_mul(y, t, t, p, ctx))
		369	goto end;
		370	if (!BN_mod_mul(x, x, t, p, ctx))
		371	goto end;
		372	if (!BN_mod_mul(b, b, y, p, ctx))
		373	goto end;
		374	e = i;
		375	}
364		376
365	vrfy:	377	vrfy:
366	if (!err)	378	if (!err) {
367	{
368	/* verify the result -- the input might have been not a square	379	/* verify the result -- the input might have been not a square
369	* (test added in 0.9.8) */	380	* (test added in 0.9.8) */
370		381
371	if (!BN_mod_sqr(x, ret, p, ctx))	382	if (!BN_mod_sqr(x, ret, p, ctx))
372	err = 1;	383	err = 1;
373		384
374	if (!err && 0 != BN_cmp(x, A))	385	if (!err && 0 != BN_cmp(x, A)) {
375	{
376	BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);	386	BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
377	err = 1;	387	err = 1;
378	}
379	}	388	}
		389	}
380		390
381	end:	391	end:
382	if (err)	392	if (err) {
383	{	393	if (ret != NULL && ret != in) {
384	if (ret != NULL && ret != in)
385	{
386	BN_clear_free(ret);	394	BN_clear_free(ret);
387	}
388	ret = NULL;
389	}	395	}
		396	ret = NULL;
		397	}
390	BN_CTX_end(ctx);	398	BN_CTX_end(ctx);
391	bn_check_top(ret);	399	bn_check_top(ret);
392	return ret;	400	return ret;
393	}	401	}