CTF连分数实战详解

admin

139627
文章

114
评论

2023年2月14日00:22:06评论53 views字数 20904阅读69分40秒阅读模式

别忘了

星标我！

连分数方法攻击RSA

为了提高RSA的解密速度，一种有效的方法就是选取较小的解密指数 d 。例如智能卡与大型服务器之间的通信，由于智能卡本身的计算能力有限，所以智能卡通常选取较小的解密指数 d ，而大型服务器则使用较大的加密指数 e 。由 Wiener 首次提出利用连分数可以攻击小解密指数的 RSA ，即当，可以分解 RSA 的模 N。

连分数定义

简单连分数形式如下：

其中是整数，，，，是正整数。如果项数有限，则称为有限简单连分数；否则，称为无限简单连分数。用符号 来表示简单连分数

定理 I：

如果是简单连分数的渐进分数，则有如下递推公式：

定理 II：

若 α 是任一实数，有理数满足，则必为的某一渐进分数

维纳攻击 (d < 1/3 N^0.25)

先假设 RSA 模N 的两个大素因子 p 和 q 的二进制长度相等，即，可以得到 ; N 的欧拉函数

又：，

由于，，所以

如果，那么

根据定理可知，是有理数的一个渐进分数

利用欧几里得算法计算的渐进分数，对于每一个 i ，计算，结合 N = p*q 判断能否分解 N，如果不能，计算下一个渐进分数直至分解 N

算法实现：

关于各个函数的 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())

2、求有限简单连分数的每个渐进分数

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]

以上是获得 e/N 的渐进分数

分解模 N ，计算出 p,q ，以及私钥 d

# 由 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

通过对进行连分数展开求其各项的渐进分数，记为并验证 % 是否成立；如果成立，则：

EXP：

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)

1997年，Verheul 和 van Tilborg 提出了 Wiener 攻击的扩展，当 d 比 n^0.25 长几位时，可以破坏RSA密码系统。对于他们的攻击需要对大约 2t+8 bits 进行彻底搜索（在所涉及的部分收敛的合理假设下），其中

对于维纳攻击的扩展，其中，对d的所有可能性进行测试，可能性的数量大致等于（r的可能性的数量）×（s的可能性的数目）

d 是 e/N 的连分数渐进分母， 和 分别是 (e/N) 的连分数的第 (m+1) 个分母和第 m 个分母

勒让德定理的推广：

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

剩下的常规RSA解密，中间有一步计算 c2 = (m*K) % a ，先计算出 K 值的逆元，再计算出 m

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攻击

当公钥 e 指数值很大时，而私钥指数与模数相比太小，那么有效攻击为：

参考 https://github.com/mimoo/RSA-and-LLL-attacks

https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage

Pell方程(连分数的应用)

设 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为非完全平方数）

设是的连分数渐进分数表示：的渐进分数列，由连分数理论知存在使得为佩尔方程的解。取其中最小的，将对应的称为佩尔方程的基本解（最小解），记作，则所有的解可表示成如下形式：

一、有理连分数：

一个实数的简单连分数表示：

把简单连分数记为：

二、无理数的连分数有理逼近（解Pell方程时的情况）：

所有无限连分数都是无理数，而所有无理数都可以用一种精确的方式表示成无限连分数，可以用这种方法逼近，无理数的值。

可以证明，一个非完全平方数的平方根的连分数是以周期呈现的。如下：

记为：

之后的计算结果就会以 <1,2,4,2,1,8> 为循环序列，周期性呈现。

还有个重要的特点：对于无理数的连分数， ，其循环一定是从 开始的，且最后一个数 一定是 2 倍的

三、求解Pell 方程的最小特解

将写成连分数的形式：

设是的连分数的渐进分数表示，记，用连分数求渐进分数迭代计算即可。

如果记循环长度为 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

点分享

点收藏

点点赞

点在看

免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。

左青龙
微信扫一扫

右白虎
微信扫一扫

CTF连分数实战详解

Wiener攻击变种 1

Wiener攻击变种 2 （d > N^0.25）

Boneh-Durfee攻击

暴力求解

连分数分解（D为非完全平方数）

Zer0 Sec团队内部靶场WP

记一次爱加密企业版脱壳与反调试绕过

2025 能源 CTF

北京市第六届信息通信行业网络安全技能大赛(初赛)-CTF夺旗阶段 EZRSA writeup

2025年能源网络安全大赛团体预赛社会组Write up

【buuctf】[极客大挑战]Knife

第八届封神台CTF writeup by Mini-Venom

流量分析 - encode

【CTFer成长之路】Python中的安全问题

第八届封神台CTF writeup by Mini-Venom

发表评论

在线咨询

微信