信息安全与技术--rsa算法详解（包括欧拉函数以及扩展欧几里得算法详解）

1.算法描述

一，**对的产生

	（1）选取两个大素数p和q。
	（2）计算n = p*q以及n的欧拉函数值 φ（n） = （p-1）*（q-1）。
	（3）然后随机选取整数e（1<e<φ（n）），且满足gcd（e,φ（n）） = 1(gcd表示最大公约数运算)，就是说φ（n）和e互素。 （互素等价于两者的最大公约数为1。）
	（4）由扩展欧几里得算法求出d，使得 e*d =1 mod φ（n）。
	（5）形成秘钥对，其中公钥为{e,n},私钥为{d,n}。p,q是秘密参数，需要保密，如不需要保存，可销毁。

二，加密过程

	加密时需要使用接受方的公钥，不妨设接收方的公钥为 e ，明文 m 满足 0 <= m < n。
	(否则就要进行分组)，计算 c = m^e(mod n) ,c为密文。

三，解密过程

   计算 m = c^d (mod n)

四，gcd 欧几里得

	欧几里得，也叫求最大公约数，又称为辗转相除法。
	比如64 24两者的最大公约数求解过程如下。
	gcd(a,b)  a = 64  b = 24  
	a = 24   64/24 = 2(余 16)  b = 16
	a = 16   24/16 = 1(余 8)   b = 8
	a = 8    16/8 = 2(余 0)    b = 0
	当b = 0的情况下 ，a就是两者的最大公约数。
	不难看出我们把上述过程总结一些，会发现是一个递归过程。
	gcd(a,b) = gcd(b,a%b)=gcd(a%b,b%(a%b))..... 直到b == 0的情况下找到最大公约数。

五，exgcd 扩展欧几里得

在最大公约数有一个性质一定存在有整数 x，y使得ax+by = gcd（a,b）。
因为 最大公约数是a，b的一个因子必然存在 a|gcd（a，b），b|gcd（a，b），那么ax|gcd(a,b),by|gcd(a,b)。
由欧几里得算法我们发现是一个递归过程最后的情况肯定是b = 0的情况下，a为最大公约数。
那么最后一次的解就为，ax+by = gcd（a,b）; x = 1， y = 0;(因为b = 0，其实y可以取任意值，通常为了好计算，我们采用y = 0)。
然后最后总结了一下，欧几里得算法是一个递归方式，在最后才可以获得解，我们可以求完最大公约数以后，再进行一个反向递归，便可以求出 x，y的值。
首先先根据rsa的算法要求，e*d =1 mod φ（n）。
e*d =1 mod φ（n）== e*d = 1+k*φ（n）== e*d+k*φ（n）=1 (k可以取任何值) 
这里我们之所以可以用此公式，是因为扩展欧几里得 gcd（e，φ（n））= 1。
因为这样才符合扩展欧几里得的定义。
e*d+k*φ（n）=gcd(e,φ（n)）=1
我们取一个符合rsa的两个数，为了好演示。

我们选择p=11，q =13。 φ（n）= （p-1）*（q-1）=120。我们选取 e = 7，与φ（n）进行互素。
k*φ（n）+ e*d =1
然后我们采用扩展欧几里得的方法
我们令a = φ（n）,b = e,x = k, y = d。
由gcd (a,b) = gcd(b,a%b) 。   
可得 ax + by = bx1+(a-a/b*b)y1,变形一下可得 ax + by = ay1 + b(x1-a/b)*y1。 这里a/b是下取整。
可得 x = y1, y = (x1-a/b)*y1 。 这就是我们一会要用的递推公式。

a = 120, b = 7。							 x = y1=1,  y = x1-17*y1=0-17*1= -17,  x = 1 , y = -17。
a = 7,  120/7= 17(余1)，b = 1。               x1 = y2=0, y1 =x2-7*y2=1-7*0=1。      x1 = 0, y1 =1。   
a = 1,   7/1 = 7(余0)	， b = 0,  	        返回 x2 = 1，y2 = 0。
 我们将x，y带入验证发现 是符合结果的。

六，欧拉函数

欧拉函数是求所有的小于n的数与n互为质数的数目。
通俗易懂的讲，当一数为素数时，那么和素数不互质的数只有是他本身，所以我们只需要求出当前n下的
所有素数，然后去掉和素数不互质的数就可以了，假如这个素数为q，那么，去掉这个素数后的数量n/q*(q-1) 

就可以把所有和q不互质的数去掉了，然后去掉小于n的所有素数系列，剩下的这个值就是欧拉函数的值。

七，欧几里得以及扩展欧几里得的代码

#include <bits/stdc++.h>

using namespace std;

int exgcd(int a,int b,int &x,int &y) ///扩展欧几里得函数
{
    if(b==0) {x=1,y=0; return a;}
    int d = exgcd(b,a%b,x,y);
    int z = x; x = y; y = z - a/b*y;
    return d;
}
int gcd(int a,int b)  ///欧几里得函数
{
	return b==0?a:gcd(b,a%b);
}

int main()
{
    
        int a,b; cin>>a>>b;
        exgcd(a,b,a,b);
        cout<<a<<" "<<b<<"\n";
    return 0;
}

八，求解明文密文算法

首先先给三个mod运算的性质
（a+b）% mod = a%mod + b%mod
（a-b）% mod = a%mod - b%mod
（a*b）% mod = a%mod * b%mod
 根据乘法取模的这个性质，我们求解密文和明文的时候是不是经常会遇到 2^1000或者更大的幂次方，
 如果我们先乘出来在进行求余，当幂次方很高的时候是不能解决掉这个问题的。所以我们可以根据算法
 当中的一个叫做快速幂的方法来进行解析。我们直接上样例进行解析。
 给我们一个数5^10 mod 7的结果是多少。
 暴力解法
 5*5 = 25
 25*5 = 125 
 125*5 = 625 虽然也能算，但是当幂次方改成1000次，这样就很难解决了。
 快速幂解法
 5^10 mod 7 = (5*5mod 7)^5 = 4 ^ 5 mod 7
 4^5  mod 7 = 4*(4*4mod 7)^2 mod 7 = 4*(2^2) mod 7
 4*4 mod 7 = 2
 总结，当幂次方为偶数的时候我们发现我们可以进行减少一半的操作，幂次方为奇数的时候，
 我们发现可以提出来一个奇数，然后剩下的偶数继续进行减少一般的操作，这样计算会发现
 只需要计算很少的次数就能求出答案。
 当幂为1000的时候我们进行计算一下
 5^1000 mod 7 = (5*5mod 7) ^500 mod 7 = 4 ^ 500 mod 7
 4^500 mod 7 = (4*4mod 7)^250 mod 7 = 2^250 mod 7
 2^250 mod 7 = (2*2mod 7)^125 mod 7 = 4^125 mod 7
 4^125 mod 7 = 4*((4*4mod 7)^62)mod 7 = 4*(2^62) mod 7
 4*(2^62)mod 7 = 4*(2*2 mod 7)^31  = 4^32 mod 7
 4^32 mod 7 = (4*4 mod 7) ^16 = 2 ^16 mod 7
 2^16 mod 7 = (2*2 mod 7) ^8 mod 7 = 4^8 mod 7
 4^8 mod 7 = (4*4 mod 7)^4 mod 7 = 2^4 mod 7
 2^4 mod 7 = (2*2 mod 7) ^2 mod 7 = 4^2 mod7
 4*4 mod 7 = 2