连分数定义
简单连分数形式如下：
定理 I：
如果 是简单连分数 的渐进分数，则有如下递推公式：
定理 II：
若 α 是任一实数，有理数 满足 ，则 必为 的某一渐进分数
维纳攻击 (d < 1/3 N^0.25)
算法实现：
关于各个函数的 implement 可以参考sage中的函数表示：https://doc.sagemath.org/html/en/reference/diophantine_approximation/sage/rings/continued_fraction.html?highlight=continued_fraction
1、使用辗转相除法将分数 x/y 转为连分数的形式
import gmpy2
def transform(x, y): # 使用辗转相除法将分数 x/y 转为连分数的形式
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
transform(45,38)
Out[5]: [1, 5, 2, 3]
等同于在sagemath中执行函数
print(continued_fraction(45/38))
sage: continued_fraction(45/38)
[1; 5, 2, 3]或者用连分数的标准形式表示：
print(continued_fraction(45/38).str())
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return numerator,denominator # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数
def sub_fraction(x,y):
res = transform(x, y)
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res)+1)))) # 将连分数的结果逐一截取以求渐进分数
return res
sub_fraction(45,38) Out[7]: [(1, 1), (6, 5), (13, 11), (45, 38)] sagemath中的表示方法： sage: a = continued_fraction(23/157); a
[0; 6, 1, 4, 1, 3]
sage: a.convergents()
[0, 1/6, 1/7, 5/34, 6/41, 23/157]
# 由 p+q 和 pq 的值通过韦达定理来求解 p 和 q
def get_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c) # 由上述可得，开根号一定是整数，因为有解
x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
return x1, x2
def wienerAttack(e, n):
for (k,d) in sub_fraction(e, n): # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if k == 0: # 可能会出现连分数的第一个为0的情况，排除
continue
if (e * d - 1) % k != 0: # ed=1 (pmod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
continue
phi = (e * d - 1) // k # 这个结果就是 φ(n)
x1, x2 = get_pq(1, n - phi + 1, n) #x^2 + (p+q)x +pq=0
if x1 * x2 == n:
p, q = abs(int(x1)), abs(int(x2)) # 可能会得到两个负数，负负得正未尝不会出现
d = gmpy2.invert(e, (p - 1) * (q - 1)) # 求ed=1 (pmod φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
return d
print("该方法不适用")
这里就是利用了上面维纳攻击的原理，计算每一个渐进分数，直到找到能够分解模 N 的渐进分数。中间过程利用到了韦达定理，如下：
定理关系：
设一元二次方程 ：
，
由一元二次方程求根公式知：
由 ， ，通过韦达定理可以得到一个一元二次方程组 ，由求根公式进而求解出根
完整 EXP :
import gmpy2
def transform(x, y): # 使用辗转相除法将分数 x/y 转为连分数的形式
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return numerator, denominator # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数
def sub_fraction(x, y):
res = transform(x, y)
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res) + 1)))) # 将连分数的结果逐一截取以求渐进分数
return res
# 以上是获得e/n的连分数
# 由 p+q 和 pq 的值通过韦达定理来求解 p 和 q
def get_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c) # 由上述可得，开根号一定是整数，因为有解
x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
return x1, x2
def wienerAttack(e, n):
for (k, d) in sub_fraction(e, n): # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if k == 0: # 可能会出现连分数的第一个为0的情况，排除
continue
if (e * d - 1) % k != 0: # ed=1 (pmod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
continue
phi = (e * d - 1) // k # 这个结果就是 φ(n)
x1, x2 = get_pq(1, n - phi + 1, n) # x^2 + (p+q)x +pq=0
if x1 * x2 == n:
p, q = abs(int(x1)), abs(int(x2)) # 可能会得到两个负数，负负得正未尝不会出现
d = gmpy2.invert(e, (p - 1) * (q - 1)) # 求ed=1 (pmod φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
return d
print("该方法不适用")
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
d = wienerAttack(e, N)
print("d=", d)
下面是github的关于wiener攻击开源脚本，可以自己学习一下
将解密的代码放入wiener-attack的目录下即可。
下载网址: https://github.com/pablocelayes/rsa-wiener-attack
工具只是方便我们计算，更重要的是掌握理论知识，才能理解连分数的本质。
例题实现：BUU rsa2
https://buuoj.cn/challenges#rsa2
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
解题步骤：
import RSAwienerHacker
n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
d = RSAwienerHacker.hack_RSA(e,n)
if d:
print(d)
运行代码得到
d=8920758995414587152829426558580025657357328745839747693739591820283538307445
再把d进行md5哈希即可得到flag
Wiener攻击变种 1
Attack on Prime Power RSA with Two RSA Moduli Paper: https://eprint.iacr.org/2015/399.pdf
from Crypto.Util.number import long_to_bytes
from gmpy2 import *
def transform(x, y): # 使用辗转相除法将分数 x/y 转为连分数的形式
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return numerator, denominator # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数
def sub_fraction(x, y):
res = transform(x, y)
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res) + 1)))) # 将连分数的结果逐一截取以求渐进分数
return res
def wienerAttack(n2, n1):
for (q2, q1) in sub_fraction(n2, n1): # 用一个for循环来注意试探 n2/n1 的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if q2 == 0: # 可能出现连分数第一个值为0的情况，排除
continue
if n2 % q2 == 0 and q2 != 1:
return (q2, q1)
print("该方法不适用")
N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
q2,q1 = wienerAttack(N2, N1) #利用wiener攻击计算出 q1,q2的值
print("q2=", q2)
print("q1=", q1)
# q2= 11628371843051760370952910026406764366191062991235308941262037248377376991693250742343307155422036713746576338866595433599862614339347536916226536644211929
# q1= 11628371843051760370952910026406764366191062991235308941262037248377376991693250742343307155422036713746576338866595433599862614339347536916226536644210947
#常规RSA解密
p1 = iroot(N1//q1,2)[0]
p2 = iroot(N2//q2,2)[0]
phi1 = p1*(p1-1)*(q1-1)
phi2 = p2*(p2-1)*(q2-1)
d1 = invert(E1,phi1)
d2 = invert(E2,phi2)
m1 = pow(c1,d1,N1)
m2 = pow(c2,d2,N2)
print(long_to_bytes(m1)+long_to_bytes(m2))
Wiener攻击变种 2 （d > N^0.25）
Paper：A variant of Wiener’s attack on RSA (https://eprint.iacr.org/2008/459.pdf)（主要看这篇就行了） CONTINUED FRACTIONS AND RSA WITH SMALL SECRET EXPONENT(https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=73494228a8f91619ce9f5bf09bf5043047a5d7d1)
勒让德定理的推广：
Wiener变种攻击的验证：
例题：ASIS Finals CTF 2017
from gmpy import *
from Crypto.Util.number import *
import gensafeprime
from flag import FLAG
def make_pubpri(nbit):
p, q, r = [ getPrime(nbit) for _ in xrange(3)]
n = p * q * r
phi = (p-1)*(q-1)*(r-1)
l = min([p, q, r])
d = getPrime(1 << 8)
e = inverse(d, phi)
a = gensafeprime.generate(2*nbit)
while True:
g = getRandomRange(2, a)
if pow(g, 2, a) != 1 and pow(g, a/2, a) != 1:
break
return (n, e, a, g), (n, d, a, g)
def encrypt(m, pub):
n, e, a, g = pub
k = getRandomRange(2, a)
K = pow(g, k, a)
c1, c2 = pow(k, e, n), (m * K) % a
return c1, c2
nbit = 512
pubkey, privkey = make_pubpri(nbit)
m = bytes_to_long(FLAG)
c = encrypt(m, pubkey)
print 'c =', c
print 'pubkey =', pubkey
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)
pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
EXP：
variant of wiener's attack 计算私钥 d 值
#sage
from sage.all import continued_fraction
def wiener(e,n):
m = 12345
c = pow(m,e,n)
q0 = 1
list = continued_fraction(e/n) #计算连分数
conv = list.convergents() #计算渐近分数
for i in conv:
q1 = i.denominator() #渐近分母
for r in range(20):
for s in range(20):
d = r*q1 + s*q0
m1 = pow(c,d,n)
if m1 == m:
return d
q0 = q1
c = (
1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773,
139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827
)
pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567,
814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451,
171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523,
96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722)
c1,c2 = c
n, e, a, g = pubkey
d = wiener(e,n)
# d=100556095937036905102538523179832446199526507742826168666218687736467897968451
from gmpy2 import *
from libnum import *
k = pow(c1,d,n)
K = pow(g,k,a)
m = (c2*invert(mpz(K),mpz(a)))% a
print(n2s(int(m)))
Boneh-Durfee攻击
参考 https://github.com/mimoo/RSA-and-LLL-attacks
https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
设 D 是一个正整数且不是完全平方数，则佩尔方程 总有正整数解，如果 是使最小的解 ，则每个解都可以通过取幂得到：
暴力求解
例：计算
from gmpy2 import *
def Pell(D):
x = 1
y = 1
while(1):
x = iroot(D*y*y + 1,2)[0]
if(pow(x,2) == D*y*y + 1):
break
y += 1
return x,y
x,y = Pell(10)
print(x,y)
连分数分解（D为非完全平方数）
设 是 的连分数渐进分数表示： 的渐进分数列，由连分数理论知存在 使得 为佩尔方程的解。取其中最小的 ，将对应的 称为佩尔方程的基本解（最小解），记作 ，则所有的解 可表示成如下形式：
一个实数的简单连分数表示：
把简单连分数记为：
所有无限连分数都是无理数，而所有无理数都可以用一种精确的方式表示成无限连分数，可以用这种方法逼近，无理数的值。
可以证明，一个非完全平方数的平方根的连分数是以周期呈现的。如下：
记为：
之后的计算结果就会以 <1,2,4,2,1,8> 为循环序列，周期性呈现。
还有个重要的特点：对于无理数的连分数 ， ，其循环一定是从 开始的，且最后一个数 一定是 2 倍的
将 写成连分数的形式：
设 是 的连分数的渐进分数表示，记 ，用连分数求渐进分数迭代计算即可。
如果记循环长度为 s，那么有如下结论：
1、如果 s 为偶数，最小特解为：，
2、如果 s 为奇数，最小特解为：，
接下来以 为例，解释如何计算 的连分数。
我们记当前展开为 ，那么首先
计算出的连分数为：
然后计算出其渐进分数得到： ，由于循环的长度为 6 是偶数，那么佩尔方程，
同理计算 得到其循环连分数为： ，循环长度 s = 4 ，最小特解为： ，
根据上面的例子设计的连分数的算法：
我们记：，
那么有：
新的 b ,c 为：
实现EXP：
from gmpy2 import *
D = 39352
a0 = isqrt(D) # 开根号向下取整
print(a0)
root_D = D ** 0.5 # 对 D 开根号
a_list = [a0]
b = a0
c = 1
while a_list[-1] != 2 * a_list[0]:
c = (D - b * b) // c
ai = int((root_D + b) / c) # 计算a_i 的值，然后取整
# print('c = {},root_D = {}, b = {} ,ai = {}'.format(c,root_D,b,ai))
a_list.append(ai)
b = c * a_list[-1] - b
print(len(a_list) - 1) # 判断循环长度 s 为奇数还是偶数
print(a_list)
# 以上计算无理数的连分数
# 以下计算连分数的渐进分数
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return numerator, denominator # 得到渐进分数的分母和分子，并返回
def sub_fraction(x):
res = x
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res) + 1)))) # 将连分数的结果逐一截取以求渐进分数
return res
list = sub_fraction(a_list)
# print(list)
for (fenzi, fenmu) in list:
if fenzi ** 2 - 39352 * (fenmu ** 2) == 1:
print('最小特解为：nx = {}ny = {}'.format(fenzi, fenmu))
测试执行 D=22 和 D=33
例题：[第一届数字空间安全攻防大赛] picproblem
assert 1301149798051259562945444365741194129602596348352064372203373*pow(x, 2) == 1175915431138623881271508290982969935822476052419526528443170552123*pow(y, 2) + 1301149798051259562945444365741194129602596348352064372203373
方程化简后得到：
符合Pell方程的形式：套用上面的 exp得到解 x，y
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论