概述

RSA是目前使用最广泛的公钥密码体制之一。它是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA算法的安全性基于RSA问题的困难性，也就是基于大整数因子分解的困难性上。但是RSA问题不会比因子分解问题更加困难，也就是说，在没有解决因子分解问题的情况下可能解决RSA问题，因此RSA算法并不是完全基于大整数因子分解的困难性上的。

注:RSA的相关证明涉及到中国剩余定理的利用

算法描述

RSA产生公私钥对

1.选取两个大素数 p,q,为了最大的安全性,p,q的位数相等

2.计算乘积 n=p*q

3.随机取加密密钥 e,使得e和(p-1)(q-1)互素,然后使用欧几里得算法计算解密密钥d

一般情况下 e 取 65537

即有公式 d = e^-1 mod (p-1)(q-1)

注意:

d和n也互素,至此,e和n为公钥,d为私钥

实际应用中，e 常常选择65537 (?)

RSA的加解密算法

设有明文m,密文为c,其中0<=m<n,0<=c<n

则加密算法为:

c = m^e mod n

解密算法为:

m = c^d mod n

RSA对明文的加解密的过程

1.首先对于明文M,要对其进行比特串分组,确保每个分组m的十进制数都小于n(即0<=m<n)

2.然后对每个分组进行加密,整合为密文C

3.对与密文C同理分组为c,有0<=c<n

4.对其进行解密,最终整合为明文M

加解密脚本

CTF中,往往只会给出n,不可能直接给你p和q,当n较小时,我们使用大数分解在线网站等工具可以直接分解出p和q,此时加密即被破解.

import gmpy2

# 已知公私钥
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 6376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

# c = input('请输入密文')
n = p * q
phi_n = (p - 1) * (q - 1)  # 对n取欧拉函数,p,q均为素数
d = gmpy2.invert(e, phi_n)  # 即e*d mod phi_n = 1 (求逆元)
m = gmpy2.powmod(c, d, n)  # 即m = c^d mod n (求大整数c的d次幂模n取余)
# print(m)  # 求得的明文
flag = str(hex(m))[2:]
# print(flag)
print(binascii.unhexlify(flag).decode())
# print(binascii.unhexlify(flag))

import gmpy2

# 如果已知公私钥
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
m = 123456

# c = input('请输入明文')
n = p * q
phi_n = (p - 1) * (q - 1)  # 对n取欧拉函数,p,q均为素数
d = gmpy2.invert(e, phi_n)  # 即e*d mod phi_n = 1 (求逆元)
c = gmpy2.powmod(m, e, n)  # 即c = m^e mod n (求大整数m的e次幂模n取余)
print(c)  # 求得的密文