from Crypto.PublicKey import RSA from Crypto.Util.number import bytes_to_long import random import binascii from secret import flag e = 3 BITSIZE = 8192 key = RSA.generate(BITSIZE) n = key.n flag = bytes_to_long(flag) m = floor(BITSIZE/(e*e)) - 400 assert (m < BITSIZE - len(bin(flag)[2:])) r1 = random.randint(1,pow(2,m)) r2 = random.randint(r1,pow(2,m)) msg1 = pow(2,m)*flag + r1 msg2 = pow(2,m)*flag + r2 C1 = Integer(pow(msg1,e,n)) C2 = Integer(pow(msg2,e,n)) print(f'{n = }\n{C1 = }\n{C2 = }')
https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage のぱくり
そういうわけなのでCoppersmith's Short Pad Attackで解ける
def resultant(f1, f2, remove_var): """ PR.<x, y> = PolynomialRing(Zmod(n)) f1 = ... f2 = ... fn, xn = resultant(f1, f2, y) # yを消去する # fnはxnについての1変数多項式であることが期待できる """ modulus = f1.base_ring().cardinality() gens = f1.parent().gens() assert len(gens) == 2 gen_idx = list(gens).index(remove_var) gen_name = f1.parent().variable_names()[1 - gen_idx] namez = [name + "z" for name in f1.parent().variable_names()] namen = gen_name + "n" PRz = PolynomialRing(Zmod(modulus), namez) q1 = f1.change_ring(PRz) q2 = f2.change_ring(PRz) PRn = PolynomialRing(Zmod(modulus), [namen]) xn = PRn.gen() f = q1.resultant(q2, gens[gen_idx]) f = f.univariate_polynomial().change_ring(PRn).subs(**{gen_name: xn}) return f, xn def gcd(a, b): while b != 0: a, b = b, a % b return a.monic() with open("out.txt") as f: n = int(f.readline().strip().split(" = ")[1]) c1 = int(f.readline().strip().split(" = ")[1]) c2 = int(f.readline().strip().split(" = ")[1]) e = 3 PR.<m, d> = PolynomialRing(Zmod(n)) f1 = m**e - c1 f2 = (m + d)**e - c2 fn, dn = resultant(f1, f2, m) roots = fn.small_roots(X=2**510, beta=1, epsilon=0.05) PR.<x> = PolynomialRing(Zmod(n)) f1 = x**e - c1 f2 = (x + roots[0])**e - c2 m = -gcd(f1, f2).constant_coefficient() e = 3 BITSIZE = 8192 x = floor(BITSIZE/(e*e)) - 400 print(bytes.fromhex(hex(int(m) // 2**x)[2:]))