RSA加密之低加密指数攻击

• 接下来学习一下RSA加密中比较简单的一部分，就是低加密指数攻击（或者也叫做小加密指数攻击），小加密指数攻击还算是比较简单的，比小私钥指数攻击简单不少，接下来就是RSA加密低加密指数攻击的一些相关内容。下面图片就是低加密指数攻击的相关内容，其中消息相关攻击单开一部分。

• 下面三个攻击都是使用小私钥指数潜在的危险。所以这些攻击都假设攻击者对被加密的明文具有一定的先验知识，并且只能恢复明文。这些攻击都无法恢复私钥指数，也无法对模数进行因数分解，因此这类攻击是对RSA加密的部分攻击，而不是完全攻击。
• 使用非常小的公钥指数可以显著降低加密的计算成本，比如$e=3$，在每次加密时只需要进行两次模乘运算，相比之下，使用一个完整大小的公钥指数大约需要$\frac{3}{2}log_2(N)$次模乘。
• 在RSA中使用小指数的思想大概在20世纪80年代就已经为人所知，甚至可能更早。最早公开指数小指数可以显著减低基于模指数运算的算法成本的文献，通常认为是Rabin在1979年发表的一篇论文。
• 在实际应用中，大多数RSA实例都会使用一个固定的小公钥指数，例如：$e=2^{16}+1$也就是65537或者$e=3$。

刻板消息攻击

• 所谓刻板消息攻击，主要攻击思想就是在刻板这边，比如说对某类人的刻板印象。（对程序员的刻板印象其实就是秃头或者男娘）而对某个消息的刻板印象就例如，每次写信等比较正式的文章开头就会先说先场面话尊敬的....，这就相当于一个比较刻板规矩，根据这种情况，由此就有了刻板消息攻击。

• 刻板消息攻击的具体描述如下：

  • 当已知明文消息的一部分，如果公钥指数和明文消息的未知部分足够小，那么就能完整恢复出整消息。

  • 在一种极端的情况下，假设我们已知明文相对于模数来说非常小。也就是说，我们知道明文的最高有效位MSB全部为0。

    • 如果一个明文$m<N^{\frac{1}{e}}$，并且使用公钥指数$e$进行加密，那么显然可以直接恢复该明文。
    • 因为$c=m^{e}~mod(~N)=m{^e}$，此时只要在整数域上对密文$c$开$e$次方根，就能恢复出明文$m$

  • 对于$Z_n$中的随机明文来说，明文恰好如此之小的概率是非常低的。然而在实际应用中，明文通常是用于对称加密方案的一个（相对较小的）密钥。当公钥指数非常小，例如$e=3,e=5$，明文$N^{\frac{1}{e}}$的情况就完全有可能发生。具体的例子如下：

    • 在使用1024位模数且公钥指数为$e=3$的情况下，长度小于约$342$位的对称密钥都可以被恢复出来。
    • 不过只要在明文后面附加随机比特位，使得$m>N^{\frac{1}{e}}$，就可以很容易地抵御这种攻击。

  • 接下来看另一种普遍情况，现在假设明文足够大使得上述攻击无法奏效，但我们已知明文的大部分结构。

    • 例如：假设用于发送每日秘钥的明文消息具有如下形式：The secret for February 29, 2008 is ?????。或者是在写书信的时候Dear ????、尊敬的xxx
    • 上面的两个明文消息，其中真正的秘密部分是未知的，但其数值非常小。在这种情况下，Coppersmith证明了如果明文中未知的那一部分足够小，那么仅凭密文就很有可能将其恢复出来。

  • Coppersmith对于刻板消息攻击的主要结论如下，我们称该结论为定理4.1：

    • 设$(e,N)$是有效的RSA公钥对，设$m$是任意明文
    • 给定公钥以及$c\equiv m^{e}~mod~N$，如果明文中除了至多占其连续比特的$\frac{1}{e}$之外，其余比特都是已知的。
    • 那么就可在关于$log(N)$和$e$的多项式时间内计算出完整的明文$m$

  • 定理4.1的证明如下：

    • 由于明文$m$中连续比特中最多只有$\frac{1}{e}$的比例是未知的，我们可以将明文表示为$m=m_22^{k_2}+m_12^{k_1}+m_0$，其中除了$m_1$之外其余部分都是已知的。此外$m_1$还满足$m_1 < N^{\frac{1}{e}}$
    • 这就使得我们可以寻找模$N$意义下的一个小解，对于下面这个在$Z_N[x]$上的首一e次多项式：

    $$f_N(x)\equiv 2^{-k_1e}((m_22^{k_2}+x2^{k_1}+m_0)-c)~mod(~N)$$

    • 因为$f_N(m_1)=2^{-k_1e}(m^{e}-c)\equiv0~mod(~N)$，其实也就是$m_1$是多项式$f_N(x)$在模$N$下的一个小根
    • 由于$|m_1|<N^{\frac{1}{e}}$，那么就可以使用Coppersmith关于一元模方程小根的结果来计算出$m_1$，从而恢复出完整的明文。
    • 由于所有计算都可以在关于$log(N)$和$e$的多项式时间内完成，因此定理得证。

