密碼學

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢
1917 年嘅詹默曼電報;張嘢上面寫嘅符號就噉睇好似語無倫次,但收訊人同傳訊人暗中知段嘢實際上講緊乜。

密碼學粵拼mat6 maa5 hok6英文Cryptography / Cryptology,源自古希臘文kryptós」,古希臘文「秘密」噉解[1][註 1]數學電腦科學嘅分支領域,專門研究點樣將數據以安全嘅方式傳達同儲起,通常係用加密等嘅方法,將段數據轉變成淨係得傳訊人同收訊人先會解讀到嘅形式,等其他人-尤其係敵人-唔能夠知道啲數據嘅內容[2][3]

密碼學最基本嘅概念係加密(encryption):加密定義係指將一段資訊入碼,轉化成第種表示方式,收訊人會知段資訊係點加密嘅,所以會有能力解讀段資訊,但收訊人以外嘅人正路就因為唔知個加密方案係點,就算攞到段資訊都解讀唔到段資訊嘅內容,而只係會得到一段望落完全雜亂無章符號[4]。一段做加密嘅演算法密文碼)大致上可以想像成好似以下噉嘅轉換過程:

  1. 傳訊者想傳一段信息
  2. 用加密演算法,將段信息轉換成一串就噉望落好似乜意思都冇嘅符號(例:%&=%&#*(%=#%#?
  3. 收訊者收到串符號(段加咗密嘅信息);
  4. 收訊人知加密演算法係乜,靠呢樣知識將段符號變返做加密前嘅樣。

密碼學上嘅知識同技術用途廣泛得好交關,例如軍事銀行電子商業等嘅工作都成日會涉及「有啲資訊要保密」-包括軍事情報同啲客嘅信用咭號碼呀噉。密碼學專家會用源自概率論資訊理論嘅知識研究「邊種加密演算法最難俾敵人拆解」等等嘅課題,係廿一世紀初資訊科技上不可或缺嘅一環[5][6]

定位[編輯]

睇埋:通訊資訊戰同埋秘密

喺最基本上,密碼學研究嘅課題係「點樣喺有敵人(指想偷同利用資訊嘅人)嘅環境之下安全噉通訊」。英文入面嘅「crypto-」呢個詞頭源自古希臘文嘅「κρυπτός」(羅馬字:kryptós),即係古希臘文裏面「隱密、秘密」噉嘅意思,而「-graphy」就源自古希臘文「γράφειν」(羅馬字:gráphein),係古希臘文「書寫」噉解,所以密碼學嘅英文名可以理解做「研究點樣寫低秘密嘢嘅學問」[7][註 2]

舉個例說明,啞謎機(Enigma machine)係密碼學史上好出名嘅一種機械。啞謎機喺廿世紀早期至中期嗰陣好流行,成日俾人攞嚟幫啲商業政治或者軍事上嘅通訊做加密,用法如下:啞謎機有一個鍵盤,上面有 26 個字母,而鍵盤對上有 26 個燈膽,每個燈膽又掕住個字母(下圖),每當用家撳鍵盤上其中一個掣嗰陣,鍵盤對上嗰啲燈膽有其中一個會著;當一個人想幫佢要傳嘅一段信息加密嗰時,佢要做嘅係

  • 用鍵盤打要傳嘅信息(明文),例如「Meet tonight at eight pm」(「今晚八點鐘見面」);
  • 記低佢打嗰段信息嗰陣有邊啲燈膽著過、啲燈膽以乜次序著、同埋啲燈膽對應嘅字母;
  • 燈膽著嘅次序就係嗰段信息嘅密文,例如「rksxf eqhbj fonil jpsku」(一段就噉望落好似係語無倫次嘅字);
  • 跟住就將段密文傳送去收信息嗰個人手上;
近睇一部啞謎機嘅鍵盤

如果收信息嘅人知道「撳咗嘅鍵盤掣」同「燈膽著嘅規律」之間嘅對應嘅話,佢就會能夠解讀嗰段密文,得知傳訊者想傳嘅信息內容。啞謎機設計到內部機制會令打嘅字同密文之間成一段固定(但唔易估)嘅關係嘅,而呢段關係會定時定候改變,確保啲用家能夠保密自己傳嘅信息,就算敵人截得住段信息,佢哋都解讀唔到段信息嘅內容[8][9]。密碼學就係想研究點樣用各種方法將要傳嘅數據隱藏起嚟,確保啲數據就算落咗入敵人手上,敵人都無力解讀啲數據嘅內容。密碼學係現代資訊戰(information warfare;指喺打仗競爭性嘅活動當中控制資訊,靠噉做令自己得到優勢)當中好重要嘅一環,喺軍事商業等嘅領域上都廣泛噉受到採用[10][11]

概念化[編輯]

內文:編碼加密密文解密、 同 鑑別

喺最基本上,密碼學所做嘅嘢包含咗編碼加密鑑別呢三個概念[2][12]

  • 編碼(coding):指一系列固定、用嚟將一段資訊嘅內容符號轉化嘅法則,喺電訊等嘅領域上成日都用到;舉個例說明,摩斯碼(Morse code;下圖)指明好嗮邊啲數列排序對應邊個羅馬字母或者阿拉伯數字,例如一點()跟一劃()係代表 A、一劃後面跟三點(-...)係代表 B、一劃一點一劃一點(-.-.)係代表 C... 如此類推,所以如果一個人將傳一段信息,而段信息嘅內容係「Wiki」(原文),用摩斯碼(法則)做編碼嘅話(轉化)就會變成「.--, .., -.-, ..[註 3]噉嘅一段符號[13]。亦都可以睇吓 ASCII資訊理論方面嘅嘢。
International Morse Code.svg
  • 加密(encryption):加密係指用一啲特定嘅編碼方法(即係所謂嘅密文碼;cipher)將一段想傳嘅信息(明文;plaintext)轉化做一串串嘅符號(密文;ciphertext),例如係一大串嘅 0 同 1,令到淨係得收信息嘅人能夠解讀(解密;decryption)嗰段嘢;技術性啲噉講嘅話,加密()同解密()可以想像成函數,會各自噉將自己嘅輸入轉化,當中解密係加密嘅反函數
  • 密文碼係編碼方法嘅一種,同一般嘅編碼方法唔同嘅係,密文碼係唔會俾外人知嘅-摩斯碼嗰啲法則公開,全世界嘅人都有得透過互聯網查到摩斯碼嘅編碼法則係點樣轉化啲符號嘅,所以第啲人攞到一串摩斯碼上手可以輕易噉解讀到串碼嘅內容;相比之下,密文碼正路嚟講淨係得傳信息嘅人同收信息嘅人會知,所以就算第啲人-例如係黑客-攞到串信息都唔會識得點樣解讀。好似係以下呢段密文噉,如果一個人唔知段密文碼(每個字母對應啲乜),佢唔會有能力搵得出嗰段信息加密之前嘅樣[14]。上述嘅過程可以想像成下圖噉嘅圖解-
    • 最左手邊嗰張白紙代表段明文,呢張紙掕住嗰條「鎖匙」就係密文碼,
    • 中間嗰張白紙代表密文-張紙上面寫咗啲就噉睇好似語無倫次噉嘅字,
    • 右手邊嗰條鎖匙係負責做解密嘅演算法,會將段密文轉化返做原本嗰段信息。
Public key encryption keys.png
  • 鑑別(authentication):鑑別泛指驗證一件資訊係咪真確;舉個例說明,想像家陣有兩個人 A 同 B,B 係 A 嘅員工,幫 A 管理佢啲財富,A 而家想傳信息俾 B,指示佢手上嗰啲股票要點樣做(繼續揸住啲股票定賣咗佢哋好),而又假想有個黑客想擾亂 A 同 B 之間嘅通訊,但 A 用嘅密文碼好先進,搞到個黑客解讀唔到段密文,但就算係噉,個黑客都大可以截住段密文,然後隨意噉篡改段密文,搞到 B 做解密嗰陣出錯。鑑別就能夠幫手應付呢個問題-假如 B 有能力做鑑別,即係有能力可靠噉知道「段信息係咪真係由 A 傳出嘅」同埋「段信息有冇俾人搞過嚟」,佢哋就能夠阻止黑客靠「隨意篡改段密文」嚟擾亂佢哋之間嘅通訊[15][16]。例如好多廿一世紀初嘅網站都會要求用家入密碼(password)先至可以簽到,簽到咗先至有得用某啲功能(好似下圖噉)-喺正常情況下,淨係得真正嘅用家先會知段密碼,所以如果一個用家入到段啱嘅密碼,佢應該就會係真正嗰位用家[17]
Mediawiki 1.25 sign in form.png

密文碼[編輯]

內文:密文碼
睇埋:密碼基元多重加密同埋乘積密碼法

密文碼(cipher),又或者叫密碼法,係密碼學其中一個最重要嘅概念,指負責「將原先嘅信息加密變做密文」嘅演算法。一段密文碼可以想像成一個函數,會將明文(輸入)轉化做對應嘅密文(輸出),而喺數學上,密文碼主要有以下兩種[14][18]

  • 換位法(transposition):將段信息文字嗰啲符號重新排列,但唔會改變啲符號嘅樣;
  • 替代法(substitution):將段信息文字入面嗰啲符號兌換做代替文字,但啲符號嘅位置不變,有系統噉將一組字或者字母換做第啲字、字母或符號(例如將啲 A 冚唪唥轉換做 D)。

好似以下呢啲都係密碼學上成日分析嘅密文碼:

圍欄密碼法[編輯]

內文:圍欄密碼法

圍欄密碼法(rail fence cipher)可以話係其中一種最基本最原始嘅密文碼。喺用圍欄密碼法嗰陣嘅步驟如下[19][20]

  • 攞段明文上手,例:WE ARE DISCOVERED. RUN AT ONCE.粵文:「我哋俾人發現咗喇。即刻走佬啦。」)
  • 將段明文用打斜對角上上落落嘅方法寫低,(如果係好似英文同粵文等由左到右寫嘅文字)將符號 寫喺符號 嘅右下,一路「將下個符號寫喺右下」直至到底(「幾多行先算係到底」係一個可調節嘅參數 ),跟住就變成將下個符號寫喺打前嗰個嘅右上,到頂就變返「將下個符號寫喺右下」,即係好似下面呢個矩陣噉():
 W . . . E . . . C . . . R . . . U . . . O . . . 
 . E . R . D . S . O . E . E . R . N . T . N . E 
 . . A . . . I . . . V . . . D . . . A . . . C . 
  • 程式編寫上,個矩陣(計埋啲空格)會係一個 咁大嘅陣列,當中 係串明文嘅長度。跟住,個用家就將段符號打橫噉寫出嚟(加密),即係
 WECRUOERDSOEERNTNEAIVDAC

