Search code examples
securityencryptionrsa

RSA Decryption when given a cipher text and public keys

I was given a data file containing the public keys and ciphertext of a RSA encryption with the prompt 'solve'. Content of the data file below where c is the ciphertext and n and e are the public keys

n = 173609852803020288223002834131318932162561139787665416528576192047476327876132454798850421956280081003881280979804498575836086539108440947007254837056034733468761051423693621264427437020985695406514584247539132412319979712982160704279304214371731146947298029541543351200373773765850026350111094739056116479933
e = 65537
c = 146573291701623033860032694367482943358809717167991558187946178139570397334278584459176841119758844010116395980273021641115121021883863835210238397309805496532340787133074631614366561581259252015208405320166679097813764492966369276431634838795604950030328620752914710666590298858915065516578271507329590475092

I loosely understand how RSA decryption works but I'm not entirely sure what to do. I have the formulas:

cd≡m (mod n)

d≡e-1 (mod ((p-1)(q-1)))

n=q*p

Any help or redirection to another question that can help me solve this would be appreciated!

I don't know where to start

Solution

  • Hence RSA being somewhat complicated I used this page as my reference, I'll also try to explain it in simpler terms:

    lets revise your formulas:

    cd ≡ m (mod n):

    It means that m mod n is equal to cd mod n (correct me if I'm wrong), tbh I do not know what m means here but it's irrelevant to my solution so I just ignored it

    d ≡ e-1 (mod ((p-1)(q-1))):

    Here d is the private key

    n = q*p

    Is referring to the fact that n is product of two prime numbers

    code:

    from sympy.ntheory import factorint


n = 173609852803020288223002834131318932162561139787665416528576192047476327876132454798850421956280081003881280979804498575836086539108440947007254837056034733468761051423693621264427437020985695406514584247539132412319979712982160704279304214371731146947298029541543351200373773765850026350111094739056116479933
e = 65537
c = 146573291701623033860032694367482943358809717167991558187946178139570397334278584459176841119758844010116395980273021641115121021883863835210238397309805496532340787133074631614366561581259252015208405320166679097813764492966369276431634838795604950030328620752914710666590298858915065516578271507329590475092

# extracting prime numerators from n (this is impossible to do in real world keys as it will take countless decades)
p, q = factorint(n).keys()

phi = (p - 1) * (q - 1)
# using formula you provided to calculate the private key
private_key = pow(e, -1, phi)
print(f"Private key: {private_key}")


# this should be your answer
plaintext_int = pow(c, private_key, n)
print(f"Plain text as integer value: '{plaintext_int}'")

# lets check the decrypted string
int_size = (plaintext_int.bit_length() + 7) // 8
byte_sequence = plaintext_int.to_bytes(int_size, 'big')
utf8_string_decrypted = byte_sequence.decode('utf-8')
print(f"Answer as utf-8 string is: '{utf8_string_decrypted}'")


# just checking the validity of code
encypted_again = pow(plaintext_int, e, n)
valid_encryption = encypted_again == c
print(f"Answer is technically valid: {valid_encryption}")

    which gives the output:

    Private key: 24416162065481148001150756400023904019749546445868931201365438791851767917883223764911490290538680540958142221811466246143113197597731055870208703986228724163345502706587387608555234208177763873924317005840634824253619123697346566415103874946106145433821273587775949295139024692042545561624642164187090250113
Plain text as integer value: '10786438895798011900914002629573009747847491781007415095503773516157'
Answer as utf-8 string is: 'flag{f$3Rm!at_COOL&*68557$A}'
Answer is technically valid: True

    the string does not seem to be really meaningful but the fact that it's valid utf-8 bytes is enough for me to believe this is the right answer