wiener(维纳)攻击脚本（e的指数很大）

wiener(维纳)攻击脚本（e指数很大）

1.给出一组n,e,c n=p*q

出题脚本：

import libnum
import random
import gmpy2
#生成随机素数
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
#字符串转数字
m=libnum.s2n(m)
n=p*q
phi_n=(p-1)*(q-1)
#计算d
while True:
    nbits=1024
    d = random.getrandbits(nbits // 4)
    if (libnum.gcd(d, phi_n) == 1 and 36 * pow(d, 4) < n):
        break
#计算e
e = libnum.invmod(d,phi_n)
c=pow(m,e,n)
print ("n=",n)
print ("e=",e)
print ("c=",c) 

解密脚本：

import gmpy2
import libnum

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(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)
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 d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


n= 68781015120012754009149819243839432182753699533745468739333557116438115901358573880902197723852823949505376140916570536753019491036629572363854637530919546688901226752085109196549145599781909847664046508960094447692268230516763088293911965638780888720788954194778424857089535187609738198309161969913567107861
e= 54093680529782962282616750547542407544796590039913570980901028264103594185617926725669901283009540557359666956131385125727959502505561517117179644650419753631214251337533961664493198676862110639584202010794500844074619335752668896589407110076134931918634061631574656816488381501901503924226166074238518619869
c= 30443384983816710270001651296607959522389400057103143909277631290995899073895621701281106228069835965181342091582584186637031613250922961166298411359757600825556083868477673357860585539016515776933117915504873987178857740106223631465737111746470236003857656528610755145017342412306680097140732745012583119076

d=wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(m).decode())

2.给出两组n,e,c n=p^r*q 论文

题目[羊城杯 2020]RRRRRRRSA

import sympy
from Crypto.Util.number import *

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

flag1 = flag[:14]
flag2 = flag[14:]
assert(len(flag) == 27)
P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)
Q1 = getPrime(512)
Q2 = sympy.nextprime(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()

脚本

import gmpy2
import libnum
import sympy
N1=28539239760609998188190348006307254423529984523926011298354682217538318221201323233400895681944936240127760319591714405028970789289069319799896668405374649890651532747231344681669678805558659075027847592497103008180667401328194026698749233856463858487096300279373254961880228864461848969277992345170787143090948199697266462389362914238819698112687026213976658417210663710975098053456243238943838516217798558036642447022751111845270483110159293737669560262193958772015914816987850140197853369767380678566336063010710812528919482513791382363881826680659095433918156094107350594201368395060384315773118343026193511099009931177740948978534045707679969732723167077325752299598557383348276880809860413060977442176372544771414690543709674125255716088409107695219200275948083389811120343
c1=1432582014696304280729383293185554513436929310033823269133977593539672022744978340029313742941392672688363895524640351487464959860278576282854691764963077939567531721178912737755379413034164798305484717033762726637503348022397339246940965129765378824268519081645805470821347112369377592502109678876165836108257610182421452838639591697308432137885174692492190957254254995673010537260331832973067691597718100899475899017281060822990010249568584370589711942182283002241043038119931455622397903939297537776804134742442672001638774739818585840571993745726530468147630711418520486306194651956014117679528472239294239116641656014852458465706006398065574504399016286485027421474307531748266141136418468990741046806688381193860509615850629805172129297224123462801586090084637746562423808
E1=165789626975534012040420057284463500775834911397214992496515507176272849770841998477139944440126985014248815418211585858658342524799286016374109756516450870298232454995876047057825952563581619963387275065218691863272435560584657400761485940130783607258311246708485662913432455714363728035174035069036312370233
N2=28539239760609998188190348006307254423529984523926011298354682217538318221201323233400895681944936240127760319591714405028970789289069319799896668405377378062335966544017315329665365256524558696688888741558627244653037221467229159144343040629127843297021870442297090214085287305843208151069804261723045390513830069085816369993597001968164660390663983571269250460727348123970070188870297493687465127551913118724304293942732950040939150438510454614095673775735977217966562306548665616925803946575019193754095625773160561193234183507671760318885800972555685452762447998320093072265818485061557955267533908006243431570323359331106169234651310488306412479972526063665874847216797986275140105142694301359006633212114432527436809944525332728559649659936613255629968696993687582732203577
c2=15573518512630583133605706431375892476846434992703760807266881477212729790675502562405142453118932977842339803883111403869334521098950030048699583130857582338419182841819307757252097704148569218757559761264396801310961344678392000382263595912787825617009851110457692404940207973548999796553024456145274114257889573707649959860997335143214788897776951837248853483762434899857463503651914305981628033038172123120703537802061315610043298426738218704990852775023413248589434394708618489802771255075164976384643287270994751622452142844176084933641827641239534332334446368745588970480750957569438747829980771324981588625047320914720986351721280038816715323656526802000900688313558979941992015923305782197562859553039256619824373010017972420560224632828808074734952385591551175446599133
E2=165789626975534012040420057284463500775834911397214992496515507176272849770841998477139944440126985014248815418211585858658342524799286016374109756516450870298232454995876047057825952563581619963387275065218691863272435560584657400761485940130783607258311246708485662913432455714363728035174035069036312370859


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 denominator, numerator  # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数
def sub_fraction(x, y):
    res = transform(x, y)
    res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res)))))  # 将连分数的结果逐一截取以求渐进分数
    return res
def wienerAttack(n1, n2):
    for (q2, q1) in sub_fraction(n1, n2):  # 用一个for循环来注意试探n1/n2的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if q1 == 0:  # 可能会出现连分数的第一个为0的情况，排除
            continue
        if n1 % q1 == 0 and q1 != 1:  # 成立条件
            return (q1, q2)
    print("该方法不适用")
q1 = wienerAttack(N1,N2)[0]
q2 = wienerAttack(N1,N2)[1]
p1 = gmpy2.iroot(N1//q1,2)[0]
p2 = sympy.nextprime(p1)
phi1 = (p1**2-p1)*(q1-1)
phi2 = (p2**2-p2)*(q2-1)
d1 = gmpy2.invert(E1,phi1)
d2 = gmpy2.invert(E2,phi2)
m1 = pow(c1,d1,N1)
m2 = pow(c2,d2,N2)
print(libnum.n2s(int(m1))+libnum.n2s(int(m2)))
#GWHT{Crypto_Is_Interesting}