RSA解密

参考博客：
https://www.cnblogs.com/pcheng/p/9629621.html
https://blog.****.net/qq_40531479/article/details/89034977
https://blog.****.net/qq_42876636/article/details/87559366

RSA加密原理简介

RSA加密是一种非对称加密，能够在不直接传递密钥的前提下，完整解密。RSA解密使用一对密钥进行加密，分别是 公钥和私钥。两个密钥之间数学相关。

首先选定两个大素数: $ p,q $

• $n=p*q$n=p∗q

然后找到一个数 $d$d，使得：

• $d$d 与 $(p-1)(q-1)$(p−1)(q−1) 互质

接下来找到数 $e$e ，使得：

• $de\equiv1(mod\ ((p-1)*(q-1)))$de≡1(mod ((p−1)∗(q−1)))

$e$e 是 $d$d 模 $(p-1)*(q-1)$(p−1)∗(q−1) 的逆元(模反元素)

则有：

• $n,e$n,e 组成了私钥

• $n,d$n,d 组成了公钥

模反元素(逆元)：

如果两个正整数a n互质，那么一定可以找到一个整数 b ，使得 ab被n除的余数是1，b称为a的模反元素，即：

$ab\equiv1(mod\ n)$ab≡1(mod n)

例：7 模 11 的逆元

$7*8=11*5+1$7∗8=11∗5+1

所以 7 模 11 的逆元为 8

加密与解密方法

设密文原文为 $X$X ：

• 加密：$C=X^{d} \ mod\ n$C=Xd mod n
• 解密：$X=C^{e}\ mod\ n$X=Ce mod n

破解方法

由于 RSA 中公钥 (n,d) 是公开的，所以：

• 通过对 $n$n 分解质因数可以得到 $p, q $

• 检测 $p, q $与 $d$d 是否互质

• 由扩展欧几里得算法、求逆元算法 根据 $p,q,d$p,q,d 得到 $e$e

• 得到加密的 $C$C 后，可以根据 $e,n$e,n 来破解得到密文 $X$X

RSA算法的可靠性：

对极大的整数进行因数分解的难度决定了RSA算法是可靠的。

涉及算法：

根据上述破解方法得到各步涉及到的算法：

各算法的原理见附件 : 算法细节.md

• 质因数分解
• 扩展欧几里得算法、求逆元算法
• 快速乘、快速幂(加取模)

质因数分解：

暴力法

LL target;
cout<<"Input target number : ";
cin>>target;
cout<<target<<" = ";
for(LL i = 1;i < target;i += 2){
	if(target % i == 0){	//遇到整除便输出
		cout<<i<<" * ";
		target /= i;
	}
}
cout<<target<<endl;

扩展欧几里得算法：

void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(b==0)
	{
		d = a; x = 1; y = 0; return;
	}
	exgcd(b,a%b,d,y,x);
	y -= (a/b)*x;
}

求逆元算法：

LL modReverse(LL t,LL m)
{
	LL d,x,y;
	exgcd(t,m,d,x,y);
	return (x%m+m)%m;
}

快速取模乘：

LL fastModMul(LL a,LL b,LL mod)//快速乘计算 a*b
{
	LL ans = 0;
	while(b)	//对 b 进行逐位检测，为1则加上对应的权重
	{
		if(b&1) ans = (ans+a)%mod;
		a = (a+a)%mod;	//a累乘2
		b>>=1;
	}
	return ans;
} 

快速取模幂(快速乘改进)：

LL fastModPow(LL a,LL b,LL mod)	//快速取模幂
{
	LL ans = 1;
	while(b)	//对 b 进行逐位检测，为1则乘上对应的权重
	{
		if(b&1) ans = fastModMul(ans,a,mod);
		a = fastModMul(a,a,mod);
		b>>=1;		
	} 
	return ans;
}

完整过程：

• 求得 $ p,q$

//由分解质因数(暴力)得到：
p = 891234941
q = 1123984201

• 求 $e$e (由扩展欧几里得算法求逆元)

