CTF密码学-RSA

数学基础

素数与互素数

1.素数：

一个数如果除了 1 与它本身之外没有其他的因数，那么这个数就被称为素数。

任意一个整数 (a > 1) 都能分解为 n 个素数之积。

2.合数：

如果一个数大于 1，且该数本身不是素数，那么这个数就是一个合数。

3.互质数：

如果两个整数 a，b 的最大公因数 gcd(a, b) = 1，那么称 a，b 两数互质。

由于要求最大公因子为正，所以 gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b)。一般gcd(a, b) = gcd(|a|, |b|)。由任一非 0 整数能整除0，可得 gcd(a, 0) = |a|。如果将 a, b 都表示为素数的乘积，则 gcd(a, b) 极易确定。

欧几里得算法

对于一个大整数而言，我们很难去因式分解，欧几里得算法提供了一个更有效的算法计算 gcd，这个算法基于一简单的观察，即：

$gcd(r_0,r_1)=gcd(r_0-r_1,r_1)$

其中，通常假设$r_0 >r_1$，并且两个数均为正整数。此属性的证明非常简单：

假设 $gcd(r_0,r_1)=g$，由于 g 可以同时除 $r_0$ 和 $r_1$，则可以记作 $r_0=g\cdot x$ 和 $r_1 = g\cdot y$，其中 $x>y$，且 x 和 y 为互素的整数，即它们没有公共因子。此外，证明（x - y）与 y 互素也非常简单。因此可以得到：

$gcd(r_0-r_1, r_1) = gcd(g\cdot (x-y),g\cdot y)=g$

即使处理非常长的数字（这些数字通常在公钥密码学中使用），欧几里得算法依然高效。迭代次数与输入操作数的位数有紧密的关系。这意味着如果一个 gcd 涉及的数字都是 1024 位，则此 gcd 的迭代次数就是 1024 乘以一个常数。几千次迭代的算法在当今 PC 上很容易实现。

模运算

设n是一正整数，a 是整数，如果用 n 除 a，得商为 q，余数为 r，则

$a=qn+r,0\leq r\leq n,q=\lfloor \frac {a}{n}\rfloor$

$\lfloor \frac {a}{n}\rfloor$表示对$\frac {a}{n}$进行下取整

用 $a\space mod\space n$ 表示余数 $r$，则$a=\lfloor \frac {a}{n}\rfloor n+amodn$。

如果$a\space mod\space n=b\space mod\space n$，则称两整数 $a$ 和 $b$ 模 $n$ 同余，记为$a≡b\space mod\space n$。称与 $a$ 模 $n$ 同余的数的全体为 $a$ 的同余类，记为$[a]$，称 $a$ 为这个同余类的表示元素。

注意： 如果$a≡0\space mod\space n$，则 $n$ |$a$

同余有以下性质：

① 若 $n$ | $(a-b)$，则 $a≡b\space mod\space n$

② $a\space mod\space n≡b\space mod\space n$，则$a≡b\space mod\space n$

③ $a≡b\space mod\space n$,则 $b≡a\space mod\space n$

④ $a≡b\space mod\space n$，$b≡c\space mod\space n$，则$a≡c\space mod\space n$

从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。

求余数运算（简称求余运算）a mod n 将整数 a 映射到集合 {0,1, …,n-1}，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：

① $[(a\space mod\space n)+(b\space mod\space n)] mod\space n=(a+b) mod\space n$。

② $[(a\space mod\space n)-(b\space mod\space n)] mod\space n=(a-b)\space mod\space n$。

③ $[(a\space mod\space n)×(b\space mod\space n)] mod\space n=(a×b)\space mod\space n$。

性质①的证明： 设 $a\space mod\space n=r_a$，$b\space mod\space n=r_b$，则存在整数$j$、$k$ 使得 $a=j\cdot n+r_a$，$b=k\cdot n+r_b$。

因此

$(a+b)\space mod\space n=[(j+k)n+r_a+r_b]\space mod\space n=(r_a+r_b)\space mod\space n= [(a\space mod\space n)+(b\space mod\space n)]\space mod\space n$

性质②、③的证明类似。

扩展欧几里得算法

在欧几里得算法的时候我们已经知道两个整数 $r_0$ 和 $r_1$ 的 gcd 的计算可以通过不断进行迭代地减小操作数来实现。然而，事实证明，欧几里得算法的主要应用并不在计算 gcd。扩展的欧几里得算法可以用来计算模逆元，而模逆元在公钥密码学中占有举重若轻的地位。拓展的欧几里得算法除了可以计算 gcd 外，还能计算以下形式的线性组合：

$gcd(r_0,r_1)=s\cdot r_0+t\cdot r_1$

其中s和t均表示整型系数。这个等式通常也称为丢番图方程。

这个算法的思路是：执行标准欧几里得算法，但将每轮迭代中的余数 $r_i$ 表示为以下形式的线性组合：

$r_i=s_ir_0+t_ir_i$

如果这个过程成功了，则最后一轮迭代对应的等式为：

$r_i=gcd(r_0,r_1)=s_ir_0+t_ir_1=sr_0+tr_1$

这也意味着最后一个系数 $s_i$ 也是等式所寻找的系数 s，同时 $t_i=t$。

费马小定理和欧拉定理

1.费马小定理

定理：若 p 是素数，a 是正整数且 $gcd(a, p)=1$，则 $a^{p-1}≡1\space mod\space p$。

费马小定理也可写成如下形式： 设 p 是素数，a 是任一正整数，则$a^{p}\equiv a\space mod\space p$。

