数学与软件科学学院 实验报告
学期:_2011_至_2012_ 第__2 学期 20## 年 月 日
课程名称: _ 专业:信息与计算科学 _2009_级_06_班
实验编号: 实验项目 _ 指导教师_ _
姓名: 林海 学号: 2009060619 实验成绩: ___
实验1-2 对称密码算法DES
一.实验原理
信息加密根据采用的密钥类型可以划分为对称密码算法和非对称密码算法。对称密码算法是指加密系统的加密密钥和解密密钥相同,或者虽然不同,但是可以从其中任意一个推导出另一个,更形象的说就是用同一把钥匙开锁和解锁。在对称密码算法的发展历史中曾出现过多种优秀的算法,包括DES、3DES、AES等。下面我们以DES算法为例介绍对称密码算法的实现机制。
DES算法是有美国IBM公司在20世纪70年代提出,并被美国政府、美国国家标准局和美国国家标准协会采纳和承认的一种标准加密算法。它属于分组加密算法,即明文加密和密文解密过程中,信息都是按照固定长度分组后进行处理的。混淆和扩散是它采用的两个最重要的安全特性,混淆是指通过密码算法使明文和密文以及密钥的关系非常复杂,无法从数学上描述或者统计。扩散是指明文和密钥中每一位信息的变动,都会影响到密文中许多位信息的变动,从而隐藏统计上的特性,增加密码安全。
DES将明文分成64比特位大小的众多数据块,即分组长度为64位。同时用56位密钥对64位明文信息加密,最终形成64位的密文。如果明文长度不足64位,则将其扩展为64位(例如补零等方法)。具体加密过程首先是将输入的数据进行初始换位(IP),即将明文M中数据的排列顺序按一定的规则重新排列,生成新的数据序列,以打乱原来的次序。然后将变换后的数据平分成左右两部分,左边记为L0,右边记为R0,然后对R0施行在子密钥(由加密密钥产生)控制下的变换f,结果记为f(R0 ,K1),再与L0做逐位异或运算,其结果记为R1,R0则作为下一轮的L1。如此循环16轮,最后得到L16、R16,再对L16、R16施行逆初始置换IP-1,即可得到加密数据。解密过程与此类似,不同之处仅在于子密钥的使用顺序正好相反。
DES全部16轮的加密过程如图1-1所示。
DES的加密算法包括3个基本函数:
1. 初始换位(IP)
它的作用是把输入的64位数据块的排列顺序打乱,每位数据按照下面换位规则重新组合。即将第58位换到第1位,第50位换到第2位,…,依次类推。重组后的64位输出分为L0、R0(左、右)两部分,每部分分别为32位。
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
R0和K1经过f(R0,K1)变换后的输出结果,再和L0进行异或运算,输出结果做为R1。R0则赋给L1。L1和__________R1同样再做类似运算生成L2和R2,…,经过16次运算后生成L16和R16。
2.f函数
f函数是多个置换函数和替代函数的组合函数,它将32位比特的输入变换为32位的输出,如图1-2。Ri经过扩展运算E变换后扩展为48比特的E(Ri),与Ki+1进行异或运算后输出的结果分成8组,每组6比特的并联B,B=B1B2B3B4B5B6B7B8,再经过8个S盒的选择压缩运算转换为4比特,8个4比特合并为32比特后再经过P变换输出为32比特的f(Ri-1,Ki)。其中,扩展运算E与置换P主要作用是增加算法的扩散效果。
输入的初始密钥值为64位,但DES算法规定,其中第8、16、......64位是奇偶校验位,不参与DES运算。所以,实际可用位数只有56位,经过缩小选择换位表1(表1-2)即密钥置换PC-1的变换后,初始密钥的位数由64 位变成了56位,将其平分为两部分C0、D0,然后分别进行第1次循环左移,得到C1、D1,将C1(28位)、D1(28位)合并后得到56位的输出结果,再经过缩小选择换位表2(表1-2)即密钥置换PC-2,从而便得到了密钥K1(48位)。依此类推,便可得到K2、...... K16,需要注意的是,16次循环左移对应的左移位数要依据表1-1中规则进行。
二.实验目的:
通过用DES算法对实际的数据进行加密和解密来深刻了解DES的运行原理。
三.实验环境:
运行windows或linux操作系统的PC机,具有gcc(linux)、VC(windows)等C语言编译环境。
四.实验内容和步骤
1.算法分析
在光盘中附加了有关DES算法的程序,根据所提供的程序分析DES算法的实现过程。DES程序包括一个头文件和一个实现DES的C文件。头文件里主要是一些宏定义和函数声明,其中还包括保证可移植性的一些定义。DES程序通过宏定义可选择小代码模式(#define small_code)或者选择大代码模式。在大代码模式下,程序定义了多个表,从而使DES算法中的很多运算都通过查表实现,速度较快,但要求有较多的存储空间。在小代码模式运行时,可以不查表,从而节省了存储空间,但是速度较慢。读者可以根据自己的需求来选择不同的运行模式。
2.代码如下:
#include<stdio.h>
#include<math.h>
#include<string.h>
int des_P1(int i);/*P逆置换表*/
int des_P(int i);/*P置换表*/
int des_E(int i);/*E置换表*/
int des_Exchange2(int i);/*选择置换2表*/
int des_Exchange1(int i);/*选择置换1表*/
int des_Ip(int i);/*IP置换表*/
char des_S(char ER_K[16][48],char Temp3[16][32],int k);/*S盒子函数*/
char des_SubKey(char Key[64],char K[17][48]);/*计算密钥函数*/
char des_encrypt(char K[17][48],char L[17][32],char R[17][32],int k);/*加密函数*/
/*P逆置换表*/
int des_P1(int i)
{
int P1[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};
return P1[i];
}
/*P置换表*/
int des_P(int i)
{
int P[32]={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};
return P[i];
}
/*E置换表*/
int des_E(int i)
{
int E[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};
return E[i];
}
/*选择置换2表*/
int des_Exchange2(int i)
{
int Exchange2[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};
return Exchange2[i];
}
/*选择置换1表*/
int des_Exchange1(int i)
{
int Exchange1[56]={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};
return Exchange1[i];
}
/*IP置换表*/
int des_Ip(int i)
{
int 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};
return Ip[i];
}
/*计算密钥函数,通过K[][]返回子密钥*/
char des_SubKey(char Key[64],char K[17][48])
{
int i,j;
char Temp1[56];
char C[17][28],D[17][28];
char Temp2[17][56];
j=0;
for(i=0;i<56;i++)
{
/*通过选择置换1表对密钥Key进行选择,并返回给Temp1[]*/
Temp1[i]=Key[des_Exchange1(i)-1];
}
for(i=0;i<56;i++)
{
if(i<28)
{
/*求出Temp1[]左边一半,并返回给C[0][]*/
C[0][i]=Temp1[i];
}
if(i>=28)
{
/*求出Temp1[]右边一半,并返回给D[0][]*/
D[0][i-28]=Temp1[i];
}
}
/*从C[0][],D[0][]开始循环左移,并存储在C[][],D[][]中*/
for(i=1;i<17;i++)
{
/*循环左移一位*/
if(i==1||i==2||i==9||i==16)
{
for(j=0;j<27;j++)
{
C[i][j]=C[i-1][j+1];
D[i][j]=D[i-1][j+1];
}
C[i][27]=C[i-1][0];
D[i][27]=D[i-1][0];
}
/*循环左移两位*/
else
{
for(j=0;j<26;j++)
{
C[i][j]=C[i-1][j+2];
D[i][j]=D[i-1][j+2];
}
C[i][26]=C[i-1][0];
C[i][27]=C[i-1][1];
D[i][26]=D[i-1][0];
D[i][27]=D[i-1][1];
}
}
/*将循环左移产生的C[][],D[][]左右连接在一起,并存储在Temp2[][]中*/
for(i=1;i<17;i++)
{
for(j=0;j<28;j++)
{
Temp2[i][j]=C[i][j];
Temp2[i][j+28]=D[i][j];
}
}
/*对Temp2[][]进行选择置换1表,产生子密钥K[][]*/
for(i=1;i<17;i++)
{
for(j=0;j<48;j++)
{
K[i][j]=Temp2[i][des_Exchange2(j)-1];
}
}
/*返回子密钥K[][]*/
return K[17][48];
}
/*S盒子函数*/
char des_S(char ER_K[16][48],char Temp3[16][32],int k)
{
int i,j,a,b,t,m,n,num=1;
int S1[4][16]={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};
int S2[4][16]={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};
int S3[4][16]={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};
int S4[4][16]={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};
int S5[4][16]={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};
int S6[4][16]={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};
int S7[4][16]={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};
int S8[4][16]={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};
for(i=0;i<8;i++)
{
/*将(6*i+1)和(6*i+6)组成的二进制数转换成十进制数,并返回给a*/
a=((int)ER_K[k][6*i+0]-48)*2+(int)ER_K[k][6*i+5]-48;
/*将(6*i+1)和(6*i+6)中间组成的二进制数转换成十进制数,并返回给b*/
b=((int)ER_K[k][6*i+1]-48)*8+((int)ER_K[k][6*i+2]-48)*4+((int)ER_K[k][6*i+3]-48)*2+(int)ER_K[k][6*i+4]-48;
/*通过选择来对S盒中的不同选择矩阵进行求值,并返回给t*/
switch(num)
{
case 1:t=S1[a][b];break;
case 2:t=S2[a][b];break;
case 3:t=S3[a][b];break;
case 4:t=S4[a][b];break;
case 5:t=S5[a][b];break;
case 6:t=S6[a][b];break;
case 7:t=S7[a][b];break;
case 8:t=S8[a][b];break;
}
num++;
/*将选择产生的十进制数转换成二进制数,并返回给Temp3[][]*/
for(j=3;j>=0;j--)
{
m=t%2;
t=t/2;
Temp3[k][4*i+j]=(char)(m+48);
}
}
/*返回Temp3[][]*/
return Temp3[16][32];
}
/*加密函数*/
char des_encrypt(char K[17][48],char L[17][32],char R[17][32],int k)
{
int i,j;
char ER[16][48];
char ER_K[16][48];
char fR_K[16][32];
char Temp3[16][32];
/*对R[]进行E置换,并返回给ER[][]*/
for(i=0;i<48;i++)
{
ER[k][i]=R[k][des_E(i)-1];
}
/*------------------------------*/
/*对ER[][]和K[][]进行模2运算,并返回给ER_K[][]*/
for(i=0;i<48;i++)
{
if(ER[k][i]==K[k+1][i])
ER_K[k][i]='0';
else
ER_K[k][i]='1';
}
printf("ER_K[%d]=",k);
for(i=0;i<48;i++)
{
printf("%c",ER_K[k][i]);
}
printf("\n");
/*------------------------------*/
des_S(ER_K,Temp3,k);
printf("S[%d]=",k);
for(i=0;i<32;i++)
{
printf("%c",Temp3[k][i]);
}
printf("\n");
/*-------------------------------*/
/*将S盒子返回回来的Temp3进行P置换表选择后,返回给fR_K[][]*/
for(i=0;i<32;i++)
{
fR_K[k][i]=Temp3[k][des_P(i)-1];
}
printf("fR_K[%d]=",k);
for(i=0;i<32;i++)
{
printf("%c",fR_K[k][i]);
}
printf("\n");
/*--------------------------------*/
/*将fR_K[][]和L[][]进行模2运算,并返回给R[][]*/
for(i=0;i<32;i++)
{
if(fR_K[k][i]==L[k][i])
R[k+1][i]='0';
else
R[k+1][i]='1';
}
/*将R[k][]的值赋给L[k+1][]*/
for(i=0;i<32;i++)
{
L[k+2][i]=R[k+1][i];
}
printf("R[%d]=",k+1);
for(i=0;i<32;i++)
{
printf("%c",R[k+1][i]);
}
printf("\n");
/*返回L[][],R[][]*/
return L[17][32],R[17][32];
}
int main()
{
/*------------------------*/
int i,j,k=0;
char M[64],C[64],Key[64],Temp[64],Temp4[64];
char L[17][32],R[17][32];
char K[17][48];
clrscr();
/*------------------------*/
printf("This is DES...........\n");
/*显示输入明文*/
printf("Please input...M...\n");
gets(M);
/*显示输入密钥*/
printf("Please input...K...\n");
gets(Key);
/*------------------------*/
des_SubKey(Key,K);
for(i=1;i<17;i++)
{
printf("K[%d]=",i);
for(j=0;j<48;j++)
printf("%c",K[i][j]);
printf("\n");
}
/*-------------------------*/
/*对明文进行IP置换,并返回给Temp[]*/
for(i=0;i<64;i++)
{
Temp[i]=M[des_Ip(i)-1];
}
/*将IP置换后的明文进行左右划分,产生L[0][]和R[0][]*/
for(i=0;i<64;i++)
{
if(i<32)
{
L[0][i]=Temp[i];
}
if(i>=32)
{
R[0][i-32]=Temp[i];
L[1][i-32]=Temp[i];
}
}
printf("\nL[0]=");
for(i=0;i<32;i++)
{
printf("%c",L[0][i]);
}
printf("\nR[0]=");
for(i=0;i<32;i++)
{
printf("%c",R[0][i]);
}
printf("\n");
/*通过循环进行16次加密(加密函数每次调用仅进行一次运算)*/
while(k<16)
{
des_encrypt(K,L,R,k);
k++;
}
/*将R[16][]和L[16][]左右连接在一起,并返回给Temp4[]*/
for(i=0;i<64;i++)
{
if(i<32)
Temp4[i]=R[16][i];
else
Temp4[i]=L[16][i-32];
}
/*对Temp4[]进行P的逆置换,产生密文,并返回给C[]*/
for(i=0;i<64;i++)
{
C[i]=Temp4[des_P1(i)-1];
}
printf("C is...");
for(i=0;i<64;i++)
{
printf("%c",C[i]);
}
/*------------------------*/
getch();
return 0;
}
3.实验截图
本程序用的是课本中P35 的例子。
//输入 明文和密钥
//得出的过程数据和最终的结果与课本上一致。
五.总结
这次的DES,我是通过将数变成字符串来处理的,如果直接用数组或者指针的形式来处理会更加的好,所以程序还有待完善的地方。通过此次实验,我对DES有更加深刻的认识,对整个加密过程都有了一个清晰的认识。