from secret import e from Crypto.Util.number import getStrongPrime, isPrime p = getStrongPrime(1024) q = getStrongPrime(1024) N = p * q phi = (p - 1) * (q - 1) with open('flag.txt', 'rb') as f: flag = int.from_bytes(f.read(), 'big') assert(isPrime(e)) assert(isPrime(e + 2)) assert(isPrime(e + 4)) e1 = pow(e, 0x10001, phi) e2 = pow(e + 2, 0x10001, phi) e3 = pow(e + 4, 0x10001, phi) c1 = pow(flag, e1, N) c2 = pow(flag, e2, N) c3 = pow(flag, e3, N) print(f'p = {p}') print(f'q = {q}') print(f'c1 = {c1}') print(f'c2 = {c2}') print(f'c3 = {c3}')
isPrime(e), isPrime(e+2), isPrime(e+4)
が全部TRUE
になるのはのときだけらしい。これでがわかったのでCommon Modulus Attackできる
p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281 q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443 c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440 c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743 c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837 e1 = 3 e1 = pow(e1, 65537, (p-1)*(q-1)) e2 = 5 e2 = pow(e2, 65537, (p-1)*(q-1)) e3 = 7 e3 = pow(e3, 65537, (p-1)*(q-1)) import sys sys.setrecursionlimit(1000000) def egcd(a, b): if a == 0: return (b, 0, 1) g, y, x = egcd(b%a,a) return (g, x - (b//a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('No modular inverse') return x%m def common_modulus_attack(c1, c2, e1, e2, n): gcd, s1, s2 = egcd(e1, e2) if s1 < 0: s1 = -s1 c1 = modinv(c1, n) elif s2 < 0: s2 = -s2 c2 = modinv(c2, n) v = pow(c1, s1, n) w = pow(c2, s2, n) m = (v * w) % n return m from math import gcd print(gcd(e1, e3)) print(common_modulus_attack(c1, c3, e1, e3, p*q)) # d = pow(e1, -1, (p-1)*(q-1)) # print(d) # m = pow(c1, d, p*q) # print(bytes.fromhex(hex(m)[2:]))