维纳攻击

攻击条件

e过大或过小，可从算法中快速推断出d的值。模数N=pq，其中q<p<2q
若d < (1/3)N^1/4，且ed ≡ 1 mod L(N)
L(N) = lcm(p-1,q-1) = (p-1)(q-1)/G = φ(N)/G，其中G = gcd(p-1,q-1)

使用原理

因为ed ≡ 1 mod φ(N)，所以∃K∈Z，s.t. ed = Kφ(N) + 1
即e/φ(N) = k/d + 1/dφ(N)，此时φ(N) ≈ N，且dφ(N)非常大，也就是说k/d和e/N非常接近
而e，N又是公钥，对e/N进行连分数展开，得到的一串分数的分母很可能就是d
如果要求pq，由于已知N = pq，φ(N) = (p-1)(q-1) = pq - (p+q) - 1，联系韦达定理，可以构造一元二次方程
x² - (p+q)x + pq = x² - (N - φ(N) + 1)x + N = 0，解出两根即为 p，q

连分数和渐进分数

连分数是具有套式结构的分数，有理数和无理数都可以用它来表示。其主要优点之一是可以比小数更方便地写出任意精确度的无理数。
最简单的连分数具有如下图的表达形式：

或者写成更简单的形式：【a0，a1，a2，a3，，，，】
如89/26可以写成如下图连分数的形式：

或者写成简单的表达式：89/26=【3，2，2，1，3】，a0=3，a1=2，a2=2，a3=1，a4=3。
可见连分数就是一个套一个，每一个都是连分数。
例如：

以此类推，可以得出【3，【2，2，1，3】】的连分数表达方式。
因此，我们可以把连分数写成：
【a0, a1, a2,,,,,an】=【a0, a1,,,,am-1, 【am, am+1,,,, an】】
其中：1 ≦ m ≦ n
从而引出渐进分数的概念。
我们称【a0, a1,,,,am】是【a0, a1, ,,,, an】的第m级渐进分数，（0 ≦ m ≦ n）。
例如：
【3】是89/26的0级渐进分数，【3】=3，89/26=3.423……，两者的误差为0.423……
【3，2】是89/26的1级渐进分数，【3，2】=3+1/2=3.5，误差为0.0769……
【3，2，2】是89/26的2级渐进分数，【3，2，2】=3.4，误差为0.02307……
可见误差越来越小。
89/26是一个有理数，如果用小数来表示，是一个无限循环小数，写出来会非常的麻烦。可如果用连分数来表示就简单多了，而且通过渐进分数不断减小表达式的误差。

---

from sage.all import *

#辗转相除法化为连分数形式
def transform(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]:
        denominator, numerator = numerator, i * numerator + denominator  # 计算新的分子和分母
    return numerator, denominator  # 返回分数形式的结果

# 计算连分数
def sub_fraction(x, y):
    res = transform(x, y)  # 获取 x 和 y 的连分数表示
    res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res) + 1))))  # 将每一步的连分数转换为分数
    return res  # 返回连分数列表

# 根据韦达定理获取 p 和 q
def get_pq(a, b, c):
    par = isqrt(b * b - 4 * a * c)  
    x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a) 
    return x1, x2 


def attack(e, n):
    for (k,d) in sub_fraction(e, n):
        if k == 0:
            continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k  
        x1, x2 = get_pq(1, n - phi + 1, n)  
        if x1 * x2 == n:
            p, q = abs(int(x1)), abs(int(x2))  # 取 p 和 q 的绝对值
            d = inverse_mod(e, (p - 1) * (q - 1))  
            print(f"p = {p}")  
            print(f"q = {q}")  
            print(f"d = {d}")  
            return         
    print("该方法不适用")

注意，在这一段代码中：

