Get Into Crypto Capture The Flags (CTFs)

Get Into Crypto Capture The Flags (CTFs)

What is one of the best ways to develop an advanced approach to solving cybersecurity problems? Well, CTFs allow you to meet new problems, and work out solutions to them. Some of the best are related to the cracking of cryptography, as they allow you to learn how encryption actually works and how to code for a given solution. This normally involves a bit of maths and then some coding in Python. You thus pick up a bit of problem-solving, a bit of maths, and a bit of Python. But the best bit is where you end up with a solution that works. So, let’s try one that I’ve been working on. For this, we will create a CTF generator and then reveal the solution.

The challenge is:

Bob’s RSA program has used the same prime number (p) for different modulus values (N1=p.q and N2=p.r). He has then lost these modulus values and the prime numbers which generated them. So, given two ciphertext values (Ca and Cb) and decryption exponents for each modulus (da and db), can you decrypt these ciphertexts?

C_A= 53076781476001918980541481586924954661844290230187469413721814208978175578689812434506485756303137373411983183821523499356718941957462796750366565306981279096920001684341033667106062625641623824611746178114499495060920261013868649922549275513310651497559442590121242176702079874889134767706658633548623441729
C_B= 66214375723148081077909765524661271392102294860920443485920503539547812832354123393198516984233648248326743019397558645683665634583739204827901703146686244806557661275393932937138218227469470130038087661496995309045470057282584397229237351202142385166897223024777017599939463027281159798627040880690330905286
D_a= 18326127586995636584285098141218168681757786122264879320014054703055073847003197047572575027006268579511731092544390315992501759086874276687767982196343211310597108418028621050865836192576665269656044089281952091701487274109493032008382660658273083638072894977147235484367072226935946066508985188329092578673
D_b= 16645060129422616936876477634832193880435221164884455055540718476107886197090753775835968325966972752092186312597462928016802219719694415979922187601325902324261158573045714150537454383860368841842967937030005108712909920799458020576957669645205485251251536134526893851542177942373049073928616554981955484973
E=65537