2.欧拉函数

定理: 若 n 是两个素数 p 和 q 的乘积，则$\phi (n)=\phi (p)× \phi (q)=(p-1)×(q-1)$。

设 n 是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为$\phi (n)$。

例如： $\phi (6)=2$ ，$\phi (7)=6$ ，$\phi (8)=4$。

若n是素数，则显然有 $\phi (n)=n-1$。

定理：若a和n互素，则 $aφ(n) ≡ 1\space mod\space n$。

中国剩余定理

中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。

例如：$Z_{10}$ 中每个数都可从这个数关于 2 和 5（10的两个互素的因子）的同余类重构。比如已知 x 关于 2 和 5 的同余类分别是 [0] 和 [3]，即 x mod 2 ≡ 0，x mod 5 ≡ 3。可知是偶数且被 5 除后余数是 3，所以可得 8 是满足这一关系的惟一的 x。

例如: 求 $12\times 13(mod\space 15)$

因为 12 和 13 所在的行号分别为 0 和 1，12 和 13 所在的列号分别为 2 和 3，由$0\times 1\equiv 0\space mod\space 3$; $2\times 3\equiv 1\space mod\space 5$ 得$12\times 13(mod\space 15)$所在的列号和行号分别为 0 和 1，这个位置上的数是6，所以得到$12\times 13(mod\space 15)\equiv 6$。

又因为 $0+1\equiv 1\space mod\space 3$; $2+3\equiv 0\space mod\space 5$第 1 行、第 0 列为 10，所以$12+13\equiv 10\space mod\space 15$。

中国剩余定理：

设 $m_1,m_2,…,m_k$ 是两两互素的正整数，$M=$ 一次同余方程组

$$\begin{cases}a_1(mod \space m_1) \equiv x \\a_2(mod \space m_2) \equiv x \\ ... \\a_k(mod \space m_k) \equiv x\end{cases}$$

对模M有惟一解:

$x\equiv (\frac{M}{m_1}e_1a_1+\frac{M}{m_2}e_2a_2+…+\frac{M}{m_k}e_ka_k)(mod \space M)$

其中 $e_i$ 满足$\frac{M}{m_i}e_i\equiv 1(mod\space m_i)\space(i=1,2,…,k)$

RSA算法

1．密钥生成

① 选取两个保密的大素数 p 和 q。

② 计算 $n = p\times q$，$\phi (n)=(p-1)(q-1)$，其中是n的欧拉函数值。

③ 随机选取整数 e，满足 $1 < e < \phi (n) $ ，且 $gcd(e,\phi (n))=1$。

④ 计算 d，满足。$de\equiv 1\space mod \space \phi (n)$

⑤ 公钥为 $(e,n)$，私钥为 $(d, n)$。

2．加密

将明文转换成十进制数，则加密算法为：

$c=m^e\space mod \space n$

c为密文，且 $0 ≤ c < n$。

3．解密

对于密文0≤c＜n，解密算法为：

$m=c^d \space mod \space n$

RSA安全性分析

对于 RSA 加密算法，公钥 (N, e) 为公钥，可以任意公开，破解 RSA 最直接（亦或是暴力）的方法就是分解整数 N，然后计算欧拉函数 φ(n) = (p-1) (q-1)，再通过 d e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥 (N, d) 通过 m = pow(c,d,N) 解密明文。

RSA常用攻击方法

模数N相关攻击

直接分解N

• yafu

p，q 差值太大或者太小，适用 Fermat 或 Pollard rho 法分解

使用方法：

打开 yafu-x64.exe。

最常用的命令是 factor(n)，将n值分解。

使用 yafu 的时候遇到 mismatched parens：

这是因为在命令行里不支持过长的位数，所以我们只要把n的值从文件中去读取即可。

新建一个文件 pcat.txt，内容里写上 n 的值，如：

注意：最后面一定要换行，不然会出现 eof; done processing batchfile

然后运行命令为：

yafu-x64 "factor(@)" -batchfile pcat.txt

输出的结果在 factor.txt 里。

• factordb网站：N 比特位数 768 或更高，在线网站会存储一些已分解成功的 N。

两个N不互素

通过欧几里德算法求 N1 和 N2 的最大公约数 gmpy2.gcd(n1, n2)，即求得 N 的任意一个因子 p。

同N，不同e加密同明文m

通过扩展欧几里德算法求出满足 se1 + te2 = 1 mod N 的 s 和 t，再结合对应的密文 c1 和 c2 求得明文 m。

gcd, s, t = gmpy2.gcdext(e1, e2)
m = gmpy2.powmod(c1, s, N) * gmpy2.powmod(c2, t, N) % N

Return of Coppersmith’s attack攻击

素数生成有漏洞，不够随机，实际上的生成方式是用 p = k * M + (65537 ^ a % M) 生成的，其中 M 为前 x 个素数乘积。

素数的生成算法不安全，攻击方法由论文可知。

https://crocs.fi.muni.cz/public/papers/rsa_ccs17

#p,q=k*M+(65537**a %M)

