1 RSA介紹
- RSA是一種非對稱加密算法，即加密和解密時用到的密鑰不同。
- 加密密鑰是公鑰，可以公開；解密密鑰是私鑰，必須保密保存。
- 基于一個簡單的數論事實：兩個大質數相乘很容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，即公鑰；而兩個大質數組合成私鑰。
2 密鑰對的生成
step 1 生成N（公鑰和私鑰的一部分）
首先選取兩個互為質數的數
p
p
p和
q
q
q（
p
≠
q
,
g
c
d
(
p
,
q
)
=
1
p\neq q, gcd(p, q)=1
p?=q,gcd(p,q)=1），于是：
N
=
p
?
q
N = p * q
N=p?q
step 2 生成L
根據歐拉函數，不大于 N N N且與 N N N互質的數是 p ? 1 p-1 p?1和 q ? 1 q-1 q?1兩個數的最小公倍數：
L = [ p ? 1 , q ? 1 ] = ( p ? 1 ) ( q ? 1 ) L = [p-1, q-1] = (p-1)(q-1) L=[p?1,q?1]=(p?1)(q?1)
互質數 p p p和 q q q不能太小，如果他們足夠大，那么根據目前的計算機技術和其他工具，至今也沒能從 N N N分解出 p p p和 q q q。也就是說，只要密鑰長度 N N N足夠大（1024足夠），基本上不可能從公鑰信息推出私鑰信息。
step 3 生成E（加密密鑰）
滿足如下兩個條件：
1 < E < L 1 < E < L 1<E<L
g c d ( E , L ) = 1 gcd(E, L) = 1 gcd(E,L)=1
g c d ( E , L ) = 1 gcd(E, L) = 1 gcd(E,L)=1保證 E E E和 L L L最大公因數為1（互質），因此保證step 4生成解密密鑰 D D D時，一定存在 D D D滿足條件。
step 4 生成D（解密密鑰）
滿足如下兩個條件：
1 < D < L 1 < D < L 1<D<L
( E ? D ) m o d L ＝ 1 (E * D) mod L ＝ 1 (E?D)modL＝1
3 加密解密過程
另外，密鑰對為： ( E , D , N ) (E, D, N) (E,D,N)。
4 計算示例
明文信息為
p
l
a
i
n
t
e
x
t
=
85
，
E
=
7
，
p
=
11
，
q
=
13.
plaintext=85，E=7，p=11，q=13.
plaintext=85，E=7，p=11，q=13.
生成密鑰對
step 1:
N
=
p
?
q
=
11
?
13
=
143
N=p*q=11*13=143
N=p?q=11?13=143
step 2:
L
=
(
p
?
1
)
(
q
?
1
)
=
10
?
12
=
120
L=(p-1)(q-1)=10*12=120
L=(p?1)(q?1)=10?12=120
step 3:
(
E
?
D
)
m
o
d
L
=
1
?
(
7
?
D
)
m
o
d
120
=
1
?
D
=
103
(E*D)modL=1 \Rightarrow (7*D)mod120=1 \Rightarrow D=103
(E?D)modL=1?(7?D)mod120=1?D=103
加密
c
y
p
h
e
r
t
e
x
t
=
p
l
a
i
n
t
e
x
t
E
m
o
d
N
=
8
5
7
m
o
d
143
=
123
cyphertext = plaintext^E mod N=85^7mod143=123
cyphertext=plaintextEmodN=857mod143=123文章來源：http://www.zghlxwxcb.cn/news/detail-788744.html
解密
p
l
a
i
n
t
e
x
t
=
c
y
p
h
e
r
t
e
x
t
D
m
o
d
143
=
12
3
103
m
o
d
143
=
85
plaintext = cyphertext^D mod 143=123^{103}mod143=85
plaintext=cyphertextDmod143=123103mod143=85文章來源地址http://www.zghlxwxcb.cn/news/detail-788744.html
到了這里，關于【密碼學基礎】RSA加密算法的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
