[erlang-questions] crypto:mod_exp/3 returns wrong result?
Nanitous
nanitous@REDACTED
Mon May 30 20:17:22 CEST 2011
Hi Jesper, Hanfei,
For the purpose in cryptographical applications this is not a problem, where in practivce only positive number are considered (actually elements from a group Z_p).
Of course one can debate whether Erlang should faithfully conserve the negative sign between libraries. But, as said before, for the crypto applications of mod_exp, it doesn't matter.
kr
Twan.
I went into the source code (see below) and the following happens:
0. The OpenSSL Big Number representation is a structure in which whether a number is negative is a separate flag in the structure:
struct bignum_st
{
BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */
int top; /* Index of last used d +1. */
/* The next are internal book keeping for bn_expand. */
int dmax; /* Size of the d array. */
int neg; /* one if the number is negative */
int flags;
};
typedef struct bignum_st BIGNUM;
From the openSSL bn.h:
/** BN_set_negative sets sign of a BIGNUM
* \param b pointer to the BIGNUM object
* \param n 0 if the BIGNUM b should be positive and a value != 0 otherwise
*/
void BN_set_negative(BIGNUM *b, int n);
/** BN_is_negative returns 1 if the BIGNUM is negative
* \param a pointer to the BIGNUM object
* \return 1 if a < 0 and 0 otherwise
*/
#define BN_is_negative(a) ((a)->neg != 0)
1. The conversion of Erlang "big number" to openSSL "big numbers" ignores whether the binary big number representation of Erlang signifies a negative number:
static int get_bn_from_mpint(ErlNifEnv* env, ERL_NIF_TERM term, BIGNUM** bnp)
{
ErlNifBinary bin;
int sz;
if (!enif_inspect_binary(env,term,&bin)) {
return 0;
}
ERL_VALGRIND_ASSERT_MEM_DEFINED(bin.data, bin.size);
sz = bin.size - 4;
if (sz < 0 || get_int32(bin.data) != sz) {
return 0;
}
*bnp = BN_bin2bn(bin.data+4, sz, NULL);
return 1;
}
2. The reverse conversion when the openSSL function BN_mod_exp has computed its result, the conversion from the openSSL representation to the Erlang representation ignores again any negative results.
From Erlang: crypto.c
static ERL_NIF_TERM mod_exp_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
{/* (Base,Exponent,Modulo) */
BIGNUM *bn_base=NULL, *bn_exponent=NULL, *bn_modulo, *bn_result;
BN_CTX *bn_ctx;
unsigned char* ptr;
unsigned dlen;
ERL_NIF_TERM ret;
if (!get_bn_from_mpint(env, argv[0], &bn_base)
|| !get_bn_from_mpint(env, argv[1], &bn_exponent)
|| !get_bn_from_mpint(env, argv[2], &bn_modulo)) {
if (bn_base) BN_free(bn_base);
if (bn_exponent) BN_free(bn_exponent);
return enif_make_badarg(env);
}
bn_result = BN_new();
bn_ctx = BN_CTX_new();
BN_mod_exp(bn_result, bn_base, bn_exponent, bn_modulo, bn_ctx);
dlen = BN_num_bytes(bn_result);
ptr = enif_make_new_binary(env, dlen+4, &ret);
put_int32(ptr, dlen);
BN_bn2bin(bn_result, ptr+4);
BN_free(bn_result);
BN_CTX_free(bn_ctx);
BN_free(bn_modulo);
BN_free(bn_exponent);
BN_free(bn_base);
return ret;
}
From: openSSL: bn_lib.h:
BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
{
unsigned int i,m;
unsigned int n;
BN_ULONG l;
BIGNUM *bn = NULL;
if (ret == NULL)
ret = bn = BN_new();
if (ret == NULL) return(NULL);
bn_check_top(ret);
l=0;
n=len;
if (n == 0)
{
ret->top=0;
return(ret);
}
i=((n-1)/BN_BYTES)+1;
m=((n-1)%(BN_BYTES));
if (bn_wexpand(ret, (int)i) == NULL)
{
if (bn) BN_free(bn);
return NULL;
}
ret->top=i;
ret->neg=0;
while (n--)
{
l=(l<<8L)| *(s++);
if (m-- == 0)
{
ret->d[--i]=l;
l=0;
m=BN_BYTES-1;
}
}
/* need to call this due to clear byte at top if avoiding
* having the top bit set (-ve number) */
bn_correct_top(ret);
return(ret);
}
/* ignore negative */
int BN_bn2bin(const BIGNUM *a, unsigned char *to)
{
int n,i;
BN_ULONG l;
bn_check_top(a);
n=i=BN_num_bytes(a);
while (i--)
{
l=a->d[i/BN_BYTES];
*(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
}
return(n);
}
On 30 mei 2011, at 08:39, Jesper Pettersson wrote:
> Writing a small example in C using the bignum library in openssl (used by the Erlang crypto driver) shows that the result there is 1 as well.
>
> #include <stdio.h>
> #include <openssl/crypto.h>
> #include <openssl/bn.h>
>
> int main(int argc, char *argv[])
> {
> static const char b[] = "-2";
> static const char e[] = "3";
> static const char m[] = "3";
>
> BIGNUM *bnb = NULL;
> BIGNUM *bne = NULL;
> BIGNUM *bnm = NULL;
> BIGNUM *res = BN_new();
>
> BN_CTX *ctx = BN_CTX_new();
>
> BN_dec2bn(&bnb, b); /* convert the string to BIGNUM */
> BN_dec2bn(&bne, e);
> BN_dec2bn(&bnm, m);
>
> BN_mod_exp(res, bnb, bne, bnm, ctx);
>
> char *result_str = BN_bn2dec(res); /* convert the res BIGNUM to string */
>
> printf("%s\n", result_str);
>
> OPENSSL_free(result_str);
>
> BN_free(bnb);
> BN_free(bne);
> BN_free(bnm);
> BN_CTX_free(ctx);
>
> return 0;
> }
>
> $ gcc -o bn -lcrypto bn.c
> $ ./bn
> 1
>
> /Jesper Pettersson
> Klarna AB
>
> On Sat, May 28, 2011 at 8:22 PM, Hanfei Shen <qqshfox@REDACTED> wrote:
> Hi all,
>
> As the doc says:
>
> mod_exp(N, P, M) -> Result
>
> Types:
> N, P, M, Result = Mpint
> Mpint = binary()
>
> This function performs the exponentiation N ^ P mod M, using the crypto library.
>
> Now, assume: N = -2, P = 3, M = 3
> Then: N ^ P mod M = (-2) ^ 3 mod 3
> = (-8) mod 3
> = (-3) * 3 + 1
> or = (-3) * 2 + (-2)
> So: the remainder should be 1 or -2
> (Remainder, From Wikipedia, http://en.wikipedia.org/wiki/Remainder)
>
> But I got a TWO from crypto:mod_exp/3... Is there some wrong...?
> And I did more tests with erlang, python and ruby.
> The result:
>
> Erlang R14B02 (erts-5.8.3) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [kernel-poll:false]
>
> Eshell V5.8.3 (abort with ^G)
> 1> crypto:mod_exp(-2, 3, 3).
> 2
> 2> crypto:mod_exp(2, 3, 3).
> 2
> 3> crypto:mod_exp(-2, 3, -3).
> 1
> 4> crypto:mod_exp(2, 3, -3).
> 8
>
> Python 2.7.1 (r271:86832, Mar 25 2011, 15:07:46)
>
> In [1]: pow(-2, 3, 3)
> Out[1]: 1
>
> In [2]: pow(2, 3, 3)
> Out[2]: 2
>
> In [3]: pow(-2, 3, -3)
> Out[3]: -2
>
> In [4]: pow(2, 3, -3)
> Out[4]: -1
>
> Welcome to IRB. You are using ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-linux]. Have fun ;)
> irb(main):001:0> (-2) ** 3 % 3
> 1
> irb(main):002:0> 2 ** 3 % 3
> 2
> irb(main):003:0> (-2) ** 3 % (-3)
> -2
> irb(main):004:0> 2 ** 3 % (-3)
> -1
>
>
> Regards,
> Hanfei
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
>
>
> --
> Jesper Pettersson
>
> Klarna AB
> Norra Stationsgatan 61
> 113 43 Stockholm, Sweden
> Tel: +46 8 - 120 120 00
> Mob: +46 70 - 001 27 25
> Fax: +46 8 - 120 120 99
> E-mail: jesper.pettersson@REDACTED
> Web: www.klarna.com
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20110530/461366f5/attachment.htm>
More information about the erlang-questions
mailing list