EvenRSACanBeBroken
🔐 Even RSA Can Be Broken???
| Category | Author |
|---|---|
| 🔐 Cryptography | Michael Crotty |
Challenge Prompt
This service provides you an encrypted flag. Can you decrypt it with just N & e?
Problem Type
- RSA
Solve
We are told we need to nc into the machine, so we start with that.
When we do that we get 3 numbers: N, e, and the cyphertext. As the challenge name suggests, this is RSA encryption.
What is interesting here is that N is normally 2 large random primes multiplied together p and q. This will always result in an odd number.
Unless… one of the primes is 2. If we look at our N we can see it is an even number and with that we can break this.
You could also use FactoDB to figure out p and q:
So we can solve this with some Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Import module depending on version this might be Crypto instead of Cryptodome for you.
from Cryptodome.Util.number import long_to_bytes
# We are given e, N, and our cyphertext in our output from the connection
e = 65537
N = 16830092949573620562109923004380422032555253605649015077259977439249981036204623428721679013333135864661234780499132068466855125435572472785173392998098638
cyphertext = 6753492921406791814444560806732404564578446163893060665321387843570118001023098154052060062257197953137887777264301927898679921962615194346118110890025225
# Now we know either p or q is 2 beacuse our N is even, so let's assign 2 to p
p = 2
# Now we can solve for q
q = N // p
# Now we can calculate Euler's totient
phi = (p - 1) * (q - 1)
# The modular inverse to get the private key d.
# You can also do this by importing inverse with long_to_bytes above and running d = inverse(e, phi)
d = pow(e, -1, phi)
# Decrypt to positive integer
plain = pow(cyphertext, d, N)
# Convert a positive integer to a byte string using big endian encoding
print(long_to_bytes(plain))
We run all those pieces in Python and we get the flag!
The final step can be done in CyberChef as well if you don’t have the Crypto or Cryptodome packages:
