信息安全基礎之密碼技術(對稱、非對稱密碼等應用)

歷史上的加密技術

在過去沒有通信設備的時代,兩軍交戰傳達命令靠的是書信,萬一下達的指令被地方截取,那就糟糕了。

相傳過去在羅馬時代,凱撒曾經使用「凱撒密碼」來將書寫內容加密。

凱撒密碼(Caesar cipher)

通過將明文中的字母按照字母表向左或向右移動一個固定數目位置的偏移以後產出密文,而通過反向操作來解密。

假設我們今天約定好偏移量為向右3格。

那麼我們的明文「ATTACK」通過規則加密後就會得到「DWWDFN」。

然而如果敵方軍隊知道了我們的加密方式,就只需要每一種偏移量都去嘗試就有可能破解這個密碼。

舉例:嘗試將密文「DWWDFN」解密。

  • 向左偏移量0 – DWWDFN
  • 向左偏移量1 – CVVCEM
  • 向左偏移量2 – BUUBDL
  • 向左偏移量3 – ATTACK
  • 向左偏移量4 – ZSSZBJ
  • 向左偏移量5 – YRRYAK
  • ….

像這樣不停地去嘗試不一樣的偏移量,運氣最差偏移第25次就會得到原文,
而這樣的破解方式我們稱為「暴力破解法」又或者「窮舉破解法」。

可以想像,如果今天銀行密碼規定只能用4位數的數字當作密碼(舊版的iOS系統就是只能輸入4位數字當密碼),這樣我們只要從0000窮舉到9999,總會成功破解的。

如同上面破解凱撒密碼的過程,有些企業會這樣覺得『自行開發一套加密算法,這樣就能保證加密不被破解』,
而這樣的想法是錯誤的,我們稱這為隱蔽式安全性(security by obscurity),當寫好加密算法的員工離職又或者該加密算法外洩的時候,這一套加密算法就完全沒有意義了。

簡單替換密碼(simple substitution cipher)

簡單替換密碼的加密過程是依次將明文中的每一個字母按照「替換表」替換成另一個字母,上面提到的「凱撒密碼」也可以說是簡單替換密碼的一種。

舉一個例子,我們這裡準備一張替換表:

根據替換表,我們可以將明文「DEVELOPER」加密成「RHEHXKUHN」

到這裡為止,不論是使用「凱撒密碼」又或者是「簡單替換密碼」我們並不知道哪一種更好破解。

然而,「凱撒密碼」可以用「暴力破解」來破譯,但「簡單替換密碼」很難通過「暴力破解」來破譯,這是因為簡單密碼中可以使用到的密鑰數量更多。
而一種密碼可以使用的「所有密鑰的集合」,我們稱為「密鑰空間(key space)」。

比如在簡單替換密碼中,明文字母A可以對應到A B C D…任何一個,B可以對應到A以外的B C D…以此類推可以計算出密鑰總數:

26 x 25 x 24 x 23 x …… x 1 = 403,291,461,126,605,000,000,000,000

這密鑰空間大使用電腦來暴力破解找到密鑰也需要非常久的時間。

假設我們獲得了一份密文

PS: 原文為大寫英文並且沒有空格

JVHLOOLMRJVHYKPVLECMFHMJHNHRCMJKLULNJMHNOVCUJKFHJVHNZHMJKGJCMJKJ
VHYKNHOJJKVGMJJVHQVLRMKJUNKSHHRHRYLNZVHMJVHQIHJLXCKMJVHYKPLUUNKLS
VHRJVHXCKMLMRUNKICOHRJKSKMJNCEHYKNVCIJVHSLUJGNHKYJVHLOOCYVHZKGXRU
XHRFHVCOZKNRJVLJVCOKZMXCYHOVKGXRBHOULNHRKMVCOLOOGNCMFVCIJVLJVHZK
GXRMKJCMDGNHVCIJVHYKPXHRJVHLOOJKLRHHUUCJLMRSKMJNCEHRJVLJVHOVKGXRY
LXXCMJKCJJVHXCKMOHHCMFJVLJJVHLOOZLOOHSGNHRCIIHRCLJHXQSXGJSVHRJVHYK
PLMRJVHMLJJLSWHRJVHLOOLJVCOXHCOGNH

