公开密钥密码体制（C语⾔实现RSA加密算法）
公开密钥密码体制：
公开密钥密码体制的产⽣主要是因为两个⽅⾯的原因，⼀是由于常规密钥密码体制的密钥分配问题，另⼀种是由于对和数字签名的需求。
传统的加密⽅法是加密、解密使⽤同样的密钥，由发送者和接收者分别保存，在加密和解密时使⽤，采⽤这种⽅法的主要问题是密钥的⽣成、注⼊、存储、管理、分发等很复杂，特别是随着⽤户的增加，密钥的需求量成倍增加。在⽹络通信中，⼤量密钥的分配是⼀个难以解决的问题。
1976年美国斯坦福⼤学的两名学者迪菲和赫尔曼提出了公开密钥密码体制的概念。所谓的公开密钥密码体制就是使⽤不同的加密密钥与解密密钥，是⼀种“由已知加密密钥推导出解密密钥在计算上是不可⾏的”密码体制。
在公开密钥密码体制中，公开密钥PK是公开信息，⽽秘密密钥SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK 是由公开密钥PK决定的，但却不能根据PK计算出SK。
该技术采⽤"⾮对称式加密⽅法，也就是两个不同的密钥来对信息加密和解密。
举个例⼦吧，单看概念属实看不懂
⾸先我有两把钥匙，公钥和私钥。我可以把我的公钥给任何⼀个想给我写信的⼈，他们写完信之后⽤我的公钥加密，发给我，然后我⽤⾃⼰的私钥解密。这⾥要强调的是，只要我的的私钥不泄露，这封信就是安全的，即使落在别⼈⼿⾥，也⽆法解密。
加密解密原理：
1. 对称加密：⼜称共享密钥加密，使⽤同⼀个密钥对数据进⾏加密解密。
2. ⾮对称加密：加密解密使⽤不同密钥，⽤公钥加密，私钥解密。
RSA公钥加密体制
RSA公共密码密钥体制是⼀种使⽤不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可⾏的”密码体制 。
在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，⽽解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK 。
正是基于这种理论，1978年出现了著名的RSA算法，它通常是先⽣成⼀对RSA密钥，其中之⼀是保密密
钥，由⽤户保存；另⼀个为公开密钥，可对外公开，甚⾄可在⽹络服务器中注册。为提⾼保密强度，RSA密钥⾄少为500位长，⼀般推荐使⽤1024位。这就使加密的计算量很⼤。为减少计算量，在传送信息时，常采⽤传统加密⽅法与公开密钥加密⽅法相结合的⽅式，即信息采⽤改进的DES或IDEA对话密钥加密，然后使⽤RSA密钥加密对话密钥和信息摘要。对⽅收到信息后，⽤不同的密钥解密并可核对信息摘要。
分析RSA加密原理
RSA算法的过程
RSA算法⽤到的数学知识特别多，所以在中间介绍这个算法⽣成私钥和公钥的过程中会穿插⼀些数学知识。⽣成步骤如下：
1. 寻两个不相同的质数
随意选择两个⼤的质数p和q，p不等于q，计算N=p*q;
什么是质数?我想可能会有⼀部分⼈已经忘记了，定义如下：
除了1和该数⾃⾝外，⽆法被其他⾃然数整除的数（也可定义为只有1该数本⾝两个正因数]的数）。
⽐如2，3，5，7这些都是质数，9就不是了，因为3*3=9了
2. 根据欧拉函数获取r
r = φ(N) = φ§φ(q) = (p-1)(q-1)。
这⾥的数学概念就是什么是欧拉函数了，什么是欧拉函数呢？
欧拉函数的定义：
欧拉函数φ(n)是⼩于或等于n的正整数中与n互质的数的数⽬。
互质的定义：
如果两个或两个以上的整数的最⼤公约数是1，则称它们为互质
例如：φ(8)=4，因为1,3,5,7均和8互质。
推导欧拉函数:
（1）如果n =1, φ(1)=1；(⼩于等于1的正整数中唯⼀和1互质的数就是1本⾝)；
（2）如果n为质数，φ(n)= n - 1；因为质数和每⼀个⽐它⼩的数字都互质。⽐如5，⽐它⼩的正整数1,2,3,4都和他互质；
(3)如果n是a的k次幂，则φ(n)=φ(a^k)= a^k - a^(k-1)=(a-1)a^(k-1)；
(4)若m,n互质，则φ(mn)=φ(m)φ(n)
证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理(经常看数学典故的童鞋应该了解，剩余定理⼜叫韩信点兵，也叫孙⼦定理)，A*B和C可建⽴双射⼀⼀对应)的关系。（或者也可以从初等代数⾓度给出欧拉函数积性的简单证明）因此的φ(n)值使⽤算术基本定理便知。（来⾃）
3. 选择⼀个⼩于r并与r互质的整数e
选择⼀个⼩于r并与r互质的整数e，求得e关于r的模反元素，命名为d（ed = 1(mod r)模反元素存在，当且仅当e与r互质），e我们通常取65537。
模反元素：
如果两个正整数a和n互质，那么⼀定可以到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
⽐如3和5互质，3关于5的模反元素就可能是2，因为3*2-1=5可以被5整除。所以很明显模反元素不⽌⼀个，2加减5的整数倍都是3关于5的模反元素{...-3, 2,7,12…}放在公式⾥就是3*2 =1(mod 5)
上⾯所提到的欧拉函数⽤处实际上在于欧拉定理：
欧拉定理：
如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下⾯的等式成⽴：
a^φ(n)=1(mod n)
由此可得：a的φ(n - 1)次⽅肯定是a关于n的模反元素。
欧拉定理就可以⽤来证明模反元素必然存在。
由模反元素的定义和欧拉定理我们知道，a的φ(n)次⽅减去1，可以被n整除。⽐如，3和5互质，⽽5的欧拉函数φ(5)等于4，所以3的4次⽅(81)减去1，可以被5整除（80/5=16）。
⼩费马定理：
假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成
a^(p-1)=1(mod p)
这其实是欧拉定理的⼀个特例。
4. 销毁p和q
此时我们的(N , e)是公钥，(N, d)为私钥，爱丽丝会把公钥(N, e)传给鲍勃，然后将(N, d)⾃⼰藏起来。⼀对公钥和私钥就产⽣了。
主流加密⽅法：
1. 不可逆加密
常应⽤于⽤户密码
2. 可逆加密
2.1. 对称加密
常⽤于⾝份证号⼿机号等敏感信息
将明⽂和加密密钥⼀起经过特殊加密处理，使⽤密钥只有⼀个
优点：算法公开、计算量⼩、加密速度快、加密效率⾼
AES、DES、3DES、Blowfish、IDEA、RC4、RC5、RC6等
2.2 ⾮对称加密
常⽤于签名和认证
⾮加密算法需要2密钥：私有密钥和公有密钥
采⽤公有密钥加密需采⽤对应私有密钥解密。反之
优点：⾮对称加密与对称加密相⽐，其安全性更好；
缺点：⾮对称加密的缺点是加密和解密花费时间长、速度慢，只适合对少量数据进⾏加密。
RSA、DSA（数字签名⽤）、ECC（移动设备⽤）、Diffie-Hellman、El Gamal等
防御密码破译⼿段
1. 严禁使⽤明⽂存储
2. 不可逆算法
MD5 sha hmac等
3. 安全机制，防⽌暴⼒破解（防⽌暴⼒破解）
⽐如验证码，或⼏次密码错误账号锁定
4. 要复杂，加盐（防⽌脱库）
盐：没有固定规律的随机字符串，盐越长越复杂，密码越安全，盐进⾏持久化保存
例如：
f()为某种加密算法
密⽂=f(明⽂密码) --> 密⽂=f(明⽂密码+盐) --> 密⽂=f(明⽂密码+盐+账号相关信息)
5. 客户端加传输过程加密（防⽌传输劫取）
传输过程例如https/tls
C语⾔（或其它主流语⾔）实现RSA加密和解密算法
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define ACCURACY 5
#define SINGLE_MAX 10000
#define EXPONENT_MAX 1000
#define BUF_SIZE 1024
/**
* Computes a^b mod c，计算a^b mod c
*/
int modpow(long long a,long long b,int c){
int res =1;
while(b >0){
c语言编译器idea/* Need long multiplication else this
必须使⽤长乘法，否则这将溢出*/
if(b &1){
res =(res * a)% c;
}
b = b >>1;
a =(a * a)% c;/* Same deal here */
}
return res;
}
/**
* Computes the Jacobi symbol, (a, n)，计算Jacobi符号（a,n）
*/
int jacobi(int a,int n){
int twos, temp;
int mult =1;
while(a >1&& a != n){
a = a % n;
if(a <=1|| a == n)break;
twos =0;
while(a %2==0&&++twos) a /=2;/* Factor out multiples of 2 ，减去2的倍数*/
if(twos >0&& twos %2==1) mult *=(n %8==1|| n %8==7)*2-1;
if(a <=1|| a == n)break;
if(n %4!=1&& a %4!=1) mult *=-1;/* Coefficient for flipping，翻转系数 */
temp = a;
a = n;
n = temp;
}
if(a ==0)return0;
else if(a ==1)return mult;
else return0;/* a == n => gcd(a, n) != 1 */
}
/**
* Check whether a is a Euler witness for n，检查a是否为n的欧拉见证 */
int solovayPrime(int a,int n){
int x =jacobi(a, n);
if(x ==-1) x = n -1;
return x !=0&&modpow(a,(n -1)/2, n)== x;
}
/**
* Test if n is probably prime, using accuracy of k (k solovay tests)，⽤k的精度检查n是否可能是素数 */ int probablePrime(int n,int k){
if(n ==2)return1;
else if(n %2==0|| n ==1)return0;
while(k-->0){
if(!solovayPrime(rand()%(n -2)+2, n))return0;
}
return1;
return1;
}
/**
* Find a random (probable) prime between 3 and n - 1在3和（n-1）之间⼀个随机素数, this distribution is，
* nowhere near uniform, see prime gaps
*/
int randPrime(int n){
int prime =rand()% n;
n += n %2;/* n needs to be even so modulo wrapping preserves oddness */
prime +=1- prime %2;
while(1){
if(probablePrime(prime, ACCURACY))return prime;
prime =(prime +2)% n;
}
}
/**
* Compute gcd(a, b)，计算gcd（a,b）
*/
int gcd(int a,int b){
int temp;
while(b !=0){
temp = b;
b = a % b;
a = temp;
}
return a;
}
/**
* Find a random exponent x between 3 and n - 1 such that gcd(x, phi) = 1，在3和n-1之间到随机指数x，使得gcd(x,phi)=1 * this distribution is similarly nowhere near uniform，这种分布同样不接近制服
*/
int randExponent(int phi,int n){
int e =rand()% n;
while(1){
if(gcd(e, phi)==1)return e;
e =(e +1)% n;
if(e <=2) e =3;
}
}
/**
* Compute n^-1 mod m by extended euclidian method，⽤扩展欧⼏⾥得法计算n^-1 mod m
*/
int inverse(int n,int modulus){
int a = n, b = modulus;
int x =0, y =1, x0 =1, y0 =0, q, temp;
while(b !=0){
q = a / b;
temp = a % b;
a = b;
b = temp;
temp = x; x = x0 - q * x; x0 = temp;
temp = y; y = y0 - q * y; y0 = temp;
}
if(x0 <0) x0 += modulus;
return x0;
}
/**
* Read the file fd into an array of bytes ready for encryption.将⽂件fd读⼊准备加密的字节数组
* The array will be padded with zeros until it divides the number of数组将填充零，知道它划分每个块加密的字节数
* bytes encrypted per block. Returns the number of bytes read.返回读取的字节数
*/
int readFile(FILE* fd,char** buffer,int bytes){
int len =0, cap = BUF_SIZE, r;