數學漫談 10

密碼學

古典密碼

In [2]:
def rot(x, n):
    return chr((ord(x)-ord('A')+n)%26+ord('A'))
def ROT(s, n):
    return "".join(rot(x,n) for x in s)
ROT('HELLO', 13)
Out[2]:
'URYYB'

據說,斯巴達司令派人给前線送一條腰带:<</p>

KGDEINPKLRIJLFGOKLMNISOJNTVWG

指挥官拿到後,把它纏缠在一根木棍上,得到明文“Kill King”,如下:

KGDEINPKLRIJLFGOKLMNISOJNTVWG

蘇格蘭的瑪麗女王

西元1578年,瑪麗女王被伊莉莎白女王軟禁。在1586年1月6日瑪麗收到一批秘密信件,得悉了安東尼·貝平頓(Anthony Babington)的計劃。安東尼和幾個同黨在密謀營救瑪麗,並計劃行刺伊莉莎白女王。他們的信件被轉成密碼,並藏在啤酒桶的木塞以掩人耳目。但卻被英格蘭大臣華興翰(Walsingham)的從中截獲、複製、還信入塞,並由菲力普.馬尼斯(Philip van Marnix)破解信件。信件破解後,華興翰使菲力普摹擬瑪麗的筆跡引誘安東尼行動,把叛逆者一網成擒,審判並處死瑪麗女王。問題在於錯誤地使用脆弱的加密法會製造虛假的安全錯覺:安東尼對他們的通訊方式太過有信心,令他的加密方法過於簡單,輕易被敵人破解。

第一次世界大戰

1914年8月25日德國的馬格德堡巡洋艦(Magdeburg)在芬蘭灣(Gulf of Finland)擱淺,俄國搜出多份德國的文件及兩本電碼本,一本被送往英國的「40號房間」(Room 40)進行密碼分析。同時,無線電的發明亦使得截獲密信易如反掌。由於德國通往美國的電纜在大戰開始時被剪斷了,德國借用了美國的海底電纜發電報到華盛頓,但電纜經過了英國,1917年1月17日齊默爾曼電報被「40號房間」截獲。同年2月23日,密電內容揭開了,內容指德國將在1917年2月1日開始『無限制潛艇戰』,用潛艇攻擊戰時包括中立國在內的海上商運船。為了阻止美國因此參戰,德國建議墨西哥入侵美國,並承諾幫助墨西哥從美國手中奪回得克薩斯、新墨西哥和亞利桑那三州。德國還要墨西哥說服日本共同進攻美國,德國將提供軍事和資金援助。密電內容揭開後,美國在4月16日向德國宣戰。

第二次世界大戰

德國汲取了第一次大戰的教訓,發展出以機械代替人手的加密方法。雪畢伍斯(Arthur Scherbius)發明了「謎」(ENIGMA,恩尼格玛密码机),用於軍事和商業上。「謎」主要由鍵盤、編碼器和燈板組成。三組編碼器合、加上接線器和其他配件,合共提供了種一億億種編碼的可能性。1925年,「謎」開始有系列生產,在20年間,德國軍方購入了3萬多台「謎」,亦難倒了「40號房」,成為德國在二次大戰的重要工具。波蘭位於德國東面,俄國的西面,一直受到威脅,故成立了波蘭密碼局(Biuro Szyfrow)以獲取情報。波蘭從漢斯-提羅.施密德(Hans-Thilo Schmidt)處得到諜報,由年輕的數學家马里安·雷耶夫斯基(Marian Rejewski)解譯,用了一年時間編纂目錄,並在1930年代製造了「炸彈」(bomba),漸漸掌握瞭解「謎」的技術。

