Mathematics of Cryptography
Difficulty | Points |
---|---|
Easy | 150 |
Description
The Defenders heard that there are some Math legends among us and have reached out for assistance in breaking one of the Uprisers' security defenses.
Solution
TL;DR
Utilize values of
n
,p-q
, and(p^3-q^3)
to find the value ofp
orphi
through solving a series of algebraic equations.
Analysis
We can see that we have very little code to work with, and the values provided are for the ones showed in output.txt
.
Recall that we need d
to decrypt the ct
, where pt = pow(ct,d,n)
.
This site provides a recap on how to obtain d
for decrypting RSA, where I quote:
Generate two large random primes, and , of approximately equal size such that their product is of the required bit length, e.g. 1024 bits. [See note 1].
Compute and . [See note 6].
Choose an integer , , such that . [See note 2].
Compute the secret exponent , , such that . [See note 3].
The public key is and the private key . Keep all the values d, p, q and Ī secret. [Sometimes the private key is written as because you need the value of n when using d. Other times we might write the key pair as .]
Our d also has to be derived from e
and phi
, where phi
would be (p-1)(q-1)
(refer to the info box above).
Using multiple expansions and substitutions with the values we are given, we can solve for p
or phi
.
Solving for Phi
We can reference this table if there is a need to recap the algebra rules:
Focusing on values of n
, p-q
, and (p^3-q^3)
:
Now we got phi
using the values that we have, we can just get d
using the Euclidean Algorithm and decrypt the ciphertext!
Last updated