Crypto_牛客博客

Crypto

对称密码

分组密码

关键在于混乱、扩散和抗分析的设计

DES、AES等

序列密码

关键在于伪随机数的生成

RC4等

非对称密码

相关推荐资料：Introduction to Mathematical Cryptography

关键在于单向陷门函数的选取

基于整数分解

RSA等

RSA

预备数学知识：

相关推荐资料：华罗庚《数论导引》前四章

欧拉函数：

定义：在模n下，与n互素的整数的个数记作 $\phi(n)$

容易知道，对于素数p， $\phi(p) = p-1$ ，对于合数n， $\phi(n) = n\prod_{i=1}^{s} (1-\frac{1}{p_i})$ ，其中 $p_1,\dots,p_s$ 为n的所有素数因子

例子： $\phi(10) = 10 *\prod_{i=1}^{s} (1-\frac{1}{p_i}) = 10 * (1-\frac{1}{2})*(1-\frac{1}{5}) = 4$ ，即是 $1, 3, 7, 9$
欧拉定理：

定义：对于a，n，若 $gcd(a,n)=1$ ，则有 $a^{\phi(n)} \equiv 1\mod n$

例子： $gcd(3, 10) = 1, \phi(10) = 4, 3 ^ 4 = 81 \equiv 1 \mod 10$
模逆：

定义：在模n下，对于任意a，如果 $gcd(a, n)=1$ ，则存在b，使得 $a * b \equiv 1 \mod(n)$ ，称b为a在模n上的模逆

从代数的角度来看，b即是a在有限域n下乘法计算的逆元，可类比有理数域中的倒数

一般可以通过扩展欧几里得算法求模逆（对于 $a,n$ ，扩展欧几里得算法可以得到一组 $s,r$ ，使得 $s * a - r * n = gcd(a,n)$ ，当 $gcd(a,n) = 1$ 时，既有 $s * a = 1 + r * n$ ，则 $s * a \equiv1\mod n$ ，s即为a在模n上的模逆）

例子：3在模5下的模逆为2， $2 * 3\equiv 1 \mod 5$
指数：

定义：在模n下， $gcd(a,n) = 1$ ，则使得 $a^e \equiv 1 \mod n$ 的最小整数e为a对模n的指数，记作 $ord_n(a)$ ，如果a对模n的指数为 $\phi(n)$ ，则a称为模n的原根

原根的作用在于，给指数规定了一个集合，即指数层面的运算都是在模ord之下的

例子： $ord_{10}(3) = 4$ ，因为 $3 ^ 4= 81 \equiv 1 \mod 10$ ，由于 $\phi(10) = 4$ ，所以3为10的一个原根。

预备pyCrypto知识

# Crypto.Util.number
bytes_to_long() & long_to_bytes()
getPrime() & getStrongPrime()
inverse() & pow()

# gmpy2
iroot()
gcdext()
next_prime()

熟练掌握这些数学原理就可以做一些比赛的题了：

Cybercis2020 too_secure

题目中描述的魔改Pedersen加密步骤为：

图片说明

获取c的部分代码可描述为：

from Crypto.Util.number import *
from gmpy2 import gcd
import hashlib


def ascii_value(string):
    sum = 0
    for i in range(len(string)):
        sum += ord(string[i]) * (2 ** (8 * i))
    return sum


def get_c(x, r, g, p):
    G = pow(g, x, p)
    a = int(hashlib.sha512(long_to_bytes(G).rjust(128, b'\x00')).hexdigest().encode(), 16)
    _a = pow(a, a, p-1)
    h = pow(g, _a, p)
    c = (G * pow(h, r, p)) % p

    return c

题目的需求是需要对于已知信息 $m_1, m_2$ ， $m_1, r_1$ 的已加密信息 $c_1$ ，求出因子 $r_2$ ，使得 $m_2$ 通过 $r_2$ 加密出的 $c_2$ 与 $c_1$ 相同，即产生碰撞。

转化成数学语言：

