RSA common prime attack

I will show how to attack RSA, if two private keys share a same factor . This is the solution of an exercice - We had to decrypt a message given the ciphertext (encrypted message) and two public RSA keys (where a common factor was used to generate them).

The public RSA keys are stored in PEM files. I used openssl to extract the relevant information ($n$ and $e$).

~/Downloads ❯❯❯ openssl asn1parse -in alicepub.pem
    0:d=0  hl=4 l= 522 cons: SEQUENCE          
    4:d=1  hl=4 l= 513 prim: INTEGER           :E6CE768A85EEADE3F379A4736081C2368217B655B4E863221F43ABD60475406E93FCA9007F97140AA5406B16D711356E356A8A3A27D36EAAA861868297C8A232CF89FD6193C3D2611CA0B9BF08E532735ADF680821E9BCF827389DE0A969B1F7A3413BB9A7A4A25BB19F89C2B175A773B73E9A504EDFCAD03DEB0864223621DFA73042178F3BA18526042DA98C4C3220E61836287F4598228BD09BAEF3C07FC3CFC479C04E30290256BDA7F96F81DDF041B4DC06EE7BA9F05230BB80635F2BAEB299CC9B515D750D163116E185BCB0A08213E07FA2E854B4E921BDEDB5628D7D4186D487D7C439E0E8A80CDF4C3666DB95B2A3B3B0C4BC913CEF45C5C30F6E17F550179A9F970568F840600F384D13723D7FA5506321F05164D4473B190417FE68B2120C34D86B7F96106353255EC8DE52D947E1D640C80962A6362E13002ECB4273F3A0B257F5CB5B47610C4C5280F69F2E294DC08310B653414FA148714C56738C2E9D5D87D586E7D6C78182FCBFDC66505384B9919BC92C19491B7F3049599D1840012AF18B9E15C545B5CCEEA2B271EF1BCD0A80B5E139B466D5F204697D632B3402838BEAD0E01E7742BFC1238980CACB47B9277ED58AD32682B3F62957DB5C3AF3D6B0E18221EF34C14475597366A9C340814DF67A260C7C0ED21D8108EB4294F1F007B2B3DC6F65C1B662CA5280A2BBF564BBF11E2FBEA481E35B2513
  521:d=1  hl=2 l=   3 prim: INTEGER           :010001
~/Downloads ❯❯❯ openssl asn1parse -in bobpub.pem
    0:d=0  hl=4 l= 522 cons: SEQUENCE          
    4:d=1  hl=4 l= 513 prim: INTEGER           :BBD890CEF716C16793533BFF054E245E020DAE05A2B978536A8A928E43E341FF1EB5B7F8A2D6389AC0072CBE57494CC328071BEF74890FA065B18648D7B5AF956776ECCA421B4EDE2642ED6D8854BF9BDEA7DB6B0B363F24CDCC047A8B14434ABCB25E32F117A1024F00415ACBB2B18F86689E94EAF5089EAB9852DD8A1236BBE9A45042AEFD8AC5F5BDA5D1D7ED96B2F215D315A27C35443A8073E74B3EBB7BB6823107D916E3D5B09B077F394D138CF1D7FB63FC6ABD6EACBDA93EFC84E285DB76CCAB9A4AAAAC81730673FD2539B491927C5AC2E64A6668302AE4CE268BC07F0042A4E9BFBD752A4C6FC96B977CF68997180FD123DDE7BF1AD54B4319B82880AA4BCAE06FBD20F1F27A2F3E48D1B072B313D51A98677EE54EB5070A607C273067D15169474DF8B0A232CD700AA98A79D819E5367FCF93006D82553E7446ED76A22429718D89E09F23A57EB273077F8DCB1F3593BAC0FAA487FDEC25EF8BC6C9AC597462FF9EF72F44DB2AD9A42A6142242EEAB50161D817CEAF3FAD3554B5A1B35FE3E5721FFBF404EED3EF25E0B7CF68C988BF8B5CDE7C80380F1615317C6770B2DF79D1B805215A1A3EF4D4CF8946AA11802BE8787F4E0DEF30335B24F829B35B3A6C6610196A88875E3C45949A6F1186341AB5C646C63B9A58D2E206EA2931A1464F32499B341119067F3C80CE6072443104B61569E11522F65580475B
  521:d=1  hl=2 l=   3 prim: INTEGER           :010001

