気まぐれブログ(日記・技術記事・研究のことなど)

気まぐれに更新します．温かい目で見ていただければ...

DES暗号を実装する(2) ~データ暗号化・復号編~

CTF 暗号理論

前回はサブ鍵の構成方法について説明しましたが, 今回はデータの暗号化と復号アルゴリズムについて見ていきましょう.

データ暗号化・復号アルゴリズム

早速アルゴリズムを以下に示したいと思います. 暗号化と復号ではほぼ同じアルゴリズムを使用することができます.

データ暗号化アルゴリズム

入力：平文 m (64bit), サブ鍵 k_1, k_2, ..., k_{16} (それぞれ48bit)
出力：暗号文 c (64bit)

(1) n = 1とする.

(2) 平文 mに初期転置 IPを適用します.

(3) 左右に2分割し, 左の32bitを L_0, 右の32bitを R_0とします.

(4) n \leq 16の間, 次の処理を繰り返します.

\ \  (4-1) R_{n-1}とサブ鍵 k_nを入力して, ラウンド関数 fを計算します. ( fについては後述)

\ \ (4-2) L_{n-1}と yの排他的論理和を取り, それを L_n'とします. R_n'は R_{n-1}と同じです.


L_n' = L_{n-1} \oplus y
R_n' = R_{n-1}

\ \ (4-3) n = 16でなければ, 左右32bitごとを入れ替えます.


L_n = R_n'
R_n = L_n'

\ \ (4-4) n = n + 1とします.

(5) L_{16}と R_{16}を連結して, 最終転置 IP^{-1}を適用して出力します.

f:id:tomonori4565:20181211125907p:plain
データ暗号化アルゴリズム

データ復号アルゴリズム

入力：暗号文 c (64bit), サブ鍵 k_1, k_2, ..., k_{16} (それぞれ48bit)
出力：平文 m (64bit)

(1) n = 1とする.

(2) 平文 mに初期転置 IPを適用します.

(3) 左右に2分割し, 左の32bitを L_0, 右の32bitを R_0とします.

(4) n \leq 16の間, 次の処理を繰り返します.

\ \ (4-3) n = 1でなければ, 左右32bitごとを入れ替えます.


L_n = R_n'
R_n = L_n'

\ \  (4-1) R_{n-1}とサブ鍵 k_nを入力して, ラウンド関数 fを計算します. ( fについては後述)

\ \ (4-2) L_{n-1}と yの排他的論理和を取り, それを L_n'とします. R_n'は R_{n-1}と同じです.


L_n' = L_{n-1} \oplus y
R_n' = R_{n-1}

\ \ (4-4) n = n + 1とします.

(5) L_{16}と R_{16}を連結して, 最終転置 IP^{-1}を適用して出力します.


転置 IP, IP^{-1}

上記のアルゴリズムで使用する IP, IP^{-1}の正体は以下の通りとなっています.

f:id:tomonori4565:20181211131057p:plainf:id:tomonori4565:20181211131108p:plain
初期転置 IP (青), 最終転置 IP^{-1} (橙)

最終転置は初期転置の逆転置であり, 次の関係式を満たします.


IP(IP^{-1}(x)) = x

ラウンド関数 f

上記アルゴリズムで使用されているラウンド関数は非線形関数であり, この関数 fの設計が暗号的強度に大きな影響を与えます.

ラウンド関数 fのアルゴリズム

入力： R(32bit), サブ鍵 k (48bit)
出力：演算結果 (32bit)

(1) Rに拡大転置 Eを適用して, 鍵と同じ48bitにします.


R' = E(R)

(2)得られたデータとサブ鍵の排他的論理和を取ります.


R'' = R' \oplus k

(3) R''を6bitごとに分割して8個のグループを作成します. 各グループに対して, S-box変換 S_nを適用することで, 6bitを4bitに変換します. 得られた結果を全て連結することで32bitの R'''が得られます.


R''' = S(R'')

(4)出力転置 Pを適用し, 結果を出力します.

