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先生:「我也知道了。」

請問:這張牌是什麼牌?

DES Encryption

Caesar Cipher

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

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

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

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

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

ENIGMA

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

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

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

Feistel Cipher

電腦草創時期的演算法。

一、以位元為基本單元。區塊長度是64位元。二、利用xor的特性,解密不需反函數。三、引入多回合的觀念。

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

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

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

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

DES

現代的演算法。Feistel Cipher的加強版。

加密的詳細架構如下:

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

F的構造如下:

S的構造如下:

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

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

網路卡已經內建DES的電路,其實沒有必要用程式語言實作。

由於電腦性能不斷上升,DES越來越容易破解,近年又推廣成Triple DES:約定三個秘密數值,連做三次DES,加密解密加密。

Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange

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

先前介紹的演算法,你我必須事先私下見面約定秘密數值。然而在電腦世界當中,你我無法事先私下見面。於是有人想出在公開場合建立秘密數值的演算法。因為非常簡潔好用,似乎也沒人去設計其他演算法了。

(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(logN),建立速度極快;餘數對數的時間複雜度為O(sqrtN),破解速度也極快。

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

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

餘數系統改成Finite Field、改成Elliptic Curve

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

以Diffie-Hellman Key Exchange得到的共同秘密來加密解密

所有的加密演算法,例如Caesar Cipher、ENIGMA、Feistel Cipher、DES,全部都可以透過Diffie-Hellman Key Exchange獲得共同秘密。

壹、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解密。

接收窗口

進一步仔細調整步驟順序,引入接收窗口的觀念。

壹、乙建立接收窗口:
 一、甲乙公開協議一個質數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,密文更不容易破解;乙每次解密都可以用同一個數字b,密文更容易接收。

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

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

根據上個段落、這個段落,傳輸秘密現在有了兩種模式:一到一、多到一。

另外還可以引入分發窗口的概念。由於不實用,大家不討論。

RSA Encryption

加密演算法:餘數加法

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

設定模數為26

[+1 table]       [+2 table]       [+3 table]
0 1 2 3 ... 25   0 1 2 3 ... 25   0 1 2 3 ... 25
1 2 3 4 ...  0   2 3 4 5 ... 1    3 4 5 6 ...  2

Caesar Cipher

餘數加法。報告完畢。

加密演算法:餘數乘法

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

模數最好設定為質數,讓各種乘數的表格,都是一對一函數,比較好處理。模數不見得要剛好是26、256,可以設定成更大的模數,尤其是質數;表格過大,仍可運作,密文比明文長罷了。

設定模數為37

[×1 table]       [×2 table]       [×3 table]
0 1 2 3 ... 36   0 1 2 3 ... 36   0 1 2 3 ... 36
0 1 2 3 ... 36   0 2 4 6 ... 35   0 3 6 9 ... 34

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

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

一、甲乙事先私下約定一個質數p。p做為模數。p也是區塊長度。
  甲乙事先私下約定一個數字a。
二、甲加密:
  甲有明文m。甲計算m×a,傳送給乙,乙獲得m×a。
三、乙解密:
  乙獲得密文m×a。
  乙計算a的倒數a。
  乙計算(m×a)×a,乙求得明文m。
 (乙計算(m×a)÷a。)

ElGamal Encryption

傳輸模式是多到一、加密演算法是餘數乘法。

加密演算法:餘數次方

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

我們可以利用餘數次方、餘數次方反運算(餘數根號),次方根號相互抵消,設計一個超級簡單的加密演算法。然而餘數次方反運算(餘數根號)要算很久。由於已經知道次方數值,所以可以直接求次方數值的倒數,避開餘數根號。

餘數乘法版本:
m×1 ≡ m (mod n)
m×(a×a) ≡ m (mod n)   // a×a ≡ 1 (mod n)
(m×a)×a ≡ m (mod n)

餘數次方版本:
m^1 ≡ m (mod n)
m^(a×a) ≡ m (mod n)   // a×a ≡ 1 (mod φ(n))
(m^a)^a ≡ m (mod n)

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

一、甲乙事先私下約定一個數字p。p做為模數。
  甲乙事先私下約定一個數字a。
二、甲加密:
  甲有明文m。甲計算m^a,傳送給乙,乙獲得m^a。
三、乙解密:
  乙獲得密文m^a。
  乙計算次方的模數φ(p) = p-1。
  乙計算a的倒數a,模數是φ(p)。
  乙計算(m^a)^a,乙求得明文m。

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。
貳、甲加密:
  甲有明文m。甲計算m^a,傳送給乙,乙獲得m^a。
參、乙解密:
  乙獲得密文m^a。
  乙計算次方的模數φ(p) = p-1。
  乙計算a的倒數a,模數是φ(p)。
  乙計算(m^a)^a,乙求得明文m。

然而外人知道m^a、a、n、p,
可以計算φ(p) = p-1,
然後計算a,
然後計算(m^a)^a,求得明文m。

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

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

外人只知道m^a、a、n,外人無法快速計算(m^a)^a。
一、想破解,必須得到m,必須計算am^a得到m。
  然而開a次根號得花很多時間!
二、想破解,另一種方式是求得a。
  必須計算a的倒數才能求得a,所以必須求得模數φ(n)。
  必須計算(p-1)×(q-1)才能求得φ(n),所以必須求得p與q。
  必須計算n是哪兩個數相乘才能求得p與q。
  然而質因數分解得花很多時間!

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

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

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

讀者可以想一想:

一、乙可以只記a與n,不記p q a φ(n)。為什麼可以呢?

二、如果p和q其中一個很小,有什麼問題呢?

三、如果由甲來公佈n與a,再由甲傳送秘密給乙,有什麼問題呢?

最後講個八卦。這三位作者跑去申請專利;然後開了一間名叫RSA的公司,變成該領域的業界龍頭;然後提倡大家都使用此演算法;然後藉勢得了圖靈獎;然後公司被美國政府買通,在演算法裡面藏後門,讓美國政府可以破解秘密,監聽全世界的秘密訊息。

ICPC 4353

RSA Signature Algorithm(RSA Asymmetric Encryption)

傳輸模式是一到多、加密演算法是餘數次方。

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

甲公佈n與a,再由甲傳送秘密給大家,大家都可以解密。基本上沒有任何加密效果。非常蠢。

然而此演算法有一個非常重要的特色:只有甲能加密!

此特色稱作「非對稱式加密asymmetric encryption」。資訊不對稱,甲知道的比乙多,甲有獨門絕技!這個特性可以運用於稍後提到的Digest和Signature。

加密演算法:餘數乘法

順帶一提,餘數乘法其實也有著換位置的功效。一種乘數,就是一種重新排列。模數則是區塊長度。

設定模數為7

[×1 table]        [×2 table]        [×3 table]
0 1 2 3 4 5 6     0 1 2 3 4 5 6     0 1 2 3 4 5 6
0 1 2 3 4 5 6     0 2 4 6 1 3 5     0 3 6 2 5 1 4

[×4 table]        [×5 table]        [×6 table]
0 1 2 3 4 5 6     0 1 2 3 4 5 6     0 1 2 3 4 5 6
0 4 1 5 2 6 3     0 4 1 5 2 6 3     0 4 1 5 2 6 3

模數設定為質數,比較好處理。但是區塊長度是質數,而不是32、64,挺彆扭。餘數系統可改成Finite Field、改成Elliptic Curve。如此一來,模數不必是質數,可以改成32、64。

Man-in-the-middle Attack

Man-in-the-middle Attack

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

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

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

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

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

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

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

Certification

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

見證人、律師、身分證、識別證、印鑑證明等等都是認證。

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

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

Digest

Integrity

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

如何確認資料未經竄改?

Digest私藏版本

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

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

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

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

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

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

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

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

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

Digest公開版本

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

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

一種實踐方式是非對稱式加密:只有本人知道如何加密,他人不知道如何加密。經典演算法是RSA Signature Algorithm、Digital Signature Algorithm,此處省略。

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

接著利用公證人來擔保摘要!

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

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

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

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

縮短摘要長度:One-way Hash Encryption

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

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

製作摘要理應使用一對一函數,然而大家習慣採用多對一函數,例如One-way Hash Encryption。

Signature

Authentication

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

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

Signature

「簽名」。大家把簽名與摘要混為一談,沿用摘要的演算法。

Password

Confidentiality

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

如何確認是自己人?

Password

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

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

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

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

Password保密版本

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

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

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

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

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

保護通行碼:One-way Hash Encryption

管理者儲存通行碼密文,理應使用一對一函數,然而大家習慣採用多對一函數,例如One-way Hash Encryption。

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

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

Password v.s. Signature

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

通行碼,傳輸模式是多到一,採對稱式加密。

簽名,傳輸模式是一到多,採非對稱式加密。

兩者都使用單向式加密來製造通行碼密文、簽名。

延伸閱讀:One-time Password

https://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm

One-way Hash Encryption

背景知識:One-to-One Function / Many-to-One Function

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

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

多對一函數的知名範例是整數乘法、整數分解(質因數分解)。

f(a,b) = ab = c
ab = 1×12 2×6 3×4 4×3 6×2 12×1 都得到 c = 12

多對一函數讓人無法以輸出判斷輸入。

通行碼是a和b,
管理者儲存通行碼,存為a*b。
即便外人盜取a*b,外人也難以猜出通行碼。

背景知識:Hash Function

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

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

背景知識:One-way Function

f(x) = y,已知x欲求y很簡單、算得快,已知y欲求x很困難、算得久,這樣的f稱做「單向函數」。

知名範例是整數乘法、整數分解(質因數分解)。

f(a,b) = ab = c
已知整數a b欲求整數c,整數相乘。時間複雜度為一次乘法的時間。
已知整數c欲求整數a b,整數分解。採用試除法,時間複雜度為c次除法的時間。

知名範例是次方、開根號。

f(a) = a^k = b   k是常數
已知a欲求b,次方運算。時間複雜度約是logk次乘法的時間。
已知b欲求a,開根號運算。採用二分法,時間複雜度約是logb*logk次乘法的時間。

Encryption

「加密」。明文變成密文。

從一個東西變成另一個東西,概念等同於數學術語「函數」。我們可以把加密看作是一種特殊的函數。

「加密」。明文變成密文。

什麼是優秀的加密、差勁的加密呢?加密的關鍵究竟是什麼呢?

加密是避免外人從密文猜出明文,有時候也要避免外人看穿明文如何變成密文。從這個想法出發,可以發現加密的原理:

一、明文與密文相差極大。
二、明文稍微改動,密文劇烈變動。
三、密文稍微改動,明文劇烈變動。

One-way Encryption

「單向式加密」。

四、只有加密,沒有解密。或者難以解密、解密代價極大。

注意到「單向式加密」和「非對稱式加密」不一樣!「非對稱式加密」是一方知道如何加密與解密、另一方只知道如何解密。

One-way Hash Encryption

「單向雜湊加密」。用於縮短、固定密文長度。

五、限制函數輸出範圍。(間接導致一對一函數變成多對一函數。)

我們習慣把密文縮得很短,間接導致一對一函數變成多對一函數。其衍生的副作用:一、不同的明文得到一樣的密文;二、外人難以從密文猜中原文。有失有得。

經典演算法是MD5、SHA-3。此處省略。