RSA加密过程详解 | 公钥加密| 密码学| 信息安全

简介

RSA加密算法是一种非对称加密算法,所谓非对称,就是指该算法加密和解密使用不同的密钥,即使用加密密钥进行加密、解密密钥进行解密,分别称为公钥和私钥

在RAS算法中,公钥是公开的,而私钥是需要保密的。加密算法和解密算法也都是公开的。虽然私钥是由公钥决定的,但由于无法计算出大数n的欧拉函数phi(N),所以不能根据公钥计算出私钥,这就是RSA的安全性

使用方法:

  • 乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
  • 甲方获取乙方的公钥,然后用它对信息加密。
  • 乙方得到加密后的信息,用私钥解密。

数论基础

欧拉函数

φ(n)表示小于n且与n互素的正整数

  • 对于素数来说,φ(n) = n - 1
  • 对于不是素数的数来说,可以将n进行质因数分解,再套用

    φ

    (

    n

    )

    =

    n

    (

    1

    1

    p

    1

    )

    (

    1

    1

    p

    2

    )

    .

    .

    .

    .

    .

    .

    (

    1

    1

    p

    c

    )

    φ(n)=n*(1-frac{1}{p_1})(1-frac{1}{p_2})......(1-frac{1}{p_c})

    φ(n)=n(1p11)(1p21)......(1pc1)

欧拉函数的原理这里就不介绍了,只需要知道素数的欧拉函数等于它-1即可

欧拉定理

aφ(n) % n = 1

乘法逆元

(a*b)%n=1,就称ba在模n下的乘法逆元,求逆元的方法有两种,如果n是素数,那利用费马小定理可以知道逆元b = a n-1%n,如果不是素数,就只能用扩展欧几里得计算了,这里就不展开

RSA算法流程

密钥的产生

  • 取两个保密的大素数p和q
  • 计算n = p * q, n的欧拉函数值为φ(n) = (p - 1) * (q - 1)
  • 任取一个整数 e, 1<e<n,且与φ(n)互素
  • 计算e在模φ(n)意义下的乘法逆元
  • 公钥为(e, n), 私钥为(d, n)

加密

=

e

m

o

d

N

密文=明文^emodN

=emodN

也就是

c

=

m

e

m

o

d

N

c = m^emodN

c=memodN,m为明文,c为密文

解密

=

d

m

o

d

N

明文 = 密文^{d}modN

=dmodN

也就是

m

=

c

d

m

o

d

N

m = c^dmodN

m=cdmodN

RSA解密的正确性证明

在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>