百家號不支持代碼格式,文章裡的代碼排版都是亂的。
如果需要拷貝代碼,可以去同名微信公眾號。
上篇說到,李雷自以為想到了一個絕妙的辦法。
對信件的內容進行加密,就可以躲過父母的監控。但是沒想到的是,他的加密方法很快就被爸爸破解了。
究其根源在於,「凱撒加密」的有效秘鑰實在是太少了。
表面看上去,「凱撒加密」的秘鑰可以有無限多個,但其實真正有效的只有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解密吧。