BN_mod_mul_montgomery returns wrong answers when computing
R = C*D mod P, where the size of P is smaller then the size of
C and D by some amount X of words.
In attachment is a c file that illustrates the error, it compares
the result of BN_mod_mul_montgomery and BN_mod_mul
(bc results agree with BN_mod_mul). Note that no errors
are returned by the calls to BN_to_mongomery or any other
BN function.
The function works if |P| >= |C|, |D|, and some other bizarre
cases.
I tested it with openssl-0.9.4 and SSLeay 0.9.0b, it gives the
same wrong answers.
-- ___________________________________________
Anton Stiglic <[EMAIL PROTECTED]> Crypto Punk
Zero-Knowledge Systems Inc. ___________________________________________
/*
* This shows that BN_mod_mul_montgomery returns the wrong result`
* when computing R = C*D mod P, with P's lenght smaller than
* C and D's by some value X.
* Anton Stiglic ([EMAIL PROTECTED]).
*/
#include <stdio.h>
#include <stdlib.h>
#include "openssl/bn.h"
int main(void) {
int ret = EXIT_FAILURE;
BIGNUM *C = BN_new();
BIGNUM *D = BN_new();
BIGNUM *P = BN_new();
BIGNUM *R1 = BN_new();
BIGNUM *R2 = BN_new();
BN_CTX *ctx = BN_CTX_new();
BN_MONT_CTX *mont = BN_MONT_CTX_new();
/* pick random values to test */
if (! BN_rand(C, 60, 0, 0)) goto done;
if (! BN_rand(D, 60, 0, 0)) goto done;
if (! BN_generate_prime(P, 20, 0, 0, 0, 0, 0)) goto done;
/* set the montgomery context with P */
if (! BN_MONT_CTX_set(mont,P,ctx)) goto done;
/* montgomery reduction to use montgomery mul mod */
if (! BN_to_montgomery(R1, R1, mont, ctx)) goto done;
if (! BN_to_montgomery(C, C, mont, ctx)) goto done;
if (! BN_to_montgomery(D, D, mont, ctx)) goto done;
/* compute montgomery mod mul */
if (! BN_mod_mul_montgomery(R1, C, D, mont, ctx)) goto done;
/* put back everything to regular expression */
if (! BN_from_montgomery(R1, R1, mont, ctx)) goto done;
if (! BN_from_montgomery(C, C, mont, ctx)) goto done;
if (! BN_from_montgomery(D, D, mont, ctx)) goto done;
/* Now try regular way mod mul, put result in R2 */
if ( ! BN_mod_mul(R2, C, D, P, ctx)) goto done;
/* compare *should* return 0 since they *should* be the same */
if (BN_cmp(R1, R2)) {
fprintf(stderr, "NO MATCH!!!\n");
}
ret = EXIT_SUCCESS;
done:
if (C) BN_free(C);
if (D) BN_free(D);
if (P) BN_free(P);
if (R1) BN_free(R1);
if (R2) BN_free(R2);
return ret;
}
