encryption

傳送秘密

秘密:一件事情,只有我知,外人不知。

如何在眾目睽睽下傳送秘密呢?

這裡提供兩個策略:掩、飾。

第一個策略是遮掩資料、包裝資料,導致外人看不見。比如寄信,我們使用信封,讓外人無法偷看資料。要驗證外人是否偷看資料,可以使用易碎膠帶;要阻止外人偷看資料,可以使用保險箱。

第一個策略在電腦世界行不通。資料在網路線中、空氣中傳送,包裝薄弱。只需接線、接收,有心人皆可直接取得資料。

第二個策略是修飾資料、加工資料,導致外人看不懂。比如行話,我們去到夜店說要冰塊和鹽,只有熟人才能理解話中有話。

第二個策略在電腦世界行得通。資料套用四則運算,就變得完全令人看不懂。套用反運算,就看得懂了。比如說字母從零開始編號,每個字母乘三加三模二十六,然後字串頭尾對調。

想要實行第二個策略,當事人必須先有共識,你知我知、外人不知;否則外人也能看懂你我傳送的秘密了。比如「從零開始編號……頭尾對調」就是共識。又比如我和你當眾說「老地方見」,外人聽了不知道是哪裡,但是你我早知道老地方是哪裡。外人一旦知道老地方是指什麼,外人就知道你我的行蹤了。

也就是說:你我必須先有共同秘密,才能傳送秘密!雞生蛋蛋生雞,總得起個頭。兩種解法:一、你我事先私下見面,約定第一個共同祕密。二、你我當眾揣摩彼此、塑造共識,形成第一個共同秘密。

你我擁有第一個共同秘密之後,即可利用遞推法,傳送更多秘密。比如過幾天我又和你說「上次隔壁那一家,東西也很棒,待會一起去。」你我分享了更多秘密,但是外人仍舊霧裡看花。

一件事情通常有各式各樣的解讀方式,理論上外人永遠無法正確解讀秘密。但是當傳送秘密越來越多,則解讀方式就越來越少。安全起見,三不五時就要更換第一個共同秘密。

A1與A2事先見面。
A1: 我跟你說,當我說「跑」,我們就逃跑。
A2: 好。

B1與B2事先見面。
B1: 我跟你說,當我說「跑」,我們就往前衝。
B2: 好。

後來A1A2B1B2通通上戰場,
C聽到他們說跑,但是不知道他們打算逃跑還是往前衝。

encrypt / decrypt

「加密」是改變資料外觀。「解密」是回復原本外觀。

資料加密之前叫做「明文plaintext」,加密之後叫做「密文ciphertext」。「加密」是明文變密文,「解密」是密文變明文。

            encrypt
thank you! --------> 3Q!
           <--------
            decrypt

                    encrypt
Fibonacci sequence --------> 13-3-2-31-1-1-8-5
                   <--------
                    decrypt

UVa 425 11220 11385

attack(crack)(cryptanalysis)

「攻擊」、「破解」、「密文分析」就是給定密文,找出明文,在不知道加密解密方式的情況下。

[ciphertext]
O, Draconian devil! Oh, lame saint. P.S. Find Robert Langdon.

please find plaintext.

即便外人不知道加密解密方式,外人還是可以用試誤法,窮舉各種加密解密可能性,一一嘗試解密,總有一種會成功。即便密文有很多種解讀方式,外人仍然可以大概猜出個端倪。

UVa 795 828 11697

加密解密基本原理:substitution與transposition

現今的加密演算法,通通都是換字面(substitution)、換位置(transposition)。這是最符合電腦運作特性的方式。

你我事先見面約定換字面、換位置的表格,不讓外人知道;如此一來,只有你我可以加密解密。

設計表格時,要注意密文是否可以正確還原成明文。用數學的術語來說就是:表格必須擁有反函數。

UVa 306 458 468 554 641 726 850 856 865 10082 10222 10896 11278 11541 11946

攻擊基本原理:frequency analysis與dictionary attack

俗話說:「兵來將擋、水來土掩」。凡有加密解密方式,就有破解方式。

XPUBKPIU ZPKB O QOTUW OTRG JINWT GEJT SERROIN PF
IEZPFW NPXXWTWIK XTER XPUBKPIU ZPKB O FROQQ EIW
PK PF RWTWQG O HJWFKPEI EX PIFKPKJKPIU FPUIF OIN FPUIOQF

換字面的知名破解方式是統計出現頻率(frequency analysis)。首先統計英文對話當中每個英文字母的出現頻率,由高到低依序是etaoinshrdlucmfwypvbgkjqxz。通常密文出現最多次的符號八九不離十就是e!如果e讀起來不通順,那就試t,以此類推。

亦可統計英文對話當中每個英文單字的出現頻率,由高到低依序是the be to of and a in that等等。通常密文多半含有這些單字。

除了針對單一字母、單一單字進行統計,亦得針對雙字母、仨字母、雙單字、仨單字等進行統計,效果更佳。

HET TEGAR SUREAQ SAH ON SCERNOR

換位置的知名破解方式是查字典(dictionary attack)。窮舉字典裡面每一個單字,一一跟密文比對,看看字母數量是否一致、讀起來是否通順。anagram就是這樣的遊戲。

以上提到的攻擊過程都是人工作業。想要寫程式自動作業,那麼讀者必須利用「natural language processing」領域的知識,判斷破解之後的明文是不是可讀的句子、判斷最有可能出現的句子。

其他加密解密的原理

除了換字面、換位置以外,還有很多神奇的加解密原理,不過我沒有仔細研究,大家可以自行研究。

基於符號。換成看不懂的符號。例如火星文、顏文字。事實上我們可以拿編碼演算法、壓縮演算法,當作加密演算法。隨機取一個演算法,稍作修改,不告訴外人,就能利用此演算法加解密。

[ciphertext]
99,3qㄋ姑力i讀豬,偶會+ Uㄉ!

