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}