RSA

常用工具

  • 分解大素数

    factordb http://www.factordb.com

    yafu($p,q$相差过大或过小yafu可分解成功)

    sage divisors(n)(小素数)

  • 在线sage环境:https://sagecell.sagemath.org/

  • Openssl

    解析加密密钥:

    openssl rsa -pubin -text -modulus -in pub.key

    生成解密密钥:

    python rsatool.py -f PEM -o key.key -p 1 -q 1 -e 1

    openssl rsautl -decrypt -inkey key.pem -in flag.enc -out flag

    openssl rsautl -decrypt -oaep -inkey key.pem -in flag.enc -out flag (OAEP方式)

    脚本生成解密密钥:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # coding=utf-8
    import math
    import sys
    from Crypto.PublicKey import RSA

    keypair = RSA.generate(1024)
    keypair.p =
    keypair.q =
    keypair.e =
    keypair.n = keypair.p * keypair.q
    Qn = long((keypair.p - 1) * (keypair.q - 1))

    i = 1
    while (True):
    x = (Qn * i) + 1
    if (x % keypair.e == 0):
    keypair.d = x / keypair.e
    break
    i += 1
    private = open('private.pem', 'w')
    private.write(keypair.exportKey())
    private.close()
  • 脚本集

RSA套路

  1. 给p,q,e,c

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    import gmpy2 as gp
    import binascii
    p =
    q =
    e =
    c =
    n = p*q
    phi = (p-1)*(q-1)
    d = gp.invert(e,phi)
    m = pow(c,d,n)
    print(m)
    print(bytes.fromhex(hex(m)[2:]))

  2. 给n,e,dp,c

    $dp\equiv d \pmod {(p-1)}$

    $\because dp\cdot e\equiv d\cdot e\equiv 1 \pmod {(p-1)}$

    $\therefore dp\cdot e-1=k\cdot (p-1)$

    $\therefore (dp\cdot e-1)\cdot d\cdot e=k’\cdot (p-1),\quad k’=k\cdot d\cdot e \\\Leftrightarrow d\cdot e=-k’\cdot (p-1)+dp\cdot e\cdot d\cdot e\equiv 1 \pmod{\varphi(n)}\\\Leftrightarrow -k’\cdot (p-1)+dp\cdot e\equiv 1\pmod{\varphi(n)}$

    $\therefore k_{1}\cdot (p-1)+dp\cdot e-1=k_{2}\cdot (p-1)\cdot (q-1)\\\Leftrightarrow (p-1)\cdot (k_{2}\cdot (q-1)-k_{1})+1=dp\cdot e$

    $\because dp<p-1\quad \therefore (k_{2}\cdot (q-1)-k_{1})\in (0, e)$

    $\therefore$ 遍历 $(1, e)$,当同时满足 $(dp\cdot e-1)\bmod i==0$ 和 $n\bmod((dp\cdot e-1)//i+1)==0$ 时,$N$ 成功分解。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    import gmpy2 as gp

    e =
    n =
    dp =
    c =

    for x in range(1, e):
    if(e*dp%x==1):
    p=(e*dp-1)//x+1
    if(n%p!=0):
    continue
    q=n//p
    phin=(p-1)*(q-1)
    d=gp.invert(e, phin)
    m=gp.powmod(c, d, n)
    if(len(hex(m)[2:])%2==1):
    continue
    print('--------------')
    print(m)
    print(hex(m)[2:])
    print(bytes.fromhex(hex(m)[2:]))
    • 变种1:给 $p,e,d_p,c,b$,其中 $n=p^bq$。

      Hensel lifting for Takagi’s scheme(p.189):

      Hensel_lifting_for_Takagi's_scheme

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      from Crypto.Util.number import *
      import gmpy2
      p =
      dp =
      c =
      b =
      e =
      mp1 = pow(c, dp, p)
      mp = pow(c, dp - 1, p)
      for i in range(1, b - 2):
      x = pow(c - pow(mp1, e), 1, p**(i + 1))
      y = pow(x * mp * (gmpy2.invert(e, p)), 1, p**(i + 1))
      mp1 = mp1 + y
      print(long_to_bytes(mp1))
    • 变种2:给 $n,e,dp_0,c,k$,其中 $dp_0$ 为 $dp$ 高 $(n\text{bits}-k)$ 位,即 $dp_0=dp>>k$。

      (Coppersmith攻击,已知dp高位攻击)

      $e\cdot dp \equiv e\cdot d\equiv 1 \pmod {(p-1)} \\\Leftrightarrow e \cdot dp=k(p-1)+1=kp-k+1 \\\Leftrightarrow e\cdot dp+k-1 \equiv 0 \pmod p$

      $\because dp<p-1$,$\therefore k<e$

      $\therefore e\cdot (dp_0<<k+x)+k-1 \equiv 0 \pmod p$

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      #Sage
      dp0 =
      e =
      n =

      F.<x> = PolynomialRing(Zmod(n))
      d = inverse_mod(e, n)
      for k in range(1, e):
      f = (secret << 200) + x + (k - 1) * d
      x0 = f.small_roots(X=2 ** (200 + 1), beta=0.44, epsilon=1/32)
      if len(x0) != 0:
      dp = x0[0] + (secret << 200)
      for i in range(2, e):
      p = (e * Integer(dp) - 1 + i) // i
      if n % p == 0:
      break
      if p < 0:
      continue
      else:
      print('k = ',k)
      print('p = ',p)
      print('dp = ',dp)
      break

  3. 给p,q,dp,dq,c

    $dp=d \bmod (p-1)$,$dq=d \bmod (q-1)$

    $\because d=k_{1}(p-1)+dp=k_{2}(q-1)+dq\\\Leftrightarrow k_{1}(p-1)=(dq-dp)+k_{2}(q-1)\\\Leftrightarrow k_{1}\frac{p-1}{\gcd(p-1,q-1)}=\frac{dq-dp}{\gcd(p-1,q-1)}+k_{2}\frac{q-1}{\gcd(p-1,q-1)}\\\Rightarrow k_{1}\frac{p-1}{\gcd(p-1,q-1)}\equiv\frac{dq-dp}{\gcd(p-1,q-1)} \pmod {\frac{q-1}{\gcd(p-1,q-1)}}\\\Leftrightarrow k_{1}\equiv \text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{dq-dp}{\gcd(p-1,q-1)} \pmod {\frac{q-1}{\gcd(p-1,q-1)}}$

    将 $k_{1}=k_{3}\frac{q-1}{\gcd(p-1,q-1)}+\text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{dq-dp}{\gcd(p-1,q-1)}$

    代入 $d=k_{1}(p-1)+dp$

    $d=k_{3}\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}+\text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{\gcd(p-1,q-1)}+dp\\\Rightarrow d\equiv \text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{\gcd(p-1,q-1)}+dp \pmod{\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}}$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    import gmpy2 as gp

    p =
    q =
    dp =
    dq =
    c =

    n = p*q
    phin = (p-1)*(q-1)
    dd = gp.gcd(p-1, q-1)
    d=(dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq
    print(d)

    m = gp.powmod(c, d, n)
    print('-------------------')
    print(m)
    print(hex(m)[2:])
    print(bytes.fromhex(hex(m)[2:]))

  4. 低解密指数攻击/低私钥指数攻击(e长度较大,d小,Wiener Attack)

    适用情况:已知 $N,e$,且 $e$ 过大或过小。

    $\varphi(n) = (p-1)(q-1)=pq - (p + q) + 1=N - (p + q) + 1$

    $\because p, q$ 非常大,$\therefore\,pq\gg p+q$, $\therefore\varphi(n)\approx N$

    $\because ed\equiv1\,mod\,\varphi(n)$,$\therefore ed-1=k\varphi(n)$,这个式子两边同除 $d\varphi(n)$ 可得:

    $\cfrac{e}{\varphi(n)}-\cfrac{k}{d}=\cfrac{1}{d\varphi(n)}$

    $\because \varphi(n)\approx N$,$\therefore \cfrac{e}{N}-\cfrac{k}{d}=\cfrac{1}{d\varphi(n)}$,同样 $d\varphi(n)$ 是一个很大的数,所以 $\cfrac{e}{N}$ 略大于 $\cfrac{k}{d}$

    因为 $e$ 和 $N$ 是知道的,所以计算出 $\cfrac{e}{N}$ 后,比它略小的 $\cfrac{k}{d}$ ,可以通过计算 $\cfrac{e}{N}$ 的连分数展开,依次算出这个分数每一个渐进分数,由于 $\cfrac{e}{N}$ 略大于 $\cfrac{k}{d}$,Wiener 证明了,该攻击能精确的覆盖 $\cfrac{k}{d}$。

    在 $e$ 过大或过小的情况下,可使用算法从 $e$ 中快速推断出 $d$ 的值。可以解决 $q<p<2q,d<\cfrac{1}{3}N^{\frac{1}{4}}$ 的问题。

    RSAWienerHacker工具:https://github.com/pablocelayes/rsa-wiener-attack

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #脚本1(带工具)
    #python2
    import RSAwienerHacker
    n =
    e =
    d = RSAwienerHacker.hack_RSA(e,n)
    if d:
    print(d)
    import hashlib
    flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
    print flag
    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
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    #脚本2
    #sage
    def rational_to_contfrac(x,y):
    # Converts a rational x/y fraction into a list of partial quotients [a0, ..., an]
    a = x // y
    pquotients = [a]
    while a * y != x:
    x, y = y, x - a * y
    a = x // y
    pquotients.append(a)
    return pquotients

    def convergents_from_contfrac(frac):
    # computes the list of convergents using the list of partial quotients
    convs = [];
    for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))
    return convs

    def contfrac_to_rational (frac):
    # Converts a finite continued fraction [a0, ..., an] to an x/y rational.
    if len(frac) == 0: return (0,1)
    num = frac[-1]
    denom = 1
    for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num
    return (num, denom)

    n =
    e =
    c =

    def egcd(a, b):
    if a == 0: return (b, 0, 1)
    g, x, y = egcd(b % a, a)
    return (g, y - (b // a) * x, x)

    def mod_inv(a, m):
    g, x, _ = egcd(a, m)
    return (x + m) % m

    def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
    x = y
    y = (x + n // x) // 2
    return x

    def crack_rsa(e, n):
    frac = rational_to_contfrac(e, n)
    convergents = convergents_from_contfrac(frac)

    for (k, d) in convergents:
    if k != 0 and (e * d - 1) % k == 0:
    phi = (e * d - 1) // k
    s = n - phi + 1
    # check if x*x - s*x + n = 0 has integer roots
    D = s * s - 4 * n
    if D >= 0:
    sq = isqrt(D)
    if sq * sq == D and (s + sq) % 2 == 0: return d

    d = crack_rsa(e, n)
    m = hex(pow(c, d, n))[2:]
    print(bytes.fromhex(m))
    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
    #脚本3
    from Crypto.Util.number import long_to_bytes
    e =
    n =
    c =

    #将分数x/y展开为连分数的形式
    def transform(x,y):
    arr=[]
    while y:
    arr+=[x//y]
    x,y=y,x%y
    return arr

    #求解渐进分数
    def sub_fraction(k):
    x=0
    y=1
    for i in k[::-1]:
    x,y=y,x+i*y
    return (y,x)
    data=transform(e,n)

    for x in range(1,len(data)+1):
    data1=data[:x]
    d = sub_fraction(data1)[1]
    m = pow(c,d,n)
    flag = long_to_bytes(m)
    if b'flag{' in flag:
    print(flag)
    break
    • 变种1:$\cfrac{N_1}{N_2}<\cfrac{q_1}{q_2}<1$

      参考:2020年羊城杯 - RRRRRRRSA

      Paper: https://eprint.iacr.org/2015/399.pdf

      尝试对 $\cfrac{N_1}{N_2}$ 进行连分数展开并求其各项渐进分数,记为 $\cfrac{t_i}{s_i}$ 并验证 $N_1\% {t_k}==0$ 是否成立,如果成立,那么 $q_1=t_k,q_2=s_k$。

      连分数逼近

      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
      def transform(x,y):	   #使用辗转相除将分数x/y转为连分数的形式
      res=[]
      while y:
      res.append(x//y)
      x,y=y,x%y
      return res

      def continued_fraction(sub_res):
      numerator,denominator=1,0
      for i in sub_res[::-1]: #从sublist的后面往前循环
      denominator,numerator=numerator,i*numerator+denominator
      return denominator,numerator #得到渐进分数的分母和分子,并返回

      #求解每个渐进分数
      def sub_fraction(x,y):
      res=transform(x,y)
      res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res))))) #将连分数的结果逐一截取以求渐进分数
      return res

      def wienerAttack(n1,n2):
      for (q2,q1) in sub_fraction(n1,n2): #用一个for循环来注意试探n1/n2的连续函数的渐进分数,直到找到一个满足条件的渐进分数
      if q1==0: #可能会出现连分数的第一个为0的情况,排除
      continue
      if n1%q1==0 and q1!=1: #成立条件
      return (q1,q2)
      print("该方法不适用")

      N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
      N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
      print(wienerAttack(N1,N2))

  5. 低加密指数广播攻击(Hastad攻击)

    适用情况: $n,c$ 不同,$m,e$ 相同。一般会是 $e=k$,然后给 $k$ 组数据。

    如果一个用户使用同一个加密指数 e 加密了同一个密文,并发送给了其他 e 个用户。那么就会产生广播攻击。这一攻击由 Håstad 提出。

    使用不同的模数 $n$,相同的公钥指数 $e$ 加密相同的信息,就会得到多个 $m^e \equiv c_i \pmod {n_i}$,将 $m^e$ 视为一个整体 $M$,这就是典型的中国剩余定理适用情况。容易求得 $m^e$ 的值,当 $e$ 较小时直接开 $e$ 方即可,可使用gmpy2.iroot(M,e) 方法。

    更一般情况($k$ 组数据的 $N$ 不同)见15。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #sage
    def chinese_remainder(modulus, remainders):
    Sum = 0
    prod = reduce(lambda a, b: a*b, modulus)
    for m_i, r_i in zip(modulus, remainders):
    p = prod // m_i
    Sum += r_i * (inverse_mod(p,m_i)*p)
    return Sum % prod
    chinese_remainder([3,5,7],[2,3,2]) #23
    1
    2
    #sage
    crt([2,3,2],[3,5,7])

  6. 共模攻击(n,m相同,c,e不同)

    当$n$不变的情况下,知道$n,e_1,e_2,c_1,c_2$可以在不知道$d_1,d_2$的情况下,解出$m$。

    首先假设$e_1,e_2$互质,

    即 $\gcd(e_1,e_2)=1$

    此时则有 $e_1s_1+e_2s_2 = 1$

    式中,$s_1,s_2$皆为整数,但是一正一负。

    通过扩展欧几里德算法,我们可以得到该式子的一组解$(s_1,s_2)$,假设$s_1$为正数,$s_2$为负数。

    因为 $c_1 = m^{e_1}\bmod n, c_2 = m^{e_2}\bmod n$

    所以 $(c_1^{s_1}c_2^{s_2})\bmod n = ((m^{e_1}\bmod n)^{s_1}(m^{e_2}\bmod n)^{s_2})\bmod n$

    根据模运算性质,可以化简为 $(c_1^{s_1}c_2^{s_2})\bmod n = ((m^{e_1})^{s_1}(m^{e_2})^{s_2})\bmod n$

    即 $(c_1^{s_1}c_2^{s_2})\bmod n = (m^{e_1s_1+e_2s_2})\bmod n$

    又前面提到 $e_1s_1+e_2s_2 = 1$

    所以 $(c_1^{s_1}c_2^{s_2})\bmod n = m\bmod n$

    即 $c_1^{s_1}c_2^{s_2}= m$

    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
    import gmpy2 as gp
    def egcd(a, b):
    if a == 0:
    return (b, 0, 1)
    else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

    n =
    c1 =
    c2 =
    e1 =
    e2 =
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1<0:
    s1 = - s1
    c1 = gp.invert(c1, n)
    elif s2<0:
    s2 = - s2
    c2 = gp.invert(c2, n)

    m = pow(c1,s1,n)*pow(c2,s2,n) % n
    print(hex(m)[2:])
    print(bytes.fromhex(hex(m)[2:]))

  7. e,m相同,多个n中存在两个n有GCD(模不互素)

    适用情况:存在两个或更多模数 ,且 $\gcd(n_1,n_2)\ne 1$ 。

    多个模数 $n$ 共用质数,则可以很容易利用欧几里得算法求得他们的质因数之一 $\gcd(n_1,n_2)$,然后这个最大公约数可用于分解模数分别得到对应的 $p$ 和 $q$,即可进行解密。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    import gmpy2 as gp

    n=[]
    for i in n:
    for j in n:
    if (i<>j):
    pub_p=gp.gcdext(i,j)
    if (pub_p[0]<>1)&(i>j):
    print(i)
    print(j)
    print(pub_p[0])
    a=i,p=pub_p[0]
    q=a//p
    p =
    q =
    e =
    c =
    n = p*q
    phi = (p-1) * (q-1)
    d = gp.invert(e, phi)
    m = pow(c, d, n)
    print(hex(m)[2:])
    print(bytes.fromhex(hex(m)[2:]))

  8. Rabin加密

    适用情况:$e=2$ 。

    一般先通过其他方法分解得到 $p,q$,然后解密。

    函数返回四个数,这其中只有一个是我们想要的明文,需要通过其他方式验证。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    import gmpy2

    def rabin_decrypt(c, p, q, e=2):
    n = p * q
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    yp = gmpy2.invert(p, q)
    yq = gmpy2.invert(q, p)
    r = (yp * p * mq + yq * q * mp) % n
    rr = n - r
    s = (yp * p * mq - yq * q * mp) % n
    ss = n - s
    return (r, rr, s, ss)

    c =
    p =
    q =
    m = rabin_decrypt(c,p,q)
    for i in range(4):
    try:
    print(bytes.fromhex(hex(m[i])[2:]))
    except:
    pass

  9. Boneh and Durfee attack

    $e$ 非常大接近于$N$,即 $d$ 较小时。与低解密指数攻击类似,比低解密指数攻击(Wiener Attack)更强,可以解决$\cfrac{1}{3}N^{\frac{1}{4}} \leq d \leq N^{0.292}$的问题。

    参考 https://github.com/mimoo/RSA-and-LLL-attacks

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

  10. Coppersmith攻击(已知p的高位攻击)

    知道 $p$ 的高位为 $p$ 的位数的约$\frac12$时即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #Sage
    from sage.all import *
    n =
    p4 =
    #p去0的剩余位
    e =
    pbits = 1024
    kbits = pbits - p4.nbits()
    print(p4.nbits())
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    roots = f.small_roots(X=2^kbits, beta=0.4)
    #经过以上一些函数处理后,n和p已经被转化为10进制
    if roots:
    p = p4+int(roots[0])
    print("n: "+str(n))
    print("p: "+str(p))
    print("q: "+str(n//p))

  11. Coppersmith攻击(已知明文高位攻击,部分m)

    这里我们假设我们首先加密了消息 $m$,如下

    $C\equiv m^e \bmod N$

    并且我们假设我们知道消息 $m$ 的很大的一部分 $m_0$,即 $m=m_0+x$,但是我们不知道 $x$。那么我们就有可能通过该方法进行恢复消息。这里我们不知道的 $x$ 其实就是多项式的根,需要满足 Coppersmith 的约束。

    可以参考 https://github.com/mimoo/RSA-and-LLL-attacks

    $e$ 足够小,且部分明文泄露时,可以采用Coppersmith单变量模等式的攻击,如下:

    $c=m^{e}\bmod n=(mbar+x_{0})^{e}\bmod n$,其中 $mbar = (m >> k\text{bits}) << k\text{bits}$

    当 $\vert x_{0}\vert\leq N^{\frac{1}{e}}$ 时,可以在 $\log N$ 和 $e$ 的多项式时间内求出 $x_0$。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #Sage
    n =
    e =
    c =
    mbar =
    kbits =
    beta = 1
    nbits = n.nbits()
    print("upper {} bits of {} bits is given".format(nbits - kbits, nbits))
    PR.<x> = PolynomialRing(Zmod(n))
    f = (mbar + x)^e - c
    x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n
    print("m:", mbar + x0)

  12. Coppersmith攻击(已知d的低位攻击,部分d)

    如果知道 $d$ 的低位,低位约为 $n$ 的位数的 $\frac14$ ($\frac{n.n\text{bits}()}{4}$)就可以恢复 $d$。

    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
    #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.4) # find root < 2^(nbits//2-kbits) with factor >= n^0.4
    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 range(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 and p != 1:
    return p
    if __name__ == '__main__':
    n =
    e =
    c =
    d0 =
    beta = 0.5
    nbits = n.nbits()
    kbits = d0.nbits()
    print("lower %d bits (of %d bits) is given" % (kbits, nbits))
    p = int(find_p(d0, kbits, e, n))
    print("found p: %d" % p)
    q = n//int(p)
    print("d:", inverse_mod(e, (p-1)*(q-1)))
    • 变种1:$n=p\cdot q\cdot r$,已知 $n,p,d=\text{inv}(e,\varphi(n)),e,c$

      $k(p-1)\rightarrow k’,qr\rightarrow n’,q+r\rightarrow s$

      $ed_{0}\equiv 1+k’(n’-s+1) \pmod {2^{d_{0}.n\text{bits}()}}\quad (1)$

      $q^{2}-sq+n’\equiv 0 \pmod {2^{d_{0}.n\text{bits}()}}\quad (2)$

      联立可得,$(ed_{0}-1-k’n’-k’)q+k’q^{2}+k’n’\equiv 0 \pmod {2^{d_{0}.n\text{bits}()}}$

      即求解同余方程可得 $q$ 的低 $size(d0)$ 位,本来是个partial d的coppersmith问题,但因为step1求解同余方程后得到的 $q$ 已是完整的 $q$,所以无需后续的coppersmith。

      参考:Dragon CTF 2019 - RSA Chained

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      #Sage
      def find_p(d0, kbits, e, n, p):
      X = var('X')
      for k in range(1, e + 1):
      k_dot = k * (p - 1)
      results = solve_mod([e * d0 * X - k_dot * X * (n - X + 1) + k_dot * n == X], 2^kbits)
      for x in results:
      q = ZZ(x[0])
      if n % q == 0:
      return q
      return None

      n = ... # q * r
      p =
      c =
      d0 =
      e =
      kbits = d0.nbits()
      q = find_p(d0, kbits, e, n, p)
      phi = (p - 1) * (q - 1) * (n // q - 1)
      d = inverse_mod(e, phi)
      print(bytes.fromhex(hex(pow(c, d, p * n))[2:]))

  13. Coppersmith攻击(已知N一个因子的高位,部分p)

    当我们知道一个公钥中模数 $N$ 的一个因子的较高位时,我们就有一定几率来分解 $N$。

    参考 https://github.com/mimoo/RSA-and-LLL-attacks

    关注下面的代码:

    1
    2
    3
    4
    5
    6
    7
    beta = 0.5
    dd = f.degree()
    epsilon = beta / 7
    mm = ceil(beta**2 / (dd * epsilon))
    tt = floor(dd * mm * ((1/beta) - 1))
    XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000
    roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

    其中,

    • 必须满足 $q\ge N^{beta}$,所以这里给出了 $beta=0.5$,显然两个因数中必然有一个是大于的。
    • XX 是 $f(x)=q′+x$ 在模 $q$ 意义下的根的上界,自然我们可以选择调整它,这里其实也表明了我们已知的 $q′$ 与因数 $q$ 之间可能的差距。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #Sage
    n =
    e =
    c =
    pbar =
    kbits =
    print("upper %d bits (of %d bits) is given" % (pbar.nbits()-kbits, pbar.nbits()))
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + pbar
    x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4
    p = x0 + pbar
    print("p:", p)
    q = n // int(p)
    d = inverse_mod(e, (p-1)*(q-1))
    print("m:", pow(c, d, n))

    注:

    sage的small_root传参X不能过大,需自行判断阈值并调整(如果X过大,即使存在X内的解,也无法求出);

    比如 $p$ 的低位泄露时因为不确定缺失高位的具体比特数,所以要在 $2^{\frac{n.n\text{bits}()}{2}−k\text{bits}}$ 附近作X的阈值估计;

    无法确定拿到的 $p$ 是否大于 $q$,所以对 $\beta=0.5$ 进行调整至 $0.4$。

  14. 目前在大部分消息加密之前都会进行 padding,但是如果 padding 的长度过短($m \in (0,\lfloor\frac{n.n\text{bits}()}{e^2}\rfloor]$),也有可能被很容易地攻击。

    这里所谓 padding 过短,其实就是对应的多项式的根会过小。

    当 Alice 使用同一公钥对两个具有某种线性关系的消息 $M_1$ 与 $M_2$ 进行加密,并将加密后的消息 $C_1$,$C_2$ 发送给了 Bob 时,我们就可能可以获得对应的消息 $M_1$ 与 $M_2$ 。这里我们假设模数为 $N$,两者之间的线性关系如下:

    $M_1 \equiv f(M_2) \bmod N$

    其中 $f$ 为一个线性函数,比如说 $f=ax+b$。

    在具有较小错误概率下的情况下,其复杂度为 $O(e\log^2N)$。

    这一攻击由 Franklin与Reiter 提出。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #脚本1
    #Sage
    import binascii
    def attack(c1, c2, b, e, n):
    PR.<x>=PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+b)^e - c2

    def gcd(g1, g2):
    while g2:
    g1, g2 = g2, g1 % g2
    return g1.monic()
    return -gcd(g1, g2)[0]
    c1 =
    c2 =
    n =
    e=
    a = 1
    id1 = 1
    id2 = 2
    b = id2 - id1
    m1 = attack(c1,c2, b,e,n)
    print(binascii.unhexlify("%x" % int(m1 - id1)))
    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
    36
    #脚本2
    #Sage
    def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+y)^e - c2
    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4
    return diff
    def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
    while g2:
    g1, g2 = g2, g1 % g2
    return g1.monic()
    return -gcd(g1, g2)[0]
    if __name__ == '__main__':
    n =
    e =
    c1 =
    c2 =
    diff = short_pad_attack(c1, c2, e, n)
    print("difference of two messages is %d" % diff)
    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)
    print("m2:", m1 + diff)

  15. RSA Hastad Attack with non-linear padding and different public keys(带非线性padding和不同公钥的广播攻击)

    适用情况:$m$ 经 $k$ 次非线性padding处理后,分别用 $k$ 组 $(N_i,e_i)$ 加密后得 $k$ 组 $c_i$。

    参考:2020年羊城杯 - Invitation

    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
    36
    37
    38
    39
    40
    41
    #Sage
    #e=3, padding: m²+(3^431)k
    def linearPaddingHastads(cArray,nArray,aArray,bArray,eArray,eps):
    if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == len(eArray)):
    for i in range(4):
    cArray[i] = Integer(cArray[i])
    nArray[i] = Integer(nArray[i])
    aArray[i] = Integer(aArray[i])
    bArray[i] = Integer(bArray[i])
    eArray[i] = Integer(eArray[i])
    TArray = [-1]*4
    for i in range(4):
    arrayToCRT = [0]*4
    arrayToCRT[i] = 1
    TArray[i] = crt(arrayToCRT,nArray)
    P.<x> = PolynomialRing(Zmod(prod(nArray)))
    gArray = [-1]*4
    for i in range(4):
    gArray[i] = TArray[i]*(pow(aArray[i]*x**2 + bArray[i],eArray[i]) - cArray[i])
    g = sum(gArray)
    g = g.monic()
    roots = g.small_roots(epsilon=eps)
    if(len(roots)== 0):
    print("No Solutions found!")
    return -1
    return roots
    else:
    print("Input error!")

    def nonLinearPadding():
    eArr = [3 for i in range(4)]
    nArr = [146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391,65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029,126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901,75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471]
    cArr = [129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823,8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214,25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080,9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346]
    aArr = [1 for i in range(4)]
    bArr = [i * 3 ** 431 for i in [3,8,10,11]]
    msg = linearPaddingHastads(cArr,nArr,aArr,bArr,eArr,eps=1/20)
    for i in msg:
    print(bytes.fromhex(hex(i)[2:]))

    if __name__ == '__main__':
    nonLinearPadding()

  16. Least Significant Bit Oracle Attack (LSB Oracle Attack / Parity Oracle)

    适用情况:可以选择密文并泄露明文的最低位(奇偶性)。

    假设存在一个oracle,能对给定密文进行解密并给出对应明文的奇偶信息,则我们只需要 $\log(N)$ 次就能解密任意密文。

    在一次RSA加密中,明文为 $m$,模数为 $n$,加密指数为 $e$,密文为 $c$。我们可以构造出

    $c’=((2^e)\cdot c)\%n=((2^e)\cdot(m^e))\%n=((2\cdot m)^e)\%n$ ,

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

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

    更多信息可参考:RSA Least-Significant-Bit Oracle AttackRSA least significant bit oracle attack

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    import decimal
    def oracle():
    return lsb == 'odd'

    def partial(c, e, n):
    k = n.bit_length()
    decimal.getcontext().prec = k # for 'precise enough' floats
    lo = decimal.Decimal(0)
    hi = decimal.Decimal(n)
    for i in range(k):
    if not oracle(c):
    hi = (lo + hi) / 2
    else:
    lo = (lo + hi) / 2
    c = (c * pow(2, e, n)) % n
    # print i, int(hi - lo)
    return int(hi)

  17. Common Private Exponent(共私钥指数攻击,d相同)

    加密用同样的私钥并且私钥比较短,从而导致了加密系统被破解。

    假定:

    $\begin{cases} e_1d=1+k_1\varphi(N_1)\\ e_2d=1+k_2\varphi(N_2)\\{\vdots}\\e_rd=1+k_r\varphi(N_r) \end{cases}$

    其中,$N_1 \lt N_2 \lt \cdots \lt N_r \lt 2N_1$。

    构造格:

    $B_r=\begin{bmatrix}{M}&{e_1}&{e_2}&{\cdots}&{e_{r}}\\
    {0}&{-N_1}&{0}&{\cdots}&{0}\\{0}&{0}&{-N_2}&{\cdots}&{0}\\{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\\{0}&{0}&{0}&{\cdots}&{-N_r}\\\end{bmatrix}$

    其中 $M=\lfloor N_r^{\frac{1}{2}} \rfloor$。

    再利用LLL算法进行规约得到 $\vert b_1\vert=Md$,则 $d=\cfrac{\vert b_1 \vert}{M}$,从而解密密文得到明文。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    ###Sage###
    from gmpy2 import *
    e0=
    n0=
    c0=
    e1=
    n1=
    c1=
    e2=
    n2=
    c2=

    M=iroot(int(n2),int(2))[0]
    a=[0]*4
    a[0]=[M,e0,e1,e2]
    a[1]=[0,-n0,0,0]
    a[2]=[0,0,-n1,0]
    a[3]=[0,0,0,-n2]

    Mat = matrix(ZZ,a)
    Mat_LLL=Mat.LLL()
    d = abs(Mat_LLL[0][0])/M
    print(bytes.fromhex(hex(pow(c1,int(d),int(n1)))[2:]))

  18. 多组低解密指数攻击

    适用情况:2-4组 $e$,且 $d$ 较小

    • 给定2组

      $g=gcd(p-1,q-1),\lambda(n)=\frac{\varphi(n)}{g},s=1-p-q$

      且有 $ed-k\lambda(n)=1$,得到 $edg-kn=g+ks\quad (1)$

      设 $e_1$ 对应 $k_1$,$e_2$ 对应 $k_2$,则有 $k_{2}d_{1}e{1}-k_{1}d_{2}e_{2}=k_{2}-k_{1}\quad (2)$

      由(1)(2)有:

      $\left\{ \begin{matrix} e_{1}d_{1}g-k_{1}n=g+k_{1}s\\ k_{2}d_{1}e{1}-k_{1}d_{2}e_{2}=k_{2}-k_{1}\\ e_{1}e_{2}d_{1}d_{2}g_{2}-e_{1}d_{1}gk_{2}n-e_{2}d_{2}gk_{1}n+k_{1}k_{2}n^{2}=(g+k_{1}s)(g+k_{2}s) \end{matrix} \right.$

      上述等式组也可表示为

      $bL_2\\=[k_{1}k_{2},k_{2}d_{1}g,k_{1}d_{2}g,d_{1}d_{2}g^{2}]\cdot\left[ \begin{matrix} n & -M_{1}n & 0 & n^{2}\\ 0 & M_{1}e_{1} & M_{2}e_{1} & -e_{1}n\\ 0 & 0 & -M_{2}e_{2} & -e_{2}n\\ 0 & 0 & 0 & e_{1}e_{2} \end{matrix} \right]\\ =[k_{1}k_{2}n,M_{1}k_{2}(g+k_{1}s),M_{2}g(k_{2}-k_{1}),(g+k_{1}s)(g+k_{2}s)]$

      (其中 $M_{1}=n^{1/2},M_{2}=n^{1+\alpha_{2}},d\approx n^{\alpha_{2}}$)

      对部分参数进行上界估计,k上界近似于 $d\approx N^{\alpha_{2}}$, $|s|$ 上界 $\approx N^{1/2}$,$g$ 一般相对极小

      因此上面的矩阵表示 $BA=C$ 中,$C$ 的每个元的size都近似 $n^{1+2\alpha_{2}}$,所以 $|C|\approx 2\cdot n^{1+2\alpha_{2}}$

      $B$ 作为格基的格中,最短向量由Minkowski Bounds知 $\approx \sqrt{4}\det(B)^{1/4}\approx 2\cdot n^{(13/2+\alpha_{2})/4}$

      因此只要满足 $n^{1+2\alpha_{2}}<n^{(13/2+\alpha_{2})/4}$ 即可将问题转化为SVP($\alpha_{2}<\frac{5}{14}$)

      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
      #Sage
      n =
      e1 =
      e2 =
      c =

      from Crypto.Util.number import *

      for i in range(731, 682, -1):
      print(i)
      alpha2 = i / 2048
      M1 = round(n ^ 0.5)
      M2 = round(n ^ (1 + alpha2))
      A = Matrix(ZZ, [
      [n, -M1*n, 0, n^2],
      [0, M1*e1, -M2*e1, -e1*n],
      [0, 0, M2*e2, -e2*n],
      [0, 0, 0, e1*e2]
      ])
      AL = A.LLL()
      C = Matrix(ZZ, AL[0])
      B = A.solve_left(C)[0]
      phi1 = floor(e1 * B[1] / B[0])
      phi2 = floor(e2 * B[2] / B[0])
      d1 = inverse(e1, phi1)
      d2 = inverse(e2, phi2)
      m1 = long_to_bytes(pow(c, d1, n))
      m2 = long_to_bytes(pow(c, d2, n))
      if b"De1" in m1 or b"De1" in m2:
      print(m1)
      print(m2)
      break

      参考:De1CTF 2020 - easyRSA

    • 给定3组

      类似2组情况,其中

      $b=[k_1k_2k_3,d_1gk_2k_3,k_1d_2gk_3,d_1d_2g^2k_3,k_1k_2d_3g,k_1d_3g,k_2d_3g,d_1d_2d_3g^3]$

      $L_3=\left[\begin{matrix} 1-N & 0 & N^2 & 0 & 0 & 0 & -N^3\\ e_1 & -e_1 & -e_1N & -e & 0 & e_1N & e_1N^2\\ 0 & e_2 & -e_2N & 0 & e_2N & 0 & e_2N^2\\ 0 & 0 & e_1e_2 & 0 & -e_1e_2 & -e_1e_2 & -e_1e_2N\\ 0 & 0 & 0 & e_3 & -e_3N & -e_3N & e_3N^3\\ 0 & 0 & 0 & 0 & e_1e_3 & 0 & -e_1e_3N\\ 0 & 0 & 0 & 0 & 0 & e_2e_3 & -e_2e_3N\\ 0 & 0 & 0 & 0 & 0 & 0 & e_1e_2e_3 \end{matrix}\right] \times D$

      其中 $D={\rm diag}(N^{3/2},N,N^{(3/2)+\alpha_3},N^{1/2},N^{(3/2)+\alpha_3},N^{1+\alpha_3},N^{1+\alpha_3},1)$

      参考:3kCTF - RSA Textbook

    • 参考Paper

      Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice)

      Extending Wiener’s Attack in the Presence of Many Decrypting Exponents

  19. 多项式RSA

    在整数RSA原理基础上将多项式代入分析:

    在有限域上选取两个不可约多项式 $g(p),g(q)$,$g(n)=g(p) \cdot g(q)$,计算出 $g(n)$ 的欧拉函数 $\varphi(g(n))=\varphi$,

    选取一个整数 $e$ 作为公钥,$e$ 与 $\varphi$ 是互素的,那么对于明文 $g(m)$,加密过程为 $g(m)^e \equiv g(c) \pmod {g(n)}$,

    计算私钥 $d$ 满足 $ed \equiv 1 \pmod \varphi$,则 $g(c)^d \equiv (g(m)^e)^d \equiv g(m)^{ed} \equiv g(m)^{\varphi+1} \pmod {g(n)}$,

    同样考虑 $g(n)$ 与 $g(m)$ 互素,欧拉定理对于多项式亦成立,

    得到 $g(m)^{\varphi+1} \equiv g(m) \pmod {g(n)}$,所以 $g(c)^d \equiv g(m) \pmod {g(n)}$。

    显然RSA对于整数的体制可以适用于有限域上的多项式。

    ★注意:

    对于素数 $x$,$\varphi(x)=x-1$,但是对于不可约多项式 $g(x)$,$\varphi(g(x))=p^n-1$。(此 $p$ 为 $GF(p)$ 的模,此 $n$ 为多项式最高项次数)

    原因:

    由欧拉函数定义本身,欧拉函数是小于 $n$ 的所有与 $n$ 互质的数的个数。

    多项式的欧拉函数则类似,表示不高于 $g(x)$ 幂级的环内所有多项式中,与 $g(x)$ 无公因式(非1)的其他多项式的个数,所以每一个不高于 $g(x)$ 幂级的环内多项式(除了它自己)均满足此条件。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #脚本1
    #Sage
    #已知p,n,m^e
    p=
    P = PolynomialRing(Zmod(p), name = 'x')
    x = P.gen()
    e =
    n =
    c =

    #分解N
    q1, q2 = n.factor()
    q1, q2 = q1[0], q2[0]

    #求φ,注意求法,
    phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
    assert gcd(e, phi) == 1
    d = inverse_mod(e, phi)
    m = pow(c,d,n)

    #取多项式系数
    flag = bytes(m.coefficients())
    print("Flag: ", flag.decode())
    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
    #脚本2
    #Sage
    #已知p=2,n,e,c
    p =
    P = PolynomialRing(GF(p), name = 'x')
    x = P.gen()
    e =
    n =
    R.<a> = GF(2^2049)
    c = []

    q1, q2 = n.factor()
    q1, q2 = q1[0], q2[0]

    phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
    assert gcd(e, phi) == 1
    d = inverse_mod(e, phi)

    ans = ''
    for cc in c:
    cc = P(R.fetch_int(cc))
    m = pow(cc,d,n)
    m = R(P(m)).integer_representation()
    print(m)
    ans += chr(m)
    print(ans)

    参考:

    0ctf - babyrsa

    watevrCTF 2019 - Swedish RSA

    InCTF 2020 - PolyRSA

    Polynomial based RSA

  20. 其他特别情形

    • 多素数因子(Multi-prime RSA)

      $n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m} \\\Rightarrow \begin{eqnarray}\varphi(n) &=&\varphi(p_1^{k_1})\varphi(p_2^{k_2}) \cdots \varphi(p_m^{k_m}) \\ &=&(p_1^{k_1-1}\cdot(p_1-1))(p_2^{k_2-1}\cdot(p_2-1)) \cdots (p_m^{k_m-1}\cdot(p_m-1)) \end{eqnarray}$

    • next_prime()

      根据素数定理,素数的平均间隔为:$\cfrac{x}{\pi(x)} \approx \ln(x)$,因此常见的下一个素数比当前素数大一点,一般不会超过1500。

      • 变种1:$n=p \cdot q \cdot \text{next_prime}(p) \cdot \text{next_prime}(q)$

        费马因式分解

    • 给 e,p,c

      $c \equiv m^e \pmod n \\\Leftrightarrow c_1 \equiv c \pmod p \equiv m^e \pmod p$

      令 $ed_1 \equiv 1 \pmod {(p-1)}$,有 $m \equiv c^d \pmod n \equiv c_1^{d_1} \pmod p$。

    • 给 e,d,modinv(q,p),c

      已知:$p,q$ 同比特位数。

      令 $cf=q^{-1} \bmod p$,有 $q\cdot cf=1 \pmod p$。

      • $ed=1+k(p-1)(q-1)$,

        比较比特位数,$k$ 与 $e$ 同长,可爆破 $k$,得 $\varphi(n)=(p-1)(q-1)=\cfrac{ed-1}{k}$;

      • 上式 $\varphi(n) =(p-1)(q-1) \pmod p=-(q-1) \pmod p$,

        结合 $q\cdot cf=1 \pmod p$,即 $q\cdot cf-1=0 \pmod p$,

        联立:

        $\begin{eqnarray} \varphi(n)&=&(p-1)(q-1)\\&=&pq-p-q+1\\&=&n-p-q+1 \end{eqnarray}$

        $\begin{eqnarray} cf\cdot \varphi(n)&=&cf\cdot(n-p-q+1)\\&=&cf\cdot n-cf\cdot p-cf\cdot q+cf \end{eqnarray}$

        $\begin{eqnarray} cf\cdot \varphi(n) \bmod p&=&(cf\cdot n-cf\cdot p-cf\cdot q+cf) \bmod p\\&=&0-0-(cf\cdot q)+cf \bmod p\\&=&-1+cf \bmod p \end{eqnarray}$

        有 $1+cf\cdot \varphi(n)-cf=0\pmod p$,

        即$x=1+cf\cdot \varphi(n)-cf$ 能被 $p$ 整除;

      • 由费马小定理,存在 $r$ 满足 $r^{p-1}=1 \pmod p$,

        $\begin{eqnarray}r^{\varphi(n)}&=&(r^{(p-1)})^{(q-1)}\\&=&1^{(q-1)} \pmod p\\&=&1 \pmod p \end{eqnarray}$,

        因对于任意 $r,k_1,k_2$,当 $k_2$ 为 $k_1$ 因子时,$r \bmod k_2=(r \bmod k_1) \bmod k_2$,

        故 $r^{\varphi(n)} \bmod p=(r^{\varphi(n)} \bmod x) \bmod p=1 \bmod p=kp$,

        已知 $\varphi(n)$,由 $(r^{\varphi(n)} \bmod x) \bmod p=kp$ 可得到多组 $p$ 的乘积,计算 $\gcd$ 可得到 $p$;

      • 由 $q\cdot cf=1 \pmod p$ 求模逆可得 $q$,再用 $c$ 计算出 $m$。

        参考:TSG CTF 2020 - Modulus Amittendus

    • gcd(e,φ(n)) ≠ 1

      $\gcd(e,\varphi(n))\neq 1$ 时,$e$ 与 $\varphi(n)$ 不互素,

      $m^e \equiv (m^{\gcd(e,\varphi(n))})^{\frac{e}{\gcd(e,\varphi(n))}} \equiv c \pmod n$,计算 $\frac{e}{\gcd(e,\varphi(n))}$ 的模逆 $d’$,

      则 $c^{d’}\equiv m^{\gcd(e,\varphi(n))}\pmod n$。

      当 $\gcd(e,\varphi(n))$ 较小时,可以直接对 $c$ 开根,有两种情况:

      • $m^e = c<n$,这种情况直接对 $c$ 开 $e$ 次方即可;
      • $m^e = c>n$,这种情况需要在有限域下对 $c$ 开方,一般先计算 $c_p=c \bmod p$,$c_q=c \bmod q$,分别求出 $c_p,c_q$ 在 $c$ 下的 $e$ 次根(可能有多个),然后使用CRT遍历所有组合,分别check得出明文。

      当 $\gcd(e,\varphi(n))$ 较大时,求 $p,q$ 的 $e$ 次根步骤需要替换为一些有限域开根的高效算法(如AMM算法等)进行计算。

      参考:

      De1CTF2019 - Baby RSA

      0ctf 2016 - RSA?

    • e|(p-1), e|(q-1)

      上面的 $\gcd(e,\varphi(n))\neq 1$ 情况不针对 $\gcd(e,\varphi(n))= e$,这里对 $e\mid (p-1),e\mid (q-1)$ 的特殊情况进行讨论。

      解题思路即求解 $m \bmod p$ 和 $m \bmod q$ ,再通过CRT还原 $m \bmod n$。主要难点则是在 $\text{GF}(p)$ 上求 $e$ 次根。

      在有限域上求r-th root有两个常见算法(Adleman-Manders-Miller algorithm和Cipolla-Lehmer algorithm),Namhun Koo提出一种更具一般性的开根算法,且在 $s$ 足够小的时候更高效($r^{s}\mid (p-1),r^{s}\nmid (p-1)$)。

      参考NCTF 2019 - easyRSAAdleman-Manders-Miller rth Root Extraction Method

      本题则为 $e$ 和 $p-1$ (或 $q-1$)的最大公约数就是 $e$ 本身,也就是说 $e\mid (p-1)$,只有对 $c$ 开 $e$ 次方根才行。

      可以将同余方程 $m^e \equiv c \pmod n$ 化成

      $\begin{cases} m^e \equiv c \pmod p\\m^e \equiv c \pmod q \end{cases}$

      然后分别在 $\text{GF}(p)$ 和 $\text{GF}(q)$ 上对 $c$ 开 $e$ 次方根,再用CRT组合一下即可得到在 $\bmod n$ 下的解。

      问题是,如何在有限域内开根

      这里 $e$ 与 $p-1$ 和 $q-1$ 都不互素,不能简单地求个逆元就完事。

      这种情况下,开平方根可以用Tonelli–Shanks algorithmWiki说这个算法可以扩展到开n次方根

      在这篇paper里给出了具体的算法:Adleman-Manders-Miller rth Root Extraction Method

      这个算法只能开出一个根,实际上开 $e$ 次方,最多会有 $e$ 个根(这题的情况下有0x1337个根)。

      如何找到其他根?

      StackOverflow – Cube root modulo P 给出了方法。

      如何找到所有的primitive 0x1337th root of 1?

      StackExchange – Finding the n-th root of unity in a finite field 给出了方法。

      Exploit(以 e=0x1337​ 为例)

      • 先用Adleman-Manders-Miller rth Root Extraction Method在 $\text{GF}(p)$ 和 $\text{GF}(q)$ 上对 $c$ 开 $e$ 次方根,分别得到一个解。大概不到10秒。
      • 然后去找到所有的0x1336primitive nth root of 1,乘以上面那个解,得到所有的0x1337个解。大概1分钟。
      • 再用CRT对 $\text{GF}(p)$ 和 $\text{GF}(q)$ 上的两组0x1337个解组合成 $\bmod n$ 下的解,可以得到0x1337**2=24196561个 $\bmod n$ 的解。最后能通过check()的即为flag。大概十几分钟。
      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
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      #脚本1
      #Sage
      import random
      import time

      # About 3 seconds to run
      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 = - discrete_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 = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
      p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
      q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
      e = 0x1337
      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 bytes.fromhex(h).startswith(b'NCTF'):
      print(bytes.fromhex(h))
      return True
      else:
      return False


      # About 16 mins to run 0x1337^2 == 24196561 times CRT
      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))
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      #脚本2
      #Sage
      c = 346925245648012783854132941104554194717281878370806475831055718275298366664505658836564073456294047402009856656647760
      p = 21122913513992623721920275602985463699928507831138027
      q = 16471885912035642894544190467774867069446937372970845578732298073
      e = 239

      P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
      f=a^e-c
      mps=f.monic().roots()

      P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
      g=a^e-c
      mqs=g.monic().roots()

      for mpp in mps:
      x=mpp[0]
      for mqq in mqs:
      y=mqq[0]
      solution = hex(CRT_list([int(x), int(y)], [p, q]))[2:]
      if solution.startswith('666c'):
      print(solution)

    • SMUPE 问题(不同N,e加密线性关系明文)

      a system of univariate polynomial equations problem = 一元多项式方程组求解问题

      • 定义

        $k$ 是一个整数,$N$ 为满足RSA算法的模数,$\delta$ 是多项式的阶。有

        $N_i<N_{i+1},\delta_i \in N\quad(i=1,2,\cdots,k)$

        多项式方程组表示如下, 目的是求解 $x$:

        $\begin{cases} f_1(x)\equiv 0 \pmod {N_1}\\ f_2(x)\equiv 0 \pmod {N_2}\\{\vdots}\\f_k(x)\equiv 0 \pmod {N_k} \end{cases}$

      • 求解条件

        Alexander May, Maike Ritzenhofent提出一种求解方法,简单地说当多项式的阶 $\delta$ 满足以下情况时可解($\delta$ 是多项式的阶):

        $\sum\limits_{i=1}^k \cfrac{1}{\delta_i} \geq 1$

        具体描述:

        令 $(f_i,\delta_i,N_i) \quad(i=1,2,\cdots,k)$ 作为SMUPE问题的首一多项式组,

        定义 $M=\prod\limits_{i=1}^k N_i^{\frac{\delta}{\delta_i}},\delta=\text{lcm}(\delta_i) \quad (i=1,2,\cdots,k)$

        则SMUPE问题可以在 $O(\delta^6\cdot \log_2M)$ 复杂度解决。

      参考:2019红帽杯 - 精明的Alice

    • 反素数(emirp数)

      已知:$q=\text{reverse_x}(p)$,$\text{x}$ 为进制数。

      爆破思路类似RSA parity oracle。$p,q$ 是bit翻转关系,已知 $p$ 最低的 $k$ 位,则已知 $q$ 最高的 $k$ 位。

      假设已知 $k$ 位的 $p,q$,记为 $ph,qh$,利用不等式

      $ph\cdot qh\cdot 2^{1024-2k}<=n<(ph+1)\cdot(qh+1)\cdot 2^{1024-2k}$ ,

      逐位向低地址爆破,不断收缩不等式的范围,最终可求得 $n$ 值。

      参考:

      ASIS 2015 Finals: RSASR

      Midnight Sun CTF 2020 Quals

      RoarCTF 2020 - Reverse

      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
      #python2
      #x=10
      n = 6528060431134312098979986223024580864611046696815854430382374273411300418237131352745191078493977589108885811759425485490763751348287769344905469074809576433677010568815441304709680418296164156409562517530459274464091661561004894449297362571476259873657346997681362092440259333170797190642839587892066761627543
      def t(a, b, k):
      # sqrt(n) has 155 digits, so we need to figure out 77 digits on each side
      if k == 77:
      if a*b == n:
      print a, b
      return
      for i in xrange(10):
      for j in xrange(10):
      # we try to guess the last not-already-guessed digits of both primes
      a1 = a + i*(10**k) + j*(10**(154-k))
      b1 = b + j*(10**k) + i*(10**(154-k))
      if a1*b1 > n:
      # a1 and b1 are too large
      continue
      if (a1+(10**(154-k)))*(b1+(10**(154-k))) < n:
      # a1 and b1 are too small
      continue
      if ((a1*b1)%(10**(k+1))) != (n%(10**(k+1))):
      # The last digits of a1*b1 (which won't change later) doesn't match n
      continue
      # this a1 and b1 seem to be a possible match, try to guess remaining digits
      t(a1, b1, k+1)

      # the primes have odd number of digits (155), so we try all possible middle digits (it simplifies the code)
      for i in xrange(10):
      t(i*(10**77), i*(10**77), 0)

详细原理

二十年以来对 RSA 密码系统攻击综述

CTF Wiki - RSA

0xDktb’s Blog

RSA常见攻击方法

Cryptanalysis of RSA and It’s Variants