2024网鼎杯半决赛的RSA加密分析

题目并不难，但线下赛断网出爆破题，也是够6的

题目：RSA加密分析.zip

Part.1 构造格基解y和k·

首先看第一部分，主要就是有三组

$$e_i \equiv (x^2)^{-1} z_i \pmod {\varphi(n_i)}$$

知道各组的$n_i$和$e_i$，分解$n_0$

把式子转一下，就是

$$x^2 e_i \equiv z_i \pmod {\varphi(n_i)}$$

拆模数，就是存在$k_i$使得

$$\begin{aligned} x^2 e_i - k_i \varphi(n_i) &= z_i \\ x^2 e_i - k_i (p_i-1) (q_i-1) &= z_i \\ x^2 e_i - k_i ((n_i+1) - (p_i+q_i)) &= z_i \\ \end{aligned}$$

令$s_i = (p_i+q_i)$，就是

$$\begin{aligned} x^2 e_i - k_i ((n_i+1) - s_i) &= z_i \\ x^2 e_i - (n_i+1) k_i &= z_i - k_i s_i \\ \end{aligned}$$

最后令$y_i = z_i - k_i s_i$，得

$$\begin{aligned} x^2 e_i - (n_i+1) k_i &= y_i \\ \end{aligned}$$

算一下各个变量大小，大概是

$$\begin{aligned} x &= O(n^{3/16}) \\ e_i &= O(n) \\ n_i &= O(n) \\ k_i &= O(x^2) = O(n^{6/16}) \\ z_i &= O(n^{10/16}) \\ s_i &= O(n^{1/2}) \\ y_i &= O(n^{14/16}) \\ \end{aligned}$$

其中未知的$x$和$k_i$都算小变量，但$y_i$有点大

先怼个格，按照HNP的方式可以把$x^2$去掉，选两个式子联立起来就是

$$\begin{aligned} x^2 e_i e_j &= e_j (n_i+1) k_i + e_j y_i \\ x^2 e_j e_i &= e_i (n_j+1) k_j + e_i y_j \\ \end{aligned}$$

相减

$$\begin{aligned} e_i (n_j+1) k_j - e_j (n_i+1) k_i + e_i y_j - e_j y_i &= 0 \\ \end{aligned}$$

构造格基

$$B = \begin{bmatrix} \begin{array}{ccc|ccc} 1 & e_1 (n_0+1) & e_2 (n_0+1) & \\ & - e_0 (n_1+1) & & \\ & & - e_0 (n_2+1) & \\ \hline & e_1 & e_2 & 1 \\ & -e_0 & & & 1 \\ & & -e_0 & & & 1 \\ \end{array} \end{bmatrix}$$

令

$$\begin{aligned} v &= (k_0, k_1, k_2\ |\ y_0, y_1, y_2) \\ w &= (k_0, 0, 0\ |\ y_0, y_1, y_2) \end{aligned}$$

就是

$$v B = w$$

算一下，理论上对$B$直接LLL的话是解不出$w$的（实际也是如此）

但观察一下$w$向量，前面有很多$0$，所以其实可以对$B$的前三列乘上一个大的常数来增大格基$B$的行列式，同时保持$w$的长度不变（注：因为$w$的第一个元素是$k_0$不是$0$，所以第一列需要乘上的一个$O(y/k)$大小的常数）

PS：当时我还试过把$i=1$、$j=2$的式子也加上去，但发现格基不满秩，然后就没有然后了

第一部分的参考代码