对于待加密信息 $m_1$ ， $c_1 = g^{m_1} * h_1 ^ {r_1}$ ，注意到 $h_1 = g ^ {a_1}$ ，故 $c_1 = g^{m_1 + a_1 * r_1}$ ，欲碰撞信息 $m_2$ 的因子 $r_2$ 应满足： $c_2 = c_1$ ，即 $m_1 + a_1 * r_1 \equiv m_2 + a_2 * r_2 \mod \phi(p)$ ，由于题中提到， $ord_p{g} = q$ ，所以有 $m_1 + a_1 * r_1 \equiv m_2 + a_2 * r_2 \mod q$ ，故而 $r_2 \equiv (m_1 + a_1 * r_1 - m_2) * a_2^{-1} \mod q$ ，即可求出 $r_2$ ，原问题即解决，exp如下：

from Crypto.Util.number import *
from gmpy2 import gcd
import hashlib


def ascii_value(string):
    sum = 0
    for i in range(len(string)):
        sum += ord(string[i]) * (2 ** (8 * i))
    return sum


def get_h_a(x, g, p):
    G = pow(g, x, p)
    a = int(hashlib.sha512(long_to_bytes(G).rjust(128, b'\x00')).hexdigest().encode(), 16)
    _a = pow(a, a, p-1)
    h = pow(g, _a, p)

    return h, _a


def get_c(x, r, g, p):
    G = pow(g, x, p)
    a = int(hashlib.sha512(long_to_bytes(G).rjust(128, b'\x00')).hexdigest().encode(), 16)
    _a = pow(a, a, p-1)
    h = pow(g, _a, p)
    c = (G * pow(h, r, p)) % p

    return c


p = 12039102490128509125925019010000012423515617235219127649182470182570195018265927223
g = 10729072579307052184848302322451332192456229619044181105063011741516558110216720725
r1 = 31245182471
M1 = 'Hi! I am Vadim Davydov from ITMO University'
M2 = 'Transfer the points for easy task to this team'


q = 1039300813886545966418005631983853921163721828798787466771912919828750891
assert(pow(g, q, p) == 1)
assert(gcd(q, p-1) == q)

m1 = ascii_value(M1) % q
m2 = ascii_value(M2) % q

h1, a1 = get_h_a(m1, g, p)
h2, a2 = get_h_a(m2, g, p)

c1 = get_c(m1, r1, g, p)


para1 = a1 * r1
para2 = m2 - m1
para3 = para1 - para2
para4 = inverse(a2, q)


r2 = ((para3 * para4) % q)
c2 = get_c(m2, r2, g, p)

if c1 == c2:
    print('r2 is ' + str(r2))

RSA算法

对于欲加密的信息flag，将其以某种形式转变为数字m（m即为明文），寻找两个大素数p，q，计算 $n = p * q, n > m$ ，并寻找一整数e，使得 $gcd(e, \phi(n)) = 1$ ，计算e在模 $\phi(n)$ 下的模逆d，既有 $e * d \equiv1\mod \phi(n)$ ，（n，e）作为公钥，d作为私钥。

加密过程：计算 $m ^ e \equiv c \mod n$ ，c作为密文

解密过程：计算 $c ^ d\equiv m \mod n$ ，即求出明文m

使用代码描述：

from Crypto.Util.number import *

# generate public key and private key
p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p-1) * (q-1)

e = getPrime(20)
while GCD(e, phi) != 1:
    e = getPrime(20)
d = inverse(e, phi)

# encrypt
flag = b'flag{te3t_f1@g}'
m = bytes_to_long(flag)
c = pow(m, e, n)

# decrypt
M = pow(c, d, n)
FLAG = long_to_bytes(M)
print(FLAG)

常见套路

n可以直接分解，使用factordb/yafu等工具分解

yafu安装

factordb
e过小，可以直接对c开根

e过小时有两种情况：
1. $m^e = c < n$ ，这种情况直接对c开e次方即可，可以使用gmpy2中的iroot函数
2. $m^e = c> n$ ，这种情况需要在有限域下对c开方，一般先计算 $c_p \equiv c \mod p, \ \ c_q \equiv c \mod q$ ，分别求出 $c_p,c_q$ 在c下的e次根（可能有多个），然后使用CRT遍历所有组合，加上一个check就可以得出明文
  
  exp如下：