注意：为了使得在实际中有用，公钥指数必须足够小。原因主要有两点：

1. 一旦$e>log_2(N)$，该攻击就需要已知明文的所有比特，都知道所有明文比特了还干嘛要攻击
2. 随着公钥指数$e$的增大，攻击的计算成本迅速上升，因为Coppersmith方法中所使用的格的维度是$e$的多项式函数。因此在常用的公钥指数$e=2^{16}+1$这种情况下，这种攻击并不适用。
3. 当使用正确的随机填充方案时，只要明文至少有$\frac{1}{e}$的比特是随机的，该攻击也将不再有效。

题型1 极端情况

极端情况 题目1

• 题目来源：SWPUCTF 2021 新生赛crypto5 | NSSCTF
• 题目附件如下：

flag= 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333
n= 134109481482703713214838023035418052567000870587160796935708584694132507394211363652420160931185332280406437290210512090663977634730864032370977407179731940068634536079284528020739988665713200815021342700369922518406968356455736393738946128013973643235228327971170711979683931964854563904980669850660628561419

• 只给了$n$和$c$，连$e$都不知道，只能边爆破边界面看看，$e$不会太大（自然就是低加密指数了）

import gmpy2
from Crypto.Util.number import *
flag = 
n = 
for e in range(1,10):
    print(long_to_bytes(int(gmpy2.iroot(flag,e)[0])))
# b'NSSCTF{because_i_like}'

极端情况 题目2

• 题目来源：鹤城杯 2021\Crazy_Rsa_Tech | NSSCTF
• 题目附件如下：

from Crypto.Util.number import *
from Crypto.Util.Padding import *

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
"""
n_list: [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list: [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]\
"""

• 这题很显然就是一个CRT+极端情况的一类题型，首先我们之间使用CRT解出如下同余方程组，此时$m^{9}< n_1...n_i$，直接对$m^{9}$开根即可。

$$\begin{cases} m^{9}\equiv c_1~mod(~n_1)\\ m^{9}\equiv c_2~mod(~n_2)\\ ...\\ m^{9}\equiv c_i~mod(~n_i) \end{cases}\Rightarrow m^{9}\equiv C~mod(~n_1*...*n_i)$$

• exp如下，使用的是sagemath：

import gmpy2
from Crypto.Util.number import *
n_list=
c_list=
e = 9
x = CRT(c_list,n_list)
print(x)
m = gmpy2.iroot(x,9)[0]
flag = long_to_bytes(int(m))
print(flag)
# b'flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16'

题型2 刻板消息

刻板消息 题目1

• 题目来源：

• 题目附件如下：

1

刻板消息 题目2

• 题目来源：NSSCTF 2ndEzRSA | NSSCTF
• 题目附件如下：

