Baby-RSA 2

Challenge: If all I have to do is keep my factors p and q secret, then I can save computation time by sharing the same modulus between all my friends. I’ll give them unique e and d pairs to encrypt and decrypt messages. Sounds secure to me!

For this we are given 2 files. The first one is a .py and the second one what prints.

from Crypto.Util.number import *
from secret import flag

# This is my stuff! Don't look at it
p = getPrime(512)
q = getPrime(512)
N = p * q

e_priv = 0x10001
phi = (p - 1) * (q - 1)

d_priv = inverse(e_priv, phi)

m = bytes_to_long(flag)
c = pow(m, e_priv, N)

# This is your stuff!
e_pub = getPrime(16)

d_pub = inverse(e_pub, phi)

print(f"e = {e_pub}")
print(f"d = {d_pub}")
print(f"N = {N}")
print(f"c = {c}")

e = 58271 d = 16314065939355844497428646964774413938010062495984944007868244761330321449198604198404787327825341236658059256072790190934480082681534717838850610633320375625893501985237981407305284860652632590435055933317638416556532857376955427517397962124909869006289022084571993305966362498048396739334756594170449299859 N = 11908266771291549727040770227788674365298563844463718805993868100807705889593534576540716051355511201319075171121352338919492532856516466781757032847478539199285763483256 2389502866385475392702847788337877472422435555825872297998602400341624700149407637506713864175123267515579305109471947679940924817268027249 c = 1070895821540922853545147589874651120161444554801263669629104142937219656827406742051002228234391509902999896805931793509330204277323867163866850522216802742834694813501 06415150660410528574034324184318354089504379956162660478769613136499331243363223860893663583161020156316072996007464894397755058410931262938

For this challenge we are requiered to know RSA cryptography and how their public and private keys work.

A cypher message with RSA is calculated like this, ciphertext = m^e mod n. Where m is the plain message, e is the public exponent and n is the product of two large numbers p and q.

To return to the plain text we have to decrypt it like this m =c^d mod n, where d is the private key. d is computed like this d×e ≡ 1 (mod φ(N)). Where φ(N) = (p-1)*(q-1).

As we said e×d ≡ 1 (mod φ(N)) and we can rearrange it like this: e×d − 1 = k × φ(N) for some small integer k. So we need to find a number k that matches (e×d − 1) % k == 0.

We can use this python script that will try different numbers.

from Crypto.Util.number import *

e_public = 58271
d_public = 16314065939355844497428646964774413938010062495984944007868244761330321449198604198404787327825341236658059256072790190934480082681534717838850610633320375625893501985237981407305284860652632590435055933317638416556532857376955427517397962124909869006289022084571993305966362498048396739334756594170449299859
N = 119082667712915497270407702277886743652985638444637188059938681008077058895935345765407160513555112013190751711213523389194925328565164667817570328474785391992857634832562389502866385475392702847788337877472422435555825872297998602400341624700149407637506713864175123267515579305109471947679940924817268027249
c = 107089582154092285354514758987465112016144455480126366962910414293721965682740674205100222823439150990299989680593179350933020427732386716386685052221680274283469481350106415150660410528574034324184318354089504379956162660478769613136499331243363223860893663583161020156316072996007464894397755058410931262938
e_private = 0x10001

phiNxK = e_public * d_public -1

for k in range(1, 1000000):
    if(phiNxK % k) == 0:
        Dprivate = pow(e_private, -1, phiNxK//k)
        m = long_to_bytes(pow(c,Dprivate,N))

        try:
            print(f"mensaje: {(m).decode()}")
        except:
            continue

DawgCTF{kn0w1ng_d_1s_kn0w1ng_f4ct0rs}