2017-06-23 Friday-night tweet-size crypto: Rabin/Blum/Williams/Shoup-style
public-key key encapsulation
(Permalink: https://mumble.net/~campbell/2017/06/23/fntsc-rbws-kem)
(Twitter: https://twitter.com/Riastradh_/status/878486389100355586)
(Secure? Maybe. Don't try this at home, kids!)
- Keygen: Pick 1024-bit primes p < q uniformly with 2^2047 < p q <
2^2048 and p = q = 3 (mod 4); publish n = p q.
- Encrypt: Pick x uniformly in (Z/nZ)^*; compute y = x^2 (mod n),
z = y^2 (mod n); use H(y) as secret key; transmit z.
- Decrypt: Compute r = z^{(p + 1)/4} (mod p), s = z^{(q + 1)/4} (mod q);
use CRT to find y with y = r (mod p) and y = s (mod q).
- Correctness 1: If z = y^2 in Z/mZ for prime m = 3 (mod 4), then
y^{m - 1} = 1, so z = y^2 = y^{m + 1} = z^{(m + 1)/2} = (z^{(m +
1)/4})^2.
- Correctness 2: Square-modulo-n is a permutation of squares modulo
n: exactly one square y = x^2 (mod n) solves z = y^2 (mod n).
- Hashless variant? On decrypt, use CRT to find z' with z' = r^2
(mod p) and z' = s^2 (mod q); reject if z =/= z' (mod n).
--> Nope, hash (as usual) is critical for security: attack works
by learning square y' =/= +/-y from z = y^2 when random y
turns out nonsquare.
- Reduction to factoring: Let y = f(z) solve z = y^2 (mod n). If
f(y^2) = y' =/= +/-y for some chosen nonsquare y, then
gcd(y+/-y', n) | n.
--
Copyright (c) 2006--2017, Taylor R. Campbell.
Verbatim copying and distribution of this entire article are permitted
worldwide, without royalty, in any medium, provided this notice, and
the copyright notice, are preserved.