2025年RSA密码

大家好，我是讯享网，很高兴认识大家。

一、什么是RSA

RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。[百度百科]

RSA是一种非对称密码也就是公钥密码，顾名思义就是加密和解密使用的密钥不同，其中一个称为公钥，即可以公开的密钥；另一个称为私钥，即必须持有者保密的密钥；而且由公钥不可能计算出私钥。

任何人都可以生成自己的私钥和公钥，把公钥公开，把私钥自己保管。当别人想把加密文件的密码发送给我的时候，就可以用我的公钥对密码进行加密，然后发给我，然后我用我的私钥解密就可以拿到加密文件的密码。因为只有我拥有我的私钥，所以除了我之外的其他人，是不可能获得加密文件密码的。

如此一来，公钥密码就解决了密钥分发问题，也保障了很好地安全性。

二、数学基础

1.整除

如果a整除b，记为a|b。

若c=
讯享网a+b，e|a，且e|b，则e|c。

2.最大公因子

所有同时整除a和b的整数中，最大的那个，称为a和b的最大公因子，记为(a,b)。

根据这个结论，对任意正整数a和b，首先a一定可以表示成a=kb+c，0≤c<b也就是说k=，a mod b =c。
其次(a,b)=(b,c)，也就是说， a和b的最大公因子，b和c的最大公因子，是相同的。

欧几里得算法（求最大公因子）

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

讯享网

扩展欧几里得算法（对于任意两个整数 a, b，必存在整数 x, y，使得 xa + yb = gcd(a,b) 成立，求出整数解 x, y，可以得到 gcd(a,b)）

讯享网def egcd(a, b): if b == 0: return a, 1, 0 gcd, x, y = egcd(b, a % b) return gcd, y, x - a / b * y

3.互素

最大公因子的最小可能取值是1，当(a,b)=1，即a和b的最大公因子为1时，我们称a和b互素。

4.乘法逆元

扩展欧几里得算法可以帮我们解决这个问题。

由于(a,b)=1，根据扩展欧几里得算法，可求得两个系数和，使得a+b=(a,b)=1，所以有a=-b+1，所以a mod b =1，所以( mod b)a mod b =1，而0≤( mod b)<b，所以(1 mod b)就是我们想要的那个乘法逆元。

5.欧拉函数

对任意一个正整数，在到的这个整数里，显然有些和是互素的，而有些和是不互素的，那些和互素的整数的数量就是n的欧拉函数，记作φ(n)。

特殊的，φ(1)=1。

如果n是质数，则φ(n)=n-1。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则φ(p^k)=p^k-p^(k-1)

如果n可以分解成两个互质的整数之积,即n=p1p2，则φ(n)=φ(p1p2)=φ(p1)φ(p2)

6.欧拉定理（RSA直接数学基础）

当(a,n)=1时，a^φ(n)≡1 (mod n)

推论

a^(φ(n)+1)≡a (mod n)

三、RSA计算

C=M^E mod N

M=C^D mod N (C代表密文，M代表明文)

N=p*q (p q为随机生成的两个质数)

E为随机生成的质数(较p q小)

E*D mod φ(n) =1 (由欧拉定理的推论得出，本文中没有详写)，所以

D = gmpy2.invert(E,(p-1)*(q-1))

至此，RSA密码的加解密都可计算。

四、例题

已知：

讯享网p =  q =  e = 65533 c =

求m。

import gmpy2 import libnum from Crypto.Util.number import * #from binascii import a2b_hex,b2a_hex p =  q =  e = 65533 n = p*q d = gmpy2.invert(e,(p-1)*(q-1)) #print(d) #c = pow(int(b2a_hex(flag),16),e,n) #print c c =  # c = m^e % n # m = c^d % n m = pow(c,d,n) print(m) #m=9

一、什么是RSA

二、数学基础

三、RSA计算

四、例题

相关推荐