Warm-up

ASCIS 2023 WARMUP

CRYPTOGRAPHY WRITEUP

Author:

• Pham Quoc Trung

Used Language:

• Python3

Problem Solving:

Welcome RSA

Welcome, here is a RSA crypto challenge. Good luck

Attachments: easy_rsa.py

#!/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}")

output.txt

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

Đọc đề bài, ta thấy được cho $N$ = $p$ * $q$ và $phi$ = $(p-1)*(q-1)$. Vì vậy, ta dễ dàng tìm lại được $p$, $q$ bằng cách đặt $q$ = $N / p$

q = N // p

 phi = (p-1)*(q-1)
=> 0 = pq - p - q + 1 - phi
=> 0 = N - p - N//p + 1 - phi
=> -p**2 + (N - phi + 1)*p - N = 0

Giải phương trình bậc 2 trên, ta sẽ thu được p. Ở đây mình sử dụng sagemath:

N = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746909058000987771268371934823850223213735201866888065931847369642802547725217919776237783287489769890109322726430755322073866327698639461994686267421903262258256777595366148454467865658097293146857749360141451451546041703858527691932299750797762597565953059522307802045384870886086792768277420112890024197381341
phi = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746628074068680399113370686212746795530576012850939713222911207509162211597032002438837189193853944160004364194868287701610512383924569996771883743351575199994707067296109349832389723176764968511964606092023026149281647383744920057620837615083525637277639792424720226658009593127619853405831534160987224728925500


R.<a> = PolynomialRing(ZZ)


f = -a**2 + (N - phi + 1)*a - N
a = f.roots()

print(a)

Và mình ra được 2 nghiệm của p:

[(147104365757691981886238610446852083772841819693796888090431035243348558951749166732911919966095528015639093479095140498246787044493026711142267958117969642510892775707277836254280575518402347244263800318277951658352705099052315213650933965287062152329328064087037860117076683589910195814549861226288772917891, 1), (133879566549680173115010000656575599386347196254555820845731098396987569234168170667682173669730202089319438083372479965107156729576438511660256112210092621038817523549520785823861905813922287648879467800147350606041615014555319097811201748949898135983939033500537527258201074877029166631336090676510695537951, 1)]

Vì ở đây message được mã hóa dựa trên p hoặc q, nên mình chỉ cần p và giải mã sử dụng c_p:

from Crypto.Util.number import *
c_p = 70770563170413485640234825332830715579644049285355981293505262738914209029517352373077018947770320280278746620671203215024503799950910898732397153179084074098233352980719945417330407037538618730258842372338429001603903091610752262516741188853590089951756761811040256580538917054394236602707893767220570272331
c_q = 13851492318566804426180559171717895114036816324429566434285593612538644178623395941843619351600718862105589158342528216101368809170495598383990497387251379469346455961514711553702647806756877972791529391358173595919397389755049646932111264878041754835352170573649918876911510785389021472942167961552938040890
N = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746909058000987771268371934823850223213735201866888065931847369642802547725217919776237783287489769890109322726430755322073866327698639461994686267421903262258256777595366148454467865658097293146857749360141451451546041703858527691932299750797762597565953059522307802045384870886086792768277420112890024197381341
phi = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746628074068680399113370686212746795530576012850939713222911207509162211597032002438837189193853944160004364194868287701610512383924569996771883743351575199994707067296109349832389723176764968511964606092023026149281647383744920057620837615083525637277639792424720226658009593127619853405831534160987224728925500

e = 65537
d = inverse(e, phi)

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

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

Flag: ASCIS{W3lc0me_t0_th3_P4rty_8597b0394054835f80ebd573a238ddbe1d86942657a59a7b6f84660d629472b5}

© 2023,Pham Quoc Trung. All rights reserved.