【IS】Classical Encryption #1

對稱式加密

圖片來源：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(從e到G)。
3. 進階字頻分析法
   • 除了單獨看每個字母的頻率之外，還可以進一步分析連字的頻率，如th、st、er等。

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個，通常將I和J視為同一個字。
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

2. 將一個字詞不停重複，直到和明文一樣長當作Key。
3. 將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