本文作者 [遇見(jiàn)數(shù)學(xué)] 核心成員: 蘑菇長(zhǎng)頸鹿

同余運(yùn)算(請(qǐng)見(jiàn)下面鏈接)在經(jīng)典的密碼問(wèn)題中也發(fā)揮著至關(guān)重要的作用，在下面文章中我們將會(huì)把密碼學(xué)與同余運(yùn)算兩者結(jié)合起來(lái)，探索同余運(yùn)算是怎樣運(yùn)用到密碼學(xué)中的。

你所想知道密碼背后的數(shù)學(xué)——同余運(yùn)算, 你所想知道密碼背后的數(shù)學(xué)——同余運(yùn)算 Part II

密碼學(xué)的起源

想象一下，Alice 和 Bob 兩個(gè)人要遠(yuǎn)距離的分享了一個(gè)重要的秘密。然而，一個(gè)叫 Eve 的竊聽(tīng)者也想要這些信息，并且有能力截獲他們的消息。所以，Alice 決定用某種密碼寫(xiě)的信來(lái)交流。首先，Alice 用一個(gè)只有她和 Bob 知道密碼的鎖將消息鎖在一個(gè)盒子里。這就是所謂的“加密”（encryption）。

愛(ài)麗絲(Alice)和鮑伯(Bob)在密碼學(xué)中是最基本的兩位代用人物，其次是伊夫(Eve)。頭一個(gè)英文字母越接近 z，該角色的使用率相對(duì)上也越低。

然后，將被鎖的信息發(fā)送給鮑勃。當(dāng) Bob 收到盒子時(shí)，他使用他們預(yù)先共享的鑰匙打開(kāi)盒子。這叫做“解密”（decryption）。

當(dāng)我們放棄物理鎖而使用“密碼”時(shí)，密碼學(xué)就要登場(chǎng)了。我們可以將密碼看作虛擬鎖。密碼使 Alice 和 Bob 能夠?qū)λ麄兊男畔⑦M(jìn)行整理和解碼，這樣，如果 Eve 截獲它們，它們就會(huì)顯得毫無(wú)意義。

一般來(lái)說(shuō)，如果我們可以將整個(gè)加密系統(tǒng)看作一個(gè)模型

凱撒密碼

第一個(gè)眾所周知的密碼是一個(gè)移位密碼，大約在公元前 58 年被凱撒大帝使用。它現(xiàn)在被稱為凱撒密碼。凱撒把他的軍事命令中的每一個(gè)字母都做了調(diào)整，以便在敵人攔截的時(shí)候讓它們顯得毫無(wú)意義。

想象 Alice 和 Bob 決定使用凱撒密碼進(jìn)行通信。首先，他們需要在轉(zhuǎn)換使用之前達(dá)成一致，比如轉(zhuǎn)換為 3。因此，為了加密她的消息，Alice 需要對(duì)原始消息中的每個(gè)字母進(jìn)行移位 3 次。 A 變成了 D，B 變成了 E，C 變成了 F，等等。

▲ 當(dāng)偏移量是 3 的時(shí)候，所有的字母 A 將被替換成 D，B 變成 E，以此類推。(圖自維基)

這條加密的消息然后公開(kāi)發(fā)送給 Bob。然后 Bob 簡(jiǎn)單地從每個(gè)字母中減去 3 的移位，以讀取原始消息。這個(gè)基本密碼在凱撒之后的幾百年里被軍事領(lǐng)導(dǎo)人使用。

這種移位密碼的工作方式是使用模運(yùn)算對(duì)消息進(jìn)行加密和解密。移位密碼的密鑰 K 是從 0 到 25 的整數(shù)。

對(duì)于消息中的每一個(gè)字母:

例如：我們同意我們的朋友使用密鑰 K=19 的移位密碼作為我們的消息。我們加密信息“SECRET”，因此，在應(yīng)用密鑰 K=19 的移位密碼后，我們的消息文本“SECRET”為我們提供了密碼文本“KWUJWL”。 我們把信息“KWUJWL”發(fā)送給我們的朋友。

對(duì)于密文中的每一個(gè)字母:

我們的朋友現(xiàn)在使用我們商定的密鑰 K=19 來(lái)解碼消息。如下: 因此，在用密鑰 K=19 解密了移位密碼之后，我們的朋友將密碼文本“KWUJWL”解密為消息文本“SECRET”。

