DES暗号を実装する(1) ~サブ鍵生成アルゴリズム編~ - 気まぐれブログ(日記・技術記事・研究のことなど)

使用言語
DES暗号とは
サブ鍵の生成方法
サブ鍵生成アルゴリズム
プログラム

共通鍵暗号方式の代表的な暗号方式である「DES暗号」を実装してみたいと思います.
今回の記事では, DESで使用する「サブ鍵」の生成アルゴリズムを実装していきます.

使用言語

Python 3系

DES暗号とは

DES暗号は, 「ブロック暗号」の一種です. 1977年ごろに開発され, 米国政府の標準暗号となりました. 1984年にはANSI(米国規格協会)によって, 民間標準規格となりました.

DES暗号については, 過去の記事で詳しく説明をしていますので, こちらを参照してください.
tomonori4565.hatenablog.com

サブ鍵の生成方法

DESでは秘密鍵(共通鍵)keyを入力として, 16個の「サブ鍵」というものを生成します. ここでサブ鍵の生成方法を見ていきましょう.

f:id:tomonori4565:20181210203717p:plain — サブ鍵の生成方法

f:id:tomonori4565:20181210203722p:plain — サブ鍵の生成方法

まずkeyが入力されたら, PC1という縮小転置を実行します. PC1によって64bitのkeyは56bitに縮小されます. PC1は以下の転置表によって実行されます.

f:id:tomonori4565:20181210204053p:plain — 縮小転置PC1の表

数式で表すと以下のようになります. $key = k_1k_2...k_{64}$ に対して,

$PC1(key) = PC1(k_1, k_2, ..., k_{64}) = (k_{57}, k_{49}, ..., k_{12}, k_{4})$

PC1が実行されたら, 左28bit, 右28bitに分割し, それぞれ $C_0, D_0$ とします. $C_0, D_0$ はそれぞれLSという手続きによって, 左に1ビット巡回シフトさせます(シフトし終わったものをそれぞれ $C_1, D_1$ とします).

そして, $C_1, D_1$ を連結させたものをPC2という縮小転置に適用させ, 48bitのサブ鍵を生成します. PC2 は以下の転置表によって実行されます.

f:id:tomonori4565:20181210205044p:plain — 縮小転置PC2の表

これらの動作を16ラウンド続けていきます.

ただ一点注意しておくことがあります. 左に1bit巡回シフトを実行するのは，1,2,9,16ラウンド目のときです. それ以外は左に2bit巡回シフトさせる必要があります.

サブ鍵生成アルゴリズム

入力
key：秘密鍵(64bit)
出力
$k_1, k_2, ..., k_{16}$ ：サブ鍵(それぞれ48bit)

(1)64bitのkeyを56bitに変換する縮小転置PC1を適用.すなわち,

$(C_0, D_0) =$ PC1( $key$ )

(2) $i$ = 1とする.

(3) $i \leq 16$ の間, 以下を繰り返す.

(3-1) $i = 1,2,9,16$ ならば左に1bit巡回シフトする. それ以外なら左に2bit巡回シフトする.

$C_i, D_i = (LS_i(C_{i-1}) , LS_i(D_{i-1}))$

(3-2) $C_i, D_i$ を連結させ, 縮小転置PC2を適用. すなわち,

$k_i =$ PC2( $C_i, D_i$ )

(3-3) i = i + 1とする.

(4) $k_1, k_2, ..., k_{16}$ を出力.

プログラム

各メソッドについてはコメントを参照してください.

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]

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
# 出力：巡回シフト結果 (n=1のとき左に1bit巡回シフト)
#
def shift(l, n):
    return l[n:] + l[:n]


#
# enc_sub_key_generate()
# 入力：秘密鍵key
# 出力：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))

    for k in sub_key_list:
        print(k)

    return sub_key_list


#
# dec_sub_key_generate(key)
# 入力：秘密鍵
# 出力：sub_key_list (encのときと逆順)
#
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))

    for k in sub_key_list:
        print(k)

    return sub_key_list


if __name__ == '__main__':

    sub_key_list = enc_sub_key_generate(key)