首页 / 算法 / 数字签名与身份认证: RSA算法指北
数字签名与身份认证: RSA算法指北
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数字签名与身份认证: RSA算法指北，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9770字，纯文字阅读大概需要14分钟。
内容图文
简介
RSA algorithm是一种非对称加密算法，解密需要两个不同的密钥，public key和private key。一个典型的非对称加密流程是：
- 客户端向服务端发送
public key并请求数据 - 服务端使用
public key加密数据并响应请求 - 客户端接收到数据后使用
private key解密
RSA算法的核心思想
大数分解因子操作的高复杂度能有效保证RSA algorithm的安全性。public key由两个数组成，其中一个数为两个大质数的乘积；private key由这两个大质数产生。实际上只要能对公钥中的数进行因子分解，就能破解对应的私钥。RSA算法的安全性随key length的增加呈现指数级增长。
RSA算法的实现机制
工作机制：
- 选择两个质数 p and q
- 计算整个加密解密运算的模 N=p?q
- 计算N的欧拉函数 ?(N)=(p?1)?(q?1)
- 选择公钥加密所需的幂指数 e∈Zn?,st.e<?(N)&gcd(e,?(N))=1
- 计算私钥解密所需的幂指数 d=e1+k??(N)?,其中k为选定常数
- 加密时对数字信息m执行 c=memodN 获得加密信息c
- 解密时对加密信息c执行 m=cdmodN 获得原信息m
实现代码如下：
#include<stdio.h>
#include<math.h>
int gcd(int a, int h)
{
int temp;
while (1)
{
temp = a%h;
if (temp == 0)
return h;
a = h;
h = temp;
}
}
int main()
{
double p = 3;
double q = 7;
double n = p*q;
double e = 2;
double phi = (p-1)*(q-1);
while (e < phi)
{
if (gcd(e, phi)==1)
break;
else
e++;
}
int k = 2;
double d = (1 + k*phi)/e;
double msg = 20;
printf("Message data = %lf", msg);
double c = pow(msg, e);
c = fmod(c, n);
printf("\nEncrypted data = %lf", c);
double m = pow(c, d);
m = fmod(m, n);
printf("\nOriginal Message Sent = %lf", m);
}
运行结果:
Message data = 20.000000
Encrypted data = 20.000000
Original Message Sent = 20.000000
RSA加密解密的合法性
- 前提：
- gcd(p,q)=1
- N=p?q
- e?d=1mod?(N)
- 结论：
- (me)d=mmodN
- 定理：
- 欧拉定理：
- 对于互质的正整数a和n,有 a?(n)=1modn
- 同余运算：
- 若 a=bmodn∧c=dmodn 则 a?c=b?dmodn
- 另一个推论：
- 若 a=bmodp∧a=bmodqst.gcd(p,q)=1 , 则 a=bmod(p?q)
- 欧拉定理：
- 证明：
- gcd(m,N)=1 时：
- 根据欧拉定理和同余运算法则易证
- gcd(m,N)??=1 时：
- 只需证得 me?d=mmodp∧me?d=mmodq
- gcd(m,N)=p∨gcd(m,N)=q
- 假设 gcd(m,N)=p , 则m=h?p,h∈Z+?
- me?d=(h?p)e?d=hpmodp
- me?d=mk?(p?1)(q?1)?m=1k?(p?1)?mmodq
- 得证
- gcd(m,N)=1 时：
RSA算法的实用实现与相关优化
代码如下：
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;//RSA算法所需参数
typedef struct RSA_PARAM_Tag
{
unsigned __int64 p, q; //两个素数，不参与加密解密运算
unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算
unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1
unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1
unsigned __int64 s; //块长，满足^s<=n的最大的s，即log2(n)
} RSA_PARAM;
//小素数表
const static long g_PrimeTable[] =
{ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
const static long g_PrimeCount = sizeof(g_PrimeTable) / sizeof(long);
const unsigned __int64 multiplier = 12747293821;
const unsigned __int64 adder = 1343545677842234541;
//随机数类
class RandNumber
{
private:
unsigned __int64 randSeed;
public:
RandNumber(unsigned __int64 s = 0);
unsigned __int64 Random(unsigned __int64 n);
};
RandNumber::RandNumber(unsigned __int64 s)
{
if (!s)
randSeed = (unsigned __int64)time(NULL);
else
randSeed = s;
}
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
randSeed = multiplier * randSeed + adder;
return randSeed % n;
}
static RandNumber g_Rnd;
/* 模乘运算，返回值x=a*b mod n */
inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n)
{
return a * b % n;
}
/* 模幂运算，返回值x=base^pow mod n */
unsigned __int64 PowMod(unsigned __int64 &base, unsigned __int64 &pow, unsigned __int64 &n)
{
unsigned __int64 a = base, b = pow, c = 1;
while (b)
{
while (!(b & 1))
{
b >>= 1; //a=a * a % n;
//函数看起来可以处理位的整数，但由于这里a*a在a>=2^32时已经造成了溢出，因此实际处理范围没有位
a = MulMod(a, a, n);
}
b--;
//c=a * c % n;
//这里也会溢出，若把位整数拆为两个位整数不知是否可以解决这个问题。
c = MulMod(a, c, n);
}
return c;
}
/* Rabin-Miller素数测试，通过测试返回，否则返回。n是待测素数。
注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4 */
long RabinMillerKnl(unsigned __int64 &n)
{
unsigned __int64 b, m, j, v, i;
m = n - 1;
j = 0;
//0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
while (!(m & 1))
{
++j;
m >>= 1;
}
//1、随机取一个b，<=b<n-1
b = 2 + g_Rnd.Random(n - 3);
//2、计算v=b^m mod n
v = PowMod(b, m, n);
//3、如果v==1，通过测试
if (v == 1)
{
return 1;
}
//4、令i=1
i = 1;
b = 2;
//5、如果v=n-1，通过测试
while (v != n - 1)
{
//6、如果i==l，非素数，结束
if (i == j)
{
return 0;
}
//7、v=v^2 mod n，i=i+1
v = PowMod(v, b, n);
++i;
//8、循环到
}
return 1;
}
/* Rabin-Miller素数测试，循环调用核心loop次全部通过返回，否则返回 */
long RabinMiller(unsigned __int64 &n, long loop)
{
//先用小素数筛选一次，提高效率
for (long i = 0; i < g_PrimeCount; i++)
{
if (n % g_PrimeTable[i] == 0)
{
return 0;
}
}
//循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)^loop
for (long i = 0; i < loop; i++)
{
if (!RabinMillerKnl(n))
{
return 0;
}
}
return 1;
}
/* 随机生成一个bits位(二进制位)的素数，最多位*/
unsigned __int64 RandomPrime(char bits)
{
unsigned __int64 base;
do
{
base = (unsigned long)1 << (bits - 1); //保证最高位是1
base += g_Rnd.Random(base); //再加上一个随机数
base |= 1; //保证最低位是1，即保证是奇数
} while (!RabinMiller(base, 30)); //进行拉宾－米勒测试次
return base; //全部通过认为是素数
}
/*欧几里得法求最大公约数*/
unsigned __int64 EuclidGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64 a = p > q ? p : q;
unsigned __int64 b = p < q ? p : q;
unsigned __int64 t;
if (p == q)
{
return p; //两数相等，最大公约数就是本身
}
else
{
while (b) //辗转相除法，gcd(a,b)=gcd(b,a-qb)
{
a = a % b;
t = a;
a = b;
b = t;
}
return a;
}
}
/* Stein法求最大公约数 */
unsigned __int64 SteinGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64 a = p > q ? p : q;
unsigned __int64 b = p < q ? p : q;
unsigned __int64 t, r = 1;
if (p == q)
{
return p; //两数相等，最大公约数就是本身
}
else
{
while ((!(a & 1)) && (!(b & 1)))
{
r <<= 1; //a、b均为偶数时，gcd(a,b)=2*gcd(a/2,b/2)
a >>= 1;
b >>= 1;
}
if (!(a & 1))
{
t = a; //如果a为偶数，交换a，b
a = b;
b = t;
}
do
{
while (!(b & 1))
{
b >>= 1; //b为偶数，a为奇数时，gcd(b,a)=gcd(b/2,a)
}
if (b < a)
{
t = a; //如果b小于a，交换a，b
a = b;
b = t;
}
b = (b - a) >> 1; //b、a都是奇数，gcd(b,a)=gcd((b-a)/2,a)
} while (b);
return r * a;
}
}
/* 已知a、b，求x，满足a*x =1 (mod b)相当于求解a*x-b*y=1的最小整数解 */
unsigned __int64 Euclid(unsigned __int64 &a, unsigned __int64 &b)
{
unsigned __int64 m, e, i, j, x, y;
long xx, yy;
m = b;
e = a;
x = 0;
y = 1;
xx = 1;
yy = 1;
while (e)
{
i = m / e;
j = m % e;
m = e;
e = j;
j = y;
y *= i;
if (xx == yy)
{
if (x > y)
{
y = x - y;
}
else
{
y -= x;
yy = 0;
}
}
else
{
y += x;
xx = 1 - xx;
yy = 1 - yy;
}
x = j;
}
if (xx == 0)
{
x = b - x;
}
return x;
}
/* 随机产生一个RSA加密参数*/
RSA_PARAM RsaGetParam(void)
{
RSA_PARAM Rsa = { 0 };
unsigned __int64 t;
Rsa.p = RandomPrime(16); //随机生成两个素数
Rsa.q = RandomPrime(16);
Rsa.n = Rsa.p * Rsa.q;
Rsa.f = (Rsa.p - 1) * (Rsa.q - 1);
do
{
Rsa.e = g_Rnd.Random(65536); //小于^16，=2^16
Rsa.e |= 1; //保证最低位是1，即保证是奇数，因f一定是偶数，要互素，只能是奇数
} while (SteinGcd(Rsa.e, Rsa.f) != 1);
Rsa.d = Euclid(Rsa.e, Rsa.f);
Rsa.s = 0;
t = Rsa.n >> 1;
while (t)
{
Rsa.s++; //s=log2(n)
t >>= 1;
}
return Rsa;
}
/* 拉宾－米勒测试 */
void TestRM(void)
{
unsigned long k = 0;
cout << " - Rabin-Miller prime check.\\\\n" << endl;
for (unsigned __int64 i = 4197900001; i < 4198000000; i += 2)
{
if (RabinMiller(i, 30))
{
k++;
cout << i << endl;
}
}
cout << "Total: " << k << endl;
}
/* RSA加密解密 */
void TestRSA(void)
{
RSA_PARAM r;
char pSrc[] = "wellcome to bjhit!";
const unsigned long n = sizeof(pSrc);
unsigned char *q, pDec[n];
unsigned __int64 pEnc[n];
r = RsaGetParam();
cout << "p=" << r.p << endl;
cout << "q=" << r.q << endl;
cout << "f=(p-1)*(q-1)=" << r.f << endl;
cout << "n=p*q=" << r.n << endl;
cout << "e=" << r.e << endl;
cout << "d=" << r.d << endl;
cout << "s=" << r.s << endl;
cout << "Source:" << pSrc << endl;
q = (unsigned char *)pSrc;
cout << "Encode:";
for (unsigned long i = 0; i < n; i++)
{
unsigned __int64 temp = (unsigned __int64)q[i];
pEnc[i] = PowMod(temp, r.e, r.n);
cout << hex << pEnc[i] << " ";
}
cout << endl;
cout << "Decode:";
for (unsigned long i = 0; i < n; i++)
{
pDec[i] = PowMod(pEnc[i], r.d, r.n);
cout << hex << (unsigned long)pDec[i] << " ";
}
cout << endl;
cout << (char *)pDec << endl;
}
int main(void)
{
TestRSA();
return 0;
}
相关优化:
- 大数乘法优化，快速傅立叶变换
- 模乘优化，Montgomery算法及其改进
- 素数生成优化，随机数生成和素性测试,前者要保证正确和高效，比如AKS素数测试，后者要保证安全性，即生成统计意义上的真随机数
内容总结
以上是互联网集市为您收集整理的数字签名与身份认证: RSA算法指北全部内容，希望文章能够帮你解决数字签名与身份认证: RSA算法指北所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】