分组密码原理简介，和DES算法介绍以及C语言源码实现
分组密码原理简介
分组密码是对称密码体制，分组密码的作用：
- 消息加密
- 消息认证和数据完整性保护。通过用于构造消息认证码(MAC)来实现
- 构造伪随机数生成器，用于产生性能良好的随机数
- 构造流密码
- 构成其它密码协议的基本模块，如密钥管理协议，身份认证协议等
分组密码（block cipher）：
分组密码是将明文消息经过二进制编码后的序列分成固定长度的组，用同一密钥和算法对每一组加密，输出也是固定长度的密文分组。加密函数E
记为)
。
记为：)
，其中
。
解密函数D
记为)
。
记为：)
，其中。
分组密码有什么要求呢？
1. 对于每个K，
一个代换，也就是一一映射的。
2. 加密函数)
和解密函数)
是容易计算的。
3. 从方程或中解出k是一个困难问题。
分组密码的基本设计原则：实现、安全。
安全性设计原则
- 混淆原则
混淆性：所设计的密码应使得明文、密文、密钥之间的依赖关系相当复杂，以至于这种依赖关系对密码分析者来说是无法利用的。密码分析者利用这种依赖关系的方法非常多，因此混淆性也是一个极为繁杂的概念。
- 扩散原则
扩散是指所设计的密码应使得
（1）密钥的每一个比特影响密文的每一个比特，以防止对密钥进行逐段破译；
（2）明文的每一个比特影响密文的每一个比特，以便最充分地隐蔽明文的统计特性。
这一准则强调微小输入改变能够导致输出的多位变化。
（2）明文的每一个比特影响密文的每一个比特，以便最充分地隐蔽明文的统计特性。
这一准则强调微小输入改变能够导致输出的多位变化。
实现性设计原则
- 软件实现的设计原则
软件实现时，要使用子块和简单的运算。要求子块的数据长度能自然地适应软件编程，比如8、16或32比特的模加、移位或异或等运算；尽量避免按比特操作。
- 硬件实现的设计原则
硬件实现时，应该保证加密和解密的相似性，即加密和解密的过程中只是在密钥的使用方式上存在不同，以便用同样的器件即可以完成加密也可以完成解密。
分组密码的设计
两种方法：直接构造密码学性质强的复杂函数，或者构造密码学性质相对较弱的简单函数，并且基于简单函数进行多次迭代。——迭代型分组密码。
前者的构造和实现通常是困难的，因此，在实际中通常采用后者。
迭代分组密码
每次迭代称为一轮，相应的函数F称作轮函数。
每一轮输入都是前一轮输出的函数。
其中
是第
轮的子密钥，由秘密密钥K作为种子密钥通过密钥扩展算法生成。
轮函数F
S盒：非线性部件， 规模较小，局部混淆
- 非线性关系：实现混淆。
- 规模：较小。例如：说8进8出。128比特需要分成16组，分别用16个S盒来处理。
- 局部：多个S盒之间没有关联，混淆是在各个S盒之内进行，是局部的。
置换P：线性部件，整体扩散。
DES算法介绍
数据加密标准（DES）的加密/解密流程
DES是数据加密标准（Data Encryption Standard）的缩写，DES算法是第一个公开的分组密码算法。
算法征集及标准化：1972年美国商业部所属的美国国家标准局NBS (National Bureau of Standards)开始实施计算机数据保护标准的开发计划。1973年，NBS公开征集计算机数据加密算法，用于保护政府机构和商业部门非机密的敏感数据。1977年，NBS 采纳了IBM的Lucifer 算法的修正版作为数据加密标准DES。
算法征集及标准化：1972年美国商业部所属的美国国家标准局NBS (National Bureau of Standards)开始实施计算机数据保护标准的开发计划。1973年，NBS公开征集计算机数据加密算法，用于保护政府机构和商业部门非机密的敏感数据。1977年，NBS 采纳了IBM的Lucifer 算法的修正版作为数据加密标准DES。
基本参数
分组长度：64比特，密钥长度：64比特，有效密钥长度：56比特。加密
DES加密过程中包含的基本操作：
- 初始置换：初始置换（Initial Permutation，简称置换）在第一轮运算之前执行。
（1）58表示：结果中位于第1个位置的值，等于原文中第58个位置的值；
（2）图中的一格代表1bit，共有64bit，即8字节。
即：%5D%3DM)
。
解密
DES算法的第i (i=1,2, … ,15)轮加密结构图：
单轮变换的数学描述：
缺点：
- 扩散速度慢：轮变换的输入有一半没有改变；
- 左右块的处理不能并行实施。
优点：
- 设计容易：轮函数F不要求可逆。
数据加密标准（DES）轮函数F
DES算法的第i (i=1,2, … ,15)轮加密结构图：
单轮变换的数学描述：
缺点：
- 扩散速度慢：轮变换的输入有一半没有改变；
- 左右块的处理不能并行实施。
- 设计容易：轮函数F不要求可逆。
轮函数F：扩展置换E、轮密钥加、S盒、置换P。
扩展置换E
将64位输入序列的右半部分从32位扩展到48位。
S—盒的输出表示：
设对应S-盒1的输入序列为：101111
行号：11即3，列号：0111即7。
结果为7即0111。
S盒的设计准则
迄今为止，有关方面未曾完全公开有关DES的S盒的设计准则。1976年，NSA披露过下述准则：
1：S盒的输出都不是其输入的线性或仿射函数。
1：S盒的输出都不是其输入的线性或仿射函数。
2：改变S盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。
3：当S盒的任一输入位保持不变，其它5位输入变化时（共有25 =32种情况），输出数字中的0和1的总数近于相等。
这三点使DES的S盒能够实现较好的混淆。
这三点使DES的S盒能够实现较好的混淆。
置换P
P盒置换是对32比特数据进行比特置换。
置换P的输入/输出关系可以用表来表示，变换规则和前面介绍的初始置换相同。
作用：置换P 与S 盒互相配合，起到了扩散作用，共同确保DES的安全。
P盒的设计特点：
P盒的设计特点：
（1）P盒的各输入组的4个比特都分配到不同的输出组之中；
比如：输入第一组1，2，3，4比特在输出中分别位于第3，5，6，8组。
（2）P盒的各输出组的4个比特都来自不同的输入组。
比如：输出第一组的四个比特分别来自输入的第4组，第2组，第5组，第6组。
比如：输入第一组1，2，3，4比特在输出中分别位于第3，5，6，8组。
（2）P盒的各输出组的4个比特都来自不同的输入组。
比如：输出第一组的四个比特分别来自输入的第4组，第2组，第5组，第6组。
数据加密标准（DES）密钥扩展方案、解密流程
DES解密：加密和解密可使用相同的算法，即解密过程是将密文作为输入序列进行相应的DES加密，与加密过程惟一不同之处是解密过程使用的轮密钥与加密过程使用的次序相反。
DES的C语言源码实现
头文件：
#ifndef __DES_H__
#define __DES_H__
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
#include <stdint.h>
#define DES_BLOCK_LEN 8 // 8bytes
#define DES_KEY_LEN_8 8 // key-length: 8bytes -> single DES
#define DES_KEY_LEN_16 16 // key-length: 16bytes -> triple DES (key1=key[0], key2=key[8], key3=key[0])
#define DES_KEY_LEN_24 24 // key-length: 24bytes -> triple DES (key1=key[0], key2=key[8], key3=key[16])
typedef enum _des_mode_e {
DES_MODE_ECB,
DES_MODE_CBC
} des_mode_e;
int32_t crypto_des_encrypt(const uint8_t *data, uint32_t data_len, uint8_t *out, const uint8_t *iv,
const uint8_t *key, uint32_t key_len, des_mode_e mode);
int32_t crypto_des_decrypt(const uint8_t *data, uint32_t data_len, uint8_t *out, const uint8_t *iv,
const uint8_t *key, uint32_t key_len, des_mode_e mode);
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /*__DES_H__*/
#include <stdio.h>
#include <string.h>
#include "des.h"
#define DES_TRUE 0x01
#define DES_FALSE 0x00
#define DES_DO_INITIAL_PERMUTATION 0x10
#define DES_ENCRYPTION_MODE 0x20
#define DES_DECRYPTION_MODE 0
#define DES_DO_FINAL_PERMUTATION 0x40
#define DES_ENCRYPT_BLOCK (DES_DO_INITIAL_PERMUTATION|DES_ENCRYPTION_MODE|DES_DO_FINAL_PERMUTATION)
#define DES_DECRYPT_BLOCK (DES_DO_INITIAL_PERMUTATION|DES_DECRYPTION_MODE|DES_DO_FINAL_PERMUTATION)
const uint8_t IPP[64] = {
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,
56, 48, 40, 32, 24, 16, 8, 0, 58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6
};
const uint8_t IPN[64] = {
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, 32, 0, 40, 8, 48, 16, 56, 24
}; //Inverse permutation
const uint8_t Choose56[56] = {
56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 9, 1,
58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 62, 54, 46, 38,
30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36,
28, 20, 12, 4, 27, 19, 11, 3
}; //Choosing the 56bit key from 64bit
const uint8_t key_round[32] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1,
0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
}; //shift key left //shift key right
const uint8_t Choose48[48] = {
31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10,
11, 12, 11, 12, 13, 14, 15, 16, 15, 16, 17, 18, 19, 20, 19, 20,
21, 22, 23, 24, 23, 24, 25, 26, 27, 28, 27, 28, 29, 30, 31, 0
}; //expands the right half text of 32 bits to 48 bits
const uint8_t E[48] = {
13, 16, 10, 23, 0, 4, 2, 27, 14, 5, 20, 9, 22, 18, 11, 3,
25, 7, 15, 6, 26, 19, 12, 1, 40, 51, 30, 36, 46, 54, 29, 39,
50, 44, 32, 47, 43, 48, 38, 55, 33, 52, 45, 41, 49, 35, 28, 31
}; //Compression and permutation for key
const uint8_t PP[32] = {
15, 6, 19, 20, 28, 11, 27, 16, 0 , 14, 22, 25, 4, 17, 30, 9,
1, 7, 23, 13, 31, 26, 2, 8, 18, 12, 29, 5, 21, 10, 3, 24
}; //P-box permutation
const uint8_t S[8][64] = {{
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
},
{
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
},
{
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
},
{
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
},
{
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
},
{
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
},
{
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
},
{
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 uint8_t _bitposition[8] = {
0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
};
static void check_table(uint8_t line, uint8_t *text, uint8_t *lasttext, const uint8_t *IDD)
{
uint8_t i, j, k, temp, temp2;
for (j = 0, k = 0; j < line; j++, k += 8) {
lasttext[j] = 0;
for (i = 0; i < 8; i++) {
temp2 = IDD[k + i];
temp = text[temp2 / 8]; // get the byte
temp &= _bitposition[temp2 & 0x7]; // get the bit
if (temp) {
lasttext[j] |= _bitposition[i];
}
}
}
}
static void single_des_operation(uint8_t *plaintext, uint8_t *key, uint8_t mode)
{
static uint8_t prevtext[8];
uint8_t prevkey[8], Ltext[4], Rtext[4];
char temp, temp1;
int32_t i = 0;
int32_t Round = 0;
uint8_t j = 0;
if (mode & DES_DO_INITIAL_PERMUTATION) {
check_table(8, plaintext, prevtext, IPP); //Initial permutation
}
for (i = 0; i < 4; i++) {
Ltext[i] = prevtext[i];
Rtext[i] = prevtext[i + 4];
}
check_table(7, key, prevkey, Choose56);
for (Round = 0; Round < 16; Round++) {
//rotate both 28bits block to left(encrypt) or right(decrypt)
if (mode & DES_ENCRYPTION_MODE) { // encrypt
for (j = 0; j < key_round[Round]; j++) {
temp = prevkey[3] & 0x08;
for (i = 7; i > 0; i--) {
temp1 = prevkey[i - 1] & 0x80;
prevkey[i - 1] <<= 1;
if (temp) {
prevkey[i - 1] |= 0x01;
}
temp = temp1;
}
if (temp) {
prevkey[3] |= 0x10;
} else {
prevkey[3] &= 0xEF;
}
}
} else { // decrypt
for (j = 0; j < key_round[Round + 16]; j++) {
temp = prevkey[3] & 0x10;
for (i = 0; i < 7; i++) {
temp1 = prevkey[i] & 0x01;
prevkey[i] >>= 1;
if (temp) {
prevkey[i] |= 0x80;
}
temp = temp1;
}
if (temp) {
prevkey[3] |= 0x08;
} else {
prevkey[3] &= 0xF7;
}
}
}
check_table(6, prevkey, plaintext, E); //Compression permutation
check_table(6, Rtext, prevtext, Choose48); //Expansion permutation
//Expanded right half xor_operation with the subkey
prevtext[0] ^= plaintext[0];
prevtext[1] ^= plaintext[1];
prevtext[2] ^= plaintext[2];
prevtext[3] ^= plaintext[3];
prevtext[4] ^= plaintext[4];
prevtext[5] ^= plaintext[5];
for (j = 6, i = 8; j > 0; j -= 3, i -= 4) { //S-Box Substitution
plaintext[i - 1] = prevtext[j - 1];
plaintext[i - 2] = ((prevtext[j - 1] >> 6) & 0x03) | (prevtext[j - 2] << 2);
plaintext[i - 3] = ((prevtext[j - 2] >> 4) & 0x0f) | (prevtext[j - 3] << 4);
plaintext[i - 4] = prevtext[j - 3] >> 2;
}
for (i = 0; i < 8; i++) { //Get the S-Box location
temp = plaintext[i] & 0x21;
if (temp & 0x01) {
temp = (temp & 0x20) | 0x10;
}
plaintext[i] = temp | ((plaintext[i] >> 1) & 0x0F);
}
//Get S-Box output
plaintext[0] = S[0][plaintext[0]];
plaintext[1] = S[1][plaintext[1]];
plaintext[2] = S[2][plaintext[2]];
plaintext[3] = S[3][plaintext[3]];
plaintext[4] = S[4][plaintext[4]];
plaintext[5] = S[5][plaintext[5]];
plaintext[6] = S[6][plaintext[6]];
plaintext[7] = S[7][plaintext[7]];
//Combine 4-bit block to form 32-bit block
plaintext[0] = (plaintext[0] << 4) | plaintext[1];
plaintext[1] = (plaintext[2] << 4) | plaintext[3];
plaintext[2] = (plaintext[4] << 4) | plaintext[5];
plaintext[3] = (plaintext[6] << 4) | plaintext[7];
check_table(4, plaintext, prevtext, PP);
for (i = 0; i < 4; i++) {
prevtext[i] ^= Ltext[i];
Ltext[i] = Rtext[i];
Rtext[i] = prevtext[i];
}
}
for (i = 0; i < 4; i++) {
prevtext[i] = Rtext[i];
prevtext[i + 4] = Ltext[i];
}
if (mode & DES_DO_FINAL_PERMUTATION) {
check_table(8, prevtext, plaintext, IPN); //Final permutation
}
}
static int32_t xor_operation(uint8_t *out, const uint8_t *data1, const uint8_t *data2, uint32_t dwLen)
{
int32_t ret = DES_TRUE;
uint32_t i = 0;
if ((dwLen != 0) && ((data1 == NULL) || (data2 == NULL) || (out == NULL))) {
ret = DES_FALSE;
} else {
for (i = 0; i < dwLen; i++) {
out[i] = data1[i] ^ data2[i];
}
}
return ret;
}
int32_t crypto_des_encrypt(const uint8_t *data, uint32_t data_len, uint8_t *out, const uint8_t *iv,
const uint8_t *key, uint32_t key_len, des_mode_e mode)
{
uint32_t i = 0;
if ((data_len % DES_BLOCK_LEN != 0) || \
((key_len != DES_KEY_LEN_8) && \
(key_len != DES_KEY_LEN_16) && \
(key_len != DES_KEY_LEN_24))) {
return -1;
}
for (i = 0; i < data_len / DES_BLOCK_LEN; i++) {
if (mode == DES_MODE_CBC) {
if (i > 0) {
xor_operation(&out[i * DES_BLOCK_LEN], &data[i * DES_BLOCK_LEN], \
&out[(i - 1) * DES_BLOCK_LEN], DES_BLOCK_LEN);
} else {
xor_operation(&out[i], &data[i], iv, DES_BLOCK_LEN);
}
} else {
memcpy(&out[i * DES_BLOCK_LEN], &data[i * DES_BLOCK_LEN], DES_BLOCK_LEN);
}
if (key_len == DES_KEY_LEN_8) { //Single DES
single_des_operation(&out[i * DES_BLOCK_LEN], (uint8_t *)&key[0], DES_ENCRYPT_BLOCK);
} else { //Trip DES
uint8_t *key1 = (uint8_t *)&key[0];
uint8_t *key2 = (uint8_t *)&key[DES_KEY_LEN_8];
uint8_t *key3 = (uint8_t *)&key[0];
if (key_len == DES_KEY_LEN_24) {
key3 = (uint8_t *)&key[DES_KEY_LEN_16];
}
single_des_operation(&out[i * DES_BLOCK_LEN], key1, DES_ENCRYPT_BLOCK);
single_des_operation(&out[i * DES_BLOCK_LEN], key2, DES_DECRYPT_BLOCK);
single_des_operation(&out[i * DES_BLOCK_LEN], key3, DES_ENCRYPT_BLOCK);
}
}
return 0;
}
int32_t crypto_des_decrypt(const uint8_t *data, uint32_t data_len, uint8_t *out, const uint8_t *iv,
const uint8_t *key, uint32_t key_len, des_mode_e mode)
{
int32_t i = 0;
if ((data_len % DES_BLOCK_LEN != 0) || \
((key_len != DES_KEY_LEN_8) && \
(key_len != DES_KEY_LEN_16) && \
(key_len != DES_KEY_LEN_24))) {
return -1;
}
for (i = data_len / DES_BLOCK_LEN - 1; i >= 0; i--) {
memcpy(&out[i * DES_BLOCK_LEN], &data[i * DES_BLOCK_LEN], DES_BLOCK_LEN);
if (key_len == DES_KEY_LEN_8) { //Single DES
single_des_operation(&out[i * DES_BLOCK_LEN], (uint8_t *)&key[0], DES_DECRYPT_BLOCK);
} else { //Trip DES
uint8_t *key1 = (uint8_t *)&key[0];
uint8_t *key2 = (uint8_t *)&key[DES_KEY_LEN_8];
uint8_t *key3 = (uint8_t *)&key[0];
if (key_len == DES_KEY_LEN_24) {
key3 = (uint8_t *)&key[DES_KEY_LEN_16];
}
single_des_operation(&out[i * DES_BLOCK_LEN], key3, DES_DECRYPT_BLOCK);
single_des_operation(&out[i * DES_BLOCK_LEN], key2, DES_ENCRYPT_BLOCK);
single_des_operation(&out[i * DES_BLOCK_LEN], key1, DES_DECRYPT_BLOCK);
}
if (mode == DES_MODE_CBC) {
if (i > 0) {
xor_operation(&out[i * DES_BLOCK_LEN], &out[i * DES_BLOCK_LEN], \
&data[(i - 1) * DES_BLOCK_LEN], DES_BLOCK_LEN);
} else {
xor_operation(&out[i], &out[i], iv, DES_BLOCK_LEN);
}
}
}
return 0;
}
投递金山WPS等公司10个岗位 >
美团公司福利 1340人发布