RSA Bwang

Deskripsi

tadi abis pesen udon, milih menu nya udon't need to lower your standard just because u're feeling lonely🥹😔🫵

Author: AnYujin

Pada soal ini kita diberikan source code chall.py dan outputnya pada file out.

import hashlib
import os
from secret import flag
import binascii
from Crypto.Util.number import *
from sympy import *

def gen():
	p=getStrongPrime(1024)
	q=getStrongPrime(1024)
	r=getStrongPrime(1024)
	return p,q,r

m1,m2=flag[:len(flag)//2],flag[len(flag)//2:]
m1=bytes_to_long(m1)
m2=bytes_to_long(m2)

p1,q1,p2=gen()
q2=q1
n1=p1*q1
n2=p2*q2
e1=0x10001
e2=0x10001

ct1=pow(m1,e1,n1)
ct2=pow(m2*(n2-1),e2,n2)

p1tambahq1=p1+q1

print(f"n1  = {n1}")
print(f"e1  = {e1}")
print(f"ct1 = {ct1}")
print(f"p1tambahq1 = {p1+q1}")

print(f"n2  = {n2}")
print(f"e2  = {e2}")
print(f"ct2 = {ct2}")

n1  = 22032750023298635970274749345124218449501435698452019341449020684059164197597967788791070470987981132916038880328230016535916806547621903166534906523930533934586853052627575754642749160485368071816511879009140296804727706282085947421186732607170849008113185829424694143648121856907721447156081006484185079002594035662105879578922818858152470000416172099684052794598257341486328939875883466569402381776772731677946136202310081157276934272706585534839222529477175610327475591508053151612071336160957591882730168241086608862369595430296175124446825051955987474126046005134704267834627472066093757642608692272679407560981
e1  = 65537
ct1 = 574417884850872068999697832228446057079507780060239237442260609431478628521816610020382325642790946604985818454727235030179156857482006569414455675932189873737272312197669917779433194037298502608856557131850698435199409300585484275211818587585660153154880076214321043088911372687186021968024225879416830884849080534341108022795506830633728659335505447111863825017009305096106168119497602478036049090219537551636693601477407228738107498551556819263793380319363267424377629173233276824204963827471848892886180812551858206200802346721464638944123095262024921627470826494239102710896579335497888864184602765071238291691
p1tambahq1 = 296871565799035185614098377177458082282843773061721125195429835460179059355256539731698388977285026751885729868745380723540697145005637497244941673662525712203255516359693021776465086393585894989441691634025900776250539684242912867095056688302619025628884192501233219310664117202327749298337582319303338466550
n2  = 19550564980846702211290976900366327009767905981141714510334785192884765402966585647924584936813337716658525293734915371527312240914390360041389314494232189776450121872682419343653090698572006421682153550402127145853800155913234191658721839006186778582296322593500628505477880847145726979336387048421379858851151461957981008016337241819389178955941723043837163668692331923507945849396810109196971194209583092998476955723571968633730754600858819072631672409824188617431004363678238066840953565258559067089026729530949062652708036342663246106811273629901356370676265764052719457230323611411670989646783853823503358446859
e2  = 65537
ct2 = 14651463834669025703740250903173886225207415197954839814165934585174049366066565640128431849388955153139148010459565795900040417158473257285884585632092333231491887033563259863767615878718096587899548684961577788451746606091957228750318549470845295146967550091065104142332234252996710399230939526821471050461233154639762261530024593792947052312302869419612430510606366670190635961305771461255837786639076139693551492776500782939667229389275142419544318214036506680625166446179395045558184656189786607318946386758700939688424038700856054463338410194798292959164453644757581574647849059739735377048579482061682851645438

Pada kode terdapat enkripsi menggunakan RSA, dimana flag dibagi menjadi 2 bagian (m1 dan m2). Bagian m1 di-enkripsi menggunakan modulus n1, dan bagian m2 menggunakan modulus n2. Di sini, terdapat vulnerability yakni kedua modulus memiliki nilai q yang sama (q1 == q2). Karena nilai n1 dan n2 diberikan, kita bisa mencari gcd(n1,n2) untuk mendapatkan q. Sisanya kurang lebih sama seperti dekripsi RSA pada umumnya. Berikut adalah solver lengkapnya.

from Crypto.Util.number import *

n1  = 22032750023298635970274749345124218449501435698452019341449020684059164197597967788791070470987981132916038880328230016535916806547621903166534906523930533934586853052627575754642749160485368071816511879009140296804727706282085947421186732607170849008113185829424694143648121856907721447156081006484185079002594035662105879578922818858152470000416172099684052794598257341486328939875883466569402381776772731677946136202310081157276934272706585534839222529477175610327475591508053151612071336160957591882730168241086608862369595430296175124446825051955987474126046005134704267834627472066093757642608692272679407560981
ct1 = 574417884850872068999697832228446057079507780060239237442260609431478628521816610020382325642790946604985818454727235030179156857482006569414455675932189873737272312197669917779433194037298502608856557131850698435199409300585484275211818587585660153154880076214321043088911372687186021968024225879416830884849080534341108022795506830633728659335505447111863825017009305096106168119497602478036049090219537551636693601477407228738107498551556819263793380319363267424377629173233276824204963827471848892886180812551858206200802346721464638944123095262024921627470826494239102710896579335497888864184602765071238291691
p1tambahq1 = 296871565799035185614098377177458082282843773061721125195429835460179059355256539731698388977285026751885729868745380723540697145005637497244941673662525712203255516359693021776465086393585894989441691634025900776250539684242912867095056688302619025628884192501233219310664117202327749298337582319303338466550
n2  = 19550564980846702211290976900366327009767905981141714510334785192884765402966585647924584936813337716658525293734915371527312240914390360041389314494232189776450121872682419343653090698572006421682153550402127145853800155913234191658721839006186778582296322593500628505477880847145726979336387048421379858851151461957981008016337241819389178955941723043837163668692331923507945849396810109196971194209583092998476955723571968633730754600858819072631672409824188617431004363678238066840953565258559067089026729530949062652708036342663246106811273629901356370676265764052719457230323611411670989646783853823503358446859
ct2 = 14651463834669025703740250903173886225207415197954839814165934585174049366066565640128431849388955153139148010459565795900040417158473257285884585632092333231491887033563259863767615878718096587899548684961577788451746606091957228750318549470845295146967550091065104142332234252996710399230939526821471050461233154639762261530024593792947052312302869419612430510606366670190635961305771461255837786639076139693551492776500782939667229389275142419544318214036506680625166446179395045558184656189786607318946386758700939688424038700856054463338410194798292959164453644757581574647849059739735377048579482061682851645438

e = 65537

q1 = GCD(n1,n2)
p1 = n1//q1

# bagian 1
phi1 = (p1-1)*(q1-1)
d1 = pow(e,-1,phi1)
m1 = pow(ct1,d1,n1)


# bagian 2
p2 = n2//q1
phi2 = (p2-1)*(q1-1)
d2 = pow(e,-1,phi2)
m2n = pow(ct2,d2,n2)
m2 = (n2-1) - m2n

print(long_to_bytes(m1) + long_to_bytes(m2))

Flag: TechnoFairCTF{J1k4_h1dup_4d4l4h_504l_m4t3m4t1k4_k4mu_4d4l4h_rumu5_y4n9_m3mbu4tny4_t3r454_m3ny3n4n9k4n}