#!/usr/bin/env sage
ns=[58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es=[46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c=45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729

e = es
n = ns

D = 2^512
C = 2^510
B = matrix(ZZ, [
  [C,  e[1] * (n[0] + 1) * D,  e[2] * (n[0] + 1) * D, 0, 0, 0],
  [0, -e[0] * (n[1] + 1) * D,  0                    , 0, 0, 0],
  [0,  0                    , -e[0] * (n[2] + 1) * D, 0, 0, 0],
  [0,  e[1]              * D,  e[2]              * D, 1, 0, 0],
  [0, -e[0]              * D,  0                    , 0, 1, 0],
  [0,  0                    , -e[0]              * D, 0, 0, 1],
])
w = B.LLL()[0]
v = w * B^(-1)

print(v)
print(w)
print()

k = v[:3]
y = v[3:]

这样就可以解出各组的$k_i$和$y_i$

本来以为到这里就结束了，但才发现需要接的并不是$x$

而根据$k_i$和$y_i$并不能直观地解出$s_i$，需要知道$s_i$才能分解

Part.2 求p高位·

接下来看看怎么使用$k_i$和$y_i$解出$s_i$

首先已知

$$y_i = z_i - k_i s_i$$

直接对$y_i$除以$k_i$的话，可以得到

$$\frac{-y_i}{k_i} = s_i + \frac{z_i}{k_i}$$

其中$z_i / k_i$的大小大概为

$$\frac{z_i}{k_i} = O(n^{10/16 - 6/16}) = O(n^{1/4})$$

而$s_i$的大小为

$$p_i + q_i = O(n^{1/2})$$

所以$\frac{-y_i}{k_i}$可以泄露$p_i + q_i$高位的约一半的比特

通过$p_i + q_i$高位比特可以计算$p_i - q_i$的高位比特，计算方法还就是那个

$$p_i - q_i = \sqrt{(p_i + q_i)^2 - 4 n_i}$$

只需要取结果的高位比特即可

最后通过计算

$$p_i = \frac{(p_i + q_i) + (p_i - q_i)}{2}$$

即可得到$p_i$的高位比特

当然，以上的计算过程都会产生误差，而且所泄露的比特数量取决于$z_i$的大小

接下来就是漫长的调参了

先给出结果和参考代码

#!/usr/bin/env sage
a = 255
error = 5
ppq = -y[0] // k[0]
pmq = floor(pow((ppq)^2 - 4*n[0], 1/2))
p = floor((ppq + pmq) // 2)
p = p >> (a + error)
print('ph = %d' % p)

最后得到了$p$的$252$比特

Part.3 调参·

至于为什么要调参，是因为接下来我想要做的是$p_i$高位泄露攻击，这个攻击需要知道$p_i$的一半以上高位比特

而根据以上分析，我们可以得到的$p_i$高位比特最多是$256$位，这是不能成功攻击的

所以需要枚举出更多的$p_i$未知比特，这是这道题最最最最最最最最最最最最最最最恶心的地方！

这个枚举需要调用Coppersmith，需要花费不少时间，所以在枚举前需要确保解出来的$p_i$高位比特是正确的

我的做法是使用题目的代码生成多次数据，然后通过调整a和error保证90%以上的正确率

参考代码

#!/usr/bin/env sage
import random
from Crypto.Util.number import *
from gmpy2 import iroot

flag = b''

N = 100
yes = 0
for _ in range(N):
  k = 3
  d = k/(2*(k+1))
  ns = []
  pqs = []
  es = []
  zs = []

  for i in range(3):
      p = getPrime(512)
      q = getPrime(512)
      if p < q:
          tmp = p
          p = q
          q = tmp
      n = p*q
      ns.append(n)
      pqs.append((p,q))

  n = min(ns)
  x = random.randint(0,int(n^(d/2)))
  x = next_prime(x)

  for i in range(3):
      p,q = pqs[i][0],pqs[i][1]
      bound1 = int((p-q)/(3*(p+q)) * x * n ^ 0.25)
      bound2 = int((p-q)/(3*(p+q)) * x^2 * n ^ 0.25)
      z = random.randint(bound1,bound2)
      zs += [z]
      f = (p-1)*(q-1)
      e = inverse(x^2,f) * z % f
      es.append(e)

  n = ns
  pq = pqs
  e = es
  z = zs

  s = []
  k = []
  y = []
  for i in range(3):
    s += [sum(pq[i])]
    phi = (pq[i][0]-1) * (pq[i][1]-1)
    assert (x^2 * e[i] - z[i]) % phi == 0
    k += [(x^2 * e[i] - z[i]) // phi]
    y += [z[i] - k[i] * s[i]]

  k0 = k[0]
  y0 = y[0]
  n0 = n[0]
  e0 = e[0]
  p0 = pq[0][0]
  q0 = pq[0][1]
  z0 = z[0]
#  if k0.nbits() != 380:
#    continue

  ppq = -y0 // k0
  a = 255
  error = 5
  print(hex(ppq >> a))
  print(hex((p0 + q0) >> a))

  pmq = floor(pow(ppq^2 - 4*n[0], 1/2))
  print(hex((p0 - q0) >> a))
  print(hex(pmq >> a))
  print()

  ppq = ppq >> a
  pmq = pmq >> a
  p = (ppq + pmq) // 2
  p = p >> error
  print(hex(p))
  print(hex(p0 >> (a + error)))
  if p == p0 >> (a + error):
    yes += 1
  print(p.nbits())
  print(Integer(n[0]).nbits())

print('%d / %d' % (yes, N))
# 99 / 100

除此之外，还需要知道在$p$为$512$比特的时候，攻击算法需要知道多少比特的高位

这个自己拿自己的算法去测就好了，反正我测出来我的至少需要知道$262$位

也即至少需要枚举$10$个未知比特

Part.4 多进程的已知p高位分解·

要知道$2^{10} = 1024$，在调Coppersmith的情况下至少要搞半天吧

所以不得已，搞了个多进程的版本

比赛前几天刚好@shikaku提到可以用sage.parallel.multiprocessing_sage实现Sage的多进程

然后我刚好没去看，所以就刚好爆0了。。。

赛后怼了份模板

#!/usr/bin/env sage
from sage.all import *
from sage.parallel.multiprocessing_sage import parallel_iter
from tqdm import tqdm

def gao(n, ph, pl=1, pbits=512):
  global tqdm
  hbits = Integer(ph).nbits()
  lbits = Integer(pl).nbits()
  PR = PolynomialRing(Zmod(n), 'x')
  x = PR.gen()
  f = ph * 2**(pbits-hbits) + x * 2**lbits + pl
  f = f.monic()
  # p:512 ph:262
#roots = f.small_roots(X=2**(pbits-hbits-lbits+1), beta=0.48, epsilon=0.0106)
  roots = f.small_roots(X=2**(pbits-hbits-lbits+1), beta=0.48, epsilon=0.0103)
  if roots:
    pm = Integer(roots[0])
    p = ph * 2**(pbits-hbits) + pm * 2**lbits + pl
    if n % p == 0:
      q = n // p
      print()
      print('p = %d' % p)
      print('q = %d' % q)
      return p, q
  return None


def mgao(n, ph, T=16, gmax=262):
  hbits = Integer(ph).nbits()
  gbits = gmax - hbits
  ph = ph << gbits
  N = 2**gbits
  for i in tqdm(range(N//T + 1)):
    pars = []
    for j in range(T):
      pars += [((n, ph+(T*i+j), 1, 512), {})]
    res = list(parallel_iter(T, gao, pars))
    for r in res:
      if r[1] != None:
        return r[1]

ph = 4154105556012159824007632555267171047079134414914023397680651326221752696528
n = 58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167
mgao(n, ph)

'''
✎ $ sage -python ./m.sage
 74%|███████████████████████████████████████████████████████████████████▏                       | 48/65 [31:05<11:01, 38.89s/it]
p = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
q = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023

p = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
q = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023
'''

其实就是之前写过的代码的多进程版本

Part.5 解密·

最后解密即可，解密时还套了一层AMM，这个之前写过了直接套

解这道题的时候顺便更新了一下之前的模板，可以去看看

#!/usr/bin/env sage
import string
# https://tover.xyz/p/n-root-in-F/
from nth import *

e = 8462913
c = 45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
p = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
q = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023

checker = genStrChecker(string.printable, 48)
#res = nthRSA_n(c, e, [p, q], checker=checker)
res = nthRSA_n(c, e, [p], checker=checker)
print(res)

# flag{N3w_Attacks_4_key_equat1ons}

总结·

菜：（