[plaintext]
舅舅,謝謝你鼓勵我讀書,我會加油的!

基於取樣。插入字母拼貼字母。例如《聖經密碼》固定間隔取字母、《火鳳燎原》的城下一聚。

[ciphertext]
Rips ExplAineD thaT eacH codE is a Case Of adDing

[plaintext]
READ THE CODE

基於推理。分析探索已知未知。例如猜數字魔術。例如下面的益智謎題:

X先生、Y先生都具有足夠的推理能力。
這天,他們正在接受推理面試。
他們知道桌子的抽屜裡有如下16張撲克牌:
紅心 A、Q、4
黑桃 J、8、4、2、7、3
梅花 K、Q、5、4、6
方塊 A、5

約翰教授從這16張牌中挑出一張牌來,
並把這張牌的點數告訴X先生,
把這張牌的花色告訴Y先生。

這時,
約翰教授問X先生和Y先生:
你們能從已知的點數或花色中推知這張牌是什麼牌嗎?
X先生:「我不知道這張牌。」
Y先生:「我知道你不知道這張牌。」
X先生:「現在我知道這張牌了。」
Y先生:「我也知道了。」

請問:這張牌是什麼牌?

UVa 10030

encryption演算法

Caesar cipher

羅馬帝國時期的演算法。原理是換字面。

加密:明文每個字元加三成為密文。解密:密文每個字元減三成為明文。三是事先約定的秘密,可以改成任意數。

引入密鑰的觀念:事先約定的秘密,只需要一個數字,不需要加密解密方式。加密解密方式可以公諸於世;只要密鑰沒有公諸於世,外人就無法解密。

大小寫、空白鍵、標點符號等細節,請自行制定規則。

攻擊方式:頻率分析。甚至可以直接窮舉26種加法量,一一嘗試解密。

ENIGMA

二戰時期的演算法。Caesar cipher的加強版。

引入區塊的觀念:各區塊各自加密解密。事先約定一個短字串當作秘密。

跳著抓字母,就是Caesar cipher。攻擊方式:窮舉各種區塊長度;針對一種區塊長度,跳著抓字母,實施頻率分析。

XOR cipher

電腦草創時期的演算法。ENIGMA的加強版。

引入位元的觀念:以位元為基本單元。XOR的意義:位元是否需要改變。事先約定一個二進位整數當作秘密。

偶數次的XOR具有抵消的功效。加密、解密,過程一模一樣!

想要避免頻率攻擊,一種方式是取消區塊。優點:每個位元的改變機率都是1/2,互相獨立,無法分辨明文,形成完美的加密。缺點:事先約定的秘密,必須跟明文一樣長,導致傳輸量遽增。

Feistel cipher

XOR cipher的加強版。

事先約定的秘密跟明文一樣長,傳輸量大,無法破解。事先約定的秘密很短,傳輸量小,容易破解。此演算法介於中間。

引入多回合的觀念:盡量讓密文「看起來似乎很亂」。

區塊長度是64 bit。

F是任意的加密演算法,例如換字面、換位置,例如Caesar cipher、ENIGMA。

F也可以是任意的函數,而且F不必擁有反函數!偶數次的XOR具有抵消的功效,因此解密時不必使用F的反函數!

key是事先約定的秘密,自行制定長度;每回合都用不一樣的秘密,以增強加密效果。

最後一回合結束,另外再左右交換一下,打亂文字先後順序。

data encryption standard(DES)

Feistel cipher的加強版。已被淘汰,參考看看就好。

引入密鑰調度的觀念:讓每回合的密鑰「看起來似乎很亂」。

加密的詳細架構如下:

permutation是重新排列換位置。contraction是重新排列並且剔除一些位元。每回合key都被分為兩段,分別往高位數循環位移,位移量只有1和2兩種可能,請查表格;所有回合的位移量總和28,剛好等於位元長度28,剛好繞一圈。

F的構造如下:

S的構造如下:

附帶一提,每個函數S1到S8的最高位元、最低位元,對應到expansion所拓展的位元。這兩個位元被調整成最高位元。

表格S1到S8是查表:輸入n,輸出表格第n個數。

Hill cipher

經濟大蕭條時期的演算法。

引入線性變換的觀念。加密:套用線性函數(矩陣)。解密:套用反函數(反矩陣)。

advanced encryption standard(AES)
Rijndael cipher

正在使用的演算法。美國國家安全局NSA公開徵選而得。

引入方塊的觀念:區塊排成方塊,方便攪亂順序。

區塊:排成4×4方塊,每格8 bit,總共128 bit。直向排列。

┌───┬───┬───┬───┐
│ 0 │ 4 │ 8 │12 │
├───┼───┼───┼───┤
│ 1 │ 5 │ 9 │13 │   ┌───┐
├───┼───┼───┼───┤   │   │ = 8 bit
│ 2 │ 6 │10 │14 │   └───┘
├───┼───┼───┼───┤
│ 3 │ 7 │11 │15 │
└───┴───┴───┴───┘

四種加密演算法:SubBytes換字面、ShiftRows換位置、MixColumns線性變換、AddRoundKey位元XOR。

加密:四種加密演算法,依序重複N+1回合。第0回合只做AddRoundKey,第N回合不做MixColumns。解密:反過來做。

SubBytes:格子為單位,換字面,請查表格。

                         encrypt
  lsb  0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
msb ┌─────────────────────────────────────────────────┐
  0 │ 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76 │
  1 │ ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0 │
  2 │ b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 │
  3 │ 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 │
  4 │ 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 │
  5 │ 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf │
  6 │ d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 │
  7 │ 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 │
  8 │ cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 │
  9 │ 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db │
  a │ e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 │
  b │ e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 │
  c │ ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a │
  d │ 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e │
  e │ e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df │
  f │ 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16 │
    └─────────────────────────────────────────────────┘
                         decrypt
  lsb  0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
