int RSA_check_key(RSA *key)
{
BIGNUM *i, *j, *k, *l, *m;
BN_CTX *ctx;
int r;
int ret=1;
i = BN_new();
j = BN_new();
k = BN_new();
l = BN_new();
m = BN_new();
ctx = BN_CTX_new();
if (i == NULL || j == NULL || k == NULL || l == NULL ||
m == NULL || ctx == NULL)
{
ret = -1;
RSAerr(RSA_F_RSA_CHECK_KEY, ERR_R_MALLOC_FAILURE);
goto err;
}
/* p prime? */
r = BN_is_prime(key->p, BN_prime_checks, NULL, NULL, NULL);
if (r != 1)
{
ret = r;
if (r != 0)
goto err;
RSAerr(RSA_F_RSA_CHECK_KEY, RSA_R_P_NOT_PRIME);
}
/* q prime? */
r = BN_is_prime(key->q, BN_prime_checks, NULL, NULL, NULL);
if (r != 1)
{
ret = r;
if (r != 0)
goto err;
RSAerr(RSA_F_RSA_CHECK_KEY, RSA_R_Q_NOT_PRIME);
}
/* n = p*q? */
r = BN_mul(i, key->p, key->q, ctx);
if (!r) { ret = -1; goto err; }
if (BN_cmp(i, key->n) != 0)
{
ret = 0;
RSAerr(RSA_F_RSA_CHECK_KEY, RSA_R_N_DOES_NOT_EQUAL_P_Q);
}
/* d*e = 1 mod lcm(p-1,q-1)? */
r = BN_sub(i, key->p, BN_value_one());
if (!r) { ret = -1; goto err; }
r = BN_sub(j, key->q, BN_value_one());
if (!r) { ret = -1; goto err; }
/* now compute k = lcm(i,j) */
r = BN_mul(l, i, j, ctx);
if (!r) { ret = -1; goto err; }
r = BN_gcd(m, i, j, ctx);
if (!r) { ret = -1; goto err; }
r = BN_div(k, NULL, l, m, ctx); /* remainder is 0 */
if (!r) { ret = -1; goto err; }
r = BN_mod_mul(i, key->d, key->e, k, ctx);
if (!r) { ret = -1; goto err; }
if (!BN_is_one(i))
{
ret = 0;
RSAerr(RSA_F_RSA_CHECK_KEY, RSA_R_D_E_NOT_CONGRUENT_TO_1);
}
if (key->dmp1 != NULL && key->dmq1 != NULL && key->iqmp != NULL)
{
/* dmp1 = d mod (p-1)? */
r = BN_sub(i, key->p, BN_value_one());
if (!r) { ret = -1; goto err; }
r = BN_mod(j, key->d, i, ctx);
if (!r) { ret = -1; goto err; }
if (BN_cmp(j, key->dmp1) != 0)
{
ret = 0;
RSAerr(RSA_F_RSA_CHECK_KEY,
RSA_R_DMP1_NOT_CONGRUENT_TO_D);
}
/* dmq1 = d mod (q-1)? */
r = BN_sub(i, key->q, BN_value_one());
if (!r) { ret = -1; goto err; }
r = BN_mod(j, key->d, i, ctx);
if (!r) { ret = -1; goto err; }
if (BN_cmp(j, key->dmq1) != 0)
{
//.........这里部分代码省略.........
//.........这里部分代码省略.........
* 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)) goto end;
/* b := (2*a)^((|p|-5)/8) */
if (!BN_rshift(q, p, 3)) goto end;
q->neg = 0;
if (!BN_mod_exp(b, t, q, p, ctx)) goto end;
/* y := b^2 */
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_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, x, t, p, ctx)) 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;
i = 2;
do
{
/* For efficiency, try small numbers first;
* if this fails, try random numbers.
*/
if (i < 22)
{
if (!BN_set_word(y, i)) 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;
}
/*
* Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test.
* OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero).
* The Step numbers listed in the code refer to the enhanced case.
*
* if enhanced is set, then status returns one of the following:
* BN_PRIMETEST_PROBABLY_PRIME
* BN_PRIMETEST_COMPOSITE_WITH_FACTOR
* BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME
* if enhanced is zero, then status returns either
* BN_PRIMETEST_PROBABLY_PRIME or
* BN_PRIMETEST_COMPOSITE
*
* returns 0 if there was an error, otherwise it returns 1.
*/
int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
BN_GENCB *cb, int enhanced, int *status)
{
int i, j, a, ret = 0;
BIGNUM *g, *w1, *w3, *x, *m, *z, *b;
BN_MONT_CTX *mont = NULL;
/* w must be odd */
if (!BN_is_odd(w))
return 0;
BN_CTX_start(ctx);
g = BN_CTX_get(ctx);
w1 = BN_CTX_get(ctx);
w3 = BN_CTX_get(ctx);
x = BN_CTX_get(ctx);
m = BN_CTX_get(ctx);
z = BN_CTX_get(ctx);
b = BN_CTX_get(ctx);
if (!(b != NULL
/* w1 := w - 1 */
&& BN_copy(w1, w)
&& BN_sub_word(w1, 1)
/* w3 := w - 3 */
&& BN_copy(w3, w)
&& BN_sub_word(w3, 3)))
goto err;
/* check w is larger than 3, otherwise the random b will be too small */
if (BN_is_zero(w3) || BN_is_negative(w3))
goto err;
/* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */
a = 1;
while (!BN_is_bit_set(w1, a))
a++;
/* (Step 2) m = (w-1) / 2^a */
if (!BN_rshift(m, w1, a))
goto err;
/* Montgomery setup for computations mod a */
mont = BN_MONT_CTX_new();
if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))
goto err;
if (iterations == BN_prime_checks)
iterations = BN_prime_checks_for_size(BN_num_bits(w));
/* (Step 4) */
for (i = 0; i < iterations; ++i) {
/* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */
if (!BN_priv_rand_range(b, w3) || !BN_add_word(b, 2)) /* 1 < b < w-1 */
goto err;
if (enhanced) {
/* (Step 4.3) */
if (!BN_gcd(g, b, w, ctx))
goto err;
/* (Step 4.4) */
if (!BN_is_one(g)) {
*status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
ret = 1;
goto err;
}
}
/* (Step 4.5) z = b^m mod w */
if (!BN_mod_exp_mont(z, b, m, w, ctx, mont))
goto err;
/* (Step 4.6) if (z = 1 or z = w-1) */
if (BN_is_one(z) || BN_cmp(z, w1) == 0)
goto outer_loop;
/* (Step 4.7) for j = 1 to a-1 */
for (j = 1; j < a ; ++j) {
/* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */
if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
goto err;
/* (Step 4.7.3) */
if (BN_cmp(z, w1) == 0)
goto outer_loop;
/* (Step 4.7.4) */
if (BN_is_one(z))
goto composite;
}
/* At this point z = b^((w-1)/2) mod w */
//.........这里部分代码省略.........
开发者ID:Ana06，项目名称:openssl，代码行数:101，代码来源:bn_prime.c
示例15: ec_GFp_simple_point_get_affine_coordinates
int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
const EC_POINT *point, BIGNUM *x,
BIGNUM *y, BN_CTX *ctx) {
BN_CTX *new_ctx = NULL;
BIGNUM *Z, *Z_1, *Z_2, *Z_3;
const BIGNUM *Z_;
int ret = 0;
if (EC_POINT_is_at_infinity(group, point)) {
OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
return 0;
}
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
if (ctx == NULL) {
return 0;
}
}
BN_CTX_start(ctx);
Z = BN_CTX_get(ctx);
Z_1 = BN_CTX_get(ctx);
Z_2 = BN_CTX_get(ctx);
Z_3 = BN_CTX_get(ctx);
if (Z == NULL || Z_1 == NULL || Z_2 == NULL || Z_3 == NULL) {
goto err;
}
/* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
if (group->meth->field_decode) {
if (!group->meth->field_decode(group, Z, &point->Z, ctx)) {
goto err;
}
Z_ = Z;
} else {
Z_ = &point->Z;
}
if (BN_is_one(Z_)) {
if (group->meth->field_decode) {
if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) {
goto err;
}
if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) {
goto err;
}
} else {
if (x != NULL && !BN_copy(x, &point->X)) {
goto err;
}
if (y != NULL && !BN_copy(y, &point->Y)) {
goto err;
}
}
} else {
if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) {
OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
goto err;
}
if (group->meth->field_encode == 0) {
/* field_sqr works on standard representation */
if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) {
goto err;
}
} else if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) {
goto err;
}
/* in the Montgomery case, field_mul will cancel out Montgomery factor in
* X: */
if (x != NULL && !group->meth->field_mul(group, x, &point->X, Z_2, ctx)) {
goto err;
}
if (y != NULL) {
if (group->meth->field_encode == 0) {
/* field_mul works on standard representation */
if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) {
goto err;
}
} else if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) {
goto err;
}
/* in the Montgomery case, field_mul will cancel out Montgomery factor in
* Y: */
if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) {
goto err;
}
}
}
ret = 1;
err:
BN_CTX_end(ctx);
BN_CTX_free(new_ctx);
//.........这里部分代码省略.........
开发者ID:reaperhulk，项目名称:ring，代码行数:101，代码来源:simple.c
示例16: RSA_check_key
int RSA_check_key(const RSA *key) {
BIGNUM n, pm1, qm1, lcm, gcd, de, dmp1, dmq1, iqmp;
BN_CTX *ctx;
int ok = 0, has_crt_values;
if (RSA_is_opaque(key)) {
/* Opaque keys can't be checked. */
return 1;
}
if ((key->p != NULL) != (key->q != NULL)) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_ONLY_ONE_OF_P_Q_GIVEN);
return 0;
}
if (!key->n || !key->e) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_VALUE_MISSING);
return 0;
}
if (!key->d || !key->p) {
/* For a public key, or without p and q, there's nothing that can be
* checked. */
return 1;
}
ctx = BN_CTX_new();
if (ctx == NULL) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_R_MALLOC_FAILURE);
return 0;
}
BN_init(&n);
BN_init(&pm1);
BN_init(&qm1);
BN_init(&lcm);
BN_init(&gcd);
BN_init(&de);
BN_init(&dmp1);
BN_init(&dmq1);
BN_init(&iqmp);
if (/* n = pq */
!BN_mul(&n, key->p, key->q, ctx) ||
/* lcm = lcm(p-1, q-1) */
!BN_sub(&pm1, key->p, BN_value_one()) ||
!BN_sub(&qm1, key->q, BN_value_one()) ||
!BN_mul(&lcm, &pm1, &qm1, ctx) ||
!BN_gcd(&gcd, &pm1, &qm1, ctx) ||
!BN_div(&lcm, NULL, &lcm, &gcd, ctx) ||
/* de = d*e mod lcm(p-1, q-1) */
!BN_mod_mul(&de, key->d, key->e, &lcm, ctx)) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_LIB_BN);
goto out;
}
if (BN_cmp(&n, key->n) != 0) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_N_NOT_EQUAL_P_Q);
goto out;
}
if (!BN_is_one(&de)) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_D_E_NOT_CONGRUENT_TO_1);
goto out;
}
has_crt_values = key->dmp1 != NULL;
if (has_crt_values != (key->dmq1 != NULL) ||
has_crt_values != (key->iqmp != NULL)) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_INCONSISTENT_SET_OF_CRT_VALUES);
goto out;
}
if (has_crt_values) {
if (/* dmp1 = d mod (p-1) */
!BN_mod(&dmp1, key->d, &pm1, ctx) ||
/* dmq1 = d mod (q-1) */
!BN_mod(&dmq1, key->d, &qm1, ctx) ||
/* iqmp = q^-1 mod p */
!BN_mod_inverse(&iqmp, key->q, key->p, ctx)) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_LIB_BN);
goto out;
}
if (BN_cmp(&dmp1, key->dmp1) != 0 ||
BN_cmp(&dmq1, key->dmq1) != 0 ||
BN_cmp(&iqmp, key->iqmp) != 0) {
OPENSSL_PUT_ERROR(RSA, RSA_check_key, RSA_R_CRT_VALUES_INCORRECT);
goto out;
}
}
ok = 1;
out:
BN_free(&n);
BN_free(&pm1);
BN_free(&qm1);
BN_free(&lcm);
BN_free(&gcd);
//.........这里部分代码省略.........
客服电话
APP下载
官方微信
请发表评论