ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

暗号理論入門　4.1〜4.3

暗号 Python

暗号理論入門 原書第3版

暗号理論入門 原書第3版

第4章

4.1 暗号化方式

暗号化方式(encryption scheme)または暗号系(cryptosystem)とは5成分からなる組 (P,\ C,\ K,\ E,\ D) であり、次の性質をもつ。

  1. P は集合であり、平文空間という。その元を平文とよぶ。
  2. C は集合であり、暗号文空間という。その元を暗号化文とよぶ。
  3. K は集合であり、鍵空間という。その元を鍵とよぶ。
  4. E = \{E_k\ \ :\ \ k \in K\} は関数 E_k\ \ :\ \ P \to C の族である。その元を暗号化関数という。
  5. D = \{D_k\ \ :\ \ k \in K\} は関数 D_k\ \ :\ \ C \to P の族である。その元を復号化関数という。
  6. 任意の e \in K に対し、すべての p \in P に対して等式 D_d(E_e(p)) = p が成立するような d \in K が存在する。

暗号化方式の例としてシーザー暗号(Caesar cipher)がある。
平文空間、暗号文空間、鍵空間は \Sigma = \{A,\ B,\ ...,\ \ Z\} である。 A, B, ..., Zを0, 1, ... 25に対応させ、数での計算が可能。
e \in \mathbb{Z}_{26} に対して暗号化関数 E_e を
　 E_e \ :\ \Sigma \to \Sigma,\ \ \ \ \ x \to (x + e) mod\ 26
と定義する。
d \in \mathbb{Z}_{26} に対しては
　 D_d \ :\ \Sigma \to \Sigma,\ \ \ \ \ x \to (x - d) mod\ 26
と定義する。 暗号化鍵 e に対する復号化鍵は d = e である。

pythonで書いてみる。アルファベットだけでなく、ascii全体を使う。

class CaesarCipher(object):
    def __init__(self, key):
        self.key = key

    def encrypt(self, t):
        return ''.join(map(lambda x : chr(ord(x) + self.key), t))

    def decrypt(self, t):
        return ''.join(map(lambda x : chr(ord(x) - self.key), t))

key = 5で'CRYPTO'を暗号化・復号化してみる。

>>> caesar = CaesarCipher(5)
>>> p = 'CRYPTO'
>>> e = caesar.encrypt(p)
>>> e
'HW^UYT'
>>> p = caesar.decrypt(e)
>>> p
'CRYPTO'

シーザー暗号では26個の鍵しか存在しない。（asciiコード全体を使っても256個）
26個すべての鍵を使って調べれば、暗号文から平文が得られ、同時に使用した鍵も得られる。

4.2 私有鍵方式と公開鍵方式

暗号化鍵 e が常にそれに対応する復号化鍵 d に一致する、または容易に計算可能であれば、これを対称鍵方式または私有鍵方式とよぶ。シーザー暗号は対称鍵方式。
非対称暗号方式では d と e は異なり、d は e からは現実的に計算できる計算量でない。

暗号化鍵 e を公開しても復号化鍵 d の方は極秘にしておく方式を公開鍵方式という。
e を公開鍵(public key)、d を私有鍵(private key)という。

4.3 安全性

4.3.1 攻撃の型

攻撃を困難にするため、暗号方式を極秘にすることもできるが、そこから得られる安全性は疑わしい。
よって、現代の暗号は、どんな暗号方式が使用されているか誰もが既に知っていると仮定している。使用された鍵と暗号化された平文のみが極秘にされていると仮定する。
暗号の攻撃方法は以下のようなものがある。

暗号文のみの攻撃

攻撃者は暗号文のみを知っていて、鍵空間の鍵をすべて使って復号化する。コンピュータの計算速度の向上により多くの暗号方式で成果が出ている。

既知平文攻撃

攻撃者は一つの平文とそれに対応する暗号文を知っている。4.14で出てくる。

選択平文攻撃

攻撃者は自分で選択した平文を暗号文にできる。公開鍵方式では誰もが公開鍵を知っているので、この方法は常に可能。誰もが任意の平文を暗号化できる。

適応性選択平文攻撃

攻撃者はどの暗号文を復号化したいか知った後、暗号文を自分で選択した平文にすることができる。公開鍵方式で可能。

選択暗号文攻撃

攻撃者は、自分で選択した暗号文を復号化鍵を知らずに復号化することができる。サーバのなりすましで認証した後、攻撃者は自分で選択した文書を復号化させる。

適応性選択暗号文攻撃

攻撃者は、どこの暗号文を復号化したいか知った後、自分で選択した暗号文を鍵を知ることなしに、復号化できる。

4.3.2 乱数化された暗号化

私有鍵方式で多くの文書を同じ鍵で暗号化する際、初期値を乱数化しておかないと、攻撃者は暗号文がある特定の平文の暗号化であるとすぐにわかってしまう。

4.3.3 数学モデル化

暗号化方式の安全性を証明するには数学的安全性モデルが必要。入門書に以下がある。

現代暗号・確率的証明・擬似乱数

現代暗号・確率的証明・擬似乱数