# Hardcoded parameters for efficiency
# Found using params.py
param = \
{
  512: {
    "n": 39,
    "a_max": 62,
    "k_max": 37,
    "M": 0x924cba6ae99dfa084537facc54948df0c23da044d8cabe0edd75bc6,
    "M_prime": 0x1b3e6c9433a7735fa5fc479ffe4027e13bea,
    "m": 5,
    "t": 6,
    "c_a": 0x80000
  },
  1024: {
    "n": 71,
    "a_max": 134,
    "k_max": 37,
    "M": 0x7923ba25d1263232812ac930e9683ac0b02180c32bae1d77aa950c4a18a4e660db8cc90384a394940593408f192de1a05e1b61673ac499416088382,
    "M_prime": 0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e,
    "m": 4,
    "t": 5,
    "c_a": 0x40000000
  },
  2048: {
    "n": 126,
    "a_max": 434,
    "k_max": 53,
    "M": 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6,
    "M_prime": 0x16928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6,
    "m": 7,
    "t": 8,
    "c_a": 0x400000000
  }
}

# https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
def coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX):
    """
    Coppersmith revisited by Howgrave-Graham

    finds a solution if:
    * b|N, b >= N^beta , 0 < beta <= 1
    * |x| < XX
    """
    #
    # init
    #
    dd = pol.degree()
    nn = dd * mm + tt

    #
    # checks
    #
    if not 0 < beta <= 1 :
        raise ValueError("beta should belongs in (0, 1]")

    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")


    #
    # Coppersmith revisited algo for univariate
    #

    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()

    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * N**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)

    # construct lattice B
    BB = Matrix(ZZ, nn)

    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]

    # LLL
    BB = BB.LLL(early_red=True, use_siegel=True)

    # transform shortest vector in polynomial
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii

    # factor polynomial
    potential_roots = new_pol.roots()

    return [i[0] for i in potential_roots]

# Top level of the attack, feeds the queue for the workers
def roca(N):

  # Key is not always of perfect size, infer from size
  keylength = int(log(N, 2))
  if keylength < 1000 :
    keylength = 512
  elif  keylength < 2000 :
    keylength = 1024
  elif keylength < 4000 :
    keylength = 2048
  else:
    keylength = 4096

  # bruteforce
  M_prime = param[keylength]['M_prime']
  c_prime = discrete_log(N, Mod(65537, M_prime))
  ord_prime = Zmod(M_prime)(65537).multiplicative_order()
  top = (c_prime + ord_prime)/2
  beta = 0.5
  mm = param[keylength]['m']
  tt = param[keylength]['t']

  XX = int((2*pow(N, beta)) / M_prime)

  # Bruteforce until p, q are found
  a_prime = floor(c_prime/2)
  while a_prime < top:

      # Construct polynomial
      m_inv = int(inverse_mod(M_prime, N))
      k_tmp = int(pow(65537, a_prime, M_prime))
      known_part_pol = int(k_tmp * m_inv)
      F = PolynomialRing(Zmod(N), implementation='NTL', names=('x',))
      (x,) = F._first_ngens(1)
      pol = x + known_part_pol

      # Get roots of polynomial using coppersmith
      roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)

      # Check if roots are p, q
      for root in roots:
        factor1 = k_tmp + abs(root) * M_prime
        if mod(N, factor1) == 0:
          factor2 = N // factor1
          return int(factor1), int(factor2)
      a_prime += 1


#N = p*q
N=15518961041625074876182404585394098781487141059285455927024321276783831122168745076359780343078011216480587575072479784829258678691739
print ("[+] Factoring %i" % N)

factor1, factor2 = roca(N)

print ("[+] Found factors of N:")
print ("[+] p =" , factor1)
print ("[+] q =" , factor2)

公钥指数e相关攻击

e很小且明文m比较小

以 e = 3 为例

m 较小的情况下，从小到大枚举 k，依次开 e 次方根，直到开出整数为止。

while 1:
  res = gmpy2.iroot(c + i * n, 3)
  if(res[1] == True):
     m = res[0]
     print(binascii.unhexlify(hex(m)[2:].strip("L")))
     break
  print "i=" + str(i)
  i = i + 1

e与模数N的一个或多个素数因子的欧拉函数不互素

N 可以直接分解，但由于 e 与一个或多个素数因子的欧拉函数不互素，而 e d - k phi(N) = 1 有解的充要条件是 gcd(e, phi(N)) = 1，因此无法直接通过扩展欧几里德算法求模反元素 d。

e=2，Rabin加密解密算法

破解 RSA 的关键即在于大整数的分解，只要 n 被成功分解，就能够破译。而 Rabin 密码体制是对 RSA 的一种修正。

1. Rabin 密码体制对于同一密文，可能有两个以上对应的明文
2. 破译该密码体制同样等价于对大整数的分解，RSA 中选取的公钥 e 满足 $1<e<\varphi(n)$
3. ，而 Rabin 中则选取 e = 2

密钥的产生:

1. 随机选择两个大素数 p，q，通常选取 p，q $\equiv 3(mod \quad4)$

2. 密钥为p，q

3. 公钥n=p*q

4. 明文：m，密文：c

5. 加密：$c \equiv m^2 \quad mod \quad n$

6. 解密过程如下：

   1. $m_p=c^{\frac{p+1}{4}}mod \quad p$

      $m_q=c^{\frac{q+1}{4}}mod \quad q$

   2. 使用扩展欧几里得算法得到 $y_p\space和\space y_q$ ，使得 $y_p·p+y_q·q=1$

   3. 利用中国剩余定理得到

      $x_1=(y_p·p·m_q+y_q·q·m_p) mod \quad n$

      $x_2=n-x_1$

      $x_3=(y_p·p·m_q-y_q·q·m_p) mod \quad n$

      $x_4=n-x_3$

      明文为该四个数中的一个。

解密脚本：

import gmpy2

