summaryrefslogtreecommitdiffstats
path: root/crypto/bn
diff options
context:
space:
mode:
Diffstat (limited to 'crypto/bn')
-rw-r--r--crypto/bn/bn_add.c24
-rw-r--r--crypto/bn/bn_exp.c60
-rw-r--r--crypto/bn/bn_gcd.c212
-rw-r--r--crypto/bn/bn_kron.c14
-rw-r--r--crypto/bn/bn_mul.c90
-rw-r--r--crypto/bn/bn_print.c12
-rw-r--r--crypto/bn/bn_sqr.c22
-rw-r--r--crypto/bn/bn_sqrt.c122
8 files changed, 278 insertions, 278 deletions
diff --git a/crypto/bn/bn_add.c b/crypto/bn/bn_add.c
index c48665a038..2f3d110449 100644
--- a/crypto/bn/bn_add.c
+++ b/crypto/bn/bn_add.c
@@ -69,12 +69,12 @@ int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
bn_check_top(a);
bn_check_top(b);
- /*-
- * a + b a+b
- * a + -b a-b
- * -a + b b-a
- * -a + -b -(a+b)
- */
+ /*-
+ * a + b a+b
+ * a + -b a-b
+ * -a + b b-a
+ * -a + -b -(a+b)
+ */
if (a_neg ^ b->neg) {
/* only one is negative */
if (a_neg) {
@@ -265,12 +265,12 @@ int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
bn_check_top(a);
bn_check_top(b);
- /*-
- * a - b a-b
- * a - -b a+b
- * -a - b -(a+b)
- * -a - -b b-a
- */
+ /*-
+ * a - b a-b
+ * a - -b a+b
+ * -a - b -(a+b)
+ * -a - -b b-a
+ */
if (a->neg) {
if (b->neg) {
tmp = a;
diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index b29df546d5..ef67843fc2 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -174,36 +174,36 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
bn_check_top(p);
bn_check_top(m);
- /*-
- * For even modulus m = 2^k*m_odd, it might make sense to compute
- * a^p mod m_odd and a^p mod 2^k separately (with Montgomery
- * exponentiation for the odd part), using appropriate exponent
- * reductions, and combine the results using the CRT.
- *
- * For now, we use Montgomery only if the modulus is odd; otherwise,
- * exponentiation using the reciprocal-based quick remaindering
- * algorithm is used.
- *
- * (Timing obtained with expspeed.c [computations a^p mod m
- * where a, p, m are of the same length: 256, 512, 1024, 2048,
- * 4096, 8192 bits], compared to the running time of the
- * standard algorithm:
- *
- * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration]
- * 55 .. 77 % [UltraSparc processor, but
- * debug-solaris-sparcv8-gcc conf.]
- *
- * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration]
- * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
- *
- * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
- * at 2048 and more bits, but at 512 and 1024 bits, it was
- * slower even than the standard algorithm!
- *
- * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
- * should be obtained when the new Montgomery reduction code
- * has been integrated into OpenSSL.)
- */
+ /*-
+ * For even modulus m = 2^k*m_odd, it might make sense to compute
+ * a^p mod m_odd and a^p mod 2^k separately (with Montgomery
+ * exponentiation for the odd part), using appropriate exponent
+ * reductions, and combine the results using the CRT.
+ *
+ * For now, we use Montgomery only if the modulus is odd; otherwise,
+ * exponentiation using the reciprocal-based quick remaindering
+ * algorithm is used.
+ *
+ * (Timing obtained with expspeed.c [computations a^p mod m
+ * where a, p, m are of the same length: 256, 512, 1024, 2048,
+ * 4096, 8192 bits], compared to the running time of the
+ * standard algorithm:
+ *
+ * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration]
+ * 55 .. 77 % [UltraSparc processor, but
+ * debug-solaris-sparcv8-gcc conf.]
+ *
+ * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration]
+ * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
+ *
+ * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
+ * at 2048 and more bits, but at 512 and 1024 bits, it was
+ * slower even than the standard algorithm!
+ *
+ * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
+ * should be obtained when the new Montgomery reduction code
+ * has been integrated into OpenSSL.)
+ */
#define MONT_MUL_MOD
#define MONT_EXP_WORD
diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c
index d6ee6b44b7..cd5f86b0e2 100644
--- a/crypto/bn/bn_gcd.c
+++ b/crypto/bn/bn_gcd.c
@@ -267,13 +267,13 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
goto err;
}
sign = -1;
- /*-
- * From B = a mod |n|, A = |n| it follows that
- *
- * 0 <= B < A,
- * -sign*X*a == B (mod |n|),
- * sign*Y*a == A (mod |n|).
- */
+ /*-
+ * From B = a mod |n|, A = |n| it follows that
+ *
+ * 0 <= B < A,
+ * -sign*X*a == B (mod |n|),
+ * sign*Y*a == A (mod |n|).
+ */
if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) {
/*
@@ -285,12 +285,12 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
int shift;
while (!BN_is_zero(B)) {
- /*-
- * 0 < B < |n|,
- * 0 < A <= |n|,
- * (1) -sign*X*a == B (mod |n|),
- * (2) sign*Y*a == A (mod |n|)
- */
+ /*-
+ * 0 < B < |n|,
+ * 0 < A <= |n|,
+ * (1) -sign*X*a == B (mod |n|),
+ * (2) sign*Y*a == A (mod |n|)
+ */
/*
* Now divide B by the maximum possible power of two in the
@@ -336,18 +336,18 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
goto err;
}
- /*-
- * We still have (1) and (2).
- * Both A and B are odd.
- * The following computations ensure that
- *
- * 0 <= B < |n|,
- * 0 < A < |n|,
- * (1) -sign*X*a == B (mod |n|),
- * (2) sign*Y*a == A (mod |n|),
- *
- * and that either A or B is even in the next iteration.
- */
+ /*-
+ * We still have (1) and (2).
+ * Both A and B are odd.
+ * The following computations ensure that
+ *
+ * 0 <= B < |n|,
+ * 0 < A < |n|,
+ * (1) -sign*X*a == B (mod |n|),
+ * (2) sign*Y*a == A (mod |n|),
+ *
+ * and that either A or B is even in the next iteration.
+ */
if (BN_ucmp(B, A) >= 0) {
/* -sign*(X + Y)*a == B - A (mod |n|) */
if (!BN_uadd(X, X, Y))
@@ -376,11 +376,11 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
while (!BN_is_zero(B)) {
BIGNUM *tmp;
- /*-
- * 0 < B < A,
- * (*) -sign*X*a == B (mod |n|),
- * sign*Y*a == A (mod |n|)
- */
+ /*-
+ * 0 < B < A,
+ * (*) -sign*X*a == B (mod |n|),
+ * sign*Y*a == A (mod |n|)
+ */
/* (D, M) := (A/B, A%B) ... */
if (BN_num_bits(A) == BN_num_bits(B)) {
@@ -427,12 +427,12 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
goto err;
}
- /*-
- * Now
- * A = D*B + M;
- * thus we have
- * (**) sign*Y*a == D*B + M (mod |n|).
- */
+ /*-
+ * Now
+ * A = D*B + M;
+ * thus we have
+ * (**) sign*Y*a == D*B + M (mod |n|).
+ */
tmp = A; /* keep the BIGNUM object, the value does not
* matter */
@@ -442,25 +442,25 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
B = M;
/* ... so we have 0 <= B < A again */
- /*-
- * Since the former M is now B and the former B is now A,
- * (**) translates into
- * sign*Y*a == D*A + B (mod |n|),
- * i.e.
- * sign*Y*a - D*A == B (mod |n|).
- * Similarly, (*) translates into
- * -sign*X*a == A (mod |n|).
- *
- * Thus,
- * sign*Y*a + D*sign*X*a == B (mod |n|),
- * i.e.
- * sign*(Y + D*X)*a == B (mod |n|).
- *
- * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
- * -sign*X*a == B (mod |n|),
- * sign*Y*a == A (mod |n|).
- * Note that X and Y stay non-negative all the time.
- */
+ /*-
+ * Since the former M is now B and the former B is now A,
+ * (**) translates into
+ * sign*Y*a == D*A + B (mod |n|),
+ * i.e.
+ * sign*Y*a - D*A == B (mod |n|).
+ * Similarly, (*) translates into
+ * -sign*X*a == A (mod |n|).
+ *
+ * Thus,
+ * sign*Y*a + D*sign*X*a == B (mod |n|),
+ * i.e.
+ * sign*(Y + D*X)*a == B (mod |n|).
+ *
+ * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
+ * -sign*X*a == B (mod |n|),
+ * sign*Y*a == A (mod |n|).
+ * Note that X and Y stay non-negative all the time.
+ */
/*
* most of the time D is very small, so we can optimize tmp :=
@@ -497,13 +497,13 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
}
}
- /*-
- * The while loop (Euclid's algorithm) ends when
- * A == gcd(a,n);
- * we have
- * sign*Y*a == A (mod |n|),
- * where Y is non-negative.
- */
+ /*-
+ * The while loop (Euclid's algorithm) ends when
+ * A == gcd(a,n);
+ * we have
+ * sign*Y*a == A (mod |n|),
+ * where Y is non-negative.
+ */
if (sign < 0) {
if (!BN_sub(Y, n, Y))
@@ -587,22 +587,22 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
goto err;
}
sign = -1;
- /*-
- * From B = a mod |n|, A = |n| it follows that
- *
- * 0 <= B < A,
- * -sign*X*a == B (mod |n|),
- * sign*Y*a == A (mod |n|).
- */
+ /*-
+ * From B = a mod |n|, A = |n| it follows that
+ *
+ * 0 <= B < A,
+ * -sign*X*a == B (mod |n|),
+ * sign*Y*a == A (mod |n|).
+ */
while (!BN_is_zero(B)) {
BIGNUM *tmp;
- /*-
- * 0 < B < A,
- * (*) -sign*X*a == B (mod |n|),
- * sign*Y*a == A (mod |n|)
- */
+ /*-
+ * 0 < B < A,
+ * (*) -sign*X*a == B (mod |n|),
+ * sign*Y*a == A (mod |n|)
+ */
/*
* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
@@ -615,12 +615,12 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
if (!BN_div(D, M, pA, B, ctx))
goto err;
- /*-
- * Now
- * A = D*B + M;
- * thus we have
- * (**) sign*Y*a == D*B + M (mod |n|).
- */
+ /*-
+ * Now
+ * A = D*B + M;
+ * thus we have
+ * (**) sign*Y*a == D*B + M (mod |n|).
+ */
tmp = A; /* keep the BIGNUM object, the value does not
* matter */
@@ -630,25 +630,25 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
B = M;
/* ... so we have 0 <= B < A again */
- /*-
- * Since the former M is now B and the former B is now A,
- * (**) translates into
- * sign*Y*a == D*A + B (mod |n|),
- * i.e.
- * sign*Y*a - D*A == B (mod |n|).
- * Similarly, (*) translates into
- * -sign*X*a == A (mod |n|).
- *
- * Thus,
- * sign*Y*a + D*sign*X*a == B (mod |n|),
- * i.e.
- * sign*(Y + D*X)*a == B (mod |n|).
- *
- * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
- * -sign*X*a == B (mod |n|),
- * sign*Y*a == A (mod |n|).
- * Note that X and Y stay non-negative all the time.
- */
+ /*-
+ * Since the former M is now B and the former B is now A,
+ * (**) translates into
+ * sign*Y*a == D*A + B (mod |n|),
+ * i.e.
+ * sign*Y*a - D*A == B (mod |n|).
+ * Similarly, (*) translates into
+ * -sign*X*a == A (mod |n|).
+ *
+ * Thus,
+ * sign*Y*a + D*sign*X*a == B (mod |n|),
+ * i.e.
+ * sign*(Y + D*X)*a == B (mod |n|).
+ *
+ * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
+ * -sign*X*a == B (mod |n|),
+ * sign*Y*a == A (mod |n|).
+ * Note that X and Y stay non-negative all the time.
+ */
if (!BN_mul(tmp, D, X, ctx))
goto err;
@@ -662,13 +662,13 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
sign = -sign;
}
- /*-
- * The while loop (Euclid's algorithm) ends when
- * A == gcd(a,n);
- * we have
- * sign*Y*a == A (mod |n|),
- * where Y is non-negative.
- */
+ /*-
+ * The while loop (Euclid's algorithm) ends when
+ * A == gcd(a,n);
+ * we have
+ * sign*Y*a == A (mod |n|),
+ * where Y is non-negative.
+ */
if (sign < 0) {
if (!BN_sub(Y, n, Y))
diff --git a/crypto/bn/bn_kron.c b/crypto/bn/bn_kron.c
index 71808321d5..88d731ac75 100644
--- a/crypto/bn/bn_kron.c
+++ b/crypto/bn/bn_kron.c
@@ -66,13 +66,13 @@ int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
int ret = -2; /* avoid 'uninitialized' warning */
int err = 0;
BIGNUM *A, *B, *tmp;
- /*-
- * In 'tab', only odd-indexed entries are relevant:
- * For any odd BIGNUM n,
- * tab[BN_lsw(n) & 7]
- * is $(-1)^{(n^2-1)/8}$ (using TeX notation).
- * Note that the sign of n does not matter.
- */
+ /*-
+ * In 'tab', only odd-indexed entries are relevant:
+ * For any odd BIGNUM n,
+ * tab[BN_lsw(n) & 7]
+ * is $(-1)^{(n^2-1)/8}$ (using TeX notation).
+ * Note that the sign of n does not matter.
+ */
static const int tab[8] = { 0, 1, 0, -1, 0, -1, 0, 1 };
bn_check_top(a);
diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c
index 3b751d3edc..b174850b6b 100644
--- a/crypto/bn/bn_mul.c
+++ b/crypto/bn/bn_mul.c
@@ -527,11 +527,11 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
}
- /*-
- * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
+ /*-
+ * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
+ * r[10] holds (a[0]*b[0])
+ * r[32] holds (b[1]*b[1])
+ */
c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
@@ -542,12 +542,12 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
}
- /*-
- * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- * c1 holds the carry bits
- */
+ /*-
+ * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
+ * r[10] holds (a[0]*b[0])
+ * r[32] holds (b[1]*b[1])
+ * c1 holds the carry bits
+ */
c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
if (c1) {
p = &(r[n + n2]);
@@ -689,11 +689,11 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
}
}
- /*-
- * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
+ /*-
+ * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
+ * r[10] holds (a[0]*b[0])
+ * r[32] holds (b[1]*b[1])
+ */
c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
@@ -704,12 +704,12 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
}
- /*-
- * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- * c1 holds the carry bits
- */
+ /*-
+ * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
+ * r[10] holds (a[0]*b[0])
+ * r[32] holds (b[1]*b[1])
+ * c1 holds the carry bits
+ */
c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
if (c1) {
p = &(r[n + n2]);
@@ -828,13 +828,13 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2]));
}
- /*-
- * s0 == low(al*bl)
- * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
- * We know s0 and s1 so the only unknown is high(al*bl)
- * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
- * high(al*bl) == s1 - (r[0]+l[0]+t[0])
- */
+ /*-
+ * s0 == low(al*bl)
+ * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
+ * We know s0 and s1 so the only unknown is high(al*bl)
+ * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
+ * high(al*bl) == s1 - (r[0]+l[0]+t[0])
+ */
if (l != NULL) {
lp = &(t[n2 + n]);
c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n));
@@ -859,22 +859,22 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
lp[i] = ((~mp[i]) + 1) & BN_MASK2;
}
- /*-
- * s[0] = low(al*bl)
- * t[3] = high(al*bl)
- * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
- * r[10] = (a[1]*b[1])
- */
- /*-
- * R[10] = al*bl
- * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
- * R[32] = ah*bh
- */
- /*-
- * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
- * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
- * R[3]=r[1]+(carry/borrow)
- */
+ /*-
+ * s[0] = low(al*bl)
+ * t[3] = high(al*bl)
+ * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
+ * r[10] = (a[1]*b[1])
+ */
+ /*-
+ * R[10] = al*bl
+ * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
+ * R[32] = ah*bh
+ */
+ /*-
+ * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
+ * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
+ * R[3]=r[1]+(carry/borrow)
+ */
if (l != NULL) {
lp = &(t[n2]);
c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n));
diff --git a/crypto/bn/bn_print.c b/crypto/bn/bn_print.c
index 984b4cf6b6..15bc51af9e 100644
--- a/crypto/bn/bn_print.c
+++ b/crypto/bn/bn_print.c
@@ -106,12 +106,12 @@ char *BN_bn2dec(const BIGNUM *a)
BIGNUM *t = NULL;
BN_ULONG *bn_data = NULL, *lp;
- /*-
- * get an upper bound for the length of the decimal integer
- * num <= (BN_num_bits(a) + 1) * log(2)
- * <= 3 * BN_num_bits(a) * 0.1001 + log(2) + 1 (rounding error)
- * <= BN_num_bits(a)/10 + BN_num_bits/1000 + 1 + 1
- */
+ /*-
+ * get an upper bound for the length of the decimal integer
+ * num <= (BN_num_bits(a) + 1) * log(2)
+ * <= 3 * BN_num_bits(a) * 0.1001 + log(2) + 1 (rounding error)
+ * <= BN_num_bits(a)/10 + BN_num_bits/1000 + 1 + 1
+ */
i = BN_num_bits(a) * 3;
num = (i / 10 + i / 1000 + 1) + 1;
bn_data =
diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c
index 51daae4481..3ca69879ee 100644
--- a/crypto/bn/bn_sqr.c
+++ b/crypto/bn/bn_sqr.c
@@ -249,23 +249,23 @@ void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t)
bn_sqr_recursive(r, a, n, p);
bn_sqr_recursive(&(r[n2]), &(a[n]), n, p);
- /*-
- * t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
+ /*-
+ * t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
+ * r[10] holds (a[0]*b[0])
+ * r[32] holds (b[1]*b[1])
+ */
c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
/* t[32] is negative */
c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
- /*-
- * t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
- * r[10] holds (a[0]*a[0])
- * r[32] holds (a[1]*a[1])
- * c1 holds the carry bits
- */
+ /*-
+ * t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
+ * r[10] holds (a[0]*a[0])
+ * r[32] holds (a[1]*a[1])
+ * c1 holds the carry bits
+ */
c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
if (c1) {
p = &(r[n + n2]);
diff --git a/crypto/bn/bn_sqrt.c b/crypto/bn/bn_sqrt.c
index 772c8080bb..232af99a21 100644
--- a/crypto/bn/bn_sqrt.c
+++ b/crypto/bn/bn_sqrt.c
@@ -132,14 +132,14 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
/* we'll set q later (if needed) */
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.
- * We have
- * 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2),
- * so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 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.
+ * We have
+ * 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;
q->neg = 0;
@@ -152,32 +152,32 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
}
if (e == 2) {
- /*-
- * |p| == 5 (mod 8)
- *
- * In this case 2 is always a non-square since
- * Legendre(2,p) = (-1)^((p^2-1)/8) for any odd prime.
- * So if a really is a square, then 2*a is a non-square.
- * Thus for
- * b := (2*a)^((|p|-5)/8),
- * i := (2*a)*b^2
- * we have
- * i^2 = (2*a)^((1 + (|p|-5)/4)*2)
- * = (2*a)^((p-1)/2)
- * = -1;
- * so if we set
- * x := a*b*(i-1),
- * then
- * x^2 = a^2 * b^2 * (i^2 - 2*i + 1)
- * = a^2 * b^2 * (-2*i)
- * = a*(-i)*(2*a*b^2)
- * = a*(-i)*i
- * = a.
- *
- * (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.)
- */
+ /*-
+ * |p| == 5 (mod 8)
+ *
+ * In this case 2 is always a non-square since
+ * Legendre(2,p) = (-1)^((p^2-1)/8) for any odd prime.
+ * So if a really is a square, then 2*a is a non-square.
+ * Thus for
+ * b := (2*a)^((|p|-5)/8),
+ * i := (2*a)*b^2
+ * we have
+ * i^2 = (2*a)^((1 + (|p|-5)/4)*2)
+ * = (2*a)^((p-1)/2)
+ * = -1;
+ * so if we set
+ * x := a*b*(i-1),
+ * then
+ * x^2 = a^2 * b^2 * (i^2 - 2*i + 1)
+ * = a^2 * b^2 * (-2*i)
+ * = a*(-i)*(2*a*b^2)
+ * = a*(-i)*i
+ * = a.
+ *
+ * (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))
@@ -277,24 +277,24 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
goto end;
}
- /*-
- * Now we know that (if p is indeed prime) there is an integer
- * k, 0 <= k < 2^e, such that
- *
- * a^q * y^k == 1 (mod p).
- *
- * As a^q is a square and y is not, k must be even.
- * q+1 is even, too, so there is an element
- *
- * X := a^((q+1)/2) * y^(k/2),
- *
- * and it satisfies
- *
- * X^2 = a^q * a * y^k
- * = a,
- *
- * so it is the square root that we are looking for.
- */
+ /*-
+ * Now we know that (if p is indeed prime) there is an integer
+ * k, 0 <= k < 2^e, such that
+ *
+ * a^q * y^k == 1 (mod p).
+ *
+ * As a^q is a square and y is not, k must be even.
+ * q+1 is even, too, so there is an element
+ *
+ * X := a^((q+1)/2) * y^(k/2),
+ *
+ * and it satisfies
+ *
+ * X^2 = a^q * a * y^k
+ * = a,
+ *
+ * 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))
@@ -333,15 +333,15 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
goto end;
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).
- *
- * We have a*b = x^2,
- * y^2^(e-1) = -1,
- * b^2^(e-1) = 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).
+ *
+ * We have a*b = x^2,
+ * y^2^(e-1) = -1,
+ * b^2^(e-1) = 1.
+ */
if (BN_is_one(b)) {
if (!BN_copy(ret, x))
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-26 12:19:21 +0000