最後得出一段好似圍欄噉梅花間竹嘅密文[註 4]。圍欄密碼法可以輕易噉做解密-只要收訊人知道 同「原先個矩陣有幾多打戙行」(呢個數值會等同段密文嘅長度),佢就可以知道(例如)段密文嘅符號 係段明文嘅符號 、段密文嘅符號 係段明文嘅符號 ... 如此類推。圍欄密碼法淨係涉及改變啲符號嘅位置,所以係一種用換位法嘅密文碼[19]

凱撒密碼法[編輯]

內文:凱撒密碼法

凱撒密碼法(Caesar cipher)係另一種原始嘅密文碼,出名在凱撒大帝(Julius Caesar)鍾意攞佢嚟喺私人書信嗰度用。用凱撒密碼法會有一個參數(),假設段明文係用字母式嘅文字嚟寫嘅,凱撒密碼法做嘅係將段明文入面嘅每個字母都轉換成(想像將啲字母打橫 A B C D 噉順序排成一行)移咗 咁多個位嘅字母,即係例如家陣段明文用羅馬字母嚟寫,當中 向左(每個字母向左移三格),就會將段明文每個 E 換做 B,每個 D 換做 A,每個 C 換做 Z... 如此類推(下圖)[21]

Caesar cipher left shift of 3.svg

畫做表嘅話如下:

明文字母 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文對應 XYZABCDEFGHIJKLMNOPQRSTUVW

設轉換法係 向左,凱撒密碼法嘅步驟如下:

  • 攞段明文上手,英文例子:
 THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG粵文:「隻好快嘅啡色狐狸喺隻懶上面跳過。」)
  • 將段明文每個字母轉換(Foreach 明文字母,做轉換),得出密文,例:
 QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

