RSA Schnorr Signatures

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 $\phi :G\to H$, you can provide a zero-knowledge protocol to prove:

$$\Pi (X;x):=\phi (x)=X$$

(with $x$ kept secret).

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

$$\begin{array}{rl}& \phi :{\mathbb{F}}_q\to \mathbb{G}\\ & \phi (x):=x\cdot G\end{array}$$

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:

$$\begin{array}{rl}& \phi :\mathbb{Z}/(N{)}^{\ast }\to \mathbb{Z}/(N{)}^{\ast }\\ & \phi (m):=m^e\end{array}$$

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

Now, this is evidently a group homomorphism, since:

$$(a\cdot b{)}^e=a^e\cdot b^e$$

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\stackrel{R}{\leftarrow }\mathbb{Z}/(N{)}^{\ast }$, and then set $X\leftarrow s^e\mathrm{mod}N$.

$x$ is the private key.

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

Signing

$$\begin{array}{rl}k& \stackrel{R}{\leftarrow }\mathbb{Z}/(N{)}^{\ast }\\ K& \leftarrow k^e\mathrm{mod}N\\ c& \leftarrow H(N,e,X,K,m)\\ r& \leftarrow k\cdot x^c\mathrm{mod}N\\ (K& ,r)\end{array}$$

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^{1}28$ or so.

Verification

$$r^e\stackrel{?}{\equiv }K\cdot X^{H(N,e,X,K,m)}\mathrm{mod}N$$

Security

Trust me :)