Created
March 3, 2016 09:56
-
-
Save vqhuy/a7c4a8d28a61f9258980 to your computer and use it in GitHub Desktop.
demo of RSA blind signature attack
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env sage -python2 | |
from sage.all import * | |
e1 = long(599703852157208324988436697659896404638315905290324375700570316485421693) | |
e2 = long(2021187385200166516022746434619391941987919206967476592818217288363509) | |
print 'gcd(e1, e2) = ' + str(gcd(e1, e2)) # should be 1 | |
n = long(108039548283467910018636019706918049787296862983920390620425680109149061265582938100265640505395436176923520902062289606379329490555998996693285930619495040456388113166495283026905991110314710632437395833112529488024010984327573108928719840003018232385552027586272040584786259207191357206321725581066222359269709853312236804681275337051689984480610347322381805920314518020927280061535012383180989715215061621017100281215170089223279840979641688194933238176625422507335413025975742216947757245112001827202742177202602339368271393570814426349) | |
cipher1 = long(64192679490201084919864109589711225051306895753052452251471181011935890793544442381990900483806859201269602393008215002967277584404244028747557515652983421402831933955031514949051711613799413945375516057965907322753883557356486350981432321137639633448144656731569958858836168965404795837648422955123798171558220417018614361054908596961274183141350877544714255973182298022152382603068819975693640211216195897799698027064327186095742305485491820097943409724898378023689276832524319007493796910829806469346146322827201567159126666629388322479) | |
cipher2 = long(59479689549560080704719346207028172045832447629676482962810835773815464251268645222410752554301728769639790100177113106905240622051153394111672911715955043318248120741697967901541458159847100613910368380426590912304442624789475183028091060736577136778183984119998489277854012692016578461901960239232919085733417338853775102362931632001858570236887517967863584958729992234586883928904928030598648389127230808653922583812124081813290524003879897252243176409322823308176329788244775196386356286749265723818517581499920415831945106137632995322) | |
val = xgcd(e1, e2) # extended euclidean algorithm | |
a = -val[1] | |
b = val[2] | |
cipher1_inv = inverse_mod(cipher1, n) # Multiplicative inverse | |
c1a = Mod(cipher1_inv, n) ** a # Square and Multiply algorithm | |
c2b = Mod(cipher2, n) ** b | |
# should print 4561387865153841354984687512687489546516849543684654468465495143548954351686168165161 | |
print 'm = ' + str((c1a * c2b) % n) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment