RSA整理
最近的论文用到了RSA相关的东西，做一个整理。
流程图
- 密钥生成过程：
- 加密解密过程：
选取2个质数p、q
\(RSA\)算法的主要就是基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难。 同时为了增强强度，\(p-1\)和\(q-1\)的最大公因子要小 质数的选取方法：
- 随机搜索法随机产生一个奇数 \(p_1\) 进行素数测试,若是素数,则结束;否则,重新随机产生一个奇数 \(p_2\) 进行素性测试,直至找到一个素数 \(p_t\)。
- 随机递增搜索法随机产生一个奇数,对以该数为起点的奇数依次进行测试,直至找到一个素数。这种方法相对于随机搜索法，在速度上有一定的提高，但是并没有本质上的区别
设:
\(p=61,q=53\)
计算n = p * q
\(n\)是公钥对，密钥对都需要的一个值，为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位，也有2048位的。
\( n = p*q=61*53 = 3233 \)
这个部分是可以直接求解的。
计算欧拉函数 ϕ(n)
\( \phi(n) = (p-1)(q-1) = 60*52 = 3120 \)
选择加密密钥 e
加密密钥 \(e\) 需要满足以下条件：
\(1 < e < \phi(n), gcd(e, \phi(n)) = 1\)
这个条件是为了确保\(e\)在模\(\phi(n)\)的情况下有逆元。出于安全性考虑 \(e=2\) 永远不该被使用 一般生成这种\(e\)的方法有2种：
- 随机生成法
- 穷举法
我们令
\(e = 17 \)
即我们得到公钥对：
\(PU\ = \ \{\ e,n\ \} = \{\ 17,3233\ \} \)
计算解密密钥 d
解密密钥 \(d\) 需要满足：
\(d \equiv\) \(e\)-1 \( \ \ (\ mod\ \phi(n) \ )\)
其实求的就是\(e\)的逆元，求逆元的方法有3种：
- 循环求解法枚举所有的数，来求解\(e\)的逆元
- 扩展欧几里
扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数\(x、y\)（其中一个很可能是负数），使它们满足贝祖等式\(ax + by = gcd(a, b)\)。
当\(gcd(a, b)=1\),那么\((ax + by = 1)\),此时可以看出\(m\)是\(a\)模\(b\)的乘法逆元，\(n\)是\(b\)模\(a\)的乘法逆元。
扩展欧几里德计算过程：
\(a = q_1b + r_1 \ \ \ r_1 = ax_1+by_1\)
\(b = q_2r_1 + r_2 \ \ \ r_2 = ax_2+by_2\)
\(r_1 = q_3b + r_3 \ \ \ r_3 = ax_3+by_3\)
…
\(r_{n-2}= q_nr_{n-1} + r_n \ \ \ r_n = ax_n+by_n\)
\(r_{n-1}= q_{n+1}r_{n} + 0 \)
通过移项，得到：
\(r_i = r_{i-2}-r_{i-1}q_i\)
同样，从i-1和i-2行，也可以得到:
\(r_{i-2} = ax_{i-2}+by_{i-2}\ \ \ \ \ r_{i-1}=ax_{i-1}+by_{i-1}\)
代入：
\(r_i =a(x_{i-2} - q_ix_{i-1})+b(y_{i-2}-q_iy_{i-1})\)
因为我们已经假设\(r_i=ax_i+by_i\),因此
\(x_i =x_{i-2} - q_ix_{i-1}\ \ \ \ \ y_i=y_{i-2} - q_iy_{i-1}\)
#include
#include
#define LL __int64
using namespace std;
LL extend_gcd(LL a, LL b, LL &x, LL &y)//ax+by=1返回a,b的gcd
{
LL ans, t;
if(b == 0)
{
x = 1;
y = 0;
return a;
}
ans = extend_gcd(b, a%b, x, y);
t = x;
x = y;
y = t - ( a / b ) * y;
return ans;
}
int main()
{
LL a, b, c, x, y;
while(~scanf(“%I64d%I64d%I64d”, &a, &b, &c))//ax+by = c
{
LL gcd = extend_gcd(a,b,x,y);
while(x < 0)//x 为正
x += b,y -= a;
printf(“ax+by = 1的最小正整数解:%I64d %I64d\n”, x, y);//ax+by = 1
//x即为a%b的逆元，y为b%a的逆元
printf(“a mod b的逆元:%I64d\n”, x);
if(c % gcd)
{
printf(“无解！\n”);
continue;
}//ax+by = c
printf(“x=%I64d,y=%I64d\n”, x*c/gcd, y*c/gcd);
}
return 0;
}
- 费马小定理成立的前提是\(\phi(n)\)为质数，否则无法使用。 假如\(a\)是整数，\(p\)是质数，且\(a,p\)互质(即两者只有一个公约数1)，那么\(a\)的\((p-1)\)次方除以\(p\)的余数恒等于1。那么逆元为 \(a\)\(m-2\)\(\ mod\ m \)
利用扩展欧几里得算法可以求得：
\(d=2753\)
即我们得到密钥对：
\(PR\ =\ \{\ d,n\ \} = \{\ 2753,3233\ \}\)
加密解密
- 加密 \(C = M^e\ (\ mod\ n\ )\)
假设对65加密,即\(M=65\)则：
\(C=65\)17 \(mod \ 3233 = 2790\)
- 解密 \(M = C^d\ (\ mod\ n\ )\)
针对密文\(C=2790\)的情况，我们进行解密：
\(M = 2790\)2753 \(\ mod\ 3233 = 65.\)
求高次幂的快速幂算法: 比如求解：
\(a^b\ mod\ n\)
把b转换成二进制数,该二进制数第\(i\)位的权为 2\(i\)-1 例如, \(b=11\)的二进制是1011
11 = 23 ×1 + 22 ×0 + 21 ×1 + 20 ×1
因此，我们将\(a\)11 转化为算
\( a\)11 =\(a\)20 *\(a\)21 * \(a\)23
int modexp(int a,int b,int n)
{
int ret=1;
while(b)
{
if(b&1) ret=reta%n;
a=aa%n;
b>>=1;
}
return ret;
}
// <![CDATA[ if (typeof MathJaxListener !== ‘undefined’) { MathJax.Hub.Register.StartupHook(‘End’, function () { MathJaxListener.invokeCallbackForKey_(‘End’); }); } // ]]>