常见的加密算法原理与实现:RSA加密

article/2025/3/18 17:48:37

系列四:RSA加密

  • 一、基本背景
  • 二、算法原理
    • 2.1、生成公钥和私钥
    • 2.2、加密消息
    • 2.3、解密消息
  • 三、Python实现RSA算法
    • 3.1、基于pycryptodome库实现RSA加解密
    • 3.2、基于rsa库实现RSA加解密
  • 四、参考文献

一、基本背景

RSA算法是是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的,算法的名字就是三人名字首字母拼凑而成的。

RSA是目前应用最为广泛的非对称加密算法之一,这里延伸一下,所谓的非对称加密,通俗来讲就是数据加密和解密用的不是同一个秘钥。维基百科官方解释如下:

公开密钥密码学(英语:Public-key cryptography)也称非对称式密码学(英语:Asymmetric cryptography)是密码学的一种算法,它需要两个密钥,一个是公开密钥,另一个是私有密钥;公钥用作加密,私钥则用作解密。使用公钥把明文加密后所得的密文,只能用相对应的私钥才能解密并得到原本的明文,最初用来加密的公钥不能用作解密。由于加密和解密需要两个不同的密钥,故被称为非对称加密;不同于加密和解密都使用同一个密钥的对称加密。公钥可以公开,可任意向外发布;私钥不可以公开,必须由用户自行严格秘密保管,绝不透过任何途径向任何人提供,也不会透露给被信任的要通信的另一方。

下图很生动的说明了非对称加密的过程,原文经过公钥加密后,生成密文,而密文的解密只能用私钥完成。而正是因为加密和解密的规则不同,这样就避免了传统加密算法需要传递秘钥可能带来的因秘钥泄露导致不安全问题。
在这里插入图片描述

二、算法原理

RSA算法的加密涉及到几个重要的数学概念,包括我们小学学过的质数(又叫素数)、欧拉定理、欧拉函数、模反元素,当然最核心的还是互质关系,在加密过程中会多次用到。

看很多教程里都已Alice和Bob来作为故事的主人公,外国人名字太拗口了,为了方便自己理解记忆,我这里就用小王和小张了。

2.1、生成公钥和私钥

假设小王要给小张用rsa算法发送一条加密信息,他首先生成公钥和私钥,具体包含以下这么几个步骤:

  1. 随意选择两个不相等的质数 pq,小王选的是3和11(实际应用中,两个数越大越安全);
  2. 计算 pq的乘积 ,n= p* q,n为33,这里的n就是秘钥的长度,33转换成二进制是100001,长度是6位,所以秘钥长度是6位;(注:实际应用中,RSA密钥一般是1024位,重要场合则为2048位。)
  3. 计算n的欧拉函数φ(n),把33带入欧拉函数计算结果为20:
    φ(n) = φ(p * q) = φ( p)* φ(q) =(p-1) * (q-1)
    φ(33) = φ(3 * 11) = φ(3) * φ(11) =(3-1) * (11-1)=20
  4. 随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质,小王在1到20之间选了7;
  5. 计算e对于φ(n)的模反元素d,ed ≡ 1 (mod φ(n)),这个公式的意思就是找到整数d,使得ed被φ(n)除的余数为1。设ed是φ(n)的k的整数倍,余数为1,上式等价于:
    7 * d = 20k + 1,即7d -20k = 1,也就是一个二元一次方程,该公式可以用扩展欧几里得方法进行求解,这里因为数字比较小,所一眼就能看出来d=3,k=1;
  6. 至此,所有计算就完成,将n和e封装成公钥,n和d封装成私钥,即加密公钥为(33,7),私钥为(33,3)。

2.2、加密消息

生成公钥和秘钥以后,小王就要开始用公钥对信息进行加密了。假设他要发送的信息是m,注意m必须是一个整数,且小于n。如果m是字符串的话,就需要使用事先与小张约好的格式将m转换为一个小于n的非负整数 ,通常取字符串的ascii值或unicode值。

加密的过程其实就是算出下式中的c:

