ElGamal¶

RSA 的数字签名方案几乎与其加密方案完全一致，只是利用私钥进行了签名。但是，对于 ElGamal 来说，其签名方案与相应的加密方案具有很大区别。

基本原理 ¶

密钥生成 ¶

基本步骤如下

选取一个足够大的素数 p（十进制位数不低于 160），以便于在 $Z_p$ 上求解离散对数问题是困难的。
选取 $Z_p^*$ 的生成元 g。
随机选取整数 d, $0\leq d \leq p-2$ ，并计算 $g^d \equiv y \bmod p$ 。

其中私钥为 {d}，公钥为 {p,g,y} 。

签名 ¶

A 选取随机数 $k \in Z_{p-1}$ ，并且 $gcd(k,p-1)=1$ ，对消息进行签名

$sig_d(m,k)=(r,s)$

其中 $r \equiv g^k \bmod p$ ， $s \equiv (m-dr)k^{-1} \bmod p-1$ 。

验证 ¶

如果 $g^m \equiv y^rr^s \bmod p$ ，那么验证成功，否则验证失败。这里验证成功的原理如下，首先我们有

$y^rr^s \equiv g^{dr}g^{ks} \equiv g^{dr+ks}$

又因为

$s \equiv (m-dr)k^{-1} \bmod p-1$

所以

$ks \equiv m-dr \bmod p-1$

进而

$ks+dr=a*(p-1)+m$

所以

$g^{ks+dr}=g^{a*(p-1)+m}=(g^{p-1})^a*g^m$

所以根据费马定理，可得

$g^{ks+dr} \equiv g^m \bmod p$

常见攻击 ¶

完全破译攻击 ¶

攻击条件 ¶

p 太小或无大素因子

如果 $p$ 太小我们可以直接用大部小步算法分解, 或者如果其无大的素因子, 我们可以采用 $Pohling\: Hellman$ 算法计算离散对数即可进而求出私钥。

随机数 k 复用

如果签名者复用了随机数 k，那么攻击者就可以轻而易举地计算出私钥。具体的原理如下：

假设目前有两个签名都是使用同一个随机数进行签名的。那么我们有

$r \equiv g^k \bmod p \\\\ s _1\equiv (m_1-dr)k^{-1} \bmod p-1\\\\ r \equiv g^k \bmod p \\\\ s_2 \equiv (m_2-dr)k^{-1} \bmod p-1$

进而有

$s_1k \equiv m_1-dr \bmod p-1 \\\\ s_2k \equiv m_2-dr \bmod p-1$

两式相减

$k(s_1-s_2) \equiv m_1-m_2 \bmod p-1$

这里， $s_1,s_2,m_1,m_2,p-1$ 均已知，所以我们可以很容易算出 k。当然，如果 $gcd(s_1-s_2,p-1)!=1$ 的话，可能会存在多个解，这时我们只需要多试一试。进而，我们可以根据 s 的计算方法得到私钥 d，如下

$d \equiv \frac{m-ks}{r}$

题目 ¶

2016 LCTF Crypto 450

通用伪造签名 ¶

攻击条件 ¶

如果消息 $m$ 没有取哈希，或者消息 $m$ 没有指定消息格式的情况下攻击成立。

原理 ¶

在攻击者知道了某个人 Alice 的公钥之后，他可以伪造 Alice 的签名信息。具体原理如下:

这里我们假设，Alice 的公钥为 {p,g,y}。攻击者可以按照如下方式伪造

选择整数 $i$ ， $j$ ，其中 $gcd(j,p-1)=1$
计算签名， $r \equiv g^iy^j \bmod p$ ， $s\equiv -rj^{-1} \bmod p-1$
计算消息， $m\equiv si \bmod p-1$

那么此时生成的签名与消息就是可以被正常通过验证，具体推导如下:

$y^rr^s \equiv g^{dr}g^{is}y^{js} \equiv g^{dr}g^{djs}g^{is} \equiv g^{dr+s(i+dj)} \equiv g^{dr} g^{-rj^{-1}(i+dj)} \equiv g^{dr-dr-rij^{-1}} \equiv g^{si} \bmod p$

