加密模型

输入输出

算法流程

密钥生成流程

已知10位的种子密钥k=(k0,k1,...,k9)k=(k_0,k_1,...,k_9)

  1. 执行P10P10置换变换得到m1=P10(k)m_1=P10(k)

  2. 5位一组分割成两组,每组内循环左移s位记作变换SLsSL_s,对m1m_1进行5位一组分割的循环左移1位变换,得m2=SL1(m1)m_2=SL_1(m_1)

  3. 执行10位变8位的P8置换变换得到k1=P8(m2)k_1=P8(m_2)

  4. m2m_2进行5位一组分割的循环左移2位变换,得m3=SL2(m2)m_3=SL_2(m_2)

  5. 执行10位变8位的P8置换变换得到k2=P8(m3)k_2=P8(m_3)

加密流程

先来看加密算法,已知明文pp

  1. pp执行初始变换IPIP得到IP(p)IP(p)

  2. IP(p)IP(p)执行依赖密钥k1k_1的变换Fk1F_{k_1}得到Fk1(IP(p))F_{k_1}(IP(p))

  3. Fk1(IP(p))F_{k_1}(IP(p))四位一组划分两组,交换两组位置,即变换SWSW,得到SW(Fk1(IP(p)))SW(F_{k_1}(IP(p)))

  4. SW(Fk1(IP(p)))SW(F_{k_1}(IP(p)))执行依赖密钥k2k_2的变换Fk2F_{k_2}得到Fk2(SW(Fk1(IP(p))))F_{k_2}(SW(F_{k_1}(IP(p))))

  5. Fk2(SW(Fk1(IP(p))))F_{k_2}(SW(F_{k_1}(IP(p))))执行IPIP逆变换IP1{IP}^{-1}得到最终密文c=IP1(Fk2(SW(Fk1(IP(p)))))c={IP}^{-1}(F_{k_2}(SW(F_{k_1}(IP(p)))))

解密流程

再看解密算法,解密算法实际上仅仅只是将上述加密流程中的k1,k2k_1,k_2的位置互换即可完成解密

加解密公式

加密公式:c=IP1(Fk2(SW(Fk1(IP(p)))))c={IP}^{-1}(F_{k_2}(SW(F_{k_1}(IP(p)))))

解密公式:p=IP1(Fk1(SW(Fk2(IP(c)))))p={IP}^{-1}(F_{k_1}(SW(F_{k_2}(IP(c)))))

Fk变换流程

FkF_k变换的输入为8位二进制数的左右两半L,R和8位子密钥kk

  1. 取右半四位二进制RR,经过扩展变换E/PE/P得到8位二进制数E/P(R)E/P(R)

  2. 与8位子密钥kk异或得到8位二进制数E/P(R)kE/P(R) \oplus k

  3. E/P(R)kE/P(R) \oplus k的左右四位二进制分别记作L1, R1

  4. L1,R1L1, R1分别经过S0,S1S0,S1变换后得到二位二进制数L2,R2L2,R2

  5. L2,R2L2, R2经过P4P4变换得到P4(L2,R2)P4(L2, R2)

  6. 记输出结果为L3,R3L3, R3,则R3=R,L3=LP4(L2,R2)R3=R, L3=L \oplus P4(L2, R2)

代码实现

使用c++实现S-DES加密算法

数据结构

代码中涉及大量二进制位操作,使用c++标准库的bitset作为存储结构

注意bitset的打印输出低位在右侧,而书面解释时,一般低位在左侧。

子密钥生成

P10变换

代码较为简单,仅仅只是查表,填充,即仅二进制位置发生变换,不改变二进制中的位(原来分别有多少0,1现在还是有多少)

1
2
3
4
5
6
bitset<10> P10(bitset<10> in) {
const int table[] = {3, 5, 2, 7, 4, 10, 1, 9, 8, 6};
bitset<10> out;
for (int i = 0; i < 10; i++) out[i] = in[table[i] - 1];
return out;
}

P8变换

同P10变换的原理

