authored by jp3bgy, ~naan
すみません！RSA暗号を実装したんですけどバグが取れなくて…ちょっと見てもらえませんか？
def my_pow(a, n, m):
result = 1
while n > 0:
if n % 2 != 0:
result = (result + a) % m # omg!
a = (a + a) % m # oops!
n = n // 2
return result
from Crypto.Util.number import getPrime, bytes_to_long
p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x101
d = my_pow(e, -1, phi)
with open('flag.txt', 'rb') as f:
flag = bytes_to_long(f.read())
c = my_pow(flag, e, N)
print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')
if my_pow(c, d, N) != flag:
print('there is a bug i guess lol')
my_pow関数という独自実装しているRSA問題です。
どうやら、そこに問題があるらしいですね。
解法
もう一度、my_pow関数を見てみましょう。
def my_pow(a, n, m):
result = 1
while n > 0:
if n % 2 != 0:
result = (result + a) % m # omg!
a = (a + a) % m # oops!
n = n // 2
return result
この処理は、掛け算の二進法アルゴリズムとなっています。
つまり、my_pow(a, n, m) は指数計算ではなく
$$
result = 1 + an
$$
を返します。したがって暗号化c = my_pow(flag, e, N)は
$$
c \equiv 1 + flag\cdot e \pmod n
$$
となります。
このことから、flagを求めるためには、
$$
flag \equiv (c-1)/e^{-1} \pmod n
$$
で求めることができます。
from Crypto.Util.number import long_to_bytes
e= 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363
print(long_to_bytes((c-1)//e).decode())
Flag: TSGLIVE{g0od_Mult1plic4t10N-Algor1thm_6y_ru55iAn_Pea5ants}