又由于消息 m 的构造方式，所以

$g^{si} \equiv g^m \bmod p-1$

需要注意的是，攻击者可以伪造通过签名验证的消息，但是他却无法伪造指定格式的消息。而且，一旦消息进行了哈希操作，这一攻击就不再可行。

已知签名伪造 ¶

攻击条件 ¶

假设攻击者知道 $(r, s)$ 是消息 $M$ 的签名，则攻击者可利用它来伪造其它消息的签名。

原理 ¶

选择整数 $h, i, j \in[0, p-2]$ 且满足 $\operatorname{gcd}(h r-j s, \varphi(p))=1$
计算下式 $\begin{array}{l} r^{\prime}=r^{h} \alpha^{i} y_{A}^{j} \bmod p \\ s^{\prime}=\operatorname{sr}(h r-j s)^{-1} \bmod \varphi(p) \\ m^{\prime}=r^{\prime}(h m+i s)(h r-j s)^{-1} \bmod \varphi(p) \end{array}$

可得到 $(r',s')$ 是 $m'$ 的有效签名

证明如下:

已知 Alice 对消息 $x$ 的签名 $(\gamma,\delta)$ 满足 $\beta^{\gamma} \gamma^{\delta} \equiv \alpha^{x}(\bmod p)$ ，所以我们目的为构造出 $\left(x^{\prime}, \lambda, \mu\right)$ 满足