msb ┌─────────────────────────────────────────────────┐
  0 │ 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb │
  1 │ 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb │
  2 │ 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e │
  3 │ 08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25 │
  4 │ 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92 │
  5 │ 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84 │
  6 │ 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06 │
  7 │ d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b │
  8 │ 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73 │
  9 │ 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e │
  a │ 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b │
  b │ fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4 │
  c │ 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f │
  d │ 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef │
  e │ a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61 │
  f │ 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d │
    └─────────────────────────────────────────────────┘

ShiftRows:橫條為單位,左循環移位,位移量漸增。

             ┌───┬───┬───┬───┐     ┌───┬───┬───┬───┐
left shift 0 │ 0 │ 4 │ 8 │12 │     │ 0 │ 4 │ 8 │12 │
             ├───┼───┼───┼───┤     ├───┼───┼───┼───┤
left shift 1 │ 1 │ 5 │ 9 │13 │     │ 5 │ 9 │13 │ 1 │
             ├───┼───┼───┼───┤ ——→ ├───┼───┼───┼───┤
left shift 2 │ 2 │ 6 │10 │14 │     │10 │14 │ 2 │ 6 │
             ├───┼───┼───┼───┤     ├───┼───┼───┼───┤
left shift 3 │ 3 │ 7 │11 │15 │     │15 │ 3 │ 7 │11 │
             └───┴───┴───┴───┘     └───┴───┴───┴───┘

MixColumns:直條為單位,實施固定的線性變換。

┌─           ─┐ ┌───┐   ┌───┐   ┌─           ─┐ ┌───┐   ┌───┐
│ 02 03 01 01 │ │ 0 │   │ 0'│   │ 02 03 01 01 │ │ 4 │   │ 4'│
│             │ ├───┤   ├───┤   │             │ ├───┤   ├───┤
│ 01 02 03 01 │ │ 1 │   │ 1'│   │ 01 02 03 01 │ │ 5 │   │ 5'│
│             │ ├───┤ = ├───┤   │             │ ├───┤ = ├───┤
│ 01 01 02 03 │ │ 2 │   │ 2'│   │ 01 01 02 03 │ │ 6 │   │ 6'│
│             │ ├───┤   ├───┤   │             │ ├───┤   ├───┤
│ 03 01 01 02 │ │ 3 │   │ 3'│   │ 03 01 01 02 │ │ 7 │   │ 7'│
└─           ─┘ └───┘   └───┘   └─           ─┘ └───┘   └───┘
┌─           ─┐ ┌───┐   ┌───┐   ┌─           ─┐ ┌───┐   ┌───┐
│ 02 03 01 01 │ │ 8 │   │ 8'│   │ 02 03 01 01 │ │12 │   │12'│
│             │ ├───┤   ├───┤   │             │ ├───┤   ├───┤
│ 01 02 03 01 │ │ 9 │   │ 9'│   │ 01 02 03 01 │ │13 │   │13'│
│             │ ├───┤ = ├───┤   │             │ ├───┤ = ├───┤
│ 01 01 02 03 │ │10 │   │10'│   │ 01 01 02 03 │ │14 │   │14'│
│             │ ├───┤   ├───┤   │             │ ├───┤   ├───┤
│ 03 01 01 02 │ │11 │   │11'│   │ 03 01 01 02 │ │15 │   │15'│
└─           ─┘ └───┘   └───┘   └─           ─┘ └───┘   └───┘
    encrypt           decrypt
┌─           ─┐   ┌─           ─┐
│ 02 03 01 01 │   │ 0e 0b 0d 09 │
│             │   │             │
│ 01 02 03 01 │   │ 09 0e 0b 0d │
│             │   │             │
│ 01 01 02 03 │   │ 0d 09 0e 0b │
│             │   │             │
│ 03 01 01 02 │   │ 0b 0d 09 0e │
└─           ─┘   └─           ─┘

AddRoundKey:格子為單位,XOR本回合密鑰。

┌───┬───┬───┬───┐   ┌───┬───┬───┬───┐   ┌───┬───┬───┬───┐
│ 0 │ 4 │ 8 │12 │   │k0 │k4 │k8 │k12│   │ 0'│ 4'│ 8'│12'│
├───┼───┼───┼───┤   ├───┼───┼───┼───┤   ├───┼───┼───┼───┤
│ 1 │ 5 │ 9 │13 │   │k1 │k5 │k9 │k13│   │ 1'│ 5'│ 9'│13'│
├───┼───┼───┼───┤ ⊕ ├───┼───┼───┼───┤ = ├───┼───┼───┼───┤
│ 2 │ 6 │10 │14 │   │k2 │k6 │k10│k14│   │ 2'│ 6'│10'│14'│
├───┼───┼───┼───┤   ├───┼───┼───┼───┤   ├───┼───┼───┼───┤
│ 3 │ 7 │11 │15 │   │k3 │k7 │k11│k15│   │ 3'│ 7'│11'│15'│
└───┴───┴───┴───┘   └───┴───┴───┴───┘   └───┴───┴───┴───┘

KeyExpansion:密鑰調度。活用上述四種加密演算法,求得每回合密鑰。細節請見維基百科:

美國國家安全局NSA提供的演算法標準文件:

網路上找到的實作程式碼:

ChaCha cipher

正在使用的演算法。以XOR cipher為基礎,參考Rijndael cipher改良而得。

引入密鑰加密【尚無正式名稱】的觀念:XOR cipher不需修飾明文,只需修飾密鑰。只對密鑰實施加密演算法,以節省計算時間。

區塊:排成4×4方塊,每格32 bit。橫向排列。

┌───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │
├───┼───┼───┼───┤
│ 4 │ 5 │ 6 │ 7 │   ┌───┐
├───┼───┼───┼───┤   │   │ = 32 bit
│ 8 │ 9 │10 │11 │   └───┘
├───┼───┼───┼───┤
│12 │13 │14 │15 │
└───┴───┴───┴───┘

方塊包含四種數字:常數constant、密鑰key、區塊編號block count、亂數種子nonce。排版請見下圖。

