Goldwasser-Micali公钥加密#

预处理#

• 大整数$N=p\;\cdot\;q$

• 取二次非剩余$y$，即$J(\frac{y}{p})=J(\frac{y}{q})=-1$

• 公钥为$PK=(y,N)$,私钥为$SK=(p,q)$

加密#

• 将明文$b$转化为01数字串$M=(m_1,m_2,\cdots)$

• 对于每一位 $m_i$ , 我们随机选取一个 $r\in\;Z_{n}^{*}$ 计算 $\;c_i\equiv\;y^{m_i}\cdot\;r^2\;mod\;n$

• 生成密文$C=(c_1,c_2,\cdots)$

解密#

• 获得密文$C=(c_1,c_2,\cdots)$

• 计算$c_i$分别对$p,q$的雅可比符号$J(\frac{c_i}{p})\;J(\frac{c_i}{q})$

• 如果$J(\frac{c_i}{p})\;=\;J(\frac{c_i}{q})\;=\;1$,说明$m_i=0$，否则$m_i=1$

证明如下

因为

当$m_i=0$,式子变为

此时我们可以往下转移到模$p$,$q$下，也就是满足$c_i$是$p,q$的二次剩余

当$m_i=1$,由于$y$不是$p,q$的二次剩余，那么我们就说

也就是说

也就是说$c_i$不是$p,q$的二次剩余，证毕

数论的香氛#

题目https://buuoj.cn/match/matches/213/challenges ↗ 我们回顾一下加密过程

和这个公钥加密有一定相似之处 ，但是这里的$m$都是79个比特，那就是稍微进行变种的Goldwasser-Micali，

我们能找到这篇paper 435.pdf (iacr.org) ↗

我们来分析一下这篇paper中的加密原理

预处理#

• 生成两个大素数$p,q$满足$p\equiv\;1\;mod\;2^k$,$q\equiv3\;mod\;4$,使得群$Z^*_p$的阶恰好包含一个$2^k$
• 生成公钥 $y$ 满足 $\;(\frac{y}{p})_{2^k}=-1\;$ ; $\;(\frac{y}{q})_{2^k}=1\;$ 即 $y$ 是 $p$ 的 $2^k$ 次非剩余，而是 $q$ 的 $2^k$ 次剩余
• 代码中为了省事直接生成 $p,q$ 的二次非剩余 $y$ ，如果不行多生成几次就ok

加密#

• 计算 $c_i\equiv\;y^{m_i}\;\cdot\;x^{2^k}\;mod\;n$ 即可;保证 $x\in\;Z^*_n$

解密#

原理#

我们主要关注群 $Z^*_p$ ，它的阶是 $Ord(Z^*_p)=p-1=r\cdot2^k$

注意到我们已经给$x$取了$2^k$次方，后续做任何有关是否为$2^k$或者$2^{k-i}$次剩余的判断 它都恒定为真，毕竟

也就是说我们模仿GM公钥解密的过程 完全消去了无关变量$x$,这其实和我们之前DLP做法有点像，先把$x$干掉

接下来我们提前获得了$n$的分解$p,q$我们尝试来解这个$m$

注意到py的bytes_to_long函数就是计算

我们来考虑计算一个指数因子

我们给加密的式子左右乘上指数因子次幂，得到

我们注意$(x^{2^k})^{e_i}$这一项对判断$2^k$阶剩余没有影响，我们关注$y^{m\;\cdot\;e_i}$,我们把它展开

由于

故

分为三个部分

• 对于后部分 我们的因子都可以拆分为$2^{k+\delta}>2^k$，它们进行$2^k$判断的结果会是1，理解为$1^{\alpha}$这部分的$y^{r\;(\sum_{j+i>k}\cdots)}=(y^{r\sum\cdots})^{2^k}$一定是$2^k$次剩余
• 对于前部分 我们的因子都可以拆分为$2^{k-\beta}<2^k$，它们进行$2^k$判断你可以理解为$1^{-\beta}$,也一定是1
• 所以我们只要关注中间的部分，即$y^{rm_{k-i}2^k}$
  • 如果$m_{k-i}=0$，很好，这一项是1，最后你剩余检查出来会是1
  • 如果$m_{k-i}=1$，我们注意到这里就保留了我们不愿意看到的$y$，那么$\forall\;t\in\;Z_p^*\;\;\;y\not\equiv\;t^{2^k}\;mod\;p$这个时候，我们计算$2^k$次剩余出来就会是-1

我们来调整一下脚本 使得我们能从 $m_{1}$ 到 $m_{i}$ 来进行验证，注意到我们取 $e_i$ ，进行 $2^k$ 次剩余检查，能查出来 $m_{k-i}$ 的取值是0或者1，那么我们不妨从 $k-i$ 算 起，使得我们验证的 $m_i$ 下标从0开始

大致思路如上 脚本可以写出来

from sympy import mod_inverse
from Crypto.Util.number import *

def decrypt(c, p, k, D):
    m = 0
    B = 1
    C = pow(c, (p - 1) // (2**k), p)
    
    for j in range(1, k):
        z = pow(C, 2**(k-j), p)
        if z != 1:
            m += B
            C = (C * D) % p
        B <<= 1  # B = 2 * B
        D = (D * D) % p
    
    if C != 1:
        m += B
    
    return m

q = 863327174253852394776516978368858092781662547
p = 628729403897154553626034231171921094272614401
n = 542799179636839492268900255776759322356188435185061417388485378278779491236741777034539347
y = 304439269593920283890993394966761083993573819485737741439790516965458877720153847056020690
k = 79

k = 79
D = pow(y, -(p - 1) // 2**k, p)  
print(D)
cs = [
    302425991290493703631236053387822220993687940015503176763298104925896002167283079926671604,
    439984254328026142169547867847928383533091717170996198781543139431283836994276036750935235,
    373508223748617252014658136131733110314734961216630099592116517373981480752966721942060039,
    246328010831179104162852852153964748882971698116964204135222670606477985487691371234998588,
    351248523787623958259846173184063420603640595997008994436503031978051069643436052471484545
]

decrypted_messages = [decrypt(ci, p, k, D) for ci in cs]

for i, m in enumerate(decrypted_messages):
    print(f"Decrypted message {i}: {m}")
    print(long_to_bytes(m))

# DASCTF{go0_j06!let1sm0v31n_t0_th3r_chanlenges~>_<}