Using python's int conversion (e.g. int("hexnum", 16)) I was able to convert the hex-integers to decimal values.

The following python script uses pycrypto to encrypt the massage and generate the private keys. Furthermore a extended euclidean algorithm (egcd) implementation from wikibooks was used.

Because I didn't know which key was used to encrypt the message in advance, I tried both:

from fractions import gcd
from Crypto.PublicKey import RSA

# source: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

bob_n = 766344654790671505215881617123992744873578422169018689104076101964146467546380197838885952535689855408732192819168891377875526890553394054548485356987632256319011800368351185748713615968184725108330897701355751272743904950684202569117734411389192756353448929939409621992691000271406772587907803128843958065769036697518836084915685106469494213589514906282401118254823379621828222701112119190109868887071862418228916632975831151537166569494389132047850953157170740642957402710555556808893413817372175985255971936826527294465818612082592642950494090191757766473227825970464562647874725765260559702004437778345247954963647609818489273792999702578452311469349295351951654951577412775319308598640620051449638980526825901107988480720543486849055886954369847606564927217281129289997149840855739918637472924408645074614636456643077804716675561765588643883474191254989715173918475193394017951740232653708312051338242156447998305349161183587791007542265556501338585641229775618128932572797542829056104651756191696100949806365858732647868221245346460182017304619101896813611562179805786951003959756292436966879888621025423454730810833216425842948232264953429896692008966430109605787667887099293157191031618541311691482148541562728786108591654747L
alice_n = 941608353465240957365828407426575376398971305444382025443977021961748243769051763975706633153057977956677589504746620192315229451595912995089829933990224449416892700665938053037962870747298153092014431276924534629498335963790096626769074472880358317217519300651968441695985721749183492164360999908706004321924030933402577572352477720969291944246402186250512189482405151006920570835940343455661824992140983117106543746254882269934927832180663078453344392310982992061748956545621136557546485188876923155329221809521643450597572762574357840736913677502633841168037233231356110851135585219090256548564594118982659030275848503156084766933990759718812506287635547668896118879482607989750242807826123647402031565573666033944708140107984694560976530201830545788712015823138388965443955574755339528477092330124512782193088447276745725989615454343664740997854483224204787382823938608949821296843449272925357747634205349644345660948913919430013122860324995375643844682685269081056529156104670707258353102198713614058192391485556048037403905421993437973095999601254751698503728859316052907138375048791752328699147773483755229266462656564282737786039679871485056191526752475301565411687917871013268219611441908699368885281544873144750384652952851L
e= 65537L
data = open('../Downloads/message.bin', "rb").read()

## start calculation
p= gcd(alice_n, bob_n)

##
## Alice
##

q_a = alice_n/p
phi_a = (p-1)*(q_a-1)
gcd, x, y = egcd(e, phi_a)

assert gcd == 1 # should be 1 = they have to be coprime
d_a = x % phi_a

private_key_a = RSA.construct((alice_n, e, d_a))
print private_key_a.decrypt(data)

dsmg = private_key_a.decrypt(data)
f = open('alice_pkey.pem','w')
f.write(private_key_a.exportKey('PEM'))
f.close()

##
## BOB
##
q_b = bob_n/p
phi_b = (p-1)*(q_b-1)
gcd, x, y = egcd(e, phi_b)

assert gcd == 1 # should be 1 = they have to be coprime
d_b = x

private_key_b = RSA.construct((bob_n, e, d_b))

print private_key_b.decrypt(data)

f = open('bob_pkey.pem','w')
f.write(private_key_b.exportKey('PEM'))
f.close()

Links