easyrsa (crypto)
We were given this Python script as the challenge.
#!/usr/bin/env python3
from Crypto.Util.number import *
from secret import flag
# Generate public key
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
e = 0x10001
# Encrypt the flag
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"n = {n}")
print(f"c = {c}")
print(f"hint = {p*q-p-q+1}")
# Output:
# n = 18304313499627278872497347106781088765844971752924494936581137294399251598122054491970352624997804891597368572151975199012875361892862378834285683652903007044947055619342684830043887388520198889986897901082447405903406407594879218477486010303949150584062013743002102223027695933305578474279402543515765336412208006859054393534570841203144021034140207743659756456355176186058669431050817944354369543943180071004478988621167578794309738088175437410128123233192513558339607610423092758817077116782370405814263505215749482674852889252017589696530422547393123978624883889069727557585210879305319883301371816205528090434407
# c = 3265951707172242709727472739386873494703249912285505265371146393196030372413781803930164663149372228439333733865082330011642704913091249653497200378094433504467567333190234739925103462552251607608028955840038227014596825040840010571742127988310589087523302675740007385714132298726983039469798322204553974625219330303100743678921966397869657279014124458772194638540183755564805923024931908465309561190023476921354145819156231466029924640305856472832006337877361608232560677427859686638842493170149297308146210190273895689592042634336709605961185187133364422992915741362901814469213680894412670787153775867317785600107
# hint = 18304313499627278872497347106781088765844971752924494936581137294399251598122054491970352624997804891597368572151975199012875361892862378834285683652903007044947055619342684830043887388520198889986897901082447405903406407594879218477486010303949150584062013743002102223027695933305578474279402543515765336411937188290852419206090437467585625464287266017790518369458197274062030222343619328717682343452270958441659650865431008054752337347886117365637267521107136683063583439472152237290665940293045834312267414723015783277860478421527455012050450676028820776344490403116318288525984705526824558715069751252595489120600
In this script, we can see that the flag is encrypted using RSA. The script also gives a useful hint.
RSA
This challenge should be quite straightforward for those who know how RSA works.
RSA encryption relies on 3 parameters, p, q, and e that the user chooses. p and q are very large prime numbers that are used to generated n (the modulus) where n=p*q. Before doing the encryption, the message which normally is a string, is first converted to a number based on the byte values of the string. We call this number m for simplicity.
Then, encryption is very simple, just take c = (m ** e) % n (or in Python, pow(m, e, n)), where c is the ciphertext.
Now, to reverse the process, to get m back from c, 3 parameters are needed again: p, q and d. Again p and q are for generating n. Then, decryption is also very simple, just take m = (c ** e) % n (or in Python, pow(c, d, n)).
But where does d come from? Is it also chosen by the user? That shouldn’t be possible, because looking at the decryption formula, it only makes sense if there is a certain d that can reverse the encryption done by a certain e.
Yes, d is generated from p, q and e, with d = (e ** -1) % phi(n) (in Python, d = pow(e, -1, phi(n))), where phi(n) = (p - 1) * (q - 1). In other words, only the person that knows p and q can find d.
This is why it is very important for p and q to be very large prime numbers, so that it is very hard to factorize n, to find p and q. If someone just knows n and e (usually distributed with a public key), it will take forever to factorize n to find p and q.
Cracking the message
In order to decrypt the encrypted flag, we need to know d. In order to know d, we need to know p and q. Or… what is the hint given?
A hint hint = p*q-p-q+1 is given, and it can be rewritten as hint = (p - 1) * (q - 1).’
You should now know how to decrypt the flag 😉
- Find
d - Find
pow(c, d, n)
#!/usr/bin/env python3
from Crypto.Util.number import *
n = 18304313499627278872497347106781088765844971752924494936581137294399251598122054491970352624997804891597368572151975199012875361892862378834285683652903007044947055619342684830043887388520198889986897901082447405903406407594879218477486010303949150584062013743002102223027695933305578474279402543515765336412208006859054393534570841203144021034140207743659756456355176186058669431050817944354369543943180071004478988621167578794309738088175437410128123233192513558339607610423092758817077116782370405814263505215749482674852889252017589696530422547393123978624883889069727557585210879305319883301371816205528090434407
c = 3265951707172242709727472739386873494703249912285505265371146393196030372413781803930164663149372228439333733865082330011642704913091249653497200378094433504467567333190234739925103462552251607608028955840038227014596825040840010571742127988310589087523302675740007385714132298726983039469798322204553974625219330303100743678921966397869657279014124458772194638540183755564805923024931908465309561190023476921354145819156231466029924640305856472832006337877361608232560677427859686638842493170149297308146210190273895689592042634336709605961185187133364422992915741362901814469213680894412670787153775867317785600107
hint = 18304313499627278872497347106781088765844971752924494936581137294399251598122054491970352624997804891597368572151975199012875361892862378834285683652903007044947055619342684830043887388520198889986897901082447405903406407594879218477486010303949150584062013743002102223027695933305578474279402543515765336411937188290852419206090437467585625464287266017790518369458197274062030222343619328717682343452270958441659650865431008054752337347886117365637267521107136683063583439472152237290665940293045834312267414723015783277860478421527455012050450676028820776344490403116318288525984705526824558715069751252595489120600
e = 0x10001
phi = hint
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# wgmy{227d1562df0d940d94d75b0512f4bc6c}