小王设定的m是数字2,那加密结果就是2的7次方除以33的余数,也就是29,然后小王把29发送给了小张。

2.3、解密消息

小张收到小王的加密信息后,就用自己的私钥(33,3)进行解密,解密公式如下:

可以得出,29的3次方除以33的余数一定为2,因此小张就得出了加密前的原文是数字2。

三、Python实现RSA算法

目前有很多库支持实现RSA加密,这里介绍两个比较常见的库:pycryptodomersa

3.1、基于pycryptodome库实现RSA加解密

安装对应的库:

pip install pycryptodome

加解密实现过程:


from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import binascii# 生成公钥和私钥,秘钥长度长度设为512位
keyPair = RSA.generate(1024)pubKey = keyPair.publickey()
print(f"Public key:  (n={hex(pubKey.n)}, e={hex(pubKey.e)})")
pubKeyPEM = pubKey.exportKey()
print(pubKeyPEM.decode('ascii'))print(f"Private key: (n={hex(pubKey.n)}, d={hex(keyPair.d)})")
privKeyPEM = keyPair.exportKey()
print(privKeyPEM.decode('ascii'))# 使用公钥进行加密
msg = b'hello kitty!'
encryptor = PKCS1_OAEP.new(pubKey)
encrypted = encryptor.encrypt(msg)
print("Encrypted:", binascii.hexlify(encrypted))# 使用私钥进行解密
decryptor = PKCS1_OAEP.new(keyPair)
decrypted = decryptor.decrypt(encrypted)
print('Decrypted:', decrypted)

输出结果:

Public key:  (n=0xd3357728da47ae241c59bf1956d0f47f291e236c32c134a04cf2e86c75200a57ffbf99bdf9e3633595b8e188ed5463ca6e274a6a9a9d7bcf6714180c9edfdc86f59db3bcd226f10b58b383d1429466e5ddae92c891ce122d52443ca7ec1b845c1e09784d0b26b0482fcb9a605fdc073ae6f6d773d114524768b2cf7733ea7b19, e=0x10001)
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDTNXco2keuJBxZvxlW0PR/KR4j
bDLBNKBM8uhsdSAKV/+/mb3542M1lbjhiO1UY8puJ0pqmp17z2cUGAye39yG9Z2z
vNIm8QtYs4PRQpRm5d2uksiRzhItUkQ8p+wbhFweCXhNCyawSC/LmmBf3Ac65vbX
c9EUUkdoss93M+p7GQIDAQAB
-----END PUBLIC KEY-----
Private key: (n=0xd3357728da47ae241c59bf1956d0f47f291e236c32c134a04cf2e86c75200a57ffbf99bdf9e3633595b8e188ed5463ca6e274a6a9a9d7bcf6714180c9edfdc86f59db3bcd226f10b58b383d1429466e5ddae92c891ce122d52443ca7ec1b845c1e09784d0b26b0482fcb9a605fdc073ae6f6d773d114524768b2cf7733ea7b19, d=0x2e7efa23bbf055e60cabfa87b583af6d5abbedea874fbc6e66356e16f0262f6d8f6ccbbae468ee892b7ea24c2aced281a5a64e0022fa16c62ef1b53ab64ce385b13e7aa44c246a046c69d7c9c58ae8d9cee1f1256170d55df3de3657f14606763e04ed9a1ac652ccc234df80ede1f420cf54d551d0dd0aaea25e85d430278a5)
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDTNXco2keuJBxZvxlW0PR/KR4jbDLBNKBM8uhsdSAKV/+/mb35
42M1lbjhiO1UY8puJ0pqmp17z2cUGAye39yG9Z2zvNIm8QtYs4PRQpRm5d2uksiR
zhItUkQ8p+wbhFweCXhNCyawSC/LmmBf3Ac65vbXc9EUUkdoss93M+p7GQIDAQAB
AoGAAufvoju/BV5gyr+oe1g69tWrvt6odPvG5mNW4W8CYvbY9sy7rkaO6JK36iTC
rO0oGlpk4AIvoWxi7xtTq2TOOFsT56pEwkagRsadfJxYro2c7h8SVhcNVd8942V/
FGBnY+BO2aGsZSzMI034Dt4fQgz1TVUdDdCq6iXoXUMCeKUCQQDc4eX8MD3gCH0l
CVnM3oCokfrkMnKMdWbfPiAZ2d4+qYqSFxthh8pFHKag7Sroj6JB1Df/LmOIjge1
DA14Tii1AkEA9MnYQUMWoeVHdgHRyJfnt5nhBVELkihrkandiGoHoPZ++oCRd+lC
AhPUeMbi48nXWsfB9aeBCyfCtrowq8h7VQJATbMxggs+WObjjvnBGy5SN/pSNaAB
Z6OM8o8aH73iTky5sDZsrVxlLPatLwL/CxwrydhrclrRLKI519hLjLyB2QJAZFcY
viex70r8r/Ku+3rJEQmSo4tFIvROo7btiC1uUxy3kBeDiZOj6xYV0iw0dQsXq66W
Ywv2aYwy1JQdv0y+wQJBAIdKhGaw+1FPXsYkxE8FTFZKYyPPPm1WeHml4Sxnoefq
HLuIv5/J1ZmThRtFrtMrUi4CLIN+T/P8QyW0CRbMyeE=
-----END RSA PRIVATE KEY-----
Encrypted: b'328ad919abfaddb41ef23a1edcdfa082e5d06a3c6f069711ea2f9acb065e010d336ac05f6e3d8a8b654c313cf8c45fed6cab63f072f088b58f5e60a63238987a8538ee9febcb475687bd052d8e0b0c73f485e4de2cc6fe01507a3a7c202b1e8cca54e3e1cd86ee7a3cbac9037e287b2b0bd30236fec6ff5d51c609f9ac07ddb5'
Decrypted: b'hello kitty!'

