Starring at the code, the only Issue I could come up with is that the number you try to invert is actually larger than your modulus.
This would trigger the assert NA<=N which wouldn't hold as the number to invert (of size NA) would be larger than your modulus (N). Confirm at: https://github.com/weidai11/cryptopp/blob/master/integer.cpp#L2643 Could you please try reducing the integers mod p before feeding them into the divide function? This could be implemented as "a %= p;" and "b%=p;" before using them, so you make sure you calculating with field elements in the first place... I think GMP may do this operation automatically or has a more robust inversion routine. BR JPM Am 22.08.2015 um 21:05 schrieb Ryan Sparlin: > I have been writing a program using Crypto++ that implements a > password-authenticated version of Diffie-Hellman key agreement (see > https://tools.ietf.org/html/rfc5683), and I've run into a problem when > performing modular arithmetic of large numbers. > > Section 3 of RFC 5683 describes the protocol for establishing a shared > secret between two parties. It's pretty straightforward, but problems > arise quickly when using the Integer and ModularArithmetic classes in > Crypto++. > > The first message sent from party A and verified by party B is as > follows, from RFC 5683: > > "A --> B: {A, X = H1(A|B|PW)*(g^Ra)} > (The above precondition on PW ensures that X != 0) > > Bob > receives Q (presumably Q = X), verifies that Q != 0 > (if Q = 0, Bob aborts the procedure); > divides Q by H1(A|B|PW) to get Xab, the recovered value of g^Ra" > > (Note that all arithmetic is performed in Zp*) > > X can be computed without any problems. However, when I try to > calculate the inverse of H1(A|B|PW) to derive g^Ra from X, CryptoPP > gives incorrect results and even fails an assert when compiled on > Windows. The modulus (p) I am using is from section 2.3 of RFC 5114 > (see http://tools.ietf.org/html/rfc5114#section-2.3). > > I used the attached code (also pasted here: > http://pastebin.com/2mrGWzcU) and makefile for testing on my laptop > running Windows 10 x64 and on another computer running Debian x64. For > comparison, I used GNU MP to make the same calculations. I also used > two numbers to test, one that I received after computing H1(A|B|PW) > myself, and the other just chosen randomly. Note that H1(A|B|PW) > outputs a 2176-bit number, as required by RFC 5683 when using a > 128-bit shared secret and a 2048-bit prime. > > My output on Debian is as follows: > > /////////////////////////////////////////////////////// > ----------CryptoPP test---------- > > GCD(a, p) = 1. > > GCD(b, p) = 1. > > Inverse of A (mod P) = > 13993266835504151842504901206548108417584389824138473736182586231676639194238581845286585918923663570607522787474364115356812048056124275062720052947173667432537514801232770975833492979079723406647871626453024708952196702974102271092245182512875304997617422322009844590841023010721666577803158723783809165272668020424174330091188840343680120155878855411989905335206223036758595866373734781381531444020197815326819712255068203106628508332387549059905318240891058480107997595577509590928577922233459987421584648453974760630274795761258794226628720022252820850857439428776879893165816481200797014485308195613687964048778. > > Inverse of B (mod P) = > 13705490201830312330074618487513543959803627963141461610718641354044617681024648693581607695965175463332930992176990671363402323447060820803731235587243086931850123948679340567177625055436297406063476964876045951835513255631068244917272415647187312532841754148267692672239676983487332539721182484282458514575342142129585295162496855409848290242035915824263940455304509534320963276427573169012700402409490369067603217889730030691276878064291184501958091755303359443749178182633376777981064406375157151783891809524401739756099236141368130210612964266443607279236983237450212901985524765832298578883758605980809355481403. > > This should be 1 = > 1474346215611490980756747988227131340701647383036764538214523980812964306736508149505782883634343697839876820848394300536367873110622170601765790305048096755697411968914226297433408067892570208629539790395710595020467953422456772185072333961659745637353486136477159596699251342286701263490573011443523338599699561311179747383980121699690474871208944447510197892409456471105748507712079088818780012177642753611077588077008954875266066889741495377555234330378366844111819100642827379052082657811266021370976526141590709232783196589770065606471941008693068832074140146468807064437423905590608377583000987485740813552540. > > This should also be 1 = 1. > > --------------------------------- > ----------GNU MP Test---------- > > GCD(a, p) = 1 > > GCD(b, p) = 1 > > Inverse of A (mod P) = > 674147149428119215672685558204522771170920769109084174752839991638414601892582489711916196468810069279797598523525067972303083412223784656320029769039998518754185346895992199547798726419459469277266912055188127802408278827974762084962832038441772026456119829400036470722102863893039316375929511756059844741581268040930395504257552255503840678636166104522906400928326469566938904913199705823447506409731846985753759689724289161067900394029474558604084732693703124373069863718523768337971387261807598422726146154321566252528246294880189372106735948960772123978874120004455561264311891936927203071345011973359467907802 > > Inverse of B (mod P) = > 13705490201830312330074618487513543959803627963141461610718641354044617681024648693581607695965175463332930992176990671363402323447060820803731235587243086931850123948679340567177625055436297406063476964876045951835513255631068244917272415647187312532841754148267692672239676983487332539721182484282458514575342142129585295162496855409848290242035915824263940455304509534320963276427573169012700402409490369067603217889730030691276878064291184501958091755303359443749178182633376777981064406375157151783891809524401739756099236141368130210612964266443607279236983237450212901985524765832298578883758605980809355481403 > > This should be 1 = 1 > > This should also be 1 = 1 > > ------------------------------- > /////////////////////////////////////////////////////// > > My output on Windows is as follows: > > /////////////////////////////////////////////////////// > ----------CryptoPP test---------- > > GCD(a, p) = 1. > > GCD(b, p) = 1. > > Assertion failed! > > Program: <path-to-test.exe> > File: integer.cpp, Line 2629 > > Expression: NA<=N && N && N%2==0 > > This application has requested the Runtime to terminate it in an > unusual way. > Please contact the application's support team for more information. > /////////////////////////////////////////////////////// > > The calculated inverse of A is incorrect when calculated using > Crypto++ on Debian. The correct inverse is given by GNU MP (verified > using the online tool located here: > http://www.mobilefish.com/services/big_number_equation/big_number_equation.php). > More surprisingly, the expression arith.Divide(a, a) does not return > 1! CryptoPP does calculate the inverse and the expected output of 1 > correctly when tested on the number B ("1337"). > > On Windows, I am using CryptoPP 5.6.2 as a shared library (DLL) that I > compiled using mingw-w64. On Debian, I tested using CryptoPP 5.6.1 > obtained via apt-get and using CryptoPP 5.6.2 as a static library that > I compiled myself. Both versions give the same output. > > More specific version information is as follows. > > Windows: > > uname -a > windows32 ryan-laptop 2.6.2 9200 i686-pc Intel unknown MinGW > > g++ -v > Using built-in specs. > COLLECT_GCC=g++ > COLLECT_LTO_WRAPPER=C:/Program\ > Files/mingw-w64/x86_64-5.1.0-release-posix-seh-rt_v4-rev0/mingw64/bin/../libexec/gcc/x86_64-w64-mingw32/5.1.0/lto-wrapper.exe > Target: x86_64-w64-mingw32 > Configured with: ../../../src/gcc-5.1.0/configure > --host=x86_64-w64-mingw32 --build=x86_64-w64-mingw32 > --target=x86_64-w64-mingw32 --prefix=/mingw64 > --with-sysroot=/c/mingw510/x86_64-510-posix-seh-rt_v4-rev0/mingw64 > --with-gxx-include-dir=/mingw64/x86_64-w64-mingw32/include/c++ > --enable-shared --enable-static --disable-multilib > --enable-languages=ada,c,c++,fortran,objc,obj-c++,lto > --enable-libstdcxx-time=yes --enable-threads=posix --enable-libgomp > --enable-libatomic --enable-lto --enable-graphite > --enable-checking=release --enable-fully-dynamic-string > --enable-version-specific-runtime-libs --disable-isl-version-check > --disable-libstdcxx-pch --disable-libstdcxx-debug --enable-bootstrap > --disable-rpath --disable-win32-registry --disable-nls > --disable-werror --disable-symvers --with-gnu-as --with-gnu-ld > --with-arch=nocona --with-tune=core2 --with-libiconv > --with-system-zlib > --with-gmp=/c/mingw510/prerequisites/x86_64-w64-mingw32-static > --with-mpfr=/c/mingw510/prerequisites/x86_64-w64-mingw32-static > --with-mpc=/c/mingw510/prerequisites/x86_64-w64-mingw32-static > --with-isl=/c/mingw510/prerequisites/x86_64-w64-mingw32-static > --with-pkgversion='x86_64-posix-seh-rev0, Built by MinGW-W64 project' > --with-bugurl=http://sourceforge.net/projects/mingw-w64 CFLAGS='-O2 > -pipe > -I/c/mingw510/x86_64-510-posix-seh-rt_v4-rev0/mingw64/opt/include > -I/c/mingw510/prerequisites/x86_64-zlib-static/include > -I/c/mingw510/prerequisites/x86_64-w64-mingw32-static/include' > CXXFLAGS='-O2 -pipe > -I/c/mingw510/x86_64-510-posix-seh-rt_v4-rev0/mingw64/opt/include > -I/c/mingw510/prerequisites/x86_64-zlib-static/include > -I/c/mingw510/prerequisites/x86_64-w64-mingw32-static/include' > CPPFLAGS= LDFLAGS='-pipe > -L/c/mingw510/x86_64-510-posix-seh-rt_v4-rev0/mingw64/opt/lib > -L/c/mingw510/prerequisites/x86_64-zlib-static/lib > -L/c/mingw510/prerequisites/x86_64-w64-mingw32-static/lib ' > Thread model: posix > gcc version 5.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project) > > Debian: > > uname -a > Linux ryan-server 4.1.0-1-amd64 #1 SMP Debian 4.1.3-1 (2015-08-03) > x86_64 GNU/Linux > > g++ -v > Using built-in specs. > COLLECT_GCC=g++ > COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.9/lto-wrapper > Target: x86_64-linux-gnu > Configured with: ../src/configure -v --with-pkgversion='Debian > 4.9.3-3' --with-bugurl=file:///usr/share/doc/gcc-4.9/README.Bugs > --enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr > --program-suffix=-4.9 --enable-shared --enable-linker-build-id > --libexecdir=/usr/lib --without-included-gettext > --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.9 > --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu > --enable-libstdcxx-debug --enable-libstdcxx-time=yes > --enable-gnu-unique-object --disable-vtable-verify --enable-plugin > --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk > --enable-gtk-cairo > --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.9-amd64/jre > --enable-java-home > --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.9-amd64 > --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.9-amd64 > --with-arch-directory=amd64 > --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc > --enable-multiarch --with-arch-32=i586 --with-abi=m64 > --with-multilib-list=m32,m64,mx32 --enable-multilib > --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu > --host=x86_64-linux-gnu --target=x86_64-linux-gnu > Thread model: posix > gcc version 4.9.3 (Debian 4.9.3-3) > -- > -- > You received this message because you are subscribed to the "Crypto++ > Users" Google Group. > To unsubscribe, send an email to > [email protected]. > More information about Crypto++ and this group is available at > http://www.cryptopp.com. > --- > You received this message because you are subscribed to the Google > Groups "Crypto++ Users" group. > To unsubscribe from this group and stop receiving emails from it, send > an email to [email protected] > <mailto:[email protected]>. > For more options, visit https://groups.google.com/d/optout. -- -- You received this message because you are subscribed to the "Crypto++ Users" Google Group. To unsubscribe, send an email to [email protected]. More information about Crypto++ and this group is available at http://www.cryptopp.com. --- You received this message because you are subscribed to the Google Groups "Crypto++ Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
smime.p7s
Description: S/MIME Cryptographic Signature
