Cryptography筆記2 - one-time pad and perfect secrecy

Symmetric Cipher定義

一個cipher是由一個3-tuple組成:( K, M, C )，分別是key space, message space, cypher text space。
然後還要有兩個efficient 演算法，分別是Encryptor E, 和 Decryptor D。

E可以把 KxM的組合mapping到C  (x是cross product)，E在過程中會產生隨機bits用於encryption
D可以把KxC的組合mapping到M，D永遠是deterministic

E, D要滿足所謂consistency equation，也就是用E編碼的，必須一定要可以用D解碼:

The One Time Pad (1917)

cipher定義如下:

key是random bits，長度跟message一樣，E D的定義如下:

c = E(k,m) = k XOR m
m = D(k,c) = k XOR c

舉例來說:

再來檢查E,D是否符合consistency equation:
D(k, E(k,m)) = k XOR E(k,m) = k XOR (k XOR m) ，注意這邊XOR有associative rule，所以
= (k XOR k) XOR m = 0 XOR m = m
得證!

 但是安全性如何呢? 如果我們有一個m，以及c，有辦法猜出k嗎?
按照其E D定義，
c = k XOR m
c XOR m = (k XOR m) XOR m
c XOR m = k XOR (m XOR m) = k XOR 0 = k

所以是可以的?!

OTP的優點是ED非常efficient，但是由於key要跟message一樣長度，所以實務上很難用，因為如果你有辦法很安全的跟遠端傳遞這個長的key，那實際上你已經有一個好的安全機制了，不需要用OTP。

Shannon對perfect secrecy的定義

白話文:看到cipher text，完全不透漏任何plain text的訊息的話，此cipher是安全的。
perfect secrecy的正式定義:

k是Key space的一個random variable (記得random variable是一個function, 把sample space中的element map到某一個real number)，其機率分布為uniform，意思就是任意k出現的機率均等。

任何attacker要是看到c，都無法猜出c是E(k,m0)還是E(k,m1)。true for all m。
所以有perfect secrecy至少可以免除cipher text only attach，但是不保證不受其他種attack!

我們必須要證明OTP有perfect secrecy:

首先按照機率的定義:
Pr[ E(k, m) = c ] = #(k in K 滿足 E(k,m) = c) / |K|，對任意m,c來說

再來根據perfect secrecy定義，如果達成Pr[ E(k,m0)=c ] = Pr[ E(k, m1) =c]，且對任意m來說都成立的話，則上式分子應該要是常數，那OTP有符合嗎? 也就是要回答OPT中 #(k in K 滿足 E(k,m) = c)   是否為常數?

對OTP來說， E(k,m) = c  = k XOR m
=> c XOR m = k XOR m XOR m = k

所以是一對一的關係，#k = 1。

得證OTP有perfect secrecy，可以免除ciphertext only attack。

可惜另外shannon也證明了，要達到perferct secrecy，key length >= message length，所以OTP是optimal perfect secrecy cipher，雖然實務上非常難以使用。