┌───┬───┬───┬───┐
│ c │ c │ c │ c │
├───┼───┼───┼───┤
│ k │ k │ k │ k │
├───┼───┼───┼───┤
│ k │ k │ k │ k │
├───┼───┼───┼───┤
│ b │ n │ n │ n │
└───┴───┴───┴───┘

常數:0x657870616e642033322d62797465206b。

常數是expand 32-byte k的ASCII編碼。想必是作者的提示。

密鑰:256 bit,只佔8格。其餘格子用其他三種數字補足。

區塊編號:從0開始。

亂數種子:事先指定一個隨機數。範例請見下圖。

constant    = (65:78:70:61:6e:64:20:33:32:2d:62:79:74:65:20:6b)
key         = (00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:
               10:11:12:13:14:15:16:17:18:19:1a:1b:1c:1d:1e:1f)
block count = 1
nonce       = (00:00:00:09:00:00:00:4a:00:00:00:00)
┌──────────┬──────────┬──────────┬──────────┐
│ 65787061 │ 6e642033 │ 322d6279 │ 7465206b │
├──────────┼──────────┼──────────┼──────────┤
│ 00010203 │ 04050607 │ 08090a0b │ 0c0d0e0f │
├──────────┼──────────┼──────────┼──────────┤
│ 10111213 │ 14151617 │ 18191a1b │ 1c1d1e1f │
├──────────┼──────────┼──────────┼──────────┤
│ 00000001 │ 00000009 │ 0000004a │ 00000000 │
└──────────┴──────────┴──────────┴──────────┘

byte reversal:每個格子,以byte為單位,頭尾顛倒。

65:78:70:61 ---> 61:70:78:65
6e:64:20:33 ---> 33:20:64:6e
     :                :

quarter round:選定四個格子abcd進行加密,融合了線性變換、位元XOR、位元左循環移位(換字面)。換位置太麻煩不做。

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

方塊加密流程:一、byte reversal。二、四個直條、四個反斜線,依序進行quarter round。重複10回合。格式請見下圖。三、步驟一和步驟二的結果相加(換字面)。四、byte reversal。

/ a▪▪▪   ▪a▪▪   ▪▪a▪   ▪▪▪a   a▪▪▪   ▪a▪▪   ▪▪a▪   ▪▪▪a \
⎸ b▪▪▪ → ▪b▪▪ → ▪▪b▪ → ▪▪▪b → ▪b▪▪ → ▪▪b▪ → ▪▪▪b → b▪▪▪ ⎹ × 10
⎸ c▪▪▪   ▪c▪▪   ▪▪c▪   ▪▪▪c   ▪▪c▪   ▪▪▪c   c▪▪▪   ▪c▪▪ ⎹
\ d▪▪▪   ▪d▪▪   ▪▪d▪   ▪▪▪d   ▪▪▪d   d▪▪▪   ▪d▪▪   ▪▪d▪ /

加密暨解密:方塊還原成區塊,明文區塊和該區塊做XOR。

網際網路工程任務組IETF提供的演算法標準文件:

演算法作者的實作程式碼:

加密解密基本原理:block cipher mode與key schedule

「區塊加密模式」。利用先前區塊的密文,改良當前區塊的密文。目前已有多種手法,但是缺乏科學根據。詳情請見維基百科:

「密鑰調度」。區塊之間也可以做密鑰調度。利用先前區塊的密鑰,改良當前區塊的密鑰。目前沒有固定手法,大家自由發揮。

最後講個八卦

相傳圖靈帶頭破譯ENIGMA,然而他只是破譯團隊當中的一員、破譯過程當中的一段。類似的神話故事還有愛迪生發明電燈。

one-way encryption

cryptographic function

加密是明文變成密文。一個東西變成另一個東西,概念等同於數學術語「函數」。加密可以視作函數,稱作「密碼學函數」。

一種方式:輸入明文,輸出密文。密鑰用來製造函數。

fkey(plaintext) = ciphertext
g(key) = fkey

另一種方式:輸入明文與密鑰,輸出密文。

f(plaintext, key) = ciphertext

什麼是優秀的加密、差勁的加密呢?目前沒有定論!

要避免外人從密文猜出明文,有時候也要避免外人看穿明文如何變成密文。大致能想到的有:

一、明文與密文一一對應。
二、明文與密文隨機對應。(關於隨機,請見本站文件「random number」。)
三、明文與密文相差極大。
四、明文稍微改動,密文劇烈變動。
五、密文稍微改動,明文劇烈變動。

many-to-one function / one-to-one function

f(x) = y,相同的x對應相同的y,有些不同的x對應相同的y,這樣的f稱作「多對一函數」。

f(x) = y,相同的x對應相同的y,不同的x對應不同的y,這樣的f稱作「一對一函數」。

hash function

f(x) = y,自訂y的範圍大小,這樣的f稱作「雜湊函數」。

學過資料結構「hash table」的讀者應該不陌生才對。

如果讓y的範圍小於x的範圍,就會形成多對一函數。一般來說,大家提到雜湊函數,習慣預設y的範圍小於x的範圍。

pseudorandom function / pseudorandom permutation

「偽隨機函數」。x與y的對應,看起來似乎很亂。

「偽隨機排列」。x與y一樣多&一對一函數&偽隨機函數。

計算機只能接受明確指令,大家只好使用明確演算法來製造隨機排列。具備明確規律,卻假裝隨機,於是稱之為「偽」。

大家努力讓偽隨機排列「看起來似乎很亂」。但由於缺乏「亂」的明確定義,所以無法精準評比優劣。一切都是靠感覺,很不科學。

換字面、換位置,其實都是偽隨機排列。先前介紹的加密演算法,其實都是偽隨機排列,除了XOR cipher系列。

one-way function

f(x) = y,給x求y算很快,給y求x算很久,這樣的f稱作「單向函數」。

所謂單向函數,是指很難反向,不是指無法反向。凡是離散函數,窮舉法必能反向。

