バーナム暗号を実装してみる
こんにちは。今回も暗号について取り上げます。今回はバーナム暗号です。
バーナム暗号とは
ＡＴ＆Ｔに所属したバーナムによって考案された暗号です。
バーナム暗号では、平文と同じ長さの鍵を用意します。この鍵は乱数により作られます。平文と鍵について、ビットごとに排他的論理和（ＸＯＲ）を求めることにより、暗号化されます。
復号するには、暗号化に使った鍵を用いて、暗号と鍵についてビットごとに排他的論理和を求めます。これにより、平文に復号されます。
１ビットの平文Ｍに対して、１ビットの鍵Ｋを使って暗号Ｃを作り、できた暗号Ｃと鍵Ｋを用いて復号します。
| 平文Ｍ | 鍵Ｋ | 暗号Ｃ （Ｍ xor Ｋ） | 鍵Ｋ （再掲） | 復号Ｍ’ （Ｃ xor Ｋ） |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
バーナム暗号について確率を考えてみる
シーザー暗号では、文字の出現確率から暗号を解読することができてしまいました。バーナム暗号ではどうでしょうか。ビットの出現確率を求めていきます。
暗号化したときのビットに出現する値の確率
はじめに暗号Ｃについて０が出現する確率を求めます。
\[ \begin{eqnarray} P(C=0)&=&P(M=0 \cap K=0) + P(M=1 \cap K=1) \\&=&P(M=0)P(K=0)+P(M=1)P(K=1)\\&=&P(M=0) \times \frac{1}{2}+P(M=1) \times \frac{1}{2}\\&=&\frac{1}{2}(P(M=0)+P(M=1))\\&=&\frac{1}{2}\times 1\\&=&\frac{1}{2}\end{eqnarray} \]
となります。同様に暗号Ｃが１になる確率も\(\frac{1}{2}\)です。これらから、暗号化したときにビットの出現確率は等確率になることがわかりました。
情報理論的安全性
次に暗号Ｃと平文Ｍとの関係を確率で考えていきます。
暗号Ｃ＝０の条件のもとでＭ＝０となる条件付き確率を考えます。
\[ \begin{eqnarray} P(M=0|C=0) &=& \frac{P(M=0 \cap C=0)}{P(C=0)} \\&=& \frac{P(M=0 \cap K=0)}{P(M=0 \cap K=0)+P(M=1\cap K=1)} \\ &=& \frac{P(M=0) \times \frac{1}{2}}{P(M=0) \times \frac{1}{2}+P(M=1) \times \frac{1}{2}}\\&=&\frac{\frac{1}{2}\times P(M=0)}{ \frac{1}{2} \times(P(M=0)+P(M=1))}\\&=&\frac{\frac{1}{2}\times P(M=0)}{ \frac{1}{2} \times 1}\\&=&P(M=0) \end{eqnarray} \]
同様にして、
\(P(M=0|C=1)=P(M=0)\)
\(P(M=1|C=0)=P(M=1)\)
\(P(M=1|C=1)=P(M=1)\)
が成り立ちます。以上の数式は、攻撃者が暗号を盗聴した元での平文の確率と平文の確率は等しいことになり、暗号Ｃからは何の情報も得られていないことを示しています。このような性質を情報理論的安全性といいます。
バーナム暗号を実装してみる
毎度のＰｙｔｈｏｎです。乱数は疑似乱数を用いています。
import random
def encrypt( plain, key ):
print( 'encrypt' )
random.seed( key )
result = ''
for letter in plain:
m = ord(letter)
k = random.randrange(256)
c = m ^ k
print( letter, format(m,'08b'), format(k,'08b'), format(c,'08b') )
result += format( c, '08b' )
return result
def decrypt( cipher, key ):
print( 'decrypt' )
random.seed( key )
result = ''
pos = 0
while pos<len(cipher):
c = int( cipher[pos:pos+8], 2 )
k = random.randrange(256)
m = c ^ k
print( format(c,'08b'), format(k,'08b'), format(m,'08b'), chr( m ) )
result += chr( m )
pos += 8
return result
if __name__ == '__main__':
plain_text = "I can accept failure, everyone fails at something. But I can't accept not trying."
key = 'Jordan'
cipher_text = encrypt( plain_text, key )
print()
decode_text = decrypt( cipher_text, key )
print()
print( 'cipher' )
print( cipher_text )
print( 'decode' )
print( decode_text )
実行結果です。ビットごとにＸＯＲをとっていることがわかるように、ビットで表示しています。
encrypt
I 01001001 01011110 00010111
00100000 10001100 10101100
c 01100011 11101100 10001111
a 01100001 11101100 10001101
n 01101110 10010111 11111001
00100000 11011111 11111111
a 01100001 11010010 10110011
c 01100011 01101100 00001111
c 01100011 00100011 01000000
e 01100101 01011011 00111110
p 01110000 10110010 11000010
t 01110100 10010111 11100011
00100000 00011111 00111111
f 01100110 01001110 00101000
a 01100001 10101100 11001101
i 01101001 11110101 10011100
l 01101100 11110111 10011011
u 01110101 11011100 10101001
r 01110010 00111111 01001101
e 01100101 00100010 01000111
, 00101100 00011011 00110111
00100000 01011010 01111010
e 01100101 01110110 00010011
v 01110110 10011000 11101110
e 01100101 00100111 01000010
r 01110010 10101000 11011010
y 01111001 01111111 00000110
o 01101111 10100101 11001010
n 01101110 01010111 00111001
e 01100101 11100111 10000010
00100000 00111110 00011110
f 01100110 11111110 10011000
a 01100001 11011100 10111101
i 01101001 11011000 10110001
l 01101100 11111011 10010111
s 01110011 01000000 00110011
00100000 10010011 10110011
a 01100001 11010101 10110100
t 01110100 11010100 10100000
00100000 10111011 10011011
s 01110011 10101111 11011100
o 01101111 01100010 00001101
m 01101101 00111001 01010100
e 01100101 00101011 01001110
t 01110100 01101101 00011001
h 01101000 11110110 10011110
i 01101001 10001110 11100111
n 01101110 01001001 00100111
g 01100111 00010100 01110011
. 00101110 00100000 00001110
00100000 00000101 00100101
B 01000010 01101001 00101011
u 01110101 11001100 10111001
t 01110100 00010001 01100101
00100000 01100100 01000100
I 01001001 01000011 00001010
00100000 01001011 01101011
c 01100011 01110111 00010100
a 01100001 01000011 00100010
n 01101110 10000011 11101101
' 00100111 01111101 01011010
t 01110100 10010000 11100100
00100000 11001101 11101101
a 01100001 10011011 11111010
c 01100011 00011101 01111110
c 01100011 10000110 11100101
e 01100101 10010001 11110100
p 01110000 11000111 10110111
t 01110100 11001101 10111001
00100000 10001111 10101111
n 01101110 11011000 10110110
o 01101111 01110011 00011100
t 01110100 00111001 01001101
00100000 11100111 11000111
t 01110100 10101110 11011010
r 01110010 11010011 10100001
y 01111001 10010101 11101100
i 01101001 00000011 01101010
n 01101110 10101111 11000001
g 01100111 11110010 10010101
. 00101110 10000000 10101110
decrypt
00010111 01011110 01001001 I
10101100 10001100 00100000
10001111 11101100 01100011 c
10001101 11101100 01100001 a
11111001 10010111 01101110 n
11111111 11011111 00100000
10110011 11010010 01100001 a
00001111 01101100 01100011 c
01000000 00100011 01100011 c
00111110 01011011 01100101 e
11000010 10110010 01110000 p
11100011 10010111 01110100 t
00111111 00011111 00100000
00101000 01001110 01100110 f
11001101 10101100 01100001 a
10011100 11110101 01101001 i
10011011 11110111 01101100 l
10101001 11011100 01110101 u
01001101 00111111 01110010 r
01000111 00100010 01100101 e
00110111 00011011 00101100 ,
01111010 01011010 00100000
00010011 01110110 01100101 e
11101110 10011000 01110110 v
01000010 00100111 01100101 e
11011010 10101000 01110010 r
00000110 01111111 01111001 y
11001010 10100101 01101111 o
00111001 01010111 01101110 n
10000010 11100111 01100101 e
00011110 00111110 00100000
10011000 11111110 01100110 f
10111101 11011100 01100001 a
10110001 11011000 01101001 i
10010111 11111011 01101100 l
00110011 01000000 01110011 s
10110011 10010011 00100000
10110100 11010101 01100001 a
10100000 11010100 01110100 t
10011011 10111011 00100000
11011100 10101111 01110011 s
00001101 01100010 01101111 o
01010100 00111001 01101101 m
01001110 00101011 01100101 e
00011001 01101101 01110100 t
10011110 11110110 01101000 h
11100111 10001110 01101001 i
00100111 01001001 01101110 n
01110011 00010100 01100111 g
00001110 00100000 00101110 .
00100101 00000101 00100000
00101011 01101001 01000010 B
10111001 11001100 01110101 u
01100101 00010001 01110100 t
01000100 01100100 00100000
00001010 01000011 01001001 I
01101011 01001011 00100000
00010100 01110111 01100011 c
00100010 01000011 01100001 a
11101101 10000011 01101110 n
01011010 01111101 00100111 '
11100100 10010000 01110100 t
11101101 11001101 00100000
11111010 10011011 01100001 a
01111110 00011101 01100011 c
11100101 10000110 01100011 c
11110100 10010001 01100101 e
10110111 11000111 01110000 p
10111001 11001101 01110100 t
10101111 10001111 00100000
10110110 11011000 01101110 n
00011100 01110011 01101111 o
01001101 00111001 01110100 t
11000111 11100111 00100000
11011010 10101110 01110100 t
10100001 11010011 01110010 r
11101100 10010101 01111001 y
01101010 00000011 01101001 i
11000001 10101111 01101110 n
10010101 11110010 01100111 g
10101110 10000000 00101110 .
cipher
000101111010110010001111100011011111100111111111101100110000111101000000001111101100001011100011001111110010100011001101100111001001101110101001010011010100011100110111011110100001001111101110010000101101101000000110110010100011100110000010000111101001100010111101101100011001011100110011101100111011010010100000100110111101110000001101010101000100111000011001100111101110011100100111011100110000111000100101001010111011100101100101010001000000101001101011000101000010001011101101010110101110010011101101111110100111111011100101111101001011011110111001101011111011011000011100010011011100011111011010101000011110110001101010110000011001010110101110
decode
I can accept failure, everyone fails at something. But I can't accept not trying.
今回はこれでおしまいにします。それではまた。