Classical Cipher and Hash function

30 April 2019

Intro

  • Ciphertext only: 攻擊者有一堆ciphertext，但不知道對應的plaintext
  • Known plaintext attack: 攻擊者有一些明文密文的範例(P,C)
  • Chosen plaintext attack:攻擊者有plaintxt，能得到對應ciphertext
  • Chosen Ciphertext attack: 攻擊者有ciphertext，能得到對應plaintxt

One-way function

定義F(X)是one way function iff
\(F(X) \in N\)
\(F^{-1}(X) \in NPHard\)

一個好的one way function就是給予一個隨機y，沒有polynomial time的解法能推得x，但大部分hash function很難符合，可能會有少數y他可以很快得到解x。 更好的定義方式為對於大部分y，沒有probablistic polynomial time解法得到x，如果x長度為k至多只有1/k個y能夠polynomial解出x，當k夠大時，\(F^{-1}\)幾乎就是沒有polynomial time的問題，因為抽到有polynomial time解的y機率很低

One-way trapdoor function

就是one-way function加上一個key，如果有這把key(trapdoor)的話，逆向\(F{-1}\)就會變得很好解，沒有的話就沒有polynomial time解。 舉例而言: public key encryption, trapdoor即為private key

One-way Hash function

h(x) = y
y 是固定長度，所以x對y是many to 1
但給定一個y要找到一個x使h(x)=y是困難的

Strong collision resistance

給定Hash function H
不能找到m,m’兩個字串 使 H(m) = H(m’)
不然attacker能claim它擁有m，但其實他擁有的是m’

Weak collision resistance

給定Hash function H 和 一個x 找不到另一個x’ 使H(x) = H(x’) 不然就能偽造

Passive attack

active attack

Cryptography 證明方法

建立threat model

construct protocol, theorem

證明這個問題很難

通常是說明他屬於NP-hard或NP-complete的問題之類的 假設在\(P \neq NP\)狀況下，這些protocol都是安全的

Common Classical Cipher

substitution cipher

每個英文字母map到另一個英文字母
所以共有26!種map法
但可以linguistic analysis來破解
分析ciphertext裡char,bigram,trigram出現頻率
跟一般語法中出現頻率，在檢查一些特殊情況，如一個char一個詞，那很可能是a,i
推出一些後再去推剩下的

缺點

很明顯的雖然mapping方法很多，但每個字母永遠是map到另一個char，很固定，所以會有一些點容易被破

Vingere cipher

可以讓char maps到不同char
key是一段letter甚至一個詞，然後不斷重複append
然後把key的char和plaintext的char加起來mod 26就可以。
但還是很好break，只要知道key length，就變成shift cipher的問題了

破解法

設法找出key length，利用英文bigram重複性很高的特性且key length不會太長，所以很容易有重複的bigram在ciphertext內，剛好plaintext對到相同的key char

  1. 先找bigram重複字串，算兩個重複的bigram間的距離，算gcd，可以猜出大概key length
  2. 算出key length後，把文章切成key length長度的block，對每個block分別作分析，例如要得到key的第一個字元，分析每個block的第一個char的出現頻率(linguistic analysis)，就可以猜出key的第一個字元為何，每個key字元都這樣做
  3. 求出key後就可以直接解密

playfair cipher

  • 把plaintext當成unit，然後做translate成ciphertext

Key matrix

一個5x5的matrix，基本上就是要填入所有英文字母 先輸入你的key，再把沒用到的字元以alphabetic order填到matrix內 key have to be no repeating letters

cipher

把plaintext拆成2,2一組，如果有疊字中間用x字元分隔，最後如果是奇數的話再加一個x
EX balloon
ba lx lo on

把兩個字元弄到table內

  • 如果兩個字元在同個column
    • 加密字元就是字元往下一格，最下就回到最上
  • 如果兩個字元在同個row
    • 加密的字元就是該字元往右一格，如果最右邊的那就回到最左邊那格
  • else: 取構成這個table的相同row的char

youtube link