尋找非對稱加密常式的教學簡單範例？

（我不是密碼學專家；我會寫軟體）

我正在和一些年輕人（11-13 歲）一起工作，想探索一個小時左右的一些基本密碼學。做對稱密碼非常簡單。很容易解釋非對稱加密的各種“雙鍵”隱喻，但我發現很難找到一個很好的、易於使用的非對稱加密數學範例。有很多很好的 RSA 分解範例，但即使數字很小，由於冪函式，您也可以快速進入“大”數字。

是否有一個“玩具”算法的好例子來說明非對稱加密/解密過程？

非對稱加密：什麼？

愛麗絲希望能夠接收任何人發送的、發佈在公共網站或 whatsapp 群組上的消息，只有她能夠破譯。傳統密碼學要求發送者和她共享一些秘密（密鑰或密碼），用於加密和解密。

在非對稱加密中，Alice 生成並保存一個秘密私鑰，並公開共享一個對應的公鑰。任何擁有 Alice 的公鑰的人都可以加密給她的消息。Alice 的私鑰是解密它所必需的。

非對稱密碼學還包括數字簽名：Alice 使用她的私鑰對數據進行簽名，然後任何擁有 Alice 可信公鑰的人都可以驗證她是否簽署了該確切數據。直到 1970 年代，這一切都被認為是不可能的。它現在很常見，例如在網路瀏覽器中。

非對稱加密：如何？

它是用數學完成的。只有電腦才能真正執行計算。常用的方法之一是 ElGamal 加密。我們可以用一點 Python 來說明（一個輕微的變體）。

我們將使用 Python 的pow(a, x, n). 它計算*“a以冪x為模n”。其中，“a到次方x”是指x份數a相乘；並且“模n”*意味著我們保留除以時剩下的內容n。

舉個pow(2, 4, 10)例子。*“2 的 4 次方”*是 2×2×2×2，即 16。當我們將 16 個東西分成 10 個人時，每個人得到 1，仍然是 6。

因此，pow(2, 4, 10)收益率6。

Alice 將隨機選擇一個私鑰，並將她的公鑰計算為

PublicKey = pow(2, PrivateKey, n)。這在 Python 中既簡單又快速，但即使是最強大的電腦也認為計算PrivateKeyfrom是不可行的，when是一個足夠大的安全素數，並且是隨機且大的。通常像這樣公開。我們將使用同樣安全但更易於鍵入的東西（或線上嘗試！）：APublicKey``n``PrivateKey``n

# Setup
import secrets                      # needed for randbits
n = 2**4096 - 3**2542 + 3547696     # some public 4096-bit safe prime

# Alice generates her keys
PrivateKey = secrets.randbits(400)  # generate secret Private Key
PublicKey = pow(2, PrivateKey, n)   # compute Public Key

# Barnabé got PublicKey and wants to send a message to Alice
M = "Surprise for you in my locker, code 47918. Barnabé"
# turn M into an integer m, at most 500 bytes
m = int.from_bytes(bytes(M, 'utf-8'), byteorder='big')
assert m.bit_length()<=4000         # bark if message is too large

# encryption of m into Ciphertext
x = secrets.randbits(400)           # number used once
r = pow(2, x, n)                    # Alice need this to decipher
s = pow(PublicKey, x, n)            # shared one-time secret
c = (s%(2**4000)) ^ m               # produce ciphertext using XOR

# remove Barnabé's secrets
del M, m, x, s

