Try   HackMD

【IS】Classical Encryption #1

對稱式加密

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

圖片來源:https://www.ssl2buy.com/wiki/symmetric-vs-asymmetric-encryption-what-are-differences

  • 所謂的對稱式加密,即為加密和解密的Key(金鑰)為同一把
  • 整個系統如同上圖所示,很單純:Plain Text(明文)經過Encryption(加密)變為Cipher Text(密文);再經由同一把Key透過Decryption(解密)變回Plain Text。

何謂優秀的加密

  • 我們不希望訊息被所有人看到,然而傳輸時可能要透過各種公開的平台才能成功傳遞,因此我們才需要進行加密。
  • 這邊需要有一個概念,由於傳遞的媒介或平台很可能是公開的,因此你的Cipher Text是會被拿到的。這裡的進行加密的目的並不是讓你的Cipher Text不被碰觸,而是即使它被碰觸也沒關係
  • 當然,我們還是希望訊息被應該看見的人看見。
  • 所以好的加密方式應該是在擁有Cipher Text的情況下,如果沒有Key就很難得到Plain Text,但如果擁有Key卻很簡單就可以得到Plain Text。

對稱式加密的問題

  • 對稱式加密其實從根本上有個矛盾點:如果我和對方能夠擁有同一把鑰匙,那我幹嘛不將訊息當作鑰匙就好?
  • 如果你想通了,你可能會覺得對稱式加密根本沒有用,但其實在現今的密碼學系統中還是有許多對稱式加密的應用。
  • 因此我們之後都是建立在雙方已經擁有Key的前提下來討論。

古典加密法

Caesar Cipher

  • 中文為凱薩加密法,就是著名的凱薩大帝發明的;又稱為Shift Cipher(位移加密)
  • 作法就是給予一個整數當作key,讓明文中的每個字母都加上key值,轉換為新的字母。
  • 解密時就反方向位移即可。
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

範例

  • Key: 3
  • Plain Text: meet me after the toga party
  • Cipher Text: PHHW PH DIWHU WKH WRJD SDUWB

特點

  1. 暴力破解
    • 因為英文字母只有26個字,因此你加密的可能性只有26種。期望值而言試13次就被破解了。
  2. 字頻分析法
    • 位移並不會改變字母的頻率。以英文字來說,字母e出現的頻率通常是最高的,如果今天密文G的頻率最高,我們可以合理推測key的值為2(從eG)。
  3. 進階字頻分析法
    • 除了單獨看每個字母的頻率之外,還可以進一步分析連字的頻率,如thster等。

Monoalphabetic Cipher

  • Caesar Cipher的加強版,讓每個字母都做相對應的替換,做一個一對一的映射,而不是位移共同的長度。
  • 改善了Caesar Cipher做26次就被破解的缺點。

範例

  • Key: DKVQFIBJWPESCXHTMYAUOLRGZN
  • Plain Text: ifwewishtoreplaceletters
  • Cipher Text: WIRFRWAJUHYFTSDVFSFUUFYA

特點

  1. 字頻分析法
    • 雖然每個字的位移長度變得不同了,然而頻率還是可以解出一定的資訊。
  2. 進階字頻分析法
    • 同上。

Playfair Cipher

  1. 做一個5*5的表格
  2. 根據Key將字母依序填入,重複的字母跳過。
    • 因為字母有26個,通常將IJ視為同一個字。
  3. 填完Key的字母後,將沒出現過的字母依序填完。
  4. 開始加密,將明文兩個兩個字一組,如果
    I. 兩個字母出現在同一直排,轉換為下面一格的字母。
    II. 兩個字母出現在同一橫列,轉換為右邊一個的字母。
    III. 其他情形,找出另外兩格使該四個字母形成一個矩形。
    • 如果兩個字母一樣、或是最後只剩一個字,插入/補上字母X

範例

  • Key: playfairexample
P L A Y F
I(J) R E X M
B C D G H
K N O Q S
T U V W Z
  • Plain Text: HI DE TH EG OL DI NT HE TR EX ES TU MP
  • Cipher Text: BM OD ZB XD NA BE KU DM UI XM MO UV IF

