namdicul's blog

気ままに更新します. CTFと暗号理論について勉強中です.

5000円のワインと100万円のワインの味の違いがわかる方が人生が豊かになるのか?

新年あけましておめでとうございます.
2019年もよろしくお願いします.




さて, 皆さんは年始をどのようにお過ごしでしょうか?友達と初詣に行ったり, おせちを食べながら家族団らんで過ごしたりする人もいることでしょう. 私は母方の祖父母の家で蟹鍋を食べるのが元旦の恒例行事となっています.


元旦といえば, 正月特番を見る方も多いと思います. 私はとりわけ好きな正月番組があります. それは「芸能人格付けチェック」という番組です.
どんな番組かと言いますと, 2種類(ないしは3種類)のワイン, 楽器, 盆栽, 牛肉などについて, 一方はとても高級で, 他方は庶民的なものであるものが出され, 出演者は高級なものを当てることができればランクを維持することができ, 間違えてしまうとランクが下がってしまうというものです.



毎年GACKTさんは一流芸能人をキープすることができてて, すげえな〜って思ったり, はたまた大御所の役者さんたちが画面から消えてしまうと, 「こんな大物芸能人でも一流を見極めることは難しいんだなあ」と思ったりもします.

そこで1つ気になることがあります.

「一流のものを見極められる方が人生は豊かになるのか?」


一流と二流は紙一重

この間, 少し高級なお店に行って, 一流の牛肉を食べてきました. とても柔らかく, 口の中でとろけるような感覚があり, 普段食べる牛肉とは全く違うように感じました. 「あっこれが一流の味なのか」と, 少し感激をしました.



今年の芸能人格付けチェックでは, 「超高級の牛肉」と「スーパーの牛肉(100g620円)」を見極める問題が出題されました. 一般の方からしたら「こんなの簡単に見極めるだろw」って思うかと思います. 僕もそう思ってました.



でも, 約半数の方が高級な牛肉を見極めることができませんでした. これは何故なのでしょうか?


1つの原因としてあげられるのは, 私たちが高級食材を目にすると「美味しいに違いない」, 「普通の食材とは何かが違うはず」といったようなある種のバイアスが脳に働くことです. これは高級なものに関する固定観念から生じる「思考停止」といってもいいかも知れません. したがって, その固定観念が生じない場面では普通の人間は「一流と二流」を見極めることが困難になると思うのです.

その他にも色々な原因があると思うのですが, そもそも私は「一流と二流は紙一重」なのではないかと思っています. 牛肉でいうと, ほんの少しの舌触り感の違いや, 脂の香りの違いが「一流と二流」を分けると思うのです.
しかし, その紙一重の差は「小さいようで大きい差」であると考えています. 紙一重の差を生み出すのには, 多大なる努力や投資が必要になってくると思うのです.

紙一重の違いを分かる方が得するのか?

まずは, 一流と二流の紙一重の差を「分からない」ことによるメリットをあげてみたいと思います. 例えば, あなたは夕食の準備をしているとします. そこでいつもとは違う高級の白米を炊いて家族に提供したとします. 家族からあまり反応が得られない, つまり一流と二流の紙一重のさを感じることができなければ, 普段使っている白米をこれから出し続けた方がコスパはよくなりますよね. 逆に, 家族から「普段とは全然違ってとても美味しい」という反応が得られた場合, 次の日に普段食べている白米を提供したら, あまり美味しさを感じれなくなるかもしれません. 次の日からも高級白米を提供することになり, 出費が多くなるかも知れません. このように一流と二流の紙一重の差を「分からない」ことによって, ある種の「生きづらさ」を感じなくて済むようになると思います.

続いて, 一流と二流の紙一重の差を「分かる」ことによるメリットをあげてみたいと思います. 紙一重の差を見極めるには, その差がなんであるのかを考え抜く必要があると思うのです. 高級であるがゆえに生じる固定観念を捨てて, 単純にモノとしての比較を通じて「紙一重の差の違い」を認識する必要があります. これは普段から脳をフル回転させていないとできないことだと思います(少なくとも今の僕にはできそうもありません).
おそらく紙一重の差を認識できる人は, 普段から色々な視点から物事を考えていて, 細かな違いにも敏感に気づける「頭の良い人」だと思うのです.

結論

ぶっちゃけ, 一流と二流の紙一重の差を感じ取ることができなくても, 人間的価値は下がりませんし, 生きていくにも支障はないと思っています.


ですが, 私は一流と二流の差を感じ取れる人間でありたいと思っています.

普段から色々な視点で物事を考え, 固定観念に囚われず, 些細な違いを認識できるようになれば, 幅広い視野を手に入れることができ, 人生が豊かになるかもしれません.

小さなことが気になってしまう?

この記事を書くきっかけ

つい3時間ほど前までは、こんな記事を書くつもりはありませんでした。でも、ついさっきこの記事を書こうと決めました。

今日は塾バイトがあったのですが,塾長から依頼されていた電話のニッケル水素電池の交換を行いました。なんでもないただの交換作業です。交換し終わって、さてお家に帰ろうと車に乗りました。

すると家に着く間際に急に不安感が押し寄せてきました。
「あれ、俺プラスとマイナス正しく接続したっけ。逆接続してないかな?」

それからは頭の中がその事でいっぱいになりました。不安で不安で仕方がない。もし逆接続してて、ニッケル電池が爆発したらどうしよう、火事になったらどうしよう、俺が全額賠償しないといけないのか、などなど・・・