def n2s(x):
    return hex(x)[2:].decode("hex")

c = 
p = 
q = 
n = p*q
c_p = pow(c,(p+1)/4,p)
c_q = pow(c,(q+1)/4,q)
a = gmpy2.invert(p,q)
b = gmpy2.invert(q,p)
x = (b*q*c_p+a*p*c_q)%n
y = (b*q*c_p-a*p*c_q)%n

print n2s(x)
print n2s(n-x)
print n2s(y)
print n2s(n-y)

e=prime * 2^k，Rsabin（hitcon-2015）

素数因子较小，RSA?（0ctf-2016）

通过以下工具计算：x^e = c mod p 可能的根 x，即为明文 m 对素数因子 p 的余数，依次求出 m 对所有素数因子的余数，再利用中国剩余定理 CRT 即可求得明文 m。

两组e与各自的N的欧拉函数均不互素，AzureRSA（高校运维赛eis-2018）

已知：两组N不互素，通过gcd可以求得共同素数因子p，进而求得q1，q2。由于：

$gmpy2.gcd(e1, (p-1))=14$

$gmpy2.gcd(e1, (q1-1)) = 2 $

$gmpy2.gcd(e2, (p-1)) = 14 $

$gmpy2.gcd(e2, (q2-1)) = 2$

因此，可以利用 q1，q2，求得：m^2 对于 q1，q2 的模，进而通过中国剩余定理CRT求得 m^2 对于 q1 * q2 的模，由于所求的值刚好可以开平方，否则需要通过 Rabin 解密法求明文m：

dq1 = gmpy2.invert(e1/2, q1 - 1)
dq2 = gmpy2.invert(e2/2, q2 - 1)
cq1 = gmpy2.powmod(c1, dq1, q1)
cq2 = gmpy2.powmod(c2, dq2, q2)
m2 = libnum.solve_crt([cq1, cq2], [q1, q2])
m = gmpy2.iroot(m2, 2)
if m[1]: # if not True, need to use Rabin to cal m
  print libnum.n2s(m[0])

e=3，模数N相同，且明文存在线性关系m1=a*m2+b mod N

def getM2(a, b, c1, c2, n):
    a3 = pow(a,3,n)
    b3 = pow(b,3,n)
    first = c1 - a3 * c2 + 2 * b3
    first = first % n
    second = 3 * b * (a3 * c2 - b3)
    second = second % n
    third = second * gmpy2.invert(first, n)
    third = third % n
    fourth = (third + b) * gmpy2.invert(a,n)
    return fourth % n
m = getM2(a, b, c1, c2, n) - padding2
print libnum.n2s(m)

e 不为 3 时，利用 Coppersmith’s short-pad attack，即 padding 过短引起的攻击:

https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage

def franklinReiter(n,e,r,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (X + r)^e - c2
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])

def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

def CoppersmithShortPadAttack(e,n,C1,C2,eps=1/30):
    import binascii
    P.<x,y> = PolynomialRing(ZZ)
    ZmodN = Zmod(n)
    g1 = x^e - C1
    g2 = (x+y)^e - C2
    res = g1.resultant(g2)
    P.<y> = PolynomialRing(ZmodN)
    rres = 0
    for i in range(len(res.coefficients())):
        rres += res.coefficients()[i]*(y^(res.exponents()[i][1]))

    diff = rres.small_roots(epsilon=eps)
    recoveredM1 = franklinReiter(n,e,diff[0],C1,C2)
    print(recoveredM1)
    print("Message is the following hex, but potentially missing some zeroes in the binary from the right end")
    print(hex(recoveredM1))
    print("Message is one of:")
    for i in range(8):
        msg = hex(Integer(recoveredM1*pow(2,i)))
        if(len(msg)%2 == 1):
            msg = '0' + msg
        if(msg[:2]=='0x'):
            msg = msg[:2]
        print(binascii.unhexlify(msg))

def testCoppersmithShortPadAttack(eps=1/25):
    from Crypto.PublicKey import RSA
    import random
    import math
    import binascii
    M = "flag{This_Msg_Is_2_1337}"
    M = int(binascii.hexlify(M),16)
    e = 3
    nBitSize =  8192
    key = RSA.generate(nBitSize)
    m = int(math.floor(nBitSize/(e*e))) - 400
    assert (m < nBitSize - len(bin(M)[2:]))
    r1 = random.randint(1,pow(2,m))
    r2 = random.randint(r1,pow(2,m))
    M1 = pow(2,m)*M + r1
    M2 = pow(2,m)*M + r2
    C1 = Integer(pow(M1,e,key.n))
    C2 = Integer(pow(M2,e,key.n))
    CoppersmithShortPadAttack(e,key.n,C1,C2,eps)

def testFranklinReiter():
    p = random_prime(2^512)
    q = random_prime(2^512)
    n = p * q 
    e = 11
    m = randint(0, n) 
    r = randint(0, n) 
    c1 = pow(m + 0, e, n)
    c2 = pow(m + r, e, n)
    print(m)
    recoveredM = franklinReiter(n,e,r,c1,c2)
    print(recoveredM)
    assert recoveredM==m
    print("They are equal!")
    return True

Wiener_attack

假如 p 大于 q 而小于 2q（这是一个很经常的情况）而 $d \lt \frac{1}{3} × N ^{\frac{1}{4}} $，那么从 N 和 e 可以很有效地推算出 d。

from __future__ import print_function
import libnum