我們知道要利用窮舉法來破解很困難,於是我們開始看這個密文有什麼特點。

我們對密文中字母出現的次數做了分析:

而正好也有人根據古典著作有做過字母頻率的計算(詞頻)的計算。

詞頻排序:e, t, a, o, i, n, s, h, r, d, l, u, c, m, f, w, g, y, p, b, v, k, j, q, z

我們已經知道詞頻最高的字母是「e」,而密文中出現最多次數的是「H」和「J」,我們先將「H」替換成「e」試試看。

然後我們知道英文中出現最多的單詞是「The」,我們將以「e」結尾的三個字母單詞看作是「The」,
而我們發現開頭就有「JVe」,因此「JVe」很有可能就是「The」。

  • 我們將「J」換成「t」、「V」換成「h」,然後我們發現有個詞「thLtthe」。

我們將這個詞拆成「thLt」、「the」之後,我們覺得這其中的「thLt」就是「that」。

  • 於是將L都替換成了a。

接著我們發現了「theQhaRM…」、「theQletaXCKM…」,我們覺得「theQ」可能是「they」

  • 於是將「Q」換成「y」。

我們把已經知道的單詞標示一下,文章開頭有個「theaOO」結尾有個「theaOOathCO」,而文章多處有「hCO」的組合。

我們知道猜測aOO是個名詞,但不知道是什麼,但我們知道文章中可能會出現很多my her his their之類的單詞,我們人為hCO是his的可能性很高。

  • 於是將「C」替換成「i」,「O」替換成「s」。

我們看到開頭變成了「theassaMRthe」,加上空格後「the ass aMR the」,我們看到文後也有「aMRthe」的組合,我覺得「aMR」很可能是「and」。

  • 於是將「M」換成「n」,將「R」換成「d」。

文中多處出現的「YKP」看起來是個名詞,而有一段內容是這樣的「theYKPXedtheasstKadeeUUitand」加入空格後「the YKP Xed the ass tKadeeUUit and」

我們認為「Xed」有可能是「Led」,後面的「tK」很可能就是「to」。

  • 所以我們將「X」轉成「l」,將「K」轉成「o」。

文章最後一句話,加入空格後有「and then attaSWed the ass at his leisGNe」,
我們覺得「attaSWed」可能就是「attacked」,而「leisGNe」,可能就是「leisure」。

  • 於是將「S」換成「c」,將「W」換成「k」,將「G」換成「u」,將「N」換成「r」。

還剩下Y、P、E、F、Z、D要破譯(有點累,這個過程很像是在玩Sudaku或者英文填詞遊戲)

  • 我們看到「Zould」,可能是「Should」或者「Would」,前面已經發現O才是對應s,於是我們將「Z」改為「w」。
  • 開頭中有個「UartnershiU」,應該是「Partnership」,於是我們將「U」轉成「p」。
  • 而「toFether」應該是「together」,於是將「F」轉成「g」。
  • 「HiI」中的大寫「I」明顯是「m」,於是將「I」換成了「m」。
  • 這句「wentoutintotheYorest」加入空格「went out into the Yorest」,其中的「Y」應該是「f」。
  • 文中多次出現的「foP」及「theQ」應該就是「fox」和「they」,所以「P」就是「x」、「Q」就是「y」。
  • 「hisownlifeshouldBespared」加入空格「his own life should Be spared」,我們知道「B 」就是「b」。
  • 最後我們發現兩處有「contriEe」,開頭有「haEing」這個「E」就是「v」了。

最後我們得到了明文:

我們得到的簡單密碼交換規則:

  • 密文:H、J、V、L、C、O、M、R、X、K、S、W、G、N、Z、U、F、Y、P、Q、B、E、I、D
  • 原文:e 、t、h、a、 i、 s、 n、 d、 l、 o、c、 k、 u、 r、w、p、g、 f、 x、y、 b、v、m、j