from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
assert m.bit_length()<200
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
c = pow(m, e, n)
kbits = 103
m = (m >> kbits) << kbits # 遮盖低103位
Mod = getPrime(1024) # 生成1024位素数
hint1 = (2021-2023*m) % Mod # 计算一个同余式,没模之前计算结果是负数,模之后是正数其实就是(Mod+2021-2023*m)
hint2 = pow(2, 2023, Mod) # 计算2^2023 % Mod
print('n =',n)
print('c =',c)
print('hint1 =',hint1)
print('hint2 =',hint2)


'''
n = 115383855234466224643769657979808398804254899116842846340552518876890834212233960206021018541117724144757264778086129841154749234706140951832603640953383528482125663673926452745186670807057426128028379664506531814550204605131476026038420737951652389070818761739123318769460392218629003518050621137961009397857
c = 5329266956476837379347536739209778690886367516092584944314921220156032648621405214333809779485753073093853063734538746101929825083615077
hint1 = 153580531261794088318480897414037573794615852052189508424770502825730438732573547598712417272036492121110446656514226232815820756435437665617271385368704576530324067841094570337328191161458300549179813432377043779779861066187597784486306748688798924645894867137996446960685210314180286437706545416961668988800
hint2 = 130939024886341321687705945538053996302793777331032277314813607352533647251650781154105954418698306293933779129141987945896277615656019480762879716136830059777341204876905094451068416223212748354774066124134473710638395595420261557771680485834288346221266495706392714094862310009374032975169649227238004805982
'''

• 这题起始也满足极端情况，但是主要目的是了解刻板消息攻击。所以在这里就直接使用刻板消息攻击进行解题。

• 接下来分析一下这个题目：

$$\begin{array}{l} h_1\equiv(2021-2023*m)~mod(~r)\\ h_2\equiv2^{2023}~mod(~r) \end{array}$$

• 使用模多项式的Coppersmith攻击的话需要两个必要的东西：其中一个就是方程，另一个是模数$N$，这个模数要满足$r|N$。根据$h_2$，我们可以得到模数$N$，如下所示：

$$2^{2023}-h_2\equiv 0~mod(~r)$$

• 现在我们就需要通过$h_1$去构造方程，所构造的方程就可以得到如下所示的方程：

$$2023*m+h_1-2021\equiv0~mod(~r)$$

• 接下来我们就可以构造如下的方程使用Coppersmith攻击去求得$m$：

$$2023*m+h_1-2021\equiv0~mod(~2^{2023}-h_2)$$

• 接下来就是比较常见的刻板消息使用Coppersmith攻击求解明文m的低位，构造方程：

$$c-(m+x)^{3}\equiv 0~mod(~n)$$

• 最后exp如下：

from Crypto.Util.number import *

n = 
c = 
hint1 = 
hint2 = 

kp = pow(2,2023) - hint2
PR.<x> = PolynomialRing(Zmod(kp))
f = hint1 - 2021 + 2023 * x
f = f.monic()
result = f.small_roots(X=2^200,beta=0.5)
print(result)
m = 1746716778150027565782467891299010283212636160
print(long_to_bytes(m))
P.<y> = PolynomialRing(Zmod(n))
g = c - (m+y)^3 
g = g.monic()
result2 = g.small_roots(X=2^200,beta=0.5)
print(result2)
flag = m+9770564320547953144707390074493
print(long_to_bytes(flag))
"""
[1746716778150027565782467891299010283212636160]
b'NSSCTF\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
[9770564320547953144707390074493]
b'NSSCTF{Rea1_Si9n3n}'
"""

刻板消息 题目3

• 题目来源：XYCTF2025 Complex_signin
• 题目附件如下：

from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import hashlib
from secret import flag