def continued_fractions_expansion(numerator,denominator):#(e,N)
	result=[] 
	divident = numerator % denominator
	quotient = numerator / denominator
	result.append(quotient) 
	while divident != 0:
		numerator = numerator - quotient * denominator 
		tmp = denominator
		denominator = numerator
		numerator = tmp
		divident = numerator % denominator
		quotient = numerator / denominator
		result.append(quotient) 
	return result
 
def convergents(expansion):
	convergents=[(expansion[0], 1)]
	for i in range(1, len(expansion)):
		numerator = 1
		denominator = expansion[i]
		for j in range(i - 1, -1, -1):
			numerator += expansion[j] * denominator
			if j==0:
				break
			tmp = denominator
			denominator = numerator
			numerator = tmp
		convergents.append((numerator, denominator)) #(k,d)
	return convergents
 
def newtonSqrt(n):
	approx = n / 2
	better = (approx + n / approx) / 2
	while better != approx:
	    approx = better
	    better = (approx + n / approx) / 2
	return approx
 
def wiener_attack(cons, e, N):
	for cs in cons:
		k,d = cs
		if k == 0:
			continue
		phi_N = (e * d - 1) / k
		a = 1
		b = -((N - phi_N) + 1)
		c = N
		delta = b * b - 4 * a * c
		if delta <= 0:
			continue
		x1 = (newtonSqrt(delta) - b)/(2 * a)
		x2 = -(newtonSqrt(delta) + b)/(2 * a)
		if x1 * x2 == N:
			return [x1, x2, k, d]

if __name__ == "__main__":
    n = 
    e = 
    c = 
    expansion = continued_fractions_expansion(e, n)
    cons = convergents(expansion)
    p, q, k, d = wiener_attack(cons, e, n)
    m = pow(c, d, n)
    print(libnum.n2s(m))

Boneh and Durfee attack

d 过大，$d \gt \frac{1}{3} × N ^{\frac{1}{4}} $
那么可以尝试Boneh and Durfee attack

低加密指数广播攻击

以 e = 3 为例，3组不同的模数 N1，N2，N3 互素（如果不互素，可以通过欧几里德算法求最大公约数直接得到 p），则有：

C1 = me mod n1

C2 = me mod n2

C3 = me mod n3

import binascii,gmpy2

def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M / m) * gmpy2.invert(M / m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M
    
e=0x3
m=gmpy2.iroot(CRT(n, c), e)[0]

e非素数

• e 非素数，e 和 phi 不互素

  e = 12
  p = 58380004430307803367806996460773123603790305789098384488952056206615768274527
  q = 81859526975720060649380098193671612801200505029127076539457680155487669622867
  ciphertext = 206087215323690202467878926681944491769659156726458690815919286163630886447291570510196171585626143608988384615185921752409380788006476576337410136447460
  
  算出的m转化成字符串

  exp：

  import gmpy2
  import libnum
  from Crypto.Util.number import *
  
  e = 12
  p = 58380004430307803367806996460773123603790305789098384488952056206615768274527
  q = 81859526975720060649380098193671612801200505029127076539457680155487669622867
  n=p*q
  c = 206087215323690202467878926681944491769659156726458690815919286163630886447291570510196171585626143608988384615185921752409380788006476576337410136447460
  phi = (p-1)*(q-1)
  d4 = libnum.invmod(3,phi)
  m4 = pow(c,d4,n)
  print m4
  m = gmpy2.iroot(m4,4)[0]
  print(m)
  print(long_to_bytes(m))

• e1 和 e2 不互素

  e1:0x33240
  
  e2:0x3e4f
  
  n:0x9439682bf1b4ab48c43c524778c579cc844b60872275725c1dc893b5bcb358b9f136e4dab2a06318bb0c80e202a14bc54ea334519bec023934e01e9378abf329893f3870979e9f2f2be8fff4df931216a77007a2509f49f697bf286285e97fac5dc6e4a164b5c2cc430887b18136437ba67777bda05aafdeaf918221c812b4c7d1665238f84ab0fab7a77fcae92a0596e58343be7a8e6e75a5017c63a67eb11964970659cd6110e9ec6502288e9e443d86229ef2364dfecb63e2d90993a75356854eb874797340eece1b19974e86bee07019610467d44ec595e04af02b574a97fa98bdb2e779871c804219cab715f4a80fef7f8fb52251d86077560b39c1c2a1
  
  c1:0x7c7f315a3ebbe305c1ad8bd2f73b1bb8e300912b6b8ba1b331ac2419d3da5a9a605fd62915c11f8921c450525d2efda7d48f1e503041498f4f0676760b43c770ff2968bd942c7ef95e401dd7facbd4e5404a0ed3ad96ae505f87c4e12439a2da636f047d84b1256c0e363f63373732cbaf24bda22d931d001dcca124f5a19f9e28608ebd90161e728b782eb67deeba4cc81b6df4e7ee29a156f51a0e5148618c6e81c31a91036c982debd1897e6f3c1e5e248789c933a4bf30d0721a18ab8708d827858b77c1a020764550a7fe2ebd48b6848d9c4d211fd853b7a02a859fa0c72160675d832c94e0e43355363a2166b3d41b8137100c18841e34ff52786867d
  
  c2:0xf3a8b9b739196ba270c8896bd3806e9907fca2592d28385ef24afadc2a408b7942214dad5b9e14808ab988fb15fbd93e725edcc0509ab0dd1656557019ae93c38031d2a7c84895ee3da1150eda04cd2815ee3debaa7c2651b62639f785f6cabf83f93bf3cce7778ab369631ea6145438c3cd4d93d6f2759be3cc187651a33b3cc4c3b477604477143c32dfff62461fdfd9f8aa879257489bbf977417ce0fbe89e3f2464475624aafef57dd9ea60339793c69b53ca71d745d626f45e6a7beb9fcbd9d1a259433d36139345b7bb4f392e78f1b5be0d2c56ad50767ee851fac670946356b3c05d0605bf243b89c7e683cc75030b71633632fb95c84075201352d6
  
  c1=pow(m, e1, n)
  c2=pow(m, e2, n)

  exp：

  s1, s2, tmp = libnum.xgcd(e1, e2)
  if s1 < 0:
      s1 = - s1
      c1 = gmpy2.invert(c1, n)
  elif s2 < 0:
      s2 = - s2
      c2 = gmpy2.invert(c2, n)
  m = pow(c1, s1, n) * pow(c2, s2, n) % n
  m = 211655262573966881062823795220179644607412162371069
  print gmpy.root(m,3)[0]

Coppersmith相关攻击

Coppersmith定理指出在一个 e 阶的 mod n 多项式 f(x) 中，如果有一个根小于 n^1/e，就可以运用一个 O(log n) 的算法求出这些根。

Coppersmith’s short-pad attack

明文padding长度太短，小于 $floor(nBitSize/(e^2))$

Hastad’s Broadcast Attack with Linear Padding

相同 e，e 组不同模数 N 加密明文 m 的线性关系，

$cArray[i] = pow(aArray[i]*msg + bArray[i],e,nArray[i])$

当 aArray[i] = 1，bArray[i] = 0 时，即为低加密指数广播攻击。

Stereotyped messages攻击

至少已知明文 m 的 ceil(nBitSize*(1-1.0/e)) 位，即知道明文的高位。

如：N.bit_length() = 2048，e = 3，则至少需要已知：$ceil(2048*(1-1.0/3)) = 1366$位明文

$pol = ((message + ZmodN((pow(2,unknownEndBitIndex)))*x)^e) - c$

当 unknownEndBitIndex = 0 时，即为明文最后字符未知的情况。

e = 0x3
b=0x666c6167206973203a746573743132313131313131313131313133343536000000000000000000
n = 0xf85539597ee444f3fcad07142ecf6eaae5320301244a7cedc50b2beed7e60ffa11ccf28c1a590fb81346fb16b0cecd046a1f63f0bf93185c109b8c93068ec02f
c=0xa75c3c8a19ed9c911d851917e442a8e7b425e4b7f92205ca532a2ab0f5abe6cb86d164cc61374877f9e88e7bca606b43c79f1d59deadfcc68c3db52e5fc42f0
kbits=72 #未知低位位数
PR.<x> = PolynomialRing(Zmod(n))
f = (x + b) ^ e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0]
print "x: %s" %hex(int(x0))

