Misay's blog

Goldwasser-Micali公钥加密以及拓展

发表于 更新于 分类于
本文字数： 4k
GM公钥加密体系简单分析以及拓展

Goldwasser-Micali公钥加密

预处理

  • 大整数

  • 取二次非剩余，即

  • 公钥为,私钥为

加密

  • 将明文转化为01数字串

  • 对于每一位 , 我们随机选取一个 计算

  • 生成密文

解密

  • 获得密文

  • 计算分别对的雅可比符号

  • 如果,说明，否则

证明如下

因为 当,式子变为 此时我们可以往下转移到模,下，也就是满足是的二次剩余

当,由于不是的二次剩余，那么我们就说 也就是说 也就是说不是的二次剩余，证毕

数论的香氛

题目https://buuoj.cn/match/matches/213/challenges 我们回顾一下加密过程 和这个公钥加密有一定相似之处 ，但是这里的都是79个比特，那就是稍微进行变种的Goldwasser-Micali，

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

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

预处理

  • 生成两个大素数满足,,使得群的阶恰好包含一个
  • 生成公钥 满足 ; 即 是 的 次非剩余，而是 的 次剩余
  • 代码中为了省事直接生成 的二次非剩余 ，如果不行多生成几次就ok

加密

  • 计算 即可;保证

解密

原理

我们主要关注群 ，它的阶是

注意到我们已经给取了次方，后续做任何有关是否为或者次剩余的判断 它都恒定为真，毕竟 也就是说我们模仿GM公钥解密的过程 完全消去了无关变量,这其实和我们之前DLP做法有点像，先把干掉

接下来我们提前获得了的分解我们尝试来解这个

注意到py的bytes_to_long函数就是计算 我们来考虑计算一个指数因子 我们给加密的式子左右乘上指数因子次幂，得到 我们注意这一项对判断阶剩余没有影响，我们关注,我们把它展开

由于 故 分为三个部分

  • 对于后部分 我们的因子都可以拆分为，它们进行判断的结果会是1，理解为这部分的一定是次剩余
  • 对于前部分 我们的因子都可以拆分为，它们进行判断你可以理解为,也一定是1
  • 所以我们只要关注中间的部分，即
    • 如果，很好，这一项是1，最后你剩余检查出来会是1
    • 如果，我们注意到这里就保留了我们不愿意看到的，那么这个时候，我们计算次剩余出来就会是-1

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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~>_<}