拡大転置 E, 出力転置 P

拡大転置 Eと出力転置 Pは以下のようになっています.

f:id:tomonori4565:20181211134514p:plain
拡大転置 E

f:id:tomonori4565:20181211134540p:plain
出力転置 P

S-boxの仕組み

S-boxの転置表は以下のサイトに載っています(自分で作るのは流石に大変すぎた).
kazukichi.hatenablog.jp

コード

import math
import random

pc1_table = [57,49,41,33,25,17,9,
            1,58,50,42,34,26,18,
            10,2,59,51,43,35,27,
            19,11,3,60,52,44,36,
            63,55,47,39,31,23,15,
            7,62,54,46,38,30,22,
            14,6,61,53,45,37,29,
            21,13,5,28,20,12,4]

pc2_table = [14,17,11,24,1,5,
            3,28,15,6,21,10,
            23,19,12,4,26,8,
            16,7,27,20,13,2,
            41,52,31,37,47,55,
            30,40,51,45,33,48,
            44,49,39,56,34,53,
            46,42,50,36,29,32]

E = [32,1,2,3,4,5,
    4,5,6,7,8,9,
    8,9,10,11,12,13,
    12,13,14,15,16,17,
    16,17,18,19,20,21,
    20,21,22,23,24,25,
    24,25,26,27,28,29,
    28,29,30,31,32,1]

P = [16,7,20,21,
    29,12,28,17,
    1,15,23,26,
    5,18,31,10,
    2,8,24,14,
    32,27,3,9,
    19,13,30,6,
    22,11,4,25]

S1 = [[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]]

S2 = [[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]]

S3 = [[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]]

S4 = [[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]]

S5 = [[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]]

S6 = [[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]]

S7 = [[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]]

S8 = [[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]]

S_list = [S1, S2, S3, S4, S5, S6, S7, S8]

IP = [58,50,42,34,26,18,10,2,
     60,52,44,36,28,20,12,4,
     62,54,46,38,30,22,14,6,
     64,56,48,40,32,24,16,8,
     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]

IP_inverse = [40,8,48,16,56,24,64,32,
             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]

bit_list = [0,1]

#
# odd_parity()
# 入力：リストl
# 出力：0 or 1
# lにおけるハミング重みが奇数個ならば0, 偶数個ならば1
#
def odd_parity(l):
    odd_count = 0
    for l_bit in l:
        if l_bit == 1:
            odd_count += 1

    if (odd_count % 2 == 0):
        return 1
    else:
        return 0

#
# key_generate()
# 入力：なし
# 出力：秘密鍵64bit
# 秘密鍵を生成する.
#
def key_generate():
    key = []
    for i in range(8):
        l = random.choices(bit_list, k=7)
        key += l
        key.append(odd_parity(l))

    return key

#
# PC1
# 入力：配列secret_key...64bit
# 出力： C0, D0...それぞれ28bit
# C0は左28bit, D0は右28bit
#
def pc1(secret_key):
    c0 = []
    d0 = []
    for i in range(56):
        if i <= 27:
            c0.append(secret_key[pc1_table[i]-1])
        else:
            d0.append(secret_key[pc1_table[i]-1])
    return c0, d0

#
# PC2
# 入力：配列c_d_list(C0とD0を連結させたもの)...56bit
# 出力： k 48bit
#
def pc2(c_d_list):
    k = []
    for i in range(48):
        k.append(c_d_list[pc2_table[i]-1])

    return k


#
# shift
# 入力：リストl, 移動ビット数n
# 出力：巡回シフト結果
#
def shift(l, n):
    return l[n:] + l[:n]


#
# sub_key_generate()
# 入力： 秘密鍵key(64bit)
# 出力：sub_key_list
#
def enc_sub_key_generate(key):
    c = []
    d = []
    sub_key_list = []

    c, d = pc1(key)

    for i in range(1, 1+16):
        if (i == 1) or (i == 2) or (i == 9) or (i == 16):
            c = shift(c, 1)
            d = shift(d, 1)
        else:
            c = shift(c, 2)
            d = shift(d, 2)
        sub_key_list.append(pc2(c + d))

    return sub_key_list


