共私钥攻击

  • 推导所参考的论文:ijeie-2017-v7-n2-p79-87.pdf
  • 这篇是关于多素数RSA的共素数攻击,在2025年强网拟态的时候就出现过一题,但是由于时间关系以及2026年的一些迷茫的状态,导致这篇博客鸽了很久,现在就来完成这篇博客。
  • 多素数的共私钥攻击,对于素数生成的条件和两个素数的共私钥攻击生成条件是一样的都是平衡素数。攻击情景就是多素数RSA的多个实例共享一个较小的私钥dd,这样的情景就是多素数RSA攻击下的共私钥攻击。现实情景就是具体针对多素数RSA被应用于广播的情况,同一条消息被广播给多个接收者,这些接收者使用相同的私钥指数,但使用不同的模数。
  • 在推导前,需要假设一些条件,这些条件作为已知条件,而这些已知条件其实就是模拟真实环境下一些模数、素数的实际情况。
    • 首先假设,该多素数RSA的模数,是由rr个不同的素数相乘得到的。
      • 在推导中,默认将这rr个素数从小到大排列,也就是p1<p2<...<prp_1<p_2<...<p_r。
      • 在上面这样情况下,再假设有4<12N1r<p1<N1r<pr<2N1r4<\frac{1}{2}N^{\frac{1}{r}}<p_1<N^{\frac{1}{r}}<p_r<2N^{\frac{1}{r}}
      • 还要保证密钥生成算法与RSA的密钥生成算法相同,在这里要求使用rr个互不相同的素数。
    • 接着在通常情况下,公钥和私钥被定义为满足ed≡1 (mod ϕ(N))ed\equiv 1~(mod~\phi(N)),此时就有ed=1+kϕ(N)ed=1+k\phi(N),其中kk是某些或者某个正数。
  • 在上面的假设下,其实就可以考虑之前正常RSA加密下经常提到的改写ϕ(N)\phi(N)的表达,也就是ϕ(N)=N−s\phi(N)=N-s,这样就可以得到了s=N−ϕ(N)s=N-\phi(N),这样就有如下推导(论文的求和符号写的不够严谨,会产生歧义,下面的式子参考的是另一篇博客多素数RSA加密原理的式子):

s=N−ϕ(N)=N−Πi=1r(pi−1)=∑i=1rNpi−∑i,j=1,i<jrNpipj+∑i,j,k=1,i<j<krNpipjpk+⋅⋅⋅+(−1)r\begin{array}{l} s&=N-\phi(N)\\ &=N-\Pi^{r}_{i=1}(p_i-1)\\ &=\sum^{r}_{i=1}\frac{N}{p_i}-\sum^{r}_{i,j=1 ,i<j}\frac{N}{p_ip_j}+\sum^{r}_{i,j,k=1,i<j<k}\frac{N}{p_ip_jp_k}+···+(-1)^{r} \end{array}

  • 从上面推导出ss的表达式,再结合前面的平衡素数的条件,可以确定ss的一个上界为∣s∣<(2r−1)N1−1r|s|<(2r-1)N^{1-\frac{1}{r}}
  • 从而得到一个关键结论:ϕ(N)\phi(N)和NN有r−1r\frac{r-1}{r}个最高位MSb是相同的,也就是说NN是ϕ(N)\phi(N)的一个很好的近似,有了这个近似,就可以从格基归约的角度出发进行破解。

