# crypto:mod_exp/3 returns wrong result?

5 messages
Open this post in threaded view
|

## crypto:mod_exp/3 returns wrong result?

 Hi all,As the doc says:mod_exp(N, P, M) -> ResultTypes:N, P, M, Result = MpintMpint = binary()This function performs the exponentiation N ^ P mod M, using the crypto library. Now, assume: N = -2, P = 3, M = 3Then: 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).22> crypto:mod_exp(2, 3, 3). 23> crypto:mod_exp(-2, 3, -3).14> crypto:mod_exp(2, 3, -3).8Python 2.7.1 (r271:86832, Mar 25 2011, 15:07:46)In [1]: pow(-2, 3, 3)Out[1]: 1In [2]: pow(2, 3, 3)Out[2]: 2 In [3]: pow(-2, 3, -3)Out[3]: -2In [4]: pow(2, 3, -3)Out[4]: -1Welcome 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 1irb(main):002:0> 2 ** 3 % 32irb(main):003:0> (-2) ** 3 % (-3)-2irb(main):004:0> 2 ** 3 % (-3)-1Regards,Hanfei _______________________________________________ erlang-questions mailing list [hidden email] http://erlang.org/mailman/listinfo/erlang-questions
Open this post in threaded view
|

## Re: crypto:mod_exp/3 returns wrong result?

 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 #include #include 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\$ ./bn1/Jesper Pettersson Klarna ABOn Sat, May 28, 2011 at 8:22 PM, Hanfei Shen wrote: Hi all,As the doc says:mod_exp(N, P, M) -> ResultTypes:N, P, M, Result = MpintMpint = binary()This function performs the exponentiation N ^ P mod M, using the crypto library. Now, assume: N = -2, P = 3, M = 3Then: 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).22> crypto:mod_exp(2, 3, 3). 23> crypto:mod_exp(-2, 3, -3).14> crypto:mod_exp(2, 3, -3).8Python 2.7.1 (r271:86832, Mar 25 2011, 15:07:46)In [1]: pow(-2, 3, 3)Out[1]: 1In [2]: pow(2, 3, 3)Out[2]: 2 In [3]: pow(-2, 3, -3)Out[3]: -2In [4]: pow(2, 3, -3)Out[4]: -1Welcome 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 1irb(main):002:0> 2 ** 3 % 32irb(main):003:0> (-2) ** 3 % (-3)-2irb(main):004:0> 2 ** 3 % (-3)-1Regards,Hanfei _______________________________________________ erlang-questions mailing list [hidden email] http://erlang.org/mailman/listinfo/erlang-questions -- Jesper PetterssonKlarna ABNorra Stationsgatan 61113 43 Stockholm, SwedenTel:         +46 8 - 120 120 00Mob:       +46 70 - 001 27 25Fax:        +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
Open this post in threaded view
|

## crypto:mod_exp/3 returns wrong result?

 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 > #include > #include > > 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 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>