CTF Generator: RSA Cracking With the Different Public Exponents But The Same Modulus

CTF Generator: RSA Cracking With the Different Public Exponents But The Same Modulus

I love cracking ciphers, and I believe it is great exercise for your brain. And, so, I see so many of our students undertaking CTF (Capture The Flag) challenges. Often there is a range of RSA ciphers in some of the more challenging ones, and one of them is related to the usage of different public exponents, but with the same public modulus. So let’s create a challenge generator for this.

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:

The coding is:

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)

Coding

The coding is [here]:

from Crypto.Util.number import *
from Crypto import Random
import Crypto.Util.number

import libnum
import sys

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
    print("Value is ",val % N)
    return (val) % N

bits=128
msg="Hello"
e1=65535
e2=65537

if (len(sys.argv)>1):
    msg=str(sys.argv[1])
if (len(sys.argv)>2):
    bits=int(sys.argv[2])
if (len(sys.argv)>3):
    e1=int(sys.argv[3])
if (len(sys.argv)>4):
    e2=int(sys.argv[4])
        
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
n=p*q

M = bytes_to_long(msg.encode('utf-8'))

ct1=pow(M,e1,n)
ct2=pow(M,e2,n)

message = attack(ct1, ct2, e1, e2, n)

print(f"Two RSA ciphers of:\nCipher 1: {long_to_bytes(ct1).hex()}\nCipher 2: {long_to_bytes(ct2).hex()}")
print("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"\nDetermine the message")
print(f"\nAns: Plaintext message recovered: {long_to_bytes(message).decode()}")

print(f"\n\nOther information: p={p}, q={q}, bits={bits}, cipher1={ct1}, cipher2={ct2}")

A sample run [here]:

Two RSA ciphers of:
Cipher 1: 6ffc5ffd6cfccc4cd5beb3bf3b8f3365538c93bc5a9194f5abde2891ea083481
Cipher 2: 24ff41f0e31182d5ae6436aaa5f82bb06197fa6e06b32fdb9bf0639d47331601

These have been created by the following RSA public keys:
Key 1: e1=65539, N=109698932908538448355997356028390659249629917171368494357815595471717157949267
Key 2: e2=65537, N=109698932908538448355997356028390659249629917171368494357815595471717157949267

Determine the message.

Ans: Plaintext message recovered: hello

Other information: p=326293445339828821994391884734928444441, q=336197169986939088284435265783579046987, bits=128, cipher1=50652634151313896438142830410451177385475392187895362971481913588538635990145, cipher2=16734263658328913334658730557058701273614779479134869562297560604337092367873

Private key (d1): d1=46749129466965911328872978743541267227508204637090059654247119107875895379659, PHI=109698932908538448355997356028390659248967426556041726447536768321198650457840
Private key (d2): d2=2191066163804825196423402643410033613941717829040978682573593996253

Conclusions

Here is a challenge for you [here]:

Two RSA ciphers of:
Cipher 1: 58f57056a9215e740b007b3afd2bbcf27ac6b55f83c4b6f40415acc438d7cb0f
Cipher 2: 3cb30040372eee76b1e54ea93bb5b08453ab7ffe10c66230ff24daaabb8b6958
These have been created by the following RSA public keys:
Key 1: e1=65539, N=46793199308666669053979225777544033748774863688455417205721837396493662926783
Key 2: e2=65537, N=46793199308666669053979225777544033748774863688455417205721837396493662926783

Determine the message.