RSA算法的数学理论基础
单向函数
单向函数是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算，但是给出一个随机输入的函数值，算出原始输入却比较困难。
同余及模运算
同余：给定一个正整数m，如果两个整数a和b满足
a
−
b
a-b
a−b能够被m整除，即
a
−
b
m
\frac{a-b}{m}
ma−b得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。
模运算：模运算在数学理论或者程序编写中都有着十分广泛的应用，判别一个数的奇偶问题、从模的幂计算到求解最大公约数问题、从中国剩余定理到凯撒密码问题…在这些数学理论中似乎到处都能看到模运算的身影，模运算与基本的四则运算有些相似，但是模n除法比传统的除法要有一些技巧，通常的法则是：在
g
c
d
(
a
,
n
)
=
1
gcd(a,n)=1
gcd(a,n)=1的情况下用
a
(
m
o
d
n
)
a(mod\ n)
a(mod n)去除。
例1
加减乘运算与基本的四则运算相似
解 x + 7 ≡ 3 ( m o d 17 ) x+7≡3(mod\ 17) x+7≡3(mod 17)
x ≡ 3 − 7 ≡ − 4 ≡ 13 ( m o d 17 ) x≡3-7≡-4≡13(mod\ 17) x≡3−7≡−4≡13(mod 17)
在进行除法运算的时候，应非常小心
设整数
a
,
b
,
c
,
n
(
n
≠
0
)
a,b,c,n(n\neq 0)
a,b,c,n(n=0)且
g
c
d
(
a
,
n
)
=
1
gcd(a,n)=1
gcd(a,n)=1如果
a
b
≡
a
c
(
m
o
d
n
)
ab≡ac(mod\ n)
ab≡ac(mod n)，那么
b
≡
c
(
m
o
d
n
)
b≡c(mod\ n)
b≡c(mod n)；换句话说，如果a和n是互素的，我们可以在同余式两边同除以a。
例2
解 2 x + 7 ≡ 3 ( m o d 17 ) 2x+7≡3(mod\ 17) 2x+7≡3(mod 17)
2 x ≡ 3 − 7 ≡ − 4 ( m o d 17 ) 2x≡3-7≡-4(mod\ 17) 2x≡3−7≡−4(mod 17) 于是有 x ≡ − 2 ≡ 15 ( m o d 17 ) x≡-2≡15(mod\ 17) x≡−2≡15(mod 17)。因为 g c d ( 2 , 17 ) = 1 gcd(2,17)=1 gcd(2,17)=1，所以能够在同余式两边同除以2。
例3
解 5 x + 6 ≡ 13 ( m o d 11 ) 5x+6≡13(mod\ 11) 5x+6≡13(mod 11)
5 x ≡ 13 − 6 ≡ 7 ( m o d 11 ) 5x≡13-6≡7(mod\ 11) 5x≡13−6≡7(mod 11) 此时虽然有 g c d ( 5 , 11 ) = 1 gcd(5,11)=1 gcd(5,11)=1，但是同余式右边不能够被5整除
注意到 7 ≡ 18 ≡ 29 ≡ 40 ≡ ⋯ ( m o d 11 ) 7≡18≡29≡40≡\cdots (mod\ 11) 7≡18≡29≡40≡⋯(mod 11)，因此可以转换为 5 x ≡ 40 ( m o d 11 ) 5x≡40(mod\ 11) 5x≡40(mod 11) -->可以得到结果 x ≡ 8 ( m o d 11 ) x≡8(mod\ 11) x≡8(mod 11)
素数、合数与互素数
素数与合数
大于1的自然数中，除了1和它本身以外不再有其他因数的自然数，那么这个数就称为素数，否则称为合数。
互素数
互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。
当三个或三个以上自然数互质时会出现两种不同的情况：
①它们之间两两互质，例如2，3，5
②它们之间不是两两互质，例如6，8，9。
判别互素数的方法有很多种，例如：
①两个素数一定是互素数。例如，2和13。
②一个素数如果不能整除另一个合数，这两个数为互质数。例如，29和4。
③1既不是素数也不是合数，所以它和任何一个自然数组合在一起都是互素数。例如1和72。
④相邻的两个自然数是互质数。例如15与16。
⑤相邻的两个奇数是互质数。例如17与19。
⑥大数是素数的两个数是互质数。例如97与88。
⑦小数是素数，大数不是小数的倍数，此时两个数是互质数。例如7和16。
⑧两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。例如357与715。
⑨两个数都是合数（二数差又较小），这两个数的差的所有质因数都不是小数的约数，这两个数是互质数。例如462与221。
⑩2和任何奇数是互素数。例如2和43。
费马小定理
费马小定理是数论中的一个重要定理，在1636年由皮埃尔·德·费马提出。如果p是一个质数，而整数a不是p的倍数，则有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}≡1(mod\ p) ap−1≡1(mod p)
例4
令a=3，p=5
此时3不是5的倍数
因此 a p − 1 ≡ 1 ( m o d p ) a^{p-1}≡1(mod\ p) ap−1≡1(mod p) --> 3 5 − 1 ≡ 1 ( m o d 5 ) 3^{5-1}≡1(mod\ 5) 35−1≡1(mod 5) 即 81 ≡ 1 ( m o d 5 ) 81≡1(mod\ 5) 81≡1(mod 5)
欧拉函数与欧拉定理
欧拉函数
在数论中，对于正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的个数。
通式：
φ
(
n
)
=
n
∏
i
=
1
n
(
1
−
1
p
i
)
φ(n)=n\prod_{i=1}^{n}(1-\frac{1}{p_i} )
φ(n)=n∏i=1n(1−pi1)(其中
p
1
,
p
2
⋯
p
n
p_1,p_2⋯p_n
p1,p2⋯pn为n的所有质因数，n是不为0的整数)
特殊性质：当n为质数时，
φ
(
n
)
=
n
−
1
φ(n)=n-1
φ(n)=n−1
由于欧拉函数是积性函数，所以如果存在两个正整数m，n，当m与n互质时，则
φ
(
m
⋅
n
)
=
φ
(
m
)
⋅
φ
(
n
)
=
(
m
−
1
)
⋅
(
n
−
1
)
φ(m\cdot n)=φ(m)\cdot φ(n)=(m-1)\cdot(n-1)
φ(m⋅n)=φ(m)⋅φ(n)=(m−1)⋅(n−1)
例5
令n=120，此时120的因数有1、2、3、4、5、6、8、10、12、15、20、24、30、40、60、120，共16个。
但其中只有2、3、5是质数，因此 φ ( 120 ) = 120 ⋅ ( 1 − 1 2 ) ⋅ ( 1 − 1 3 ) ⋅ ( 1 − 1 5 ) = 32 φ(120)=120\cdot (1-\frac{1}{2})\cdot (1-\frac{1}{3})\cdot (1-\frac{1}{5})=32 φ(120)=120⋅(1−21)⋅(1−31)⋅(1−51)=32
例6
令n=10，此时n可分解为两个不同的素数的乘积，即2×5。此时有 φ ( 2 ⋅ 5 ) = φ ( 2 ) ⋅ φ ( 5 ) = ( 2 − 1 ) ⋅ ( 5 − 1 ) = 4 φ(2\cdot 5)=φ(2)\cdot φ(5)=(2-1)\cdot(5-1)=4 φ(2⋅5)=φ(2)⋅φ(5)=(2−1)⋅(5−1)=4
欧拉定理
如果两个正整数a和n互质，则
a
φ
(
n
)
≡
1
(
m
o
d
n
)
a^{φ(n)}≡1(mod\ n)
aφ(n)≡1(mod n)
欧拉定理的推论：若正整数a，n互质，那么对于任意正整数b，有
a
b
≡
a
b
(
m
o
d
φ
(
n
)
)
(
m
o
d
n
)
a^b≡a^{b(mod\ φ(n))} (mod\ n)
ab≡ab(mod φ(n))(mod n)
例7
令a=3，n=7，此时a和n互质。由于n是质数， φ ( 7 ) = 7 − 1 = 6 φ(7)=7-1=6 φ(7)=7−1=6
a φ ( n ) ≡ 1 ( m o d n ) a^{φ(n)}≡1(mod\ n) aφ(n)≡1(mod n) --> 3 φ ( 7 ) ≡ 1 ( m o d 7 ) 3^{φ(7)}≡1(mod\ 7) 3φ(7)≡1(mod 7) 即 729 ≡ 1 ( m o d 7 ) 729≡1(mod\ 7) 729≡1(mod 7)
例8
接例5中的数据，令b=13。则 a b ≡ a b ( m o d φ ( n ) ) ( m o d n ) a^b≡a^{b(mod\ φ(n))} (mod\ n) ab≡ab(mod φ(n))(mod n) --> 3 13 ≡ 3 13 ( m o d 6 ) ( m o d 7 ) 3^{13}≡3^{13(mod\ 6)} (mod\ 7) 313≡313(mod 6)(mod 7) 即 3 13 ≡ 3 ( m o d 7 ) 3^{13}≡3 (mod\ 7) 313≡3(mod 7)
贝祖定理与欧几里得算法
贝祖定理
如果a、b是整数，那么一定存在整数x、y使得 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)。换句话说，如果 a x + b y = m ax+by=m ax+by=m有解，那么m一定是 g c d ( a , b ) gcd(a,b) gcd(a,b)的若干倍。因此可以通过这种方法来判断一个式子是否有解。但通常情况下我们并不仅仅想要知道有没有解，而是想要知道在有解的情况下这个解到底是多少。于是我们需要用到扩展欧几里得算法对这个式子进行求解。
欧几里得算法
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。
定理：
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
(
m
o
d
b
)
)
gcd(a,b)=gcd(b,a(mod\ b))
gcd(a,b)=gcd(b,a(mod b))
例9
求解482和1180的最大公约数gcd(482,1180)
1180=2×482+216
482=2×216+50
216=4×50+16
50=3×16+2
16=8×2+0
当最后一个式子余数为0时结束计算，则gcd(482,1180)=2
欧几里得算法有以下两个重要的方面：
1.它不需要因式分解；
2.速度快。
欧几里得扩展算法
扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。
除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax + by = gcd(a,b)
ax+by=gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
ax+by=gcd(a,b)的整数解。
原理：令
g
c
d
(
a
,
b
)
=
a
x
1
+
b
y
1
，
g
c
d
(
b
,
a
(
m
o
d
b
)
)
=
b
x
2
+
(
a
(
m
o
d
b
)
)
y
2
gcd(a,b)=ax_1+by_1，gcd(b,a(mod\ b))=bx_2+(a(mod\ b))y_2
gcd(a,b)=ax1+by1，gcd(b,a(mod b))=bx2+(a(mod b))y2。
根据欧几里得
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
(
m
o
d
b
)
)
gcd(a,b)=gcd(b,a(mod\ b))
gcd(a,b)=gcd(b,a(mod b))，则
a
x
1
+
b
y
1
=
b
x
2
+
(
a
(
m
o
d
b
)
)
y
2
ax_1+by_1=bx_2+(a(mod\ b))y_2
ax1+by1=bx2+(a(mod b))y2。
由于
a
(
m
o
d
b
)
=
a
−
[
a
b
]
⋅
b
a(mod\ b)=a-[\frac{a}{b}]\cdot b
a(mod b)=a−[ba]⋅b，有
a
x
1
+
b
y
1
=
b
x
2
+
(
a
−
[
a
b
]
⋅
b
)
y
2
ax_1+by_1=bx_2+(a-[\frac{a}{b}]\cdot b) y_2
ax1+by1=bx2+(a−[ba]⋅b)y2 。
变形为
a
x
1
+
b
y
1
=
a
y
2
+
b
(
x
2
−
[
a
b
]
⋅
y
2
)
ax_1+by_1=ay_2+b(x_2-[\frac{a}{b}]\cdot y_2 )
ax1+by1=ay2+b(x2−[ba]⋅y2) (其中“[ ]”表示取整函数)
根据多项式恒等定理有：
x
1
=
y
2
，
y
1
=
x
2
−
[
a
b
]
⋅
y
2
x_1=y_2，y_1=x_2-[\frac{a}{b}]\cdot y_2
x1=y2，y1=x2−[ba]⋅y2。
可以看出，
x
1
，
y
1
x_1，y_1
x1，y1的值由
x
2
，
y
2
x_2，y_2
x2，y2求出，这种求解思想称之为递归。
此时一定会存在b=0，使整个递归算法结束。
例10
求整数x和y，使得101x+3427y=gcd(101,3427)
(此时101与3427互质，gcd(101,3427)=1，即求解101x+3427y=1)
3427=33×101+94
101=1×94+7
94=13×7+3
7=2×3+1
当最后一个式子余数为1时结束计算，然后开始倒推
1=7-2×3
3=94-13×7
7=101-1×94
94=3427-33×101
有1=7-2×3=7-2×(94-13×7)=(101-1×94)-2×[94-13×(101-1×94)]=101-1×(3427-33×101)-2×{(3427-33×101)-13×[101-1×(3427-33×101)]}=984×101-29×3427
解得x=984，y=-29
例11
接例7的数据，求整数x和y，使得482x+1180y=gcd(482,1180)
(此时482与1180不互质，根据例7中的计算结果，gcd(482,1180)=2，即求解482x+1180y=2)
2=50-3×16
16=216-4×50
50=482-2×216
216=1180-2×482
有2=50-3×16=50-3×(216-4×50)=(482-2×216)-3×[(1180-2×482)-4×(482-2×216)]=[482-2×(1180-2×482)]-3×{(1180-2×482)-4×[482-2×(1180-2×482)]}=71×482-29×1180
解得x=71，y=-29
模反元素及其求法
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，即满足
a
b
≡
1
(
m
o
d
n
)
ab≡1(mod n)
ab≡1(modn)。这时，b就叫做a的“模反元素”。
模反元素可通过两种方法进行求解：
①用费马小定理求解：
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}≡1(mod\ p)
ap−1≡1(mod p) -->
a
⋅
a
p
−
2
≡
1
(
m
o
d
p
)
a\cdot a^{p-2}≡1(mod\ p)
a⋅ap−2≡1(mod p)，即a的模反元素为
a
p
−
2
a^{p-2}
ap−2
例12
接例2中的数据
3 5 − 1 = 3 ⋅ 3 5 − 2 ≡ 1 ( m o d 5 ) 3^{5-1}=3\cdot 3^{5-2}≡1(mod\ 5) 35−1=3⋅35−2≡1(mod 5)，即3的模反元素为27
②扩展欧几里得算法求解：
a
b
≡
1
(
m
o
d
n
)
ab≡1(mod n)
ab≡1(modn)等价于
a
x
+
n
y
=
1
ax+ny=1
ax+ny=1，用扩展欧几里得算法求得一组解，当求得的解为负数时，通过计算
(
b
+
n
)
m
o
d
n
(b+n)mod\ n
(b+n)mod n可以将它转换为整数。
中国剩余定理
线性方程同余组
(
S
)
=
{
x
≡
a
1
(
m
o
d
m
1
)
x
≡
a
2
(
m
o
d
m
2
)
⋮
x
≡
a
n
(
m
o
d
m
n
)
(S)= \begin{cases} x≡a_1(mod\ m_1)\\ x≡a_2(mod\ m_2)\\ \ \ \ \ \ \ \ \ \ \ \vdots \\x≡a_n(mod\ m_n) \end{cases}
(S)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧x≡a1(mod m1)x≡a2(mod m2) ⋮x≡an(mod mn)
假设整数
m
1
,
m
2
,
⋯
,
m
n
m_1,m_2,\cdots,m_n
m1,m2,⋯,mn两两互质，则对任意的整数：
a
1
,
a
2
,
⋯
,
a
n
a_1,a_2,\cdots,a_n
a1,a2,⋯,an，方程组(S)有解，并且通式可以用以下方式构造得到：
- 设 M = m 1 × m 2 × ⋯ × m n = ∏ i = 1 n m i M=m_1× m_2×\cdots×m_n=\prod_{i=1}^{n}m_i M=m1×m2×⋯×mn=∏i=1nmi是整数 m 1 , m 2 , ⋯ , m n m_1,m_2,\cdots,m_n m1,m2,⋯,mn的乘积，并设 M i = M m i M_i=\frac{M}{m_i} Mi=miM,∀i∈{1,2,⋯,n}是除了 m i m_i mi以外的n-1个整数的乘积。
-
- 设
t
i
=
M
i
−
1
t_i=M_i^{−1}
ti=Mi−1为
M
i
M_i
Mi模
m
i
m_i
mi的数论倒数
（
t
i
为
N
i
模
m
i
意
义
下
的
逆
元
）
（t_i为N_i模m_i意义下的逆元）
（ti为Ni模mi意义下的逆元）
M i ⋅ t i ≡ 1 ( m o d m i ) M_i\cdot t_i≡1(mod\ m_i ) Mi⋅ti≡1(mod mi),∀i∈{1,2,⋯,n}。
- 设
t
i
=
M
i
−
1
t_i=M_i^{−1}
ti=Mi−1为
M
i
M_i
Mi模
m
i
m_i
mi的数论倒数
（
t
i
为
N
i
模
m
i
意
义
下
的
逆
元
）
（t_i为N_i模m_i意义下的逆元）
（ti为Ni模mi意义下的逆元）
- 方程组(S)的通解形式为 x = a 1 ⋅ t 1 ⋅ M 1 + a 2 ⋅ t 2 ⋅ M 2 + ⋯ + a n ⋅ t n ⋅ M n + k M = k M + ∑ i = 1 n a i t i M i x=a_1\cdot t_1\cdot M_1+a_2\cdot t_2\cdot M_2+\cdots+a_n\cdot t_n \cdot M_n+kM=kM+\sum_{i=1}^na_it_iM_i x=a1⋅t1⋅M1+a2⋅t2⋅M2+⋯+an⋅tn⋅Mn+kM=kM+∑i=1naitiMi，在模M的意义下，方程组(S)只有一个解： x = ( ∑ i = 1 n a i t i M i ) m o d M x=(\sum_{i=1}^na_it_iM_i)mod\ M x=(∑i=1naitiMi)mod M
例13
在中国古代著名数学著作《孙子算经》中，有一道题目叫做“物不知数"，原文如下: 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何? 即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。
中国数学家秦九韶于1247年做出了完整的解答，口诀如下: 三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五使得知。
使用中国剩余定理来求解上面的“物不知数”问题，便可以理解口诀中的数字含义。
线性方程同余组 ( S ) = { x ≡ 2 ( m o d 3 ) x ≡ 3 ( m o d 5 ) x ≡ 2 ( m o d 7 ) (S)= \begin{cases} x≡2(mod\ 3)\\ x≡3(mod\ 5)\\x≡2(mod\ 7) \end{cases} (S)=⎩⎪⎨⎪⎧x≡2(mod 3)x≡3(mod 5)x≡2(mod 7)
其中 a 1 = 2 ， a 2 = 3 ， a 3 = 2 ， m 1 = 3 ， m 2 = 5 ， m 3 = 7 a_1=2，a_2=3，a_3=2，m_1=3，m_2=5，m_3=7 a1=2，a2=3，a3=2，m1=3，m2=5，m3=7
- M = ∏ i = 1 n m i = 3 × 5 × 7 = 105 M=\prod_{i=1}^nm_i =3×5×7=105 M=∏i=1nmi=3×5×7=105
由 M i = M m i M_i=\frac{M}{m_i} Mi=miM分别求得 M 1 = 105 3 = 35 ， M 2 = 105 5 = 21 ， M 3 = 105 7 = 15 M_1=\frac{105}{3}=35，M_2=\frac{105}{5}=21 ，M_3=\frac{105}{7}=15 M1=3105=35，M2=5105=21，M3=7105=15- 由 M i ⋅ t i ≡ 1 ( m o d m i ) M_i\cdot t_i≡1(mod\ m_i ) Mi⋅ti≡1(mod mi)分别求得 t 1 = 2 ， t 2 = 1 ， t 3 = 1 t_1=2，t_2=1，t_3=1 t1=2，t2=1，t3=1
- 方程组(S)的通解形式为 x = k M + ∑ i = 1 n a i t i M i = k ⋅ 105 + 233 , k ∈ Z x=kM+\sum_{i=1}^na_it_i M_i=k\cdot 105+233,k∈Z x=kM+∑i=1naitiMi=k⋅105+233,k∈Z
当k取值为-2时，有最小正整数解 x=23