#!/usr/bin/python3 from Crypto.Util.number import getPrime, bytes_to_long import flag import secrets assert(len(flag.flag) == 33) p = getPrime(512) q = getPrime(512) N = p * q phi = (p - 1) * (q - 1) e = 3 assert(phi%e!=0) d = pow(e, -1, phi) m1 = bytes_to_long(flag.flag+secrets.token_bytes(12)) m2 = bytes_to_long(flag.flag+secrets.token_bytes(12)) c1 = pow(m1, e, N) c2 = pow(m2, e, N) print(f'N = {N}') print(f'e = {e}') print(f'c1 = {c1}') print(f'c2 = {c2}')
RSA で、平文の後ろに異なる12バイトのパディングがついた暗号文が2つ得られる。普通にCoppersmith's Short Pad Attack で解けるが、https://www.youtube.com/live/RvMF4u1Ifgc?feature=share&t=15496 によるとより天才的な解法でも解けるらしい
N = 131524088884825815804488932464729357040334400654894482058463384631465646564218562087397372641691153724192714309237816737178676891008253858742684770007206270690351261617425456727727358875299906146914830254560972052930255319744195538734348410986466067329708785605858045414804679488686183262367088579297015291141 e = 3 c1 = 53446890814226238195814900775610146361354688642953984822875182297861976571235892581728318314459205473773163777796449566433544434134073179844466939691972553393776130664306258111549148944010961079361802647342130537687069419065674984241592765378827102906801889899262139334877519178755098426417577535191788787887 c2 = 53446890814226238195814900775610146361354688642953984822875182321385725425008957482596867857544541131433772697093663878596038952458110930478268276653144018403231153004739183129121025413011758697599979926904528387653993851636222310955660828650069081991070148602980332627389671548440711748081532341124803683994 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() # # p = random_prime(2**512) # q = random_prime(2**512) # # n = p * q # e = 3 # # m1 = randint(2, n-1) # delta = randint(2, 2**60) # m2 = m1 + delta # # assert m2 < n # # c1 = pow(m1, e, n) # c2 = pow(m2, e, n) 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**(13 * 8), beta=1, epsilon=0.01) roots = [13102448862201039697373809223] PR.<x> = PolynomialRing(Zmod(N)) f1 = x**e - c1 f2 = (x + roots[0])**e - c2 m = -gcd(f1, f2).constant_coefficient() print(m)