RSA 加密算法的实现与破解

实验二：实现RSA加密算法，根据已知明文计算出RSA的加密密文，并解密。

1、 选择一对不同的、足够大的素数 p，q。
2、 计算 n=pq。
3、 计算 f(n)=(p-1)(q-1)，同时对 p, q 严加保密，不让任何人知道。
4、 找一个与 f(n) 互质的数 e，且 1 5、 计算 d，使得 de ≡ 1 mod f(n)。这个公式也可以表达为 d ≡ e-1 mod f(n)。
这里要解释一下，≡ 是数论中表示同余的符号。公式中，≡ 符号的左边必须和符号右边同余，也就是两边模运算结果相同。显而易见，不管 f(n) 取什么值，符号右边 1 mod f(n) 的结果都等于 1；符号的左边 d 与 e 的乘积做模运算后的结果也必须等于 1。这就需要计算出 d 的值，让这个同余等式能够成立。
6、 公钥 KU=(e,n)，私钥 KR=(d,n)。
7、 加密时，先将明文变换成 0 至 n-1 的一个整数 M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为 C，则加密过程为：
8、 解密过程为：

RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

大素数生成算法可参考上次实验：https://blog.csdn.net/qq_45927266/article/details/120748887

代码思想：先将明文转化为数字（ASCII），再将数字尽可能化小（1-26），然后利用循环将若干个字符分为一组（该代码并未实现这一功能，仅用于短加密），最后依次组合每组的数字进行RSA加密。需要注意的是，该代码编写较为简单，仅针对大写字母进行加解密，代码如下：

#include
#include
#include
#include
using namespace std;
typedef long long ll;

ll Quick_Multiply(ll a,ll b,ll c) 
{
    ll ans=0,res=a;
    while(b)
    {
        if(b&1)
        	ans=(ans+res)%c;
        res=(res+res)%c;
        b>>=1;
    }
    return ans;
}

ll Quick_Power(ll a,ll b,ll c)
{
    ll ans=1,res=a;
    while(b)
    {
        if(b&1)
        	ans=Quick_Multiply(ans,res,c);
        res=Quick_Multiply(res,res,c);
        b>>=1;
    }
    return ans;
}

int main()
{
	ll p,q,n,r,e,d = 1;
	string plaintext,temp,hide,seek;
	cout<<"Please enter a prime number p:";
	cin>>p;
	cout<<"Please enter a prime number q:";
	cin>>q;
	n = p*q;
	r = (p - 1)*(q - 1);
	cout<<"r = (p - 1)*(q - 1) = "<>e;
	cout<<"Please input the plaintext:";
	cin>>plaintext;
	while(true)
	{
		d++;
		if(Quick_Multiply(e,d,r)==1)
		{
			cout<<"d = "<>flag;
	cout<<"plaintext:"< 
运行结果如下：
 
 
 当 plaintext 中出现 J-Z 时，decrypt_plaintext 无法接解析出正确结果，但 decrypt_ciphertext 仍然正确。这是因为解密代码中默认一个字母只对应一位数字，例如 A-1，但 J-Z 对应的均是两位数，因此导致转化时出错。这里笔者实在是懒得实现了，大家可以自行完善代码，例如使每个字母均对应两位数字，不足时高位补 0。
 
单就字符类型转换这一点就不难发现，Python 相比于 C/C++ 是何等方便（但 C/C++ 作为编程界的常青藤也有其自身的道理）。更逆天的是 Python 提供了第三方的 rsa 库，它可以很轻松地帮助我们实现RSA加解密，代码如下：
 
import rsa
 
def rsa_encrypt(str):
    (pubkey,privkey) = rsa.newkeys(512) # 最大加密长度
    print("pubkey = ",pubkey)
    print("privkey = ",privkey)
    bytes = str.encode("utf-8") # str => bytes
    ciphertext = rsa.encrypt(bytes, pubkey)
    return (ciphertext, privkey)
 
def rsa_decrypt(bytes,privk):
    plaintext = rsa.decrypt(bytes,privk)
    plaintext = plaintext.decode("utf-8")
    return plaintext
 
if __name__ == "__main__":
    ciphertext,privk = rsa_encrypt("flag")
    print("ciphertext:",ciphertext)
    plaintext = rsa_decrypt(ciphertext,privk)
    print("plaintext:",plaintext)
 
运行结果如下：
 
 需要注意的是，pubkey 与 privkey 都是执行脚本时随机生成的，且满足对应关系。如果想要将加密与解密分离实现且重复使用的话，需要记下当前随机生成的 pubkey 与 privkey，且在脚本中声明后作为参数传入。
 
0x02 RSA加密算法的破解 
https://www.packetmania.net/2020/12/01/RSA-attack-defense/
 
0x03 Summary 
由于笔者的 Dev-C++ 版本过低，C++11 标准增加的 std::to_string 等全局函数无法使用。本文采用的是字符串流 sstream 中的 stringstream 类实现的字符类型转换，调试代码如下：
 
#include
#include
#include
using namespace std;

int main()
{
	string flag,flag2,flag3;
	flag = "Hello ";
	flag2 = "World!";
	flag3 = flag + flag2;
	cout< 
运行结果如下：