僅用數學分析就破譯了最高等級密碼,他比圖靈更厲害

2021-02-19 數學研討

說起密碼相關的話題,大家腦海裡首先直觀感覺就是這東西很神秘,是個很高級的玩意。

軍事史上最著名的密碼之一 凱撒密碼

古希臘有著名的凱撒密碼,他創造性地把所有的字母向後移動了3位,使得看到密文的時候根本不懂得其意思,使得戰場上的機密消息得以安全傳遞。

後來人們覺得凱撒密碼太簡單,又發明了置換密碼,多表替換密碼,可以說,正是情報對於戰爭的重要性迫使著加密方式越來越先進,給人的感覺也就越來越神秘。

在給信息加密這方面,中國古代有過非常成熟的案例,並且在使用的幾百年時間裡居然從未被破解過,這就是我國的晉商推出的票號兌換業務。

票號業集大成者 雷履泰

在沒有票號業之前,商人們走南闖北,需要攜帶大量金銀,重量且不說,那個時代的環境下, 攔路土匪強盜不知道有多少,安全性很難保證。

在這樣的歷史環境下,晉商雷履泰開啟了票號承兌業務,把銀子在票號裡兌換成票據,然後憑藉票據異地取現銀。其實就差不多相當於是現在的存摺,但是那個時候其實實現類似存摺的方法難度不小,首先要解決的就是如何防偽並且識別的問題,那個時候可沒有什麼資料庫的概念,所謂憑證僅僅是依靠票據上的痕跡暗號來判斷的。

在這種情況下,雷履泰發明了一套在當時幾乎不可破解的加密方式,下面我們來領略一下雷大掌柜的天才構想。

日升昌 防偽密押

首先他不在票面上直接寫上銀兩數目,而是用密語寫成,這些密語只有票號的資深人士才能看懂,旁人根本察覺不了,他用了一首詩來做加密,類似於現在的秘鑰。

「謹防假票冒取,勿忘細視書章」其實這表示著一到十二月。幾月存取就印第幾個字的章。而日期是堪笑世情薄,天道最公平。昧心圖自私,陰謀害他人。善惡終有報,到頭必分明。這三十個字。生客多查看,斟酌而後行。代表銀兩第一個數一到十。趙氏連城璧,由來天下傳,代表銀兩第二位數一到十。國寶流通代表萬千百兩。」

事實上,這一份防偽密押在書寫的時候也不是隨意的,這裡的前30個字緊挨在這裡,左邊的部分10個字為一組,最後4個字又為一組。30個字為一組,容易讓人想到就是一個月30天,中間兩個為10的組,也容易讓人想起是十進位。。。

現在我們這樣想都是建立在人們千辛萬苦破解之後的聯想。假如,我們對於這樣的加密方式毫無知曉,破解他其實相當有難度。你的匯票上寫著「看寶通」,拿給票號掌柜,掌柜核驗匯票無誤之後就會給你兌出5000兩銀子來。

日升昌僅存的一張匯票

只有這一道加密手段肯定是不可靠的,雷掌柜又想到一種辦法,當時的所有票據都是人工手寫的,只要是人工手寫的,那麼就很容易留下一些極為隱秘的特徵。比如在某些筆畫上加重或者特意拖長,甚至在製作票據的時候,在某些筆畫上扎個眼,或者褶皺一下,這些重重加密的手段全部用上了,只要有一個特徵有疑問,那麼就要經過更加嚴格的審核才會有結果。

每次兌換之後匯票就立刻銷毀,防止有人收集過多票據進行分析解密。至於那個加密的詩句,當然也不是永久的,一個月一換,本身那塊密押詩句就是絕密的,再加上一個月一換,所以就更加保險了。

在如此反覆的加密過程之後,票號業的保險程度也是讓人瞠目結舌,一百幾十年來,從來沒有人成果偽造過一次匯票,也沒有人破解其中的奧秘。現代的支票業務或多或少都借鑑了中國的票號加密手段,票號業務以及匯票加密手段是我國封建時期商業上一次非常了不起的發明。

人工智慧先驅者 密碼專家 圖靈大神

到了近代戰爭,敵對雙方不但要在戰場上拼的你死我活,在那些看不見的戰場上也是針鋒相對,總是不懈餘力地想去破解對方的指令,通過提前掌握對方的指令來在戰場上取得主動權。

