Making Cybersecurity … Fun

Making Cybersecurity … Fun

Cracking RSA with low factors

So, what’s the generic skill that you need to be good at Cybersecurity? Well, it helps to be a problem solver, as every new cyber attack can bring something new, and a new puzzle to solve. So how do you keep your skills high? Well, one way is to undertake CTFs (Capture The Flags), and where we are given puzzles to solve, and then have to find the flags associated with the puzzle. These flags are then associated with points.

But, there’s a strong educational foundation within the CTFs, and where (hopefully) the person taking the challenge will learn a little bit about the methods they are using. So, let’s see if we can learn a little bit about RSA, and solve this puzzle:

Bob sends Alice a cipher using the RSA method. The cipher is 19751341666776829065145843236986750288541130546660759092487484411847198444616087576014984895888571809225722300519581208873003514281409162845915831387840637819795193966050551817621046535516655170078018847403058110927999276083560649057732777457816307053213770302914981171661624894526596565625046726300570757509 and the public modulus is 192247615240664001075810513096751311609683976963787814718441586578958832355166767958201426039181231816419634943060292354393521994868872801869535699304244869614547129415233143542941809084381313545370139423683646039909973002255483647108402153623758317808745424432777539126677681952573356360387033133415891670353. The value of e is 65537. Unfortunately a low factor has been used to generate N. Using this information, can you crack the cipher?

How do we do this? Well, first let’s understand how RSA works.

RSA

We start by generating two prime numbers (p,q) and then calculate the modulus (N):

N=pq

We select e as 65,637, and then compute d

with:

φ=(p−1)×(q−1)

d=e^{−1} (mod φ)

Now we have a message (M), and create a cipher with:

C=M^e (mod N)

and decrypt with:

M=C^d (mod N)

The difficulty of RSA is in the factorizing of N.

Setting up a weak modulus

With this, we can create a random prime number for q between 0 and 10,000 with the sympy library, and then generate a prime with the required number of bits in the modulus. After this, we can then simply compute the modulus with N=p.q [here]:

m=  bytes_to_long(msg.encode())

badprime=sympy.randprime(0, 10000)
p = Crypto.Util.number.getPrime(bits-int(math.log10(badprime)//math.log10(2)), randfunc=Crypto.Random.get_random_bytes)

N=p*q

Cracking RSA

If p is a relatively low prime, we can simply search for it within a list of low prime numbers. In this case, we use the sympy library to generate all the prime numbers from 0 to 10,000, and then test if N (mod p)=0 [here]:

for p in sympy.primerange(0, 10000):
	if (N%p==0): 
		q=N//p
		print(f"Found at {p} and {q}")
		PHI=(p-1)*(q-1)
		print(f"PHI={PHI}")
		d=pow(e,-1,PHI)
		m=pow(C,d,N)
		print(f"\nDecipher: {long_to_bytes(m).decode()}")
		break

CTF generator

Here is the full code of the CTF generator:

The coding is here:

from Crypto.Util.number import long_to_bytes,bytes_to_long
from Crypto import Random
import Crypto
import sys
import libnum
import sympy
import math

bits=256
e=65537
msg="ABC"

if (len(sys.argv)>1):
    msg=str(sys.argv[1])
if (len(sys.argv)>2):
    bits=int(sys.argv[2])

m=  bytes_to_long(msg.encode())
q=sympy.randprime(0, 10000)
p = Crypto.Util.number.getPrime(bits-int(math.log10(badprime)//math.log10(2)), randfunc=Crypto.Random.get_random_bytes)
N=p*q

C=pow(m,e,N)
print(f"Bob sends Alice a cipher using the RSA method. The cipher is {C} and the public modulus is {N}. The value of e is {e}. Unfortunately a low factor has been used to generate N.\nUsing this information, can you crack the cipher, and find the message?")
print("\n\nAnswer:")
for p in sympy.primerange(0, 10000):
 if (N%p==0): 
  q=N//p
  print(f"Found at {p} and {q}")
  PHI=(p-1)*(q-1)
  print(f"PHI={PHI}")
  d=pow(e,-1,PHI)
  m=pow(C,d,N)
  print(f"\nDecipher: {long_to_bytes(m).decode()}")
  break

print(f"\nTo check, the values used are:")
print("p=",p)
print("q=",q)

A sample run with a 1,204 bit modulus is:

Bob sends Alice a cipher using the RSA method. The cipher is 3144751744468932142249426522453173421274590411571451604611043277613958264173651592267076793183232724623455653338739881595850722880029252005099195247134904590264492305941339179343432315724666726905471473158543852868240211120579077724057543856805332083093972380496140664059862074582268446654468398408969187474 and the public modulus is 148493405966164839273399937972159428009354952390629962659201945071424847161153045184986476367470300456301621698966145570348704657350415749892931622393516303508972350328068106759345783809373838657164388250279734467064548338610649604438336611991400395607468652142773982756469666092648438683844125604727179965841. The value of e is 65537. Unfortunately a low factor has been used to generate N.
Using this information, can you crack the cipher, and find the message?

Answer:
Found at 2767 and 53665849644439768439971065403743920494887948099251883866715556585263768399404786839532517660813263627141894361751407867852802550542253613983712187348578353273932905792579727777139784535371824596011705186223250620550975185620039611289604847123744270187014330373246831498543428295138575599509983955448926623
PHI=148439740116520399504959966906755684088860064442530710775335229514839583392753640398146943849809487192674479804604394162480851854799873496278947910206167725155698417422275527031568644024838466832568376545093511216443997363425029564827047007144276651337281637812400735924971122664353300108244615620771731036452
Decipher: Well done!
To check, the values used are:
p= 2767
q= 53665849644439768439971065403743920494887948099251883866715556585263768399404786839532517660813263627141894361751407867852802550542253613983712187348578353273932905792579727777139784535371824596011705186223250620550975185620039611289604847123744270187014330373246831498543428295138575599509983955448926623

Conclusions

Can you find the rock bank:

Bob sends Alice a cipher using the RSA method. The cipher is 116854949858460473657866077888161437444638339834535756242765463536001535574100770443045061917653546211894618190135308973240875920866534921197239540080632116927508029888849379166833091835532212128309951749525754601955187871674133927207707260815872252480713984320964294186406329265953679691833819742659781993223 and the public modulus is 148536571767167009810738701312165815188390401257634593068621986138169915322920790715376988049223345265030980053235825650628549709422878363962279443900813478856258740930185109921494342991111983212186183639063114154225351531008626173243553105103194752395957769201610684417520772604706443863486703311679917524877. The value of e is 65537. Unfortunately, a low factor has been used to generate N.
Using this information, can you crack the cipher, and find the rock band?