从一题中类比Wiener攻击

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

def pad(msg, nbits):
    pad_length = nbits - len(msg) * 8 - 8
    assert pad_length >= 0
    pad = random.getrandbits(pad_length).to_bytes((pad_length + 7) // 8, "big")
    padded_msg = pad[:len(pad)//2] + b"\x00" + msg + pad[len(pad)//2:]

    return padded_msg

def All_in_my_name(p, q):
    #开启三技能<俱以我之名>后，维娜立即在周围八格可部署地面召唤“黄金盟誓(Golden_Oath)”;对RSA造成真实伤害。
    Golden_Oath = (p-114)*(p-514)*(p+114)*(p+514)*(q-1919)*(q-810)*(q+1919)*(q+810)
    x = bytes_to_long(pad(gift, random.randint(bytes_to_long(gift).bit_length(), 512)))
    y = inverse(x, Golden_Oath)
    return y

flag = b'flag{?????}'
gift = b'?????'
assert gift[:3] == b'end'

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c = pow(bytes_to_long(flag), e,n)

print(f'n = {n}')
print(f'c = {c}')
print(f'All_in_my_name = {All_in_my_name(p, q)}')

'''
n = 141425071303405369267688583480971314815032581405819618511016190023245950842423565456025578726768996255928405749476366742320062773129810617755239412667111588691998380868379955660483185372558973059599254495581547016729479937763213364591413126146102483671385285672028642742654014426993054793378204517214486744679
c = 104575090683421063990494118954150936075812576661759942057772865980855195301985579098801745928083817885393369435101522784385677092942324668770336932487623099755265641877712097977929937088259347596039326198580193524065645826424819334664869152049049342316256537440449958526473368110002271943046726966122355888321
All_in_my_name = 217574365691698773158073738993996550494156171844278669077189161825491226238745356969468902038533922854535578070710976002278064001201980326028443347187697136216041235312192490502479015081704814370278142850634739391445817028960623318683701439854891399013393469200033510113406165952272497324443526299141544564964545937461632903355647411273477731555390580525472533399606416576667193890128726061970653201509841276177937053500663438053151477018183074107182442711656306515049473061426018576304621373895497210927151796054531814746265988174146635716820986208719319296233956243559891444122410388128465897348458862921336261068868678669349968117097659195490792407141240846445006330031546721426459458395606505793093432806236790060342049066284307119546018491926250151057087562126580602631912562103705681810139118673506298916800665912859765635644796622382867334481599049728329203920912683317422430015635091565073203588723830512169316991557606976424732212785533550238950903858852917097354055547392337744369560947616517041907362337902584102983344969307971888314998036201926257375424706901999793914432814775462333942995267009264203787170147555384279151485485660683109778282239772043598128219664150933315760352868905799949049880756509591090387073778041
'''

这是一个自定义的RSA加密，首先n不能分解，整体计算还是按RSA的流程，最后打印了All_in_my_name(p, q)，这是找到p、q值的关键

def All_in_my_name(p, q):
    #开启三技能<俱以我之名>后，维娜立即在周围八格可部署地面召唤“黄金盟誓(Golden_Oath)”;对RSA造成真实伤害。
    Golden_Oath = (p-114)*(p-514)*(p+114)*(p+514)*(q-1919)*(q-810)*(q+1919)*(q+810)
    x = bytes_to_long(pad(gift, random.randint(bytes_to_long(gift).bit_length(), 512)))
    y = inverse(x, Golden_Oath)
    return y

首先Golden_Oath进行了一系列计算；random.randint(bytes_to_long(gift).bit_length(), 512)生成一个随机整数，这个整数的范围是从gift转换后的长整数的位数到512；随后用pad函数对消息用这个位数来填充；最后输出逆元y

def pad(msg, nbits):
    pad_length = nbits - len(msg) * 8 - 8
    assert pad_length >= 0
    pad = random.getrandbits(pad_length).to_bytes((pad_length + 7) // 8, "big")
    padded_msg = pad[:len(pad)//2] + b"\x00" + msg + pad[len(pad)//2:]

    return padded_msg

先计算填充长度pad_length，确保其大于等于0；pad是一个随机填充数据；将其分为前一半后一半加在msg两边

从注释中可以看到提示维纳攻击，那在我看来这里用到的是维纳攻击的思想，主要用于攻击那些使用较小私钥d的 RSA实现，而本代码中x是通过gift进行消息填充获得的，其是一个比n小得多的值，我们可以用类维纳攻击的思想来解决这个问题

d满足：

$$ed \equiv 1 \pmod{phi}$$

x满足：

$$yx \equiv 1 \pmod{Golden\_Oath}$$

在RSA中有

$$phi=(p−1)(q−1)=N−(p+q)+1$$

因为p和q是大质数，可以近似为

$$phi\approx N$$

转换一下

$$ed-1=k*phi$$

同时除以d*phi

$$\frac{e}{phi}-\frac{k}{d} =\frac{1}{d*phi}$$

近似

$$\frac{e}{phi}-\frac{k}{d} =\frac{1}{d*N}$$

d*N是个很大的数,所以我们可以将等式右边看成0

$$\frac{e}{phi}\approx\frac{k}{d}$$ $$\frac{y}{Golden\_Oath}\approx\frac{k}{x}$$

而接下来就用连分数去逼近具体的值

因为

$$Golden\_Oath = (p-114)*(p-514)*(p+114)*(p+514)*(q-1919)*(q-810)*(q+1919)*(q+810)$$

所以

$$Golden\_Oath\approx N^{4}$$

from Crypto.Util.number import long_to_bytes

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 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 b'end' in long_to_bytes(d):
            print(d)
            print(k)
            break
     return (y*d-1)//k

n = 141425071303405369267688583480971314815032581405819618511016190023245950842423565456025578726768996255928405749476366742320062773129810617755239412667111588691998380868379955660483185372558973059599254495581547016729479937763213364591413126146102483671385285672028642742654014426993054793378204517214486744679**4
y = 217574365691698773158073738993996550494156171844278669077189161825491226238745356969468902038533922854535578070710976002278064001201980326028443347187697136216041235312192490502479015081704814370278142850634739391445817028960623318683701439854891399013393469200033510113406165952272497324443526299141544564964545937461632903355647411273477731555390580525472533399606416576667193890128726061970653201509841276177937053500663438053151477018183074107182442711656306515049473061426018576304621373895497210927151796054531814746265988174146635716820986208719319296233956243559891444122410388128465897348458862921336261068868678669349968117097659195490792407141240846445006330031546721426459458395606505793093432806236790060342049066284307119546018491926250151057087562126580602631912562103705681810139118673506298916800665912859765635644796622382867334481599049728329203920912683317422430015635091565073203588723830512169316991557606976424732212785533550238950903858852917097354055547392337744369560947616517041907362337902584102983344969307971888314998036201926257375424706901999793914432814775462333942995267009264203787170147555384279151485485660683109778282239772043598128219664150933315760352868905799949049880756509591090387073778041

Golden_Oath = wienerAttack(y, n)
print(Golden_Oath)

最后解方程

import sympy as sp
import libnum

p, q = sp.symbols('p q')
Golden_Oath = (p - 114) * (p - 514) * (p + 114) * (p + 514) * (q - 1919) * (q - 810) * (q + 1919) * (q + 810)
N = p * q
n = 141425071303405369267688583480971314815032581405819618511016190023245950842423565456025578726768996255928405749476366742320062773129810617755239412667111588691998380868379955660483185372558973059599254495581547016729479937763213364591413126146102483671385285672028642742654014426993054793378204517214486744679

def calculate_p_q():
    golden_oath = 400042032831098007958224589201074030167511216235146696966889080122265111949126155016295896501799032251334875101500882585261911204171467951139573150807043239564581043145433814155757093989016940205116328236031283789686099217459678429270939065783626769903068201144816933538226628329294355184200590029028565011348654002192085571172863125467318356642528249715812871925525776008917314884490518613080652875623759460663908309369135829140204137773254011408135516737187092812588388209697036416805176286184831779945910125467423823737934475944632379524991238593952097013985394648562259886597816452815669024660257170465154297959999722533255899489096196292778430386116108069053440749172609798098777046509743030019115282253351905670418760503352277616008654327326851761671410084489662135479597061419403235762755010286075975241013273964842915146756571330207605591193457296347769260777032489271278979332616929093357929916558230665466587125254822846466292980360420737307459205352964255972268278992730637939153686420457279334894980200862788513296786385507282999530973028293157179873999483225505784146175328159014143540959190522315340971608002638786511995717564457749873410017343184395040614025573440462522210939180555090227730875845671821586191943346000
    equation = [sp.Eq(Golden_Oath, golden_oath), sp.Eq(N, n)]
    solutions = sp.solve(equation, (p, q))
    
    return (solutions[1])

solution = calculate_p_q()
p = solution[0]
q = solution[1]
e = 65537
c = 104575090683421063990494118954150936075812576661759942057772865980855195301985579098801745928083817885393369435101522784385677092942324668770336932487623099755265641877712097977929937088259347596039326198580193524065645826424819334664869152049049342316256537440449958526473368110002271943046726966122355888321

d = libnum.invmod(e, (p-1)*(q-1))
m = pow(c, int(d), n)

print(libnum.n2s(int(m)).decode())