```
from Crypto.Util.number import *
import time
from binascii import hexlify, unhexlify
```

  def all_printable(s):
      for i in s:
          if i in range(0x20, 0x7f):
              continue
          else:
              return False
      return True


  c1 = 41916660509735681027019909671717018487229272406236122504156289977758731252417
  c2 = 85375408267213626505407298139766901118881297413238027698850458304286969338892
  p = 89834581734992535082202189661356183331605576085712018104013855381701242019439
  q = 92380672743807969126953374734947674114196691294242882383797634346123981206093
  e = 6

  PR.<x> = PolynomialRing(Zmod(p))
  f1 = x ^ e - c1
  p_roots = [int(i[0]) for i in f1.monic().roots()]

  PR.<y> = PolynomialRing(Zmod(q))
  f2 = y ^ e - c2
  q_roots = [int(i[0]) for i in f2.monic().roots()]

  print('p_roots = ' + str(p_roots))
  print('q_roots = ' + str(q_roots))
  m = []
  for pp in p_roots:
      for qq in q_roots:
          tmp_solve = long_to_bytes(CRT_list([pp, qq], [p, q]))
          if all_printable(tmp_solve):
              print(tmp_solve)
  ```

  数据使用的是一组随机生成的，e较小的数据

d过小，使用Wiener Attack/Boneh Durfee Attack
1. Wiener Attack:
  
  本质利用了连分数的最佳逼近性，
  
  当 $d<\frac{1}{3}n^{\frac{1}{4}}$ 时， $\frac{e}{N} - \frac{1}{d\phi(n)} = \frac{k}{d}$ ，其中k满足 $ed = k\phi(n)+1$
  
  由于连分数有着最佳有理数逼近的特性：
  
  即对于任意有理数 $\frac{p}{q}$ ，若其可以由渐近分数序列 $a_i$ 逼近，且有 $a_n = \frac{p}{q}$ ，则小于 $\frac{p}{q}$ 的最大的有理数等于 $a_{n-1}$ 。
  
  所以如果我们求得了n $\frac{e}{n}$ 的渐近分数序列 $b_i$ ， $b_n = \frac{e}{N}$ ，则在 $a_1,\dots,a_{n-1}$ 中包含了所有 $a_1 到\frac{e}{n}$ 的有理数，当 $\frac{k}{d}$ 和 $\frac{e}{n}$ 相差不大时，其必然在这n-1个数当中。
  
  知道 $d,k$ 后，可以通过 $ed = k\phi(n)+1$ 计算出 $\phi(n)$ ，再通过 $n = p * q, \ \phi(n) = (p-1)*(q-1)$ 计算出 $p,q$ ，遍历渐进分数序列，检验计算出的p，q是否为n的正确分解即可分解n。
2. Boneh Durfee Attack:
  
  比Wiener Attack更强，此处不详述攻击原理，给出约束条件和sage脚本。
  
  约束条件： $d < n^{0.292}$ 时，即可使用Boneh Durfee Attack
已知e，d，有多项式时间内可分解的算法

具体的证明涉及二次剩余的一些知识，这里不作详述，在附录中贴了证明步骤

此种办法其实只是利用了 $e * d -1 = K * \phi(n)$ ，如果不知道 $e*d$ ，但知晓类似 $lcm(p-1, q-1)$ 此种包含了 $\phi(n)$ 大量因子的数值，也是可以直接使用此种方法的，下面贴出exp：
```
def Factorize(n, e_d_1):
    g = 2
    while True:
        k = e_d_1
        while not k & 1:
            k //= 2
            p = int(gcd(pow(g, k, n) - 1, n)) % n
            if p > 1:
                return p, n // p
        g = int(next_prime(g))