1
2
3
4
5
6
bitset<8> P8(bitset<10> in) {
const int table[] = {6, 3, 7, 4, 8, 5, 10, 9};
bitset<8> out;
for (int i = 0; i < 8; i++) out[i] = in[table[i] - 1];
return out;
}

循环移位

bitset循环左移

1
2
3
4
5
6
/// 循环左移size位
template <size_t N>
bitset<N> rol(bitset<N> src, int size) {
size = (size + N) % N;
return src << size | src >> (N - size);
}

分组移位变换

5位一组分割成两组,每组内循环左移s位记作变换SLsSL_s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bitset<10> SL(bitset<10> in, int s) {
// 5位一组分组
bitset<5> left, right;
for(int i=0;i<5;i++) left[i] = in[i];
for(int i=0;i<5;i++) right[i] = in[i+5];

// 循环左移(实际上计算机上是循环右移)
left = rol<5>(left, -s);
right = rol<5>(right, -s);

// 分组合并
bitset<10> out;
for(int i=0;i<5;i++) out[i] = left[i];
for(int i=0;i<5;i++) out[i+5] = right[i];

return out;
}

求解子密钥k1,k2

1
2
3
4
5
6
7
8
9
10
/// 计算子密钥k1,k2
void subkey(bitset<10> in, bitset<8>& out_k1, bitset<8>& out_k2) {
bitset<10> m1 = P10(in);

bitset<10> m2 = SL(m1,1);
out_k1 = P8(m2);

bitset<10> m3 = SL(m2,2);
out_k2 = P8(m3);
}

加解密流程

IP置换

1
2
3
4
5
6
bitset<8> IP(bitset<8> in) {
const int table[] = {2, 6, 3, 1, 4, 8, 5, 7};
bitset<8> out;
for (int i = 0; i < 8; i++) out[i] = in[table[i] - 1];
return out;
}

IP逆置换

1
2
3
4
5
6
bitset<8> IP_rev(bitset<8> in) {
const int table[] = {4, 1, 3, 5, 7, 2, 8, 6};
bitset<8> out;
for (int i = 0; i < 8; i++) out[i] = in[table[i] - 1];
return out;
}

Fk变换

E/P扩展变换

输入4位输出8位的E/P扩展置换变换

1
2
3
4
5
6
7
bitset<8> E_P(bitset<4> in) {
const int table[] = {4, 1, 2, 3, 2, 3, 4, 1};
bitset<8> out;
for (int i = 0; i < 8; i++)
out[i] = in[table[i] - 1];
return out;
}

S盒变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bitset<2> S0(bitset<4> in) {
const int table[4][4] = {
{1, 0, 3, 2}, {3, 2, 1, 0}, {0, 2, 1, 3}, {3, 1, 3, 2}};
int i = in[0] << 1 | in[3];
int j = in[1] << 1 | in[2];
return table[i][j];
}

bitset<2> S1(bitset<4> in) {
const int table[4][4] = {
{0, 1, 2, 3}, {2, 0, 1, 3}, {3, 0, 1, 0}, {2, 1, 0, 1}};
int i = in[0] << 1 | in[3];
int j = in[1] << 1 | in[2];
return table[i][j];
}

P4置换

1
2
3
4
5
6
bitset<4> P4(bitset<4> in) {
const int table[] = {2, 4, 3, 1};
bitset<4> out;
for (int i = 0; i < 8; i++) out[i] = in[table[i] - 1];
return out;
}

F变换

1
2
3
4
5
6
7
8
9
10
11
12
bitset<8> F(bitset<8> in, bitset<8> k) {
bitset<4> in_L, in_R;
for (int i = 0; i < 4; i++) in_L[i] = in[i];
for (int i = 0; i < 4; i++) in_R[i] = in[4 + i];

bitset<4> out_L = in_L ^ P4(S(E_P(in_R) ^ k));
bitset<4> out_R = in_R;
bitset<8> out;
for (int i = 0; i < 4; i++) out[i] = out_L[i];
for (int i = 0; i < 4; i++) out[i+4] = out_R[i];
return out;
}

