Goldwasser–Micali Cryptosystem

今天看了一个新的密码系统Goldwasser–Micali Cryptosystem，名字很复杂，原理很简单，记录一下！

Goldwasser–Micali Cryptosystem是基于概率加密，什么是概率加密呢？举个简单的例子，我们通常把加密中，发送方记为Alice,接收方记为Bob, 截取破解方称为Eve.

如果A通过公钥加密系统加密信息，然而只想发送0，1给B，那么他只需要加密两个数0，1

所以E所做的很简单，就是用同样的加密系统加密0， 1，然后和A的密文作比较，对比得出明文。

为了解决问题，Goldwasser and Micali发明了新密码。其实现在于每次传输明文m时选择一个随机字符串r,然后用B的公钥加密(m, r)

r在其所有可能的值之间变化。假如有两个明文m1, m2，其密文范围就为

$$\begin{align} e(m_1,\ r) = the\ ciphertext\ for\ plaintext\ m_1\ and\ for\ random\ string\ r,\\ e(m_2,\ r) = the\ ciphertext\ for\ plaintext\ m_2\ and\ for\ random\ string\ r, \end{align}$$

在实际加密方案中，它每次只用来加密1位，尽管有点不切实际，，但是很安全。

加密方案如下：

$$\begin{align} &选择两个秘密素数p.q,\ N=pq\ 给出。对于一个给定的整数a,\ 测试a是否为模N的二次剩余即\\ &if\ exists \ an\ integer\ u\ satisfying\ u^2 \equiv a\ (mod\ N) \end{align}$$

对于B来说， 他知道N = pq, 他就可以轻松解出这个密码，因为

$$a\ is\ \text{a}\ square\ module\ pq,\ if\ and\ only\ if\ (\frac{a}{p})=1\ and\ (\frac{a}{q}) = 1.\$$

然而E只知道N， 只能计算

$$(\frac{a}{N})$$

然而可能得到-1.1这并不能告诉他a是模N的二次剩余。所以，利用这一点，概率密码出生了！

密钥选择：

$$秘密素数p, \ q,\ 选择a满足(\frac{a}{p}) = -1 = (\frac{a}{q}),\ 并且将N和a公开。$$

​ 加密：

$$\begin{align} &plaintext\ m \in \{0, 1\}.\\ &random\ r\ with\ r\ \in (1,\ N)\\ &use\ public\ key\ (N,\ a).\\ &compute\ c =r^2\ mod\ N\ if\ m=0,\\ &compute\ c =ar^2\ mod\ N\ if\ m=1,\\ &send\ ciphertext\ c\ to\ B \end{align}$$

解密：

$$compute\ (\frac{c}{p}),如果为1， m为0\\ 如果为-1， m为1.$$

下面做一个简单的证明，

$$\begin{align} &if\ m=0,\ (\frac{c}{p}) = (\frac{r^2}{p})=(\frac{r}{p})^2=1\\ &if\ m=1,\ (\frac{c}{p}) = (\frac{ar^2}{p})=(\frac{a}{p})(\frac{r}{p})^2=(\frac{a}{p})=-1\\ &这样就完全可以区分了 \end{align}$$

然而对于EVE来说，他只有N的值，

$$\begin{align} &if\ m=0,\ (\frac{c}{N})=(\frac{r^2}{N})=(\frac{r}{N})^2=1\\ &if\ m=1,\ (\frac{c}{N})=(\frac{ar^2}{N})=(\frac{a}{N})=(\frac{a}{pq})=(\frac{a}{p})(\frac{a}{q})=(-1)(-1)=1\\ \end{align}$$

所以肯定拿不到明文啊。只不过需要按位加密，这里也很好实现，代码如下

c = []
while m:
    t = random.randint(1, N)
    if m & 1:
        c.append((a * t**2) % N)
    else:
        c.append(t**2 % N)
    m = m >> 1
print(c)