the code book

RSA 所使用的數學

  • Quote

此文節錄《碼書:編碼與解碼的戰爭》的附錄

此書提供了許多簡單易懂的技術描繪(可惜台灣沒有再版了)


如下是 RSA 加密與解密過程的數學描述:

一、愛麗絲挑選兩個巨大的質數 pq。這兩個質數應該要非常龐大,不過,為了簡化說明,我們假設愛麗絲所挑選的是 p=17,q=11。這兩個數字必須保存好,不讓任何人知道。

二、愛麗絲把這兩個質數相乘,得到另一個數字 N。在此例,N=187。她又再挑一個數字 e,假設 e=7,數字 e 和數字 (p-1)×(q-1)必須互質,也就是說,它們不可以有共同的因數

三、愛麗絲公佈 e 和 N,這兩個數字一起,被稱為公開鑰匙(所選取的 e 值可以跟其他人的一樣,但 N 值必須是獨一無二的)

四、加密訊息時,必須先把訊息轉換成一個數字 M。例如,文字被轉換成 ASCII 二進位數字時,我們可以把這些二進位想成一個十進位數字。接著根據如下的公式,就可以把 M 加密成密碼文 C

五、假設巴伯想送愛麗絲一個吻,就單單一個字母 X。X 的 ASCII 碼是 1011000,換算成十進位數字是 88,因此 M=88

六、巴伯查詢愛麗絲的公開鑰匙,發現 N=187, e=7。這兩個數字等於提供了他加密訊息給愛麗絲所需的公式。套入公式:

用電子計算機運算這個式子反而費事,因為它的顯示版容不下這麼大的數字。事實上,模算術的指數函數有一個計算訣竅:

巴伯把密碼文 C=11 寄送給愛麗絲

七、我們知道模算術裡的指數函數是單向函數,要從 C=11 逆向求出原始訊息 M 是非常困難的事。所以,依芙沒有辦法解譯這則訊息。

八、愛麗絲可以解譯這則訊息,因為她有特別的資訊:她知道 p 和 q 的值。她會利用下面的公式計算出一個 d 值,即她的私人鑰匙:

d 值的演算並非輕而易舉的工作,不過一種稱為歐基里德演算法的技巧可以幫愛麗絲又快又簡單地求出 d 值

九、愛麗絲利用下面的公式解譯訊息:


瑞維斯特、薛米爾和艾多曼創造了一個特殊的單向函數,只有持有特別資訊(p 和 q)的人才能求回原值。每個人都挑選不一樣的 p 和 q,等於把這個函數個人化,任何人都可以用 N 值加密訊息,但只有知道 d 值的人可以解密訊息

碼書:編碼與解碼的戰爭

  • Quote

鑰匙的重要性遠高於演算法,這就是密碼學上顛撲不破的真理……密碼系統的安全性不在於防止敵人洞悉密碼演算法,鑰匙的保密才是決定密碼安全性的唯一關鍵

每種密碼法都可視為一種演算法(algorithm)——再加上一把鑰匙(key)的組合結果。鑰匙是用來指定特定加密程序的演算細節

(替代法的)鑰匙的定義可以更簡單,制定密碼字母集時,發信人可以選用一個鑰匙字(keyword)/鑰匙片語(keyphrase),而不必將全部的字母隨機重排……例如,選用 JULIUSCAESAR 當鑰匙片語,再以這些字母當密碼字母集的起始字母,接著,把字母集的其他字母,依照原有順序,接到鑰匙片語的後面,就能造出密碼字母集

舊約聖經含有一些蓄意的、明顯的密碼應用例子,讓中世紀的修士深深著迷。例如,舊約聖經就有幾段以「atbash 法」加密的文字。Atbash 是一種傳統的希伯來文替代式密碼法:要替換字母時,先記下他在字母集的順序編號,再取從字母及後頭倒數過來順序相同的字母取代。以英文為例,第一個字母 a,就以最後一個字母 Z 來代替。事實上,atbash 這個字就暗示了它所描述的替代法。它包含希伯來文字母的 aleph,跟著的是最後一個字母 taw,再來是第二個字母 beth,最後是倒數第二個字母 shin

……簡易的方法來增強單套字母替代法的安全性,其中一種方法是引進「虛元」(nulls),亦即不代表任何字母,像空格一樣不具任何意義的字母或符號。例如我們可以在 1 到 99 之間任選 26 個數字來替代明文字母,剩餘 73 個不代表任何字母的數字,則以不同的頻率隨意散至在密碼文之間……這些虛元會干擾頻率分析法的應用

另一個扶助岌岌可危的單套字母替代法的辦法是使用代碼字 (codewords)。code 這個字在日常語言有非常廣泛的含義,常被用來描述任何祕密通訊方法……它其實有特定的意義,專指某種形式的替代法……讓整個單字改由另一個單字或符號替代

在技術上,代碼法 (code) 指的是單字或片語層面的替代法;密碼法 (cipher) 指的是字母層面的替代法。因此,密碼加密 (encipher) 指的是用密碼法改寫訊息;代碼加密(encode)則是用代碼法改寫訊息。同理,解譯密碼 (decipher) 是還原以密碼法加密的訊息,解譯代碼 (decode) 則是還原以代碼法加密的訊息

……仔細檢視代碼法,我們會發現它有兩大缺點,不如密碼法實用……要達到同樣的彈性,得先定義數千個可能會用到的明文單字代碼。這樣一本代碼簿恐怕會有好幾百頁……(攜帶不易)……再者,代碼簿被敵人俘獲的後果會非常悽慘,發信人和收信人必須再度重新編撰一本全新的代碼簿

Read More »碼書:編碼與解碼的戰爭