m = (p - 1) * (q - 1);
e = modReverse(d, m);
//Result : e = 823816093931522017

• 利用公式解密

c = 20190324ll;
n = p * q;
result = fastModPow(c, e, n);
//Result : 579706994112328949

---

附:算法细节

1.扩展欧几里得算法：

由欧几里得算法可以得到：
$gcd(a,b)=gcd(b,a\%b)$gcd(a,b)=gcd(b,a%b)
定理：对于两个整数 a,b 必有整数 x y 使得：
$ax+by=gcd(a,b)$ax+by=gcd(a,b)
则由上面两式可得：
$ax_{1}+by_{1}=bx_{2}+(a\%b)y_{2}\\ 即\\ ax_{1}+by_{1}=bx_{2}+(a-(\frac{a}{b})b)y_{2}\\ 即\\ ax_{1}+by_{1}=ay_{2}+b(x_{2}-(\frac{a}{b})y_{2})$ax1​+by1​=bx2​+(a%b)y2​即ax1​+by1​=bx2​+(a−(ba​)b)y2​即ax1​+by1​=ay2​+b(x2​−(ba​)y2​)
由于a,b为常数且等式成立，可以得到：
$x_{1}=y_{2}\\y_{1}=x_{2}-(\frac{a}{b})y_{2}$x1​=y2​y1​=x2​−(ba​)y2​

---

显然利用:
$gcd(b,a\%b)=gcd(a\%b,b\%(a\%b))$gcd(b,a%b)=gcd(a%b,b%(a%b))
可以继续得到 $x_{2},y_{2}$x2​,y2​和 $x_{3},y_{3}$x3​,y3​ 的关系，这种关系可以一直保持下去。

但是由于辗转相除法是有穷的，所以$x_{i},y_{i}$xi​,yi​之间的迭代也是有穷的，$x_{max},y_{max}$xmax​,ymax​ 显然在辗转相除法中是当 $b=0$b=0 时的情形，所以 $b=0$b=0 是递归基。

实现代码：

void extgcd(int a,int b,int &x,int &y){
    if(b==0){
        x = 1;
        y = 0;
        return;
    }
    extgcd(b,a%b,x,y);
    //从这里开始往回倒,最后求出x,y
    int x1 = x,y1 = y;
    x = y1;
    y = x1 - (a/b) * y1;
}

---

2.快速幂：

使用累乘的方法实现幂运算 x^y 的时间复杂度是 O(n)，而使用快速幂改进之后可以达到 O(logn)。

原理:

将 y 展开为二进制形式，则可得 二进制代码长度为 log₂n

例如：假设 y = 10, 则 y = 1010₂ ，第i位的位权是 2^i-1，计算过程为：

从最低位向高位遍历：

从低位到高位	数值	结果累乘操作
最低位	0	不乘 x1
第二位	1	乘以 x2
第三位	0	不乘 x4
第四位	1	乘以 x8

代码实现：

int fastPow(int X, int Y){
	int result = 1;
	int x = X;
	int y = Y;
	//循环移位累乘
	while(y){
		if(y & 1)	result *= x;
		x *= x;
		y = y >> 1;
	}
	return(result);
}

---

3.快速乘改进的快速取模幂：

快速乘的时间复杂度是 O(logn)，付出这个时间代价可以防止累加时溢出：

快速取模乘：

LL fastModMul(LL a,LL b,LL mod)//快速乘计算 a*b
{
	LL ans = 0;
	while(b)
	{
		if(b&1) ans = (ans+a)%mod;
		a = (a+a)%mod;	//a乘2，以进行下一位的运算
		b>>=1;	//b右移一位，检测下一位
	}
	return ans;
} 

使用快速取模幂来改进：

LL fastModPow(LL a,LL b,LL mod)//快速幂
{
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = fastModMul(ans,a,mod);
		a = fastModMul(a,a,mod);
		b>>=1;		
	} 
	return ans;
}

快速幂用于在防止溢出的前提下计算(计算过程中不断模n)：

$result=x^{y}\ mod \ n$result=xy mod n