# Alice receives ciphertext c and r, and deciphers that using PrivateKey
s = pow(r, PrivateKey, n)           # shared one-time secret
m = (s%(2**4000)) ^ c               # decipher using XOR
# turn integer m into a string M
M = str(m.to_bytes((m.bit_length()+7)//8, byteorder='big'), 'utf-8')
print(M)                            # show the deciphered message

# remove Alice's secrets, except her PrivateKey which can be reused
del s, m, M

s發送者在加密期間計算的值是pow(pow(2, PrivateKey, n), x, n)，Alice 在解密期間使用的值是pow(pow(2, x, n), PrivateKey, n)，並且由於它們的數學屬性pow是相同的。

摘要：使用非對稱加密，發送機密消息不需要任何秘密。我們可以使用一些巧妙的數學運算、能夠生成隨機數的可信電腦以及預期接收者的可信公鑰。

---

教學筆記

雖然我相信 17 歲的觀眾中有相當一部分能夠掌握/適應/擴展上述內容，但只有一小部分 11-13 歲的觀眾會。因此，我認為對這些年輕觀眾最好的方法是解釋非對稱加密的作用（如果可能的話，數字簽名至少同樣有用）。說明使用密鑰生成/加密/解密框，其中相應的 Python 程式碼作為小字元或被截斷，交換的值用省略號縮短，但不要深入研究程式碼的確切作用。但是可以訪問材料（原始碼），展示這是如何完成的並允許複製它。準備好的人可能會使用它。

ElGamal 加密是Diffie-Hellman 密鑰交換加密的直接轉置，這是第一個公開的非對稱密碼系統之一。它對所有正整數都使用它 $ a,n,\text{PrivateKey},x $ , $$ {\left(a^\text{PrivateKey}\right)}^x\equiv a^{\text{PrivateKey},x}\equiv a^{x,\text{PrivateKey}}\equiv{\left(a^x\right)}^\text{PrivateKey}\pmod n $$ 並且，對於 $ n $ 一個大的安全素數和大多數 $ a $ 包括 2，如果 $ x $ 和 $ \text{PrivateKey} $ 是隨機選擇的，有 $ a $ , $ n $ , $ a^\text{PrivateKey}\bmod n $ 和 $ a^x\bmod n $ 公開但 $ \text{PrivateKey} $ 和 $ x $ 是大的隨機未知數，那麼 $ a^{x,\text{PrivateKey}}\bmod n $ 被認為在計算上與隨機無法區分 $ \Bbb Z_n^* $ 除了 1 位資訊。如果我們保留一些高位位，則低位位是共享秘密，我們將其用於使用 XOR 進行對稱加密。

這不是玩具密碼學。這就是學術意義上的IND-CPA 安全非對稱加密。參數提供了非常高的安全級別。後者在教學環境中沒有任何懲罰，因為無論如何都不能手動完成計算，並且程式碼在任何執行 Python 3 的東西上都足夠快。

但是，必須注意的是，ElGamal 加密和程式碼存在嚴重的缺陷：

• 沒有什麼可以阻止 Alice 的公鑰在前往 Barnabé 的途中被篡改，這會導致攻擊。Barnabé 可能會被欺騙使用某個對手的公鑰而不是 Alice 的公鑰，然後對手可以破譯消息並訪問 Barnabé 的儲物櫃。
• 沒有身份驗證：Alice 不確定消息是否來自 Barnabé。任何人都可以對發給她的任何資訊進行加密。
• 更糟糕的是：對手可以巧妙地改變資訊並獲取一些資訊。例如：猜測消息的結尾Barnabé（因為他總是這樣做），對手可以更改密文，以便 Alice 解密的內容以不同的名稱結尾。愛麗絲可能會嘗試打開其他人的儲物櫃，但失敗了；如果對手操縱那個儲物櫃來發送 Alice 的嘗試程式碼，那麼攻擊者現在可以在 Alice 之前訪問 Barnabé 的儲物櫃。更一般地說，該方案缺乏IND-CCA2安全性。
• 沒有說明密鑰的安全儲存和密鑰分配。
• 密文發送/接收被避開。
• 程式碼沒有受到實施攻擊的保護（例如填充預言、定時和邊通道）。

小參數會限制消息大小，或者使程式碼更複雜。這也將教孩子們做出不必要的妥協（本著同樣的精神，我沒有將資訊限制為 ASCII，它的大小是經過範圍檢查的，因為我們應該盡可能培養良好的編碼習慣）。但是，可能需要使用較小的值，例如使展示程式碼適應沒有對大整數的內置支持的環境，或者實際上在紙上的個人之間轉移值。在這種情況下，可能將消息限制為 24 位（3 個字節，適用於 3 或 4 個字元），更改n為 2147481143，更改2**4000為 16777216，並使用範圍內的隨機整數

$$ 1, 1073740570 $$對於PrivateKey和x。當然，所有的安全都失去了：可程式計算器可以找到私鑰。 我沒有介紹 RSA，因為它使用了更重的數學（我們需要模反演和小費馬定理來解釋它為什麼起作用），而且 RSA 更難實現。更糟糕的是，大多數教學實現都有一個基本缺陷：可以從密文中驗證明文的猜測（例如班級名冊上的名稱）。獨立地，參數通常很小，以至於可以逐個字母地進行檢查；並且對密文重新加密一小段固定的時間就足以解密而無需任何猜測。模量也可以被分解，通常是手動的（也許使用費馬的方法）。

我的觀點是，最好不要誤導觀眾，尤其是年輕人，讓他們相信他們了解非對稱加密的工作原理，或者可以使用 10 位數字來完成。設計它需要幾個世紀的努力，那是因為它很難。

我從“想像一個每個人都可以將數字相乘，但除法非常困難的世界”開始取得了一些成功（另外還有一個算法可以用乘積 1 生成兩個數字）。加上掛鎖的類比似乎足以說明這一點。最後，我可以概述一些現實生活中難以反轉的函式的例子。

請記住，沒有多少 11-13 歲的孩子精通函式、函式組合、反函式等。此外，如果沒有群論，您將無法真正做很多事情，儘管它是一個引人入勝的主題，其中的介紹性範例很容易為年輕人所接受學習者，連同密碼學可能太多了。

引用自：https://crypto.stackexchange.com/questions/74642