SW变换

1
2
3
4
5
6
7
8
9
10
11
bitset<8> SW(bitset<8> in) {
bitset<4> in_L, in_R;
for (int i = 0; i < 4; i++) in_L[i] = in[i];
for (int i = 0; i < 4; i++) in_R[i] = in[4 + i];
bitset<4> out_L = in_R;
bitset<4> out_R = in_L;
bitset<8> out;
for (int i = 0; i < 4; i++) out[i] = out_L[i];
for (int i = 0; i < 4; i++) out[i+4] = out_R[i];
return out;
}

加密与解密

定义通用加解密流程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bitset<8> crypt(bitset<8> p, bitset<8> k1, bitset<8> k2) {
// 明文p进行IP置换得p1
bitset<8> IP_out = IP(p);

// 对p1进行Fk1变换
bitset<8> Fk1_out = F(IP_out, k1);

// 对p3进行SW交换变换
bitset<8> SW_out = SW(Fk1_out);

// 对p4进行Fk2变换
bitset<8> Fk2_out = F(SW_out, k2);

// p6进行IP逆置换得密文p7
bitset<8> IP_rev_out = IP_rev(Fk2_out);
return IP_rev_out;
}

加密解密的函数模块入口可实现如下,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/// 加密
bitset<8> encrypt(bitset<8> p, bitset<10> k) {
// 求解子密钥k1, k2
bitset<8> k1, k2;
subkey(k, k1, k2);
return crypt(p, k1, k2);
}

/// 解密
bitset<8> decrypt(bitset<8> p, bitset<10> k) {
// 求解子密钥k1, k2
bitset<8> k1, k2;
subkey(k, k1, k2);
return crypt(p, k2, k1);
}

主函数测试

实现反向输出bitset的函数

1
2
3
4
5
6
template <int T>
string reverse(bitset<T> src) {
stringstream ss;
for (int i = 0; i < src.size(); i++) ss << src[i];
return ss.str();
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main() {
// 密钥k
int _k[] = {1, 0, 1, 0, 0, 0, 0, 0, 1, 0};
bitset<10> k;
for (int i = 0; i < 10; i++) k[i] = _k[i];
// 明文p
int _p[] = {0, 1, 0, 0, 0, 0, 0, 1};
bitset<8> p;
for (int i = 0; i < 8; i++) p[i] = _p[i];

auto c = encrypt(p, k);
cout << "密文=" << reverse<8>(c) << endl;
auto mp = decrypt(c, k);
cout << "明文=" << reverse<8>(mp) << endl;

return 0;
}

输出结果

1
2
密文=00010101
明文=01000001

手算过程

2、已知种子密钥k=0111111101,
密钥生成中置换P10、P8分别如下:

1 2 3 4 5 6 7 8 9 10
3 5 2 7 4 10 1 9 8 6
1 2 3 4 5 6 7 8
6 3 7 4 8 5 10 9

(1)试采用S-DES算法计算子密钥K1,K2。
k=0111111101

m1=P10(k)=11111,10011

m1分组后各自循环左移1位得到m2=11111,00111

m2分组后各自循环左移2位得到m3=11111,11100

K1=P8(m2)=01011111

K2=P8(m3)=11111100

(2)若明文p=10011101,试用S-DES算法给出加密过程,要有中间步骤。

IP置换

p1=IP§ = 01011110

进行Fk1变换

输入如下:

p1=01011110

k1=01011111

L1=0101, R1=1110

p2=E/P(R1)=0111101

p3=p2^k1=00100010

L2=0010, R2=0010

S0(L2)=S0_01=00

S1(R2)=S1_01=01

p4=P4(S0||S1=0001)=0100

L3 = p4^L1=0001

R3=1110

p5=Fk1(p1)=00011110

进行SW变换

p6=11100001

进行Fk2变换

输入如下,

p6=11100001

k2=11111100

与Fk1同理可得

p7=Fk2(p6)=11100001

IP逆置换

c=IP1(p7)IP^{-1}(p7)=01100100

故密文为c=01100110