3.2、基于rsa库实现RSA加解密

安装对应的库:

pip install rsa

加解密实现过程:

import rsa#生成公钥和私钥,秘钥长度长度设为512位
(pub_key, priv_key) = rsa.newkeys(512)#对要加密的信息先做编码预处理
message = 'hello kitty!'.encode('utf8')#使用公钥进行加密
crypto = rsa.encrypt(message, pub_key)#使用私钥进行解密
message = rsa.decrypt(crypto, priv_key)print('公钥:',pub_key)
print('公钥:',priv_key)
print('加密结果:',crypto)
print('解密结果:',message.decode('utf8'))

输出结果:

公钥: PublicKey(7314317358276496179673675826113974816867276788014695748377826142338549872987934756025496125702108198463672589083200012256019911170396983233914797109169127, 65537)
公钥: PrivateKey(7314317358276496179673675826113974816867276788014695748377826142338549872987934756025496125702108198463672589083200012256019911170396983233914797109169127, 65537, 943181653032556711696022619382779211397307721371319922632116342354747469961338103051165777010084765246227308796305985673201500446076915010752259511551713, 4468680789217211695491298837720072527208283405518529890430453910323843023628553431, 1636795668181472565104977515834979867527383910843535218329587708682536817)
加密结果: b'\x0e\xd7\x02|\x17>\xb1\xd0\xebyD\x18\x9f\xdf\xa8\xe7n\xe0\xd3\xe3~#\xa8\xbe\xcdA\xa8k\xef\xc3T\xb70\xdd\x85\xcc\x9e\xf518\x83\xf2\n\x1c\xf5\xf2\x89\xaaDp\x1d\xb5\x90\xe8\x1c\x96\xfc\xd2\xb0\xf7H*\xcc;'
解密结果: hello kitty!

四、参考文献

1、维基百科,RSA加密算法
2、RSA Encrypt / Decrypt - Examples
3、Python-RSA 4.7 documentation
4、阮一峰,RSA算法原理(一)
5、阮一峰,RSA算法原理(二)
6、五分钟知识科普:什么是 RSA 算法


http://chatgpt.dhexx.cn/article/k58ge9bO.shtml

相关文章

RSA加密和解密原理及过程(非对称加密)

非对称加密 用公钥来加密数据发送出去&#xff0c;接收方收到数据后用私钥解密数据。公钥是所有人都知道的&#xff0c;私钥只有接收方才知道。 加密解密基本流程 注意&#xff1a;公钥私钥中的33是同一个数字&#xff0c;是公开的&#xff0c;只有私钥的3是只有接收方才知道…

关于RSA加密解密原理

前言&#xff1a; 随着我们的学习的不断深入&#xff0c;信息的安全也愈加重要&#xff0c;我们发布的代码中可能含有我们的私密信息&#xff0c;比如对接支付宝沙箱api&#xff0c;下载一些专业软件时就需要我们输入公钥和私钥以此来验证我们的身份信息&#xff0c;就相当于用…

RSA加密解密原理及工具类

1. 什么是RSA RSA算法是现今使用最广泛的公钥密码算法&#xff0c;也是号称地球上最安全的加密算法。 RSA是被研究得最广泛的公钥算法&#xff0c;从提出到现在已近三十年&#xff0c;经历了各种攻击的考验&#xff0c;逐渐为人们接受&#xff0c;普遍认为是目前最优秀的公钥…

RSA 非对称加密原理(小白也能看懂哦~)

RSA 加密原理 步骤说明描述备注1找出质数P 、Q-2计算公共模数N P * Q-3欧拉函数φ(N) (P-1)(Q-1)-4计算公钥E1 < E < φ(N)E的取值必须是整数 E 和 φ(N) 必须是互质数5计算私钥DE * D % φ(N) 1-6加密C &#xff1d; M E mod NC&#xff1a;密文 M&#xff1a;明文7…

RSA加密的原理——为什么被公钥加密的可以被私钥解密?

RSA加密的原理——为什么被公钥加密的可以被私钥解密&#xff1f; 目录 一&#xff0c;RSA 数学理论基础 二&#xff0c;RSA实现原理 三&#xff0c;RSA加密的过程 四&#xff0c;参考文献 引言 在密码学最开始&#xff0c;都是使用的普通加密模式 A 用加密规则加密了字符串m…

关于RSA加密原理

什么是RSA RSA算法是现今使用最广泛的公钥密码算法&#xff0c;也是号称地球上最安全的加密算法。在了解RSA算法之前&#xff0c;先熟悉下几个术语 根据密钥的使用方法&#xff0c;可以将密码分为对称密码和公钥密码 对称密码&#xff1a;加密和解密使用同一种密钥的方式 公钥密…

RSA加密原理与RSA公钥加密系统、数字签名

通过公钥加密系统&#xff0c;可以对传输于两个通信单位之间的消息进行加密&#xff0c;即使窃听者窃听到加密之后的消息&#xff0c;也不能对其破译。 1、RSA公钥加密原理 1.1 几个核心概念 公钥P与公钥函数P()密钥S与密钥函数S() 可以简单理解&#xff0c;一个公钥对应一个…

RSA加密解密原理

引言&#xff1a; CTF密码学类题目中&#xff0c;RSA加密可谓是很重要且常见的加密类型&#xff0c;今天就总结下 RSA加密的原理及解密方法。 文章目录 RSA算法简介:1、什么是非对称加密算法&#xff1a;2、RSA 加密原理&#xff1a;3、RSA加密算法过程详解&#xff1a…

# RSA加密原理和一些知识笔记

RSA加密原理和一些知识笔记 原文地址&#xff1a; 01&#xff1a;RSA 加密和原理 .pem .csr .crt .der .p12文件的区别 base64 (https://www.cnblogs.com/zyzmlc/p/12875277.html) 写得不错&#xff0c;这应该是他的学习笔记&#xff0c;我做了一些错误修正 复习&#xff1a;…

Rsa加密原理与简单实现

源码&#xff1a;https://gitee.com/Cheney822/programmes/blob/master/rsa.py 1背景 1.1 数据加密 指的是根据一定规则&#xff0c;将数据处理成不规则的数据&#xff0c;使得人们除非有了关键的钥匙以及得知这个规则&#xff0c;难于得知无规则数据的真实含义。这个一定规则…