知名範例是整數乘法、整數分解。

f(a,b) = ab
整數乘法:給a和b求ab。時間複雜度是一次整數乘法。
整數分解:給ab求a和b。試除法,時間複雜度是sqrt(ab)次整數除法。

知名範例是餘數次方、餘數開方。

f(a) ≡ aᵏ (mod m)   k m是常數
餘數次方:給a求aᵏ。時間複雜度是log(k)次餘數乘法。
餘數開方:給aᵏ求a。NP-complete。

collision-free function(collision-resistant function)

f(x₁) = f(x₂),符合條件的x₁與x₂稱作「碰撞」。

f(x₁) = f(x₂),求得符合條件的x₁與x₂要算很久,這樣的f稱作「無碰撞函數」。

所謂無碰撞函數,是指很難找到碰撞,不是指沒有碰撞。凡是多對一函數,必有碰撞。

cryptographic hash function(cryptographic many-to-one collision-free one-way pseudorandom hash function)

「密碼學雜湊函數」。加密很快,解密很久。

大家的需求,目前是這五樣,以後還可能更多:

雜湊函數的用途:密文限制長度。
隨機函數的用途:密文看起來似乎很亂。
單向函數的用途:難以還原明文。
無碰撞函數的用途:難以偽造明文。
多對一函數的用途:難以確定明文。

不必解密、不被解密,這種情況下適合使用密碼學雜湊函數。例如XOR cipher,解密不需要反函數,可用此函數做密鑰加密。

不必解密、不被解密,因此密碼學雜湊函數不含密鑰。

攻擊基本原理:rainbow table attack

尋找碰撞的知名方式是彩虹表攻擊。

曾經計算過的x與y,一對一對儲存起來,以後直接查表。

攻擊基本原理:brute-force attack與birthday attack

尋找碰撞的知名方式是暴力攻擊和生日攻擊。

暴力攻擊:依序窮舉x。根據鴿籠原理,最差N+1次,必定成功。N是y的數量。

生日攻擊:隨機窮舉x。根據生日問題,經過sqrt(N)次,成功機率可過半。N是y的數量。

簡單起見,假設一年365天,假設每天出生機率均等。

鴿籠原理:366人之中,一定有人生日碰巧相同。

生日問題:K人之中,有人生日碰巧相同的機率如下。

所有可能性    365ᴷ = 365×365×365×...
生日皆異的可能性 P(365,K) = 365×364×363×...
生日相同的可能性 365ᴷ - P(365,K)
生日相同的機率  (365ᴷ - P(365,K)) / 365ᴷ
N日K人版本    (Nᴷ - P(N,K)) / Nᴷ

想讓機率過半,固定N的情況下,那麼K要足夠大,K ≈ sqrt(N)。推導過程請見:

延伸閱讀:pseudorandom generator theorem

有人利用機率學的均勻分布,重新定義隨機函數、單向函數。

並且發現以下性質:一、隨機數能產生隨機函數,隨機函數能產生隨機排列。反之亦然。二、隨機函數能產生單向函數。反之亦然。

但是注意到,「均勻分布」只是「隨機」的需求之一,「隨機」只是「加密」的需求之一,而「隨機」和「加密」的需求至今仍然沒有明確規範。因此,實務上沒人利用這些性質建立加密演算法。

此處不介紹這些性質。有興趣的讀者請自行查閱維基百科:

one-way encryption演算法

MD5

容易找到碰撞,已被淘汰。

SHA-2

正在使用的演算法。美國國家安全局NSA自行開發而得。

SHA-3

尚未使用的演算法。美國國家標準技術局NIST公開徵選而得。

BLAKE3

加密解密基本原理:one-way compression function

「單向壓縮函數」。利用先前區塊的雜湊值,改良整體的雜湊值。目前已有多種手法,但是缺乏科學根據。詳情請見維基百科:

「單向壓縮函數」的地位宛如先前章節的「區塊加密模式」。雖然名稱有壓縮二字,但是其實毫無關聯。命名品味不太好。

key exchange

Diffie–Hellman key exchange

本單元的先備知識是「residue」!

想要傳送秘密,你我必須事先私下見面約定共同秘密。然而在電腦世界當中,你我無法事先私下見面。因此有人想出在公開場合建立共同秘密的演算法。由於非常簡單易用,似乎沒人再去設計其他演算法了。

g^(a×b) ≡ (g^a)^b ≡ (g^b)^a (mod p)
一、甲乙公開協議一個質數p。p作為模數。
  甲乙公開協議一個數字g。
二、甲心中隨便想一個數字a。
  乙心中隨便想一個數字b。
三、甲計算g^a,傳送給乙,乙獲得g^a。
  乙計算g^b,傳送給甲,甲獲得g^b。
四、甲計算(g^b)^a,乙計算(g^a)^b,
  兩人求得共同秘密(g^a)^b。
外人只知道g、g^a、g^b、p,外人無法快速計算(g^a)^b。
想破解,必須求得a,必須計算log(g^a)求得a。(或者是b)
然而log得花很多時間!

遺珠之憾是不能控制共同秘密為何。

當數字很小,餘數次方的時間複雜度是O(log(n)),建立速度極快;餘數對數的時間複雜度是O(sqrt(n)),破解速度也算快。

當數字夠大,餘數對數演算法的記憶體便不敷使用,必須改用試誤法,時間大幅成長為O(n)!利用餘數次方與餘數對數的時間差,讓外人一時無法破解;當外人破解時,秘密早就傳送完畢了!

然而外人只要肯花時間,總有一天還是能破解秘密。實務上的應對方式是資料分段加密、資料分流傳送,讓外人永遠無法追上最新進度,讓外人無法獲得資料全貌。

餘數系統改成finite field、改成elliptic curve

此處的餘數系統,基本單元是整數。我們可以進一步把整數改成餘數多項式、改成橢圓曲線格點,讓對數更難計算、計算更久。

最後講個八卦

