Sharky CTF 2020 | Noisy RSA

from Crypto.Util.number import bytes_to_long, getStrongPrime
from fractions import gcd
from secret import flag
from Crypto.Random import get_random_bytes

def encrypt(number):
    return pow(number,e,N)

def noisy_encrypt(a,m):
    return encrypt(pow(a,3,N)+(m << 24))

e = 3
p = getStrongPrime(512)
q = getStrongPrime(512)
while (gcd(e,(p-1)*(q-1)) != 1):
    p = getStrongPrime(512)
    q = getStrongPrime(512)
N = p * q

print("N : " + str(N) + "\n")
print("e : " + str(e) + "\n")
rand = bytes_to_long(get_random_bytes(64))
ct = []
ct.append(encrypt(rand << 24))
for car in flag:
    ct.append(noisy_encrypt(car,rand))
print(ct)

平文を1文字ずつ暗号化しているRSAだが、 67byte 程度のパディングがついている + 平文を暗号化したものをもう一度暗号化しているのでそのままでは解けない。

また、ヒントとして、パディングだけを暗号化したものも与えられている。

↑より、mがわかっていれば Franklin-Reiter Related Message Attackができそう。フラグのフォーマットからはsと推測して、次のようにパディングを求める。

パディングがわかれば、あとは平文と暗号文を対応させるテーブルを作るだけ。

from sage.all import *

N = 166340340660877519226247260987065058211371932250499241074633026863387096385721863889904212902371869444274842128829082337552709506851212430322777753756706525557339442213042322434951929492350910439291882068704178535251621706072605607671593003649095340546077718624006859019891494745600258808326203381366558360403
e = 3
cs = eval(open("output.txt").read().strip().split("\n")[4])

b = pow(ord('s'), e, N)
_, x = PolynomialRing(Zmod(N), name='x').objgen()
f1 = x**e - cs[0]
f2 = (b + x)**e - cs[1]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

pad = -gcd(f1, f2).coefficients()[0]

table = {}
for i in range(256):
    c = pow(pow(i, e, N) + pad, e, N)
    table[c] = chr(i)

flag = ''
for c in cs:
    flag += table[c]
print(flag)