2022-04-05

RSA Schnorr Signatures

[!note] Note: I wasn't aware when quickly writing this up, but it turns out that this is an application of the Guillou-Quisquater protocol.

Maurer's 2009 paper provides a generalization of schnorr signatures to a large class of situations. Essentially, any time you have a group homomorphism $\varphi : G \to H$, you can provide a zero-knowledge protocol to prove:

(with $x$ kept secret).

In the case of a cyclic group of prime order $q$, with generator $G$, and the following homomorphism:

We have the usual Schnorr sigma protocol, which leads to Schnorr signatures after a Fiat-Shamir transform.

RSA

We can use the following group homomorphism, inspired by RSA:

Here, $(N, e)$ is an RSA public key.

Now, this is evidently a group homomorphism, since:

Furthermore, this homomorphism is one way, provided we don't know the factorization of $N$, and we think RSA is hard.

The Signature Protocol

For the memes, let's explicitly describe the signature scheme.

Key-Generation

Generate random primes $p, q$ of half the desired modulus size. Let $N = p \cdot q$, and pick $e$ such that $\text{gcd}(e, (p - 1)(q - 1)) = 1$.

Pick a random $x\xleftarrow{R} \mathbb{Z}/(N)^*$, and then set $X \gets s^e \mod N$.

$x$ is the private key.

$(N, e, X)$ is the public key.

Signing

[!note] Note: What type should $c$ have? Well, one approach is to take it such that $c$ is coprime with $e$, so that we'll have extractability. Basically, given $x^c$ and $x^e$, you can learn $x$. We also need $e$ to be large enough to have our security parameter, i.e. $e > 2^128$ or so.

Verification

Security

Trust me :)