凱撒密碼法做嘅係按某啲法則將明文嘅每個符號轉換做第個款嘅符號,所以係一種用替代法嘅密文碼[21][22]。凱撒密碼法喺凱撒大帝嗰個時代-好多人都係文盲-頗為有效,不過到咗廿一世紀初,密碼學研究經已表明,凱撒密碼法查實好易拆解,例如羅馬字母噉,唔同羅馬字母喺英文當中嘅出現頻率都唔同-AE 常見啲,XJ 少見啲呀噉,做密碼拆解嘅人好多時可以齋靠觀察一段密文入面唔同字母嘅出現頻率嚟估到 嘅數值。因為噉,所以專業做密碼學嘅人好少可仲會用凱撒密碼法,就算要用都起碼都會喺凱撒密碼法上作出一啲創新,例如係以每兩個字母或者每三個字母做一組,對每組獨立噉做轉換[23]

彼利菲密碼法[編輯]

內文:彼利菲密碼法

彼利菲密碼法(Playfair cipher)係源自 1854 年嘅一種替代法密文碼,可以用嚟將用字母寫嘅明文加密。步驟如下[24][25]

  • 設定一個加密用嘅矩陣
    • 揀一個關鍵字,例:Playfair Example 做關鍵字;
    • 將個關鍵字啲字母排入去一個 5 × 5 格嘅矩陣嗰度,排完就按 A B C D 順序排,途中要揀一個字母(通常係 J)唔填而且重複咗嘅字母唔填,因為羅馬字母有 26 個咁多,所以噉做會得出一個啱啱好 25 格填嗮、冇任何字母重複咗嘅矩陣,例如下圖係將 Playfair Example 填落去個矩陣嗰度得出嘅樣(J 忽略,而紅色嗰啲細字母係因為重複咗而冇填落去嗰啲):
Playfair Cipher building grid omitted letters.png
  • 將明文嘅字母分開做一對對,如果明文嘅字母數量係單數,噉最後單丁嗰個字母掕個(例如)Z,例:明文係 instruments,分咗做一對對就變成
    'in' 'st' 'ru' 'me' 'nt' 'sz'
  • 當中一對字母當中嗰兩個字母唔可以同款,如果同款,就插個(例如)X 喺裏面,例:明文係 hello(唔可以俾 ll 呢個組合出現),做咗分對嘅過程之後應該會係
    'he' 'lx' 'lo'

做咗分對之後,Foreach 字母對,做以下嘅嘢:

  • 攞個矩陣上手睇,
  • 如果嗰對字母出現喺同一打戙行,將每個字母變成喺嗰個字母對落嗰個字母(最底嗰行對落當係最頂嗰行),例:用返頭先 Playfair Example 做關鍵字嘅矩陣,如果有對字母對係 DE,就將對字母變成 OD
Playfair Cipher 02 DE to OD.png
  • 如果嗰對字母出現喺同一打橫行,將每個字母變成喺嗰個字母對右嗰個字母(最右嗰行對右當係最左嗰行),例:用返頭先 Playfair Example 做關鍵字嘅矩陣,如果有對字母對係 EX,就將對字母變成 XM
Playfair Cipher 10 EX to XD.png
  • 如果上述兩點都唔成立,噉就喺對字母畫一個長方形,令對字母成為個長方形嘅兩個角,再將每一個字母換做同佢喺同一條橫行嗰個對角,例:繼續用 Playfair Example 做關鍵字嘅矩陣,如果有對字母對係 HI,就將對字母變成 BM
Playfair Cipher 01 HI to BM.png

如是者,就會得出一段密文。彼利菲密碼法相當好用,就算到咗廿一世紀初,彼利菲密碼法嘅變種就連喺專業嘅密碼學工作上都仲有人用[26]

維吉尼密碼法[編輯]

內文:維吉尼密碼法

維吉尼密碼法(Vigenère cipher)係一種多表置密碼法(polyalphabetic cipher),即係會用多過一款替代方案嚟幫段明文做加密,明文嘅唔同部份用唔同嘅替代方案。維吉尼密碼法會用到一幅表格(tabula recta)-喺英文入面,呢幅表格會係一個 26 × 26 格嘅矩陣,每一條橫行都係有齊嗮 26 個英文字母,每一行都係打前嗰後向左移咗 1 格,即係第一行會係 A 開頭跟住出嗮淨低嗰 25 個字母,第二行會係 B 開頭跟住出嗮淨低嗰 25 個字母,第三行會係 C 開頭跟住出嗮淨低嗰 25 個字母... 如此類推,即係好似下面呢幅圖噉[27][28]

Vigenère square shading.svg

攞住幅表格喺手,個傳訊人跟住就要有個關鍵字,例如家陣個關鍵字係 deceptive(英文「呃人嘅」噉解),傳訊人可以將個關鍵字重複寫無限咁多次,令明文嘅每個字母都有個對應嘅關鍵字字母[29][30]

  • 例如家陣明文係 WE ARE DISCOVERED. SAVE YOURSELF.粵文:「我哋俾人發現咗喇。自己走佬啦。」)
  • 將明文(唔包標點符號)同關鍵字對準:
 WE ARE DISCOVERED SAVE YOURSELF
 DE CEP TIVEDECEPT IVED ECEPTIVE (關鍵字重複無限次,令明文每個字母有個對應嘅關鍵字字母)
  • Foreach 明文字母以及佢對應嗰個關鍵字字母,
    • 攞個明文字母對應嗰一條打戙行;
    • 攞個關鍵字字母對應嗰一條打橫行;
    • 幅表格入面明文字母打戙行同關鍵字字母打橫行相交嗰點,就係對應呢個明文字母嘅密文字母;
    • 例:喺上面嗰幅表格入面,打戙行 W 同打橫行 D 相交嗰點嘅字母係 Z,所以 Z 就係密文第一個字母,打戙行 E 同打橫行 E 相交嗰點嘅字母係 I,所以 I 就係密文第二個字母... 如此類推:
 WE ARE DISCOVERED SAVE YOURSELF
 DE CEP TIVEDECEPT IVED ECEPTIVE
 ZI CVT WQNGRZGVTW AVZH CQYGLMGJ