而這篇原文其實是來自「伊索寓言」裡面的驢子、狐狸與獅子(The Ass, the Fox, and the Lion)

The Ass and the Fox, having entered into a partnership together, went out into the forest to hunt.

They had not proceeded far, when they met a Lion.

The Fox approached the Lion and promised to contrive for him the capture of the Ass, if he would pledge his word that his own life should be spared.

On his assuring him that he would not injure him, the Fox led the Ass to a deep pit, and contrived that he should fall into it.

The Lion, seeing that the Ass was secured, immediately clutched the Fox, and then attacked the Ass at his leisure.

我們使用的是被稱為頻率分析的密碼破譯方法,適合拿來破解簡單替換密碼。

  • 除了高頻字母以外,低頻字母也可以拿來利用。
  • 密文越長線索越多。
  • 同一個字母連續的出現也是不錯的線索。
  • 當解開了一些字母以後,開始出現一些單詞,加上前後文會有更多線索。

密碼算法

用於解決複雜問題的步驟,我們稱為「算法(Algorithm)」。把明文加密成密文的步驟,我們稱為「加密算法」。
而解密的步驟我們稱為「解密算法」,這兩個算法我們合在一起稱為「密碼算法」。

而密碼算法中,我們會使用到「密鑰(key)」,就像現實生活中用鑰匙開鎖一樣。


對稱密碼(Symmetric Cryptography) – 用相同的密鑰進行加密和解密

當密鑰同時使用在加密和解密時,我們稱這個密鑰為「對稱密碼(Symmetric Cryptography)」。

常見的有:

  • DES(Data Encryption Standard) –  目前 DES 已經能夠被暴力破解,所以不建議使用了。
  • 3DES(Triple Data Encryption Standard)- 由 IBM 提出,為了加強 DES。
  • AES(Advanced Encryption Standard)- 取代 DES 稱為新的標準,採用的是 Rijndael 的對稱密碼算法。

密鑰配送問題(key distribution problem)

在通信過程中,假設 A 要傳送一封 email 給 B,這封email含有商業機密,所以A將email通過密鑰加密後傳送給了B。

這時候即使 C 從中拿到了 email 的內容,也會因為沒有密鑰而無法解鎖。

然而 B 拿到 email 後也需要密鑰才能夠進行解鎖,但如果 A 將密鑰發送給 B,這個密鑰可能會被 C 拿到,
這樣連 C 也可以對內容進行解鎖了。

於是有人為了解決這個問題發明了公鑰密碼(Public-key cryptography)


公鑰密碼(Public-key Cryptography)

A 發送 email 給 B 的過程中我們發現:

  • A 需要加密用的密鑰 email
  • B 需要解密用的密鑰 email
  • 不能讓 C 獲得解密的密鑰
  • C 拿到加密密鑰沒關係

於是用來解決「密鑰配送問題」的「公鑰密碼」,將密鑰分成了「加密密鑰」和「解密密鑰」,只有持有「解密密碼」的人才能對通過「加密密碼」的內容進行解密。

而根據密鑰的保管情況,我們將公開的密鑰稱為「公鑰(public key)」,而只有自己擁有的密鑰稱為「私鑰(private key)」。
所以這裡的公鑰就充當了『加密』的功能呢,而私鑰就承擔了『解密』的功能。

有了公鑰密碼的概念,A、B 在互相發送email之前,
就可以先自行產生一對『公鑰』和『私鑰』,也就是『密鑰對(key pair)』,
A、B將自己的「公鑰」發送給對方,即使C竊取了也沒有用途,因為「公鑰」無法解密密文。

  • 公鑰:一把可以散播出去給大家的鑰匙。
  • 私鑰:一把留給自己的鑰匙。

A通過「公鑰B」來加密email的內容並發送給B,這個過程即使C拿到了「加密過的email」也會因為沒有B的私鑰而無法解密。

RSA加密

RSA是一種應用最廣泛的公鑰密碼算法,在RSA中,明文、密鑰、密文都是數字組成。

