S-DES加密过程

加密模型

输入输出

算法流程

密钥生成流程

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

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

2. 5位一组分割成两组，每组内循环左移s位记作变换$SL_s$，对$m_1$进行5位一组分割的循环左移1位变换，得$m_2=SL_1(m_1)$

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

4. 对$m_2$进行5位一组分割的循环左移2位变换，得$m_3=SL_2(m_2)$

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

加密流程

先来看加密算法，已知明文$p$

1. 对$p$执行初始变换$IP$得到$IP(p)$

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

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

4. 对$SW(F_{k_1}(IP(p)))$执行依赖密钥$k_2$的变换$F_{k_2}$得到$F_{k_2}(SW(F_{k_1}(IP(p))))$

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

解密流程

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

加解密公式

加密公式：$c={IP}^{-1}(F_{k_2}(SW(F_{k_1}(IP(p)))))$

解密公式：$p={IP}^{-1}(F_{k_1}(SW(F_{k_2}(IP(c)))))$

Fk变换流程

$F_k$变换的输入为8位二进制数的左右两半L，R和8位子密钥$k$

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

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

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

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

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

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

代码实现

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

数据结构

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

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

子密钥生成

P10变换

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

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变换的原理

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循环左移

/// 循环左移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位记作变换$SL_s$

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

/// 计算子密钥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置换

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逆置换

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扩展置换变换

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盒变换

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置换

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变换

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变换

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;
}

加密与解密

定义通用加解密流程如下

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;
}

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

/// 加密
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的函数

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

主函数

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;
}

输出结果

密文=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=$IP^{-1}(p7)$=01100100

故密文为c=01100110