Keys are generated in the standard way with the default setup...
task.py
output.txt
import os import gmpy2 flag = int(open('flag.txt').read().encode("hex"), 16) def genPrime(bits): data = os.urandom(bits/8) number = int(data.encode("hex"), 16) return gmpy2.next_prime(number) e = 1667 # rsa1: p - 700 bits q - 1400 bits p = genPrime(700) q = genPrime(1400) n = p*q phi = (p-1)*(q-1) d = gmpy2.powmod(e, -1, phi) rsa1 = (n, d) # rsa2: p - 700 bits, q - 700 bits, r = 700 bits p = genPrime(700) q = genPrime(700) r = genPrime(700) n = p*q*r phi = (p-1)*(q-1)*(r-1) d = gmpy2.powmod(e, -1, phi) rsa2 = (n, d) # rsa3: p - 700 bits, q - 700 bits, r = 700 bits p = genPrime(700) q = genPrime(700) n = p*q*r phi = (p-1)*(q-1)*(r-1) d = gmpy2.powmod(e, -1, phi) rsa3 = (n, d) # rsa4: p - 700 bits, q - 700 bits p = genPrime(700) q = genPrime(700) n = p*q*q phi = (p-1)*(q-1)*q d = gmpy2.powmod(e, -1, phi) rsa4 = (n, d) rsa = sorted([rsa1, rsa2, rsa3, rsa4]) for n, d in rsa: print 'pubkey:', n, d % (2**1050) flag = pow(flag, e, n) print 'encrypted flag', flag
4つのRSAと4つのd'が与えられる。 なのでd'はおよそ1050bit?
rsa1 n=p*q で 700bits と 1400bits
rsa2 n = p*q*r でそれぞれ700bits
rsa3 n = p*q*r でrsa2とrを共有している
rsa4 n = p * q * q でそれぞれ700bits
rsa1
ここで説明されているPartial Key Exposure Attackみたいなものができるらしい（著者 Boneh と DurfeeだけどBoneh Durfee Attackとはおそらく別）。これはeがある程度小さくてdの下位bitが1/4程度わかっているときにd全体を復元できるという攻撃っぽい。また、eが程度の素数の場合にも似たような結果が得られるとか。
今回はLow exponent RSAの場合のみを考える。前提としてのとき、
であるような整数kが存在する。そして、
、つまりdの下位1/4bitであるようなd_0が与えられているとする。
このとき、
である。ここで、であり、これを探索して整数sを求める。sがわかると以下の式を解いてpがわかる。（何でかはpaperを読んでくれ）
わからん
import sys
import gmpy2
N1=859120656206379031921714646885063910105407651892527052187347867316222596884434658659405822448255608155810241715879240998190431705853390924506125009673776539735775578734295308956647438104082568455604755897347443474837969627723792555180605570061543466558710984713039896691188382997755705425087392982168984185229388761020298907843938651747237132404355197739247655148879984476412365078220648181358131779226613410257975180399575865809381114503102493767755197618305439592514756307937482535824886677028869214462143121897901687818277055753103973809215799348093165770108731899625440232334370794010877047571087634088643565878666814823597
N2=1311485515090222718982495198730831073955174624382380405255882886012541076751694096664143914783345786808989030195914045177845164364400711539537456739170589346033729436625658871146633553503774866142568716068953663977222002088477902235884717082069070796901652820969777833174034685816622756524282480580399883160755030115364291412718061758142515305389808681261201028647918631486855998332674824264495109641835596608336454102370944531225289276734441189842117114187272485368222698210402692987316946307402124818683662256285425749745044473836534317911693431019535047343774304237969249813708212575639444584092633692220540287380100087406907
d1lower = 6404011758157972703612261793681759246464215350955339624160911161422611520145549655575457659757671312362520534084082807541566604214336116674150997699501607769566852492157994984170248823333294918447786457066546086171046532955584494739314351490726886444164048184241514125678560723782999029659135170314199032519015517483
d2lower = 6762547460602241256253304403057840010356965995658332151464306076734886668348338229477220486851971695831025738065540621944954803087639187605826246170852109559079074614119808221929013953607066074389809368603757307759386199129306765569186327590211123849053154881101151177686828760168745679159348065176015209027306930795
def modinv(a, mod):
return gmpy2.divm(1, a, mod)
def crt(p,q, dmp, dmq):
prod = p * q
ret = dmp * modinv(q, p) % p * q
ret += dmq * modinv(p, q) % q * p
return ret % prod
# P egy ismert prímosztója N-nek, nem az eredeti támadás része
def d_partial_exposure(_dlower, N, p):
assert N%p == 0
e = 1667
p1 = p-1
dmp1 = modinv(e, p1)
assert e*dmp1%p1 == 1
assert gmpy2.powmod(2, dmp1*e, p) == 2
p1x = p1
while p1x%2 == 0:
p1x //= 2
dmp1x = dmp1%p1x
dlower = crt(p1x, 2**1050, dmp1x, _dlower)
assert dlower % (2**1050) == _dlower
assert dlower % p1 == dmp1
assert dlower < (1<<1750)
assert dlower > (1<<1460)
MOD = p1x<<1050
for k in range(e+1):
dupper = (k*N+1)//e
dupper = dupper//MOD*MOD
for x in range(-2,3):
dcand = dupper + dlower + x*MOD
if dcand < 0:
continue
assert dcand % p1 == dmp1
assert dcand % (1<<1050) == _dlower
if gmpy2.powmod(2, dcand*e,N) == 2:
return dcand
assert(False)
# egyik prim
P = gmpy2.gcd(N1,N2)
assert P != 1
e = 1667
#d1 = d_partial_exposure(d1lower, N1, P)
d1 = 536499461974109521434016165211368644522933032765519292937629951935325568900237840230618752950590334787161644646808812165036736296216784614523620956850870652588447736930054839006520685702669438369696791175248139333899178109132857129498644463812879241313217838272698759059618670904301503031370482593128601064601988543628242477255811668562806753373863919467532704381724235908139965837261439492025443764063209607138449745387083882085791921688501309079739936184841144642836768681165552475426747942922033566756338240250913366448461590599540047734659944902532315561198549877167966775516159467684027796694761374788473470169610840165675
#d2 = d_partial_exposure(d2lower, N2, P)
d2 = 689965684903494495829423088954372436627887309888030963053034967626273859814778477969078712216553242370415944500189932586064912506046445123079993737404083297223503728806660365924173741105465241515916475100463296876910366439207642483647683954896773567500287530655465704536301654714603709153441934810480180612520736719117071180018835175344146545698946933779921074459607196808941644511778420505254623841265774408774443891495012930540080236965626719028359450733805499546172601502884736802703320296093816630611677176285813425155240682413132686810513081547455776384558547313469435113077571280358641899861943541720182054572347130790507
from crypto_commons.rsa.rsa_commons import hensel_lifting
def solve_rsa4(n, e, d_):
def check_k(k):
ka = (k*n + 1 - e*d_) % 2**1050
f = lambda x: (k*x**3 - k*x**2 - ka*x + k*n) % 2**1050
df = lambda x: (3*k*x**2 - 2*k*x - ka) % 2**1050
sols = [p for p in hensel_lifting(f, df, 2, 1050, 1) if n % p == 0]
if sols:print(sols)
for k in tqdm.trange(1, e):
check_k(k)
