25.Python密碼學入門之四:仿射加密

2021-01-10 和孩子一起學Python

百家號不支持代碼格式,文章裡的代碼排版都是亂的。

如果需要拷貝代碼,可以去同名微信公眾號。

上篇說到,李雷自以為想到了一個絕妙的辦法。

對信件的內容進行加密,就可以躲過父母的監控。但是沒想到的是,他的加密方法很快就被爸爸破解了。

究其根源在於,「凱撒加密」的有效秘鑰實在是太少了。

表面看上去,「凱撒加密」的秘鑰可以有無限多個,但其實真正有效的只有26個。

比如秘鑰 key = 1 和 秘鑰 key = 27 效果是一樣的,都是把字母向後平移1位。

為什麼「凱撒加密」只有26個有效秘鑰,根源其實在於,它只是把26個字母完整地進行平移,而不打亂26個字母的順序。

如果打亂順序呢?

簡單替換加密

比如下面的表格,明文的每一個字母,都沒有規律地任選一個其它字母和它對應。

當然,不要出現多個明文字母對應同一個密文字母。

在密碼學上,這種加密方式被稱為「簡單替換加密」。

它的有效秘鑰有多少種呢?

對於明文字母A,它對應的密文字母有 26 種可能。(我們認為密文字母也為A也是可以的)

當A選擇好了一個密文字母後,明文字母B就只剩下25種可能了。

以此類推,可以得知

簡單替換加密的有效秘鑰有 26!種。

26! = 403291461126605635584000000

這是一個非常非常大的數字了。

使用暴力破解是不可能的。

但「簡單替換」是不是就是牢不可破的加密方法呢?

其實也不是的,後面我們會介紹一種巧妙的辦法來破解「簡單替換加密」。

不過,現在李雷碰到的問題是。

這種加密方法不方便描述。它的秘鑰太長了!

Jim也不敢在爸爸眼皮底下拿出小紙條,一個字母一個字母地讀給Kate。

所以這種方法行不通。

那有沒有別的方法,可以讓字母的映射是亂的,但又是可以通過一個簡單的秘鑰計算出來呢?

乘數加密

在電腦裡,每個字母都會對應一個數字。

而這個數字由2部分組成,我們不妨稱為 基礎數+補充數。

大寫字母的基礎數是 65,如字母B對應的數字是 65 + 1。

小寫字母的基礎數是 97,如字母b對應的數字是 97 + 1。

「凱撒加密」的數學含義是

密文字母 = 明文字母的 基礎數 + (補充數 + 秘鑰) % 26

使用的是加法之後取餘數。

能不能把加法換成乘法呢?

密文字母 = 明文字母的 基礎數 + (補充數 * 秘鑰) % 26

看上去也是可行的,因為(補充數 * 秘鑰) % 26也在[0,25]範圍裡。

不過乘法加密並不像加法那麼簡單。

不妨來看一個小例子,假設秘鑰 key = 8。

對字母F(65+5),和 S(65+18)加密。

(5 * 8 )% 26 = 40 % 26 = 14

(18* 8 )% 26 = 144% 26= 14

也就是說,F 和 S 經過加密之後,得到的結果都是 O。

如果Kate看到密文裡有一個字母O,她不知道對應的明文是F還是S。

什麼秘鑰才能確保不同的明文字母算出來的密文字母都是不同的呢?

答案就是這個秘鑰必須26互為質數。

這裡面的數學原理就先不展開了。有興趣的話可以百度。

比如秘鑰為3,5,7,11……都可以。

仿射加密

乘數加密還有一個小小的缺點。

無論秘鑰是什麼,字母A加密之後始終還是A。

所以,我們很少直接使用乘數加密,而是在乘數加密之後再使用「凱撒加密」進行平移。這種結合的加密方式稱為仿射加密。

所以,仿射需要2個秘鑰,第一個秘鑰是乘數,第2個秘鑰是加數。

仿射的Python實現只需要在「凱撒加密」的基礎上稍做修改。

凱撒加密:

