Breaking and Unbreaking in Cybersecurity: RSA Solver for Two Different Public Key Exponents
Breaking and Unbreaking in Cybersecurity: RSA Solver for Two Different Public Key Exponents
As a child, I was forever taking things apart and often did not put them back together again. For me, I had to discover the magic that made the thing work. But, not putting it together again was not good for my parents.
And so, if you are into cybersecurity, you often have to break things, or, at least, think about breaking them (as Eve will be the one that will try and break them). But, when you break them, you should know how to rebuild or fix them. And so yesterday, I posed a CTF RSA Generator for two ciphertext values which have been encrypted with the same public modulus but with two different public exponents:
https://asecuritysite.com/rsa/rsa_e
And I posed the following:
Two RSA ciphers of:
Cipher 1: 43693c02880808d0d2b46cbb6b4dbeb83137b4e60141c6c38cbd33c257c91107
Cipher 2: 59bc6b76ba5da12a30a4d5df5a12907d256f8477610d549af0cbc181aef8ccf0
These have been created by the following RSA public keys:
Key 1: e1=65539, N=51364748517562181021885530774005627727169317925882185055045182454845234587917
Key 2: e2=65537, N=51364748517562181021885530774005627727169317925882185055045182454845234587917
Determine the city.
Unfortunately, no one has yet posted the answer, so let’s give it a try and create a solver.
Theory
In RSA, Bob generates two random prime numbers (p and q), and creates a public modulus:
Bob will then use a public exponent (e_1) to cipher a message (M) with:
and cipher the same message with another public exponent (e_2):
This could have happened because of an error on the system. Now, Eve can take the two ciphers, and then can recover the plaintext if:
and:
With Bezout’s Theorem we can find two integer values (x and y) for two integer values of a and b:
If gcd(e₁, e₂)=1, we can determine the values for x and y for:
Next we can use the Extended Euclidean algorithm to determine x and y. With these values, we can then compute the message with:
and which is:
And, so, the code is just where we use the Extended Euclidean algorithm (xgcd) to discover x and y, and then raise C_1 to the power of x, and C_2 to the power of y, and then multiply them together:
def attack(c1, c2, e1, e2, N):
if libnum.gcd(e1, e2) != 1:
print ("Exponents e1 and e2 cannot be coprime")
sys.exit(0)
x,y,_=libnum.xgcd(e1,e2)
val = (pow(c1,x,N) * pow(c2,y,N)) % N
And that’s it.
Code
Now, let’s solve it. For this our values will either be as an integer or as a hex value, so we just need to determine if the values begin with a ‘0x’ or not. We can read in as a string, and then easily convert to an integer. In Python, we can convert a string to an integer with:
n=int(n)
and if it is in hex, we can use these methods to detect if it is a hex value, and then convert the hex value into an integer (and which is required with the RSA method, as we an exponential function):
def is_hex(s):
if (s.startswith("0x")): return(True)
else: return(False)
def hex_to_long(c):
c=unhexlify(c.replace("0x",""))
return(bytes_to_long(c))
Once, we have converted into an integer, that’s it, and we can just add our attack method:
from Crypto.Util.number import *
from Crypto import Random
import Crypto.Util.number
import re
from binascii import unhexlify
import libnum
import sys
def is_hex(s):
if (s.startswith("0x")): return(True)
else: return(False)
def hex_to_long(c):
c=unhexlify(c.replace("0x",""))
return(bytes_to_long(c))
def attack(c1, c2, e1, e2, N):
if libnum.gcd(e1, e2) != 1:
print ("Exponents e1 and e2 cannot be coprime")
sys.exit(0)
x,y,_=libnum.xgcd(e1,e2)
val = (pow(c1,x,N) * pow(c2,y,N)) % N
return (val)
bits=128
msg="Hello"
e1="65539"
e2="65537"
ct1="87555742451143214550510940735669946042838407030652142562911446641510581736409"
ct2="8187475496363033313022953190006217397649222244707441834312330643068727902323"
ct1="0xc192cb484720a32dc1a765b1b12cba5680a4baa92379b89a9646dc717a4713d9"
ct2="0x1219f268b276a9164d1a6c181cfe3e27f4eaf5ece7745a320873c341db18c073"
n="91462144540927624672750342645999035324723943248127277372366267733038838617033"
if (len(sys.argv)>1):
ct1=str(sys.argv[1])
if (len(sys.argv)>2):
ct2=str(sys.argv[2])
if (len(sys.argv)>3):
e1=str(sys.argv[3])
if (len(sys.argv)>4):
e2=str(sys.argv[4])
if (len(sys.argv)>5):
n=str(sys.argv[5])
c1=0
c2=0
if is_hex(ct1)==True: c1=int(hex_to_long(ct1))
else: c1=int(ct1)
if is_hex(ct2)==True: c2=int(hex_to_long(ct2))
else: c2=int(ct2)
if is_hex(e1)==True: e1=int(hex_to_long(e1))
else: e1=int(e1)
if is_hex(e2)==True: e2=int(hex_to_long(e2))
else: e2=int(e2)
if is_hex(n)==True: n=int(hex_to_long(n))
else: n=int(n)
print("RSA Solver with two public exponents solver. If you use a hex value for the ciphers or N, please put a 0x in front of it.")
message = attack(c1, c2, e1, e2, n)print(f"\nThe input ciphers are:\nCipher 1: {c1}\nCipher 2: {c2}")
print("\nAnd these have been created by the following RSA public keys:")
print(f"Key 1: e1={e1}, N={n}")
print(f"Key 2: e2={e2}, N={n}")
print(f"\n")
print(f"\nPlaintext message recovered: {long_to_bytes(message).decode()}")So now let’s try our challenge:
Two RSA ciphers of:
Cipher 1: 43693c02880808d0d2b46cbb6b4dbeb83137b4e60141c6c38cbd33c257c91107
Cipher 2: 59bc6b76ba5da12a30a4d5df5a12907d256f8477610d549af0cbc181aef8ccf0
These have been created by the following RSA public keys:
Key 1: e1=65539, N=51364748517562181021885530774005627727169317925882185055045182454845234587917
Key 2: e2=65537, N=51364748517562181021885530774005627727169317925882185055045182454845234587917
Determine the city.
If we enter these values, we get:
and we can see the answer is “glasgow”.
Now, using this method, can you find the fruit:
Two RSA ciphers of:
Cipher 1: 9c5d83b8be3450ed1265f16abc7c09642f89ffebab390cc6e25a28de3f8afdc6
Cipher 2: 7c8af9a478e92b50608ef00b08e143601025ef6f179126a0bfee410b56481e49
These have been created by the following RSA public keys:
Key 1: e1=65539, N=81881335856652665568334229359987627088181117117221368903722930687492487109593
Key 2: e2=65537, N=81881335856652665568334229359987627088181117117221368903722930687492487109593
The code is here: