Rsa学习

参考

RSA 算法正确性证明

RSA 介绍 - CTF Wiki (ctf-wiki.org)

(41条消息) 对于RSA算法的一些理解_y=0 mod (p-1)/gcd(b-1,p-1)_lxp61666666的博客-CSDN博客

(41条消息) 【RSA原理2】浅谈–什么是欧拉函数_rsa 欧拉函数是什么_韦_恩的博客-CSDN博客

RSA中，e＊d＝1（mod（p-1）(q-1)）中为什么是mod（p-1）(q-1)而不是modpq？_百度知道 (baidu.com)

逆元

互为逆元的两个数可以取消其中一个数做的运算(一个运算中一般只有两个互为逆元的数)如e*d≡1mod(p*q)此处d取消了e做的运算

如果e乘了一个其他的数(a)那么再乘上d的值就是这个其他的数(a)

e*a*d=a

基本运算

^符号都是指 指数运算

≡符号指同余,可在≡符号右边的计算式中加入mod(num)表示等式两边取num的模同余 如 a≡b mod(c)

p,q 互不相等的质数(可以称为互素)

e 加密密钥

d 解密密钥

n 用于对加密结果取模,n=p*q

phi（n） 用于对解密结果取模(直接用n对解密结果取模必须要求a n为不相等的质数) phi(n)=(p-1)*(p+1)

加密运算

设flag为待加密的字符(明文),ec为已加密的数

一般通过bytes_to_long来转换为数

flag='密文'
m=bytes_to_long(bytes(flag.encode()))#此刻就转换为了大数

通过ec≡m^e( mod n )跟ec = m^e(mod n)一样

获得密文

解密运算

设ed为解密后的数

ed≡m^d(mod phi(n)) 跟ed = m^d(mod phi(n))

可通过Crypto.Util.number库的long_to_bytes转化为bytes数组再转化为字符串

flag=long_to_bytes(ed).encode()

隐含条件0≤ a,c＜p*q

python常用库

gmpy2 (41条消息) gmpy2常见函数使用_abtgu的博客-CSDN博客

​ 求逆元可用于求e对应的d或者d对应的e

import gmpy2
gmpy2.invert(e,phi(n))#e mod n的逆元
gmpy2.invert(e,(p-1)*(q-1))
#值为d