- ardim
-
RSA遭受攻击的很多情况是因为算法实现的一些细节上的漏洞所导致的,所以在使用RSA算法构造密码系统时,为保证安全,在生成大素数的基础上,还必须认真仔细选择参数,防止漏洞的形成。根据RSA加解密过程,其主要参数有三个:模数N,加密密钥e,解密密钥d。
3.4.1 模数N的确定
虽然迄今人们无法证明,破解RSA系统等于对N因子分解,但一般相信RSA系统的安全性等同于因子分解,即:若能分解因子N,即能攻破RSA系统,若能攻破RSA系统,即能分解因子Ⅳ。因此,在使用RSA系统时,对于模数N的选择非常重要。在RSA算法中,通过产生的两个大素数p和q相乘得到模数N,而后分别通过对它们的数学运算得到密钥对。由此,分解模数N得到p和q是最显然的攻击方法,当然也是最困难的方法,如果模数N被分解,攻击者利用得到的P和q便可计算出,进而通过公开密钥e由解密密钥d,则RSA体制立刻被攻破。相当一部分的对RSA的攻击就是试图分解模数N,选择合适的N是实现RSA算法并防止漏洞的重要环节。一般地,模数N的确定可以遵循以下几个原则:
①p和q之差要大。
当p和q相差很小时,在已知n的情况下,可假定二者的平均值为,然后利用,若等式右边可开方,则得到及,即N被分解。
②p-1和q-1的最大公因子应很小。
③p和q必须为强素数。
一素数p如果满足:
条件一:存在两个大素数,,使得|p-1且|p+1;
条件二:存在四个大素数,,,使得。则此素数为强素数。其中,,,称为3级的素数,,称为2级的素数,p则称为1级的素数,很明显地,任何素数均为3级的素数。只有两个强素数的积所构成的N,其因子分解才是较难的数学问题。
④p和q应大到使得因子分解N为计算上不可能。
RSA的安全性依赖于大数的因子分解,若能因子分解模数N,则RSA即被攻破,因此模数N必须足够大直至因子分解N在计算上不可行。因子分解问题为密码学最基本的难题之一,如今,因子分解的算法已有长足的进步,但仍不足以说明RSA可破解。为保证安全性,实际应用中所选择的素数P和拿至少应该为300位以上的二进制数,相应的模数N将是600位以上的二进制数。
目前,SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥,其他实体使用1024比特的密钥。随着计算能力的提高和分布式运算的发展,安全密钥的长度将是动态增长的。
Jadith Moore给出了使用RSA时有关模数的一些限制:
①若给定模数的一个加/解密密钥指数对已知,攻击者就能分解这个模数。
②若给定模数的一个加/解密密钥指数对已知,攻击者无需分解模数Ⅳ就可以计算出别的加/解密密钥指数对。
③在通信网络中,利用RSA的协议不应该使用公共模数。
④消息应该用随机数填充以避免对加密指数的攻击。
3.4.2 e的选取原则
在RSA算法中,e和互质的条件容易满足,如果选择较小的e,则加、解密的速度加快,也便于存储,但会导致安全问题。
一般地,e的选取有如下原则:
①e不能够太小。在RSA系统中,每人的公开密钥P只要满足即可,也即e可以任意选择,为了减少加密运算时间,很多人采用尽可能小的e值,如3。但是已经证明低指数将会导致安全问题,故此,一般选择e为16位的素数,可以有效防止攻击,又有较快速度。
②e应选择使其在的阶为最大。即存在i,使得,
可以有效抗击攻击。
3.4.3 d的选取原则
一般地,私密密钥d要大于。在许多应用场合,常希望使用位数较短的密钥以降低解密或签名的时间。例如IC卡应用中,IC卡CPU的计算能力远低于计算机主机。长度较短的d可以减少IC卡的解密或签名时间,而让较复杂的加密或验证预算(e长度较长)由快速的计算机主机运行。一个直接的问题就是:解密密钥d的长度减少是否会造成安全性的降低?很明显地,若d的长度太
小,则可以利用已知明文M加密后得,再直接猜测d,求出是否等于M。若是,则猜测J下确,否则继续猜测。若d的长度过小,则猜测的空间变小,猜中的可能性加大,已有证明当时,可以由连分式算法在多项式时间内求出d值。因此其长度不能过小。
- 黑桃云
-
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
int str2num(char *str) //字符转数字
{
int i=0,num=0;
for(i=0;i<(int)strlen(str);i++)
num=num*10+str[i]-"0";
return num;
}
float CarmSqrt(float x) //求平方根 系统的太慢,用了别人的
{
union
{
int intPart;
float floatPart;
}convertor;
union
{
int intPart;
float floatPart;
}convertor2;
convertor.floatPart = x;
convertor2.floatPart = x;
convertor.intPart = 0x1FBCF800 + (convertor.intPart >> 1);
convertor2.intPart = 0x5f3759df - (convertor2.intPart >> 1);
return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));
}//可以不用,用sqrt()也可以
int isPrime(int n) //判断是否为素数
{
int i=0,k=2;
k=(int)CarmSqrt(n);
for(i=2;i<=k;i++)
{
if(n%i==0)
break;
}
if(i>k)
return 1;
else
return 0;
}
int rnd(int max) //生成随机数 2~max 用来生成e,
{ //取系统时间做随机数种子
int range,n;
int min=2,flag=0;
time_t t;
double j;
range=max-min;
t=time(NULL);
srand((unsigned)t);
n=rand();
j=((double)n/(double)RAND_MAX);
n=(int)(j*(double)range);
n+=min;
return n;
}
int co_prime(int a ,int b) // 求互质
{
int c;
do
{
if(b==1)
return 1;
c=a%b;
a=b;
b=c;
}while(c!=0);
return 0;
}
void get_d_e(int p,int q)
{
int r,t,e,d,i=2,k=0;
if(isPrime(p)!=1||isPrime(q)!=1)
{
printf("Invaild Parameters should be PRIME! ");
printf("Usage:RSA Prime1 Prime2 ");
exit(0);
}
r=p*q;
t=(p-1)*(q-1);
e=rnd(t)/10;
while(co_prime(t,e)!=1)
{
e=e+1;
}
for(d=2;d<t;d++)
{
if((e*d)%t==1)
break;
}
printf("d=%d e=%d r=%d ",d,e,r);
}
void en(int n,int e,int r)
{
//加密
}
void de(int c,int d,int r)
{
//解密
}
void main(int argc,char* argv[])
{
int n1,n2;
if(argc!=3&&argc!=5)
{
printf("Invaild Parameters! ");
printf("Usage: RSA -e Express e r ");
printf("RSA -d Ciphertext d r ");
printf("RSA Prime1 Prime2 ");//错误输出
exit(0);
}
else
if(argv[1][0]!="-")
{
n1=str2num(argv[1]);
n2=str2num(argv[2]);
get_d_e(n1,n2);
exit(0);
}
else
if(argv[1][1]=="e") //加密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
if(argv[1][1]=="d") //解密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
else{
printf("Invaild Parameters! ");
printf("Usage: RSA -e Express e r ");
printf("RSA -d Ciphertext d r ");
printf("RSA Prime1 Prime2 ");
exit(0);
}
}
- 里论外几
-
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
int str2num(char *str) //字符转数字
{
int i=0,num=0;
for(i=0;i<(int)strlen(str);i++)
num=num*10+str[i]-"0";
return num;
}
float CarmSqrt(float x) //求平方根 系统的太慢,用了别人的
{
union
{
int intPart;
float floatPart;
}convertor;
union
{
int intPart;
float floatPart;
}convertor2;
convertor.floatPart = x;
convertor2.floatPart = x;
convertor.intPart = 0x1FBCF800 + (convertor.intPart >> 1);
convertor2.intPart = 0x5f3759df - (convertor2.intPart >> 1);
return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));
}//可以不用,用sqrt()也可以
int isPrime(int n) //判断是否为素数
{
int i=0,k=2;
k=(int)CarmSqrt(n);
for(i=2;i<=k;i++)
{
if(n%i==0)
break;
}
if(i>k)
return 1;
else
return 0;
}
int rnd(int max) //生成随机数 2~max 用来生成e,
{ //取系统时间做随机数种子
int range,n;
int min=2,flag=0;
time_t t;
double j;
range=max-min;
t=time(NULL);
srand((unsigned)t);
n=rand();
j=((double)n/(double)RAND_MAX);
n=(int)(j*(double)range);
n+=min;
return n;
}
int co_prime(int a ,int b) // 求互质
{
int c;
do
{
if(b==1)
return 1;
c=a%b;
a=b;
b=c;
}while(c!=0);
return 0;
}
void get_d_e(int p,int q)
{
int r,t,e,d,i=2,k=0;
if(isPrime(p)!=1||isPrime(q)!=1)
{
printf("Invaild Parameters should be PRIME! ");
printf("Usage:RSA Prime1 Prime2 ");
exit(0);
}
r=p*q;
t=(p-1)*(q-1);
e=rnd(t)/10;
while(co_prime(t,e)!=1)
{
e=e+1;
}
for(d=2;d<t;d++)
{
if((e*d)%t==1)
break;
}
printf("d=%d e=%d r=%d ",d,e,r);
}
void en(int n,int e,int r)
{
//加密
}
void de(int c,int d,int r)
{
//解密
}
void main(int argc,char* argv[])
{
int n1,n2;
if(argc!=3&&argc!=5)
{
printf("Invaild Parameters! ");
printf("Usage: RSA -e Express e r ");
printf("RSA -d Ciphertext d r ");
printf("RSA Prime1 Prime2 ");//错误输出
exit(0);
}
else
if(argv[1][0]!="-")
{
n1=str2num(argv[1]);
n2=str2num(argv[2]);
get_d_e(n1,n2);
exit(0);
}
else
if(argv[1][1]=="e") //加密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
if(argv[1][1]=="d") //解密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
else{
printf("Invaild Parameters! ");
printf("Usage: RSA -e Express e r ");
printf("RSA -d Ciphertext d r ");
printf("RSA Prime1 Prime2 ");
exit(0);
}
- 南yi
-
#include
<stdio.h>
#include
<string.h>
#include
<time.h>
#include
<stdlib.h>
#include
<math.h>
int
str2num(char
*str)
//字符转数字
{
int
i=0,num=0;
for(i=0;i<(int)strlen(str);i++)
num=num*10+str[i]-"0";
return
num;
}
float
CarmSqrt(float
x)
//求平方根
系统的太慢,用了别人的
{
union
{
int
intPart;
float
floatPart;
}convertor;
union
{
int
intPart;
float
floatPart;
}convertor2;
convertor.floatPart
=
x;
convertor2.floatPart
=
x;
convertor.intPart
=
0x1FBCF800
+
(convertor.intPart
>>
1);
convertor2.intPart
=
0x5f3759df
-
(convertor2.intPart
>>
1);
return
0.5f*(convertor.floatPart
+
(x
*
convertor2.floatPart));
}//可以不用,用sqrt()也可以
int
isPrime(int
n)
//判断是否为素数
{
int
i=0,k=2;
k=(int)CarmSqrt(n);
for(i=2;i<=k;i++)
{
if(n%i==0)
break;
}
if(i>k)
return
1;
else
return
0;
}
int
rnd(int
max)
//生成随机数
2~max
用来生成e,
{
//取系统时间做随机数种子
int
range,n;
int
min=2,flag=0;
time_t
t;
double
j;
range=max-min;
t=time(NULL);
srand((unsigned)t);
n=rand();
j=((double)n/(double)RAND_MAX);
n=(int)(j*(double)range);
n+=min;
return
n;
}
int
co_prime(int
a
,int
b)
//
求互质
{
int
c;
do
{
if(b==1)
return
1;
c=a%b;
a=b;
b=c;
}while(c!=0);
return
0;
}
void
get_d_e(int
p,int
q)
{
int
r,t,e,d,i=2,k=0;
if(isPrime(p)!=1||isPrime(q)!=1)
{
printf("Invaild
Parameters should
be
PRIME! ");
printf("Usage:RSA
Prime1
Prime2 ");
exit(0);
}
r=p*q;
t=(p-1)*(q-1);
e=rnd(t)/10;
while(co_prime(t,e)!=1)
{
e=e+1;
}
for(d=2;d<t;d++)
{
if((e*d)%t==1)
break;
}
printf("d=%d
e=%d
r=%d ",d,e,r);
}
void
en(int
n,int
e,int
r)
{
//加密
}
void
de(int
c,int
d,int
r)
{
//解密
}
void
main(int
argc,char*
argv[])
{
int
n1,n2;
if(argc!=3&&argc!=5)
{
printf("Invaild
Parameters! ");
printf("Usage:
RSA
-e
Express
e
r ");
printf("RSA
-d
Ciphertext
d
r ");
printf("RSA
Prime1
Prime2 ");//错误输出
exit(0);
}
else
if(argv[1][0]!="-")
{
n1=str2num(argv[1]);
n2=str2num(argv[2]);
get_d_e(n1,n2);
exit(0);
}
else
if(argv[1][1]=="e")
//加密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
if(argv[1][1]=="d")
//解密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
else{
printf("Invaild
Parameters! ");
printf("Usage:
RSA
-e
Express
e
r ");
printf("RSA
-d
Ciphertext
d
r ");
printf("RSA
Prime1
Prime2 ");
exit(0);
}
}
- 再也不做稀饭了
-
#include
<stdio.h>
#include
<string.h>
#include
<time.h>
#include
<stdlib.h>
#include
<math.h>
int
str2num(char
*str)
//字符转数字
{
int
i=0,num=0;
for(i=0;i<(int)strlen(str);i++)
num=num*10+str[i]-"0";
return
num;
}
float
CarmSqrt(float
x)
//求平方根
系统的太慢,用了别人的
{
union
{
int
intPart;
float
floatPart;
}convertor;
union
{
int
intPart;
float
floatPart;
}convertor2;
convertor.floatPart
=
x;
convertor2.floatPart
=
x;
convertor.intPart
=
0x1FBCF800
+
(convertor.intPart
>>
1);
convertor2.intPart
=
0x5f3759df
-
(convertor2.intPart
>>
1);
return
0.5f*(convertor.floatPart
+
(x
*
convertor2.floatPart));
}//可以不用,用sqrt()也可以
int
isPrime(int
n)
//判断是否为素数
{
int
i=0,k=2;
k=(int)CarmSqrt(n);
for(i=2;i<=k;i++)
{
if(n%i==0)
break;
}
if(i>k)
return
1;
else
return
0;
}
int
rnd(int
max)
//生成随机数
2~max
用来生成e,
{
//取系统时间做随机数种子
int
range,n;
int
min=2,flag=0;
time_t
t;
double
j;
range=max-min;
t=time(NULL);
srand((unsigned)t);
n=rand();
j=((double)n/(double)RAND_MAX);
n=(int)(j*(double)range);
n+=min;
return
n;
}
int
co_prime(int
a
,int
b)
//
求互质
{
int
c;
do
{
if(b==1)
return
1;
c=a%b;
a=b;
b=c;
}while(c!=0);
return
0;
}
void
get_d_e(int
p,int
q)
{
int
r,t,e,d,i=2,k=0;
if(isPrime(p)!=1||isPrime(q)!=1)
{
printf("Invaild
Parameters should
be
PRIME! ");
printf("Usage:RSA
Prime1
Prime2 ");
exit(0);
}
r=p*q;
t=(p-1)*(q-1);
e=rnd(t)/10;
while(co_prime(t,e)!=1)
{
e=e+1;
}
for(d=2;d<t;d++)
{
if((e*d)%t==1)
break;
}
printf("d=%d
e=%d
r=%d ",d,e,r);
}
void
en(int
n,int
e,int
r)
{
//加密
}
void
de(int
c,int
d,int
r)
{
//解密
}
void
main(int
argc,char*
argv[])
{
int
n1,n2;
if(argc!=3&&argc!=5)
{
printf("Invaild
Parameters! ");
printf("Usage:
RSA
-e
Express
e
r ");
printf("RSA
-d
Ciphertext
d
r ");
printf("RSA
Prime1
Prime2 ");//错误输出
exit(0);
}
else
if(argv[1][0]!="-")
{
n1=str2num(argv[1]);
n2=str2num(argv[2]);
get_d_e(n1,n2);
exit(0);
}
else
if(argv[1][1]=="e")
//加密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
if(argv[1][1]=="d")
//解密
{
n1=str2num(argv[3]);
n2=str2num(argv[4]);
en(str2num(argv[2]),n1,n2);
exit(0);
}
else{
printf("Invaild
Parameters! ");
printf("Usage:
RSA
-e
Express
e
r ");
printf("RSA
-d
Ciphertext
d
r ");
printf("RSA
Prime1
Prime2 ");
exit(0);
}