共私钥攻击 推导

  • RSA攻击最终目标就是要分解大整数,得到私钥其实还不算完全破解,所以共私钥攻击一共有两个关键步骤,这篇文章主要讨论的是第一步:

    • 第一步就是通过条件,判断是否可以进行格攻击,能进行格攻击,就使用格攻击将私钥dd求出来。
    • 第二步就是通过求出的私钥dd,利用ed≡1 mod( ϕ(N))ed\equiv 1~mod(~\phi(N)),这个式子结合Miller的结论可以通过随机数算法分解出素数。这一步在这里不多介绍,在多素数RSA分解加密之分解n攻击1中有详细的推导和解答。
  • 先说论文用到的攻击结论:N1<N2<N3<...<Nn<2N1N_1<N_2<N_3<...<N_n<2N_1且(e1,N1),(e2,N2),...,(en,Nn)(e_1,N_1),(e_2,N_2),...,(e_n,N_n)是有效的多素数RSA公钥,对应的私钥为d<Nnδnd<N^{\delta_n}_{n},其中δn<nr(n+1)−logNn(4r−2)\delta_n<\frac{n}{r(n+1)}-log_{N_n}(4r-2),此时所有的模数能在关于log(Nn)log(N_n)和nn的多项式时间内被分解。

  • 证明如下:

    • 设M=⌊Nn1−1r⌋M=\lfloor N_n^{1-\frac{1}{r}}\rfloor,对于已知的公钥对(e1,N1),...,(en,Nn)(e_1,N_1),...,(e_n,N_n)以及未知的私钥指数dd,将这些nn组密钥对都使用密钥等式展开eid=1+ki(Ni−si)e_id=1+k_i(N_i-s_i)。再加上一个恒等式dM=dMdM=dM。展开如下所示(注意论文在列式子的时候e1d−N1k1=1−k1s1e_1d-N_1k_1=1-k_1s_1写成了e1d−N1k2=1−k1s1e_1d-N_1k_2=1-k_1s_1):

    dM&=&dM\\ e_1d-N_1k_1&=&1-k_1s_1\\ e_2d-N_2k_2&=&1-k_2s_2\\ \vdots&\dots&\vdots\\ e_nd-N_nk_n&=&1-k_ns_n

    • 将上面的一些列等式重写,写成向量·矩阵的形式,即xn⃗Bn=vn⃗\vec{x_n}B_n=\vec{v_n},其中xn⃗=(d,k1,k2,...,kn)\vec{x_n}=(d,k_1,k_2,...,k_n),以及Bn=[Me1e2…en0−N10…000−N2…0⋮⋮⋮⋱⋮000…−Nn]B_n=\begin{bmatrix}M&e_1&e_2&\dots&e_n\\ 0&-N_1&0&\dots&0\\ 0&0&-N_2&\dots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\dots&-N_n\end{bmatrix},再加上v⃗=(dM,1−k1s1,...,1−knsn)\vec{v}=(dM,1-k_1s_1,...,1-k_ns_n),这样就造出一个格了。造出的格如下面的式子所示:

    (d,k1,k2,...,kn)[Me1e2…en0−N10…000−N2…0⋮⋮⋮⋱⋮000…−Nn]=(dM,1−k1s1,...,1−knsn)(d,k_1,k_2,...,k_n)\begin{bmatrix}M&e_1&e_2&\dots&e_n\\ 0&-N_1&0&\dots&0\\ 0&0&-N_2&\dots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\dots&-N_n\end{bmatrix}=(dM,1-k_1s_1,...,1-k_ns_n)

    • 向量v⃗n\vec{v}_n是矩阵BnB_n的各行向量的一个整数线性组合,因此vnv_n是由矩阵BnB_n的行向量所生成的格LL中的一个向量。由于Ni≤Nn<2N1,ki<d<Nnδn,∣si∣<(2r−1)N(1−1r),i=1,2,...,nN_i≤N_n<2N_1,k_i<d<N^{\delta_n}_{n},|s_i|<(2r-1)N^{(1-\frac{1}{r})},i=1,2,...,n
    • 因此构造出来的目标向量∣∣vn∣∣<1+n(2r−1)2Nnδn+1−1r||v_n||<\sqrt{1+n(2r-1)^{2}}N^{\delta_{n}+1-\frac{1}{r}}_n,推导如下:

    ∣∣vn∣∣2=(dM)2+(1−k1s1)2+...+(1−knsn)2≤(Nnδn+1−1r)2+(1−Nnδn+1−1r(2r−1))2+...+(1−Nnδn+1−1r(2r−1))2=(Nnδn+1−1r)2+n(1−Nnδn+1−1r(2r−1))2=(Nnδn+1−1r)2+n{1−2Nnδn+1−1r(2r−1)+[Nnδn+1−1r(2r−1)]2}=[n(Nnδn+1−1r)2−2n(2r−1)Nnδn+1−1r+(2r−1)2n](Nnδn+1−1r)2<(1+(2r−1)2n)(Nnδn+1−1r)2\begin{array}{l} ||v_n||^{2}&=(dM)^{2}+(1-k_1s_1)^{2}+...+(1-k_ns_n)^{2}\\ &≤(N_n^{\delta_n+1-\frac{1}{r}})^{2}+(1-N_n^{\delta_n+1-\frac{1}{r}}(2r-1))^{2}+...+(1-N_n^{\delta_n+1-\frac{1}{r}}(2r-1))^{2}\\ &=(N_n^{\delta_n+1-\frac{1}{r}})^{2}+n(1-N_n^{\delta_n+1-\frac{1}{r}}(2r-1))^{2}\\ &=(N_n^{\delta_n+1-\frac{1}{r}})^{2}+n\{1-2N_n^{\delta_n+1-\frac{1}{r}}(2r-1)+[N_n^{\delta_n+1-\frac{1}{r}}(2r-1)]^{2}\}\\ &=[\frac{n}{(N_n^{\delta_n+1-\frac{1}{r}})^{2}}-\frac{2n(2r-1)}{N_n^{\delta_n+1-\frac{1}{r}}}+(2r-1)^{2}n](N_n^{\delta_n+1-\frac{1}{r}})^{2}\\ &<(1+(2r-1)^{2}n)(N_n^{\delta_n+1-\frac{1}{r}})^{2}\\ \end{array}

    • 注意:n(Nnδn+1−1r)2−2n(2r−1)Nnδn+1−1r<0\frac{n}{(N_n^{\delta_n+1-\frac{1}{r}})^{2}}-\frac{2n(2r-1)}{N_n^{\delta_n+1-\frac{1}{r}}}<0,所以将其直接放缩成1
    • 因此,就可以得到∣∣vn∣∣<1+n(2r−1)2Nnδn+1−1r||v_n||<\sqrt{1+n(2r-1)^{2}}N^{\delta_{n}+1-\frac{1}{r}}_n
    • 接着,尝试计算BB构成的格的体积,也就是vol(L)=∣det(Bn)∣vol(L)=|det(B_n)|的值,计算过程如下:

    vol(L)&=|M\Pi^{n}_{i=1}(-N_i)|\\ &=\lfloor N_n^{1-\frac{1}{r}}\rfloor\Pi_{i=1}^{n}N_i\\ &>(\frac{N_2}{2})^{n+1-\frac{1}{r}}

    • v⃗n\vec{v}_n小于闵可夫斯基上界是v⃗n\vec{v}_n是该格中最短向量的必要条件,因此需要满足:∣∣vn∣∣<(n+1)vol(L)1(n+1)||v_n||<\sqrt{(n+1)}vol(L)^{\frac{1}{(n+1)}}
    • 接合上面已经求得的v⃗n\vec{v}_n的二阶范数的上界以及格LL的体积,就可以得到一个充分条件:

    ∣∣vn∣∣<1+n(2r−1)2Nnδn+1−1r<(n+1)(Nn2)n+1−1rn+1||v_n||<\sqrt{1+n(2r-1)^{2}}N^{\delta_{n}+1-\frac{1}{r}}_n<\sqrt{(n+1)}(\frac{N_n}{2})^{\frac{n+1-\frac{1}{r}}{n+1}}

    • 这就意味着:

    Nnδn+1−1r<cr(Nn2)(n+1−1r)(n+1)其中,cr=n+11+(2r−1)2n>(12r−1)(12)N^{\delta_{n}+1-\frac{1}{r}}_n<c_r(\frac{N_n}{2})^{(n+1-\frac{1}{r})(n+1)}\\ 其中,c_r=\sqrt{\frac{n+1}{1+(2r-1)^{2}n}}>(\frac{1}{2r-1})(\frac{1}{2})

    • 比较两边,我们可以得到δn+1−1r<n+1−1rn+1−logNr(4r−2)\delta_n+1-\frac{1}{r}<\frac{n+1-\frac{1}{r}}{n+1}-log_{N_r}(4r-2)
    • 因此就有,就可以得到δn<nr(n+1)−logNn(4r−2)\delta_n<\frac{n}{r(n+1)}-log_{N_n}(4r-2),当r=2r=2的时候就是两个素数RSA的小私钥攻击的条件。
  • 因此,当密钥指数dd小于NδN^{\delta}时,向量v⃗n\vec{v}_n满足闵可夫斯基条件,并且成为格LL中的一个最短向量。

  • 一旦获得向量vrv_r,我们就可以很容易地分解所有模数,根据v⃗n\vec{v}_n我们就可以得到密钥指数dd,再利用密钥等式ki=eid−(1−kisi)Nik_i=\frac{e_id-(1-k_is_i)}{N_i},从而计算出ϕ(Ni)=eid−1ki\phi(N_i)=\frac{e_id-1}{k_i}

  • 然而,多素数RSA加密的时候,不存在确定性地算法在已知ϕ(N)\phi(N)的情况下求分解出模数NN的素数,但是存在概率性算法可以利用ϕ(N)\phi(N)的倍数来分解出模数NN的素数。(其实就是在已知e、de、d的条件下分解NN的多素数的情况)