演算法作者其實不是這兩人。原作者創造許多傳送秘密的重要觀念,然而太過突發奇想、太過簡潔單純,不被指導教授接受。原作者只好跨校找Hellman協助完成論文、完成學業。後來此演算法變成網路傳輸的重要關鍵,這兩人藉勢得了圖靈獎。

asymmetric encryption🚧

以Diffie–Hellman key exchange得到的共同秘密來加密解密
【目前稱作symmetric-key encryption】

用來加密解密的共同秘密,英文稱作key,中文譯作「金鑰」或「密鑰」。共同秘密宛如鑰匙,開啟得到明文、關閉得到密文。

壹、Diffie–Hellman key exchange:
 一、甲乙公開協議一個質數p。p作為模數。
   甲乙公開協議一個數字g。
 二、甲心中隨便想一個數字a。
   乙心中隨便想一個數字b。
 三、甲計算g^a,傳送給乙,乙獲得g^a。
   乙計算g^b,傳送給甲,甲獲得g^b。
 四、甲計算(g^b)^a,求得共同秘密(g^a)^b = s。
   乙計算(g^a)^b,求得共同秘密(g^a)^b = s。
貳、任意一個加密演算法:
 一、甲利用s加密。
 二、乙利用s解密。

接收端口【目前稱作public-key encryption】

調整步驟順序,引入接收端口的觀念。

壹、乙建立接收端口:
 一、甲乙公開協議一個質數p。p作為模數。 (乙公佈一個質數p)
   甲乙公開協議一個數字g。      (乙公佈一個數字g)
 二、乙心中隨便想一個數字b。      (乙心中隨便想一個數字b)
   乙計算g^b,傳送給甲,甲獲得g^b。  (乙公佈g^b)
貳、甲加密:
 一、甲心中隨便想一個數字a。
   甲計算g^a,傳送給乙,乙獲得g^a。
 二、甲計算(g^b)^a,求得共同秘密(g^b)^a = s。
 三、甲利用s加密。
參、乙解密:
 一、乙計算(g^a)^b,求得共同秘密(g^a)^b = s。
 二、乙利用s解密。

隱藏數字a,英文稱作private key,中文譯作「私鑰」。公開數字g^b,英文稱作public Key,中文譯作「公鑰」。

甲每次加密都可以重新想一個數字a,密文更不容易破解;乙每次解密都可以用同一個數字g^b,密文更容易接收。

人人都知道g^b,人人都可以利用g^b傳送秘密給乙,人人都無法窺伺彼此秘密!

機制類似聯絡地址、聯絡電話。乙提供服務專線0800-092-000,人人皆可撥打專線聯絡乙,人人皆無法獲知其他人的電話內容!

此演算法的特色:人人都能加密,只有乙能解密!

發送端口【目前稱作digital signature】

追加單向函數,引入發送端口的觀念。


甲傳送密文給大家,並且公布解密方式,讓大家都可以解密。資料沒有任何保密效果,但是大家可以確信資料來自同一人。

機制類似產品商標。甲請大家認明三支雨傘標,人人都可以進行檢視,確信產品來自同一人!

此演算法的特色:只有甲能加密,人人都能解密!

傳送秘密現在有了三種模式:一到一、多到一、一到多。

asymmetric encryption演算法

餘數加法

餘數加法有著換字面的功效。對象是小寫英文字母,模數設定成26。對象是位元組,模數設定成2⁸ = 256。

餘數加法、餘數減法(餘數加法反運算),一加一減相互抵銷。我們可以以此設計一個超級簡單的加密演算法:

加密:明文加s成為密文。解密:密文減s成為明文。s是事先約定的秘密。

Caesar cipher

餘數加法。報告完畢。

餘數乘法

餘數乘法有著換字面的功效。乘法是加法來的。

餘數乘法、餘數除法(餘數乘法反運算),一乘一除相互抵銷。我們可以以此設計一個超級簡單的加密演算法:

加密:明文乘以s成為密文。解密:密文乘以s的倒數成為明文。s是事先約定的秘密。

模數必須是質數,才有乘法反運算,才能解密。餘數系統改成finite field、改成elliptic curve,模數就有更多選擇。

ElGamal encryption

餘數乘法。接收端口。

餘數次方

餘數次方有著換字面的功效。次方是乘法來的。

餘數次方、餘數開方(餘數次方反運算),次方開方相互抵消。我們可以以此設計一個超級簡單的加密演算法:

加密:明文的s次方成為密文。解密:密文的s倒數次方成為明文。s是事先約定的秘密。

明文必須是原根,才有次方反運算,才能解密。餘數系統改成finite field、改成elliptic curve,明文就不受限制。

注意到次方值的模數是φ(n),次方值的倒數要用φ(n)來算。

注意到m是明文、n是模數。符號使用方式與數論領域不同。

餘數乘法加密解密:(m×s)×s ≡ m (mod n)     where s×s ≡ 1 (mod n)
餘數次方加密解密:(m^s)^s ≡ m (mod n)     where s×s ≡ 1 (mod φ(n))

RSA encryption

餘數次方。接收端口。

壹、乙建立接收端口:
 一、乙公佈一個質數p。p作為模數。
   乙公佈一個數字g。
 二、乙心中隨便想一個數字b。
   乙公佈g^b。
貳、甲加密:
 一、甲心中隨便想一個數字a。
   甲計算g^a,傳送給乙,乙獲得g^a。
 二、甲計算(g^b)^a,求得共同秘密(g^a)^b = s。
 三、甲有明文m,甲計算m^s,傳送給乙,乙獲得m^s。
參、乙解密:
 一、乙計算(g^a)^b,求得共同秘密(g^a)^b = s。
 二、乙有密文m^s。
   乙計算次方的模數φ(p) = p-1。
   乙計算s的倒數s,模數是φ(p)。
   乙計算(m^s)^s,乙求得明文m。

儘管可以運作,但是一堆次方,看了就煩,乾脆簡化。

