CTF连分数实战详解

admin

101398
文章

87
评论

2023年2月14日00:22:06评论29 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为非完全平方数）

PWNHUB Web第一题writeup

Vulnerable Docker VM WriteUp

2024 红明谷 dualrsa

2024第四届红明谷 WriteUp By Mini-Venom

第二届数据安全大赛暨首届数信杯数据安全大赛数据安全积分争夺赛预赛南区- WriteUp By EDISEC

来写点安卓逆向题吧③：dynamicRegReverse

东区-第二届数据安全大赛暨首届数信杯数据安全大赛 WP

第二届数据安全大赛暨首届数信杯北部赛区writeup

2024 数信杯

第二届数据安全大赛暨首届数信杯积分争夺赛实践预赛南区Writeup

发表评论

在线咨询

微信