RSA——第一次不自闭

理论

基础知识

• 互质

  互质就是两个数的最大公约数是1，gcd(a,b)=1

  任意两个质数都互质

• 同余

  给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，那么就称整数a与b对模m同余，记作$a≡b(mod\ m)$ 其实可以这么理解：a对m取余后得到b：$a\ mod\ m=b$

• 欧拉函数

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

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

• 模反元素

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

  即 $ab≡1 (mod\ n)$ 也可以这么理解：ab对n取余之后得到1，b就是a的模反元素$ab\ mod\ n = 1$

  各种定理和算法

• 欧拉定理

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

• 欧几里得算法

  是求最大公约数的一种方法。

  用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

  代码实现：

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

• extend_gcd

  如果a、b是整数，那么一定存在整数x、y使得：$ax+by=gcd(a,b)$ 这是一个很简单的问题，但是解决它就⑧一定简单了

  这时候就要用到extend_gcd算法だよ。

  1. 显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
  2. ab!=0 时, $ax~1~+by~1~=gcd(a,b);$ $bx~2~+(a mod b)y~2~=gcd(b,a mod b);$
  3. 根据朴素的欧几里德原理有$ gcd(a,b)=gcd(b,a mod b)$;则:$ax~1~+by~1~=bx~2~+(a mod b)y~2~$;
  4. 即:$ax~1~+by~1~=bx~2~+(a-(a/b)b)y~2~=ay~2~+bx~2~-(a/b)by~2~$;
  5. 根据恒等定理得：$x~1~=y~2~; y~1~=x~2~-(a/b)*y~2~; $

  上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

  所以代码实现：

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

• 孙子定理（中国剩余定理）

  学习的事以后再说——老总

实践

加密过程

1. 随机选两个不相等的质数p和q。

   例如：p=14214677

   ​ q=15733001

2. 两数相乘得到n

   $n=p*q=22363952745677$

3. 将两数分别减一再相乘得到phin

   $phin=(p-1)(q-1)=223639497508000$

4. 随机选择一个整数 e ( 1 < e < phin 且 e 与 phin 互质） e=65537

5. 计算e对于phin的模反元素。

   $ed≡1\ (\ mod\ φ(n))$ 得到d=156179448585473

6. n和e组成公钥，n和d组成私钥。 公钥(22363952745677,65537) 私钥(22363952745677,156179448585473)

公钥加密

加密flag

m=int('flag'.encode('hex'),16)

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

python中可操作：pow(m,e,n)

得到c=32176455243891

私钥解密

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

题目分析

RSA_small_plain

小公钥指数攻击，e=7还⑧算大

因为 $c≡m^e（mod n）$ 然后可以设 $m\^e=c+kn，m=(c+kn)\^{1/e}$ 然后扯淡的是，直接给c开7次方，是个整数……

直接decode：

RSA_common_modulus

有n，和e1,e2,c1,c2

应该是共模攻击s1e1+s2e2=1

扩展欧几里得算法求一波s1和s2

然后发现s2是个负的，就求c2r取-s2次方

最后解码