注：以下內(nèi)容出自《An Introduction to Mathematical Cryptography》3.10 Probabilistic Encryption and the Goldwasser–Micali Cryptosystem一節(jié)。

假如Alice使用公鑰密碼系統(tǒng)向Bob發(fā)送信息，如比特0或1。在該場景下，這樣的方式可能是不安全的。偷聽者Eve可以加密兩個可能的明文 m = 0 和 m = 1，然后將加密值與 Alice 的密文進行比較。更一般地說，在任何一個密碼系統(tǒng)中，如果它可能的明文集合很小，那么Eve 總是可以使用 Bob 的公鑰加密各個明文，然后找到和Alice發(fā)送的一樣的密文。

所謂的概率加密（Probabilistic encryption）是由Goldwasser 和 Micali 發(fā)明的針對上述問題的加密方法。其想法是 Alice 選擇一個明文 m 和一個隨機數(shù)據(jù)r，然后使用 Bob 的公鑰加密 (m,r)對。理想情況下，當 r 選遍所有可能的值， 的加密值將“隨機”選遍可能的密文。更準確地說，對于任何固定的 和 以及變化的 ，對下面兩個量的值在分布上應該是不可區(qū)分的：

• 是對明文 和 隨機值 的密文
• 是對明文 和 隨機值 的密文

注意，Bob 在進行解密時沒有必要恢復完整的對，他只需要恢復明文 即可。

上面這個想法的思路是很清晰的，但是如何創(chuàng)造一個實際可行的概率加密方案呢？Goldwasser 和 Micali 描述了一種方案，雖然不實用（因為它一次只加密 1 位），但其具有易于描述和分析的優(yōu)點。 他們的想法基于以下的困難問題：

設和是需要保密的兩個不同的素數(shù)；令，并公開；給定一個整數(shù)，判斷是否是模的一個二次剩余，即判斷同余方程是否可解。

我們注意到，由于Bob知道如何分解，他可以方便的計算：是模的二次剩余，當且僅當是模的二次剩余而且也是模的二次剩余。而對于，由于她只知道，即使她計算對的Jacob符號，仍然無法知道是否是模的二次剩余。

Goldwasser 和 Micali 利用這一事實， 創(chuàng)建了下表描述的概率公鑰密碼系統(tǒng)。

image-20220605235719650.png

該方案易于驗證：

image-20220606000000354.png

因為Alice隨機選取，當Alice加密明文時，可以選遍模N的二次剩余；當Alice加密明文時，可以選遍模N的二次非剩余（且該數(shù)對的Jacob符號為1）。這樣的話，即使Eve計算對的Jacob符號，仍無法獲得任何有用的信息，如下:

即無法判斷同余方程是否可解。

來看一個例子，Bob通過以下參數(shù)創(chuàng)建Goldwasser–Micali公鑰：

可以確認。Bob公開作為公鑰，保留。

如果Alice要發(fā)送的明文比特，她首選在[1,13048158]范圍內(nèi)隨機選取。然后計算

，并將密文發(fā)送給Bob。Bob通過計算對的Legendre符號，即，即可知明文。

之后，Alice繼續(xù)發(fā)送。同樣先隨機選取，然后計算

，并將密文發(fā)送給Bob。Bob通過計算對的Legendre符號，即，即可知明文m=1。

按照這樣的方式，如果Alice再次發(fā)送明文，隨機選取r之后計算

。

可以看到，前后兩次發(fā)送的的密文是完全沒有相關性的。

注：

Goldwasser-Micali 公鑰密碼系統(tǒng)其實不實用，因為明文的每一位都模 N 加密。為了安全，要保證 Eve 不能有效分解 ，所以 N 至少是一個 1000 位bit長的數(shù)。 這樣，如果 Alice 想向 Bob 發(fā)送 位長度明文，她的密文將有 位長。因此，Goldwasswer-Micali 公鑰密碼系統(tǒng)的密文膨脹率為 1000。一般來說，Goldwasswer-Micali 公鑰密碼系統(tǒng)的密文膨脹率為。

存在其他密文膨脹率小得多的的概率公鑰加密系統(tǒng)。比如Elgamal公鑰加密系統(tǒng)。