چالش Symmetric RSA¶

صورت سوال¶

با توجه به عنوان سوال پی میبریم که با رمزنگاری RSA سرو کار داریم. حالا میگه رمزنگاری RSA متقارن؟ یعنی چی مگه RSA نامتقارن نبود؟ منظورش چی میتونه باشه؟

یه فایل پایتون بهمون دادن که محتواش اینه:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes as ltb, bytes_to_long as btl, getPrime

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

n = p*q

e = p

with open("flag.txt", "rb") as f:
    PT = btl(f.read())

CT = pow(PT, e, n)
print(f"{CT = }")

for _ in range(4):
    CT = pow(int(input("Plaintext: ")), e, n)
    print(f"{CT = }")

جالب اینجاست که یکی از فاکتورهای e, n هست. در ابتدا میاد فلگو رمز میکنه و در خروجی نمایش میده و بعدش ۴ بار اجازه داریم هر متنی که دوست داریم رمز کنیم و هر بار برامون رمز رو چاپ میکنه.

روش حل¶

خب در اولین مرحله خیلی خوبه که بیایم یه یادآوری کنیم از قضیه Fermat's little :

حالا شما در نظر بگیرید به جای a پیام رو قرار بدیم و از اونطرف $p = e$ (طبق فرض سوال) همچنان داریم:

خب جالب شد ولی دقت کنید که ماژول ما اینجا $N$ هست و نه $p$. ولی میتونیم به چیزی که میخوایم برسیم با این حساب داریم:

حالا داستان اینه که ما $p$ که همون $p=e$ باشه رو که نداریم! پس باید بریم و $p$ رو بدست بیاریم.

توجه کنید که دیدیم:

حالا همانطور که توی بررسی صورت سوال دیدیم اجازه داریم ۴ بار هر پیامی رو که دوست داشتیم رمز کنیم. دیگه چی از این بهتر؟!

حالا میایمو هر بار یه پیام رو رمز میکنیم و بعدش از پیام رو از رمز کم میکنیم و بعد میایم GCD (بزرگترین مقسوم علیه مشترک) رو میگیریم و با این کار $p$ محاسبه میشه!

حالا میایم GCD میگیریم:

و حالا به راحتی پیام رمز شده اصلی رو با استفاده از ($\ref{eq:1}$) بدست میاریم:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from Crypto.Util.number import *
from pwn import *

r = remote('litctf.org', 31783)

ct = int(r.recvline().decode().split()[-1])
out = []
for x in [2, 3, 5, 7]:
    _ = r.recv()
    r.sendline(str(x).encode())
    out.append(x - int(r.recvline().decode().split()[-1]))

p = GCD(*out)
flag = ct % p
print(long_to_bytes(flag))

FLAG

LITCTF{ju57_u53_e=65537_00a144ca}