S-DES加密解密算法C++版.doc

S-DES算法详解
其实跟上一篇一样,这还是网络安全的作业…
S-DES是DES算法的简化版,并没有什么实际使用的价值,只用于教学来理解DES算法的加密方法,这篇文章就是按照S-DES的算法来实际加密和解密的一段2进制数,演示了加密的运算过程.
下面从准备知识开始
先讲一下置换,举例说明,对”ABCDEFGH”做一下”82641753″置换的结果就是”HBFDAGEC”,这样就能看懂是怎么置换的了吧.
然后是循环移位,继续举例,”ABCDEFGH”循环左移2位结果就是”CDEFGHAB”.
还有个S盒的替代选择,具体到S-DES来说就是输入的四位数”ABCD”在S盒中找第AD行BC列的数字作为输出,比如0101输入S0(见下)的话就是第1(01)行第2(10)列(0-3行,0-3列),输出为1即01,再比如1001输入S0的话就是第3(11)行第0(00)列,输出为3即11.
最后是按位异或,举例的话1^1=0,1^0=1,0^1=1,0^0=0,1100^1010=0110,其实这个大家都懂吧.
好了,准备知识就这么多,下面开始正题:
S-DES算法的输入是一个8位的明文或者密文组和一个10位的密钥，输出是一个8位的密文或者明文组。

以下是S-DES所需的几个置换表
P10 {3,5,2,7,4,10,1,9,8,6}
P8 {6,3,7,4,8,5,10,9} 注意这个置换选择输入10位输出8位
P4 {2,4,3,1}
IP {2,6,3,1,4,8,5,7}
IPI {4,1,3,5,7,2,8,6}
EP {4,1,2,3,2,3,4,1} 注意这个是扩展置换,输入4位输出8位
以下是两个S盒
S0:
{1,0,3,2},
{3,2,1,0},
{0,2,1,3},
{3,1,3,2},
S1:
{0,1,2,3},
{2,0,1,3},
{3,0,1,0},
{2,1,0,3},

接下来就是加密和解密算法
首先讲子密钥的生成,子密钥在加密和解密算法中都有使用.
10位密钥 key = 01111 11101
对key做P10置换得到 11111 10011
记左半(高位)的为Lk=11111,右半(低位)为Rk=10011
Lk和Rk均循环左移1位,得到Lk=11111,Rk=00111
对Lk和Rk组合得到的11111 00111做P8置换选择,得到子密钥K1=0101 1111
Lk和Rk均再次循环左移2位,得到Lk=11111,Rk=11100
对Lk和Rk组合得到的11111 11100做P8置换选择,的到子密钥K2=1111 1100
以上,通过密钥得到了算法所需的子密钥.

下面是加密过程
首先是初始置换
对明文m=0001 0110做IP置换,得m’=0100 1001
接下来是标准的Feistel密码结构,共有两次循环
第一次循环
记左半(高位)为Lm=0100,右半(低位)为Rm=1001
对Rm做EP扩展置换,得Rm’=1100 0011
Rm’与子密钥K1按位异或,得Rm’=1001 1100
Rm’左半1001进入S0盒替代选择得11,右半1100进入S1盒替代选择的01,组合后得Rm’=1101
对Rm’做P4置换,得Rm’=1101
Rm’与Lm按位异或,得Lm’=1001
Lm’与Rm(最开始的那个Rm)组合得到输出 1001(Lm’) 1001(Rm)
至此完成第一次循环
然后交换高低位,作为第二次循环的输入,即1001(Rm) 1001(Lm’)作为输入
开始第二次循环
记左半为Ln=1001,右半为Rn=1001
对Rn做EP扩展置换,得Rn’=1100 0011
Rn’与子密钥K2按位异或,得Rn’=0011 1111
Rn’左半0011进入S0盒替代选择得10,右半1111进入S1盒替代选择的11,组合后得Rn’=1011
对Rn’做P4置换,得Rn’=0111
Rn’与Ln按位异或,得Ln’=1110
Ln’与Rn(最开始的那个Rn)组合得到输出 1111(Ln’) 1001(Rn)
至此完成第二次循环
最后进行逆初始置换对上面的输出m’=1111 1001做IPI置换得到密文m’=0111 0110

OK,到这里就完成了将明文加密为密文,S-DES加密结束.

下面开始解密,解密过程与加密基本一致,就是密钥使用顺序是相反的,第一次循环使用K2第二次循环使用K1
首先还是初始置换
对密文m=0111 0110做IP置换,得m’=1110 1001
Feistel密码结构
第一次循环
记左半(高位)为Lm=1110,右半(低位)为Rm=1001
对Rm做EP扩展置换,得Rm’=1100 0011
Rm’与子密钥K2按位异或,得Rm’=0011 1111
Rm’左半0011进入S0盒替代选择得10,右半1111进入S1盒替代选择的11,组合后得Rm’=1011
对Rm’做P4置换,得Rm’=0111
Rm’与Lm按位异或,得Lm’=1001
Lm’与Rm(最开始的那个Rm)组合得到输出 1001(Lm’) 1001(Rm)
至此完成第一次循环
然后交换高低位,作为第二次循环的输入,即1001(Rm) 1001(Lm’)作为输入
开始第二次循环
记左半为Ln=1001,右半为Rn=1001
对Rn做EP扩展置换,得Rn’=1100 0011
Rn’与子密钥K1按位异或,得Rn’=1001 1100
Rn’左半1001进入S0盒替代选择得11,右半1100进入S1盒替代选择的01,组合后得Rn’=1101
对Rn’做P4置换,得Rn’=1101
Rn’与Ln按位异或,得Ln’=0100
Ln’与Rn(最开始的那个Rn)组合得到输出0100(Ln’) 1001(Rn)
至此完成第二次循环
最后进行逆初始置换
对上面的输出m’=0100 1001做IPI置换得到明文m’=0001 0110