$\beta^{\lambda} \lambda^{\mu} \equiv \alpha^{x'}(\bmod p)$

那么，首先我们把 $\lambda$ 表示为三个已知底 $\alpha, \beta, \gamma$ 的形式: $\lambda=\alpha^{i} \beta^{j} \gamma^{h} \bmod p$ , 由条件可得

$\beta^{\gamma} \gamma^{\delta} \equiv \alpha^{x}(\bmod p) \Leftrightarrow \gamma=\left(\beta^{-\gamma} \alpha^{x}\right)^{\delta-1} \bmod p$

那么我们可以得到

$\lambda=\alpha^{i+x \delta^{-1} h} \beta^{j-\gamma \delta^{-1} h} \bmod p$

我们把 $\lambda$ 的表达式代入一式中

$\begin{aligned}& \beta^{\lambda}\left(\alpha^{i+x \delta^{-1} h} \beta^{j-\gamma \delta^{-1} h}\right)^{\mu} \equiv \alpha^{x^{\prime}}(\bmod p) \\\Leftrightarrow & \beta^{\lambda+\left(j-\gamma \delta^{-1} h\right) \mu} \equiv \alpha^{x^{\prime}-\left(i+x \delta^{-1} h\right) \mu}(\bmod p)\end{aligned}$

我们令两边指数为 $0$ , 即

$\left\{\begin{matrix}\lambda+\left(j-\gamma \delta^{-1} h\right) \mu \equiv 0 \bmod p-1 \\ x^{\prime}-\left(i+x \delta^{-1} h\right) \mu \equiv 0 \bmod p-1 \end{matrix}\right.$

可以得到

$\mu=\delta \lambda(h \gamma-j \delta)^{-1} \quad(\bmod p-1) \\ x^{\prime}=\lambda(h x+i \delta)(h \gamma-j \delta)^{-1}(\bmod p-1)$

其中

$\lambda=\alpha^{i} \beta^{j} \gamma^{h} \bmod p$

所以我们得到 $(\lambda, \mu)$ 是 $x'$ 的有效签名。

此外, 我们还可以借助 CRT 构造 $m'$ , 原理如下:

$u=m^{\prime} m^{-1} \bmod \varphi(p), \quad s^{\prime}=s u \bmod \varphi(p)$
再计算 $r^{\prime}, \quad r^{\prime} \equiv r u \bmod \varphi(p), r^{\prime} \equiv r \bmod p$

显然可以使用 CRT 求解 $r'$ , 注意到 $y_{A}^{r'} r'^{s^{\prime}}=y_{A}^{ru} r^{s u}=\left(y_{A}^{r} r^{s}\right)^{u}=\alpha^{m u} \equiv \alpha^{m} \bmod p$

所以 $(r',s')$ 是消息 $m'$ 的有效签名。

抵抗措施: 在验证签名时, 检查 $r < p$ 。

选择签名伪造 ¶

攻击条件 ¶

如果我们可以选择我们消息进行签名，并且可以得到签名，那么我们可以对一个新的但是我们不能够选择签名的消息伪造签名。

原理 ¶

我们知道，最后验证的过程如下

$g^m \equiv y^rr^s \bmod p$

那么只要我们选择一个消息 m 使其和我们所要伪造的消息 $m'$ 模 p-1 同余，然后同时使用消息 m 的签名即可绕过。

题目 ¶

这里以 2017 年国赛 mailbox 为例，i 春秋有复现。

首先，我们来分析一下程序，我们首先需要进行 proof of work

    proof = b64.b64encode(os.urandom(12))
    req.sendall(
        "Please provide your proof of work, a sha1 sum ending in 16 bit's set to 0, it must be of length %d bytes, starting with %s\n" % (
        len(proof) + 5, proof))

    test = req.recv(21)
    ha = hashlib.sha1()
    ha.update(test)

    if (test[0:16] != proof or ord(ha.digest()[-1]) != 0 or ord(ha.digest()[-2]) != 0): # or ord(ha.digest()[-3]) != 0 or ord(ha.digest()[-4]) != 0):
        req.sendall("Check failed")
        req.close()
        return

我们需要生成一个以 proof 开头的长度为 proof 长度加 5 的字符串，并且其 sha1 的值以 16 比特的 0 结束。

这里我们直接使用如下的方式来绕过。

def f(x):
    return sha1(prefix + x).digest()[-2:] == '\0\0'


sh = remote('106.75.66.195', 40001)
# bypass proof
sh.recvuntil('starting with ')
prefix = sh.recvuntil('\n', drop=True)
print string.ascii_letters
s = util.iters.mbruteforce(f, string.ascii_letters + string.digits, 5, 'fixed')
test = prefix + s
sh.sendline(test)

这里使用了 pwntools 中的 util.iters.mbruteforce，这是一个利用给定字符集合以及指定长度进行多线程爆破的函数。其中，第一个参数为爆破函数，这里是 sha1，第二个参数是字符集，第三个参数是字节数，第四个参数指的是我们只尝试字节数为第三个参数指定字节数的排列，即长度是固定的。更加具体的信息请参考 pwntools。

绕过之后，我们继续分析程序，简单看下 generate_keys 函数，可以知道该函数是 ElGamal 生成公钥的过程，然后看了看 verify 函数，就是验证签名的过程。

继续分析

            if len(msg) > MSGLENGTH:
                req.sendall("what r u do'in?")
                req.close()
                return
            if msg[:4] == "test":
                r, s = sign(digitalize(msg), sk, pk, p, g)
                req.sendall("Your signature is" + repr((hex(r), hex(s))) + "\n")
            else:
                if msg == "Th3_bery_un1que1i_ChArmIng_G3nji" + test:
                    req.sendall("Signature:")
                    sig = self.rfile.readline().strip()
                    if len(sig) > MSGLENGTH:
                        req.sendall("what r u do'in?")
                        req.close()
                        return
                    sig_rs = sig.split(",")
                    if len(sig_rs) < 2:
                        req.sendall("yo what?")
                        req.close()
                        return
                    # print "Got sig", sig_rs
                    if verify(digitalize(msg), int(sig_rs[0]), int(sig_rs[1]), pk, p, g):
                        req.sendall("Login Success.\nDr. Ziegler has a message for you: " + FLAG)
                        print "shipped flag"
                        req.close()
                        return
                    else:
                        req.sendall("You are not the Genji I knew!\n")

根据这三个 if 条件可以知道

我们的消息长度不能超过 MSGLENGTH，40000。
我们可以对消息开头为 test 的消息进行签名。
我们需要使得以 Th3_bery_un1que1i_ChArmIng_G3nji 开头，以我们绕过 proof 的 test 为结尾的消息通过签名验证，其中，我们可以自己提供签名的值。

分析到这里，其实就知道了，我们就是在选择指定签名进行伪造，这里我们自然要充分利用第二个 if 条件，只要我们确保我们输入的消息的开头为‘test’，并且该消息与以 Th3_bery_un1que1i_ChArmIng_G3nji 开头的固定消息模 p-1 同余，我们即可以通过验证。

那我们如何构造呢？既然消息的长度可以足够长，那么我们可以将'test'对应的 16 进制先左移得到比 p-1 大的数字 a，然后用 a 对 p-1 取模，用 a 再减去余数，此时 a 模 p-1 余 0 了。这时再加上以 Th3_bery_un1que1i_ChArmIng_G3nji 开头的固定消息的值，即实现了模 p-1 同余。

具体如下

# construct the message begins with 'test'
target = "Th3_bery_un1que1i_ChArmIng_G3nji" + test
part1 = (digitalize('test' + os.urandom(51)) << 512) // (p - 1) * (p - 1)
victim = part1 + digitalize(target)
while 1:
    tmp = hex(victim)[2:].decode('hex')
    if tmp.startswith('test') and '\n' not in tmp:
        break
    else:
        part1 = (digitalize('test' + os.urandom(51)) << 512) // (p - 1) * (
            p - 1)
        victim = part1 + digitalize(target)