RSA加密原理简述

RSA加密原理简述 RSA简介&#xff1a;前置技能&#xff08;数论知识&#xff09;RSA加密原理 RSA简介&#xff1a; RSA加密算法使用不同的加密密钥与解密密钥&#xff0c;且由已知加密密钥推导出解密密钥在计算上是不可行的&#xff0c;以此来保障安全。 RSA算法通常是先生成一…

RSA加密基本原理

工作中遇到RSA加密的内容&#xff0c;特意学习了一下&#xff0c;作为自己的笔记吧。&#xff08;公钥和私钥得到不在本次文章范围内&#xff0c;此处只有基本原理&#xff09;方便自己更好的理解。 笔记来源于bilibili的视频&#xff0c;地址如下&#xff1a; https://www.bil…

非对称加密算法--RSA加密原理详解

密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用&#xff0c;已成为一门综合性的尖端技术科学。 密码学发展史 在说RSA加密算法之前&#xff0c; 先说下密码学的发展史。其实密码学的诞生&#xff0c;就是为了运用在战场&#xff0c;在公元前&#…

密码学——RSA加密算法原理

前言&#xff1a;之前在做密码学题的时候了解了一下RSA&#xff0c;但总感觉那时总结的过少&#xff0c;而且也理解的不到位&#xff0c;这次就再来详细的了解一下&#xff0c;并通过做题来巩固一下。 一、对称加密与非对称加密 对称加密&#xff1a; 加密和解密用的是同一密…

如何利用好大数据挖掘潜在用户?

就目前而言&#xff0c;现在的大数据技术为绝大部分的业务提供了许多功能&#xff0c;同时还提高了效率和收入。当然除了这些以外&#xff0c;大数据分析还为公司的潜在客户和现有客户提供了许多好处。这些优点让很多公司对于大数据技术十分向往&#xff0c;那么怎么能够利用好…

激发客户潜在需求

企业不光要看到客户的显现需求&#xff0c;更要挖掘客户的潜在需求&#xff0c;因为客户的潜在需求是可以转化为显现需求的&#xff0c;满足客户的潜在需求可以为企业带来更多经济效益。 前言 潜在需求是指消费者虽然有明确意识的欲望&#xff0c;但由于种种原因还没有明确的显…

HubSpot入站营销:吸引潜在客户的7大技巧!

入站营销是当今数字化时代的重要策略之一。它不仅可以帮助企业吸引潜在客户、建立品牌知名度&#xff0c;还能促进客户参与并提高客户满意度。今天运营坛将带领大家深入探讨HubSpot入站营销的理论和实践&#xff0c;包括如何开始入站营销、入站营销的框架以及关键技巧。 一、什…

Python决策树、随机森林、朴素贝叶斯、KNN(K-最近邻居)分类分析银行拉新活动挖掘潜在贷款客户

最近我们被客户要求撰写关于银行拉新活动的研究报告&#xff0c;包括一些图形和统计输出。 项目背景&#xff1a;银行的主要盈利业务靠的是贷款&#xff0c;这些客户中的大多数是存款大小不等的责任客户&#xff08;存款人&#xff09;。银行拥有不断增长的客户。该银行希望增…

潜在客户需要单独管理吗?

通常销售型企业会将客户类型区分为&#xff1a;潜在客户、意向客户和购买客户等状态。那么&#xff0c;潜在客户需要单独拿出来进行管理吗&#xff1f;。 企业从展会、网站、广告及其它市场活动收集来的潜在客户是客户挖掘、获得、细分的主要目标受众&#xff0c;这些线索客户的…

python数据分析与挖掘实战---航空公司客户价值分析

航空公司客户价值分析 一、 背景与挖掘目标 **** 客户关系管理是企业的核心问题&#xff0c;关键在于客户的分类&#xff1a;区别无价值客户&#xff0c;高价值客户&#xff0c;针对不同客户群体有的放矢投放具体服务方案&#xff0c;实现企业利润最大化的目标。 各大航空公…