Obviously, this would not happen in real life, as an RSA program should never produce the same prime numbers of different modulus values. In this case, Bob has used RSA encryption to generate two ciphertext outputs (c1 and c2). He has the encryption (e) and decryption exponents (d), but does not have the modulus and prime numbers that were used for the cipher. One thing is that the modulus values were generated with a shared prime number (p. We thus need to take c1, c2, d1, d2, and e, and determine p, q and r.

RSA Outline

With RSA encryption, we have and encryption of:

C=M^e (mod N)

and to decrypt, we have::

M=C^d (modN)

For this we have a modulus of:

N=p.q

and where:

d=e^{−1} (mod φ)

and:

φ=(p−1).(q−1)

Solution

If these modulus values are large, it will be extremely difficult to factorize them. But we can crack to find out p, q and r. In this case we will have two modulus values:

N_a=p.q

N_b=p.r

Now we can derive that:

e.d_a=1 (mod φ)

e.db =1( mod φ)

And then that:

e.da−1=0 (modφ)

e.db−1=0 (modφ)

Thus ed.a−1 and e.db−1 must be multiples of φ. We can find this multiple by taking the Greatest Command Divisor (GCD) of the two:

k=GCD(e.d_a- 1, e.d_b- 1)

Now we can search for the value of p with:

for i in range(2, 100):
    p = k// i + 1
    if isPrime(p):
        print('p =', p)
        break

Now we can divided by \(p-1) to gain another constant:

(e.da−1)/(p−1)=k_a (q−1)

We can then search for q with:

k= (e*d_a-1) // (p - 1)
for i in range(2, 100000):
    q=k//i + 1
    if miller_rabin(int(q)):
        m = pow(int(ct_a), int(d_a), int(p) * int(q))
        msg = long_to_bytes(m)
        try:
            print('q =', q)
            break
        except:
            continue

This will give us the first modulus (N_1) as:

N_1=p.q

We can then easily decrypt with:

M1=C_1^{d_a} (mod p)

M2=C_1^{d_b} (mod p)

Coding

The coding is here:

from Crypto.Util.number import *
from nprime import miller_rabin
msg1="Test"
msg2="Ankle"
bits=1024
if (len(sys.argv)>1):
    msg1=sys.argv[1]
if (len(sys.argv)>2):
    msg2=sys.argv[2]
if (len(sys.argv)>3):
    bits=int(sys.argv[3])
print("Bob's RSA program has used the same prime number (p) for different modulus values (N1=p.q and N2=p.r). He has then lost these modulus values and the prime numbers which generated them. So, given two ciphertext values (Ca and Cb) and decryption exponents for each modulus (da and db), can you decrypt these ciphertexts?\n\n")

e=65537
p,q,r=[getStrongPrime(bits,e) for _ in range(3)]
pt_a=bytes_to_long(msg1.encode())
pt_b=bytes_to_long(msg2.encode())
n_a=p*q
n_b=p*r
phin_a=(p-1)*(q-1)
phin_b=(p-1)*(r-1)
d_a=inverse(e,phin_a)
d_b=inverse(e,phin_b)
ct_a=pow(pt_a,e,n_a)
ct_b=pow(pt_b,e,n_b)
print(f"C_A= {ct_a}\nC_B= {ct_b}\nD_a= {d_a}\nD_b= {d_b}\nE={e}")

k=GCD(e*d_a-1,e*d_b-1)
p=3
for i in range(2, 100):
    p = k// i + 1
    if miller_rabin(int(p)):
        break
k= (e*d_a-1) // (p - 1)
for i in range(2, 100000):
    q=k//i + 1
    if miller_rabin(int(q)):
        m = pow(int(ct_a), int(d_a), int(p) * int(q))
        msg = long_to_bytes(m)
        try:
            break
        except:
            continue
N1=p*q
k = (e*d_b-1) // (p - 1)
for i in range(2, 100000):
    r = k// i + 1
    if miller_rabin(int(r)):
        m = pow(int(ct_b), int(d_b), int(p) * int(r))
        msg = long_to_bytes(m)
        try:
            break
        except:
            continue
N2=p*r
try:
    print("\n\n\n=== Answer and solution check ===")
    print(long_to_bytes(pow(ct_a,d_a,p)).decode())
    print(long_to_bytes(pow(ct_b,d_b,p)).decode())
    print('p =', p)
    print('q =', q)
    print('r =', r)
    print(f"N1= {N1}")
except:
    print("Cannot decrypt. Please try another example")

A sample run is:

Bob's RSA program has used the same prime number (p) for different modulus values (N1=p.q and N2=p.r). He has then lost these modulus values and the prime numbers which generated them. So, given two ciphertext values (Ca and Cb) and decryption exponents for each modulus (da and db), can you decrypt these ciphertexts?

C_A= 94807061832241723856704200144012370801846259999031280463897665781258661200612751202738314351037859850587025251234767037460260985406593709168947674411889677630941062371042257863798077695665798060891756577086283210623926601078006186153810954613465314185840293528940127254281255675496488923257980725886247988846
C_B= 104455341717448281140800068446009950453172110573730993951915854691201436029818057980064523583845951753983039369186223172035156447497119269467678877871787841359478354977819192698780676656618558467349048088759009125856542454219640869434604509117549605437682651616474936533113332744600849714872913703332649586267
D_a= 31860732315882115186468265389728115322206543781889540468673974539258348752485308818157028786600630089240891703744871295508445778037434034803624055473135992339206519580303505845242065637551106794426161951216433108567857578579814271885888162145161768624464170472208780229186949250246618977099611865600045652993
D_b= 149435291119112998435975842248212107373988997294725500983145154049563700057503414959035966576779368741571397110444618511323623813501504906205868107858379028105157430882359977058149932924928972702349228441012404760281100842149610058296857594578857077811364849730913942083007425852846273730882329935936480662913
E=65537

=== Answer and solution check ===
Hello123
Hello234
p = 11554753182804206931460666049162477934517969511846325278130669914695179764905701854779533110055942166268106006030163285903946665879734416000975824934425921
q = 220109344765373733314847020987310095282295706406728209187061573942841832389865530343445249198654474277963065787927729042158846188781870919644299995651954161
r = 2682205048666850130845950806588247337720545969101026803244715090093481947350576125610304895232042786831408575876397091113812018953009092899297239917899808329
N1= 2543309151992650649178527050970294146006638562525815851029824932252587578796138470177292564661931174370986990972384445911981742941826205041321692720515120236558792277213990080256247619319099627913684427382759598241340916980925977310654978779455286154629744122727057955988092630628079676804064354576926342207281

You can try it here:

https://asecuritysite.com/ctf/rsa_ctf09

and other CTFs here:

https://asecuritysite.com/ctf