維吉尼密碼法相當有效,能夠好大程度上收埋明文嘅字母頻率:例如凱撒密碼法最大嘅問題就係敵人能夠齋靠觀察密文當中唔同字母嘅出現頻率嚟大致噉估到段密文碼嘅參數(向左定向右、移咗幾多);相比之下,維吉尼密碼法就冇呢個問題-例如 E 係廿一世紀初英文入面最常出現嘅字母,如果用嘅係維吉尼密碼法,篇明文唔同部份嘅 E 會分別被轉換做唔同嘅字母,而唔似得凱撒密碼法噉個個 E 都係轉換做同一個密文字母。事實係,有密碼學專家實際計過條數,發現用維吉尼密碼法出嘅密文嘅字母頻率變異(簡單講指「出現得最多嘅字母」同「出現得最少嘅字母」之間喺出現頻率上嘅差距;可以睇埋變異數)會明顯細過明文嘅,所以令到敵人更加難齋靠觀察密文唔同字母嘅出現頻率嚟破解段密文碼[27][31]

以下圖為例,Y 軸表示出現頻率,X 軸係英文字母,由字母頻率高至低噉排,每個字母都有個冧把(1 到 26)表示佢排第幾。深色線係明文嘅字母頻率分佈,淺色線係密文嘅分佈,紅色線係一段完全隨機嘅文字嘅分佈。由幅圖嗰度睇得出,維吉尼密碼法會令「出現最多嗰個字母」(1)同「出現最少嗰個字母」(26)之間喺出現頻率上嘅差距縮細。

Vigenere letter frequencies.PNG

密碼體制[編輯]

對稱密匙密碼嘅圖解;家陣有兩個人-BobAlice-之間通訊,Bob 想傳嘅明文係 Hello Alice!加密解密都係用同一條匙嚟做。
相比之下,公開密匙密碼就係傳訊人 Bob 同收訊人 Alice 各自有條匙,傳訊人加密用嘅匙同收訊人解密用嘅匙唔同。
Alice 傳信息(Hello Bob!),並且用佢條私人匙幫一段掕住嘅額外信息加密,任何人都可以用公開匙嚟解讀段額外信息,知道傳段信息嘅人係手持 Alice 條私人匙嘅-就好似一個簽名噉。
內文:密碼體制
睇埋:密碼協議

對稱密匙[編輯]

內文:對稱密匙密碼

對稱密匙密碼(symmetric-key cryptography)泛指傳訊人同收訊人用嘅密匙一樣嘅密碼體制。密匙係指用嚟幫手做加密同解密嘅額外資訊,例如圍欄密碼法凱撒密碼法當中嘅 以及係彼利菲密碼法維吉尼密碼法當中用到嗰啲關鍵字。喺實際應用上,用家梗要有啲方法傳達有關「密匙係乜」嘅資訊,收訊人先會有能力解密,通常係傳訊人同收訊人事先講好個用開嘅密匙,或者係傳訊人要傳信息之前講個密匙俾收訊人知。一路直至 1976 年中為止,世上嘅加密方法冚唪唥都係用對稱密匙做嘅[6]

對稱密匙密碼可以分做兩大種:

  • 組密碼法(block cipher)-呢種密碼法會對固定長度嘅位元做加密同解密;即係例如每 2 位元嘅數據做一組,段演算法會對每組分別做加密,如果手上淨係得其中一個位元嘅數據(另外嗰個位元仲未傳到過嚟),部機就會企咗喺度乜嘢都唔做[32];例子可以睇吓數據加密標準(Data Encryption Standard,DES)同進階加密標準(Advanced Encryption Standard,AES)[33]
  • 流密碼法(stream cipher)-呢種密碼法會對段密文嘅每個位元獨立噉做加密同解密;即係每次收到一個位元就會即場做加密或者解密,就算收唔到下一個位元嘅數據都唔會企喺度唔郁,頂櫳係將段唔完整嘅密文或者解密輸出傳俾個用家[34]
問題

對稱密匙密碼成日俾人詬病話佢難以處理大規模組織(大型企業或者軍隊呀噉)嘅通訊:對稱密匙密碼要求做通訊嘅人個個手上都有條密匙,而點樣確保「啲成員個個都有密匙得嚟又冇安全漏洞」已經係一條撈絞得好交關嘅問題-大少少嘅組織閒閒地會有成千上萬咁多個成員,「俾個個成員手上都揸住條密匙」就難保唔會梗有幾個人口風唔夠密搞到條密匙外泄,但「個個成員手上嘅密匙都唔同」就會搞到有好多條密匙要記住(例如個組織有 1,000 個人,每對可能配對之間都有條密匙嘅話,淨係內部通訊就要用到成 499,500 條密匙)[註 5];除此之外,對稱密匙密碼要求通訊雙方信任對方,如果是但一個(因為惡意或者決策上嘅失誤)泄漏咗條密匙,另外嗰方就會跟住失去咗保護,呢樣嘢喺商業應用上係一條大問題[6]

公開密匙[編輯]

內文:公開密匙密碼

公開密匙密碼(public-key cryptography)係因應對稱密匙密碼嘅劣處而喺 1976 年誕生嘅一種體制,係史上第一款「一條通訊用多過一條密匙」嘅密碼體制。同對稱密匙密碼唔同,公開密匙密碼會將密匙分做公開(public)同私人(private)兩組,當中前者會攞去周圍派俾啲用家(例如係一間企業啲客),後者淨係得控制個系統嗰一方(例如間企業啲高層)會知。技術性啲噉講嘅話,想像家陣有套密碼體制 ,個系統會用到兩條唔同嘅密匙[35][36]

  1. 用家一定要能夠輕易噉計得出邊對密匙(加密匙 解密匙 )係相配嘅。
  2. 運算上要簡單,即係用電腦行起上嚟唔使嘥好多系統資源
  3. 最重要點:就算一個嘗試破解密碼嘅人就算清楚知道咗 、任何數量嘅對應明文密文、以及係兩條密匙()當中其中一條,淨低冇俾佢攞到嗰條密匙依然係喺運算上極難搵得出嚟嘅(例如想像條密匙用電腦計要計成 100 年先計到出嚟;可以睇運算複雜度[37])。
  4. 信息 係密匙,,就算知道咗 都要係難以搵到出嚟嘅。