#
# dec_sub_key_generate()
# 入力：秘密鍵key(64bit)
# 出力：sub_key_list
#
def dec_sub_key_generate(key):
    c = []
    d = []
    sub_key_list = []

    c, d = pc1(key)

    for i in range(1, 1+16):
        if i == 1:
            c = c
            d = d
        elif (i == 2) or (i == 9) or (i == 16):
            c = shift(c, -1)
            d = shift(d, -1)
        else:
            c = shift(c, -2)
            d = shift(d, -2)
        sub_key_list.append(pc2(c + d))

    return sub_key_list


#
# xorを計算
#
def calc_xor(x, k):
    if (x == k):
        return 0
    else:
        return 1

#
# 10進数numを2進数に変換して配列に格納(4bitで固定)
#
def calc_binary(num):
    list = []
    while num > 0:
        list.append(num % 2)
        num = num // 2

    while len(list) != 4:
        list.append(0)

    list.reverse()
    return list

#
# ラウンド関数f
# 入力：x(32bit), サブ鍵k(48bit)
# 出力：y(計算結果, 32bit)
#
def f(x, k):

    x1 = []
    x2 = []
    x3 = []
    y = []
    for i in range(48):
        x1.append(x[E[i]-1])

    for x1_item, k_item in zip(x1, k):
        x2.append(calc_xor(x1_item, k_item))

    for i in range(0, 48, 6):
        arg1 = (i//6)
        arg2 = x2[i+0] * 2 + x2[i+5] * 1
        arg3 = x2[i+1] * 8 + x2[i+2] * 4 + x2[i+3] * 2 + x2[i+4] * 1
        x3 = x3 + calc_binary(S_list[arg1][arg2][arg3])

    for i in range(32):
        y.append(x3[P[i]-1])

    return y

#
# 暗号化アルゴリズム
#
def encryption(m, sub_key_list):
    n = 1

    m_list = []
    for i in range(64):
        m_list.append(m[IP[i]-1])

    L = m_list[:32]
    R = m_list[32:]

    for k in sub_key_list:
        y = f(R, k)
        for i in range(32):
            L[i] = calc_xor(L[i], y[i])
        if n != 16:
            L, R = R, L
        n += 1

    c = []
    LR = L + R
    for i in range(64):
        c.append(LR[IP_inverse[i]-1])

    return c

#
# 復号化アルゴリズム
#
def decryption(c, reverse_sub_key_list):
    n = 1

    c_list = []
    for i in range(64):
        c_list.append(c[IP[i]-1])

    L = c_list[:32]
    R = c_list[32:]

    for k in reverse_sub_key_list:
        if n != 1:
            L, R = R, L
        y = f(R, k)
        for i in range(32):
            L[i] = calc_xor(L[i], y[i])
        n += 1

    m = []
    LR = L + R
    for i in range(64):
        m.append(LR[IP_inverse[i]-1])

    return m


#
# メイン関数
#
if __name__ == '__main__':

    tmp = []
    for i in range(1, 65):
        tmp.append(i % 10)

    #print(tmp)
    m = random.choices(bit_list, k=64)
    print(m)

    key = key_generate()
    sub_key_list = enc_sub_key_generate(key)
    reverse_sub_key_list = dec_sub_key_generate(key)

    c = encryption(m, sub_key_list)
    m = decryption(c, reverse_sub_key_list)

    print(c)
    print(m)

出力結果

上から, 「ビット桁表示」, 「元の平文 m」, 「暗号文 c」, 「暗号文を復号した結果 m'」

python des.py 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4]
[0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]
[1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]

まとめ

元の平文と暗号文を復号した結果が一致しているので, DESを実装することができた. 気が向いたらDESの仕組みをもっと掘り下げて説明したり, 危険性について説明していこうと思う(書いてる途中で挫折しそう).