简介

ElGamal 算法的安全性是基于求解离散对数问题的困难性，既可以用来加密也可以用来进行数字签名。

密钥生成

选择一个大素数$p$，使得在$Z_p$上求解离散对数是困难的。

选择$Z^*_p$的生成元$g$。

随机选取$0≤k≤p-2$，计算$g^k\equiv y\pmod p$。

私钥为$k$，公钥为$p,g,y$。

加密

Alice选择随机数$r\in Z_{p-1}$，对明文$m$进行加密：

$\begin{cases}y_1\equiv g^r\pmod p\\y_2\equiv my^r\pmod p\end{cases}$

解密

$y_2(y_1^k)^{-1}\bmod p\equiv m(g^{kr})(g^{kr})^{-1}\equiv m\bmod p$

ElGamal数字签名

数字签名由公钥密码发展而来，用于对数字消息进行签名，防止消息伪造或篡改，也可以用在通信双方的身份鉴别。

数字签名依赖非对称密码：

先利用相同的方式生成公钥：

选择一个随机质数$p$，选择$Z^*_p$的生成元$g$，随机选择整数$0≤d≤p-2$，计算：

$g^d\equiv y (\bmod p)$

私钥为$k$，公钥为$p,g,y$。

Alice计算密文$m$的哈希值$H(m)$，选择随机数$k\in Z_{p-1}$，有$gcd(k,p-1)=1$，进行签名：

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

验证：Bob接收到$m$和$(r,s)$，如果满足$g^{H(m)}\equiv y^rr^s(\bmod p)$，那么验证成功。

证明：

$y^rr^s\equiv g^{dr}g^{ks}\equiv g^{dr+H(m)-dr}\equiv g^{H(m)}(\bmod p)$

扩展：ElGamal在ECC

Alice和Bob选择一个特定的素数$p$，椭圆曲线$E$和点$P\in E(F_p)$。

Alice选择一个秘密乘数$n_A$，计算并发布$Q_A=n_AP$作为公钥。Bob明文为$M\in E(F_p)$，他选择一个整数$k$作为临时密钥，计算：

$\begin{cases}C_1=kP\\C_2=M+kQ_A\end{cases}$

Bob将$C_1,C_2$两个点发送给Alice，Alice计算$C_2-n_AC_1=M$来恢复出明文。

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

常见攻击

分解$p$

如果$p$太小可以直接分解，如果其中没有大的素因子，可以使用Pohling Hellman算法计算离散对数可以求出私钥。

签名伪造

在未经过消息做检验时，我们可以进行伪造签名进行验证，这里拿0xGame 2023的题目Overflow举例子：

from ElGamal import *
import socketserver
import signal
from secert import flag
pub,pri = getKey(512)

class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def handle(self):
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return

        self.send(b'Here are your public key:')
        self.send(str(pub).encode())
        while True:
            #sign
            self.send(b'Pz tell me what you want to sign?')
            message = self.recv()
            if message == b'0xGame':
                self.send(b"Permission denied!")
                quit()
            self.send(b'Here are your sign:')
            r,s = sign(message,pub,pri)
            self.send(f'r={r}\ns={s}'.encode())
            #ver
            self.send(b'Tell me your signature,if you want to get the flag.')
            r = int(self.recv())
            s = int(self.recv())

            if verity(b'0xGame',(r,s),pub):
                self.send(b'Here you are:'+flag)
                self.send(b'bye~')
                quit()
                
            else:
                self.send(b"sorry~you can't get it.")

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10007
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

from Crypto.Util.number import getPrime,GCD,inverse,bytes_to_long,long_to_bytes
import random

def getKey(bits):
    p = getPrime(bits)
    g = getPrime(bits//2)
    d = random.randint(1,p-2)
    y = pow(g,d,p)
    public,private = (p,g,y),d
    return public,private

def sign(m,public,private):
    m = bytes_to_long(m)
    p,g,y = public
    d = private
    while True:
        k = random.randint(1,p-1)
        if GCD(k,p-1)==1:break
    r = pow(g,k,p) 
    s = ((m-d*r)*inverse(k,p-1)) % (p-1)
    return (r,s)

def verity(m,sign,public):
    m = bytes_to_long(m)
    p,g,y = public
    r,s = sign
    if pow(g,m,p) == (pow(y,r,p)*pow(r,s,p)) % p:
        return True
    else:
        return False

其他无关紧要的部分就不管了，直接看看怎么伪造签名：

#sign
self.send(b'Pz tell me what you want to sign?')
message = self.recv()
if message == b'0xGame':
    self.send(b"Permission denied!")
    quit()
self.send(b'Here are your sign:')
r,s = sign(message,pub,pri)
self.send(f'r={r}\ns={s}'.encode())
#ver
self.send(b'Tell me your signature,if you want to get the flag.')
r = int(self.recv())
s = int(self.recv())

if verity(b'0xGame',(r,s),pub):
    self.send(b'Here you are:'+flag)
    self.send(b'bye~')

最后验签的消息是0xGame，但是他做了一个直接拦截处理，肯定是不能直接发送0xGame的，这时候可以联系一下进行签名的操作：

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

我们最终要得到的肯定是满足用0xGame消息进行签名后的结果，所以在上式中，可以通过模数溢出伪造签名：

$s\equiv (H(m)+(p-1))k^{-1}-drk^{-1}(\bmod p-1)\equiv H(m)k^{-1}-drk^{-1}(\bmod p-1)$

所以，这里我们发送的消息可以是$p-1+0xGame$，根据计算，$p-1$就会被模掉，就能得到符合要求的签名。

贴一个官方的wp：

from pwn import *
from Crypto.Util.number import *

io = remote('0.0.0.0',10002)
io.recvuntil(b'key:\n')
pub = eval(io.recvline())
io.recvuntil(b'>')
msg = long_to_bytes(bytes_to_long(b'0xGame')+pub[0]-1)
io.sendline(msg)
io.recvuntil(b'r=')
r = int(io.recvline())
io.recvuntil(b's=')
s = int(io.recvline())
io.recvuntil(b'flag.\n')
io.sendline(str(r).encode())
io.sendline(str(s).encode())
io.interactive()
io.close()
#b'0xGame{24b6edfdc07d71311774ed15248f434e}'

随机数$k$复用

如果有两个签名是使用同一个随机数进行签名，那么可以通过计算计算出私钥$d$。有：

$\begin{cases}s_1\equiv (m_1-dr)k^{-1}\pmod {p-1}\\s_2\equiv (m_2-dr)k^{-1}\pmod {p-1}\end{cases}$

将两式相减，得到：

$k(s_1-s_2)\equiv m_1-m_2\pmod {p-1}$

这里已知了$s_1,s_2,m_1,m_2,p-1$均已知，可以算出$k$。如果$\gcd(s_1-s_2,p-1)≠1$的话会出现多个解，可以逐个检验一下。然后计算私钥：

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

ElGamal算法

简介