密码学课程设计实验报告
专业:信息安全
班级:0903
姓名:付晓帆
学号:U200915328
一、 DES 的编程实现
1.实验目的
通过实际编程掌握DES的加、脱密及密钥生成过程,加深对DES算法的认识。
2.实验原理
a.加密过程
DES是一个分组密码,使用长度为56比特的密钥加密长度为64比特的明文,获得长度为64比特的密文,其加密过程:
(1) 给定一个明文X,通过一个固定的初始置换IP置换X的比特,获得X0,X0=IP(X)=L0R0,L0R0分别是X0的前32比特和后32比特。
(2) 然后进行16轮完全相同的运算,有如下规则,其中0<i<17,K1, K2……,K16都是密钥K的函数,长度均为48比特:
其中函数f(A,J)的A是一个长度为32的比特串,第二个变量J是一个长度为48的比特串,输出的是一个长度为32的比特串,其过程:
a、将f的第一个变量A根据一个固定的扩展函数E扩展成为一个长度为48的比特串
b、计算,并将所得结果分成8个长度为6的比特串,记为B=B1B2B3B4B5B6B7B8
c、使用8个S盒,每个Si是一个固定的4X16阶矩阵,它的元素来自0到15这16个整数。给定一个长度为6的比特串,用首位两个比特作行号,用中间四个比特作为列号,则Sj(Bj)的取值就是Sj的行号列号的整数所对应的二进制表示。记Cj=Sj(Bj),0<j<9,
8个S盒为:
S1:
14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
S2:
15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
S3:
10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
S4:
7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
S5:
2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
S6:
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
S7:
4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
S8:
13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11,
d、将长度为32的比特串C=C1 C2 C3 C4 C5 C6 C7 C8通过一个固定的置换P置换,将所得结果P(C)记为f(A,J)。
(3) 对比特串R16 L16应用初始置换IP的逆置换IP-1,获得密文Y,即Y=IP-1(R16 L16)。
b.子密钥生成过程
密钥方案计算:每一轮都是用不同的、从初始密钥或称种子密钥K导出的48比特密钥Ki。K是一个长度为64的比特串,实际上除去校验比特只有56比特有效:
(1) 给定一个64比特的密钥K,删掉8个校验比特并利用一个固定的置换PC-1置换K的剩下的56比特,记PC-1(K) = C0D0,这里C0D0是PC-1(K)的前28比特、后28比特。
(2) 对每一个i,0<i<17,计算:
其中LSi表示一个或两个位置的左循环移位,当i=1,2,9,4,16时,一个位置,当i=3,4,5,6,7,8,10,11,12,13,14,15时,移动两个位置。PC-2是另一个固定置换。
C. 解密过程
与加密的过程相同,是加密的逆过程,区别在于加密输入明文输出密文而脱密输入密文输出明文,16个内部密钥加密的顺序和解密的顺序相反。
d.加密算法流程图
(1) 加密算法
输入64比特明文X,经过16轮变换,输出64比特密文Y
(2) F函数
Ri-1经过E扩展与K(i)异或,通过S盒变换后进行P置换得到32比特的输出
(3) 子密钥生成过程
种子密钥通过PC-1变换后,CiDi左移并经过PC-2变换得到Ki
(4) 程序结构图
3. 实验要求
a. 输入一串有意义的汉字,显示密文和脱密结果;
b. 设计用户窗口;
c. 实验环境说明:操作系统、机型、语言。
4. DES的实现
a. 开发环境
主机:
Microsoft Windows XP Professional 版本2002 ServicePack3
Intel(R) Core(TM)2 Duo CPU T6570 @2.10GHz 2.09GHz,1.99GB的内存物理地址扩展
编程工具:
Visual C++ 6.0
功能测试:如图所示:
相关函数:
void ByteToBit(bool *Out, const char *In, int bits);
//字符转换成字节
void BitToByte(char *Out,const bool *In,int bits)
//字节转换成字符
void RotateL(bool*In,int len,int loop)
//循环左移
void Xor(bool*InA,const bool*InB,int len)
//异或
void Transform(bool*Out,bool*In,const char*Table,int len)
//各个置换转换
void S_func(bool Out[32],const bool In[48])
//将48位转换成32位
void F_func(bool In[32],const bool Ki[48])
//F函数
void SetKey(char key[8])
//生成子密钥
void CDES::Encryption(char out[8],char In[8])
//加密函数
void CDES::Decryption(char out[8],char In[8])
//解密函数
二、 DES的弱密钥检测
1、什么是DES弱密钥
DES的解密过程,DES的解密过程和DES的加密过程完全类似,只不过将16圈的子密钥序列K1,K2……K16的顺序倒过来。即第一圈用第16个子密钥K16,第二圈用K15,其余类推。
如果K16=K1,K15=K2,…,K9=K8,则加密所用的子密钥与解密所用的子密钥相同,对一个明文X加密两次,得到的还是明文X。
更强的,若K1=K2=…=K16,则加密过程与解密过程完全一样。
弱密钥的定义也就是这样定义:若k使得加密函数与解密函数一致,则称k为弱密钥。
DES至少有4个弱密钥,让我们先来看看子密钥的产生过程:
64Bits的密钥K经PC-1之后,变为56Bits,然后分为高28Bits和低28Bits,分别进行移位。
LSi是循环左移。PC-2是从56Bits中选出48Bits输出。若C0和D0为全0或全1,则经过移位后显然不变,于是16个子密钥都相同。C0和D0是独立进行移位的,组合一下,就有4个弱密钥了。因此至少有4个弱密钥。
(1)K1=…=K16=0x000000000000
(2)K1=…=K16=0xFFFFFFFFFFFF
(3)K1=…=K16=0x000000FFFFFF
(4)K1=…=K16=0xFFFFFF000000
还可以注意到,第一组和第二组是互补的,第三组和第四组也是互补的。
事实上,对于任意密钥k,我们还有以下关系成立:(DES的互补性)
若y=Des(k,X),则yBar=DES(kBar,XBar)。(后缀Bar表示取补)
2、检测方法
检测16个内部密钥是否完全相同,若完全相同则判断为弱密钥,否则为正常密钥
3、检测弱密钥实现
在DES程序中加入一个弱密钥检测函数,通过检测其16个内部密钥是否相同,来判断所输入的密钥是否为弱密钥。所加入函数如下:
bool CheckKey(char* key)
{
SetKey(key);
char A[6],B[6];
for(int i=1,j=16;i<=16,j>=1;i++,j--)
{
BitToByte(B,SubKey[i],48);
BitToByte(A,SubKey[j],48);
//若16个子密钥完全相同,则为弱密钥
if (memcmp((void*)A,(void*)B,6) )
return 1;
else return 0;
}
}
4、实验过程
(1)输入密钥00000000,程序显示为弱密钥。
(2)输入密钥3e96GR4J,检测显示为非弱密钥。
5、实验源代码
#include<iostream>
#include <string>
using namespace std;
const static char IP[64] =//初始置换
{
58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7
};
const static char EP1[56] =//密钥置换(原64位去掉奇偶校验位后)
{
57, 49, 41, 33, 25, 17, 9,
1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27,
19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15,
7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29,
21, 13, 5, 28, 20, 12, 4
};
const static char LOOP[16] =//左移
{
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
const static char EP2[48] =//选择子密钥
{
14, 17, 11, 24, 1, 5,
3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8,
16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55,
30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53,
46, 42, 50, 36, 29, 32
};
static const char EC[48] =//放大换位
{
32, 1, 2, 3, 4, 5,
4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1
};
const static char SBox[8][4][16] =//8个S盒
{
{
// S1
{ 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7 },
{ 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8 },
{ 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0 },
{ 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 }
},
{
// S2
{ 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10 },
{ 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5 },
{ 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15 },
{ 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 }
},
{
// S3
{ 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8 },
{ 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1 },
{ 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7 },
{ 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 }
},
{
// S4
{ 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15 },
{ 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9 },
{ 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4 },
{ 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 }
},
{
// S5
{ 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9 },
{ 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6 },
{ 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14 },
{ 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 }
},
{
// S6
{ 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11 },
{ 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8 },
{ 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6 },
{ 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 }
},
{
// S7
{ 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 },
{ 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6 },
{ 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2 },
{ 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 }
},
{
// S8
{ 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7 },
{ 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2 },
{ 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8 },
{ 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11 }
}
};
const static char PP[32] =//P盒置换
{
16, 7, 20, 21, 29, 12, 28, 17,
1, 15, 23, 26,5, 18, 31, 10,
2, 8, 24, 14,32, 27, 3, 9,
19, 13, 30, 6,22, 11, 4, 25,
};
const static char LP[64] =//末置换
{
40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25
};
static bool M[64], tmp[32], *Li = &M[0], *Ri = &M[32];
static bool SubKey[16][48];//16个子密钥
class CDES//定义DES类
{
public:
//void Mode();//模式
void Encryption(char out[8],char In[8]);//加密函数
void Decryption(char out[8],char In[8]);//解密函数
};
void ByteToBit(bool *Out, const char *In, int bits)//字符转换成字节
{
int i;
for(i=0;i<bits;i++)
{
// In[i]的第N位右移N位并和0x01按位"与"运算(N=1~8)
Out[i] = (In[i>>3]>>(i&7)) & 1;
}
}
void BitToByte(char *Out,const bool *In,int bits)//字节转换成字符
{
int i;
memset(Out,0,(bits+7)/8);
for(i=0;i<bits;i++)
{
Out[i>>3] |= In[i]<<(i&7);
}
}
void RotateL(bool*In,int len,int loop)//循环左移
{
static bool tmp[256];
memcpy(tmp,In,loop);
memcpy(In,In+loop,len-loop);
memcpy(In+len-loop,tmp,loop);
}
void Xor(bool*InA,const bool*InB,int len)//异或
{
int i;
for(i=0;i<len;i++)
{
InA[i]^=InB[i];
}
}
void Transform(bool*Out,bool*In,const char*Table,int len)//各个置换转换
{
int i;
static bool tmp[256];
for(i=0;i<len;i++)
{
tmp[i]=In[Table[i]-1];
}
memcpy(Out,tmp,len);
}
void S_func(bool Out[32],const bool In[48])//将48位转换成32位
{
int j,m,n;
//膨胀后的比特串分为8组,每组6比特。
for(j=0;j<8;j++,In+=6,Out+=4)
{
m = (In[0]*2)+In[5];
n = (In[1]*8)+(In[2]*4)+(In[3]*2)+In[4];
ByteToBit(Out,&SBox[j][m][n],4);
}
}
void F_func(bool In[32],const bool Ki[48])
{
static bool MR[48];
Transform(MR,In,EC,48);
Xor(MR, Ki, 48);
//膨胀后的比特串分为8组,每组6比特。各组经过各自的S盒后,又变为4比特,合并后又成为32比特。
S_func(In, MR);
//该32比特经过P变换后,输出的比特串才是32比特的f(Ri-1,Ki)。
Transform(In, In, PP, 32);
}
void SetKey(char key[8])//生成子密钥
{
int i;
static bool K[64], *KL = &K[0], *KR = &K[28];
ByteToBit(K,key,64); //转换为二进制
Transform(K,K,EP1,56); //64比特的密钥K,经过EP1后,生成56比特的串。
//生成16个子密钥
for(i=0;i<16;i++)
{
//循环左移,合并
RotateL(KL,28,LOOP[i]);
RotateL(KR,28,LOOP[i]);
Transform(SubKey[i],K,EP2,48);
}
}
bool CheckKey(char* key)
{
SetKey(key);
char A[6],B[6];
for(int i=1,j=16;i<=16,j>=1;i++,j--)
{
BitToByte(B,SubKey[i],48);
BitToByte(A,SubKey[j],48);
//若16个子密钥完全相同,则为弱密钥
if (memcmp((void*)A,(void*)B,6) ) return 1;
else return 0;
}
}
void CDES::Encryption(char out[8],char In[8])//加密函数
{
ByteToBit(M,In,64); //转换为二进制
Transform(M,M,IP,64);
for(int i=0;i<16;i++)
{
memcpy(tmp,Ri,32);
F_func(Ri,SubKey[i]);
Xor(Ri,Li,32);//将所得结果与明文的左32位进行异或
memcpy(Li,tmp,32);//将明文的左右32位交换
}
Transform(M, M, LP, 64);
BitToByte(out, M, 64);
// return(out);
}
void CDES::Decryption(char out[8],char In[8])//解密函数
{
ByteToBit(M,In,64); //转换为二进制
Transform(M,M,IP,64);
for(int i=15;i>=0;i--)
{
memcpy(tmp,Li,32);
F_func(Li,SubKey[i]);
Xor(Li,Ri,32);
memcpy(Ri,tmp,32);
}
Transform(M, M, LP, 64);
BitToByte(out, M, 64);
// return(out);
}
void main()
{ int c;
char key[10];
char str[128];
char str1[128];
cout<<"请输入要加密的字符:";
cin>>str;
cout<<"请设置密码(不多于8位):";
cin>>key;
c=CheckKey(key);
if(c)
printf("非弱密钥\n");
else printf("弱密钥\n");
SetKey(key);
memset(str1,0,sizeof(str1));
CDES des;
des.Encryption(str1,str);
cout<<"密文:"<<str1<<endl;
cout<<"是否解密(1.是;0.否)";
int n;
cin>>n;
if(n==1)
{
while(1)
{
cout<<"请输入密码:";
char sec[10];
cin>>sec;
if(strcmp(sec,key)==0)
{
memset(str,0,sizeof(str));
des.Decryption(str,str1);
cout<<"解密后明文:"<<str<<endl;
break;
}
else
cout<<"密码错误!"<<endl;
}
}
else
cout<<"过程结束!"<<endl;
}
三、RSA的快速实现
一、实验原理
1、选取长度相等的两个大素数p 和q,计算其乘积:
n = pq
然后随机选取加密密钥e,使e 和(p–1)(q–1)互素。
最后用欧几里德扩展算法计算解密密钥d,以满足
ed = 1(mod(p–1) ( q–1))
即d = e–1 mod((p–1)(q–1))
e 和n 是公钥,d 是私钥
2、加密公式如下:
ci = mi^e(mod n)
3、解密时,取每一密文分组ci 并计算:
mi = ci^d(mod n)
Ci^d =(mi^e)^d = mi^(ed) = mi^[k(p–1)(q–1)+1 ]
= mi mi^[k(p–1)(q–1)] = mi *1 = mi
4、消息也可以用d 加密用e 解密
二、实验目的
通过RSA加密算法的实现,进一步掌握RSA算法的原理,为今后的工程应用打下坚实的基础。
三、源程序
//RSA 算法的C 程序实现
#include <stdio.h>
int candp(int a,int b,int c) //数据处理函数,实现幂的取余运算
{ int r=1;
b=b+1;
while(b!=1)
{
r=r*a;
r=r%c;
b--;
}
printf("%d\n",r);
return r;
}
int fun(int x,int y) //公钥e 与t 的互素判断
{
int t;
while(y)
{
t=x;
x=y;
y=t%y;
}
if(x == 1)
return 0; //x 与y 互素时返回0
else
return 1; //x 与y 不互素时返回1
}
void main()
{
int p,q,e,d,m,n,t,c,r;
printf("请输入两个素数p,q: ");
scanf("%d%d",&p,&q);
n=p*q;
printf("计算得n 为%3d\n",n);
t=(p-1)*(q-1); //求n 的欧拉数
printf("计算得t 为%3d\n",t);
printf("请输入公钥e: ");
scanf("%d",&e);
if(e<1||e>t||fun(e,t))
{
printf("e 不合要求,请重新输入: "); //e<1 或e>t 或e 与t 不互素时,重新输入
scanf("%d",&e);
}
d=1;
while(((e*d)%t)!=1) d++; //由公钥e 求出私钥d
printf("经计算d 为%d\n",d);
printf("加密请输入1\n"); //加密或解密选择
printf("解密请输入2\n");
scanf("%d",&r);
switch(r)
{
case 1: printf("请输入明文m: "); //输入要加密的明文数字
scanf("%d",&m);
c=candp(m,e,n);
printf("密文为%d\n",c);break;
case 2: printf("请输入密文c: "); //输入要解密的密文数字
scanf("%d",&c);
m=candp(c,d,n);
printf("明文为%d\n",m);break;
}
}
四、实验过程
1、加密数据:
P=131,q=139, e=113,明文为1016,加密后密文为13163.
2、解密数据:
P=131,q=139, e=113,密文为13163,明文为1016.
五、程序运行结果及相关说明
主函数实现求N 的欧拉数、由公钥求解私钥、加密解密选择以及相应的密文明文输出。子函数candp 实现加密解密时的求幂取余运算,fun 实现e 与t 的互素判断,已验证e 是否符合要求。程序主体参考了网上的相关RSA 算法程序,我对其中e 的合法性判断、主函数实现的顺序以及相关提示信息做了补充与修改并加上了注释,这样程序可读性更强,运行时更容易操作,思路也更加严密。