有咗個噉嘅系統,一位用家就可以想佢手上條解密匙保密-私人匙 ,同時又將自己條加密匙公開-公開匙 ,俾任何人隨意通過互聯網睇到 。想像家陣有班人想同嗰位用家進行私人通訊(例:成千上萬嘅客想向一間企業傳信息,問件產品應該點樣用),佢哋嘅個人電腦可以隨意噉攞到 ,用 將自己嘅信息(例:可能會包括信用咭號碼等嘅敏感資訊)做加密跟住傳送去位用家嗰度;位用家可以輕易噉(點 1 同 2)用 嚟解讀呢啲信息[35]

優劣

公開密匙密碼解決到對稱密匙密碼嗰啲撈絞問題:喺公開密匙密碼呢種情況下,密匙嘅數量只會係用家數量嘅兩倍,每位用家一條 一條 ;而且因為 公開咗都唔會泄露 (點 3),所以 大可以交俾啲未必靠得住嘅人(例:一間企業唔能夠預自己啲客識密碼學曉保護自己手上嘅密匙);因為噉,同對稱密匙密碼比起嚟,公開密匙密碼比較啱用喺啲大得嚟又要同普羅大眾通訊嘅組織,例如廿一世紀初嘅大型企業同埋政府嘅各部門都會遇到「一般市民想用電郵向呢啲組織問嘢」等嘅情況[38][39]

唯一問題係齋用呢種基本系統嘅話,用家(企業)唔能夠向外界(客)單向噉傳達秘密嘅信息。不過亦有進階啲嘅公開密匙密碼系統會用到「喺用傳訊方條私人匙做加密,再用收訊方條公開匙做加密,做到(因為用咗傳訊方嗰條私人匙)鑑別傳訊方身份」等嘅技術[38]

功能分隔

值得一提嘅係,公開密匙密碼做嘅嘢係將保密系統同鑑別系統分開:喺對稱密匙密碼系統當中,一位收訊人能夠由收到嘅信息當中同時知道段信息嘅內容(保密)同埋傳訊人嘅身份(鑑別)-每位傳訊人都有相應嘅一條密匙,所以「對方用咗邊條密匙」能夠向收訊人同時透露傳訊人嘅信息內容同身份;公開密匙密碼就唔同,一位收訊人能夠由收到嘅信息當中同時知道段信息嘅內容,但因為會想向佢傳信息嘅人冚唪唥都會用同一條 ,所以佢唔能夠齋靠「對方用咗邊條密匙」嚟得知對方嘅身份,而係要靠進一步問對方嘅(例如)電話號碼生日日期先會知對方身份-保密同鑑別分開咗做兩個唔同嘅功能[35]

RSA[編輯]

內文:RSA 密碼系統
睇埋:輾轉相除法

RSA 密碼系統(RSA cryptosystem)係一種好出名嘅公開密匙密碼系統,專門攞嚟幫一啲以數字形式存在嘅重要資料(信用咭號碼、電話號碼同埋生日日期呀噉)做加密。RSA 密碼系統建基於一點[40]

將兩個埋一齊係好容易嘅,要搵出『一個數係由邊幾個因數乘埋產生嘅』相比之下就麻煩好多。

