RSA基本操作

• 数学知识

  • 互质

    如果两个或两个以上的整数的最大公约数是 1，则称它们为互质

    任意两个质数构成互质关系

  • 同余

    给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，那么就称整数a与b对模m同余，记作$a≡b(mod\ m)$

  • 模反元素

    如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a对模数n的“模反元素” 。

    即 $ab≡1 (mod\ n)$

  • 扩展欧几里得算法

    扩展欧几里德算法是用来在已知a, b时，求解一组x，y，使它们满足贝祖等式 $ax+by = gcd(a, b)$

  • 欧拉函数

    对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目

    欧拉函数是积性函数，若m,n互质，则 $φ(mn)=φ(m)φ(n)$

    若n为质数，则 $φ(n)=n-1$

  • 欧拉定理

    若n,a为正整数，且n,a互质，则 $a^{φ(n)}=1\ (mod\ n)$

• 密钥生成

  1. 随机选择两个不相等的质数p、q

     $p=14214677$

     $q=15733001$

  2. 计算p、q乘积n

     $n=p× q=223639527455677$

  3. 计算φ(n)

     $φ(n)=(p-1)(q-1)=14214676×15733000=‭223639497508000‬$

  4. 随机选择一个整数$e$ ($1<e<φ(n)$且e与φ(n) 互质)

     $e=30001$

  5. 计算e对于φ(n)的模反元素d

     $ed≡1\ (mod\ φ(n))$

     变形，得到一个二元一次方程

     $ed-kφ(n)=1$

     $30001d-‭223639497508000k=1$

     可以看作

     $30001x+223639497508000y=gcd(30001,223639497508000)=1$

     使用扩展欧几里得算法求解，得到

     $(x,y)=(166769868946001,7629)$

     $d=166769868946001$

  6. 将n和e封装成公钥，n和d封装成私钥

     公钥$(223639527455677,30001)$

     私钥$(223639527455677,166769868946001)$

• 加密与解密

  • 公钥加密

    $m^e≡c (mod\ n)$

    m为明文，c为密文，加密就是计算c

    加密“flag”

    m=0x666c6167=‭1718378855‬

    $‭1718378855^{30001} ≡c (mod\ 223639527455677)$

    解得$c=191215680523649$

  • 私钥解密

    $c^d≡m\ (mod\ n)$

    $191215680523649^{166769868946001}≡m\ (mod\ 223639527455677)$

    解得$m=‭1718378855$

    转化为字符串得到“flag”

    解密方法的证明

    证：$c^d≡m\ (mod\ n)$

    由加密规则可得

    $c=m^e-kn$

    代入，即证：

    $(m^e-kn)^d≡ m\ (mod\ n)$

    左边展开后除了第一项，其余项均模n余0，即证：

    $m^{ed}≡m\ (mod\ n)$

    d为e对于φ(n)的模反元素，所以

    $ed=hφ(n)+1$

    代入，即证：

    $m^{hφ(n)+1}≡m\ (mod\ n)$

    1. m、n互质

       根据欧拉定理可得

       $m^{φ(n)}=1\ (mod\ n)$

       所以

       $m(m^{φ(n)})^h=m\ (mod\ n)$

       即

       $m^{hφ(n)+1}≡m\ (mod\ n)$

    2. m、n不互质

       n的因数为1，n，p，q，若m、n不互质，必然有$m=kp$ 或 $m=kq$

       不妨设 $m=kp$

       $m<n$ 所以 $k<q$，k与q一定互质，kp和q互质，所以

       $(kp)^{φ(q)}≡1\ (mod\ q)$

       即

       $(kp)^{q-1}≡1\ (mod\ q)$

       所以

       $[kp^{(q-1)}]^{h(p-1)}kp≡kp\ (mod\ q)$

       即

       $(kp)^{ed}≡kp\ (mod\ q)$

       $(kp)^{ed}=tq+kp$

       $(kp)^{ed}$和$kp$能被p整除，所以t一定能被p整除

       设$t=ap$

       $(kp)^{ed}=apq+kp$

       即

       $m^{ed}=an+m$

       所以

       $m^{ed}≡m\ (mod\ n)$

• 快速幂取模

  • 同余定理

    (a +/- b) % c = (a % c +/- b % c) % c 
        
    (a * b) % c = (a % c) * (b % c) % c 
        
    ab % c = (a % c)b % c
    

  • python实现

    def quick_mod(a,b,c):
        ans = 1
        t = a % c
        while b:
            if b & 1:
                ans = (ans * t) % c
            t = (t * t) % c
            b >>= 1
        return ans
    

• 欧几里得算法

  定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

  python实现

  递归

  def gcd(a, b):
  	if b == 0:
  		return a
  	return gcd(b,a%b)
    
  

  循环

  def gcd(a, b):
      while 0 != b:
          a, b = b, a % b
      return a
  

• 扩展欧几里得算法

  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)
    
  def modinv(a, m):
      g, x, y = egcd(a, m)
      if g != 1:
          raise Exception('modular inverse does not exist')
      else:
          return x % m