特點

  • 成功解決了頻率分析的問題,Key也不需要像Monoalphabetic Cipher那麼長。
  • 少一個字母能夠轉換,且會在某些時候插入字母X,使明文受到影響。
  • Code table的後半部分幾乎是固定的,容易從這邊遭到攻擊破解。

Vigenère Cipher

  1. 準備和Caesar Cipher一樣的表格。
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  1. 將一個字詞不停重複,直到和明文一樣長當作Key。
  2. 將Key和明文相加成為密文。
    • 如果超過26就modulo 26

範例

  • Key: SESAME
  • Plain Text: T H I S I S A T E S T M E S S A G E
  • Key Stream: S E S A M E S E S A M E S E S A M E
  • Cipher Text: L L A S U W S X W S F Q W W K A S I

特點

  • 明文中同樣的字母會被不同的Key加工,成功迴避掉字頻的問題。
  • 如果Key的長度被得知,被破解的可能性會大幅上升。

Autokey Cipher

  • 針對需要Key和明文一樣長的加密法,提供Key的產生法,因此可搭配其他加密法使用。
  • 在提供一個字詞當作Key之後,不是不停重複Key來完成Key Stream,而是將明文放到Key後面當作新的Key。

範例(搭配Vigenère Cipher)

  • Key: deceptive
  • Key Steam: deceptivewearediscoveredsav
  • Plain Text: wearediscoveredsaveyourself
  • Cipher Text: ZICVTWQNGKZEIIGASXSTSLVVWLA

特點

  • 解密時需要先解開前段,然後用解出來的明文放到Key後面繼續解。

Vernam Cipher

  • 和Vigenère Cipher基本上一樣,只是將運算方法從加法改為XOR。
  • XOR需要先將字母對應的數字轉為五位元的二進制碼,再將每個位元分別做XOR。
Plain Text Key Cipher Text
0 0 0
0 1 1
1 0 1
1 1 0

範例

  • Plain text: H → 7(十進位) → 00111(二進位)
  • Key: X → 23(十進位) → 10111(二進位)
  • Cipher Text: 10000(二進位) → 16(十進位) → Q

特點

  • XOR有個特別的地方,將明文X對金鑰K兩次XOR運算,其結果必定為X(不變)。
    • XOR的這個特點,也常常在之後的其他加密法被運用,因為同樣的運算可以同時加密和解密,在實際上可以節省硬體成本。
  • 不過在Vernam Cipher會導致結果可能超過A~Z的範圍,結果會出現非英文字母的東西。

One-Time Pad

  • 給予和明文一樣長的密碼本,做XOR的運算即可加解密。
  • 安全性是絕對安全,完全不可能破解;然而需要以下前提:
    1. 密碼產生的方式完全隨機
    2. 密碼本使用一次便銷毀。
  • 在世界大戰期間被大量使用,掌握敵軍的密碼本便會大幅影響戰況。

Rail Fence Cipher

  • Key為一個數字,代表籬笆的數量。
  • 將明文用籬笆的方式寫下(↘↗),然後用橫排的方向去重新排列,得到密文。

範例

  • Key: 3
  • Plain Text: HELLOWORLD
H       O       L
  E   L   W   R   D
    L       O
  • Cipher Text: HOLELWRDLO

特點

  • 相較於前面的加密法,這個加密法只進行字母的換位而不進行替換

Row Transposition Ciphers

  • Key為row的順序,將明文寫成矩形後,再按照key的順序一個一個直排重新排列。
    • 有點難描述,請直接看範例。

範例

  • key: 4312567
  • Plain Text: attackpostponeduntiltwoamxyz
4 3 1 2 5 6 7

a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
  • Cipher Text: TTNAAPTMTSUOAODWCOIXKNLYPETZ

Product Ciphers

  • 直接給予一個Table代表新的順序。

範例

  • Key:
15 11 19 18 16 03 07 14 02 20
04 12 09 06 01 05 17 13 10 08
  • Plain Text : thestrengthofthispig
t h e s t r e n g t
h o f t h i s p i g
  • Cipher Text : HHIPIEETHGSOGRTTSFTN
H H I P I E E T H G
S O G R T T S F T N
tags: IS note