問題

すみません！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')

N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591
e = 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363
there is a bug i guess lol

TL;DR

• 数式を見抜く

解法

eの値とべき乗の計算方法が通常のRSAと異なる。

my_pow内のコメント行は本来掛け算だが足し算になっている。

これは初期値1にnの2進展開の和（つまりnそのもの）×aを加えた結果を返す

式で書くと $\text{my\_pow}(a,n,m)\equiv 1+an \pmod m$

となり、暗号文は

$c\equiv e*flag +1 \pmod N$

と計算されるので逆算する。

（eは小さいのでそのまま求まる）

ソルバ

from Crypto.Util.number import long_to_bytes

N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591
e = 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363
m = (c - 1) // e
print(long_to_bytes(m))