Info
  • Name: Royal Society of Arts
  • Difficulty: Medium
  • Points: 70
  • Category: Cryptography

 

 

Description

RSA strikes strikes strikes strikes again again again again!

rsa.py output

Approach

rsa.py

from Crypto.Util.number import getStrongPrime, bytes_to_long
f = open("flag.txt").read()
m = bytes_to_long(f.encode())
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 65537
c = pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)
print("(p-2)*(q-1) =", (p-2)*(q-1))
print("(p-1)*(q-2) =", (p-1)*(q-2))

output

n = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230158509195522123739130077725744091649212709410268449632822394998403777113982287135909401792915941770405800840172214125677106752311001755849804716850482011237
e = 65537
c = 40544832072726879770661606103417010618988078158535064967318135325645800905492733782556836821807067038917156891878646364780739241157067824416245546374568847937204678288252116089080688173934638564031950544806463980467254757125934359394683198190255474629179266277601987023393543376811412693043039558487983367289
(p-2)*(q-1) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230125943565148141498300205893475242956903188936949934637477735897301870046234768439825644866543391610507164360506843171701976641285249754264159339017466738250
(p-1)*(q-2) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230123577760657520479879758538312798938234126141096433998438004751495264208294710150161381066757910797946636886901614307738041629014360829994204066455759806614

 

we can find $p$ and $q$ from the following equations using python

$a = (p-1)(q-2)$
$b = (p-2)(q-1)$
$n = p*q$

 

from sympy import symbols, Eq, solve

p, q = symbols('p q')

eq1 = Eq((p-1)*(q-2) - 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230123577760657520479879758538312798938234126141096433998438004751495264208294710150161381066757910797946636886901614307738041629014360829994204066455759806614, 0)
eq2 = Eq((p-2)*(q-1) - 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230125943565148141498300205893475242956903188936949934637477735897301870046234768439825644866543391610507164360506843171701976641285249754264159339017466738250, 0)
eq3 = Eq((p*q) - 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230158509195522123739130077725744091649212709410268449632822394998403777113982287135909401792915941770405800840172214125677106752311001755849804716850482011237, 0)

sol = solve((eq1, eq2, eq3), (p, q))

print("p =", sol[0][1])
print("q =", sol[0][0])

 

output

p = 10066608627787074136474825702134891213485892488338118768309318431767076602486802139831042195689782446036335353380696670398366251621025771896701757102780451
q = 12432413118408092556922180864578909882548688341838757808040464238372914542545091804094841981170595006563808958609560634333378522509950041851974318809712087

 

decryption

 

  1. Compute \(\phi(n) = (p-1)(q-1)\).
  2. Calculate the modular multiplicative inverse of \(e\) modulo \(\phi(n)\), denoted as \(d\), such that \((d \cdot e) \bmod \phi(n) = 1\).
    In python we can use inverse function from Crypto.Util.number
  3. Compute \(m = c^d \bmod n\). In python pow(c, d, n).
    The plaintext message, denoted as \(m\), can then be obtained by converting the resulting integer value to its corresponding character representation.
from Crypto.Util.number import long_to_bytes, inverse

p = 10066608627787074136474825702134891213485892488338118768309318431767076602486802139831042195689782446036335353380696670398366251621025771896701757102780451
q = 12432413118408092556922180864578909882548688341838757808040464238372914542545091804094841981170595006563808958609560634333378522509950041851974318809712087

n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

c = 40544832072726879770661606103417010618988078158535064967318135325645800905492733782556836821807067038917156891878646364780739241157067824416245546374568847937204678288252116089080688173934638564031950544806463980467254757125934359394683198190255474629179266277601987023393543376811412693043039558487983367289
m = pow(c, d, n)

plaintext = long_to_bytes(m)
print(plaintext.decode())

 

Flag: actf{tw0_equ4ti0ns_in_tw0_unkn0wns_d62507431b7e7087}