对称加密算法:信息的收发方会通过事先商定好的密钥对数据加密和解密。这种加密算法会导致
非对称加密算法:用不同的密钥对数据进行加密和解密,加密的密钥(公钥)是公开的,而解密的密钥(私钥)仅接收者持有。
由于模运算(取余运算)正向计算非常容易,且不可逆的特性,我们可以保证用公钥加密之后的明文不会被轻易破解。
考虑算式 3 3 ? % ? 7 3^3\ \%\ 7 33?%?7,可以很容易得出答案为6。而已知 3 x ? % ? 7 = 6 3^x\ \%\ 7=6 3x?%?7=6时,反向推算 x x x就只能逐一代入验证了。鉴于此例数量级较小,还是很容易就可以推算出答案。
而如果改为 3 x ? % ? 984426289703667782113631386235633223212587 = 6 3^x\ \%\ 984426289703667782113631386235633223212587=6 3x?%?984426289703667782113631386235633223212587=6,再一一尝试就不太现实了。因为有对大数来说求模运算非常困难的特性,模运算也被冠以“单向函数”(One-way Function)之名。
假设要加密的信息为m (message),对其求 e 次幂,此处 e (encrypt)代表加密用的公钥。随后对N取模,得到密文c (cipher):
m
e
m
o
d
??
N
=
c
m^e\mod N=c
memodN=c
显然,由m得到c的正向计算很简单,但由c推算m是非常困难的。
解密的过程与加密类似:
c
d
m
o
d
??
N
=
m
c^d\mod N=m
cdmodN=m
其中d (decrypt)代表解密用的私钥。
将两个式子合并,得
m
e
d
m
o
d
??
N
=
m
m^{ed}\mod N=m
medmodN=m
到此为止,问题变为如何选取合适的 e 和 d 。
欧拉定理(Euler’s theorem):
m,n互质时,取m的
?
(
n
)
\phi(n)
?(n)次方,并对n取余数,结果恒等于1,即:
m
?
(
n
)
≡
1
?
(
m
o
d
?
n
)
m^{\phi(n)}\equiv 1\ (mod\ n)
m?(n)≡1?(mod?n)
其中,
?
(
n
)
\phi(n)
?(n)为欧拉函数,它代表小于等于n的数中,有几个数与n互质,例如
?
(
6
)
=
2
\phi(6)=2
?(6)=2。
对
m
?
(
N
)
m
o
d
??
n
=
1
m^{\phi(N)}\mod n= 1
m?(N)modn=1等式两端同取k次幂,并乘以m,可以写成
m
k
?
(
N
)
+
1
m
o
d
??
N
=
m
m^{k\phi(N)+1}\mod N = m
mk?(N)+1modN=m
经过变换,这个式子形式上与上面的
m
e
d
m
o
d
??
N
=
m
m^{ed}\mod N = m
medmodN=m 相同,可以得到
e
d
=
k
?
(
N
)
+
1
ed=k\phi(N)+1
ed=k?(N)+1
将e移到式子右边,得:
d
=
k
?
(
N
)
+
1
e
d=\frac{k\phi(N)+1}{e}
d=ek?(N)+1?
所以我们可以通过选取此处k、N、e的值来确定私钥d。
问题在于 ? ( n ) \phi(n) ?(n)的计算是十分困难的。它只能够根据定义计算,即对n做质因数分解。而对上百位的大数做质因数分解几乎可以看做计算上不可行的(computational infeasible)。但如果n本身就是一个质数,我们可以很容易得到 ? ( n ) = n ? 1 \phi(n)=n-1 ?(n)=n?1。即n只与自己存在非1公因数。
且 ? ( n ) \phi(n) ?(n)还有一个重要的性质:积性函数。即对任意互质的数p, q,总有 ? ( p ? q ) = ? ( p ) ? ? ( q ) \phi(p*q)=\phi(p)*\phi(q) ?(p?q)=?(p)??(q)。例如选取 p = 17 ? q = 23 p=17\ q=23 p=17?q=23,就有 ? ( 17 ? 23 ) = ? ( 17 ) ? ? ( 23 ) = 16 ? 22 \phi(17*23)=\phi(17)*\phi(23)=16*22 ?(17?23)=?(17)??(23)=16?22,也即 ? ( 391 ) = 352 \phi(391)=352 ?(391)=352。
例如我们选取
k
=
5
N
=
391
e
=
3
k=5\quad N=391\quad e=3
k=5N=391e=3(e应选与
?
(
N
)
\phi(N)
?(N)互质的数,而k的选取较为随意,保证d为整数即可),代入上式,得
d
=
5
?
352
+
2
3
=
587
d=\frac{5*352+2}{3}=587
d=35?352+2?=587
计算出d后,我们就不再需要p和q,将e和N作为加密的公钥(public key)公布,而d作为解密的私钥(private key)。
其他人因为不知道p,q两个互质数,无法计算出 ? ( N ) \phi(N) ?(N),也就无法破解私钥d
利用上面得到的参数,加密字符’a’(ascii编码97)
加密:
9
7
3
m
o
d
??
391
=
79
97^3\mod 391=79
973mod391=79
解密:
7
9
587
m
o
d
??
391
=
97
79^{587} \mod 391=97
79587mod391=97
成功解密字符a
https://www.bilibili.com/video/BV14y4y1272w
目录 问题 A: 努力的虫子 问题 B: 六位数 问题 C: 小h的工具人 问题 D: 小h的礼...
本文章向大家介绍MySQL锁详细讲解,包括数据库锁基本知识、表锁、表读锁、表写锁...
这篇文章介绍了英国《卫报Guardian》为什么和如何从Mongo迁移到Postgres,英国卫...
本文介绍了ASP.NET MVC HttpPostedFileBase文件上传 ,分享给大家,希望对大家有...
队列 目录 队列 阻塞队列 常用方法 常用队列 实现原理 阻塞队列 阻塞队列 ( Bloc...
2月27日消息 微软早些时候已恢复 因假期带来的更新延期,最新一次的 Windows 10 ...
本文将介绍如何在Java中使用正则表达式来处理文本数据。正则表达式就是一个字符...
外媒 Windows Latest 报道,微软推出的一款新的更新补丁正在向 Windows 10 版本 ...
小高不太行之前端——CSS样式基础下 提示还有一篇延申哦等等我qaq 提示 文章目录...
第一个:abbr 或 acronym 这两个标识是一回事,主要是用于一些英语的缩写,当你...