class Complex:
    def __init__(self, re, im):
        self.re = re # 实部
        self.im = im # 虚部

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im # 相乘后的实数部分
        im_ = self.re * c.im + self.im * c.re # 相乘后的虚数部分 
        return Complex(re_, im_)

    def __eq__(self, c):
        return self.re == c.re and self.im == c.im # 判断相等

    def __rshift__(self, m):
        return Complex(self.re >> m, self.im >> m) # 实部和虚部同步右移

    def __lshift__(self, m):
        return Complex(self.re << m, self.im << m) # 实部和虚部同步左移

    def __str__(self):
        if self.im == 0:
            return str(self.re) # 如果虚数部分为0,返回实数部分
        elif self.re == 0:      # 如果实数部分为0,且虚部为1
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

    def tolist(self):
        return [self.re, self.im]


def complex_pow(c, exp, n): # 定义复数域上的模幂运算
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

bits = 128
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

'''
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
'''

• 此题同样有两种做法，第一种就是二元Coppersmith攻击，第二种是使用结式消元将二元多项式转换成一元多项式然后打一元Coppersmith攻击。

• 附件中实现了复数域上的RSA加密。在附件的代码中，我们能看到一个复数类，这个类里面的属性有re（实部）、im（虚部），然后还有几个方法：

• def __mul__即两个复数相乘运算，运算结果如下：

  • 设$x = a_1 + b_1i$，设$y= a_2+b_2i$
  • 则两个复数相乘的结果为$x*y = a_1*a_2-b_1*b_2+(a_1*b_2+a_2*b_1)i$

• def __eq__，这个方法定义了判断两个复数是否相等。

• def __rshift__(self, m)、def __rshift__(self, m)这两个定义了复数域上的位移操作，左移或者右移m位就相当于将实部和虚部都左移或者右移m位。

• def __str__，返回的就是这个复数的字符表达形式。

• def tolist，获取这个复数类的实部和虚部。

• 程序中还有一个函数def complex_pow，实现的就是复数域上的模幂运算。

• 接下来我们查看加密过程，与正常RSA加密没差，先是生成n，然后这里m即明文是复数，并且实部和虚部都是随机生成的一个整数。

bits = 128
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