Partial Key Exposure Attack

已知密钥 d 的低位 d0，d0 位数大于 nBitSize / 4。

sage 脚本：

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()
    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p

if __name__ == '__main__':
    n =0x56a8f8cbc72ff68e67c72718bd16d7e98150aea08780f6c4f532d20ca3c92a0fb07c959e008cbcbeac744854bc4203eb9b2996e9cf630133bc38952a2c17c27d 
    e = 0x3
    d = 0x594b6c9631c4987f588399f22466b51fc48ed449b8aae0309b5736ef0b741893
    beta = 0.5
    epsilon = beta^2/7

    nbits = n.nbits()
    kbits = 255
    d0 = d & (2^kbits-1)
    print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    print hex(d)
    print hex(inverse_mod(e, (p-1)*(q-1)))

Partial Key Recovery Attack

已知密钥 d 的低位 d0，d0 位数大于 nBitSize / 2

Factoring with high bits known攻击

题目给出p的高位，给出n，e，c

该后门算法依赖于Coppersmith partial information attack算法, sage实现该算法。

p = 0xd7e990dec6585656512c841ac932edaf048184bac5ebf9967000000000000000
n = 0xb50193dc86a450971312d72cc8794a1d3f4977bcd1584a20c31350ac70365644074c0fb50b090f38d39beb366babd784d6555d6de3be54dad3e87a93a703abdd

kbits = 60
PR.<x> = PolynomialRing(Zmod(n))
f = x + p
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print "x: %s" %hex(int(x0))
p = p+x0
print "p: ", hex(int(p))
assert n % p == 0
q = n/int(p)
print "q: ", hex(int(q))
#其中kbit是未知的p的低位位数
#x0为求出来的p低位

其他条件相关攻击

已知p，q其他等式

已知 p + q = s，根据一元二次方程：a = 1，b = -s，c = N，可解得：

p = long((-b + gmpy2.isqrt(b ** 2 - 4*a*c))/2L) 

dp&dq泄露

$dp = d \space mod \space(p - 1)$

$dq = d \space mod \space (q - 1)$

这种参数是为了让解密的时候更快速产生的(CRT)。

仅给出 p，q，dp，dq，c，不给公钥 e；

解密：

inv = gmpy2.invert(q, p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)
m = (((mp - mq) * inv) % p) * q + mq

dp泄露

给出公钥n,e以及dp

求解私钥d脚本:

def getd(n,e,dp):
  for i in range(1,e):
     if (dp*e-1)%i == 0:
       if n%(((dp*e-1)/i)+1)==0:
         p=((dp*e-1)/i)+1
         phi = (p-1)*(q-1)
         d = gmpy2.invert(e,phi)%phi
         return d

多素数因子

公钥 n 由多个素数因子组成。

分解整数网站

2020 国赛初赛的 RSA 要求分解 n 得到多个素因子，利用 fermat attack。（分解次数10e级别，额……）

费马小定理

1. 已知d其他等式，以2为明文，构造p的倍数，使之与N共模

   已知：k = (p - r) * d，构造如下：

   tmp = pow(2, e * k + r - 1, n) - 1
   p = libnum.gcd(tmp, n)

2. 利用 pow(p + q, e1, N ), pow(p + e1, q, N) 构造 p 的倍数，使之与 Ｎ 共模

   $c_1 = pow(p + q, e_1, N ), c_2 =pow(p + e_1, q, N),已知c_1,c_2,e_1,N,求p,q$

   • 整理$c_1$

     $c_1 =(p+q)^{e_1} \mod n$

     $c_1=(p+q)^{e_1}-kpq$

     $c_1 \mod q = (p \mod q + q \mod q)^{e_1} \mod q - (kpq \mod q)$

     $c_1 = p^{e_1} \mod q$

     $c1 = p^{e_1}-kq$

   • 整理$c_2$

     $c_2=(p+e_1)^q \mod N$

     $c_2=(p+e_1)^q -kpq$

     $c_2 \mod q = (p \mod q + e_1 \mod q)^q \mod q - (kpq \mod q)$

     $其中p \mod q + e_1 \mod q =(p+e_1) \mod q ，且根据费马小定理，a^p ≡ a (\mod p) ，得$

     $c_2=(p+e_1) \mod q$

     $c_2=p+e_1-kq$

     $c_2-e_1=p-kq$

   • 结合$c_1 、c_2$

     $c1 = p^{e_1}-kq $ ①

     $c_2-e_1=p-kq$

     $(c_2-e_1)^{e_1}=p^{e_1}+…+(k-q)^{e_1}$ ②

     ② - ① => $(c_2-e_1)^{e_1}-c_1=tkq$

     $有 pow((c_2-e_1),e_1,N)=(c_2-e_1)^{e_1}$

     $所以：gcd(pow((c_2-e_1),e_1,N))-c_1,N)=q$

   k = pow(c2 - e1, e1, N)
   q = gmpy2.gcd(k - c1, N)

next_prime

原理：根据素数定理，素数的平均间隔为：$x/π(x)≈lnx$，因此常见的下一个素数比当前素数大一点，一般不会超过1500。

可以用 yafu 分解。

LHY

已知：

p = gmpy.next_prime(x ** 3 + y ** 3)
q = gmpy.next_prime(x ** 2 * y + y ** 2 * x)
x = 2 * y

因此：

p = next_prime(9 * y ** 3) = 9 * y ** 3 + a
q = next_prime(6 * y ** 3) = 6 * y ** 3 + b

根据素数定理，a，b 很小，因此 n ≈ 54 * y ** 6。可以通过以下方法求得 p：

• 得知 y 的上界，而 y 的下界也不会离上界太远，可以利用二分查找法来寻找满足条件的 y，p 和 q

• 由于 a，b 很小，y 如果改变，y ^ 3 改变的值将远大于 a，b 的影响，因此可以认为 y = iroot(y / 54, 6)，进而爆破 a（从1到1500）求得：

  p = next_prime(9 * y ** 3) = (9 * y **3 + a) % n = 0

  ，比直接求 next_prime 速度快些

• p = 9 * y ** 3 + a，由于 a，b 很小，可以认为 p 高位大部分 bit 已知，通过 Coppersmith 攻击可恢复不确定的低位。

import gmpy2
tmp = 

print gmpy2.iroot(tmp, 2018)
print gmpy2.iroot(tmp - 1, 2018)
print gmpy2.iroot(tmp - 2, 2018)

n = 
y = 
y = gmpy2.next_prime(y)

enc = 

end = gmpy2.iroot(n / 54, 6)[0]
beg = end - 2000000

mid = 1
while beg < end:
    mid = (beg + end) / 2
    if gmpy2.is_prime(mid) != 1:
        mid = gmpy2.next_prime(mid)
    p = gmpy2.next_prime(9 * mid**3)
    q = gmpy2.next_prime(6 * mid**3)
    n1 = p * q
    if n1 == n:
        print p, q
        phin = (p - 1) * (q - 1)
        d = gmpy2.invert(0x10001, phin)
        m = gmpy2.powmod(enc, d, n)
        print hex(m)[2:].strip('L').decode('hex')
        print 'ok'
        exit(0)
    elif n1 < n:
        beg = mid
    else:
        end = mid
    print beg, end

已知nextprime(p)*nexprime(q)的值

$npnq = nextprime(p)nextprime(q) = (p + x) (q + y)$

联立 $p * q = N$，得：

$yp^2 + (n + xy - npnq)p + x n = 0$

爆破 x 和 y（从1到1500）解一元二次方程。

import gmpy2
n = 
m = 
def quadratic(a,b,c):
    ga=gmpy2.mpz(a)
    gb=gmpy2.mpz(b)
    gc=gmpy2.mpz(c)
    delta=gb**2-4*ga*gc
    if delta<=0 or a==0:
        return 0
    tmp=gmpy2.iroot(delta,2)
    if tmp[1]==True:
        x1 = (-gb + tmp[0]) / (2*ga)
        x2 = (-gb - tmp[0]) / (2 * ga)
        if x1>0 and n%x1==0:
            print x1
            return x1
        if x2>0 and n%x2==0:
            print x2
            return x2
    return 0
