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)