crypto:mod_exp/3 returns wrong result?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

crypto:mod_exp/3 returns wrong result?

Hanfei Shen
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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: crypto:mod_exp/3 returns wrong result?

Jesper Pettersson
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 <[hidden email]> 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
[hidden email]
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:     [hidden email]
Web:        www.klarna.com

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

crypto:mod_exp/3 returns wrong result?

Sverker Eriksson-2
Looks like crypto does not handle negative integers correctly at all.

/Sverker, Erlang/OTP

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> 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
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>>    
>
>
>  
> ------------------------------------------------------------------------
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions
> http://erlang.org/mailman/listinfo/erlang-questions
>  



Reply | Threaded
Open this post in threaded view
|

Re: crypto:mod_exp/3 returns wrong result?

Nanitous
In reply to this post by Jesper Pettersson
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 == NULLreturn(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 <[hidden email]> 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
[hidden email]
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:     [hidden email]
Web:        www.klarna.com
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
moi
Reply | Threaded
Open this post in threaded view
|

Re: crypto:mod_exp/3 returns wrong result?

moi
I think the problem with crypto here is if it could not handle negative numbers properly, it should not handle it at all.

crypto:mpint/1 is trying to use complement numbers to represent negatives.
> crypto:mpint(-1).
<<0,0,0,1,255>>
> crypto:mod_exp(-2, 3, -3) == crypto:mod_exp(254, 3, 253).
true

PS, Will Erlang be a possible choice for scientific computation? Like SciPy.