Cryptography

Challenge	Link
WELCOME RSA (100 pts)	Here

WELCOME RSA (100 pts)

Description

-

Solution

Given source code below

#!/usr/bin/python3

from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long

N = 1024
p = getPrime(N)
q = getPrime(N)

m = 0
with open('flag.txt', 'rb') as f:
    m = bytes_to_long(f.read())
e = 65537

phi = (p-1) * (q-1)
c_p = pow(m, e, p)
c_q = pow(m, e, q)

print(f"c_p = {c_p}")
print(f"c_q = {c_q}")
print(f"N = {p * q}")
print(f"phi = {phi}")

What we have:

• c_p = m^e mod p

• c_q = m^e mod q

• n = p * q

• phi = (p-1)*(q-1)

We can get p and q by utilizing phi and n

$$(p-1)(q-1) = pq - p - q + 1\\ (p-1)(q-1) = n - (p + q) + 1\\ p + q = n - phi + 1$$

After getting p+q we can put it on quadratic equation

$$x^2 - bx + c = 0\\ x^2 - (p+q)x + pq = 0$$

Finally, with asumption that m < p, we can decrypt it by only using p.

from Crypto.Util.number import *

c_p = 70770563170413485640234825332830715579644049285355981293505262738914209029517352373077018947770320280278746620671203215024503799950910898732397153179084074098233352980719945417330407037538618730258842372338429001603903091610752262516741188853590089951756761811040256580538917054394236602707893767220570272331
c_q = 13851492318566804426180559171717895114036816324429566434285593612538644178623395941843619351600718862105589158342528216101368809170495598383990497387251379469346455961514711553702647806756877972791529391358173595919397389755049646932111264878041754835352170573649918876911510785389021472942167961552938040890
N = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746909058000987771268371934823850223213735201866888065931847369642802547725217919776237783287489769890109322726430755322073866327698639461994686267421903262258256777595366148454467865658097293146857749360141451451546041703858527691932299750797762597565953059522307802045384870886086792768277420112890024197381341
phi = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746628074068680399113370686212746795530576012850939713222911207509162211597032002438837189193853944160004364194868287701610512383924569996771883743351575199994707067296109349832389723176764968511964606092023026149281647383744920057620837615083525637277639792424720226658009593127619853405831534160987224728925500
e = 65537

p_plus_q = N + 1 - phi

R, x = QQ['x'].objgen()

f = x^2 - (p_plus_q*x) + N

roots = f.roots()
p, _ = roots[0]
q, _ = roots[1]

assert p*q == N

d = pow(e, -1, p-1)

print(long_to_bytes(pow(c_p, d, p)))

Flag: ASCIS{W3lc0me_t0_th3_P4rty_8597b0394054835f80ebd573a238ddbe1d86942657a59a7b6f84660d629472b5}