ikautak.log

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

暗号理論入門　4.10〜4.12

暗号 Python

暗号理論入門 原書第3版

暗号理論入門 原書第3版

4.10 アフィン暗号

m を自然数、平文アルファベットを \mathbb{Z}_m とする。アフィン暗号(affine cypher)とは、ブロック長 n = 1 のブロック暗号で、鍵空間は m に素である a のすべての組 (a,\ b) \in \mathbb{Z}_{m}^{2} からなる。

鍵 e = (a,\ b) に対する暗号化関数 E_e は
　E_e\ \ \ :\ \ \ \Sigma \to \Sigma,\ \ \ \ \ x \to ax + b\ mod\ m
である。鍵 d = (a', b) に対する復号化関数は
　 D_d\ \ \ :\ \ \ \Sigma \to \Sigma,\ \ \ \ \ x \to a'(x - b) mod\ m
である。

pythonで書いてみる。'A'〜'Z'のみ使用する。

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

    def Encrypt(self, m):
        enc = lambda x : chr((self.key[0] * (ord(x)-ord('A')) + self.key[1]) % 26 + ord('A'))
        return ''.join(map(enc, m))

    def Decrypt(self, m):
        gcd, a_, y = xeuclid(self.key[0], 26)
        if a_ < 0:
            a_ += 26

        dec = lambda x : chr((a_ * (ord(x)-ord('A')) - a_ * self.key[1]) % 26 + ord('A'))
        return ''.join(map(dec, m))

拡張ユークリッドアルゴリズムのxeuclid()は以前の記事のものをそのまま使用。

鍵(7, 3)で動かしてみる。

>>> key = (7, 3)
>>> affine = AffineCypher(key)
>>> p = 'AFFINECYPHER'
>>> e = affine.Encrypt(p)
>>> print e
DMMHQFRPEAFS
>>> p = affine.Decrypt(e)
>>> print p
AFFINECYPHER

m = 26 となるアフィン暗号の鍵空間は、 \varphi(26)*26 = 312 個の元がある。鍵をすべて当たってみることで暗号文のみ攻撃で復号化できる。

4.11 行列と線形写像

行列の一般的な話がほとんど。

4.12 アフィン線形ブロック暗号

アフィン線形ブロック暗号はアフィン暗号を一般化したもので、以前はよく使用された。

アフィン線形ブロック暗号を定義するため、自然数 n と m,\ \ \ m \gt 2 を必要とし、n をブロックの長さとする。

ブロック長 n のブロック暗号と平文空間、暗号文空間 \mathbb{Z}_{m}^{n} に対して、そのすべての暗号文関数がアフィン線形であれば、このブロック暗号をアフィン線形という。すべての暗号化関数が線形であれば、このブロック暗号を線形という。

暗号化関数はアフィン線形であるため、
　 E\ :\ \ \mathbb{Z}_{m}^{n} \to \mathbb{Z}_{m}^{n}\ \ ,\ \ \ \ \ \ \vec{v} \to A \vec{v} + \vec{b}\ mod \ m
という形である。 A \in \mathbb{Z}^{(n,n)} かつ b \in \mathbb{Z}^{n} とする。

復号化関数は
　 D\ :\ \ \mathbb{Z}_{m}^{n} \to \mathbb{Z}_{m}^{n}\ \ ,\ \ \ \ \ \ \vec{v} \to A' (\vec{v} - \vec{b})\ mod\ m
となる。
ここで、 A' = (a' adj\ A)\ mod\ m とし、 a' は det\ A の mod\ m での逆元とする。