最后的脚本如下

from pwn import *
from hashlib import sha1
import string
import ast
import os
import binascii
context.log_level = 'debug'


def f(x):
    return sha1(prefix + x).digest()[-2:] == '\0\0'


def digitalize(m):
    return int(m.encode('hex'), 16)


sh = remote('106.75.66.195', 40001)
# bypass proof
sh.recvuntil('starting with ')
prefix = sh.recvuntil('\n', drop=True)
print string.ascii_letters
s = util.iters.mbruteforce(f, string.ascii_letters + string.digits, 5, 'fixed')
test = prefix + s
sh.sendline(test)

sh.recvuntil('Current PK we are using: ')
pubkey = ast.literal_eval(sh.recvuntil('\n', drop=True))
p = pubkey[0]
g = pubkey[1]
pk = pubkey[2]

# construct the message begins with 'test'
target = "Th3_bery_un1que1i_ChArmIng_G3nji" + test
part1 = (digitalize('test' + os.urandom(51)) << 512) // (p - 1) * (p - 1)
victim = part1 + digitalize(target)
while 1:
    tmp = hex(victim)[2:].decode('hex')
    if tmp.startswith('test') and '\n' not in tmp:
        break
    else:
        part1 = (digitalize('test' + os.urandom(51)) << 512) // (p - 1) * (
            p - 1)
        victim = part1 + digitalize(target)

assert (victim % (p - 1) == digitalize(target) % (p - 1))

# get victim signature
sh.sendline(hex(victim)[2:].decode('hex'))
sh.recvuntil('Your signature is')
sig = ast.literal_eval(sh.recvuntil('\n', drop=True))
sig = [int(sig[0], 0), int(sig[1], 0)]

# get flag
sh.sendline(target)
sh.sendline(str(sig[0]) + "," + str(sig[1]))
sh.interactive()

这里还要说几个有意思的点就是

int(x,0) 只的是将 x 按照其字面对应的进制转换为对应的数字，比如说 int('0x12',0)=18，这里相应的字面必须有对应标志开头，比如说十六进制是 0x,8 进制是 0，二进制是 0b。因为如果没有的话，就不知道该如何识别了。
python(python2) 里面到底多大的数，计算出来最后才会带有 L 呢？正常情况下，大于 int 都会有 L。但是这个里面的 victim 确实是没有的，， 一个问题，待解决。。