Cryptography筆記8 - Block Ciphers (PRPs)

Block Cipher

map n bits PT block to n bits CT block，key的長度不一定和block長度一樣：

key越長，越安全，但是加密當然就越花時間。

block cipher是一個iterative process，首先key k會先被expand成許多round keys，每個round會對m做一次加密，透過round function: R(k,m):

AES #round = 10, 3DES #round = 48。

Pseudo Random Permutations

Block cipher本質是一個PRP，定義如下：

存在一"efficient" E(k,x) 是一個function，input定義域為key space K，和X，把某個key 和 x map到另一個y。
x和x'是 1-to-1 relationship，所以這是一個invertible function，其"efficient" inversion為D(k,y)。

兩個PRP例子：

事實上PRP是PRF的更限縮例子：

PRP的output domain X和input domain X是同一個，而PRF output domain和input domain不需要是同一個。

什麼是secure PRF?

PRF定義如下：

定義Funs[X,Y]為一個set，包含所有mapping from X to Y，總共有|Y|^(|X|)個，因為一個y就可以搭配|X|種可能，以128-bit AES來說，X ->Y maps 128 bit to 128 bit，所以滿足此mapping的functions總共有:

(2^128)^(2^128)!!!! 天文數字!


另外定義Funs[X,Y]的subset :

意思是說，如果考慮mapping中一定要一個key k才能把X -> Y 的話，那我們只需要考慮key space K的數量即可，以128-bit AES來說，只有2^128 種可能。

所以我們說一個PRF是secure，如果隨機從Funs[X,Y]中選出的function (truely random function)，不能與隨機從Sf中選取出來的function區別的話(pseudo random function)，就是一個安全的PRF。

同樣的直覺可以用在PRP，如果隨機從X的permutation中選出的function (truely random permutation)，不能與隨機從PRP 利用key set形成的set中選出的permutation區別的話，則說此PRP是secure。

範例: 這是一個secure PRF嗎?

假設我們有一個secure PRF如下:

請問以下G是否也是一個secure PRF?

明顯就不是，因為adversary只要餵食x = 0進入G，就可以得到跟random function in F完全不同的結果，可以明顯區別目前是G還是F在作用，所以這不是一個secure PRF。

PRF => PRG

pseudo random functions可以拿來當作pseudo random generator。
假設某個secure PRF 的Input ->Output 如下:

定義某個Key Generator  maps K to t blocks of n bits each，定義如下:

由於每個block是一個secure PRF的產出，是無法跟pure random function區別的，所以其t個concatenation定義出來的Generator G(k)也是無法跟單一pure random generator產出的結果區分出來，所以這是一個secure PRG。

注意此G(k)定義可以parallel process!