0
$\begingroup$

Is it possible (and is there any research I can read) to have 2 key pairs for different ciphers, for example RSA 1024 and some yet to be released EC (or other asymmetric cipher) than uses 1024 bit keys, that have the same public key?

$\endgroup$
1
  • $\begingroup$ Sure. $\:$ Just let the ciphertexts for it equal the plaintexts, and let the generation algorithms have non-zero but negligible probabilities of outputting it. $\;\;\;\;$ $\endgroup$
    – user991
    May 20, 2015 at 22:45

2 Answers 2

3
$\begingroup$

There's not really a good way to answer your question other than to explain the concepts involved. The answer can be any one of "yes", "no", or "it depends".

Asymmetric encryption algorithms use public keys that have some structure. For instance, RSA public keys are a tuple of $(n,e)$, where $e$ is the exponent, and $n=pq$ for some primes $p$, $q$ unknown to all but the holder of the private key. In modern systems, $n$ will typically be on the order of 2,048 or 4,096 bits. ECC keys, on the other hand, consist of a point $(x, y)$ on an agreed-upon elliptic curve. In typical ECC schemes, each of these points will be on the order of 192, 256, or 384 bits.

Semantically there will not be colliding keys between these algorithms, because the constituent components of these keys have different meanings. On the other hand, it's technically possible (but exceedingly unlikely in practice) to create, say, a 512-bit RSA key whose $(n, e)$ is also a point $(x,y)$ on an elliptic curve used in ECC. Or, whose bit representation of $n||e$ is equal to the bit representation of a point on an elliptic curve $x||y$.

On the other hand, if two different ECC elliptic curves intersect, you could have a point $(x,y)$ that lies at that that intersection and works for both curves. One could also hypothesize the existence of a future cryptosystem that uses public keys of the form $(n,e)$ as RSA does, but isn't RSA.

However, most cryptosystems that handle public/private keys encode the type of key and additional parameters into the public key file, so it's impossible in practice to ever have a public key that will work natively for two different types of cryptosystems.

TL;DR, it's plausible that one could find colliding keys between different ECC schemes. It's not totally inconceivable to find a colliding key between RSA/ECC by either bit representation or by actual colliding $(n,e)=(x,y)$. And it's not out of the question for some new cryptosystem to reuse keys from an existing cryptosystem verbatim. But in practice, no real world software is likely to be able to use an single public key file for more than one cryptosystem.

$\endgroup$
1
  • $\begingroup$ Yeah, sorry it was kind of a vague question. This is a great answer though. Thank you! The context is along the lines of could a (serialized) public key be used as a primary key/unique index in a database table. $\endgroup$
    – Endophage
    May 21, 2015 at 2:55
-3
$\begingroup$

Well, it is very rarely the case to have a collision. However it is still possible, especially if the Random Number Generator doesn't generate a good random. There is a group of researchers who are working on this problem you can check it out https://factorable.net

What they found is that

    • We found that 5.57% of TLS hosts and 9.60% of SSH hosts share public keys
         in an apparently vulnerable manner, due to either insufficient randomness
         during key generation or device default keys
    • We were able to remotely obtain the RSA private keys for 0.50% of TLS hosts 
         and 0.03% of SSH hosts because their public keys shared nontrivial common 
         factors due to poor randomness.
    • We were able to remotely obtain the DSA private keys for 1.03% of SSH hosts 
         due to repeated signature randomness.

You may also check this article http://www.technewsworld.com/story/74436.html

$\endgroup$
4
  • $\begingroup$ This does not attempt to answer the question. $\endgroup$
    – Maeher
    May 21, 2015 at 9:28
  • $\begingroup$ @Maeher Sorry I did answer the question and put some efforts $\endgroup$
    – Nayef
    May 21, 2015 at 11:17
  • 4
    $\begingroup$ No, the answer is off-topic and does not adress the question in any way. The question is whether it is possible to have two unrelated public key encryption schemes that are able to use the same public key. The question has nothing to do with collisions in the key-generation algorithm. $\endgroup$
    – Maeher
    May 21, 2015 at 12:29
  • 1
    $\begingroup$ @Nayef it looks like you misunderstood the question ... it is about public keys from different schemes colliding, not about collisions within one scheme (RSA and DSA in your example). $\endgroup$ May 25, 2015 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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