CTF现代密码之RSA之数论

  前言：

在 CTF 的密码题目中，RSA 以其加密算法之多且应用之广泛，所以在比赛中是最常见的题目。学习密码学并不难，但首先得打好数学基础，并在攻破密码的学习之路上持之以恒。今天我们就来打开 RSA 加密世界的第一扇门 《数论》。

本文涉及知识点实操：RSA加密实验 ：RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。通过本实验，了解RSA加密算法的基本原理。

 

数论基础：

1.素数

2.公约数与公倍数

3.欧拉函数

4.欧几里得算法

5.扩展欧几里得算法

6.同余

7.模运算

8.逆

9.中国剩余定理

10.逆元与同余式定理

1.素数：

定义：

一个大于1的自然数，除了1和它本身外，

不能被其他自然数整除（除0以外）的数称之为素数（质数）；

否则称为合数。

如：
3×4 = 12,不是素数。

11除了等于11×1以外，不能表示为其它任何两个整数的乘积，

所以11是一个素数。

关于素数有以下事实：

(1) 如果p是素数，且p | ab (表示 ab 能被 p 整除)，则p | a或 p | b，即 p 至少整除 a 与 b 中的一个。

(2)(算术基本定理) 每个整数n ≥ 2，均可分解成素数幂之积：

 

若不计因数的顺序，这个分解式是唯一的。其中 k ≥ 1，  是两两互不相同的素数，  是正整数。

(3) 素数有无穷多个。

2.最大公约数与最小公倍数

定义 1：

设 ， 是两个整数。如果  且 ，那么 d 就称为是  和  的公约数（或公因数）我们把  和  的公约数中最大的称为  和  的最大公约数，记作

当  时，我们称  和  是互素的。

定义 2：

设 ， 是两个整数。如果 且 ，那么  就称为是  和  的公倍数。我们把  和  的正的公倍数中的最小的称为  和  的最小公倍数，记作 。

3.欧拉函数

定义：

对正整数 ，欧拉函数是小于或等于  的数中与  互质的数的个数，

记作：φ

例如：φ ,因为 ，，， 均与  互质。

性质：

(1) 若  为一素数 P，则：φ

(2) 如果 P 是素数， ,则：φ =

例如 ：求 φ(16)，由于 16 = 2×2×2×2，故 φ(16) = (2-1) × = 8

(3) 若 n 为任意两个互质的 数  的积，则：φ(a*b) = φ(a) × φ(b)

例：求 φ(40)，由于 40 = 5×8，所以 φ(40) = φ(5) × φ(8) = 4×4 = 16

(4)对于整数 ，根据算术基本定理， 可以分解成唯一的形如  ⋯ 的分解式，则：

4.欧几里得(Euclid)算法

定义：

  欧几里得算法又称为辗转相除法，用于求两个数的最大公约数。

原理： = (，  ) ，

1.python 代码实现

2.python 第三方库：

gmpy2.gcd(a,b)     #求 a,b 的最大公约数

Crypto.Util.number

5.扩展欧几里得算法

定义：

  在已知 ， 时，求解一组解 ，使得 ，

算法输入：两个正整数  和

算法输出： 和  的最大公因数  及满足等式  的整数  和

python 代码实现:

gmpy2 库函数 gcdext()

6.同余

定义：

  设 a,b 是整数，，如果 ，则称  和  模  同余，记为 ( )，整数  称为模数。

  由于  等价于 ，所以 ( ) 与      等价。因此，一般我们总假定模数 。

同余的性质

性质 1：

(1)自反性：a ≡ a (mod m)

(2)对称性：a ≡ b (mod m)， b ≡ c (mod m) ，则 a ≡ c (mod m)

性质 2：

(1) 若  ( )， ( )

则： ( )， ( )

特别的，对于一个整数 e,都有  ( )， ( )

(2) 若  ( )，k>0，则 ak ≡ bk (mod mk)

(3)  若  ( )，d 是 a，b 的公因数，则  (mod )

(4) 若  ( )，d|m，d>0，则: a ≡ b (mod d)

(5) 若  ( )，则: ≡ (mod m)

(6)    = (     )  

(7)    = (  )  

7.模运算

定义：

   模  的运算给出了  对模  的余数，这种运算称为模运算。注意：模运算的结果是从 0 到  的一个整数。

  模运算就像普通的运算一样，它是可交换、可结合、可分配的。而且，对每一个中间结果进行模  运算后再进行模  运算，其作用与先进行全部运算，然后再进行模  运算所得到的结果是一样的。例如：

这些性质对于密码学中的数学计算非常的重要，模运算可以将所有中间结果和最后结果限制在一个范围内。对于一个  位的模数  ，任何、加、减、乘的中间结果将不会超过  位长，这样避免了巨大的中间结果，使得计算机能够有效的处理数据。

如：计算 (mod n)，不要直接进行 7 次乘法和一个大数的模运算：

相反，应该进行三次比较小的乘法和三次比较小的模化简：

(( mod n) mod n) mod n

这样就可以避免巨大的中间结果出现。

8.逆

定义：

若 m≥1，,则存在 c 使得：

 

我们把 c 称为 a 对模 n 的逆，记作  (mod m)，在模数已经指明的情况下，有时也记作 。

在(a,m)=1 时，我们可以使用扩展欧几里得算法来求 a 的逆元：，这是因为：扩展欧几里得算法可以找到整数 , 使得 ，这样  ( )

9.中国剩余定理

中国剩余定理（Chinese remainder theorem，CRT），又称孙子定理，最早可见于中国南北朝时期（公元 5 世纪）的数学著作《孙子算经》中，为一次同余方程组的起源。

定理(CRT):

  设  是两两互素的正整数，

,则同余方程组：

有唯一解:  ( )

其中  ( )，i=1,2,⋯,k

代码实现：

10.逆元与同余式定理 1.模运算重要公式：

(a+b) % m = (a % m + b % m) % m

(a-b) % m = (a % m - b % m) % m

(a*b) % m = (a % m * b % m) % m

 % m = (a % m) % m

2.威尔逊定理：

若 p 为素数，则：   ⟹ 推导：  ;

其逆定理同样成立。即：若    ，则 p 为素数

3.二次探测定理：

定义：

若  是素数且 0