RSA公开密钥算法

RSA算法是Merkle背包算法出现后的第一个较为完善的公开密钥算法。

包含公开密钥和私人密钥，如果Alice想发送消息给Bob，应该怎么做呢？

Alice用公开密钥对消息加密
Alice将加密后的密文发送给Bob
Bob用私人密钥对密文进行解密

产生两个密钥的方法:

选取两个大素数
p

p

p和

q

q

q，为了安全，两数的长度一样长
计算乘积
n

=

p

q

n=pq

n=pq
然后随机选取加密密钥
e

e

e，并且

e

e

e和

(

p

−

1

)

(

q

−

1

)

(p-1)(q-1)

(p−1)(q−1)互素
最后使用扩展欧几里得算法，得到解密密钥
d

d

d

e

d

=

1

m

o

d

(

p

−

1

)

(

q

−

1

)

ed=1 \ \mathrm{mod}\ (p-1)(q-1)

ed=1 mod (p−1)(q−1)

d

d

d是

e

e

e模

(

p

−

1

)

(

q

−

1

)

(p-1)(q-1)

(p−1)(q−1)的逆

d

,

n

d,n

d,n也互素，

e

e

e和

n

n

n就是公开密钥，

d

d

d就是私人密钥

公开密钥

私人密钥

加密

(

)

解密

(

)

\begin{array}{|c|c|c|} \hline 公开密钥& n,e \\ \hline 私人密钥& d\\ \hline 加密&C=P^e \pmod{n} \\ \hline 解密&P=C^d \pmod{n} \\ \hline \end{array}

公开密钥私人密钥加密解密n,edC=Pe(modn)P=Cd(modn)

例如我们需要加密消息

857

P=857

取素数
p

=

37

,

q

=

91

p=37,q=91

p=37,q=91
计算乘积
n

=

p

q

=

3367

n=pq=3367

n=pq=3367
随机选取加密密钥
e

e

e，与

(

p

−

1

)

(

q

−

1

)

=

3240

(p-1)(q-1)=3240

(p−1)(q−1)=3240互素，

e

=

137

e=137

e=137
扩展欧几里得算法
e

x

t

e

n

d

extend

extend_

g

c

d

(

e

,

(

p

−

1

)

(

q

−

1

)

,

d

,

y

)

gcd(e,(p-1)(q-1),d,y)

gcd(e,(p−1)(q−1),d,y)，求出

d

=

473

d=473

d=473
加密：密文
C

=

P

e

(

m

o

d

n

)

=

85

7

137

(

m

o

d

3367

)

=

376

C=P^e \pmod n=857^{137}\pmod {3367}=376

C=Pe(modn)=857137(mod3367)=376
解密：明文
P

=

C

d

(

m

o

d

n

)

=

37

6

473

(

m

o

d

3367

)

=

857

P=C^d\pmod{n}=376^{473}\pmod {3367}=857

P=Cd(modn)=376473(mod3367)=857

解密原理:

欧拉定理&费马小定理

定义：

a

,

m

∈

N

+

，

a,m\in N^+，

a,m∈N+，且

g

c

d

(

a

,

m

)

=

1

，

gcd(a,m)=1，

gcd(a,m)=1，则有

a

φ

(

m

)

≡

1

(

m

o

d

m

)

a^{\varphi(m)}\equiv 1\pmod{m}

aφ(m)≡1(modm)其中

φ

(

m

)

\varphi(m)

φ(m)是小于

m

m

m且与

m

m

m互质的自然数的个数当

m

m

m是素数

，

a

φ

(

m

)

=

m

−

1

，

a

m

−

1

≡

1

(

m

o

d

m

)

，a^{\varphi(m)}=m-1，a^{m-1}\equiv 1\pmod{m}

，aφ(m)=m−1，am−1≡1(modm)什么？这不是费马小定理吗?

所以费马小定理是欧拉定理的一个特殊情况
设
a

,

m

a,m

a,m是互素的正整数,那么

φ

(

a

m

)

=

φ

(

a

)

φ

(

m

)

，

\varphi(am)=\varphi(a)\varphi(m)，

φ(am)=φ(a)φ(m)，这说明欧拉函数是一个积性函数

那有

，

(

)

(

)

(

)

(

)

(

−

)

(

−

)

n=pq，\varphi(n)=\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)

n=pq，φ(n)=φ(pq)=φ(p)φ(q)=(p−1)(q−1)

(

)

C^d\pmod{n}

Cd(modn)

(

)

=P^{ed}\pmod{n}

=Ped(modn)

(

−

)

(

−

)

(

)

=P^{k(p-1)(q-1)+1}\pmod{n}

=Pk(p−1)(q−1)+1(modn)

∗

(

−

)

(

−

)

(

)

=P*P^{k(p-1)(q-1)}\pmod{n}

=P∗Pk(p−1)(q−1)(modn)

∗

(

)

(

)

(

)

=P*(P^{\varphi(n)}\pmod n)^k \pmod{n}

=P∗(Pφ(n)(modn))k(modn)

∗

(

)

=P*1^k \pmod{n}

=P∗1k(modn)

不过，既然我们知道公开密钥

e和

n，还知道

(

−

)

(

−

)

，

−

(

−

)

(

−

)

n=pq,gcd(e,(p-1)(q-1))=1，d=e^{-1} \mathrm{mod}\ (p-1)(q-1)

n=pq,gcd(e,(p−1)(q−1))=1，d=e−1mod (p−1)(q−1)，那我们通过分解

n，得到正确的

p和

q，就可以得到私人密钥

d(其实还可以猜测

(

−

)

(

−

)

(p-1)(q-1)

(p−1)(q−1)，这显然比分解

n还要难)

这个想法的确很美好,

But

But难度极其大

1976

1976年,

Richard Guy

RichardGuy说道，“本世纪如果有人不采用特殊的方式成功地对

10^{80}

1080大小的数进行因子分解的话那我将非常惊讶”。

1977

1977年,

Ron Rivest

RonRivest说，分解一个

125

125位的十进制数大约需要

∗

40*10^{50}

40∗1050年。

1994

1994年，一个

129

129位的数据被成功分解。

两个大素数进行相乘是一个单向函数，得到乘积很容易，但是想分解却特别困难了，目前，

129

129位十进制数字的模数被认为是能分解的临界数，所以

n更应该大于这个数

随着密钥长度的增加，分解的难度更大，但是解密时间也会增加

现今，有很多针对RSA的攻击方法，例如选择密文攻击，公共模数攻击，低加密指数攻击，加密和签名攻击

谢谢🙏

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/3d7b5a7862.html

RSA公开密钥算法