def continued_fraction(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:
        denominator, numerator = numerator, i * numerator + denominator  # 计算新的分子和分母
    return numerator, denominator  # 返回分数形式的结果

和最后的

def attack(e, n):
    for (k,d) in sub_fraction(e, n):
        if k == 0:
            continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k  
        x1, x2 = get_pq(1, n - phi + 1, n)  
        if x1 * x2 == n:
            p, q = abs(int(x1)), abs(int(x2))  # 取 p 和 q 的绝对值
            d = inverse_mod(e, (p - 1) * (q - 1))  
            print(f"p = {p}")  
            print(f"q = {q}")  
            print(f"d = {d}")  
            return
    print("该方法不适用")

很多博客在for (k,d) in sub_fraction(e,n)这里会是(d,k)，或者强调说是d是分子，但是仔细分析代码发现是continued_fraction(sub_res)这个函数的返回值不一样的问题，返回的numerator对应k，denominator对应d即可（需要注意numerator和denominator的初始值为1还是0）

例题

e/N << 1，但是(N1/N2) = (P1/P2)²(Q1/Q2)

import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{************}'

flag1 = flag[:19].encode()  #两截flag
flag2 = flag[19:].encode()
assert(len(flag) == 38)

P1 = getPrime(1038)
P2 = sympy.nextprime(P1)  #p2>p1
assert(P2 - P1 < 1000)

Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)  #q2>q1

N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2

E1 = getPrime(1024)
E2 = sympy.nextprime(E1)

m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)

c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)


output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()

N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393

题目分析

• wiener attack 是依靠连分数进行的攻击方式，适用于非常接近某一值（比如1）时，求一个比例关系(通常是e / N = 1)
• 此题中e比较大，想到维纳攻击，但题中 e / N << 1, 不符合利用条件，但是N1和N2的关系却合适
• 对于这一道题，(N1/N2) = (P1/P2)²(Q1/Q2)，显然(N1/N2) < (Q1/Q2)
• 所以Q1/Q2在区间(N1/N2~1)之间，那么就可以对N1/N2进行连分数展开并求其各项分数，其中某个连分数的分子可能就是Q1

解题代码