```

对于相同的n和明文m，有两组不同的e和c，且 $gcd(e_1,e_2)=1$ 使用共模攻击方法

此种情况可表示为：

$m^{e_1}\equiv c_1 \mod n$

$m^{e_2}\equiv c_2 \mod n$

对e1，e2使用扩展欧几里得除法，则可以得到s，t使得 $s*e_1 + t*e_2 = gcd(e_1,e_2) = 1$

则 $c_1^{s} * c_2^{t} = m ^ {e_1*s + t*e_2} = m$ ，即求出明文

注意这里直接求出的s或t可能为负数，以s为负数为例，则有 $c_1 ^ s = c_1^{-|s|} = (c1^{-1})^{|s|}$ ，即先求出c1对n的模逆，然后再计算即可
e与 $\phi(n)$ 不互素，除去公因数之后，有限域开根

当 $gcd(e, \phi(n)) > 1$ ，则 $m^e \equiv (m^{gcd(e,\phi(n))})^{\frac{e}{gcd(e,\phi(n))}} \equiv c \mod n$ ，计算 $\frac{e}{gcd(e,\phi(n))}$ 的模逆a，则 $c^a \equiv m^{gcd(e,\phi(n))} \mod n$ ，当 $gcd(e,\phi(n))$ 较小时，即为之前讨论过的e较小情况，当 $gcd(e,\phi(n))$ 较大时，求p，q的e次根步骤需要替换为一些有限域开根的高效算法（如AMM算法等）进行计算。

备注：当 $gcd(e,\phi(n)) = e$ 时，无需乘模逆，直接有限域开根即可。
Copper Smith

这里不深究底层原理，只需要了解Copper Smith用法即可，此处只讨论单变量的Copper Smith。

简单来说，Copper Smith算法可以在多项式时间内求出有限域上一个一元同余方程在某一上限下的所有解。

具体：

已知部分m情况：

可列方程 $m = M_{high} + mdar * 2 ^ k + M_{low}$

则有 $f = (M_{high} + mdar * 2 ^ k + M_{low}) ^ e - c$

对此方程求根即可得到m，约束条件： $|mdar| < n^{\frac{1}{e}}$

但注意这里e需要足够小，才可以求出解，所以实际用处不大，因为可以直接使用Wiener Attack

已知部分p情况：

可列方程 $f = x + \hat{p}$

设beta为0.4（由于并不确定p，q的大小关系），当欲求部分小于 $2n^{\frac{1}{4}}$ 时，可以求得p

已知部分d情况：

设 $s = p + q$ ，则有

$e * dhar \equiv 1 + k(n-s+1) \mod 2 ^{\frac{n}{4}}$

和

$p^2 - sp + n \equiv 0 \mod 2 ^{\frac{n}{4}}$

为了消掉s（即只保留p一个变量），通过观察，一式乘p，二式乘k，相减，得到：

$e*dhar*p \equiv p + kpn - kp^2 -kn + kp \mod 2 ^{\frac{n}{4}}$

则使用Copper Smith解此方程，可以得到部分p，这就转化为了部分p的问题

示例代码：

   from Crypto.Util.number import *

   base = 512
   p = random_prime(2^base, 2^(base-1))
   q = random_prime(2^base, 2^(base-1))

   e = random_prime(2^6, 2^4)                    # for test partial d
   # e = random_prime(2^25, 2^23)               # for test partial p 
   # e = 7                                       # for test partial m 

   assert(gcd(e, p-1) ==1 and gcd(e, q-1) == 1)

   n = p * q
   m = bytes_to_long(b'flag{Test_flag_for_LordRiot}')

   c = pow(m, e, n)

   print('p = ' + str(p))
   print('q = ' + str(q))
   print('n = ' + str(n))
   print('e = ' + str(e))
   print('c = ' + str(c))

   R.<x> = PolynomialRing(Zmod(n))


   # this situation should use with a small e
   def partial_m(k1, k2):
       m_high = (m >> (k1+k2)) << (k1+k2)
       m_low = m & (2 ^ (k2+1) - 1)

       wait = (m - m_high - m_low) >> k1
       assert(m_high + wait  * 2 ^ k1 + m_low == m)

       assert(wait < n ^ (1/e))

       f = (m_high + m_low + x * 2 ^ k1) ^ e - c
       solve = f.monic().small_roots(X=2^k1, beta=1)
       x0 = solve[0]

       print(long_to_bytes(m_high + x0 * 2 ^ k1 + m_low))



   def partial_p(low_bit, leak_bits, phar=0, _beta=0.4, test=False):

       if low_bit:        
           if test:
               phar = p & (2 ^ (leak_bits+1) - 1)    
           assert((p - phar) >> leak_bits <= 2 * n ^(1/4))                    
           f = x * 2 ^ leak_bits + phar        
           solve = f.monic().small_roots(X=2^(base - leak_bits), beta=_beta)
       else:    
           if test:                    
               phar = (p << leak_bits) >> leak_bits                        
           assert(p - phar <= 2 * n ^(1/4))
           f = x + phar
           solve = f.monic().small_roots(X=2^leak_bits, beta=_beta)


       x0 = solve[0]
       p_solve = int(x0 * 2 ^ leak_bits + phar)
       q_solve = n//p_solve
       print(p_solve * q_solve == n)

       d = inverse(e, (p_solve-1) * (q_solve-1))
       print(long_to_bytes(pow(c, d, n)))
       return p_solve


   # cause the partial_p function need little k, so we may need to reduce the p0
   def partial_d(k, second_bits = (base * 2) // 6 ):
       assert(k>0)
       kbits = k + int(n).bit_length()//4
       d = inverse(e, (p-1) * (q-1))
       dhar = d & (2 ^ (kbits + 1) - 1)
       solved = False

       X = var('X')
       for k in range(1, e+1):
           results = solve_mod([e*dhar*X - k*X*(n-X+1) + k*n == X], 2^kbits)
           for x in results:
               p0 = int(x[0])
               leak_bits = p0.bit_length()
               if p0 == p & (2 ^ (leak_bits+1) - 1):
                   print("leak p bits: " + str(p0.bit_length()))

                   try:        
                       p_solve = partial_p(true, p0.bit_length(), phar = p0)
                       if p == p_solve:
                           print('Got the solution!')
                           solved = True
                           break
                   except:
                       continue
           if solved:
               break
       if not solved:
           print("No solution found")


   # partial_p(true, 300, test=True)
   # partial_m(50, 50)
   # partial_d(50)

例题：

天翼杯Crypto3：

此题给出的 $n = p * q * r$ ，故而之前推导的部分d的公式就不相符了，需要重新推导新的方程

可知：

$e * dhar = 1 + k\phi(n) = 1 + k(p-1)(q-1)(r-1)$

设 $s = q + r, q\_r = q * r$

则原式变为

$e *dhar = 1 + k(p-1) * (q\_r - s + 1)$

$e * dhar \equiv 1 + k(p-1) * (q\_r - s + 1) \mod 2^{\frac{n}{4}}$

又有

$q^2 -s*q + q\_r \equiv 0 \mod 2^{\frac{n}{4}}$

同样为了消掉s，下式乘以 $k*(p-1)$ ，上式乘以 $q$ ，相减得到

$e * dhar * q \equiv k*(p-1)*(q-1)*(q\_r -q) + q \mod 2^{\frac{n}{4}}$

其他脚本与部分d情况的Copper Smith相同

特殊情况下可以对n进行分解（如p，q接近或 $gcd(p-1, q-1)$ 足够大）
1. p，q接近时，可以直接对n开方，然后在n的附近爆破来得到p/q
2. $gcd(p-1, q-1)$ 足够大时，可以使用修改过迭代函数的Pollard's rho算法分解n
如果有时间，可以再多讲些别的，比如一些格在RSA破解上的应用

基于离散对数

Elgamal等

基于椭圆曲线

ECC等

基于格

NTRU、GGH等

基于其他NP问题

Knapsack等

Hash函数

md5、sha族等

附录

RSA数学原理证明

图片说明