想像家陣噉樣做:

  • 攞兩個數值有返咁上下大嘅質數
  • 計出 。喺實際應用上, 嘅數值極之大-喺廿一世紀初,十進制表示嘅話兩個都會有超過 150 個位;所以「要用演算法搵出 嘅因數」要嘥極大量嘅時間[41]
  • 計出
  • 搵一個整數 ,當中 相對質數(coprime)-即係話 最大公因數 ;而且
  • 計出 ,當中 (可以睇商餘計算[40]
  • 係公開匙, 要保密。

虛擬碼表達嘅話[42]

 int x = 61, int y = 53; // 為咗簡單起見,當住 x 同 y 係 61 同 53 先。
 int n = x * y; // 計出 n
 // n = 3233.
 
 // 計出 
 int phi = (x-1)*(y-1);
 // phi = 3120.
 
 int e = findCoprime(phi);  // 計出 e
 // 喺呢個例子當中,e = 17 滿足到上述嘅條件。
 
 // 搵出滿足到以下條式嘅 d:
 d = (1 mod (phi))/e;
 // 喺呢個例子當中,d = 2753 
 public_key = (e=17, n=3233);
 private_key = (d=2753, n=3233);
 
 // 想像明文 P = 123, 密文 C 會係:
 C = (123^17) % 3233 = 855;
 // 幫密文 C 做解密嘅話:
 P = (855^2753) % 3233 = 123;

因為 數值極大,要用電腦喺夠短嘅時間之內搵出 嘅數值喺運算上行唔通(可以睇吓運算理論,尤其係運算複雜度理論)。而且做密碼嗰一方仲有得定時改變呢啲數值嚟加強保安[43][44]

密碼分析[編輯]

「嗱,家吓有段密文,我哋唔知明文同密文碼係乜,但要郁手破解段嘢。」
內文:密碼分析
睇埋:頻率分析同埋通信量分析

密碼分析(cryptanalysis)係研究點樣分析系統內部嘅隱藏資訊嘅一門學問,包括咗(喺唔知明文密文碼係乜嘅情況下)諗密文要點拆解。呢種研究係密碼學嘅重要一環:專業做密碼學工作嘅人往往要識唔同類嘅密文碼出嘅密文分別有啲乜特徵;然後佢哋就會睇吓可唔可以由密文嘅特徵嗰度,估傳訊方用咗邊種或者邊啲密文碼呀噉,從而加深自己對「唔同密文碼有乜弱點」嘅理解。好似黑客等會出於惡意嘗試破解密文嘅人會做密碼分析,而密碼學工作者又會嘗試模仿黑客嘅呢啲行為,嘗試用黑客興用嘅技巧嚟拆解自己嘅密文碼-如果結果發現「黑客常用嗰啲技巧拆解唔到佢嘅密文碼」嘅話,一位密碼學工作者就知自己發明咗一種新嘅強力密文碼技術[45][46]

分析基礎[編輯]

內文:唯密文攻擊

想像家陣分析者手上有段密文,要嘗試齋靠手上揸住嘅密文估明文同密文碼係乜(唯密文攻擊;ciphertext-only attack)。最基本上,佢要做嘅包括咗以下呢啲工序[47]

  • 觀察段密文:原則上,有關明文同密文碼嘅資訊會或多或少噉殘留喺一段密文嗰度,所以分析者有得靠住觀察段密文嘅特徵,嚟大致噉估到傳訊方可能係用咗邊種或者邊啲密文碼,而如果篇密文係用字母嚟寫嘅話,呢種工作中途會涉及對字母頻率分析-例如正話提到,維吉尼密碼法傾向令字母之間喺出現頻率上嘅差異縮細,而基本嘅凱撒密碼法唔會引起呢種差異;如果用電腦計咗吓,發覺段密文喺「字母頻率嘅最大差異」上明顯有別於正常書寫文字嘅話,段密文就唔似係用咗凱撒密碼法。
  • 估密文碼同密匙:想像分析者做咗一啲初步分析,心目中對於「傳訊方用嘅係邊種密文碼」有幾個可能嘅答案。佢跟住就需要估吓密匙係乜(例如維吉尼密碼法當中嘅關鍵字),原則上,呢種方法可以係完全靠撞,但呢種做法就算係用現代電腦都仲係會嘥時間得滯(做唔到喺夠短嘅時間之內破解密文),所以正路嚟講,分析者最起碼會用某啲方法縮窄搜尋嘅範圍,例如係靠傳訊方嘅喜好嚟估邊啲字佢會大機會用嚟做關鍵字,又或者計吓邊啲關鍵字係多人會用嘅。順帶一提,因為呢個緣故,有好多密碼學工作者都想做到完全隨機噉產生密匙,令到密匙最難估(技術性噉講即係資訊熵要有咁大得咁大)。
  • 重複做好多次嘅嘗試拆解:產生「預想中嘅密文碼係乜」同埋一條「估嘅密匙」,嘗試用呢兩樣資訊解讀段密文,睇吓段密文似唔似係明文;如果佢估錯咗密文碼同密匙,解讀過程通常會出一段語無倫次嘅混亂字母,不過如果分析者將呢個過程重複好多次,而且佢對密文碼同密匙嘅估計有返咁上下準嘅話,係有可能做到喺夠短嘅時間之內破解密文嘅。

進階分析[編輯]

睇埋:攻擊模型

除此之外,密碼分析上會諗嘅攻擊模型(attack model)仲可以按「攻擊者手上有乜資訊」嚟分類-唯密文攻擊只不過係密碼破解上最簡單最基本嗰種情況,除咗唯密文攻擊之外,密碼分析仲成日會思考(例如)已知明文攻擊(known-plaintext attack)嘅情況,即係指攻擊者攞到咗若干段嘅密文同埋相應嘅明文,而且佢知道邊段密文對應邊段明文,喺度嘗試靠噉嚟搵出段密文碼以及破解更多嘅密文。做密碼學工作嘅人會做考慮呢啲咁多唔同嘅情況,攞一隻研究緊嘅密文碼,估吓隻密文碼喺唯密文攻擊之下會撐到幾耐、喺已知明文攻擊之下又會撐到幾耐... 呀噉,靠睇隻密文碼喺唔同情況下嘅表現嚟評估隻密文碼掂唔掂[48]

要留意嘅係,做密碼分析好多時比較睇重分析「個密碼系統撐到幾耐」:原則上,廿一世紀初嘅密碼系統絕大多數-除咗一次性密碼本(OTP)之外-都係有可能拆解得到嘅,例如攻擊方喺估密匙嗰陣,查實大可以夾硬嚟-索性逐隻逐隻英文字撞(即係所謂嘅窮舉攻擊),不過用呢種方法拆起密文上嚟會好嘥時間噉解。因為噉,喺實際應用上,密碼學工作者關注嘅好多時都唔係「個密碼系統有冇可能拆解」,而係「喺唔同嘅攻擊模型之下,個密碼系統能夠擋住個攻擊者擋到幾耐,能唔能夠爭取到足夠嘅時間,俾防守方發覺自己受到攻擊並且採取必要嘅保安行動」[49]

歷史[編輯]

凱撒大帝嘅胸像

密碼學呢家嘢歷史好悠久:

古典密碼學[編輯]

睇埋:古典密文碼

古典密碼學最少可以追溯到去公元前一兩個世紀,例如羅馬共和國凱撒大帝拉丁文:Gaius Julius Caesar;公元前 100 年至 44 年)就出咗名鍾意喺私人書信嗰度用凱撒密碼法幫自己嘅信息加密,而且亦有報告話凱撒大帝佢試過用呢種密碼法嚟向自己手下嘅將軍傳達信息,可以話係世上最早嘅密碼學技術(指認真噉為咗想隱藏自己要傳嘅信息嘅內容而做嘅密文)之一[50];而打前少少嘅印度古書《慾經》(Kama Sutra;梵文:कामसूत्र)當中亦有提到將一段文字嗰啲字母轉化嚟隱藏想傳嘅信息[51][52]

基本上,「古典密碼學」一詞可以包嗮電腦出現打前嘅時代嘅密碼學:喺電腦時代嘅密碼技術絕大多數都係古典密文碼(classical cipher)-意思即係話家陣唔會再有專業嘅密碼學工作者採用;噉係因為呢啲密文碼實會泄露明文嘅統計特性,例如凱撒密碼法就掩飾唔到啲字母之間喺出現頻率上嘅差異,而 9 世紀嘅阿拉伯數學家肯迪(Al-Kindi;阿拉伯文:أبو يوسف يعقوب بن إسحاق الصبّاح الكندي‎)發明咗頻率分析嘅技術,做到分析一段文字當中唔同字母嘅出現頻率[53][54],令到任何有足夠嘅知識同運算能力嘅人都能夠輕易噉破解多表置密碼法以外嘅替代法密文碼產生嘅密文,而且喺有電腦打前嘅時代,都仲話有可能出現「一個人識頻率分析,但唔夠運算能力做所需嘅運算」嘅情況,不過喺廿世紀中後期開始,電腦經已普及化,任何人都可以隨手攞到能夠好快噉解開古典密文碼產生嘅密文嘅架生[55][56]。因為噉,到咗廿一世紀初,呢啲古代密文碼响專業密碼學工作上經已冇人仲會用,頂嗮櫳係俾人攞嚟做解謎遊戲等消閒用途嘅一部份[57]

現代密碼學[編輯]

廿世紀上半橛至中期出現咗一樣巨大嘅變化-電腦呢種運算機械崛起。電腦最大嘅特徵就係能夠以快過人手好多嘅速度嚟計數,例如好似凱撒密碼法嗰種「Foreach 明文字母,做轉換」嘅做法用電腦做能夠喺一瞬間搞掂,快過人手好多;除此之外,廿世紀後半橛資訊科技開始成熟,有咗互聯網呢樣嘢,所以出現咗「要點樣喺公用渠道保密信息內容,將密匙交俾一般普羅大眾用」(可以睇返公開密匙密碼)等嘅問題[58]。呢啲巨變引起咗密碼學技術上嘅重大革新,於是數學電腦科學等嘅領域就喺 1970 年中正式開展對密碼學嘅研究[6]

現代密碼學喺著眼點上同古典密碼學有明顯嘅差異:古典密碼學多數時候都淨係考慮加密同解密,頂櫳要諗埋信息嘅傳遞;現代密碼學就仲要考慮埋好多額外嘅嘢-現代密碼學仲包括要驗證一件信息係咪完整(信息驗證碼)、信息係咪無可抵賴由預期嗰位傳訊人發出(數碼簽名)同埋喺分散式運算嘅時候嚟自裏面同外面嘅攻擊嘅相關問題。除此之外,現代密碼學有明顯嘅理論基礎-古典密碼學係一種實用工藝,好多時亦冇對密碼學嗰啲概念有清晰嘅定義,而現代密碼學研究嘅嚴謹性(例如會用數學符號表達啲概念)就令到密碼學成為咗一門嚴格嘅科學[2]

喺技術上,現代密碼學明顯比較睇重運算複雜度(computational complexity)方面嘅思考:運算複雜度係指一條運算上嘅問題要用幾多資源(時間記憶體等)先至可以解得到,如果話一條運算問題運算複雜度高,即係話條問題要嘥好多資源先會解得到[59][60];原則上,密碼學工作者正路都會希望「拆解段密文」呢樣工作嘅運算複雜度盡可能有咁高得咁高,噉嘅話嘗試破解密碼嘅人嘅電腦就做唔到喺夠短嘅時間之內破解段密文同密文碼-令到要隱藏嘅信息內容就算喺敵人有先進電腦科技嘅情況下,都一樣係拆解唔到,例如 RSA 密碼系統就係噉[6]

註釋[編輯]

  1. 密碼學集中研究嘅唔係攞嚟驗證身份嗰啲密碼
  2. 「Cryptology」嘅詞尾「-logy」就係嚟自「λογία」(-logia),即係古希臘文「研究」噉解。
  3. 呢度加逗號係為咗方便用家喺維基介面睇清楚啲字母邊個打邊個。
  4. 喺進階啲嘅做法當中,傳訊人跟手仲可以對段密文做多幾次圍欄密碼嚟進一步加強保密。
  5. 廿世紀初嘅組織用「淨係俾高層管理人員攞密匙」嘅做法嚟做折衷,不過喺實際應用上都係成日會撞到問題。

應用[編輯]

睇埋[編輯]

文獻[編輯]

  • Becket, B (1988). Introduction to Cryptology. Blackwell Scientific Publications. ISBN 978-0-632-01836-9. OCLC 16832704.
  • Bellare, M., & Rogaway, P. (2005). Introduction to modern cryptography. Ucsd Cse, 207, 207.
  • Flannery, S. (2002). In code: A mathematical journey. Algonquin Books.
  • Galbraith, S. D. (2012). Mathematics of public key cryptography. Cambridge University Press.
  • Gannon, J. (2001). Stealing Secrets, Telling Lies: How Spies and Codebreakers Helped Shape the Twentieth Century. Potomac Books, Inc.
  • Hellman, M. E. (2002). An overview of public key cryptography (PDF). IEEE Communications Magazine, 40(5), 42-49.
  • Lee, Tom (August 2000). "Cryptography and the New Economy" (PDF). The Industrial Physicist. 6 (4): 31.
  • Massey, J. L. (1988). An introduction to contemporary cryptology. Proceedings of the IEEE, 76(5), 533-549.
  • Paar, C., & Pelzl, J. (2009). Understanding cryptography: a textbook for students and practitioners. Springer Science & Business Media.