import gmpy2
from Crypto.Util.number import *
import sympy
def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradualFra(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:
        denominator, numerator = numerator, i * numerator + denominator  # 计算新的分子和分母
    return numerator, denominator  # 返回分数形式的结果

def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for q1,q2 in gf: 
        if q1 == 0: continue
        if N2 % q2 == 0 and q2 != 1:
            return q2


N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
Q2=wienerAttack(N1,N2)
Q1 = sympy.prevprime(Q2)
P1 = gmpy2.iroot(N1 // Q1,2)[0]
P2 = sympy.nextprime(P1)
phi1 = P1 * (P1 - 1) * (Q1 - 1)
phi2 = P2 * (P2 - 1) * (Q2 - 1)
d1 = gmpy2.invert(E1,phi1)
d2 = gmpy2.invert(E2,phi2)
m1 = pow(c1,d1,N1)
m2 = pow(c2,d2,N2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

# b'GWHT{3aadab41754799'
# b'f978669d53e64a3aca}'

---

t ≡ P(p-58) + q (mod Q)，给出t，Q，P

import gmpy2
from pwn import *
from hashlib import sha256
import string
from Crypto.Util.number import *
from random import *


from Crypto.Util.number import *
import gmpy2
from flag import flag

m=bytes_to_long(flag)

def getPQ(p,q):
    P=getPrime(2048)
    Q=getPrime(2048)
    t=(p*P-58*P+q)%Q
    assert (isPrime(Q))
    return P,Q,t

B=getRandomNBitInteger(11)
p=getPrime(B)
q=getPrime(B)
n=p*q
e=65537
c=pow(m,e,n)
P,Q,t=getPQ(p,q)

print("B=",B)
print("P*P*Q=",P*P*Q)
print("P*Q*Q=",P*Q*Q)
print("t=",t)
print("c=",c)
'''
1023
17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
44
4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
'''

题目分析

• P，Q很容易得出

  PQ = gcd(PPQ,PQQ)
  P = PPQ // PQ
  Q = PQQ // PQ

• 又因为t ≡ P(p-58) + q (mod Q)
• 即t + KQ = P(p-58) + q
• 两边同时除以Q，t/Q ≈ 0，q/Q ≈ 0
• 所以化简为K/(p-58) ≈ P/Q，对后者进行连分数展开即可得到p

解题代码

from gmpy2 import *
from Crypto.Util.number import *

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradualFra(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:
        denominator, numerator = numerator, i * numerator + denominator  # 计算新的分子和分母
    return numerator, denominator  # 返回分数形式的结果

def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for _,p_58 in gf: 
        if isPrime(p_58 + 58) and (p_58 + 58).bit_length() == 1023:
            return p_58 + 58


P = 25947339118736016261419550658264175914664266822085997909314096786508816404704696671837899420298768803641977765786592354116676036035881712512184992851487828263900367476619650087372125353190561974783134059421570649293920248116730478378196277387377082481961542018611824082110164117796622604412648512092528479878502094797494405077897059911764470830302447618882229233093021156725194893124743848364119720591518073753197359351271987724752861168913839307431377592888760273762302003490303315903644695784992125784390012046834505490167165377346036077504298195544062111718133371983287540723388743607671934081891907851056034062109
Q = 26068172028162605137516470004551766376185367701690988148920400408760716114172673253571631718337447931195718779018987169967053546674529251665443499183399035216407895285607965767100708187327533611193709308966698251023076404422362272378862918994525181107002728889256377161661579892599243396304207048944032235378667269998644227976609632271355152717352269223310163307304914315780234040829575689991453848537587516055955657960061856059046256125836544109066275645648666876772298883460637600522819402448386193499472702636751025558486665290530268273787746964353937663176851849214999005525738643454160169651485201028944583316101
p=wienerAttack(P,Q)
q = ((58 - p) * P +44) % Q
c=4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
e=65537
phi = (p-1)*(q-1)
d = invert(e,phi)
m = long_to_bytes(int(pow(c,d,p * q)))
print(m)
# DASCTF{8f3djoj9wedj2_dkc903cwckckdk}

注意，在这里m < p，所以直接用p算可以得到flag
还有一种解法，可以通过构造格来解(还没学会，转载一下原文写法)
P,Q 2048bits，p，q大概是1200多bits

from Crypto.Util.number import *
from gmpy2 import *
B=1023
PPQ=17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
PQQ=17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
t=44
c=4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
PQ = gcd(PPQ,PQQ)
P = PPQ // PQ
Q = PQQ // PQ
print(P)
print(Q)
e=65537
mat = [[1,P],[0,Q]]
m = matrix(ZZ,mat)
p_58,t_q = m.LLL()[0]
p_58 = abs(p_58)
t_q = abs(t_q)
p = p_58 + 58
q = t_q + t
phi = (p-1)*(q-1)
d = invert(e,phi)
m = long_to_bytes(int(pow(c,d,p * q)))
print(m)

---

已知n，e，d,求p，q

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
from random import *

gift = 0x98efa1cac6d4a1031759ddfb2cb2a1361b76a0327802e5b99e2f98a1a410705fe93f36979441c6b5eab2737bacc66565d425c56c434d04cbc2b3d756d264995f8b198d6887ec2dddfa640d88932604115d80a9f1f0d18538a738016292057518e02b8520d1322f2cc8c500438d24e041ef9d3e70244e327e28d03c371b7d119a387bf7dfaf7b1ad89ce68f0bdf5858d961b48a6080c589a7e5ac9505cb3893510670299d2f4570acca050e26f828056a4276387b69f64a1498552754ede89e21a1c4a5e0754b41aa2c17823b6d84666896d865c9627a3be5cb8ede76461b44f7ed2398cb29f52073f23c5b0b5ac1af048d310ddec9b683ae0535670195ea510012eb16fb60186a5c26f6c516addeade9bed3dea308fc9196de5b5e99b8f8354b9116995dffb350b5b71ee8ae21b776e122508bf4acd8c9c69bb67a8003291b9a217301656ff332d6802db63605aee2a881e0ddf08904e5c8ace0cd44bffdeee7b10e1b5d868b25ddb1248802c7341267f9862b9319cbaada6d7b557425273256505470d2d610232c00d53475693db249299594ee62271589ec4ebd92c0f37d05ca24c556948dd30b3e6b124f059e4776ef219766e805bf7b1003734172e8d2cda130966bd6c5643071efef3e39bc11f6bdfef4ba6e9fa450f7605bcf9ca22c5f12fdec2f8b3ead07a34a427e3602792939873a2481a8dd0e454305b5ce374a77

def make_gift(p, q):
    n_bits = len(bin(p * q)) - 2
    phi = (p - 1) * (q - 1)
    r = randint(11, 111)
    while True:
        a = getPrime(n_bits // 4 - r)
        if gcd(a, phi) != 1:
            continue
        b = invert(a, phi)
        e = invert(b, gift)
        if gcd(e, phi) == 1:
            break
    d = invert(e, phi)
    return (e, d)

p = getPrime(2048)
q = getPrime(2048)
n = p * q
e, d = make_gift(p, q)
c = pow(bytes_to_long(flag), e, n)

print("n:", hex(n))
print("e:", hex(e))
print("c:", hex(c))

'''
n: 0xf5da802f4a0d148a957254c9287bf1515c81088416067574fb614342d15757b84014125fa9b0b2e8158a7321a0bcde32c6b98abede5da9e526dd2e67c148f89ac0787fa55dd2a2922bc0595e67cb347ab923ee251b1e7c395706a8956335032914f152fe30556feb48592be713c120186266a085a96dee08d86283362dd2593c0df06d83050ad7d3ce5a0ae482b32800a80f66f5d8bfa306b365faec72f4cfc02846c222602a660bd024c8b05055ee824a7a14d6c3d1227ecff1c5b95016ba4ac82f3d493c51ba5e07f3d220ec633358165c97062ffe35abba6745cb7e9182aade6f867fe1ade89515ef61e1c20f08b81b19afbc09be357b2cb328fbb341408bc2ac3fbd66ab7eb7470123e8bea12c3f46082c1f37dd9eb9716d2fe92c090b63f64b8fe3e456f08ced64068e9232309c1d71f9723a2cdf643aa3eca2c0d5fcb1ffe95f9c25bd090ea94f408411e1e030016a91b024eba077fd709d69feec798a86160b921fdc058a5d6b041997737789cd4afbab4a92a80f53152ef4c6cfed432de2bf5c1cb53e33cbed6776a1f7ea4b543f688f34c7765eb441246fdccd34f0c07dca305649375d59f62087d5b2bb863f1fc6d74fe47ab1e8cbf948473e7bc08d6bb8801518d908548624a6eea403ac7ec8531920bbb319681887e70fe1c67def9a431e3ed342fae3fe4bbed35f3081ffe54b8d41409a9d017963ceb1261745
e: 0x324029b96d92446e3315b04d321db7228b30a3d0f0be3d16b7356b4259bf54e9203756fbb08713b88dbdc4986cc7ca676888f7b286b648028428af30175f4568d6443ba8f3a96a168fbe60a71addaf63b307e619c1047c24c88f2619c54b565a20fb066639c74bd7187f66e641384acca5dd59ae652873ebf715de7e1ccaa13187377e1a3c2f7ef2a3607a03bd216ef34ba3788bdb4a23b2a0ae158282c773e19635494907f65798e2a8927d6df96a4eb24ff3b40689d8ea4a82587d6dc7a268e5094c049e2321689c9d0f3fe6e261642970946d7454911518198b6e3cf7227a8e5467a6efa2ffff369307121216c65670e1319cfa20da72b4b5f5cd4a2115f360d9da94b84469466ca886d30184059dec26caca654e601c62c17b33dc30dcd66e1b89578267df7cbc4fe5270b72a23861d54426e86e3dfd7a6ae5a38168229d3f6352dfcd3d21674f349af741cc6a858a3e67c55329fb8c0fd21fb50fd2c3174b0ec2e365b0a0f444de1759ecb98a56dbd7830401e663782a564b4de2208606bee3aa98e0970d6f7cdf923c12852caaf86ef75ff438b1879da69b30564fcc7cc9aa38691ce1353fec995eaf4b8d97792b4f627bb7b631ec0dfcf8ee9333f592462ca6f16e99ef5ecece276c25ddb57b03f87266be0038bc78d374161bb8f558b8fca419a7716c984499bf17832ea2eb2e68fd4118fdb2e5a6d49d08dba0db69
c: 0x5951976397efab4db75cecd1d669f64e31da28c82f383b920fe83a1b99a913d1cb60db9d5fc58795ae011a5c5949cc0b1f53ce28e1505aad93a5ffc9e71418f32aff300ff7d9d5de83c5f53535ea6f25bbc31b56bb7f785d95edf10672bb458f6dba81acc3fd9c2de79506ea7520068b17018359642f34c365580a8e200d411f5a80f38b673706b365f0e6d2e6fb3732208acc0ab64e6159310f8fe4076f9cff17192cb8cbf37c0278e5772c1ac7c80314fc8ec6eaa39852a8e67c5592a5d87dd406e189c19c8db635f8d50e48051dc6e29d1d52e233a490cb53e1d1a592fd3883ef25f02beaf90eb4323a6e3b37c814969689c11e696422125ccd7f8a2e4fcb5276784f1d2cb5aaa2b5a5944f6330684c1c9b9c8da6ca25b18b4024d6e859014ed488643193fe1f8a4b7fdc94ad59965e00cc6cfcbb123a04c13bacbfdf2a3fc240d08c416cbb0acfaa416c81aa351c43ab62020ab39ffa3d2ccde402cb7afbde6dcb61ad0270c44560dced8eb70ae6eeb4c3c092428e94fcf334afab39e10eb1a48a02444358d32ca2ebee3045b473c3b7f9629bbce56d599969c2e2e43d6c2d10079c0e7358f5e944020f77d5f79f6cf78952434cc038ffdadccc6ef1e88f0b8cf6cfe1a6b3f0f5ac1492b387c1dc29f6624f6b20fa86c0ed5d71296275df3388467680bf5208afbb39277045f0dd6a3230418e8220ee7a213888a712d682
'''

题目分析

• 已知e = invert(b，gift) => b = invert(e，gift)
• 又因为a*b ≡ 1 (mod phi)，a，b都很大，可以想到维纳攻击（把b看成e，a看成d）
• 维纳攻击有一个条件d < (1/3)N^1/4，恰巧代码中有一行a = getPrime(n_bits // 4 - r)
• 维纳攻击后得到a，那就相当于得到了n，e（实际是a），d（实际是b）,还要求p，q
• 有一个算法已知n，e，d,求p，q，解出p，q后就是简单RSA了

解题代码

from gmpy2 import *
from Crypto.Util.number import *
import random

def continuedFra(x, y):
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradualFra(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:
        denominator, numerator = numerator, i * numerator + denominator  # 计算新的分子和分母
    return numerator, denominator  # 返回分数形式的结果

def getGradualFra(cf):
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    n_bits = len(bin(n)) - 2
    for _,a in gf: 
        if  a.bit_length() < (n_bits // 4 - 11) and a.bit_length() > (n_bits // 4 - 111) and isPrime(a):
            return a

n=0xf5da802f4a0d148a957254c9287bf1515c81088416067574fb614342d15757b84014125fa9b0b2e8158a7321a0bcde32c6b98abede5da9e526dd2e67c148f89ac0787fa55dd2a2922bc0595e67cb347ab923ee251b1e7c395706a8956335032914f152fe30556feb48592be713c120186266a085a96dee08d86283362dd2593c0df06d83050ad7d3ce5a0ae482b32800a80f66f5d8bfa306b365faec72f4cfc02846c222602a660bd024c8b05055ee824a7a14d6c3d1227ecff1c5b95016ba4ac82f3d493c51ba5e07f3d220ec633358165c97062ffe35abba6745cb7e9182aade6f867fe1ade89515ef61e1c20f08b81b19afbc09be357b2cb328fbb341408bc2ac3fbd66ab7eb7470123e8bea12c3f46082c1f37dd9eb9716d2fe92c090b63f64b8fe3e456f08ced64068e9232309c1d71f9723a2cdf643aa3eca2c0d5fcb1ffe95f9c25bd090ea94f408411e1e030016a91b024eba077fd709d69feec798a86160b921fdc058a5d6b041997737789cd4afbab4a92a80f53152ef4c6cfed432de2bf5c1cb53e33cbed6776a1f7ea4b543f688f34c7765eb441246fdccd34f0c07dca305649375d59f62087d5b2bb863f1fc6d74fe47ab1e8cbf948473e7bc08d6bb8801518d908548624a6eea403ac7ec8531920bbb319681887e70fe1c67def9a431e3ed342fae3fe4bbed35f3081ffe54b8d41409a9d017963ceb1261745
e=0x324029b96d92446e3315b04d321db7228b30a3d0f0be3d16b7356b4259bf54e9203756fbb08713b88dbdc4986cc7ca676888f7b286b648028428af30175f4568d6443ba8f3a96a168fbe60a71addaf63b307e619c1047c24c88f2619c54b565a20fb066639c74bd7187f66e641384acca5dd59ae652873ebf715de7e1ccaa13187377e1a3c2f7ef2a3607a03bd216ef34ba3788bdb4a23b2a0ae158282c773e19635494907f65798e2a8927d6df96a4eb24ff3b40689d8ea4a82587d6dc7a268e5094c049e2321689c9d0f3fe6e261642970946d7454911518198b6e3cf7227a8e5467a6efa2ffff369307121216c65670e1319cfa20da72b4b5f5cd4a2115f360d9da94b84469466ca886d30184059dec26caca654e601c62c17b33dc30dcd66e1b89578267df7cbc4fe5270b72a23861d54426e86e3dfd7a6ae5a38168229d3f6352dfcd3d21674f349af741cc6a858a3e67c55329fb8c0fd21fb50fd2c3174b0ec2e365b0a0f444de1759ecb98a56dbd7830401e663782a564b4de2208606bee3aa98e0970d6f7cdf923c12852caaf86ef75ff438b1879da69b30564fcc7cc9aa38691ce1353fec995eaf4b8d97792b4f627bb7b631ec0dfcf8ee9333f592462ca6f16e99ef5ecece276c25ddb57b03f87266be0038bc78d374161bb8f558b8fca419a7716c984499bf17832ea2eb2e68fd4118fdb2e5a6d49d08dba0db69
c=0x5951976397efab4db75cecd1d669f64e31da28c82f383b920fe83a1b99a913d1cb60db9d5fc58795ae011a5c5949cc0b1f53ce28e1505aad93a5ffc9e71418f32aff300ff7d9d5de83c5f53535ea6f25bbc31b56bb7f785d95edf10672bb458f6dba81acc3fd9c2de79506ea7520068b17018359642f34c365580a8e200d411f5a80f38b673706b365f0e6d2e6fb3732208acc0ab64e6159310f8fe4076f9cff17192cb8cbf37c0278e5772c1ac7c80314fc8ec6eaa39852a8e67c5592a5d87dd406e189c19c8db635f8d50e48051dc6e29d1d52e233a490cb53e1d1a592fd3883ef25f02beaf90eb4323a6e3b37c814969689c11e696422125ccd7f8a2e4fcb5276784f1d2cb5aaa2b5a5944f6330684c1c9b9c8da6ca25b18b4024d6e859014ed488643193fe1f8a4b7fdc94ad59965e00cc6cfcbb123a04c13bacbfdf2a3fc240d08c416cbb0acfaa416c81aa351c43ab62020ab39ffa3d2ccde402cb7afbde6dcb61ad0270c44560dced8eb70ae6eeb4c3c092428e94fcf334afab39e10eb1a48a02444358d32ca2ebee3045b473c3b7f9629bbce56d599969c2e2e43d6c2d10079c0e7358f5e944020f77d5f79f6cf78952434cc038ffdadccc6ef1e88f0b8cf6cfe1a6b3f0f5ac1492b387c1dc29f6624f6b20fa86c0ed5d71296275df3388467680bf5208afbb39277045f0dd6a3230418e8220ee7a213888a712d682
gift = 0x98efa1cac6d4a1031759ddfb2cb2a1361b76a0327802e5b99e2f98a1a410705fe93f36979441c6b5eab2737bacc66565d425c56c434d04cbc2b3d756d264995f8b198d6887ec2dddfa640d88932604115d80a9f1f0d18538a738016292057518e02b8520d1322f2cc8c500438d24e041ef9d3e70244e327e28d03c371b7d119a387bf7dfaf7b1ad89ce68f0bdf5858d961b48a6080c589a7e5ac9505cb3893510670299d2f4570acca050e26f828056a4276387b69f64a1498552754ede89e21a1c4a5e0754b41aa2c17823b6d84666896d865c9627a3be5cb8ede76461b44f7ed2398cb29f52073f23c5b0b5ac1af048d310ddec9b683ae0535670195ea510012eb16fb60186a5c26f6c516addeade9bed3dea308fc9196de5b5e99b8f8354b9116995dffb350b5b71ee8ae21b776e122508bf4acd8c9c69bb67a8003291b9a217301656ff332d6802db63605aee2a881e0ddf08904e5c8ace0cd44bffdeee7b10e1b5d868b25ddb1248802c7341267f9862b9319cbaada6d7b557425273256505470d2d610232c00d53475693db249299594ee62271589ec4ebd92c0f37d05ca24c556948dd30b3e6b124f059e4776ef219766e805bf7b1003734172e8d2cda130966bd6c5643071efef3e39bc11f6bdfef4ba6e9fa450f7605bcf9ca22c5f12fdec2f8b3ead07a34a427e3602792939873a2481a8dd0e454305b5ce374a77

b = invert(e,gift)

a = wienerAttack(b,n)

def divide_pq(e, d, n):
    k = e*d - 1
    while True:
        g = random.randint(2, n-1)
        t = k
        while True:
            if t % 2 != 0:
                break
            t //= 2
            x = pow(g, t, n)
            if x > 1 and gcd(x-1, n) > 1:
                p = gcd(x-1, n)
                return (p, n//p)

p,q = divide_pq(a,b,n)
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
# flag{W1nn3r_4tt4ck_1s_0k_!}

---

已知n，d，求e

from gmpy2 import invert
from md5 import md5
from secret import p, q

e = ?????
n = p*q
phi = (p-1)*(q-1)
d = invert(e, phi)
ans = gcd(e,phi)

print n, e, d
print "Flag: DASCTF{%s}" %md5(str(p + q)).hexdigest()

"""
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
"""

题目分析

解题代码

from gmpy2 import *
from Crypto.Util.number import *
import random

def continuedFra(x, y):
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradualFra(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:
        denominator, numerator = numerator, i * numerator + denominator  # 计算新的分子和分母
    return numerator, denominator  # 返回分数形式的结果

def getGradualFra(cf):
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(d, n):
    cf = continuedFra(d, n)
    gf = getGradualFra(cf)
    for k,e in gf: 
        if e == 1:
            continue
        if (e * d - 1) % k == 0:
            print(k)
            print(e)
            p_q = n + 1 - (e * d - 1) // k
            print('p + q =', p_q)

n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
a = wienerAttack(d,n)

---

直接给出小数形式

from Crypto.Util.number import *
from random import *
from sage.all import *
 
flag = b'--hidden_message--'
data1 = getPrime(256)
data2 = getPrime(256)
m = bytes_to_long(flag)+data2
prec = 600
ring = RealField(prec)
data3 = ring(data1) / ring(data2)
print(data3)
 
while True:
    p = randint(2**255, data1)
    q = randint(2**255, data2)
    if isPrime(p) and isPrime(q) and p!=q:
        break
 
n = p*q
e = 65537
leak = pow(p-q, data1, data1*data2)
c = pow(m, e, n)
print(c)
print(n)
print(leak)
 
 
 
data3 = 1.42870767357206600351348423521722279489230609801270854618388981989800006431663026299563973511233193052826781891445323183272867949279044062899046090636843802841647378505716932999588
c = 1046004343125860480395943301139616023280829254329678654725863063418699889673392326217271296276757045957276728032702540618505554297509654550216963442542837
n = 2793178738709511429126579729911044441751735205348276931463015018726535495726108249975831474632698367036712812378242422538856745788208640706670735195762517
leak = 1788304673303043190942544050868817075702755835824147546758319150900404422381464556691646064734057970741082481134856415792519944511689269134494804602878628

题目分析

• d直接给出了data3 = data1/data2，小数形式，可以直接取其连分数获得data1和data2

  #sage代码
  data3=1.42870767357206600351348423521722279489230609801270854618388981989800006431663026299563973511233193052826781891445323183272867949279044062899046090636843802841647378505716932999588
  
  c = continued_fraction(data3)
  alist = c.convergents()
  for i in alist:
      a = str(i).split('/')
      if len(a)>1 and gcd(int(a[0]),int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(a[0]).bit_length()==256 and int(a[1]).bit_length()==256:
              print(a)
  #['97093002077798295469816641595207740909547364338742117628537014186754830773717','67958620138887907577348085925738704755742144710390414146201367031822084270769']

• 然后就是求解p，q
• leak = (p-q)^data1 (mod data1*data2)
• (p-q)^data1 ≡ leak (mod data1)
• p - q ≡ leak (mod data1)，所以解方程就可以得到p，q

  import sympy
  from Crypto.Util.number import inverse,long_to_bytes
  data1 = 97093002077798295469816641595207740909547364338742117628537014186754830773717
  data2 = 67958620138887907577348085925738704755742144710390414146201367031822084270769
  n=2793178738709511429126579729911044441751735205348276931463015018726535495726108249975831474632698367036712812378242422538856745788208640706670735195762517
  leak=1788304673303043190942544050868817075702755835824147546758319150900404422381464556691646064734057970741082481134856415792519944511689269134494804602878628
  leak1=leak%data1
  p,q = sympy.symbols("p q")  
  h = sympy.solve([p*q-n,p-q-leak1],[p,q])
  p=h[1][0]
  q=h[1][1]
  print(p,q)
  #89050782851818876669770322556796705712770640993210984822169118425068336611139 31366133449465349655535843217834713141354178841659172525867412449648339136903

  p，q得到后就是正常RSA解密

---

参考文章RSA–维纳攻击–代码和题目分析