Goldwasser-Micali cryptosystem - crypto-writeup-public

確率的公開鍵暗号方式で、その難しさは Quadratic residuosity problemに基づく（ので結局素因数分解の困難性に基づく）

XORに関する準同型性を持っていて、暗号文 $C_0, C_1$ に対して、 $C_0C_1 \mod N$ を復号したときに $m_0 \oplus m_1$ が得られる

https://eprint.iacr.org/2007/177.pdf ?

原理

Quadratic residuosity problemにあるように、合成数 $N = pq$ と $a \in Z_N^*$ に対して、 $a$ がquadratic residueである確率は1/2で、判定方法もない

素数 $p, q$ と $N = pq$ に対して $\left(\frac{a}{N}\right) = \left(\frac{a}{p}\right)\left(\frac{a}{q}\right)$

また、Qadratic Residueを $Q$ 、Non Quadratic Residueを $NQ$ とした時

$Q\times Q \to Q$
$Q \times NQ \to NQ$
$NQ \times NQ \to ?$

これを利用して $NQ$ な $z$ を公開鍵として、各bitをランダムな $x$ を用いて次のように変換する

$1 \to zx^2 : NQ$

$0 \to x^2 : Q$

実装

https://www.csa.iisc.ac.in/~arpita/Cryptography15/CT7.pdf を見ながらやった

from Crypto.Util.number import *

def xor(a, b):
    c = []
    for x, y in zip(a, b):
        c.append(x^y)
    return c

def legendre_symbol(x, p):
    a = pow(x, (p-1) // 2, p)
    if a == 0:
        return 0
    elif a == 1:
        return 1
    else:
        return -1

def key_gen(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    n = p * q

    while True:
        z = getRandomRange(2, n)
        a, b = legendre_symbol(z, p), legendre_symbol(z, q)
        if a == -1 and b == -1:
            break

    return (n, z), (p, q)

def enc(pubkey, m):
    n, z = pubkey
    bits = [int(b) for b in "{:b}".format(m)]

    c = []
    for b in bits:
        while True:
            x = getRandomRange(2, n)
            if GCD(x, n) == 1:
                break
        c.append( ((z**b) * (x**2)) % n )
    return c

def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)


def main():
    m = b"some plaintext to encrypt"
    pubkey, privkey = key_gen(256)

    c = enc(pubkey, bytes_to_long(m))

    m2 = long_to_bytes(dec(privkey, c))
    assert m == m2

    m3 = b"text edited with xor     "
    diff = bytes(xor(m, m3))
    cdiff = enc(pubkey, bytes_to_long(diff))

    if len(cdiff) < len(c):
        cdiff = [1] * (len(c) - len(cdiff)) + cdiff
    else:
        c = [1] * (len(cdiff) - len(c)) + c

    c2 = []
    for i in range(len(c)):
        c2.append((c[i] * cdiff[i]) % pubkey[0])

    m4 = long_to_bytes(dec(privkey, c2))
    assert m3 == m4


if __name__ == '__main__':
    main()