RSA原理以及计算逻辑
RSA基于的基础数学难题是大质数分解难题
计算原理如下：
1. 寻找两个大质数
p
p
p
,
q
q
q
，如超过200位的大质数
基于素数定理可知，素数的分布规律在趋于无穷大的时候
π
(
x
)
\pi(x)
π
(
x
)
渐近于
x
/
l
o
g
x
x/logx
x
/
l
o
gx
。
所以在数字接近
1
0
200
10 ^ {200}
1
0
200
的时候，随机选择一个200位长度的数字是质数的概率是
1
/
l
n
(
1
0
200
)
1 / ln(10^{200})
1/
l
n
(
1
0
200
)
，
很显然，我们是不回去选择偶数的，所以概率可以扩大一倍，
于是大约有
1
/
(
2
/
l
n
(
2
0
200
)
)
=
230
1/(2 / ln(20^{200}))=230
1/
(
2/
l
n
(
2
0
200
))
=
230
个数中会找到一个质数。
基于拉宾概率素性检验可知，随机找一个正整数，只要通过100次米勒检验，那么该数字是合数的概率不足
(
1
/
4
)
100
<
1
0
−
60
(1/4)^{100}<10 ^ {-60}
(
1/4
)
100
<
1
0
−
60
。这个时候我们就可以基本认定改数字是质数了。
于是上述操作在计算机中可以极为轻松的得到。于是我们就有了两个大质数
p
,
q
p,q
p
,
q
2. 生成公私钥
-
获得
n=
p
⋅
q
n=p \cdot q
n
=
p
⋅
q
-
计算
nn
n
的欧拉函数
ϕ(
n
)
=
(
p
−
1
)
(
q
−
1
)
\phi(n) = (p-1)(q-1)
ϕ
(
n
)
=
(
p
−
1
)
(
q
−
1
)
注意：这是因为欧拉函数
ϕ(
n
)
\phi(n)
ϕ
(
n
)
是一个乘性函数 -
根据步骤1的方法再生成一个大于
p,
q
p,q
p
,
q
的素数
ee
e
这样即满足了
(e
,
ϕ
(
n
)
)
=
1
(e,\phi(n))=1
(
e
,
ϕ
(
n
))
=
1
-
目标为找到 关于
ee
e
的一元一次同余方程式
ed
≡
1
(
m
o
d
ϕ
(
n
)
)
ed \equiv 1 (mod \ \phi(n))
e
d
≡
1
(
m
o
d
ϕ
(
n
))
，求逆元
dd
d
一次丢番图方程，代码形式类似递归，思路应该是连分数求解 -
此时得到公钥
(e
,
n
)
(e,n)
(
e
,
n
)
，私钥
dd
d
3. 加解密逻辑
明文信息为
P
P
P
加密为
E
(
P
)
=
C
≡
P
e
(
m
o
d
n
)
E(P)=C \equiv P^e(mod \ n)
E
(
P
)
=
C
≡
P
e
(
m
o
d
n
)
解密为
D
(
E
(
P
)
)
=
E
(
P
)
d
(
m
o
d
n
)
≡
P
e
d
(
m
o
d
n
)
D(E(P))= E(P)^d (mod \ n) \equiv P^{ed} (mod \ n)
D
(
E
(
P
))
=
E
(
P
)
d
(
m
o
d
n
)
≡
P
e
d
(
m
o
d
n
)
因为
e
d
≡
1
(
m
o
d
ϕ
(
n
)
)
ed \equiv 1 (mod \ \phi(n))
e
d
≡
1
(
m
o
d
ϕ
(
n
))
，所以 ed 可以写成
k
ϕ
(
n
)
+
1
k\phi(n)+1
k
ϕ
(
n
)
+
1
，其中
k
k
k
是正整数
所以有
D
(
E
(
P
)
)
≡
P
k
ϕ
(
n
)
⋅
P
(
m
o
d
n
)
D(E(P)) \equiv P^{k\phi(n)} \cdot P \ (mod \ n)
D
(
E
(
P
))
≡
P
k
ϕ
(
n
)
⋅
P
(
m
o
d
n
)
以及欧拉定理可知
P
k
ϕ
(
n
)
≡
1
(
m
o
d
n
)
P^{k\phi(n)} \equiv 1 (mod \ n)
P
k
ϕ
(
n
)
≡
1
(
m
o
d
n
)
所以
D
(
E
(
P
)
)
≡
P
(
m
o
d
n
)
D(E(P)) \equiv P (mod \ n)
D
(
E
(
P
))
≡
P
(
m
o
d
n
)
针对RSA的攻击
哈氏广播攻击(Hastad broadcast attack)
用不同的密钥针对同一段明文加密
防御方式：针对明文信息填充不同的随机数在进行加密
p
,
q
p,q
p
,
q
满足
q
<
p
<
2
q
q<p<2q
q
<
p
<
2
q
的时候解密
d
d
d
的次数小于
n
1
/
4
/
3
n^{1/4}/3
n
1/4
/3
这表明在生成
p
,
q
p,q
p
,
q
的时候 二者距离不能过近
得知大质数
p
,
q
p,q
p
,
q
的部分信息
可以通过解密时间来进行攻击
可以在解密的时候随机等待时间
拉宾密码系统
一种RSA密码系统的变种
ElGamal密码系统原理以及计算逻辑
lGamal基于的基础数学难题是求模大素数的离散对数的困难性
计算原理如下：
1. 寻找一个大素数
p
p
p
和 这个素数的原根
r
r
r
这里找大素数不止依靠拉宾素性检验就可以了，因为我们还需要寻找相对应的原根，所以需要进行以下操作
-
（1） 寻找一个200位长度的大素数
qq
q
-
（2） 去计算
2q
+
1
2q+1
2
q
+
1
是否通过拉宾素性检验，通过则将其定义为
pp
p
否则重新寻找大素数
qq
q
-
（3） 此时拥有了一个大素数
qq
q
和另一个大素数
p=
2
q
+
1
p=2q+1
p
=
2
q
+
1
-
（4） 注意，这样
ϕ(
p
)
=
p
−
1
=
2
q
\phi(p) = p-1 = 2q
ϕ
(
p
)
=
p
−
1
=
2
q
，于是乎，只要随机找一个大数
rr
r
使其满足
rϕ
(
p
)
/
2
=
r
q
≢
1
(
m
o
d
p
)
r^{\phi(p)/2} = r^q \not \equiv 1 ( mod \ p)
r
ϕ
(
p
)
/2
=
r
q
≡
1
(
m
o
d
p
)
以及
rϕ
(
p
)
/
q
=
r
2
≢
1
(
m
o
d
p
)
r^{\phi(p)/q} = r^2 \not \equiv 1 ( mod \ p)
r
ϕ
(
p
)
/
q
=
r
2
≡
1
(
m
o
d
p
)
即可判定
rr
r
为
pp
p
的原根，此时完成大素数与原根的计算（依据定理9.1.1）
2. 生成公私钥
随机生成一个大数
a
a
a
作为私钥，计算
r
a
≡
b
(
m
o
d
p
)
r^a \equiv b ( mod \ p)
r
a
≡
b
(
m
o
d
p
)
，此时，公钥为
(
p
,
r
,
b
)
(p,r,b)
(
p
,
r
,
b
)
，私钥为
a
a
a
3. 加解密逻辑
明文信息为
P
P
P
加密为
E
(
P
)
=
(
γ
,
δ
)
E(P) = (\gamma, \delta)
E
(
P
)
=
(
γ
,
δ
)
其中 先生成一个随机整数
k
k
k
得到
γ
=
r
k
(
m
o
d
p
)
,
0
≤
γ
≤
p
−
1
\gamma = r^k ( mod \ p), \qquad 0 \leq \gamma \leq p-1
γ
=
r
k
(
m
o
d
p
)
,
0
≤
γ
≤
p
−
1
以及
δ
=
P
⋅
b
k
(
m
o
d
p
)
,
0
≤
δ
≤
p
−
1
\delta = P \cdot b^k ( mod \ p), \qquad 0 \leq \delta \leq p-1
δ
=
P
⋅
b
k
(
m
o
d
p
)
,
0
≤
δ
≤
p
−
1
解密为
D
(
C
)
=
γ
a
‾
δ
D(C) = \overline{\gamma^a}\delta
D
(
C
)
=
γ
a
δ
其中
γ
a
‾
\overline{\gamma^a}
γ
a
代表
γ
a
\gamma^a
γ
a
的逆
依据欧拉定理可知，因为
p
p
p
是素数，
γ
<
p
\gamma<p
γ
<
p
所以
(
γ
,
p
)
=
1
(\gamma,p)=1
(
γ
,
p
)
=
1
，于是有
γ
ϕ
(
p
)
≡
1
(
m
o
d
p
)
\gamma^{\phi(p)} \equiv 1 ( mod \ p)
γ
ϕ
(
p
)
≡
1
(
m
o
d
p
)
这样我们计算
γ
a
‾
\overline{\gamma^a}
γ
a
即可通过
γ
a
‾
=
γ
ϕ
(
p
)
−
a
=
γ
p
−
1
−
a
\overline{\gamma^a} = \gamma^{\phi(p)-a}=\gamma^{p-1-a}
γ
a
=
γ
ϕ
(
p
)
−
a
=
γ
p
−
1
−
a
得到
于是解密
D
(
C
)
=
γ
p
−
1
−
a
⋅
δ
(
m
o
d
p
)
D(C)=\gamma^{p-1-a} \cdot \delta (mod \ p)
D
(
C
)
=
γ
p
−
1
−
a
⋅
δ
(
m
o
d
p
)
在正确性上有
D
(
C
)
=
γ
a
‾
δ
=
r
k
a
‾
⋅
P
b
k
=
(
r
a
)
k
‾
⋅
P
b
k
=
b
k
‾
⋅
b
k
⋅
P
≡
P
(
m
o
d
p
)
D(C)= \overline{\gamma^a}\delta = \overline{r^{ka}} \cdot Pb^k=\overline{(r^a)^k} \cdot Pb^k=\overline{b^k} \cdot b^k \cdot P\equiv P (mod \ p)
D
(
C
)
=
γ
a
δ
=
r
ka
⋅
P
b
k
=
(
r
a
)
k
⋅
P
b
k
=
b
k
⋅
b
k
⋅
P
≡
P
(
m
o
d
p
)