もうそれからは他のことを考えることは出来ませんでした。他の人からすれば単なる杞憂かと思われるのですが、自分にとっては気が気で仕方がない。爆発してからは手遅れなので、迷惑を承知で帰宅した塾長を呼び出し、校舎を開けてもらって電話の電池の接続を確認しました。


結果、正しく接続出来ていました。ああ、良かった良かった。大事にならなくて。


それで一安心して、帰宅してお風呂に入っていると、また不安感に襲われました。「塾長にすげえ迷惑かけてしまったな。忙しいのに申し訳ないな。」今度はこのことで頭がいっぱいになってしまったのです。


昔から自分は完璧主義でかつ不安症なのですが、最近はそれが顕著に出てしまい、異常なほどの不安感を感じることが多いのです。

他にも思い当たる節が・・・

この他にも最近、過度な不安を感じることが多々あります。

①家の鍵や窓の鍵を複数回チェックしないと家を出れない。また通学途中に家の鍵や窓の鍵を閉めたか不安になってしまうと、いちいち家に帰宅して確認してしまう。

②バイトで数学を教えているときに、ミスが怖くて何度も計算を確認する。

③インフルエンザや感染症にかかるのがこわくて、何度もアルコール消毒をする。

④車を運転しているときに、少しの衝撃(段差等)を感じても「人をひいたのではないか」と不安になり、現場まで戻る。

その他にも色々ありますが、代表的なものを挙げました。

もしや強迫性障害パニック障害と関係

以前の記事で自分がパニック障害であることを告白しましたが(おかげさまでどん底の状態は抜け出して、今では普通に生活出来るレベルになりました)、どうやら「強迫性障害」もパニック障害と併発する病気らしい。そういや、なんか医者からそんなようなことも聞いた気がする。


http://bunshun.jp/articles/-/7488


どちらも原因はセロトニンの不足らしい。最近はトマトやナッツなど、セロトニンを増加させるものは沢山食べているつもりなんだが、本質的に改善するには薬物治療が必要みたい。


もし似通った症状がある方はコメントして下さると嬉しいです。

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

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

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

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

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

入力:平文 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の仕組みをもっと掘り下げて説明したり, 危険性について説明していこうと思う(書いてる途中で挫折しそう).

DES暗号を実装する(1) ~サブ鍵生成アルゴリズム編~

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

使用言語

Python 3系

DES暗号とは

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

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

サブ鍵の生成方法

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

f:id:tomonori4565:20181210203717p:plainf: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)

共通鍵暗号の攻撃モデル

今回は, 共通鍵暗号の攻撃モデルについて説明していきたいと思います.

暗号文単独攻撃(Ciphertext Only Attack; COA)

暗号文単独攻撃とは, 同一の秘密鍵によって暗号化された複数の暗号文を利用することで, 鍵や平文に関する情報を取得しようとする攻撃です.

例えば, 単一換字暗号を解析するには「頻度分析」というものを使用します(知らなかったor忘れていた方は以下のリンクをクリック)
tomonori4565.hatenablog.com

頻度分析は, 暗号文に出現する文字の頻度から平文に関する情報を取得する分析方法でしたね. これは暗号文単独攻撃の1つと言えます.

既知平文攻撃(Known Plaintext Attack; KPA)

既知平文攻撃とは, ある特定の平文に対してその暗号文が既知である場合に利用される攻撃手法です. ただし, すべての暗号文は同一の秘密鍵によって暗号化されているものとします.

例えば, "I LOVE YOU"という平文に対する暗号文が"QWERTY"であるとします. このとき, 取得した暗号文がたまたま"QWERTY"であったら, 秘密鍵に関する情報を何も知らなくても, 平文が"I LOVE YOU"であることがわかります.

このように, ある特定の平文と暗号文のペアがわかっている場合に仕掛けられる攻撃が既知平文攻撃となります.

選択平文攻撃(Chosen Plaintext Attack; CPA)

選択平文攻撃とは, 自分で選んだ任意の平文に対する暗号文を得られる状況において, 攻撃を実行するモデルです.
攻撃者は暗号化オラクルと呼ばれる, 入力した平文に対して適切な暗号文を返す装置を利用して暗号文を得ます. 暗号化オラクルを入手するには, 暗号化装置を入手したり, 認証サーバを悪用したりします.
暗号化オラクルを入手することで, 秘密鍵を知らなくとも平文に対して適切な暗号文を得られることになり, 暗号を解読する大きな手がかりを入手することになります.

選択暗号文攻撃

選択暗号文攻撃とは, 解読対象の暗号文 c^*を受け取るの時点で, 復号オラクルを利用して自分で選んだ任意の暗号文に対する平文を得られるという状況下で攻撃するモデルのことです.

適応的選択暗号文攻撃

適応的選択暗号文攻撃とは, 解読対象の暗号文 c^*を受け取る前後の時点で, 復号オラクルを利用して自分で選んだ任意の暗号文に対する平文を得られるという状況下で攻撃するモデルのことです.

シーザー暗号をUNIXで試す

UNIXでシーザー暗号を使いたいとき, 以下のようにコマンドを打てばOKです.

Hirata:~ hiratatomonori$ echo AKADEMIA | tr A-Z D-ZA-C
DNDGHPLD
Hirata:~ hiratatomonori$ echo DNDGHPLD | tr D-ZA-C A-Z
AKADEMIA
Hirata:~ hiratatomonori$ 

trコマンドについては以下を参照にしてください.

www.atmarkit.co.jp