TSG LIVE CTF 8 | RSA Debug ?

def my_pow(a, n, m):
    result = 1
    while n > 0:
        if n % 2 != 0:
            result = (result * a) % m
        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())

assert flag.bit_length() <= 400

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')

TSG LIVE CTF 8 | RSA Debugとちょっと変わっていて、繰り返し二乗法の二乗するところが2倍になってる

よくわかんなかったけどとりあえず二分探索したらよい

N = 161158216253038255124492156151962399187548922270772103599266892572221327481080333694151491753952386387865153735917628775435896449548933903421087242431342475272954753478257425320498033392103209016100073542891497164623755193739116081982087416601688042791555293758187880072012603318037132783685510192234882270727
e = 257
c = 35670804975997119135517974550619182851023199117712172481981302698858610501172231787573382627176449105648892197879980333661081777520179757444468521044149805726225887861984296836753557996580478318594607972377600

def my_pow(a, n, m):
    result = 1
    while n > 0:
        if n % 2 != 0:
            result = (result * a) % m
        a = (a + a) % m # oops!
        n = n // 2
    return result


ok = 1
ng = 2**400

while abs(ok -ng) > 1:
    m = (ok + ng) // 2
    if my_pow(m, e, N) < c:
        ok = m
    else:
        ng = m

print(m)