Blum-goldwasser cryptosystem - crypto-writeup-public

Goldwasser-Micali cryptosystemの拡張？　みたいな感じ

鍵生成

$p \equiv 3 \mod 4$ と $q \equiv 3 \mod 4$ を選ぶ（秘密鍵）
$n = pq$ （公開鍵）

暗号化

$h = \log_2(\log_2(n))$ （ブロックサイズ）
平文 $M$ をサイズ $h$ のブロック $m_1, m_2, \dots, m_t$ に分割する
$r < n$ をランダムに選ぶ
$x_0 = r^2 \mod n$
for $i$ from $1$ to $t$
- $x_i = x^2_{i-1} \mod n$
- $c_i = m_i \oplus x_i$
$x_{t+1} = x_t^2 \mod n$

暗号文 $(c_1, c_2, \dots, c_t; x_{t+1})$

復号

$d_p = ((p+1)/4)^{t+1} \mod (p-1)$
$d_q = ((q+1)/4)^{t+1} \mod(q-1)$
$u_p = x^{d_p} \mod p$
$u_q = x^{d_q} \mod q$
extended euclidean algorithm で $r_pp + r_qq = 1$ なる $r_p$ と $r_q$ を計算する
$x_0 = u_qr_pp + u_pr_qq \mod n$ として計算できる

証明

特に $x_0 = u_qr_pp + u_pr_qq$ の証明

まず、 $x_0$ は $\mod n$ でquadratic residueになるように作っている（適当な $r$ を選んで $x_0 = r^2 \mod n$ としているのだからそれはそう）。したがって、 $x_0$ は $\mod p$ でもquadratic residueである（これはjacobi記号のところに書いてある）

同様にすべての $x_i$ が $\mod n$ と $\mod p$ でquadratic residueである。

したがって、 $x_i^{(p-1)/2} \equiv 1 \mod p$ が成り立つ（これはjacobi記号をみるとそう書いてある）

したがって、下記が成り立つ

$x_{t+1}^{(p+1)/4} \equiv ((x_t)^2)^{(p+1)/4} \equiv x_t^{(p+1)/2} \equiv x_t(x_t^{(p-1)/2}) \equiv x_t * 1 \equiv x_t \mod p$

同様に下記も成立する（のでこれを使って逆順に $x_t \dots x_0$ と遡ることもできそう）

$x_t^{(p+1)/4} \equiv x_{t-1} \mod p$

ということは $x_{t+1}^{((p+1)/4)^2} \equiv x_{t-1} \mod p$ であり、

$x_{t+1}^{((p+1)/4)^{t+1}} \equiv x_0 \mod p$ である

これが $u_p, u_q$ に相当する

あとは中国人剰余定理で $x_0 \mod n$ を復元するだけだが、それをやっているのが $u_qr_pp + u_pr_qq \mod n$ というわけ

from Crypto.Util.number import getPrime, getRandomRange
from math import log2
import gmpy2
from typing import Tuple, Sequence

def keygen(size: int) -> Tuple[int, Tuple[int, int]]:
    while True:
        p = getPrime(size//2)
        if p % 4 == 3:
            break

    while True:
        q = getPrime(size//2)
        if q % 4 == 3:
            break

    n = p*q
    return n, (p, q)


def encrypt(n: int, m: int)->Tuple[Sequence[int], int]:
    h = int(log2(log2(n)))
    ms = []
    while m:
        m, block = divmod(m, 1 << h)
        ms.append(block)

    r = getRandomRange(2, n)
    x = pow(r, 2, n)
    cs = []
    for i in range(len(ms)):
        x = pow(x, 2, n)
        cs.append(ms[i] ^ x)
    return cs, pow(x, 2, n)

def decrypt(p: int, q: int, cs: Sequence[int], x: int)->int:
    t = len(cs)
    dp = pow((p+1) // 4, t+1, p-1)
    dq = pow((q+1) // 4, t+1, q-1)
    up = pow(x, dp, p)
    uq = pow(x, dq, q)
    n = p * q
    # up == x % p, uq == x % q

    _, rp, rq = gmpy2.gcdext(p, q)
    x = int(uq*rp*p + up*rq*q) % n

    h = int(log2(log2(n)))
    m = 0
    for i in range(len(cs)):
        x = pow(x, 2, n)
        m += (cs[i] ^ x) << (h * i)
    return m

n, (p, q) = keygen(1024)
m = getRandomRange(2, n)
cs, x = encrypt(n, m)
m_ = decrypt(p, q, cs, x)
assert m == m_