现代对称密码之S-DES算法Cpp源码
对称密码是指加密密钥与解密密钥相同或能推算的加密算法,其特点是解密密钥能够从加密密钥中推算出来,加密密钥也能够从解密密钥中推算出来。在大多数对称算法中,加密密钥和解密密钥是相同的,此时,这种算法也被称为单密钥算法。对称算法的安全性依赖于密钥,密钥泄露意味着任何人都可以对它们发送或接收的消息进行解密。对称加密算法的优点在于加解密的高速度和在使用长密钥时的难破解性,但密钥的生成和分发是使用对称密码算法的最大问题。
目前在国际上使用的对称密码算法主要有:DES算法、三重DES算法、CAST-128算法、Blowfish算法、RC5算法、IDEA算法等。
目前在国际上使用的对称密码算法主要有:DES算法、三重DES算法、CAST-128算法、Blowfish算法、RC5算法、IDEA算法等。
S-DES算法又称为简化的DES算法,是美国圣达拉卡大学的爱德华·施菲尔教授提出的用于教学的一个算法,其结构和性质与DES算法相似。学习S-DES算法有助于加深理解DES算法。
S-DES算法原理
S-DES整体结构见下图。S-DES加密算法的输入是一个8 位的明文组(例如10111101)和一个10位的密钥,输出为8位的密文组。
S-DES解密算法的输入是一个8位的密文组和一个10位的密钥,输出为8位的明文组。
S-DES的加密算法包括5步:
- 通过函数进行初始置换;
- 通过复杂函数进行置换和代换运算(这部分运算依赖于输入的密钥);
- 通过函数进行两部分的简单置换;
- 再次通过函数进行置换和代换;
- 通过置换函数的逆函数进行置换。
S-DES算法通过多层置换和代换操作来增加密码分析的难度。
S-DES的加密过程可以简单地表示为。
也可以写为:。
解密过程是加密过程的逆过程,可以表示为:。
也可以写为:。
解密过程是加密过程的逆过程,可以表示为:。
S-DES密钥的生成
在S-DES的加密和解密过程中分别使用了两次运算,运算过程中分别使用了不同的两个密钥,和。和的生成的基本过程可以表示为:
将10位的密钥表示成,那么P10置换定义为:
,
。
密钥生成的基本过程如下图所示:
或可以按下面形式定义为:
即第1个位置输出的是第3位,第2个位置输出的是第5位,以此类推。例如,初始的密钥为(10100 00010),经过置换后变成了(10000 01100),接下来分别对前面5位和后面5位循环左移(LS-1)1位,密钥变为(00001 11000)。然后按下面的P8置换规则计算子密钥,得到。
在对密钥进行循环左移1位后,得(00001 11000),再循环左移2位,那么,密钥(00001 11000)就转换为(00100 00011),再进行P8置换,得到另一个子密钥。
。
生成过程为:
。
例:假设10位S-DES密钥为1100011110,试计算子密钥和。
生成过程为:
Bit# | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
K | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
P10(K) | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
Shift(P10(K)) | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
P8(Shift(P10(K))) | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
|
|
生成过程为:
Bit# | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
K | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
P10(K) | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
Shift(P10(K)) | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
P8(Shift(P10(K))) |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
|
|
S-DES加密与解密过程
S-DES的加密过程可以简单表示为:
。
在加密过程中,两次进行置换操作,两次进行运算,一次进行交换,其中核心部分是两次运算。
S-DES的加密过程如下图所示:
S-DES算法的第1步是对输入的8位明文使用IP函数进行置换,其置换方法为:
这个置换过程保留了所有8位明文的特性,但进行了混淆。最后的置换使用了函数进行置换,其置换方法为:
第2个置换是第1个置换的逆,即两个置换的关系为。
函数是S-DES算法中最为复杂的部分,它是由置换函数和代换函数组合而成。函数可以表达为:设L和R分别是的8位输人的左边4位和右边4位,F是一个4位串到4位串的映射(不一定是一对一映射)。那么设,其中是子密钥,是按位异或。
函数的计算过程中,F函数最为复杂,F函数的执行过程如下:
(1)F函数中的R是明文经过IP置换后得到的输出的右半部分,F函数首先执行对R的E/P扩展置换,将4位R扩展置换成8位,其扩展置换的方法为
(2)将E/P扩展置换得到的结果与密钥进行XOR运算。
(3)根据S盒对第2步获得的数据分为左、右两部分进行替换。S盒的定义为
假设从第2步中获得的结果为:,盒与左边4位进行运算,盒与右边4位进行运算。运算方法为:第1位和第4位决定的行,第2位和第3位决定S盒的列。例如:有, ,那么,输出的是盒的第0行第2列,结果为3,写成二进制则为11。同理,可以通过、与盒产生另一个2位的二进制输出,将两者结合得到4位的二进制输出。
(1)F函数中的R是明文经过IP置换后得到的输出的右半部分,F函数首先执行对R的E/P扩展置换,将4位R扩展置换成8位,其扩展置换的方法为
(3)根据S盒对第2步获得的数据分为左、右两部分进行替换。S盒的定义为
(4)将S盒的输出进行P4置换,P4置换的方法为
函数的输出就是F函数的输出。
例1
例1 假设明文为0010 1000,密钥,试计算。
(1)首先进行IP置换,置换过程为:
得到:
(2)
(3)
(4)完整计算过程如下:
(5)运行函数F后得到的结果为0001。
(6)计算。
在执行完函数之后执行SW交换函数,SW交换函数的功能是交换输人的左半部分与右半部分,这样函数就作用在不同的部分了。在的执行过程中,、、和都是相同的,但输入的密钥为.
例2
例2 根据前两个例子得到的计算结果,计算加密后的明文。
(1) 在上上例,计算得到。在上例中计算得到的,因此有: L=0011,R=0010,进行sw交换后有:L= 0010,R= 0011。
(2) 计算。
(3) 计算F函数,F函数计算过程如下:
(2) 计算。
(3) 计算F函数,F函数计算过程如下:
(4)此时我们得到F为(0011)。
(5)计算。
(6)最后计算置换,计算过程为
(7)最终加密结果为: 1000 1010。
S-DES算法的解密过程如下:
。
具体实现方法的各个步骤与加密方法的具体实现完全一样。
(5)计算。
(6)最后计算置换,计算过程为
S-DES算法的解密过程如下:
。
具体实现方法的各个步骤与加密方法的具体实现完全一样。
Feistel密码结构
在对数据加密的方法中比较典型的加密方法有两种,一种是流加密方法,该方法在加密过程中每次仅加密一位或一个字节,Vigenere加密方法是典型的流加密方法。另种加密方法是分组加密方法,这种方法在加密时将明文组作为整体进行加密,得到的密文通常是与之等长的密文组。
现在使用的几乎所有的对称分组加密算法都是基于Feistel 分组密码结构的,因此,在进一步研究对称密码之前,了解Feistel密码结构是十分必要的。
Feistel密码是以德国出生的、在IBM工作的物理学家及密码学家Horst Feistel命名的加密方法,属于分组对称密码结构。这种加密结构广泛应用于分组加密,包括数据加密标准(DES)算法。Feistel结构的加密和解密过程非常相似,有时候除了密钥顺序有变化外,其他过程都一样。
现在使用的几乎所有的对称分组加密算法都是基于Feistel 分组密码结构的,因此,在进一步研究对称密码之前,了解Feistel密码结构是十分必要的。
Feistel密码是以德国出生的、在IBM工作的物理学家及密码学家Horst Feistel命名的加密方法,属于分组对称密码结构。这种加密结构广泛应用于分组加密,包括数据加密标准(DES)算法。Feistel结构的加密和解密过程非常相似,有时候除了密钥顺序有变化外,其他过程都一样。
Feistel密码结构的加密和解密的基本结构如下图所示。在下图中,F为轮函数(或圈函数),为与轮数相对应的子密钥。Feistel密码结构的基本操作过程如下:
(1)将输入的明文分割成相同大小的两部分。
(2)对的每一 轮计算:
;
(2)对的每一 轮计算:
;
。
(3)最后获得密文。
解密密文,是计算,每一轮的计算方法为
;
;
最后获得的就是解密得到的明文。
大多数采用Feistel结构的密码算法都是采用对称的方法,即左半部分和右半部分的大小相同,但也有少数加密算法采用了非对称的密码算法,Skipjack加密算法就是一种非对称的加密算法。
(3)最后获得密文。
解密密文,是计算,每一轮的计算方法为
;
;
最后获得的就是解密得到的明文。
大多数采用Feistel结构的密码算法都是采用对称的方法,即左半部分和右半部分的大小相同,但也有少数加密算法采用了非对称的密码算法,Skipjack加密算法就是一种非对称的加密算法。
S-DES算法实现
SDES.h的代码如下:
#ifndef SDES_H #define SDES_H #include <iostream> using namespace std; class SDES{ public: SDES(); void setKey(string s); //设置密钥 void setPlainText(string s); //设置明文 void fk(int key,int &left,int right); //fx运算 void getKey(); //获得密钥key1和key2 void encryption(); //加密过程 void decryption(); //解密过程 int permutations(int num,const int p[],int pmax,int n); //进行置换操作 int shiftLS(int num); //循环左移(左右各半分别左移1位) void showResultEnc(); //显示加密结果 void showResultDec(); //显式解密结果 private: int key; //初始密钥 int key1; //密钥K1 int key2; //密钥K2 int stringToInt(string s); //将输入的字符串(0、1)转换为整型数据 int plainText; //明文 int cipherText; //密文 int decipherText; //解密后的明文20名 //以下为常量 static const int P10[10]; //P10置换常量 static const int P8[8]; //P8置换常量 static const int IP[8]; //IP置换常量 static const int IPI[8]; //IP-1置换常量 static const int EP1[4]; //E/P1置换常量 static const int EP2[4]; //E/P2置换常量 static const int P4[4]; //P4墅换常址 static const int S0[4][4]; //S0盒 static const int S1[4][4]; //S1盒 }; #endifSDES.cpp的代码如下:
#include "SDES.h" const int SDES::P10[10]= {3,5,2,7,4,10,1,9,8,6}; const int SDES::P8[8]={6,3,7,4,8,5,10,9}; const int SDES::IP[8]={2,6,3,1,4,8,5,7}; const int SDES::IPI[8]={4,1,3,5,7,2,8,6}; const int SDES::EP1[4]={4,1,2,3}; const int SDES::EP2[4]={2,3,4,1}; const int SDES::P4[4]={2,4,3,1}; const int SDES::S0[4][4]={{1,0,3,2},{3,2,1,0},{10,2,1,3},{13,1,3,2}}; const int SDES::S1[4][4]={{0,1,2,3}, {2,0,1,3},{3,0,1,0},{2,1,0,3}}; SDES::SDES(){ } void SDES::setKey(string s){ key=stringToInt(s); } int SDES::stringToInt(string s){ int key=0; //整型表示的密钥 int i; int n=s.length();//n为字符串的长度 for(i=0;i<n;i++){ key=key*2+s[i]-'0'; } return key; } void SDES::getKey(){ int tempKey; tempKey=permutations(key,P10,10,10); tempKey=shiftLS(tempKey); key1=permutations(tempKey,P8,10,8); tempKey=shiftLS(tempKey); tempKey=shiftLS(tempKey); key2=permutations (tempKey,P8,10,8); } int SDES::permutations(int num,const int p[], int pmax, int n){ int temp=0; int i; for(i=0;i<n;i++){ temp<<= 1; //temp左移一位 temp|=(num>>(pmax-p[i]))&1; } return temp; } int SDES::shiftLS(int num){ int temp; int L,R; //左右各半数据 L=(num>>5) & 0x1F; R=num & 0x1F; L=((L&0xF)<<1) | ((L&0x10)>>4); R=((R&0xF)<<1) | ((R&0x10)>>4) ; temp=(L<<5) | R; return temp; } void SDES::encryption(){ cipherText= permutations(plainText,IP,8,8) ; int R,L; //置换后密文分成左、右两半 R=cipherText&0xF; L=((cipherText&0xF0)>>4) ; fk(key1,L,R); int temp=L; L=R; R=temp; fk(key2,L,R); temp=(L<<4) | R; cipherText=permutations(temp,IPI,8,8); } void SDES::fk(int key,int &left,int right){ int L=left; int R=right; int temp; int tempL, tempR; temp=((permutations (R,EP1,4,4))<<4) | (permutations(R,EP2,4,4)); temp=temp^key; tempR=temp&0xF; tempL=((temp&0xF0)>>4); tempL=S0[((tempL&0x8)>>2)|(tempL&1)][(tempL>>1)&0x3]; tempR=S1[((tempR&0x8)>>2)|(tempR&1)][(tempR>>1)&0x3]; temp=(tempL<<2)|tempR; temp=permutations(temp,P4,4,4); left=L^temp; } void SDES::decryption(){ decipherText=permutations(cipherText,IP,8,8); int R,L; //置换后密文分成左右两半 R=decipherText&0xF; L=((decipherText&0xF0)>>4); fk(key2,L,R); int temp=L; L=R; R=temp; fk(key1,L,R) ; temp=(L<<4)|R; decipherText=permutations(temp,IPI,8,8); } void SDES::showResultEnc(){ cout<<cipherText<<endl; } void SDES::showResultDec(){ cout<<decipherText<<endl; } void SDES::setPlainText(string s){ int res = stringToInt(s); plainText = res; }main.cpp的源代码如下:
#include <iostream> #include "SDES.h" /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int main(int argc, char** argv) { SDES* sdes = new SDES(); sdes->setKey("123456789"); sdes->setPlainText("12"); sdes->encryption(); sdes->showResultEnc(); sdes->decryption(); sdes->showResultDec(); return 0; }