基礎數 +(補充數 + 秘鑰) % 26

仿射加密:

基礎數 + ((補充數 * 乘數秘鑰) % 26 + 加數秘鑰)

f_read = open('data/letter.txt')

content = f_read.read()

target = ''

key1 = 5

key2 = 3

for i in range(len(content)):

tmp = content[i]

num = ord(tmp)

if tmp.isalpha():

if ord(tmp) < 97:

target += chr( 65 + (((num - 65)*key1) % 26 + key2) % 26 )

else:

target += chr( 97 + (((num - 97)*key1) % 26 + key2) % 26 )

else:

target += content[i]

f_read.close()

Kate如何解密

還是要靠Jim通過電話告訴Kate使用新的加密方法。

當然,我們得假設Kate明白什麼是仿射加密。

這樣,Jim只需要壓低聲音說「仿射加密,乘數秘鑰5,加數秘鑰3」就可以了。

不過仿射加密的解密要更複雜,原因是其中的乘數加密的解密更複雜。

以字母 Y (65+24) 為例

對於凱撒加密,我們用加法來加密,減法來解密。

假設秘鑰是3,加密得到 65+(24+3)%26 = 65+1,得到字母B。

對字母B解密, 65 + (1-3)%26 = 65 + 24 ,得到字母 Y。

但對於乘數加密,我們用乘法來加密,卻不能用除法來解密。

假設秘鑰是5,加密得到 65 + (24*5)%26 = 65+16 ,得到字母Q。

對字母Q解密,65 + (16/5)%26 = 65 + 3.2,顯然是錯誤的。

如上,24 經過 秘鑰 5 加密後得到了 16

那 16 怎麼解密才能得到 24呢?

這是一個複雜的數學問題。

為了理解,我們先用一些字母來表示這些數字。

需要被加密的數字設為 X ,也即 24。

秘鑰設為 K ,也即 5。

加密得到的結果設為 Y ,也即 16。

被除數設為M,也即 26。

當已知 X,K,M

Y = (X*K )% M

也即,16 = (24*5)%26

但是,如果知道 Y,K,M,要求X

X ≠ (Y ÷ K )% M

也即 24 ≠ (16÷ 5 )% 26

那要怎麼求呢?

假設存在這麼一個數 I,使得

X = (Y * I ) % M

這裡的變量 I 被稱為 K 取模 M 的模逆。

也即 I 是 5 取模 26 的模逆。

所以,我們就是要把這個 I 求出來。

求 I 的辦法只需要先記著這個等式 ( I * K ) % M == 1

至於這個等式是怎麼來的,還是和歐幾裡得算法相關,這裡也先不展開。

根據等式,於是就可以從1開始找 I

(1 * 5 ) % 26 = 5

(2 * 5 ) % 26= 10

(3 * 5 ) % 26= 15

……

(21 * 5) % 26 = 1

所以, I 就是 21。

這樣,我們就可以通過 I 來計算 X 了。

X = (Y * I )% M = (16 * 21) % 26 = 24

答案是正確的。

用Python幫Kate解密吧

Jim告訴Kate,李雷用仿射加密對信的內容進行了加密,乘數秘鑰是7,加數秘鑰是5。

請用Python幫Kate解密吧。

相關焦點

  • 吳軍:《數學之美》中的密碼學原理,古代密碼學和現代密碼學
    在《數學之美》的第17章,吳軍由於很喜歡電視劇《暗算》的構思和演員的表演,給我們科普了密碼學原理。密碼學聽起來很神秘,也比較有趣,那麼密碼學原理究竟是什麼?古代密碼學和現代密碼學又有什麼區別呢?古代密碼學在現代體育競技還有著廣泛的應用。比如我們經常看到籃球或足球比賽中,同隊運動員相互之間打手勢布置戰術就是。1871年,上海大北水線電報公司選用了6899個漢字,代以四碼數字,成為中國最初的商用明碼本,同時也設計了由明碼本改編為密本及進行加亂的方法。在此基礎上,逐步發展為各種比較複雜的密碼。
  • 29.Python密碼學入門之八:手把手破解維吉尼亞加密後的英文詩
    同時,也不能像破解簡單替換加密那樣,通過計算字母出現的頻率,和字母的單詞模式來破解,因為經過維吉尼亞加密之後,字母頻率和單詞模式都變化了。上一篇的最後,給了一首經過維吉尼亞加密之後的英文詩,這一篇,我們就來演示如何來破解這首詩。
  • 默克爾樹創始人談加密貨幣和量子時代密碼學
    與公共密鑰密碼學先驅拉爾夫·默克爾(Ralph Merkle)博士,以了解下一代量子抗性密碼標準如何幫助區塊鏈加密保持安全。問:拉爾夫,讓我們從您的背景開始:作為公鑰密碼學和密碼哈希技術的發明者之一,您的工作對於現代網際網路的安全至關重要。考慮到此成就的全球範圍和實用性,創建對數據身份驗證和加密如此重要的內容的感覺如何?答:很顯然,擁有一件已經被廣泛使用並且會隨著時間的流逝而被更廣泛使用的作品,感覺很棒。隨著我們繼續進入數字時代,對於密碼學的身份驗證和隱私而言,事情只會越來越好。
  • 什麼是後量子密碼學?
    量子密碼學對經典公鑰密碼學意味著什麼?量子密碼學可以解決什麼問題。什麼是後量子密碼學?在前一篇文章中,討論了量子計算機的出現對經典公鑰密碼學意味著什麼。我們現有部署的所有公鑰技術都基於大整數分解或求解離散對數問題。
  • 如何快速學會Python爬蟲(入門篇)
    一、爬蟲入門Python爬蟲入門一之綜述2.Python爬蟲入門二之爬蟲基礎了解3. Python爬蟲入門三之Urllib庫的基本使用4. Python爬蟲入門四之Urllib庫的高級用法5. Python爬蟲入門五之URLError異常處理6.
  • python安全開發軍規之四:使用安全的隨機數生成器
    實際上,在密碼學上對隨機性有三個分類:偽隨機序列,密碼學意義上的偽隨機序列,真隨機序列。前面小Z寫的程序就類屬於偽隨機序列,1-100中每個數出現的頻率相等或近似相等。而真隨機序列則要求隨機數不能重複產生,且不能由已知的任意數推導出來。
  • python入門基礎之lambda匿名函數詳解
    python入門基礎之lambda匿名函數詳解剛開始學習python的時候很多人可能對於lambda函數不了解,感覺和def很混亂,下面我來介紹一下lambda函數我從一下幾個方面來介紹lambda:1、lambda簡介2、lambda與def不同之處3、lambda的使用方法1、lambda簡介先來看一段代碼示例:
  • 仿射變換(二)—仿射變換在解題中的應用
    仿射變換在解決與橢圓相關的面積問題,特別是面積的最值問題,以及對某些幾何的轉化中有很好的應用,有時可以大大地簡化計算,或將一些題目中隱藏的「平凡」的條件轉化成對解題很有利的「特殊」條件.在仿射變換(一)—什麼是仿射變換中,我們已經知道,對橢圓 應用仿射變換
  • 科技:量子密碼學中的量子效應
    【科技:量子密碼學中的量子效應】導語:通信,電話交談或電子郵件:任何通信都可以錄音。密碼學的目標,加密科學是為了使間諜的生活儘可能地困難。現代加密方法適用於隨機生成的一次性密鑰。因此,也難怪的加密信息,稱為加密的科學,是幾乎一樣古老人類自身。在古希臘使用的斯巴達Skytale過程中,凱撒替換和二戰期間所扮演的著名Enigma密碼機起著重要作用。現代密碼系統由密鑰和算法兩部分組成。該算法描述了如何將密鑰應用於源信息。例如,在文本的情況下,算法可以是字母的替換,然後鍵將指示正在交換哪個字符。
  • 美國是如何發展後量子密碼學的?
    &34;Misoczki是報名參加8月22日至25日在加州大學聖巴巴拉分校舉行的第二屆PQC標準化會議的250多名註冊與會者之一。此次活動中,幾乎所有從事26種候選算法的團隊都做了演講,這些算法是從69個第一輪候選算法中篩選出來的。NIST希望這些第二輪候選算法的發展能超越單純的概念驗證,並開始進行基準測試。
  • Python開發簡單爬蟲【學習資料總結】
    使用HTTPCookieProcessor; 需要代理才能訪問的網頁使用ProxyHandler; 需要HTTPS加密訪問的網站使用HTTPSHandler; 有些URL存在相互自動跳轉的關係使用
  • 量子密碼學的誕生
    密碼學最早可追溯到幾千年前,《六韜》中曾記載,早在周朝時就有通過「陰符」和「陰書」加密傳遞信息的做法。
  • python基礎教程之python是什麼?
    這是最近10年最常用的10種程式語言的變化圖:python是什麼--python的功能總的來說,這幾種程式語言各有千秋。龜叔給Python的定位是「優雅」、「明確」、「簡單」,所以Python程序看上去總是簡單易懂,初學者學Python,不但入門容易,而且將來深入下去,可以編寫那些非常非常複雜的程序。總的來說,Python的哲學就是簡單優雅,儘量寫容易看明白的代碼,儘量寫少的代碼。
  • 區塊鏈中的密碼學系列之對稱加密算法DES(六)
    Feistel網絡的解密結構:Feistel解密過程本質上與加密過程一樣。密文作為輸入,使用子密鑰Ki的次序與加密過程相反, Kn,Kn-1,…,K1。保證了加密與解密過程可採用同一算法。3. DES算法框架輪函數:Li=Ri-1;Ri=Li-1⊕f(Ri-1, Ki)。4.
  • 幾何運算-仿射變換
    仿射變換,實際就是對圖像、區域、XLD輪廓等的平面坐標進行平移、縮放、旋轉後,得到新的平面坐標
  • 知識來了 | ECC橢圓曲線密碼學簡介
    加密和解密的各種操作必須在消息之間進行變換,以使變換服從有限消息空間內部的封閉性。然而,數的一般運算諸如加減乘除並不滿足有限空間內部的封閉性。所以密碼算法通常運行於具有某些保持封閉性的代數結構的空間中,這種代數結構就是有限循環群。在數學中,群是一種代數結構,由一個集合以及一個二元運算組成。群必須滿足以下四個條件:封閉性,結合律,存在單位元和存在逆元。
  • 《小灰教你零基礎學python》-Python入門語言
    程式語言有很多,咱們就學簡單強大的python即可。三、python程式語言介紹Python是荷蘭人吉多·范羅蘇姆(Guido van Rossum)在1989年聖誕節期間開發的一門解釋性的腳本語言,什麼是解釋性的語言,大家可以參照百度百科(
  • 玩轉Python 中的隨機數
    開發中我們經常遇到需要隨機數的場景,比如為了用戶密碼更安全我們有時會加鹽,也就是將用戶原密碼連接上一串隨機字符然後加密保存,又比如我們可能需要隨機展示某張圖片等等。今天,我們就來理一理 Python 中的隨機數的玩法,當然,這裡只涉及標準庫。
  • 數據加密中的DES加密算法詳解
    [摘要] 本文詳細介紹了DES數據加密算法的原理,並給出了一個例子演示了如何使用c#中的加密包進行DES算法加密,最後對DES進行了評價。信息加密技術是一門涉及數學、密碼學和計算機的交叉學科。現代密碼學的發展,使信息加密技術已經不再依賴於對加密算法本身的保密,而是通過在統計學意義上提高破解的成本來提供高加密算法的安全性。密碼學是一門古老而又年輕的科學,它用於保護軍事和外交通信,可追溯到幾千年前。1976年Diffie和Hellman的「密碼學的新方向」一文引發的密碼學的一場革命,開創了公鑰密碼學的新紀元。