1938年12月德國加強了「謎」的安全性,令波蘭失去了情報。「謎」成為了希特勒(Hitler)閃電戰略的核心,每天更改的加密排列維繫了強大快速的攻擊。 1939年4月27日德國撤銷與波蘭的互不侵犯條約,波蘭才不得不決定把「炸彈」這個構想與英、法分享,合力破解新的「謎」。1939年9月1日,德國侵擊波蘭,大戰爆發。英國得到了波蘭的解密技術後,40號房間除了原有的語言和人文學家,還加入了數學家和科學家,後來更成立了政府代碼曁密碼學校(Government code and Cipher School),5年內人數增至7000人。1940至1942年是加密和解密的拉鋸戰,成功的解碼提供了很多寶貴的情報。例如在1940年得到了德軍進攻丹麥和挪威的作戰圖,以及在不列顛戰役(Battle of Britain)事先獲得了空襲情報,化解了很多危機。但「謎」卻並未被完全破解,加上「謎」的網絡很多,令德國一直在大西洋戰役中佔上風。最後英國在「順手牽羊」的行動中在德國潛艇上俘獲「謎」的密碼簿,破解了「謎」。英國以各種虛假手段掩飾這件事,免得德國再次更改密碼,並策劃摧毀了德國的補給線,缩短了大西洋戰役的持续时间。

公鑰密碼學

Diffee-Hellman 1976

已知 $B = g^b $

很難從 $B$, $g$ 得到 $b$ 的資訊

In [15]:
from gmpy2 import next_prime, powmod, invert
from random import randint
Alice , Bob = {}, {}
p = next_prime(1000000)
g = 3
from IPython.display import Math, Latex
Latex("$p=%d$ and $g=%d$"%(p,g))
Out[15]:
$p=1000003$ and $g=3$
In [32]:
Alice = {"a": randint(1, p-1)}
A = powmod(g, Alice['a'], p)
Latex("$A = g^a = %d$"%(Alice['a']))
Out[32]:
$A = g^a = 212417$
In [30]:
eval("powmod(g,a,p)", None, Alice)
Out[30]:
mpz(576932)
In [17]:
Bob['b'] = randint(1, p-1)
B = powmod(g, Bob['b'], p)
print("B=",B)
B= 423936
In [18]:
print(powmod(A, b, p), powmod(B, a, p))
67431 67431

RSA

產生公鑰和私鑰

  • 隨機選兩個大質數 $p$ 和 $q$,計算 $N=pq$
  • $r=(p-1)(q-1)$
  • 隨機選 $e < r$ ,並求得 $d$ 使得 $ ed \equiv 1 (\mod r)$

$(N, e)$ 是公鑰

$d$ 是私鑰

In [23]:
from gmpy2 import invert
def generate_keys():
    p = next_prime(randint(100000,200000))
    q = next_prime(randint(100000,200000))
    N = p*q
    r = (p-1)* (q-1)
    e = randint(2,r-1)
    d = invert(e, r)
    return N, e, d
N, e, d = generate_keys()
print(N, e, d)
29525450761 18443871385 11416876585

加密

In [25]:
m = 12345678
c = powmod(m, e, N)
print(c)
12412927935

解密

In [26]:
x = powmod(c, d, N)
print(x)
12345678

因為費瑪定理的關係

在 $\mod N $ 下

$ n^r \equiv 1 $

$(n^e)^d \equiv n^{ed} \equiv n^{\alpha\cdot r+1} \equiv n$

In [29]:
print(powmod(7,e*d, N))
7

ElGamal

生成公鑰、私鑰

In [57]:
p = next_prime(1000000000) # 公鑰
g = 3              # 公鑰
x = randint(2, p-1) # 私鑰
h = powmod(g, x, p) # 公鑰

加密

In [65]:
m = 31415926
y = randint(2, p-1)
s0 = powmod(g, y, p)
s1 = powmod(h, y, p)
print("s1=", s1)
c = (s0, m*s1)
print(c[0], c[1])
s1= 39744455
753187146 1248608857190330

$ c = (g^y, m\cdot h^y) = (g^y, m\cdot g^{xy})$

解密

In [66]:
s1 = powmod(c[0], x, p)
print("s1=", s1)
solution = c[1] * invert(s1, p)  % p
print(solution)
s1= 39744455
31415926

打電話丟銅板

電子簽章

Zero-knowledge proof

量子危機