def main():
    for x in range(1500):
        print x
        for y in range(1500):
            a=y
            b=x * y - m + n
            c=x * n
            if quadratic(a,b,c)!=0:
                return 0
main()

LLL算法

通过三组 e 和 N（d 相同），我们可以将三组 e 和 N 进行基础矩阵的构造，使用 lattice 还原技术中的 LLL 可以求得该矩阵的最小基向量 b。

详细可见格密码。

实现参考论文：Factoring Polynomials with Rational Coefficients

sage 脚本：

e0=
n0=
c0=
e1=
n1=
c1=
e2=
n2=
c2=
M1 = Matrix(4,4,0)
temp = int(n1)
M = isqrt(max(n0,n1,n2))
M1[0,0] = M
M1[0,1] = e0
M1[0,2] = e1
M1[0,3] = e2
M1[1,1] = -n0
M1[2,2] = -n1
M1[3,3] = -n2
BL = M1.LLL()
print (BL)
d = abs(BL[0,0])/M
print(d)

题目：SCTF-RSA

e 和 phi(n) 不互素

正常情况下的 RSA 都要求 e 和 phi(n) 要互素，不过也有一些 e 和 phi(n) 有很小的公约数的题目，这些题目基本都能通过计算 e 对 phi(n)的逆元 d 来求解。

然而当 e 和 p - 1 或 q - 1 的最大公约数就是 e 本身，也就是说 e | p - 1，需要对 c 开 e 次方根才行。

可以将同余方程

$$m^e \equiv c \quad (\text{mod}\ n)$$

化成

$$\begin{aligned} m^e &\equiv c \quad (\text{mod}\ p)\newline m^e &\equiv c \quad (\text{mod}\ q) \end{aligned}$$

然后分别在 GF(p) 和 GF(q) 上对 c 开 e 次方根，再用 CRT 组合一下即可得到在 mod n 下的解。

做法

• 先用 Adleman-Manders-Miller rth Root Extraction Method 在 GF(p) 和 GF(q) 上对 c 开 e 次根，分别得到一个解。
• 然后去找到所有的 e 个 primitive nth root of 1，乘以上面那个解，得到所有的 e 个解。
• 再用 CRT 对 GF(p) 和 GF(q) 上的两组 e 个解组合成 mod n 下的解，可以得到 e ^ 2 个 mod n 的解。最后能通过 check 的即为 flag。

sage 脚本：

import random
import time

def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - dicreat_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

c = 
p = 
q = 
e =
cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print mps, mqs

def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    if h.decode('hex').startswith('NCTF'):
        print(h.decode('hex'))
        return True
    else:
        return False

start = time.time()
print('Start CRT...')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
    print(time.time() - start)

end = time.time()
print("Finished in {} seconds.".format(end - start))

选择密文攻击

任意给定密文，系统返回明文，选择密文攻击。

Decryptor（noxCTF-2018）

已知n，c，e，向服务器发送密文得到明文。

构造一个 x，使得：

$k \equiv x^ec \text{ } mod \text{ } n$

然后我们把 k 发送过去，得到：

$k^d \equiv (x^ec)^d \text{ } mod \text{ } n$

$ k^d \equiv xc^d \text{ } mod \text{ } n $

$ k^dx^-1 \equiv m \text{ } mod \text{ } n $

我们构造 x=2 即可。

x = hex((pow(2,e,N)*c)%N)[2:-1]
#put x
#get tmp
libnum.n2s((tmp*gmpy2.invert(2,N))%N)

LSB Oracle Attack

适用情况：可以选择密文并泄露最低位。

在一次RSA加密中，明文为 m，模数为 n，加密指数为 e，密文为 c。

我们可以构造出 $c’=(2^ec) \mod n=(2^em^e) \mod n=(2m)^e \mod n$

因为 m 的两倍可能大于 n，所以经过解密得到的明文是 $m’=(2m) \mod n $。

我们还能够知道 $m’ $的最低位lsb 是1还是0。
因为 n 是奇数，而 2m 是偶数，所以如果 lsb 是0，说明 (2m) % n ​是偶数，没有超过 n，即 m < n / 2.0，反之则 m > n / 2.0 。
举个例子就能明白 2 % 3 = 2 是偶数，而 4 % 3 = 1 是奇数。
以此类推，构造密文 $c” = (4^ec) \space mod \space n ，使其解密后为 \space m” = (4m) \mod n$ ，判断 m” 的奇偶性可以知道 m 和 n / 4 的大小关系。
所以我们就有了一个二分算法，可以在对数时间内将m的范围逼近到一个足够狭窄的空间。

def brute_flag(encrypted_flag, n, e):

    flag_count = n_count = 1
    flag_lower_bound = 0
    flag_upper_bound = n
    ciphertext = encrypted_flag
    mult = 1
    while flag_upper_bound > flag_lower_bound + 1:
        sh.recvuntil("input your option:")
        sh.sendline("D")
        ciphertext = (ciphertext * pow(2, e, n)) % n
        flag_count *= 2
        n_count = n_count * 2 - 1
        print("bit = %d" % mult)
        mult += 1
        sh.recvuntil("Your encrypted message:")
        sh.sendline(str(ciphertext))
        data=sh.recvline()[:-1]
        if(data=='The plain of your decrypted message is even!'):
            flag_upper_bound = n * n_count / flag_count
        else:
            flag_lower_bound = n * n_count / flag_count
            n_count += 1
    return flag_upper_bound