In [527]:
e=3
In [528]:
p1=1956752826832932957082650074336486942566378034199352125350523342312381913025312675442406526685350427098579473839265857771074226789577853983293784141957443925237636221211754976614487065084616571990688831932038387640192669677334549875586472436226222109016656855899362572306441500257098742148456966235189138250769041734876686463698437936905541388722585022630687967914591146445655506074754113366986061825787059233833362409489807714968646517126727165875874487844136020230251595351067921682872550560776805339588582987871251115615860125855947550832115147033671143380279581641946566892504072936577110185720172632279408537894497238273989669241202172070034995924339205308087149373314141785914772962788345547798625631417555938214674321176979880154402464776497047945449094114925261395105397314877741718318311776964882164630272620483087148245333119217280849167464971491376589416615649330031642659949098091834921121221479593257741392483058861321810289669906104192944450853954159101680674421448474816360008823310348349662014475049433710640522497418109237016484946155579849198277143611446833689861465394305482151867209423965385640374606437308951714760554351468616899500306144623889007175256075856390110015661749908463650752822502623725106630246006543
q1=1625160284018507939788525437278456477842584497746409964301754589124674457423948142579817389352028668465589548200931274317448769554604459108604477912440028472607035893749261592668570255594270210474966517032151993450404732141174826887624255107797002895180368756859109091816471665703524184935007316003578688976815665033192704325790942689629208703467585496006152484734055648597623135475685232057227643430518607612754043099694979649237244496880481058677065035441234567771472302495734696120159460649557392252764642309558639401996657966927744049103448457755203737538258313095808633004397315478312663650252535125327373711820312009151734357101090844857637785977083446710188460916590975999495912020468232021578335747043183256426880498772658023313161558986586860240014354643715855334378590834266228101062923566198185060181734200120388538771740465343459062685471344864712023013915290158661143701018580486545507524663781480983059245334243821970880934831852331912536107364559104031849910494771429819721582209430349646362586402796186850908640344838523310308004735990710668182815944803462762436299505876221735338782261451657167926125692703719498953904312599551852993255723062362978285566752514555964827077173416848357943697396308582700721339238507451
modulus1=p1*q1
In [529]:
p2=1716362260071867927038836158160273076001108281663839018571693858190656142425529076615009028920877137264560078578446842736978330075109883282033245650748759411485559271175277047866364574930949534923388586576170576431919873789758303611921704966219779566373748890392328289865843332773520518418149504199657226509329016216216718294179289146474548796533407296033541493613955242351236908626877876027709013205815908149126648777546138630191131097534422149988173008026795423481160655062118524685171487928164709741335363439053219042871197589731447571912424195728327337759697289239111349572171467700535641715733033075816743593444285664937866425740693890201609424241478064695327578616009726989243155573859443456240068507865134037129237466980440045127022198511961519498680827733360625622811400118741534658493235796906002392681581659210189861123296038714014461767439054451563138667432443326022540802906184127532355039984488238346815191628500606316691108497255948906687116456928577988993837768512446100321653822792681265099439785052522365504147494898144223694167662112095427904183430228264460504098869405036915458842395013206214039209855379966617530410467001720050518078980782189170612227938523864564816671253134912944610077733114964266935088551724601
q2=1108303997272563268842995022809516552972610838092354124409041032147196865881150685487410017234841439158423155845487637463464084400916748998623518760970690203020739181455471327406254804526495908104754913881174423401387677438994194652608910833127202837464919738674500734913643336553753992665802751623203385983282117890156452993947648500468890173075922538132492748885145561067232414368702024023763167234154327245767388270283213736672113640853788793211307227892778108939795079308088397730290865286647583518125311793160843035822489411128348567405159301448372418487363390160899260482387479793167954847125275954359294665099017402333218189930657026873665186337877741498013421970088048779896014884922860393925606694612224829323335787629852504692233268325916511253538704005147580443021803175993083597474832290261471922513453624489783429747569310026521053295688006400869734783380442164011810726368110647467676275299445539059951527002978192599069824692332511571176917593180559597678004460583427819209636391057629959459017054266675924258638626519454386241696616555662682601955363033436249834856783262546884973578479350159416031724819111155108651591099130857472778128616372277473003856769122877137666141571106467067701543137919872098114945646552309
modulus2=p2*q2
In [530]:
p3=1629788355422340687805182517683704195481267556986456621892651135478584384395613855489821438999344726088215047302398288473247404494931288989167135852760126882232290921903072655180706698629801718495756512525905041407893855261872301586377868042519846013118472712693602181511439229654448128670718079538731555622646941625291587948834924415701848542403321298462929697521729069612309229753244967081822086063424433003492144496900546320463772293599556533082318781993384584819328488305536301965125723037139577008339551807297654332128913909929301178227661086413833655288211460861541938912414026777211760816720472373167159348717291966405791186994398340660138758673790836044921298397940976801923628831857404717970814076516075282688109754678669765933352961267356407171025084634514494373070309203702147515980016079635944782919651129618458493733345784347700421535538341052499795057660806681126927277058194796975000125250089025861287730061158730088982408082287287227410846928285522854907226491057501518676109288483175726435833280031517045340749190245858349411588885762281908516371079895885829988710171145515901036783045460244002633213559769155729702462133294604117948979727898744548836629634129698534333156696247355727830081199179338575384434053024707
q3=1693538420832821368299718472089742896755658618100014436417822399388256118709411097383229749933715637060575326061474775608233512329080978390853536482742629886487443507027043997191588747502997287423783945555962630261445445694623564869358723570543330630275427507646179952486272581744747801706941549975057236171889761271025694543534460436891856691220940643857545446168398680317577299072451059474067543420343270785320259150323328316038193356879243408372761469377915364377427471432417200625449730060163724687611841240558596218623763638847705708124501184810699486942922159092040785682099535207888048371322289275895081557720094518829485324668184622948710776402492268284448978013219090654631939609513403750482904337090819061406819471073820150305121569792237258015232244714608497009486862477849450419879602232944166267614998352095670933322911547249783768167021451577328919707768938883288495774554905497792043595300097932656359570826975887664985218298944352044543221504532080605000608629895205870066599100665886478934876772813797059208424769235579474548924209823237312671692384702332678062210002097858263469186426377995456274728831361084521997608169607605246305516120949715602540643681202260389378347035785364925242261695651690674076851243509953
modulus3=p3*q3
In [531]:
m=123456789**250 # set 250 for 4096 bit modulus, 30 for 512 bit modulus
In [532]:
assert m<modulus1 and m>p1 and m>q1
In [533]:
# ZZ is used to coerce <sage.rings.finite_rings.integer_mod.IntegerMod_int> type to <sage.rings.integer.Integer> type
In [534]:
c1=ZZ(pow(m,e,modulus1))
In [535]:
c2=ZZ(pow(m,e,modulus2))
In [536]:
c3=ZZ(pow(m,e,modulus3))
In [537]:
math.gcd(c1,c2,c3)
Out[537]:
1
In [538]:
# tmp=m^e
tmp=crt([c1,c2,c3],[modulus1,modulus2,modulus3])
In [539]:
recovered=tmp**(1/e) # same as tmp^{1/3}, it's cubic sqrt. SageMath can't do 1/5 here. so e=3 only, alas.
In [540]:
m==recovered
Out[540]:
True
In [ ]:
# Now try DIY homebrew algorithm instead of CRT
In [541]:
# The algo from https://crypto.stackexchange.com/questions/6713/low-public-exponent-attack-for-rsa
# See also the older version of the page: https://en.wikipedia.org/w/index.php?title=Chinese_remainder_theorem&oldid=548432813
def solve_eq(cb,cc,cd,nb,nc,nd):
    tb=cb*(nc*nd)*ZZ(pow(nc*nd,-1,nb))
    tc=cc*(nb*nd)*ZZ(pow(nb*nd,-1,nc))
    td=cd*(nb*nc)*ZZ(pow(nb*nc,-1,nd))
    return divmod(tb+tc+td, nb*nc*nd)[1]
In [542]:
assert solve_eq(330,34,419,377,391,589)==1061208
In [543]:
tmp=solve_eq(c1,c2,c3,modulus1,modulus2,modulus3)
In [544]:
recovered=tmp**(1/e)
In [545]:
m==recovered
Out[545]:
True
In [ ]: