跳去內容

密碼學

出自維基百科,自由嘅百科全書

一九一七年嘅詹默曼電報[歐 1];張嘢上面寫嘅符號就噉睇好似語無倫次,但收訊人同傳訊人暗中知段嘢實際上講緊乜。

密碼學粵拼mat6 maa5 hok6)係數學電腦科學嘅分支領域,專門研究點樣將數據以安全嘅方式傳達同儲起,通常係用加密等嘅方法,將段數據轉變成得傳訊人同收訊人先解讀到嘅款,敵人無法知道啲數據講乜[1][2]

密碼學最基本嘅概念係加密[歐 2]定義上,加密係指將資訊入碼,轉化做第種表示方式;正常嚟講,收訊人知段資訊係點加密嘅,所以有能力解讀段資訊,但係收訊人以外嘅人唔知加密方案為何,就算攞到段資訊都解讀唔到,只會得到望落完全雜亂無章符號[3]。做加密嘅演算法cipher —大致可以想像成以下噉嘅轉換過程:

  1. 傳訊者想傳某段信息
  2. 用加密演算法,將信息轉做一串望落咩意思都冇嘅符號,例如 %&=%&#*(%=#%#?
  3. 收訊者收到符號;
  4. 收訊人知道解密演算法係乜,有能力將段符號變返做加密前嘅款。

密碼學知識嘅用途非常廣泛,諸如軍事銀行電子商業等嘅工作都成日有資訊要保密-例如係軍事情報或者啲客嘅信用咭號碼呀噉。喺研究方面,密碼學專家會用概率論資訊理論嘅知識研究邊啲加密演算法難拆解或者類似嘅課題。而呢啲研究對廿一世紀初嘅資訊科技嚟講好有用[4][5]

要留意嘅係,密碼學集中研究嘅攞嚟驗證身份嗰啲密碼。為咗避免混亂,好多人會用通行碼嚟稱呼驗證身份用嗰啲密碼。

領域定位

[編輯]
睇埋:通訊資訊戰秘密

最基本上,密碼學(參見英文cryptography)研究嘅係點樣喺有敵人嘅環境下安全噉通訊,當中敵人係指緊想偷同利用資訊嘅人。英文同其他歐語成日用嘅 crypto- 詞頭,源自古希臘文

κρυπτός羅馬字轉寫為 kryptós

即係隱密、秘密噉嘅意思[6]而 -graphy 就源自古希臘文 γράφειν / gráphein,即係古希臘文書寫噉解,所以密碼學個英文名可以理解為研究點樣寫低秘密嘢嘅學問噉嘅意思[7][註 1]

舉個例,啞謎機[歐 3]密碼學史上嘅經典機械。啞謎機盛行於廿世紀早至中期,成日用嚟幫商業政治或者軍事上嘅通訊做加密,用法如下:啞謎機有一個鍵盤,上面有 26 隻字母,而鍵盤對上有 26 個燈膽,每個燈膽又掕住隻字母,好似下圖噉,每當用家撳掣,其中一個燈膽會著;噉使用者想幫佢嘅信息加密嗰時,佢要噉做:

  • 用鍵盤打想傳嘅信息,呢段信息謂之明文,例如用粵拼今晚八點鐘見粵拼gam1 maan1 baat3 dim2 zung1 gin3)同時暫且假設就算只打字母唔打聲調數字,對方都一樣理解到。
  • 記低佢打信息嗰陣邊啲燈膽著過、啲燈膽以咩次序著、同埋每個燈膽對應嘅字母;
  • 燈膽著嘅規律就係段信息嘅密文,例如 rksxf eqhbj fonil jpsku,呢段字就噉望落好似語無倫次;

跟住佢就郁手將段密文傳送去收訊方手上。

如果收訊方知道燈膽著嘅規律點樣對應撳咗嘅鍵盤掣,佢就能夠解讀密文,得知傳訊方想講乜。啞謎機嘅設計係,內部機制會令打嘅字同密文之間成一段固定但唔易估嘅關係,而呢段關係會定時更改,確保用家能夠保密信息,就算敵人截得住信息都解讀唔到[8][9]

密碼學研究嘅重點,就係想知點樣用各種方法,將要傳嘅數據隱藏起嚟,確保數據就算落入敵人手,敵人都無力解讀。現代資訊戰涉及各方喺競爭性質嘅活動中控制資訊,務求令自己得到優勢,而其中重要嘅一環就係密碼學。密碼學知識喺軍事商業等嘅領域上都廣受採用[10][11]

概念基礎

[編輯]

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

編碼

[編輯]
内文:編碼

編碼[歐 4]係指一系列法則,用嚟將資訊嘅內容符號轉化。編碼呢樣嘢喺電訊等領域上成日都用到,舉例說明,摩斯碼(下圖)指明好晒邊啲數列排序對應邊隻羅馬字母或者阿拉伯數字,譬如

  • A 係一點()跟一劃()、
  • B 係一劃後面跟三點(-...)、
  • C 係一劃一點一劃一點(-.-.

... 如此類推,所以如果有人想傳一段信息,信息內容係 Wiki(原文),用摩斯碼(法則)做編碼嘅話就會變成

.-- (w), .. (i), -.- (k), .. (i) [註 2]

噉嘅符號[13]。亦都可以睇吓 ASCII資訊理論方面嘅嘢。


加密

[編輯]
内文:加密密文解密

加密[歐 2]:加密係指用特定嘅編碼方法將想傳嘅信息,即係明文[歐 5],轉化做一串串符號,形成密文[歐 6],例如係一大串 0 同 1,噉淨係得收信息嘅人能夠解讀(解密[歐 7])嗰段嘢。數學化啲講,加密 E 同解密 D 可以想像成函數,會各自將自己嘅輸入轉化,當中解密係加密嘅反函數

密碼法係編碼方法一種,同一般編碼方法唔同嘅係,密碼法係唔會俾外人知嘅-摩斯碼嗰啲法則公開,全世界都有得透過互聯網查到摩斯碼嘅編碼法則係點樣轉換符號嘅,所以任何人攞住串摩斯碼喺手,都可以輕易解讀;相比之下,密碼法正常淨係得傳信方同收信方知,所以就算其他人-例如黑客-攞到信息,都唔會識得解讀。好似係以下呢段密文噉,如果一個人唔知密碼法係乜,佢唔會有能力搵出段信息加密之前嘅樣[14]。想像下圖噉嘅圖解-

  • 最左手邊嗰張白紙代表段明文,呢張紙掕住嗰條鎖匙就代表緊密碼法,
  • 中間嗰張白紙代表密文-張紙上面寫咗嘅字,就噉睇好似語無倫次,
  • 右手邊嗰條鎖匙係負責做解密嘅演算法,會將段密文轉化返做原本嗰段信息。


鑑別

[編輯]
内文:鑑別
睇埋:通行碼

鑑別[歐 8]泛指驗證資訊係咪真確

舉例說明,想像依家有兩個人 A 君同 B 君,B 係 A 嘅員工,幫 A 管理佢啲財富,而家 A 想傳信息俾 B,指示佢手上嗰啲股票要繼續揸住定賣,而又假想有個黑客想擾亂 A 同 B 之間嘅通訊,但 A 用嘅加密技術好先進,個黑客解讀唔到密文,但就算係噉,黑客都大可以截住密文,然後隨意篡改,搞到 B 解密嗰陣出錯。鑑別就能夠應付呢個問題-假如 B 有能力做鑑別,即係有能力可靠噉知道段信息係咪真係由 A 傳出,同埋知道段信息有冇做過手腳,佢哋就能夠防止黑客透過隨意篡改密文嚟擾亂通訊[15][16]

例如通行碼[歐 9]就係一種常用嘅鑑別方式。有好多廿一世紀初嘅網站,都會要求用家入通行碼先至可以簽到,簽到咗先至有得用某啲功能-喺正常情況下,只得真正嘅用家先會知通行碼,所以如果某位用家入到啱嘅通行碼,佢應該就會係真正嘅用家[17]



廿一世紀初嘅電腦保安工作者好關注通行碼嘅相關課題。有關密碼學技術可以點樣幫手保密通行碼,通行碼強度雜湊函數等嘅課題都會提到。

釐清概念

密碼學:研究點樣「寫秘密嘢」,成日用到密文碼,而密碼學嘅技術,可以用嚟保密資訊,譬如係銀行嘅通行碼呀噉。

密碼法

[編輯]
内文:Cipher

Cipher粵拼saai1 faa2*4),又或者叫密碼法,係密碼學其中一個最重要嘅概念,演算法一種,負責將原先嘅信息加密變做密文。密碼法可以想像成函數,會攞住明文做輸入,轉化做對應嘅密文做輸出,而喺數學上,密碼法主要有兩種[14][18]

  • 換位法[歐 10]:將信息文字嗰啲符號重新排過,但唔會改變啲符號嘅樣;
  • 替代法[歐 11]:將信息文字入便嗰啲符號兌換做代替文字,但符號位置不變,有系統噉將一組字或者字母換做第啲字、字母或符號,例如將啲 A 冚唪唥轉換做 D 呀噉。

圍欄密碼法

[編輯]

圍欄密碼法[歐 12]步驟如下[19][20]

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

最後得出好似圍欄噉梅花間竹嘅密文[註 3]。圍欄密碼法可以輕易解密-收訊人只要知道 n 嘅數值為何同埋原先個矩陣有幾多行打戙行(呢個數值會等同段密文嘅長度),佢就可以知道

段密文嘅符號 2 係段明文嘅符號 5、
段密文嘅符號 3 係段明文嘅符號 9

... 如此類推。

圍欄密碼法淨係涉及改變符號嘅位置,所以屬於換位法嘅密碼法[19]

凱撒密碼法

[編輯]

凱撒密碼法[歐 13]係另一種原始嘅密碼法,據講凱撒大帝鍾意用呢種做法嚟保密佢啲私人書信。

用凱撒密碼法會有一個參數 n,假設明文係用字母式嘅文字嚟寫嘅,想像將啲字母打橫 A B C D 噉順序排成一行,凱撒密碼法係將明文入面嘅每個字母都轉換成移咗 n 咁多個位嘅字母,即係例如依家明文用羅馬字母嚟寫,當中 n = 3 向左,即係每個字母向左移三格,就會將段明文每個 E 換做 B,每個 D 換做 A,每個 C 換做 Z... 如此類推,好似下圖噉[21]

畫做表格嘅話就係:

明文字母 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文對應 XYZABCDEFGHIJKLMNOPQRSTUVW

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

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

凱撒密碼法按某啲法則將明文嘅每個符號轉換成第個款嘅符號,所以屬於換位法嘅密碼法[21][22]

喺凱撒大帝嗰個時代,好多人都係文盲。喺嗰陣時凱撒密碼法幾有效,不過到咗廿一世紀初密碼學研究表明,凱撒密碼法查實好易拆解,例如羅馬字母噉,唔同羅馬字母喺英文當中嘅出現頻率都唔同-AE 常見啲,XJ 少見啲呀噉,做密碼拆解嘅人可以齋靠觀察密文入面唔同字母嘅出現頻率,估到 n 嘅值。因為噉,專業做密碼學工作嘅人好少可會用凱撒密碼法,就算係用都起碼都會做創新,例如以每兩個字母或者每三個字母做一組,同每組獨立噉轉換[23]

彼利菲密碼法

[編輯]

彼利菲密碼法[歐 14]係源自一八五四年嘅一種替代型密碼法,可以將用字母寫嘅明文加密。步驟如下[24][25]

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

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

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

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

維吉尼密碼法

[編輯]

維吉尼密碼法[歐 15]係一種多表置密碼法[歐 16],即係會用多過一款替代方案嚟幫明文加密,明文唔同部份用唔同嘅替代方案。

維吉尼密碼法會用到表格[歐 17]:喺英文入面,呢幅表格會係 26 × 26 格嘅矩陣,每條橫行都係有齊晒 26 個英文字母,每行都係之前嗰行向左移咗 1 格,即係第一行會係 A 開頭跟住出晒淨低嗰 25 個字母,第二行會係 B 開頭跟住出晒淨低嗰 25 個字母,第三行會係 C 開頭跟住出晒淨低嗰 25 個字母... 如此類推,好似下面幅圖噉[27][28]

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

  • 例如家陣明文係 WE ARE DISCOVERED. SAVE YOURSELF.(粵譯:我哋俾人發現咗喇。你自己保命啦。
  • 將明文(唔包標點符號)同關鍵詞對準:
 WE ARE DISCOVERED SAVE YOURSELF
 DE CEP TIVEDECEPT IVED ECEPTIVE (關鍵詞重複無限次,明文每個字母有對應嘅關鍵詞字母)
  • 同每個明文字母以及佢對應嗰個關鍵詞字母,
    • 攞個明文字母對應嗰一條打戙行;
    • 攞個關鍵詞字母對應嗰一條打橫行;
    • 表格入面明文字母打戙行關鍵詞字母打橫行相交嗰點,就係對應呢個明文字母嘅密文字母;
    • 例:喺上面幅表格入便,打戙行 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 都係轉做同一個密文字母。事實係有密碼學專家實際計過數,觀察用維吉尼密碼法嗰陣密文嘅字母頻率變異,簡單講呢個概念係指

  • 出現得最多嘅字母
  • 出現得最少嘅字母

之間喺出現頻率上爭幾遠[註 5],佢哋發覺喺呢種情況下,密文嘅字母頻率變異同明文比會明顯細咗,於是敵人就更難透過觀察密文嘅字母出現頻率嚟破解密碼法[27][31]

以下圖為例,Y 軸表示出現頻率(以百分比計)而X 軸係英文字母,由字母頻率高至低排,每個字母都有個冧把(1 到 26)表示佢排第幾。

  • 藍色線係明文嘅字母頻率分佈,
  • 藍色線係密文嘅分佈,
  • 紅色線係一段完全隨機嘅文字嘅分佈。

由圖中睇得出,維吉尼密碼法會令出現最多嗰個字母(1)同出現最少嗰個字母(26)之間喺出現頻率上嘅差距縮細。

密碼體制

[編輯]
内文:密碼體制
睇埋:密碼協議

對稱密匙

[編輯]
對稱密匙嘅圖解:家陣有兩個人-波巴愛麗絲-要通訊,波巴想傳嘅明文係哈佬!,加密同解密都係用同一條匙嚟做。
公開密匙嘅圖解 1:愛麗絲有條公開匙,公開匙個個都睇到,波巴可以用公開匙加密佢段明文,段明文要用愛麗絲條私人匙先解到密。
公開密匙嘅圖解 2:愛麗絲傳信息,用佢條私人匙幫段掕住嘅額外信息加密;任何人都可以用公開匙解讀額外信息,知道傳訊人揸住愛麗絲條私人匙-嗰段額外信息好似個簽名噉。

對稱密匙密碼[歐 18]指一套密碼體制,講緊傳訊人同收訊人用嘅密匙粵拼ki1)一樣。密匙係指用嚟幫手做加密同解密嘅額外資訊,例如係圍欄密碼法凱撒密碼法當中嘅 n,或者係彼利菲密碼法維吉尼密碼法用到嗰啲關鍵詞。喺實際應用上,用家梗要有方法傳達有關密匙係乜嘅資訊,收訊人至有能力解密,通常係傳訊人同收訊人事先講好用開嘅密匙,或者係傳訊人傳信息之前講個密匙俾收訊人知。一路直至一九七六年中為止,世上所有嘅加密方法都係用對稱密匙做嘅[5]

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

對稱密匙密碼成日俾人詬病,話佢難以處理大規模組織嘅通訊:對稱密匙密碼要求做通訊嘅人個個手上都有條密匙,而點樣確保成員個個都有密匙得嚟又冇安全漏洞,已經非常撈絞;較大型嘅組織閒閒哋有成千上萬個成員,如果個個成員手上都揸住條密匙,就難保唔會有某幾個人口風唔夠密,搞到條密匙外泄,但假如個個成員手上嘅密匙都唔同,就有極大量嘅密匙要記-例如個組織有 1,000 個人,每對可能配對之間都有條密匙嘅話,淨係組織內部通訊就要用成 499,500 條密匙咁多[註 6]

此外,對稱密匙密碼要求通訊雙方信任對方,如果佢哋是但一個因為惡意或者決策上嘅失誤泄漏咗密匙,另外嗰方就會跟住失去咗保護,呢樣嘢喺商業應用上係大問題[5]

公開密匙

[編輯]

公開密匙密碼[歐 23]係喺一九七六年誕生嘅體制,係史上第一款密碼體制做到一條通訊使用多過一條密匙。同對稱密匙密碼唔同,公開密匙密碼會將密匙分做公開[歐 24]私人[歐 25]兩組,當中前者會攞去周圍派俾啲用家,例如係某企業嘅客,同時後者只得控制系統嗰方會知,即係例如交俾間企業啲高層噉。

技術化啲噉講嘅話,想像家陣有套密碼體制 T,個系統會用到兩條唔同嘅密匙[35][36]

  1. 用家一定要能夠輕易計得出邊對密匙(加密匙 e 同解密匙 d)係相配嘅。
  2. T 喺運算上要簡單,用電腦行唔使花好多系統資源
  3. 最重要點:就算嘗試破解密碼嘅人清楚知道 T,手上有任何數量嘅對應明文密文,又知道兩條密匙(e 同 d)當中其中一條,淨低冇泄漏嗰條密匙依然係喺運算上極難搵得出嘅,即係想像條密匙喺噉嘅情況下要計 100 年先搵到出嚟[37]
  4. 設 x 做信息,k 係密匙,,就算知道咗 y,x 都係難以搵出嘅。

有咗噉嘅系統(想像公開密匙圖解 1),用家可以將佢手上條解密匙保密-私人匙 d,同時又將自己條加密匙公開-公開匙 e,俾任何人隨意通過互聯網睇到 e。想像依家有班人想同嗰位用家進行私人通訊,譬如係千上萬嘅客想向企業傳信息,問件產品點用,佢哋嘅個人電腦可以隨意攞到 e,用 e 將自己嘅信息[註 7]做加密傳去用家度;位用家可以輕易(點 1 同 2)用 d 解讀呢啲信息[35]

公開密匙密碼解決到對稱密匙密碼嗰啲撈絞問題:喺公開密匙下,密匙嘅數量只會係用家數量嘅兩倍,每位用家一條 e 一條 d;而且因為 e 公開咗都唔會泄露 d(點 3),所以 e 大可以交俾靠唔住嘅人-例如一間企業,唔可以預期自己啲客會識保護密匙;因此同對稱密匙比,公開密匙適用於大又要同普羅大眾通訊嘅組織,例如廿一世紀初嗰啲大型企業同埋政府嘅各部門都會有一般市民想用電郵向佢哋問嘢[38][39]

唯一問題係,齋靠呢種系統嘅話,用家(企業)唔能夠向外界(客)單向傳秘密信息。不過亦有進階嘅公開密匙系統會用噉嘅做法:想像用傳訊方條私人匙做加密,再用收訊方條公開匙做加密,做到(因為用咗傳訊方嗰條私人匙)鑑別傳訊方身份[38]。可以睇吓公開密匙圖解 2

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

RSA

[編輯]

RSA 密碼系統[歐 26]係一種公開密匙密碼系統,專門攞嚟同一啲以數字形式存在嘅資料做加密,譬如係信用咭號碼、電話號碼同埋生日日期呀噉做加密。RSA 密碼系統建基於一點[40]:將兩個埋一齊好容易,但係攞住一個數,要搵出佢係由邊幾個因數乘埋產生嘅,相比之下就麻煩好多。

想像依家噉樣做:

  • 攞兩個數值有返咁上下大嘅質數 x 同 y。
  • 計出 n,n = x × y。喺實用上,x 同 y 嘅值極大-喺廿一世紀初,x 同 y 用十進制表示嘅話,通常兩個都有超過 150 個位;所以要用演算法搵出 n 嘅因數,要嘥極大量嘅時間[41]
  • 計出 φ(讀音近似粵拼faai1),當中 φ = (x-1) × (y-1)。
  • 搵一個整數 e,當中 e 係 φ 嘅相對質數[歐 27]-即係話 e 同 φ 嘅最大公因數係 1;而且
  • 計出 d,當中 d × e = ,呢條式用咗商餘計算[40]
  • n 同 e 係公開匙,x、y、φ 同 d 則要保密。

虛擬碼表達嘅話[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;

由於 x、y 同 φ 數值極大,敵人難以喺夠短嘅時間內搵出 d 嘅值。而且做密碼嗰方仲有得定時改變呢啲數值嚟加強保安[43][44]

密碼分析

[編輯]
想像:「嗱,家吓有段密文,我哋唔知明文同 cipher 係乜,但要破解佢。」
内文:密碼分析

密碼分析[歐 28]研究點樣分析系統內部嘅隱藏資訊,包括喺唔知明文密碼法係乜嘅情況下,思考密文要點拆解。

呢種研究係密碼學嘅重要一環:專業做密碼學工作嘅人往往要理解唔同類嘅密碼法,出嘅密文分別有咩特徵;然後佢哋就要思考可唔可以由密文嘅特徵度,估傳訊方用咗邊種或者邊啲密碼法,從而加深自己對唔同密碼法嘅弱點嘅理解。好似黑客等出於惡意破解密文嘅人會做密碼分析,而密碼學工作者又要嘗試模仿黑客呢啲行為,用黑客用開嘅技巧嚟拆解自己嘅密碼法[註 8]-如果結果發現黑客常用嗰啲技巧,完全拆解唔到佢嘅密碼法,呢位工作者就知道自己發明咗一種強力嘅密碼法[45][46]

分析基礎

[編輯]

想像依家分析者手上有段密文,要嘗試單靠手上揸住嘅密文,估明文同密碼法係乜,即係所謂嘅唯密文攻擊[歐 29]。最基本上,分析者要做嘅包括以下工序[47]

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

進階分析

[編輯]
睇埋:攻擊模型

除此之外,密碼分析仲會諗埋攻擊模型[歐 30]嘅概念,按照攻擊者手上有咩資訊嚟將情況分類:唯密文攻擊只係密碼破解上最簡單最基本嗰種情況;除咗唯密文攻擊之外,密碼分析仲成日會思考例如已知明文攻擊[歐 31]嘅情況,喺呢種情況下,攻擊者得到咗若干量嘅密文同埋相應嘅明文,而且佢知道邊段密文對應邊段明文,喺度嘗試搵出密碼法以及破解更多嘅密文。做密碼學工作嘅人,會做考慮埋呢啲唔同情況,攞住佢哋研究緊嘅密碼法,估吓呢種密碼法喺唯密文攻擊之下撐到幾耐、喺已知明文攻擊之下又撐到幾耐...,如是者,佢哋就可以理解手上嘅密碼法喺唔同情況下嘅表現如何,評估呢種密碼法掂唔掂[48]

做密碼分析好多時比較重視個密碼系統「撐到幾耐」:原則上,廿一世紀初嘅密碼系統絕大多數[註 10]都係有可能拆解嘅,例如攻擊方估密匙,查實大可以夾硬嚟-索性逐隻逐隻英文詞撞,即係用所謂嘅窮舉攻擊,不過由於用呢種方法拆密文會好嘥時間,攻擊方唔能夠喺有限時間內拆得到。因此喺實際應用上,密碼學工作者關注嘅好多時都唔係個密碼系統有冇可能拆解,而係以下呢點[49]

喺唔同攻擊模型下,呢個密碼系統能夠擋住攻擊者擋到幾耐?

亦即係話佢哋關注個系統能唔能夠爭取到足夠時間,俾防守方發覺自己受攻擊並且採取相應嘅保安行動。

歷史

[編輯]

古典密碼學

[編輯]
凱撒大帝胸像

古典密碼學最少可以追溯至公元前,例如羅馬共和國凱撒大帝[歐 32](公元前 100 年至 44 年)就出晒名鍾意喺私人書信之中用凱撒密碼法,幫自己嘅信息加密,而且亦有報告話凱撒大帝試過用呢種密碼法向自己手下嘅將軍傳信息,可以話係世上最早嘅密碼學技術之一,遠古時期鮮有咁認真為咗想隱藏信息內容而造密文[50];而喺佢之前嘅印度古書《慾經[歐 33]當中亦有提到將一段文字嗰啲字母轉化,隱藏想傳達嘅信息[51][52]

基本上,古典密碼學一詞可以包晒電腦出現前嘅密碼學:喺電腦時代前嘅密碼技術,近乎變晒做古典密碼法-意思即係話而家唔會再有專業嘅密碼學工作者採用;噉係因為呢啲密碼法實會泄露明文嘅統計特性,例如凱撒密碼法就掩飾唔到字母喺出現頻率上嘅差異,而九世紀嘅阿拉伯數學家肯迪[歐 34]就發明咗頻率分析嘅技術,做到分析一段文字中唔同字母嘅出現頻率[53][54],令到任何有足夠知識同運算能力嘅人都能夠輕易破解多表置密碼法以外嘅替代式密碼法產生嘅密文,而且喺電腦前嘅時代,都仲有可能有人識頻率分析,但唔夠運算能力做所需嘅運算,不過自從廿世紀中後期開始,電腦經已普及,任何人都可以隨手就快速解開古典密碼法產生嘅密文[55]。因為噉,到咗二十一世紀初,呢啲古代密碼法响專業嘅密碼學工作上經已冇人會用,頂攏係攞嚟做解謎遊戲等嘅消閒用途[56][57]

現代密碼學

[編輯]
睇埋:電腦

廿世紀上半至中期出現咗一樣巨大變化:電腦崛起。電腦最大嘅特徵就係能夠以快過人手好多嘅速度計數,好似凱撒密碼法嗰種同每個明文字母做轉換嘅做法,用電腦做能夠喺一瞬間搞掂,快過人手好多;此外,廿世紀後半橛資訊科技開始成熟,有咗互聯網,就出現咗

「要點樣喺公用渠道保密信息內容,將密匙交俾一般普羅大眾用」(可以睇返公開密匙密碼

等嘅問題[58]。呢啲巨變引起密碼學技術上嘅大革新,於是數學電腦科學等嘅領域就喺一九七零年中正式開展對密碼學嘅研究[5]

現代密碼學喺著眼點上同古典密碼學有明顯差異:古典密碼學多數時候都淨係考慮加密同解密,最多就係要諗埋信息傳遞;現代密碼學就仲要考慮埋好多額外嘅因素-現代密碼學仲要驗證信息係咪完整(信息驗證碼)、驗證信息係咪真係由預想中嘅傳訊人發出(數碼簽名)同埋喺分散式運算嘅時候思考嚟自內同外嘅攻擊。現代密碼學仲有埋理論基礎-古典密碼學係實用工藝,好多時並冇對密碼學概念有清晰定義,而現代密碼學研究要嚴謹,例如會用數學符號表達佢哋嘅概念,就更加令到密碼學成為嚴格嘅科學[1]

喺技術上,現代密碼學重視運算複雜度[歐 35]方面嘅思考:運算複雜度係指一條運算問題要用幾多資源,諸如時間記憶體等,先至可以解到,如果話某條運算問題運算複雜度高,即係話條問題要嘥好多資源先解到[59][60];原則上,密碼學工作者都會希望拆解密文嘅工作,運算複雜度要盡量有咁高得咁高,噉嘅話嘗試破解密碼嘅人嘅電腦,就做唔到喺夠短嘅時間內破解密文同密碼法-噉樣要隱藏嘅信息內容,敵人就算有先進電腦科技都一樣拆解唔到,譬如 RSA 密碼系統就係噉[5]

後量子

[編輯]

後量子密碼學[歐 36]係廿一世紀初開始興起嘅密碼學。

後量子密碼學同打前嘅密碼學技術有大分別,重點在於佢係想抵抗用量子運算嚟行嘅密碼分析:廿世紀後期至廿一世紀初嘅電腦保安技術,好多時都係靠住將資料攞去加密,要破解呢啲加密咗嘅資料要做大量運算,而咁大量運算現實電腦根本處理唔掂;但隨住量子電腦引起討論,密碼學工作者發現行量子運算嘅電腦有可能達致極高運算能力,例如本來要成一百萬年先計到嘅數,量子電腦可以喺一個月內計完,於是好多電腦保安專家就開始擔心,量子運算嘅強勁運算力會俾黑客利用,用嚟輕易破解密文同密碼法,於是學界就出咗後量子密碼學嘅諗頭—意思係指「用嚟應對量子運算嘅世界」嘅新密碼學[61]

應用

[編輯]

睇埋

[編輯]

文獻

[編輯]

歐美文獻:

  • 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.
  • 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.

註釋

[編輯]
  1. Cryptology 一詞嘅詞尾 -logy 就嚟自 λογία / -logia,即係古希臘文研究噉解。
  2. 呢度加逗號同括號,純粹係為咗方便用家喺維基介面睇清楚啲字母邊個打邊個。
  3. 喺進階嘅做法中,傳訊人跟住仲可以對段密文做多幾次圍欄密碼嚟加強保密。
  4. 因為噉,彼利菲密碼法查實有漏洞-想像插咗 X 之後字母數量變咗單數。進階版嘅彼利菲密碼法有多種方法補救。
  5. 可以睇埋統計學上講嘅變異數
  6. 廿世紀初嘅組織試過淨係俾高層管理人員攞密匙,諗住作為折衷做法,但喺實際應用上都係成日會遇到問題。
  7. 會包括地址信用咭冧把等嘅敏感資訊
  8. 好似白帽黑客做嘅嘢噉。
  9. 完全隨機,就表示資訊熵去到最大數值。
  10. 除咗一次性密碼本(OTP)之外

歐詞

[編輯]

外語詞彙,主要係英文:

一覽
    1. Zimmermann Telegram
    2. 2.0 2.1 encryption
    3. Enigma machine
    4. coding
    5. plaintext
    6. cipher text
    7. decryption
    8. authentication
    9. password
    10. transposition
    11. substitution
    12. rail fence cipher
    13. Caesar cipher
    14. Playfair cipher
    15. Vigenère cipher
    16. polyalphabetic cipher
    17. tabula recta
    18. symmetric-key cryptography
    19. block cipher
    20. Data Encryption Standard,DES
    21. Advanced Encryption Standard,AES
    22. stream cipher
    23. public-key cryptography
    24. public
    25. private
    26. RSA cryptosystem
    27. coprime
    28. cryptanalysis
    29. ciphertext-only attack
    30. attack model
    31. known-plaintext attack
    32. 拉丁文:Gaius Julius Caesar
    33. Kama Sutra;梵文:कामसूत्र
    34. Al-Kindi;阿拉伯文:أبو يوسف يعقوب بن إسحاق الصبّاح الكندي‎
    35. computational complexity
    36. post-quantum cryptography

[編輯]

引用咗嘅文獻網頁

一覽
    1. 1.0 1.1 1.2 Aumasson, J. P. (2017). Serious cryptography: a practical introduction to modern encryption. No Starch Press.
    2. Definition of 'Cryptography'. The Economic Times.
    3. Agrawal, Monika (May 5, 2012). "A Comparative Survey on Symmetric Key Encryption Techniques". International Journal on Computer Science and Engineering. 4: 877-882.
    4. Rivest, Ronald L. (1990). "Cryptography". In J. Van Leeuwen (ed.). Handbook of Theoretical Computer Science. 1. Elsevier.
    5. 5.0 5.1 5.2 5.3 5.4 Diffie, Whitfield; Hellman, Martin (November 1976). "New Directions in Cryptography" (PDF). IEEE Transactions on Information Theory. IT-22 (6): 644-654.
    6. Liddell, Henry George; Scott, Robert; Jones, Henry Stuart; McKenzie, Roderick (1984). A Greek-English Lexicon. Oxford University Press.
    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 互聯網檔案館歸檔,歸檔日期2021年7月26號,. (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? 互聯網檔案館歸檔,歸檔日期2021年7月26號,.. 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 互聯網檔案館歸檔,歸檔日期2023年3月15號,.. 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 互聯網檔案館歸檔,歸檔日期2021年8月4號,.". 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. Crack the Code! Make a Caesar Cipher. Scientific American.
    57. Lennon, Brian (2018). Passwords: Philology, Security, Authentication. Harvard University Press. p. 26.
    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.
    61. How Will Quantum Technologies Change Cryptography?. Caltech.

[編輯]