好早之前的笔记了，拿来水一下（
前言
RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。
如今只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。
RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
根据密钥的使用方法，可以将密码分为对称密码和公钥密码
- 对称密码：加密和解密使用同一种密钥的方式
- 公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
RSA涉及变量名
n = p*q
p 大素数
q 大素数
m 明文
c 密文(ciper)
e 公钥 一般为 65537 //2^16+1
d 私钥欧拉定理
若整数 a 和 n 互素，则 a^φ(n) = 1 (mod n)
eg: 5^φ(n) = 5^8 = 1(mod 24)
其中 φ(24) = 8 ，即1，5，7，11，13，17，19，23，是小于24且与24互素的数。
φ(n) = (p-1)(q-1) 欧拉函数
欧拉定理-例题
计算 2^1000000 mod 77 = ?
显然，gcd(2,77) = 1，φ(77) = φ(7*11) = 6*10 = 60
根据欧拉定理，2^60 mod 77 = 1
又因为 1000000 = 16666*60+40
所以 2^1000000 mod 77 = 2^40 mod 77 →计算器→ = 23
密钥对生成
- 选取两个大素数p和q ，两个数长度接近且相差较大，目前安全的是1024位。
- 计算 n = p*q，φ(n) = (p-1)(q-1)
- 随机选取整数 e ，满足 gcd(e,φ(n)) = 1
- 计算 d ，满足 d*e = 1 modφ(n)
//n 公开，p 和 q 保密
加解密过程
加密算法：c = m^e (mod n)
解密算法：m = c^d (mod n)
RSA-例题1
取 p = 11, q = 13 ，这时 n =143 ，φ(n) =120
若选取e = 17 ( 满足 gcd(e,φ(n)) = 1 ) ，则私钥 d = e^-1 mod120 = 113
若要加密消息m = 24，计算
c = m^e mod n
= 24^17 mod 143
= 24^(2^4+1)mod 143
= 7
解密计算
m = c^d mod n
=7^113 mod 143
=7^(2^6+2^5+2^4) mpod 143
=24
RSA-例题2
p=43, q=59, n=p*q=43*59=2537
φ(2537)=42*58=2436
取e=13,解方程 de=1 (mod 2436） 得： d=937
若有明文： public key encryptions
先将明文分块为： p u b l i c k e y e n c r y p t i o n s
如利用英文字母表的顺序，即a为00 ，b为01……z为25 ，将明文数字化得： 1520 0111 0802 1004 24041302 1724 1519 0814 1418，加密得到密文： 0095 1648 1410 1299 1365 1379 2333 2132 1751 1289
RSA算法的安全基础
若n=p*q被因子分解,则RSA便被破解。
这是因为若p,q 已知，则φ(n)=(p-1)(q-1)便可算出。公钥e关于私钥d满足： d*e=1（modφ(n) ），故私钥d便不难求的。
因此， RSA 的安全性依赖大数的分解的困难性。目前因子分解速度最快的方法，其时间复杂性为： exp(sqrt(ln(n)lnln(n))).
随着计算机计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。目前密钥长度介于1024 比特和2048 比特之间的RSA算法是安全的。
例题
(1)取p = 3 ，q = 11，这时 n = ? φ(n) = ? ，若选取e = 3，求私钥；若要加密消息 m = 4， 求加解密过程。
解：
n = p*q = 33
φ(n) = φ(33) = 2*10 = 20
de = 1 mod 20 所以 de%20 = 1
瞪眼法求出 d 是 7
加密过程：
c = 64 mod 33，c是31
(2) buuctf上的rsarsa
题目内信息如下
Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
Use RSA to find the secret message看我竖式手算（bushi，真列竖式算就变成 长期竖式 和我算一辈子竖式吧
这么大的数当然要用程序算了
import gmpy2 as gp
import binascii
p = gp.mpz(9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483)
q = gp.mpz(11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407)
e = gp.mpz(65537)
c = gp.mpz(83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034)
n = p*q
phi = (p-1) * (q-1)
d = gp.invert(e, phi)
m = pow(c, d, n)
print(m)结果是5577446633554466577768879988