Mind Your Ps and Qs picoGym writeup.

Challenges

In RSA, a small e value can be problematic, but what about N? Can you decrypt this?

File given: values

values:

c= 8533139361076999596208540806559574687666062896040360148742851107661304651861689
n= 769457290801263793712740792519696786147248001937382943813345728685422050738403253
e= 65537

Explaination

RSA is an asymmetric cryptographic algorithm. It is called asymmetric because there are 2 keys. Public key are used to encrypt the clear text. Private key on the other hand are used to decrypt the encrypted text.

there are a few variables that are needed in RSA.

• p is q are random prime number.
• n is the product of p and q (p * q).
• phi is calculated using the formula [(p-1) * (q-1)]. phi is the number of integers that are coprime to n and commonly calculated with Euler’s Totient Function.
• e is the encryption key, that is larger than 2 and smaller than phi and also have a gcd of 1 with both n and phi.
• d is the decryption key, found with the formula [(d*e) % phi = 1] % is modulo operator.

Solution

search for the factor of the given n. http://factordb.com/index.php?query=769457290801263793712740792519696786147248001937382943813345728685422050738403253 after the value of p and q was found, we calculate the value of phi using the formula (p-1) * (q-1). Then we can find the private key by using inverse totient function on e with phi.

finally we can decrypt the text by raising c with the private key and modulo n

here’s my code:

from Crypto.Util.number import inverse, long_to_bytes
c= 8533139361076999596208540806559574687666062896040360148742851107661304651861689
n= 769457290801263793712740792519696786147248001937382943813345728685422050738403253
e= 65537
p= 1617549722683965197900599011412144490161
q=  475693130177488446807040098678772442581573
phi = (p -1) * (q - 1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

thank you for reading