0
$\begingroup$

I am reading up on group signatures. With RSA a public key can have more than one private key. For a public exponent $e$, private exponent $d$ and modulus $n$, there is more than one solution for the equation

$$d \cdot e \equiv 1 \pmod{\lambda(n)}$$

This is possible because of the modulus operation. So, if I want to create a group of keys, I can do so as long as I keep $p$ and $q$ (which are used to compute $n = pq$) secret.

How do I guarantee that two systems/users have not picked the same private key? Would it matter if they did?

Are group signatures possible with DSA or ECDSA? From the key generation steps I see on the wiki it does not look like it's possible. Am I right? I ask this because the parameters ($p$, $q$, $g$) are already public, and the only thing secret is the private key $x$, which was generated first and based on the public key that was generated. So, can I conclude that it is impossible to generate multiple private keys for a given public key?

$\endgroup$
  • $\begingroup$ While your statement about RSA having multiple equivalent private keys is technically correct, in practice this feature is useless for group signatures (or anything else I can think of). This is because 1) the keys are literally equivalent, such that there's no way for anyone to tell which key was used to create a given signature, 2) most of them are awkwardly large and slow to work with, and 3) anyone who knows $λ(n)$ can generate any of these equivalent keys, while anyone who knows any two such equivalent keys can simply take their difference to find $λ(n)$ (or a small multiple of it). $\endgroup$ – Ilmari Karonen Mar 8 '18 at 16:07
2
$\begingroup$

You seem to be confused a bit. You're talking about three or four distinct things here. At one side, you have RSA. On the other side, there's DSA and ECDSA, which are more or less based on the same cryptographical ideas. Then you talk about group signatures.

Your first question is about RSA

How do I guarantee that two systems/users have not picked the same private key? Would it matter if they did?

Two different users generate two different keys, by picking random primes $p$ and $q$, both having a bit length around $\log(n)/2$, such that the product of them ($n=pq$) will have length $\log(pq)=\log(p)+\log(q)=\log(n)$. Let's see how many primes there are for an RSA system of 4096 bits. According to Wikipedia, the prime counting function $\pi(x)$, which computes the amount of primes smaller than $x$ can be approximated by $$\pi(x)\approx\frac{x}{\ln{x}}$$. We need primes of length 2048, so we need to substract around $\pi(2^{2047})$

\begin{align} \pi(2^{2048})-\pi(2^{2047})&\approx\frac{2^{2048}}{\ln{2^{2048}}}-\frac{2^{2047}}{\ln{2^{2047}}}\\ &=\frac{2^{2048}}{2048\ln{2}}-\frac{2^{2047}}{2047\ln{2}}\\ &=2^{2037.5}-2^{2036.5}=2^{2036.5} \end{align}

That's a lot of primes to choose from. This basically guarantees that no two RSA secret keys will ever be the same.

Are group signatures possible with DSA or ECDSA?

Let's recall what a group signature is, on an abstract level: There's a group manager $\mathcal{Z}$, who chooses the group members (setup). The group members can sign a message, and a verifier only learns that the signature was created by someone in the group, without being able to pinpoint who it was. $\mathcal{Z}$ can optionally choose to reveal the original signer.

Now, DSA and ECDSA are two specific instances of a regular digital signature. These obviously aren't group signatures schemes, but regular digital signatures.

What you probably are asking about is whether it is possible to use the mathematical constructs behind DSA and ECDSA to create a group signature scheme, just like Chaum et al. constructed their scheme on RSA. (EC)DSA are based on the (elliptic curve) discrete logarithm problem(s). Indeed, there are a lot of proposed group signature schemes based on elliptic curve, as there are based on regular DH groups.

Also worth noting are ring signature schemes (RST, for example), which provide a similar but spontaneous construction, without a group manager (and thus without possible revealing of the original signer).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.