这样就完成的S-DES的解密

代码清单
#include <iostream>
#include <string>
using namespace std;

//some consts
static int P10MAX= 10;
static int P8MAX= 10;
static int P4MAX= 4;
static int IPMAX= 8;
static int IPIMAX= 8;
static int EPMAX= 4;

// two keys K1 and K2
int K1=0;
int K2=0;
/*permutation for 10-bit key*/
static int P10[]={3,5,2,7,4,10,1,9,8,6,'\0'};
/*permutation....*/
static int P8[]={6,3,7,4,8,5,10,9,'\0'};
static int P4[]={2,4,3,1,'\0'};
static int IP[]={2,6,3,1,4,8,5,7,'\0'};
static int IPI[]={4,1,3,5,7,2,8,6,'\0'};
static int EP[]={4,1,2,3,2,3,4,1,'\0'};
static int S0[4][4]={
{1,0,3,2},
{3,2,1,0},
{0,2,1,3},
{3,1,3,2},
};
static int S1[4][4]={
{0,1,2,3},
{2,0,1,3},
{3,0,1,0},
{2,1,0,3},
};

int Getlength(int p[])
{
int i=0;
for(;p[i]!='\0';++i);
return i;
}
int BinaryToDecimal(string binary){
int result=0;
for(int i=0;i<binary.length();i++){
result=2*result+(binary[i]-'0');
}
return result;
}
//print in binary so that we can see the result
void printBin(int x, int n)
{
int mask=1<<(n-1);
while(mask > 0){
((x&mask)==0)?printf("0"):printf("1");
mask >>=1;
}
cout<<endl;
}

//Permute function
int Permute(int inum,int p[],int pmax)
{
int result=0;
int length=Getlength(p);
for(int i=0;i<length;++i){
result<<=1;
result|=(inum>>(pmax-p[i]))&1;
}
return result;
}

//F function
int F(int R, int K)
{
int t=Permute(R,EP,EPMAX) ^ K;
int t0=(t>>4)& 0xf;
int t1=t& 0xf;
t0= S0[((t0 & 0x8)>>2) | (t0 & 1)] [(t0>>1)&0x3];
t1= S1[((t1 & 0x8)>>2) | (t1 & 1)] [(t1>>1)&0x3];
t= Permute( (t0<<2)|t1, P4,P4MAX);
return t;
}

//fk function
int fk(int m, int k){
int l=(m>>4) & 0xf;
int r=m & 0xf;
return ((l ^ F(r,k))<< 4)| r;
}

//switch function
int SW(int x){
return ((x & 0xf)<<4) | ((x>>4) & 0xf);
}

//encryption for 8-bit plaintext
int encrypt(int m){
m=Permute(m,IP,IPMAX);
m=fk(m,K1);
m=SW(m);
m=fk(m,K2);
m=Permute(m,IPI,IPIMAX);
return m;
}

//decryption for 8-bit ciphertext
int decrypt(int m){
m=Permute(m,IP,IPMAX);
m=fk(m,K2);
m=SW(m);
m=fk(m,K1);
m=Permute(m,IPI,IPIMAX);
return m;
}

//use Key as a parameter to get K1 and K2
void SDES(int K)
{
int t1=0,t2=0;
K=Permute(K,P10,P10MAX);
//get 5-bit
t1= (K >> 5) & 0x1f;
t2 = K & 0x1f;
//LS-1
t1=((t1&0xf)<<1) | ((t1 & 0x10) >> 4);
t2=((t2&0xf)<<1) | ((t2 & 0x10) >> 4);
K1=Permute(( t1 << 5)| t2,P8,P8MAX);
//LS-2
t1=((t1 & 0x07)<< 2) |((t1 & 0x18) >> 3);
t2=((t2 & 0x07)<< 2) |((t2 & 0x18) >> 3);
K2=Permute((t1<<5) | t2,P8,P8MAX);
}

//the test main function is following
int main()
{
string plaintext,key,ciphertext;
int st;
for(;;)
{
printf(" ************************\n");
printf(" *** 1 加密 ***\n");
printf(" *** 2 解密 ***\n");
printf(" *** 3 退出 ***\n");
printf(" ************************\n");
printf("请输入你的操作: ");
scanf("%d",&st);
if(st==1)
{
cout<<"请输入明文：";
cin>>plaintext;
cout<<"请输入密钥：";
cin>>key;
SDES(BinaryToDecimal(key));
cout<<"对于明文"<<plaintext<<"经SDES加密后，得到的密文为:";
printBin(encrypt(BinaryToDecimal(plaintext)),8);
cout<<"\n\n"<<endl;
}
else if(st==2)
{
cout<<"请输入密文：";
cin>>ciphertext;
cout<<"请输入密钥：";
cin>>key;
SDES(BinaryToDecimal(key));
cout<<"对于"<<ciphertext<<"经SDES解密后，得到的明文为:";
printBin(decrypt(BinaryToDecimal(ciphertext)),8);
cout<<"\n\n"<<endl;
}
else
exit(0);
}
}
结果显示如下：