壹、乙建立接收端口:
  乙公佈一個質數p。p作為模數。
  乙公佈一個數字a。a作為公鑰。
貳、甲加密:
  甲有明文m。甲計算m^a,傳送給乙,乙獲得m^a。
參、乙解密:
  乙有密文m^a。
  乙計算次方的模數φ(p) = p-1。
  乙計算a的倒數a,模數是φ(p)。
  乙計算(m^a)^a,乙求得明文m。

再把計算倒數的步驟往前挪,預先計算,不必每次重算。

壹、乙建立接收端口:
  乙公佈一個質數p。p作為模數。
  乙公佈一個數字a。a作為公鑰。
  乙計算a的倒數a,模數是φ(p) = p-1。
貳、甲加密:
  甲有明文m。甲計算m^a,傳送給乙,乙獲得m^a。
參、乙解密:
  乙有密文m^a。乙計算(m^a)^a,乙求得明文m。
然而外人知道p、a、m^a,
可以計算φ(p) = p-1,
然後計算a,
然後計算(m^a)^a,求得明文m。

為了不讓外人輕鬆計算a的倒數,把模數從一個質數改成兩個質數相乘,而且不讓外人知道是哪兩個質數。

壹、乙建立接收端口:
 一、乙心中隨便想兩個質數p與q。
   乙計算p×q = n。
   乙公佈一個數字n。n作為模數。
 二、乙心中隨便想一個數字a。
   乙計算a的倒數a,模數是φ(n) = φ(p×q) = (p-1)×(q-1)。
   乙公佈一個數字a。a作為公鑰。(a亦可)
貳、甲加密:
  甲有明文m。甲計算m^a,傳送給乙。
參、乙解密:
  乙有密文m^a。乙計算(m^a)^a,乙求得明文m。
外人只知道n、a、m^a,外人無法快速計算(m^a)^a。
一、想破解,必須得到m,必須計算ᵃ√m^a得到m。
  然而開a次方得花很多時間!
二、想破解,另一種方式是求得a。
  必須計算a的倒數才能求得a,所以必須求得模數φ(n)。
  必須計算(p-1)×(q-1)才能求得φ(n),所以必須求得p與q。
  必須計算n是哪兩個數相乘才能求得p與q。
  然而質因數分解得花很多時間!

餘數倒數、餘數次方,遠小於餘數開方、整數分解的時間複雜度。原理如同Diffie–Hellman key exchange,利用時間差,讓外人一時無法破解。

ICPC 4353

RSA signature

餘數次方。發送端口。

壹、甲建立發送端口:
 一、甲心中隨便想兩個質數p與q。
   甲計算p×q = n,n作為模數。
   甲公佈一個數字n。n作為模數。
 二、甲心中隨便想一個數字a。
   甲計算a的倒數a,模數是φ(n) = φ(p×q) = (p-1)×(q-1)。
   甲公佈一個數字aa作為公鑰。
貳、甲加密:
  甲有明文m。甲計算m^a,傳送給乙,乙獲得m^a。
參、乙解密:
  乙有密文m^a。乙計算(m^a)^a,乙求得明文m。

最後講個八卦

這三位作者跑去申請專利,開了一間公司叫做RSA security。然後美國政府將演算法實作列為軍事管制商品,禁止出口,詳情請見crypto wars與pretty good privacy。然後美國政府兜售自製晶片、埋入監聽系統,該公司登高一呼、挺身對抗,詳情請見clipper chip。然後三位作者藉勢得了圖靈獎。然後媒體爆料該公司被美國政府買通,使用美國政府設計的、藏有後門的演算法,讓美國政府可以破解秘密、監聽訊息,詳情請見RSA backdoor。然後其中一位作者被美國政府拒發入境簽證,理由不明。貴圈真亂。

certification

man-in-the-middle attack

「中間人攻擊」。傳送秘密時,他人佯裝接收對象。得進一步推廣為雙向版本,他人兩面討好、居中斡旋。

勞保黃牛、信用卡客服詐騙、社交工程等等都是中間人攻擊。

中間人攻擊的精髓:接洽對象全是壞人。假的檢察官、假的行員、假的電話號碼、假的法規。極端案例是《楚門的世界》。

中間人攻擊是必勝攻擊手法,所有的加密演算法一律失效!

一種破解方式是確認對象身分。不幸的是,電腦世界當中,訊息在網路上傳輸,可以隨時攔截;而且無法見到對方。

一種破解方式是測量溝通時間。不幸的是,電腦世界當中,訊息在電腦中處理,計算速度飛快,難以察覺差異。

最後大家只好依賴「認證」。

certification

「認證」。傳送秘密前,預先諮詢他人,確認接收對象的身分;或者請對方出具他人頒發的良民證。得進一步推廣為雙向版本,他人列席旁聽、居中調解。

見證人、身分證、印鑑證明、合格標章等等都是認證。

認證的精髓:接洽對象全是好人。由第三方公正人士親自驗明正身,頒發證書,昭告天下。極端案例是「好人好事代表」。

「中間人攻擊」和「認證」皆運用了第三者的概念,本質相同、卻又相對,正所謂陰陽相生相剋。第三者可以為善、可以為惡。

password

confidentiality

一份資料,只給自己人知道,不給外人知道。

如何確認是自己人?

password

「通行碼」。中文習慣稱作「密碼」,翻譯不太準確。

通行碼的機制很簡單。雙方事先約定關鍵字,一方說出關鍵字,另一方驗證關鍵字。例如《阿里巴巴和四十大盜》的芝麻開門、《魔戒》《指环王》的mellon。

通行碼通常不需要加密。大家習慣背記抄寫明文、而非密文。

通行碼通常需要保密。主要是為了避免他人冒用身分為非作歹。也可以不保密,與他人分享。

password保密版本

事先做最好的準備、最壞的打算。使用者必須防止外人得知通行碼,管理者必須預設外人入侵伺服器、盜取通行碼。

