[技术]RSA算法

前言

网络世界中,发送的许多消息都是经过加密的。加密方式主要分为对称加密和非对称加密。然而对称加密不仅需要传输密文,还需要传输秘钥。如果秘钥在传输过程中遭到泄露,那么别人就可以知道你发送了什么。所以,非对称性加密几乎成了现在的主流。而RSA算法就是现在非对称加密的主流算法之一。注意:base64之类的只是对字符进行编码,不能属于加密

RSA算法的实现

首先,我们随机找来两个质数p和q,在实际运用中,这两个质数大小都是1024比特(比特可以参考上一篇文章https://xcao.top/post-214.html)接着,我们可以求出n,n=pq,然后,我们需要计算n的欧拉函数即φ(n),这里 φ(n) 为(p-1)(q-1)。接着,需要找到公钥e,e的取值1<e< φ(n) e需要为正整数且e与 φ(n) 互质。接着还需要找到一个私钥d,d要求为正整数且ed除以 φ(n) 余数为1。

找到上述这些数字之后,我们就可以发送加密数据了。首先,需要接收方完成上述步骤,将公钥e,两质数积n传递给发送方。发送方收到这些数据后,便需要将发送的明文m进行一个运算。计算m的e次方,然后算出这个数与n的余数,将余数传递给接收方,这个算出来的数就是密文c。而接收方只需要一个简单的运算,算出密文c与的私钥d次方,算出这个数与n的余数。从数学定理上可以证明(具体的证明过程可以百度搜索,这里就不赘述了),算出来的这个余数一定等于明文m。这样就完成了一次安全的数据交换。为了更好的演示,我写了两个小程序去模拟RSA的信息传递过程。

#RSA算法接收方程序,by小草 https://xcao.top/?p=222
import random

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def coprime(a, b):
    return gcd(a, b) == 1


# 两个函数作用均为判断两数是否互质

p = 0
q = 0
while p == q:
    p = random.choice([2, 3, 5, 7, 11, 13, 17, 19])
    q = random.choice([2, 3, 5, 7, 11, 13, 17, 19])
n = p * q
n1 = (p - 1) * (q - 1) #φ(n)不方便打,以n1代替

# 随机取p和q(此处只取20以内的质数方便计算,并计算出n以及φ(n)
while True:
    e = random.randint(1, n1)
    if coprime(e, n1):
        break
for i in range(1, 10000):
    d = (i * n1 + 1) / e
    if e*d > n1:
        if d % 1 == 0:
            d = int(d)
            break
print('公钥是',e)
print('两质数积为',n)
# 计算出公钥以及私钥


c = int(input('请输入密文\n'))
m = pow(c,d)
m = m % n
print('明文是',m)
#RSA算法发送方程序,by小草 https://xcao.top/?p=222
e = int(input('请输入公钥\n'))
n=int(input('请输入两质数积\n'))
m = int(input('请输入明文\n'))
c = pow(m,e)
c = c % n
print('密文是',c)

RSA算法安全性

那么,RSA算法是否安全呢。首先,在这里需要交换的数据有公钥e,密文m以及两质数之和n。而解密需要密文m,两质数之和n以及私钥d。那么我们能不能去计算出私钥d呢?从上边的实现过程可以发现,想要知道私钥d,就需要知道 φ(n) 想要知道 φ(n) 就需要知道p和q,也就是说,只要有人有能力去把两质数之和n给质因数分解,那么我们就有办法去破解RSA。但实际应用中RSA的两个质数是长度为1024的二进制数,以目前技术几乎无法破解。但随着量子计算机发展,有朝一日人们可能是有办法去分解的。但我们也相信,到了那个时候,一定也会有更先进的技术去进行加密。综上所述,目前人们是几乎无法破解RSA的,使用RSA算法加密的数据基本是安全的

加入QQ群1014345230一起划水吧
转载请注明来源及链接
如需商业用途请联系作者

评论

  1. [email protected], [email protected]
    Windows Chrome 94.0.4606.81
    2月前
    2021-11-28 17:21:30

    写得好,所以我选择ECDSA

    • 小草 博主
      Windows Chrome 96.0.4664.45
      2月前
      2021-11-28 17:25:18

      看看能不能给ECDSA也写一篇文章

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