首页 / 算法 / RSA算法的数学基础
RSA算法的数学基础
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了RSA算法的数学基础,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含10666字,纯文字阅读大概需要16分钟。
内容图文
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?pi?1?)(其中
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=1n?mi?是整数 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?=mi?M?,?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=1n?ai?ti?Mi?,在模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=1n?ai?ti?Mi?)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=1n?mi?=3×5×7=105
由 M i = M m i M_i=\frac{M}{m_i} Mi?=mi?M?分别求得 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=1n?ai?ti?Mi?=k?105+233,k∈Z
当k取值为-2时,有最小正整数解 x=23
内容总结
以上是互联网集市为您收集整理的RSA算法的数学基础全部内容,希望文章能够帮你解决RSA算法的数学基础所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。