共私钥攻击 例题1

  • 题目来源:2025年强网拟态Unsafe Parameters

  • 题目附件如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha3_512
from secret import *

def genParams():
ns = []
es = []
ps = []
d = getPrime(425)
for _ in 'flag{':
p, q, r = [getPrime(512) for _ in range(3)]
ps.append((p, q, r))
n = p * q * r
totient = (p - 1) * (q - 1) * (r - 1)
es.append(inverse(d, totient))
ns.append(n)

return (ns, es), (d, ps)

pub, priv = genParams()

key = sha3_512(str(sum(sum(psum) for psum in priv[1])).encode()).digest()[:16]
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16))

print(f'ns = {pub[0]}')
print(f'es = {pub[1]}')
print(f'ct = {ct}')

"""
ns = [729626364576206469704240917876675932841677846807662743683194531189219993605123671836962855605283722577718230552963049472251011326675202612492908848548419883361685662678347011887752523869081347313358470192291106167923273619672010347904232948623232956703976722596246251219832472749781700661621717970912452690860710243752051416797956410009096107757901714990018414837758557784033898837218196380413347278999394220278929595840196278059116531409774355756772349502091527, 1905432596115201099512716986634374621489368222604315919606798930577721863294916275385323430940054377575273762764157350871093106918016952598143825002497857813393515175754983371150373414986745909170502391681896252141058196242286758315439213464335711981585004206505072743627148478873299089587473670712150938286701206231734068594554186483978059254161949801153805752489828395472590106405761648181381945795038085612905557546907903561767813822101495476457137965288880829, 1364349980724204783960363890369037262456777329397270902364257972605993939460160766530889520645888701966401869980072151818996346007664249855901114579605632358191242379651843548926065735575249122023543206153088606751338328933651430885645444839242513718915066302971957689904414300766000572990594260836480347717506097403302570129593533017205416936506156113683938133811098995666977893386015199252455279325252257306124895958614122639652100229863446635612470942945471629, 801368910415539931617837996119032301790585643652894417707002521182569449104238101253556548156062846942011258499343192564944616333555000780965111384091131074358231330717413121484815002612991437436336271715078003900216545055505405363415778086330672269759661284535787363323398929120499505051378299467980018690275341014026390376705451595348674549031968858607633947674244014656615045639930798213161815130251215148286379903187335369475976106390101774566278602818405563, 966507016385573035667733231340091844033410158675175976938028218854439065352997895173668326599042719776214706325758565722305289931861889759808022284179479582700755314576250841330755684569639628012527976286442288571350327307582007959428925460653350857512795573323486273071975979456828134582982048746188934676698845075430701350305713747666370252912970653968385390246217234899448990236850880873105998296512557366752267827688836849041157572772272378435636367162425013]
es = [271264973728317298627822473902975461834475616151421882685140849409171660245987005602120200976835072966082573357282000859946014645129524701781302678299643424924092704444611429422064341444927220441684375194952864825982915148126084102832224731498348832396834993134927447743362540828447462072582023959357845229307404791804881057335208287771899121154533179273274029972648764343120454360366227609296867085751393693129946684282269737380796082741762647814800935844443493, 1003585299728442138241618739786172474341836074346983356412903232651178484164007865852681323340512406956827176253325249434459143223478630158795320316445722303141000749369087588146876087005139101967705654538148200848735795226715484701026716263131990473014248826031226350016169675911701420383849573743077161936130739955632072650333006768068396767746102320645544271946493533626477749495460960365939362830334782483616521427745117179433129272929291131199903349977861093, 528794486797786998573050589647661205854628331390578568482905276781799068613879068393786314280307765489986817827366340249545226369795434498075653554440390174127680889163962386407937584138342055553885382937486807537913781141805602397908008361192107987266566035872632130183102501118938531330140154852996630732644530954025739132771439783366022539476194754352734861357158197716623228211860189868592877935421689151152269864018399507621324672725433395533000425391708101, 63082374875671578481986217433413118060930080658278695174993640397998104913203950822096713822227514918774669078130439943184022889683633824002111416144422250644695809731240622289790840695469043596475009958463780096705571401137513331089894183226911665633164170027318352120002851940432163291498705806239158684141492080194438572549164494596965748695244152843943149994989589419519395650481254722496058552304954140980743159877918387972030837603120258130045817858729621, 120373323462979513980656435521004077312964483601298713849302793507801996545855844801219890178210569842943901523332883574699699439655256681068585396438543716728771762620808023696864023456625376138578749985774885652016790204471223404504866831356254849552890279653807176865165230965065842479979722094076544915080001416276324550993965426099480075249719779502220020343237480355441663501565965298776708377675024327374331823503627493136287447543537154779812201209689733]
ct = b'J\x08\x0c\xfe\x0eC\n\x96!\xb3\x05\xa9\x9b\xf9\n\xe3-\xf2m\xdb&.\xb5h\xe1\x0e\xd6\x89\x14\x87Z\x0b0p\xbb\xd9\x93\xd7\x1cT\xa2\xf36\x02\x8e:\\\x92'
"""

共私钥攻击 板子