math/big: int: Exp is not consistent with other implementations

[gopherbot]

by hoelle:

math/big/int.Exp is producing different results from equivalent bigint modular
exponentiation functions in other languages/libraries.

Background:
My team maintains SRP implementations in several languages. csrp
(http://code.google.com/p/csrp/) is our target implementation. We have ports in Python,
Ruby, C#.

While adapting a Go implementation (https://code.google.com/p/go-srp/) to match csrp's
salting & padding, we got stuck on an apparent bug in the standard library.
math/big/Int.Exp does not consistently produce the numbers that these other
implementations do (csrp uses openssl's bignum).


Workaround:
github.com/cznic/mathutil has a ModPowBigInt function which is consistent with
csrp/openssl. We are using it successfully.


Demo code:

// Go version: http://play.golang.org/p/cRuXM_8pmt
package main

import "fmt"
import "math/big"

func main() {
    M, _ := big.NewInt(0).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
    t1, _ := big.NewInt(0).SetString("-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2", 0)
    t2, _ := big.NewInt(0).SetString("0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD", 0)
    result := big.NewInt(0).Exp(t1, t2, M)
    fmt.Println(result)
}

// Go output
//
-281922260841133273551070008025043459914555276268337460643460315108526877765261390464352640496671039887789192505298225252794539957185024768842469313161479764129247224181297189401525990925473795326087755094680584008760347811744316689416240130559700085054950633118266475951840800503487485174955924840394049387045989174404949532788547856893369861895770550960914964280527618589465570877605006694415646846171541358662415892984829085205264645240029384180584221302020859884571200976183374536230510251046143237942841512234402830927839775811565384377262636188961565843464936744103267299036324029111735191229863576145323218377

# Python 3.4 version
import math

t1 =
int(b'-1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2',16)
t2 =
int(b'B08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD',16)
M =
int(b'AC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73',16)
S = pow(t1, t2, M)
print(S)

# Python 3.4 Output
#  
21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442

[ianlancetaylor]

Comment 1:

Labels changed: added repo-main, release-go1.5.

[minux]

Comment 2:

they are just using different semantics of Exp.
This is at best a docs issue.
http://play.golang.org/p/eeZnsgQuM-

[agl]

Comment 3:

The result is not wrong here, as such, but the current code means that Exp(x, y, m) !=
Exp(x, y, nil) followed by Mod(m) -- and that seems unfortunate. The "Python" result
does ensure that.
The change is, I think, pretty easy (attached). However, I rather suspect that we can't
make a subtle change like this in Go 1, esp when it's so easy for the reporter to move
the result into the 0 <= x < m range that they want.

Owner changed to @agl.

Attachments:

1. patch (864 bytes)

[griesemer]

Comment 4:

https://golang.org/cl/145650043

Status changed to Started.

[gopherbot]

Comment 5:

CL https://golang.org/cl/145650043 mentions this issue.

[griesemer]

Comment 6:

This issue was closed by revision 28ddfb0.

Status changed to Fixed.