然而，一把鎖的堅(jiān)固程度取決于它最薄弱的地方。開(kāi)鎖器可能會(huì)尋找機(jī)械缺陷。如果做不到這一點(diǎn)，則提取信息以縮小正確的組合范圍。鎖的破解和密碼破解的過(guò)程非常相似。

800 年后，一位名叫阿爾·肯迪(Al-Kindi)的阿拉伯?dāng)?shù)學(xué)家出版了《凱撒密碼的弱點(diǎn)》。他利用語(yǔ)言中一個(gè)重要屬性的線索破解了凱撒密碼。如果你從任何一本書(shū)中掃描文本并計(jì)算每個(gè)字母的頻率，你會(huì)發(fā)現(xiàn)一個(gè)相當(dāng)一致的模式。例如，下面條形圖所表示就是用典型的英語(yǔ)書(shū)寫(xiě)的文字樣本中各字母出現(xiàn)頻率。

▲ 圖自維基

這條線索是密碼破譯者最有價(jià)值的工具之一。為了破解這個(gè)密碼，他們計(jì)算出加密文本中每個(gè)字母的頻率，并檢查頻率最高的字母移動(dòng)了多遠(yuǎn)。例如，如果 是加密消息中最受歡迎的字母，而不是 ，那么移位可能是 。

因此，只需要逆轉(zhuǎn)其偏移量就可以進(jìn)行解密。這樣即便是在僅知已加密文字的情況下就可以通過(guò)頻率分析，或者窮舉法就可以攻破信息，這對(duì)凱撒密碼的安全性是一個(gè)打擊。

公共密鑰

第二次世界大戰(zhàn)后，隨著歐洲大部分地區(qū)的廢墟，蘇聯(lián)和美國(guó)之間的緊張關(guān)系加劇，互聯(lián)網(wǎng)在全球范圍內(nèi)的蓬勃發(fā)展，一個(gè)新的問(wèn)題出現(xiàn)了。當(dāng)時(shí)，加密需要雙方首先共享一個(gè)稱為密鑰的秘密隨機(jī)數(shù)。那么，兩個(gè)素未謀面的人怎么可能在共享密鑰的問(wèn)題上達(dá)成一致，而又不讓一直在偷聽(tīng)的 Eve 獲得一份副本呢?

1976 年，惠特菲爾德·迪菲（Whitfield Diffie）和馬丁·赫爾曼（Martin Hellman）發(fā)明了一種神奇的方法。

首先，讓我們來(lái)看看如何使用顏色來(lái)完成這個(gè)方法。Alice 和 Bob 怎么能在一個(gè)秘密的顏色上達(dá)成一致而不被 Eve 發(fā)現(xiàn)呢?

這個(gè)方法基于兩個(gè)事實(shí):

1. 我們很容易把兩種顏色混合在一起，并形成第三種顏色;
2. 對(duì)于混合后的顏色，要想找到完全相同的原始顏色是很困難的。

即密碼要滿足朝一個(gè)方向容易，朝反方向難，也就是所謂的單向函數(shù)(One-way function)。

現(xiàn)在，我們的方案如下:

首先，他們公開(kāi)同意一種起始顏色，比如黃色。作為偷聽(tīng)者 Eve 也能成功獲取此消息，如下圖所示。?

接下來(lái)，Alice 和 Bob 都隨機(jī)選擇了私有顏色(紅藍(lán)兩色)，將它們混合到公共黃色中，以掩蓋它們的私有顏色并發(fā)送給對(duì)方，這個(gè)過(guò)程如下面圖形所示。

而后，Alice 和 Bob 將他們的私有顏色添加到另一個(gè)人的混合色中，得到一個(gè)共享的秘密顏色，下右圖為混合后顏色。

注意到偷聽(tīng)者伊芙無(wú)論如何都無(wú)法確定這個(gè)確切的顏色，因?yàn)樗枰粋€(gè)他們的私人顏色來(lái)做這件事。

這就是關(guān)鍵所在。現(xiàn)在，為了在數(shù)學(xué)上實(shí)現(xiàn)，我們就需要一個(gè)在單方向上容易計(jì)算，而在反方向上計(jì)算很困難的過(guò)程，這就是下面一節(jié)的內(nèi)容。