• 然后我们对m进行rsa加密，加密过程$c \equiv m^3~mod~(n)$，很显然是一个低指数加密，并且之后我们的m还泄露了高位。这时我们就会想到需要使用coppersmith攻击。但是这与我们之前做的一元coppersmith攻击不同。我们先将方程列好。

  • 设$m = a+bi$，则有如下式子：

  $$\begin{array}{l} c \equiv m^3~mod(n) \\c \equiv (a+bi)^3~mod(n) \\c \equiv a^3-3ab^2+(3a^2b-b^3)i~mod(n) \end{array}$$

  • 这时我们再设$a = a_h+x,~~~b=b_h+y$，带入上面的式子就会得到：

  $$c \equiv (a_h+x)^3-3(a_h+x)(b_h+y)^2+[3(a_h+x)^2(b_h+y)-(b_h+y)^3~mod(n)$$

  • 实部对实部虚部对虚部就会有如下式子：

  $$0 \equiv (a_h+x)^3-3(a_h+x)(b_h+y)^2-c_1~mod(n) \\0 \equiv 3(a_h+x)^2(b_h+y)-(b_h+y)^3-c_2~mod(n) \\记f_1 = (a_h+x)^3-3(a_h+x)(b_h+y)^2-c_1~mod(n) \\记f_2 = 3(a_h+x)^2(b_h+y)-(b_h+y)^3-c_2~mod(n)$$

• 这时我们就列出了一个coppersmith求解形式的方程，但是这时我们会发现这里面有俩个未知数，所以显而易见，可以尝试使用二元coppersmith攻击。网上有现成的脚本可以使用。（不懂原理，只会当脚本小子）。这边有俩个方程式，经过尝试，我们可以通过f1这个方程式求出x和y，或者通过f1-f2这个方程式求出x和y，但是使用f2这个方程式并不能解出x和y

import itertools

def small_roots2(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []
mh = 
n = 
C = 

PR.<x,y> = PolynomialRing(Zmod(n))
f1 = (mh[0]+x)^3 - 3*(mh[0]+x)*(mh[1]+y)^2 - C[0] 
f2 = 3*(mh[1]+y)*(mh[0]+x)^2 - (mh[1]+y)^3 - C[1]
#f = f1-f2
x,y = small_roots2(f1,[2^128,2^128],4,d=3)[0]
print(x)
print(y)
m1 = x + mh[0]
m2 = y + mh[1]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
from Crypto.Cipher import ChaCha20
import hashlib
print(ChaCha20.new(key=hashlib.sha256(str(m1 + m2).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc))
# b'XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}'

• 接下来再提供一种结式消元的做法，其中结式这个概念在高等代数中会学习到。（等学到了再补充，先鸽一下）

随机填充攻击

• 随机填充和刻板消息这两个攻击要区别开来

  • 刻板消息是掩盖掉原来消息的部分值，这个值足够小。
  • 随机填充是在完整的明文上添加一个随机填充值，这个值足够小。

• 当已知两个明文有仿射关系$m_2=m_1+b$，此时$b$是不知道的。这个时候当$b$足够小的时候也仍然能恢复明文。这个攻击需要再公钥指数为$e=3$的时候，使用Coppersmith攻击。接下来介绍一下这个攻击的相关定理，该定理为定理4.5。

  • 设$(e,N)$是有效的RSA密钥，并且公钥指数$e=3$。设$m_1$和$m_2$是两个明文消息，并且满足$m_2=m_1+b$。

  • 并且已知$c_1=m_1^{3} mod(~N),c_2=(m_1+b)^{3}mod(~N)$和公钥，如果$|b|<N^{\frac{1}{9}}$那么这个明文$m_1,_2$就能在关于$log(N)$的多项式时间内算出来。

  • 该定理的证明如下：

    • 因为$m_1^{3}-c_1\equiv 0~mod(~N)$并且$(m_1+b)^{3}-c_2\equiv0~mod(~N)$，就有如下结式：

    \begin{align} R_{m_1}&=(m_1^{3}-c_1,(m_1+b)^{3}-c_2)\\ &\equiv b^{9}+(3c_1-3c_2)b^{6}+(3c_1^{2}+21c_1c_2+3c_2^{2})b^{3}+(c_1-c_2)^{3}~mod(~N)\\ &\equiv 0(mod~N) \end{align}

    • 根据这个结式计算，可以看到这个是一个次数为9的多项式$f_N(x)\in Z_N(x)$

    $$f_N(x)=x^{9}+(3c_1-3c_2)x^{6}+(3c_1+21c_1c_2+3c_2^{2})x^{3}+(c_1-c_2)^{3}~mod(~N)$$

    • 该多项式有根$x_0=b~mod(N)$，因为$|b|<N^{\frac{1}{9}}$，所以我们可以使用Coppersmit方法发现小根$b$。
    • 一旦$b$被求出，就可以应用Franklin-Reiter相关消息攻击来计算出$m_1$和$m_2$。由于所有计算都可以在关于$log(N)$的多项式时间内完成，因此定理得证。

泄露信息

• 当使用较小的公钥指数，私钥指数的某些信息可能会被泄露。Boneh、Durfee和Frankel观察到，如果已知密钥等式中的常数k，就会泄露关于私钥指数最高有效位的信息

$$ed=1+k\phi(N)$$

• 该结论的定理如下，记该定理为定理4.6，定理内容如下：
  • 设$(e,N)$是有效的RSA公钥，设$(d,p,q)$是相对应的私钥，则有密钥等式$ed=1+k\phi(N)$，$k$是正整数。
  • 我们可以这样计算$d_1$，$|d_1-d|<p+q$，可以在关于$log(N)$的多项式时间内计算出来
  • 证明：
    • 有公钥$(e,N)$和$k$，我们计算出$d_1=\lceil\frac{1+kN}{e}\rfloor$。
    • 因此$d_1=\frac{1+(kN)}{e}+\alpha$，其中$|\alpha|<1$
    • 重新回顾密钥等式，将其写成$ed=1+k(N-s)$
    • 这样就有$$|d_1-d|=|\frac{1+kN}{e}+\alpha-\frac{1+k(N-s)}{e}|=|\frac{ks}{e}+\alpha|<s+1=p+q$$
    • 当$k<e,s=p+q-1$，计算出$d_1$能在关于$log(N)$的多项式时间内算出。
  • 进而可以得出如下结论：
    • 对于平衡素数RSA这种情况来说，素数之和满足$p+q>\frac{3}{2}N^{\frac{1}{2}}$。因此给定公钥和常数$k$的情况下，我们可以计算出一个$d_1$，使得$|d_1-d|<\frac{3}{2}N^{\frac{1}{2}}$
    • 也就是说，当$k$已知时，我们实际上掌握了私钥指数$d$的大约一半最高有效位。
    • 反过来，也比较容易证明当已知私钥指数的最高有效位会泄露关于常数$k$的信息，这一点会在部分私钥泄露攻击中被利用。
    • 当公钥指数足够小时，由于$k<e$，可以通过穷举法直接猜测$k$。
    • 一般来说还需要一种机制来验证猜测，从而确定$k$的正确值。然而，在极端情况下，当$e=3$时，可以证明$k=2$。这一观察最早由Boneh提出，并在下面的4.7中被形式化表达。
• 接下来介绍一下定理4.7，定理内容如下：
  • 设$N=pq$是有效的RSA模数，其中$p,q>3$，并设$(e,N)$是有效的RSA公钥。如果$e=3$，密钥等式$ed=1+k\phi(N)$的常数满足$k=2$
  • 证明如下：
    • 从密钥等式中我们知道$0<k<e$，由于$e=3$是一个有效的RSA公钥指数。
    • 还已知$gcd(3,p-1)=1$，因此$p-1\not\equiv 0~mod(~3)$，从而得到$p>3$
    • 还知道$gcd(3,p)=1$，因此$p-1\not\equiv 2~mod(~3)$
    • 同理可以得到$q-1\equiv~mod(~3)$
    • 因此就有$\phi(N)=(p-1)(q-1)\equiv1~mod(~3)$
    • 那么就有$3d=1+k\phi(N)~mod (~3)$，可以得到$k\equiv -1 \equiv 2~mod(~3)$，又因为$0<k<3$
    • 从而得到$k=2$
  • 因此，当公钥指数$e=3$时，私钥指数有大约一半的最高有效位总是会被泄露。尽管这似乎表明使用公钥指数$e=3$的RSA可能是不安全的，但目前并不存在一种攻击，能够在没有额外信息的情况下，仅利用这一性质来攻破RSA。
  • 此外，正如Boneh、Durfee和Frankel在论文所讲到的那样，如果存在一种算法，在公钥指数较小的情况下，能够在已知私钥指数最高有效位一半的前提下分解模数，那么该算法就可以被用作任意RSA模数的通用分解算法了。
  • 设这样一种运算的运行时间为$T$。对于任意RSA模数$N$，令$z$为不整除$\phi(N)$的最小素数，则$(z,N)$构成模数$N$的一个合法公钥。根据定理4.6，我们可以通过对所有满足$k<z$的候选值进行尝试，计算出对应私钥指数最高有效位的大约一半。正确的候选值能够使我们得到私钥指数的一半最高有效位，从而进一步分解该模数。
  • 由于$z$是未知的，我们需要一次测试每一个奇素数，并对每个素数枚举其对应的所有$k$候选值，知道找到$k$为止。被测试的候选数量被$z^2$所界定，因此该通用分解算法的总体运行时间最多为$z^{2}T$。对于随机选取的RSA素数，通常认为$z$不会很大，因此在高概率意义下，其运行时间将主要由$T$所主导。