一、設計通行碼。讓通行碼毫無規律、難以聯想。例如不要使用生日。甚至以亂數演算法決定通行碼。令外人難以猜中。

二、傳送通行碼。使用者加密通行碼,傳送密文,管理者解密通行碼。令外人無法窺視。

三、保存通行碼。管理者加密通行碼,儲存密文。只有管理者知道密鑰。即便外人盜取通行碼密文,也不知道如何解密。

四、驗證通行碼。甲、收到的通行碼實施加密、伺服器的通行碼密文,比對兩者;乙、收到的通行碼、伺服器的通行碼密文實施解密,比對兩者。大家傾向採用甲,只需加密,不需解密。令外人無法盜取解密程式、無法解密通行碼密文。

保護通行碼:cryptographic hash function

管理者儲存通行碼密文,理應使用一對一函數,然而大家習慣採用多對一函數。

一對一函數,不同的通行碼,對應不同的通行碼密文。優點是避免外人亂敲亂打通行碼,碰巧通行碼密文一樣,導致驗證通過。

多對一函數,有些不同的通行碼,碰巧通行碼密文一樣。優點是即使外人竊取通行碼密文,也無法從反向推導通行碼,可能性太多。

製作通行碼密文的密碼學雜湊函數有bcrypt、PBKDF2、scrypt、Argon2。

signature

authentication

一份資料,作者身分為真,未經他人冒名頂替。

如何確認資料是否為他人偽作?

signature

「簽名」。創立獨門絕技,只有本人能達成,避免冒名頂替。

integrity

一份資料,資料內容為真,未經他人竄改造假。

如何確認資料未經竄改?

digest

「摘要」。增加檢查項目,確認是否相符,避免竄改造假。

大家把簽名與摘要混為一談,使用相同的演算法。

digest私藏版本

首先利用編碼演算法製作摘要!

避免他人只竄改本文、只竄改摘要:相同本文得到相同摘要,不同本文得到不同摘要;從本文到摘要是一對一函數。

壹、製作摘要:
 一、甲心中隨便想一個編碼演算法。
 二、甲編碼本文,得到摘要。
貳、檢查摘要:
 一、甲編碼本文,得到新摘要。
 二、甲比對舊摘要、新摘要。
   若一致,本文未竄改。
   若不一致,本文已竄改。

接著利用加密演算法掩飾摘要!

避免他人同時竄改本文和摘要:加密本文、或者加密摘要、或者兩者皆加密。一般僅加密摘要,節省時間。

壹、製作摘要:
 一、甲心中隨便想一個編碼演算法。
 二、甲編碼本文,得到摘要。
 三、甲心中隨便想一個加密演算法。(以及密鑰)
 四、甲加密摘要,得到摘要密文。
貳、檢查摘要:
 一、甲編碼本文,得到新摘要。
 二、甲加密新摘要,得到新摘要密文。
 三、甲比對舊摘要密文、新摘要密文。
   若一致,本文未竄改。
   若不一致,本文已竄改。

第二三步可以改成:甲解密舊摘要密文,然後改為比對舊摘要、新摘要。

此方式僅適用單人。一旦他人知道密鑰,那麼他人就可以解密、竄改、重新加密,令偽本文、偽摘要兩相符合。

digest公開版本

繼續利用非對稱式加密來製作摘要!

避免他人只竄改本文、只竄改摘要:只允許本人製作摘要!如此一來,他人擅自改動本文,也無法重製摘要;他人擅自改動摘要,也無法與本文的編碼結果相符。

一種實踐方式是非對稱式加密:只有本人知道如何加密,他人不知道如何加密。

壹、製作摘要:
 一、甲公佈一個編碼演算法。
 二、甲編碼本文,得到摘要。
 三、甲公佈一個非對稱式加密演算法。(只有甲知道如何加密,他人不知。)
 四、甲加密摘要,得到摘要密文。
 五、本文、摘要密文一併傳送給他人。
貳、檢查摘要:
 一、他人編碼本文,得到摘要。
 二、他人解密摘要密文,得到摘要。
 三、他人比對兩份摘要。
   若一致,本文未竄改。
   若不一致,本文已竄改。

避免他人同時竄改本文和摘要:找公證人登記摘要密文,先登記先贏。再由公證人宣布解密方式。

壹、製作摘要:
 一、甲公佈一個編碼演算法。
 二、甲編碼本文,得到摘要。
 三、甲心想一個非對稱式加密演算法。(只有甲知道如何加密,他人不知。)
 四、甲加密摘要,得到摘要密文。
 五、甲洽詢公證人,登記㊣摘要密文、㊣解密方式。
 六、本文、摘要密文一併傳送給他人。
貳、檢查摘要:
 一、他人編碼本文,得到摘要。
 二、他人洽詢公證人,搜尋摘要密文,得到㊣解密方式。
 三、他人解密摘要密文,得到摘要。
 四、他人比對兩份摘要。
   若一致,本文未竄改。
   若不一致,本文已竄改。

不幸的是,如果公證人變成海邊的消波塊、山上的堆肥桶,就無法確認本文是否被竄改了。

因而又衍生許多攻防技術,例如台灣的白色恐怖時期、《進撃の巨人》的雷斯家族、《ONE PIECE》的歷史本文。這已經超出加密演算法的範圍,就此打住。

縮短摘要長度:cryptographic hash function

縮短摘要長度,可以節省時間與空間!

製作摘要理應使用一對一函數。摘要盡量短,又滿足一對一函數,其極限是壓縮演算法!如果摘要更短,便無法滿足一對一函數,而形成多對一函數。有失有得。

衍生的副作用:一、不同的明文得到一樣的密文;二、外人難以從密文猜中原文。

製作摘要的演算法有ECDSA、EdDSA。

password vs. signature

通行碼、簽名,兩者都是驗證身分的機制。

通行碼,多傳一,對稱式加密。

簽名,一傳多,非對稱式加密。

兩者都使用了密碼學雜湊函數,製造通行碼密文、縮短簽名。