[編輯]

  1. Liddell, Henry George; Scott, Robert; Jones, Henry Stuart; McKenzie, Roderick (1984). A Greek-English Lexicon. Oxford University Press.
  2. 2.0 2.1 2.2 Aumasson, J. P. (2017). Serious cryptography: a practical introduction to modern encryption. No Starch Press.
  3. Definition of 'Cryptography'. The Economic Times.
  4. Agrawal, Monika (May 5, 2012). "A Comparative Survey on Symmetric Key Encryption Techniques". International Journal on Computer Science and Engineering. 4: 877–882.
  5. Rivest, Ronald L. (1990). "Cryptography". In J. Van Leeuwen (ed.). Handbook of Theoretical Computer Science. 1. Elsevier.
  6. 6.0 6.1 6.2 6.3 6.4 Diffie, Whitfield; Hellman, Martin (November 1976). "New Directions in Cryptography" (PDF). IEEE Transactions on Information Theory. IT-22 (6): 644–654.
  7. cryptography (n.). Online Etymology Dictionary.
  8. Kruh, L.; Deavours, C. (2002). "The Commercial Enigma: Beginnings of Machine Cryptography". Cryptologia. 26: 1-16.
  9. Aldrich, Richard James (2010). GCHQ: The Uncensored Story of Britain's Most Secret Intelligence Agency. HarperPress.
  10. Denning, D. E. R. (1999). Information warfare and security (Vol. 4). Reading, MA: Addison-Wesley.
  11. Bellare, Mihir; Rogaway, Phillip (21 September 2005). "Introduction". Introduction to Modern Cryptography. p. 10.
  12. Biggs, Norman (2008). Codes: An introduction to Information Communication and Cryptography. Springer. p. 171.
  13. Carron, L. Peter (1986). Morse Code: The essential language. Radio amateur's library. 69.
  14. 14.0 14.1 Bellare, M., Kilian, J., & Rogaway, P. (1994, August). The security of cipher block chaining. In Annual International Cryptology Conference (pp. 341-358). Springer, Berlin, Heidelberg.
  15. "What is Authentication? Definition of Authentication, Authentication Meaning". The Economic Times.
  16. Digital Authentication - the basics.
  17. Urbina, Ian; Davis, Leslye (November 23, 2014). "The Secret Life of Passwords". The New York Times.
  18. King, D. A. (2001). The Ciphers of the Monks: A Forgotten Number-Notation of the Middle Ages (Vol. 44). Franz Steiner Verlag.
  19. 19.0 19.1 Rail Fence Cipher – Encryption and Decryption. GeeksforGeeks.
  20. Talbert, R. (2006). The Cycle Structure and Order of the Rail Fence Cipher (PDF). Cryptologia, 30(2), 159-172.
  21. 21.0 21.1 Luciano, Dennis; Gordon Prichett (January 1987). "Cryptology: From Caesar Ciphers to Public-Key Cryptosystems". The College Mathematics Journal. 18 (1): 2–17.
  22. Pieprzyk, Josef; Thomas Hardjono; Jennifer Seberry (2003). Fundamentals of Computer Security. Springer. p. 6.
  23. Leyden, John (2006-04-19). "Mafia boss undone by clumsy crypto". The Register. Retrieved 2008-06-13.
  24. Murali, P., & Senthilkumar, G. (2009, April). Modified version of playfair cipher using linear feedback shift register. In 2009 International Conference on Information Management and Engineering (pp. 488-490). IEEE.
  25. Rahim, R., & Ikhwan, A. (2016). Cryptography technique with modular multiplication block cipher and playfair cipher. Int. J. Sci. Res. Sci. Technol, 2(6), 71-78.
  26. Gaines, Helen Fouché (1956) [1939], Cryptanalysis / a study of ciphers and their solutions, Dover. p. 201.
  27. 27.0 27.1 Kahn, David (1996). The Codebreakers (2nd ed.). Scribner. p. 133.
  28. Soofi, A. A., Riaz, I., & Rasheed, U. (2016). An enhanced Vigenere cipher for data security. Int. J. Sci. Technol. Res, 5(3), 141-145.
  29. Mendelsohn, Charles J (1940). "Blaise De Vigenere and The 'Chiffre Carre'". Proceedings of the American Philosophical Society. 82 (2).
  30. Helen F. Gaines (18 November 2014). Cryptanalysis: A Study of Ciphers and Their Solution. Courier Corporation. p. 117.
  31. Omran, S. S., Al-Khalid, A. S., & Al-Saady, D. M. (2011, September). A cryptanalytic attack on Vigenère cipher using genetic algorithm. In 2011 IEEE Conference on Open Systems (pp. 59-64). IEEE.
  32. Knudsen, Lars R.; Robshaw, Matthew (2011). The Block Cipher Companion. Springer.
  33. "FIPS PUB 197: The official Advanced Encryption Standard" (PDF). Computer Security Resource Center. National Institute of Standards and Technology.
  34. Matt J. B. Robshaw (1995). Stream Ciphers Technical Report TR-701, version 2.0, RSA Laboratories.
  35. 35.0 35.1 35.2 Stallings, William (1990). Cryptography and Network Security: Principles and Practice. Prentice Hall. p. 165.
  36. Diffie, Whitfield; Hellman, Martin (8 June 1976). "Multi-user cryptographic techniques". AFIPS Proceedings. 45: 109–112.
  37. Cryptography: Theory and Practice, 3rd Edition. (Discrete Mathematics and Its Applications), (2005), by Douglas R. Stinson, Chapman and Hall/CRC.
  38. 38.0 38.1 Diffie, W. (1988). The first ten years of public-key cryptography. Proceedings of the IEEE, 76(5), 560-577.
  39. Galbraith, S. D. (2012). Mathematics of public key cryptography. Cambridge University Press.
  40. 40.0 40.1 Rivest, Ronald L.; Shamir, A.; Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM. 21 (2): 120–126.
  41. Why Are Prime Numbers Important in Cryptography?. Medium.
  42. Boneh, Dan (1999). "Twenty Years of attacks on the RSA Cryptosystem". Notices of the American Mathematical Society. 46 (2): 203–213.
  43. Håstad, Johan (1986). "On using RSA with Low Exponent in a Public Key Network". Advances in Cryptology - CRYPTO '85 Proceedings. Lecture Notes in Computer Science. 218. pp. 403–408.
  44. Coppersmith, Don (1997). "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities". Journal of Cryptology. 10 (4): 233-260.
  45. Bard, Gregory V. (2009). Algebraic Cryptanalysis. Springer.
  46. Hinek, M. Jason (2009). Cryptanalysis of RSA and Its Variants. CRC Press.
  47. Cryptanalysis and Decryption. digit.
  48. Gordon Welchman, The Hut Six Story: Breaking the Enigma Codes, p. 78.
  49. Shannon, Claude; Weaver, Warren (1963). The Mathematical Theory of Communication. University of Illinois Press.
  50. Icitsuser (22 January 2017). "The Ancient Cryptography History". ICITS.
  51. Translators: Richard Burton, Bhagavanlal Indrajit, Shivaram Parashuram Bhide (18 January 2009). The Kama Sutra of Vatsyayana (Translated From The Sanscrit in Seven Parts With Preface,Introduction and Concluding Remarks). The Project Gutenberg.
  52. David Kahn (December 1996). The Codebreakers. Simon and Schuster. p. 74.
  53. Singh, Simon (2000). The Code Book. New York: Anchor Books. pp. 14-20.
  54. Leaman, Oliver (16 July 2015). The Biographical Encyclopedia of Islamic Philosophy. Bloomsbury Publishing.
  55. Al-Kadi, Ibrahim A. (April 1992). "The origins of cryptology: The Arab contributions". Cryptologia. 16 (2): 97-126.
  56. Lennon, Brian (2018). Passwords: Philology, Security, Authentication. Harvard University Press. p. 26.
  57. Crack the Code! Make a Caesar Cipher. Scientific American.
  58. Lee, Tom (August 2000). "Cryptography and the New Economy" (PDF). The Industrial Physicist. 6 (4): 31.
  59. Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
  60. Braatz, R. P., Young, P. M., Doyle, J. C., & Morari, M. (1994). Computational complexity of/spl mu/calculation. IEEE Transactions on Automatic Control, 39(5), 1000-1002.

[編輯]