# 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
521:d=1  hl=2 l=   3 prim: INTEGER           :010001
0:d=0  hl=4 l= 522 cons: SEQUENCE
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

## 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()``````