I am trying to reimplement SRP protocol for AWS Cognito in C++ with Boost and looking at Android implementation from Amazon.
I faced an issue where powm function with the same argument returns different results in Java and in C++. Below are real variables to reproduce.
base = -60069516222067934465050534050924735913259123336604003695277708341824332895413979944668873920813978546728706494838542031539374089411576323557683032079456300479576399686088457834323998789559447280306593096633556722918700757880790576568543160534527724248702686289473589204691773279466673778290317667494679021095759596587143108565755917479750768759519224411507201300590256025341023717379667034891896621559345748879219694808586783746072343055239350628677886152249850829448959449884027507137715617906830580188376921330347491783964930384160916882168844833991645809121747349916283613126899731249980617076083650399040055004037242145087844202129219022561806749382444723981250548071098932686072865117465590944246091868534389708960372902345012028512996301150892770425867448873457573540209290963648133766450038070701366521974251173331552053367466421294567346255207594293174647572109245024389844295595423148975431938500850550834122854589221010198699007954971109000609845414067610786404346462923082635417069420150663
exp = 146462318780050704398491824679577877249637357233997958820955798606849034089055435560888738746472653803474347785215052176587544928236521681250726410243117146638424272590451021577470339456543664816801048455555325077949491666342480646917362501726371391429930610071051177605862191601117139467049042192421315075925
mod = 5809605995369958062791915965639201402176612226902900533702900882779736177890990861472094774477339581147373410185646378328043729800750470098210924487866935059164371588168047540943981644516632755067501626434556398193186628990071248660819361205119793693985433297036118232914410171876807536457391277857011849897410207519105333355801121109356897459426271845471397952675959440793493071628394122780510124618488232602464649876850458861245784240929258426287699705312584509625419513463605155428017165714465363094021609290561084025893662561222573202082865797821865270991145082200656978177192827024538990239969175546190770645685893438011714430426409338676314743571154537142031573004276428701433036381801705308659830751190352946025482059931306571004727362479688415574702596946457770284148435989129632853918392117997472632693078113129886487399347796982772784615865232621289656944284216824611318709764535152507354116344703769998514148343807
Java (all variables are BigInteger):
BigInteger x = base.modPow(exp, mod);
x: 1230568615184131985239346694446825655892733339973705775794155717290665406519709910407387531042376274634783342677355212818101752559959454003565957987129773506359982415765799964505534198533317147147330259998210157489219128947077927164476066764792878755295287228542190650053716328463274779372118557925988198416352338648543137326490077853579150463484865391556678099929526143587731521332343634512569891817217753866541107231323752824752313183429346607264168653584884607177140562811376873489718089411252979981686946488318076743666882294457424784508392043142317072588165582750606934742360106685332345292776496954791945874043489368333919203276279792510478642311867043688320756550623809890002329790942184110903137973601678472100031271022409063644536472615014574455126844337240082531858482475302880382827055687831445880729409121007713054522708302456617762637870271318479897319132492452505220079651903923918555883332563223829904474269679
C++ (all variables are cpp_int):
using namespace boost::multiprecision;
cpp_int x = boost::multiprecision::powm(base, exp, mod);
x: -4579037380185826077552569271192375746283878886929194757908745165489070771371280951064707243434963306512590067508291165509941977240791016094644966500737161552804389172402247576438447445983315607920171366436346240703967500042993321496343294440326914938690146068493927582860693843413532757085272719931023651481057868870562196029311043255777746995941406453914719852746433297205761550296050488267940232801270478735923542645526706036493471057499911819023531051727699902448278950652228281938299076303212383112334662802243007282226780266765148417574473754679548198402979499450050043434832720339206644947192678591398824771642404069677795227150129546165836101259287493453710816453652618811430706590859521197756692777588674473925450788908897507360190889864673841119575752609217687752289953513826752471091336430166026751963668992122173432876639494526155021977994961302809759625151724372106098630112631228588798233012140546168609674074128
Where is the issue?
UPDATE:
Python pow(base,exp,mod) returns the same as Java.
Looks like a bug in Boost, or I am using it in wrong way?
That's a documented difference of how signed modulo is implemented.
Try -3 mod 5 for fun.
As an immediate workaround, you can select a different backend (like gmp): Live On Coliru
There is a slight inconsistency between the cpp_int backend and the GMP backend, e.g. testing:
----
CppInt: -3 mod 5 = consistently -3
----
MpzInt: -3 mod 5 = -3
MpzInt: -3 powm 5 = 2
MpzInt: -3 mypm 5 = -3
mismatch
----
CppInt: -3 mod 17 = consistently -3
----
MpzInt: -3 mod 17 = -3
MpzInt: -3 powm 17 = 14
MpzInt: -3 mypm 17 = -3
mismatch
As you can see Boost chose to be consistent for its own types.
Note that the Boost approach seems to be objectively better because it makes sure that the identity (a/b)*b + powm(a,1,b) always holds.
As a simple fix, just add the divisor if the return value is negative:
template <class T> T my_powm(const T& a, const T& p, const T& c) {
using std::abs; // summon the god of ADL
T r = powm(a, p, c);
return r<0? r + abs(c) : r;
}
#include <boost/multiprecision/cpp_int.hpp>
template <class T> T my_powm(const T& a, const T& p, const T& c) {
using std::abs; // summon the god of ADL
T r = powm(a, p, c);
return r<0? r + abs(c) : r;
}
int main() {
boost::multiprecision::cpp_int
base{"-60069516222067934465050534050924735913259123336604003695277708341824332895413979944668873920813978546728706494838542031539374089411576323557683032079456300479576399686088457834323998789559447280306593096633556722918700757880790576568543160534527724248702686289473589204691773279466673778290317667494679021095759596587143108565755917479750768759519224411507201300590256025341023717379667034891896621559345748879219694808586783746072343055239350628677886152249850829448959449884027507137715617906830580188376921330347491783964930384160916882168844833991645809121747349916283613126899731249980617076083650399040055004037242145087844202129219022561806749382444723981250548071098932686072865117465590944246091868534389708960372902345012028512996301150892770425867448873457573540209290963648133766450038070701366521974251173331552053367466421294567346255207594293174647572109245024389844295595423148975431938500850550834122854589221010198699007954971109000609845414067610786404346462923082635417069420150663"},
exp{"146462318780050704398491824679577877249637357233997958820955798606849034089055435560888738746472653803474347785215052176587544928236521681250726410243117146638424272590451021577470339456543664816801048455555325077949491666342480646917362501726371391429930610071051177605862191601117139467049042192421315075925"},
mod{"5809605995369958062791915965639201402176612226902900533702900882779736177890990861472094774477339581147373410185646378328043729800750470098210924487866935059164371588168047540943981644516632755067501626434556398193186628990071248660819361205119793693985433297036118232914410171876807536457391277857011849897410207519105333355801121109356897459426271845471397952675959440793493071628394122780510124618488232602464649876850458861245784240929258426287699705312584509625419513463605155428017165714465363094021609290561084025893662561222573202082865797821865270991145082200656978177192827024538990239969175546190770645685893438011714430426409338676314743571154537142031573004276428701433036381801705308659830751190352946025482059931306571004727362479688415574702596946457770284148435989129632853918392117997472632693078113129886487399347796982772784615865232621289656944284216824611318709764535152507354116344703769998514148343807"};
std::cout << my_powm(base, exp, mod) << "\n";
}
Prints
1230568615184131985239346694446825655892733339973705775794155717290665406519709910407387531042376274634783342677355212818101752559959454003565957987129773506359982415765799964505534198533317147147330259998210157489219128947077927164476066764792878755295287228542190650053716328463274779372118557925988198416352338648543137326490077853579150463484865391556678099929526143587731521332343634512569891817217753866541107231323752824752313183429346607264168653584884607177140562811376873489718089411252979981686946488318076743666882294457424784508392043142317072588165582750606934742360106685332345292776496954791945874043489368333919203276279792510478642311867043688320756550623809890002329790942184110903137973601678472100031271022409063644536472615014574455126844337240082531858482475302880382827055687831445880729409121007713054522708302456617762637870271318479897319132492452505220079651903923918555883332563223829904474269679