在這方面,大名鼎鼎的圖靈是最經典的代表,他最偉大的創造在於把數學分析和機器運算加入到密文分析這個非常枯燥繁雜的過程中來。通過對已知密文的不斷歸納總結,然後把可能的結果交給機器去運算,從而省下大量人力物力。

圖靈用天才般的直覺找到了突破口,恩尼格瑪機雖然是機器加密的優秀代表,但是終究還是人操作的,只要是人為操作的,就不可避免地留下一些痕跡。

圖靈的終極武器 炸彈

比如,德國人每天早上六點都會發送天氣預報,雷打不動,這些固定的字母串當然就被圖靈作為線索逐層破解,有些這些已知的結果,再交給他發明的炸彈機器,最終得以在有效的時間裡算出結果來,從而破解了德軍的恩尼格碼,一舉扭轉了盟軍在歐洲戰場的局面。

你的每一次指令都已經被對方截獲並破譯,這個仗還怎麼打,人家完全可以在你眼皮底下溜走,而你卻完全沒有任何察覺。

德軍迷之自信的機器 恩尼格瑪機

後來有人分析,正是因為圖靈傑出的工作,使得二戰結束時間至少提前了兩年以上!

歐洲戰場密碼大戰如此精彩,其實當時的美軍對於日軍的密碼破譯也同樣驚心動魄,甚至美國人用的方法比圖靈的更加高明。

美國最偉大的密碼破譯專家 威廉姆·弗裡德曼

威廉姆·弗裡德曼是美國陸軍軍官,1891年出生,也是一位傑出的密碼教育學家,培養了許許多多密碼分析方面的專業人才。曾經破譯了日軍紫密密碼,提前洞悉了日本外交的各種秘密指令。

與圖靈的方法不同,弗裡德曼和他的團隊沒有用小線索的方式來逐步試探最終的答案,他對於機械式密碼的破譯工作是終極層面的,也就是說他的方法適用於任何機械式加密,不會造成更換加密方式,之前的破譯方法和工作就立刻一文不值的情況。

我們大概都知道在日常使用的英文單詞裡,不同字母出現的概率是不同的。5個原因字母出現的可能最高,其中出現概率最高的是字母e,概率大概是13%,最少的是字母z大概只有0.06%。

這是人們很久以前就注意到了的規律,在經過大量統計之後得出的分布情況。也就是說只要你的文件是英文書寫的,那麼這裡的字母分布情況就基本上是這樣的情況。

這是一個非常重要的結論,如果現在有一個簡單的替換加密,當密文數量足夠多的時候,任何人只要根據這個分布規律都可以破譯這樣的加密文件。

英文中字母出現的概率是固定的

當然了,這個秘密是如此地容易理解,實際上加密過程中就得千方百計地避免這種靠字母頻率分析的方式就可以破解的加密方式。

於是密碼設計者就得往另外一個方向靠,那就是想方設法使得密文能夠經受得住統計學的考驗,也就是說,你用了頻率分析法也得不到之前明文裡出現的各個字母的分布情況,所有的字母看起來都像是均勻分布的。

你統計之後大概會在500個字母裡得出20個a,20個e,,,20個z。如果真是這樣,那麼頻率分析法便完全失去作用了,必須另闢蹊徑。

弗裡德曼想出一個方法,他在英文文檔中統計了連續兩個字母相同的概率會是多少,比如,aa在所有英文中出現的可能性大概就是8%*8%=0.0064,ee的概率就是13%*13%=0.00169,以此類推,我們把所有連續字母對出現的概率加起來,大概是0.0667。

也就是講,我們拿起一份自然英語的文檔,大概平均100個字母裡會有6.67次連續出現相同字母。我們把這個0.0667叫作Kp,意思是明文字母重碼率。這裡的明文重碼率有個專門的詞叫Kappa值。

這是明文情況下統計的,肯定也有密文情況下的字母碰撞概率,由於密文裡失去了字母頻率分析的意義,各個字母已經呈現均勻分布。那麼從aa,bb一直到zz的概率就是26*1/26*1/26=0.0385。我們把這個0.0385叫作密文字母重碼率,用Kr表示。

弗裡德曼的測試方法 字母碰撞

Kappa值在密碼分析領域非常重要,為什麼呢?

因為多數情況下,發送者都不會只用一種加密方式來發送密文,那假如在信息的不同部位採用了不同的加密手段怎麼做呢?

Kappa檢測此時就派上用場了。如果兩段密文採用的是同種加密方式,那麼,字母碰撞的概率一定會接近密文重碼率Kr,如果採用的是不同加密方式,那麼字母碰撞概率就會接近Kp。這一句話價值萬金!

密碼分析工作很大程度上是對字母做頻率分析

破譯員應該怎麼做呢?

就是拿起兩段密文不斷進行字母比對,統計密文重碼率。如果得到了Kr相近的數值,那麼就可以認為是同種加密了。事實上,這裡就相當於是我們要去一個未知的城市,這個城市的方向我們不知道,距離我們也不知道,做什麼交通工具還是不知道。

經過kappa檢測之後,我們就知道了,這個城市在我們的東邊大概200公裡,坐高鐵就可以到了。Kappa檢測給我們提供了破譯的方向,接下來就是具體的破譯方法了。

到了這裡,弗裡德曼的助手所羅門·庫爾巴克提出了kappa檢測升級版Phi檢測和Chi檢測。

Phi檢測通過比較理論Phi值和統計Phi值判定一份密文是由單一密表加密所得還是多份密表加密所得,區分原理大體相同於Kappa檢測。而Chi檢測則可以通過比較Chi值判定出兩份密文的密鑰是否一致。

二戰中美軍裡的風語者們

機械式加密一般都會內置輪盤,所有複雜到難以破譯的機器無非就是輪盤數量多點,變換複雜點而已。這一些障眼法在密碼學分析上都是多表替換的結果。

而到了弗裡德曼這裡,他們已經可以在不藉助於任何外部信息的基礎就將加密方式準確分類了,不再像圖靈團隊們還需要依賴一點外部線索才可以展開工作,弗裡德曼揭露的是任何機械式密碼的根本屬性,只要是機械式加密,弗裡德曼的理論就可以派上用場。

在破譯密碼這方面,弗裡德曼的境界要高出圖靈太多!他們在數學頻率統計基礎上通過縝密細緻的觀察,就從密文裡分析了各種各樣的重要信息,並最終破譯。弗裡德曼團隊發現的這套終極破譯理論也是人類密碼分析史上最大的成就之一。

機械輪盤加密本質上都是多表替換加密

按道理說,如果這是其他科學領域有了這麼偉大的發現,那毫無疑問帶來的是榮譽和財富,但是這裡是密碼領域,密碼分析幾乎等同於軍事機密啊。因此弗裡德曼團隊沒辦法申請專利,只能默默地服務於美國陸軍。

在1956年,美國國會真的要給弗裡德曼一筆補償了,於是給了他10萬美元,以此來獎勵他的傑出工作。然而,弗裡德曼的工作在戰爭時期的價值豈是十萬美元就可以補償的!

理論上不可破譯的密碼 量子加密

今天的密碼被用在了我們知道的幾乎所有領域,商業,軍事,支付,區塊鏈等等。

可以說是密碼確保了我們現在的生活是如此的安全可靠。

今天的密碼科學仍然在不斷進步著,現在的量子密碼已經被證明是一種理論上永遠不可破譯的密碼了。

可能弗裡德曼那個針對於機械式密碼的終極解決方案已經不再具有實踐性了,但是人們會永遠紀念那些默默奮鬥在密碼破譯前線的科學家們!

徐曉亞然獨家授權,禁止轉載,違者投訴

高中數學教研QQ群 :807237820

點「閱讀原文」加入高中數學教研群

相關焦點

  • 從果粉眼裡的破譯明星池步洲談談常凱申手下的密碼破譯
    李直峰是破譯專家,但是並不懂日語,所以才能凸顯池步洲的用處。但是問題是,霍實子不僅僅是組長,而且聰明過人,更麻煩的是霍實子精通日語,池步洲在他手下只能打下手,凸顯不出這位破譯珍珠港密電的長處了。破譯密碼來說,懂不懂被破譯一方的語言並不是必要條件,比如英國的圖靈,德語就不怎麼靈;美國的羅切福特倒是去日本進修過日語,深入學習了好幾年,還在美國駐日本大使館幹過翻譯。
  • 講述電影《模仿遊戲》:男子用一生研究破譯密碼機器,最後卻自殺
    克里斯多福很欣賞圖靈的才能,總是以自己的方式去鼓勵他,兩人經常在上課的時候寫暗語傳紙條,在這次放假之前兩人也用暗語約定了開學後再見。然而開學後圖靈卻永遠地失去了克里斯多福的消息。過了不久校長將圖靈交到辦公室,在詢問他與克里斯多福之間的關係的同時也告訴他有人去世的消息。
  • 偉大的圖靈與恩尼格碼的對決,最終勝利者為何英年早逝?
    有人說,頂級數學家的能力可以用「恐怖」來形容,那麼,數學天才艾倫·麥席森·圖靈與恩格尼碼的對決就是這樣一個「恐怖」過程。恩格尼碼不是一個人,而是一個密碼機。這個密碼機在二戰殺了很多人,而圖靈就是這個密碼機的終結者。
  • 看完《模仿遊戲》圖靈的一生,讓你愛上數學!
    在二戰期間,盟軍召集了許多優秀的數學家破譯德國的「英格瑪」系統,獲得敵方的軍事秘密,從而扭轉現在局勢。政府召集許多優秀數學家進行破譯,因為是純手工計算,有無數種可能,需要花費大量時間,而密碼每天都會更新,根本不可能計算出來。
  • 寶媽趁此破譯了美國高難度密碼,獲百萬獎勵
    有這樣一位厲害的寶媽,她月子裡無聊,便去破解密碼了!坐月子太無聊?寶媽趁此破譯了美國高難度密碼,獲百萬獎勵王小雲從小就比較聰明,對數學尤為感興趣,高考成績很是優異,因為不想去外省,所以她選擇了山東大學的數學系,她的數學老師是非常著名的數學家潘承洞,王小雲也是潘承洞的第一位女學生。
  • 艾倫·圖靈:機器智能與人類思維邊界的孤獨守望者
    圖靈的數學天賦得到了充分的施展,克裡斯的遺物《數學之樂》讓他接觸了密碼的基礎理論,讓他走入了無窮樂趣的數學世界。圖靈每年都獲得數學獎學金,而劍橋此時是科學世界的中心,各領域的大師林立,圖靈選擇了象徵著學生能力的多科目學位攻讀項目(比正常的獲得學位方式多考數門高級學科)。
  • 圖靈「打敗」霍金麥克斯韋盧瑟福,登上新版50英鎊,榮耀比肩牛頓
    △ 圖片來自《獨立報》除了僅在蘇格蘭和北愛爾蘭流通的100英鎊,50英鎊是紙幣中面額最高的。印在鈔票正面的人物是英國女王伊莉莎白二世,目前流通的這一版50英鎊鈔票上,背面的人物是蒸汽機的發明者詹姆斯·瓦特,以及瓦特的合伙人、讓蒸汽機得以量產的企業家馬修·博爾頓。
  • 她兩度破譯「白宮密碼」,獲 771 萬獎金
    在高中學習時,王小雲的數學和物理成績一直遙遙領先,同學們都叫她「天才」。1983年,王小雲憑藉優異的成績考入山東大學的數學系學習。在大學期間,有一次老師給布置了一道數學難題,同學們至少花一個月時間解決,王小雲僅用一個星期就找出了最優解法。
  • 遺傳密碼的破譯史
    從1953年提出遺傳密碼到1966年破譯全部遺傳密碼,期間反覆經歷了抽象的理論分析和巧妙的實驗驗證,很值得我們總結和學習。
  • 英選定5所大學領導圖靈研究所
    原標題:英選定5所大學領導圖靈研究所  科技日報倫敦2月7日電 (記者鄭煥斌)英國商業、創新和技能大臣文斯·凱布爾日前宣布,為了強化英國在大數據和算法研究方面的領先地位,已選定5所大學來領導大數據研究機構——圖靈研究所。   5所入選的大學為:劍橋大學、愛丁堡大學、牛津大學、華威大學和倫敦大學學院。
  • 數論與密碼
    因此,英軍迅速在倫敦北邊不到一百公裡處徵集了一塊空曠的土地(該地名為布萊克利公園,後也成了該秘密機構的名字),並在那裡集結起一大批傑出的數學家、語言學家和象棋大師等,包括現代計算機科學的開山鼻祖圖靈和後來在愛丁堡大學創辦世界上第一個人工智慧系的米基(D.Michie)。他們專門負責截獲、破譯愛尼格瑪密碼。
  • 影視賞析 | 卸去「人工智慧之父」,他是一個有血有肉的「圖靈」——《模仿遊戲》
    若非是計算機領域的研究者,圖靈可能只是計算機歷史上的光輝偉人,很少有人知道他在計算機與人工智慧上的成就,也不知道他在二戰期間破譯密碼做出的貢獻,「圖靈」兩個字經過幾十年的沉澱,逐漸被符號化,所以今天我們分享的這部電影就是一部人工智慧之父的傳記
  • 4個終於被破譯的世界級密碼
    很多時候,一個設計精巧的密碼就像數學難題一樣,許許多多難以破解的密碼讓人青絲泛白,至今仍未見天日。不過,也有一些密碼中的幸運兒,最終仍然迎來了真相大白的那天。秘密組織的手抄本密碼這份超過 75000 個字母的手抄加密文件名叫 「Copiale cipher」。
  • 中途島海戰破譯日軍密碼的美軍功臣授勳內幕
    珍珠港事件後,美國海軍痛感情報的重要,開始大力加強情報收集分析和密碼破譯工作,海軍動用了它全部情報部門的力量,通過破譯JN-25b來了解日軍的動向;這裡面主要有:海軍菲律賓情報站STATION CAST、夏威夷情報站 STATION HYPO、華盛頓的海軍部情報處OP-20-G,也叫 STATION NEGAT,「N」,是代指 NAVALDEPARTMENT,海軍部。
  • 歷時百年都無人能解的密碼,是一封英國作曲家給一位女士的信
    此時大家會忍不住爆粗口:「誰XX發明的密碼¥%@%&%……」那麼,現代密碼的創始人是誰?他又在怎樣的機緣巧合下創造了密碼呢?現代計算機密碼誕生記如今被人們重視和想著用各種方式謹防被盜的「密碼」,在最初只是某個更重要發明的附屬產物。
  • 圖靈成50英鎊新鈔人物,傳奇人生照亮未來
    圖靈1936年關於可計算書的論文中的表格和公式;圖靈設計的自動計算引擎(ACE)試驗機,也是最早的計算機之一;圖靈破譯Enigma密碼系統的工具Bombe的圖紙;圖靈1947年在布萊切利公園訪客簿上的籤名;旁邊印刷的磁帶條上還有圖靈生日19120623的二進位編碼。
  • 遺傳密碼的破譯
    破譯遺傳密碼實際上就是要找到基因中DNA的鹼基順序與其編碼的蛋白質胺基酸順序的對應關係:幾個鹼基決定一個胺基酸?哪幾個鹼基決定哪種胺基酸?要判斷哪個三聯體密碼決定哪種胺基酸,首先需要一種人工合成RNA的方法和一個能夠在體外合成蛋白質的實驗系統,這樣,在試管中加入已知序列的RNA,再通過分析新合成的蛋白質產物的胺基酸排列順序就可以推斷密碼子和胺基酸的對應關係。
  • 人工智慧之父——圖靈的傳奇人生
    圖靈當時在劍橋大學攻讀數學碩士學位,正在研究可計算性理論,並將在接下來的幾個月中發表他現在著名的論文「 論可計算數及其在判定性問題上的應用」。圖靈去了兩次美國,第一次是在1936年,第二次是在1942年。他第一次是為了攻讀數學研究生,第二次是在布萊切利公園擔任英國密碼分析師團隊的聯絡員。這篇文章旨在敘述他在那裡的一些經歷。
  • 【活動設計】《破譯情緒密碼》
    可以說,情緒就像是住在我們大腦裡的特工,不斷地為我們收集、傳遞著各種訊息,只是這些訊息通常都是加密的,不那麼容易被我們直觀地讀懂,這便需要我們做個有心人,對情緒密碼進行破譯,這樣才能更好地了解我們的情緒,接納情緒、發揮情緒的力量,不斷地促進劑生命的進步與成長。那麼今天,就讓我們一起來做情緒密碼的破譯員,一起破譯情緒密碼。