RSA的加密、解密公式:

  • E和N是加密的密鑰,也就是說E和N的組合是RSA的公鑰。
  • D和N是解密的密鑰,也就是說D和N的組合是RSA的密鑰。

我們可以寫成「公鑰(E,N)、密鑰(D,N)」,其中E是Encryption,N是Number,D是Decryption。

其中的E、D、N的產生方式可以參考wiki

中間人攻擊(Man in the middle attack)

雖然有了公鑰密碼來加密明文,但其實遞交公鑰的過程會有一個風險:

這裡將文字畫成圖解釋看看,從右上方的B開始:

  • A和B準備開始通信,首先他們將自己的公鑰發給對方。
  • C截取了「公鑰A」和「公鑰B」,並且自己保留一份。
  • C將自己的「公鑰C」分別傳給了A和B。
  • A拿著「公鑰C」加密了內容,並且發送給B。
  • C從中拿到了加密的內容,通過「私鑰C」解密,並且拿「公鑰A」將內容再次加密並發給B。
  • B拿到了加密的內容,通過自己的「私鑰B」進行解密。
  • A和B通信的過程沒有發現任何問題。

至於中間人攻擊的問題如何解決,會在後面一點的內容中提到「證書」的使用。


單向散列函數(one-way hash function)- 信息的指紋

當我們需要驗證一份文件是否有被修改過,可以通過「單向散列函數」來為文件產生「指紋」。

單向散列函數的特點是,它可以將任意長度的信息輸出成一個固定長度的散列值(Hash value)。

我們對同一份文件產出的散列值是相同的,並且無法通過散列值反算出原本的內容。
所以要驗證這一張圖片是否有被修改過,可以再次對圖片進行散列值的輸出並比較。

而單向散列函數也會被利用在儲存密碼的功能上,我們將使用者設定的密碼通過單向散列函數輸出的散列值儲存起來。
下一次使用者登入時只要比照散列值是否一致(通常會密碼+salt 來進行hash處理)。

單向散列函數:

  • MD4、MD5
  • SHA-1、SHA-256、SHA-384、SHA-512

其中MD是Message Digest、SHA是Secure Hash Algorithm


數字簽名(Digital Signature)

為了驗證收到的消息是不是真的來自於某人,於是有了數字簽名的概念。

舉例一個驗證的例子,假設A已經將公鑰A交給了B,但B不確定這是不是真的是公鑰A(前面提到的中間人攻擊可能已經將公鑰換掉了)

  1. A將消息發送給B。
  2. A同時將消息通過「私鑰A」簽名加密消息發送給B。
  3. B將簽名過的消息通過手上的「公鑰A」進行解密。
  4. B比較消息和解密過的消息是否一致,如果一致則嚴正簽名成功,也就是手上的這把公鑰真的是A的。

之所以加密可以作為「簽名」、解密可以用作與「驗證簽名」,是因為公鑰密碼中,不論用公鑰或者私鑰來加密,都只能用對應的私鑰或者公鑰來解密

數字簽名的方法

  • 直接對消息簽名的方法。
  • 對消息的散列值(hash value)簽名的方法。

而如果對整個消息進行加密有時候會非常耗時,所以如果我們對消息的散列值來進行加密就會快很多了。


證書(Certificate)

上面提到的密鑰配送問題,A和B並不知道收到的公鑰是否真的是對方發過來的。

因此有認證機構(Certification Authority、Certifying Authority,CA)來提供「公鑰證書」(Public key certificate,PKC),也簡稱為「證書(Certificate)」

為了防止中間人攻擊,我們引入了證書認證。

  1. B這次不直接將公鑰發送給A了,而是發送給「認證機構T」
  2. T通過自己的「私鑰T」來對「公鑰B」進行數字簽名,並且生成證書發送給A。
  3. A通過已經拿到的「公鑰T」來對數字簽名進行驗證,確認「公鑰B」的合法性。
  4. 驗證後就可以通過拿到的「公鑰B」來對信息進行加密發送給B了。

推薦資料:


 

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *