Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Premises - please check it and critique if necessary:

If factoring the products of large numbers suddenly becomes simple, PKI goes up in smoke.

Is this correct?

If it is correct, it seems to me that the only alternative is a return to shared secret schemes… is there anything serious out there that still relies on shared secret (and not in a hybrid fashion like SSL)?

share|improve this question
up vote 4 down vote accepted

No, this is not correct.

Your fallacy here is to assume that a public-key infrastructure implies RSA. RSA is just a way of implementing an PKI.

There are other cryptographic schemes out there that do not reduce to the problem of factoring large numbers.

share|improve this answer
So it looks like my question should be formulated more along the lines of "What's the alternative should RSA collapse?" and the answer is Post-Quantum Cryptography. NTRU looks like it's probably ready for prime-time, if nothing else is. – Chris B. Behrens Dec 23 '13 at 21:23

I'll answer the second question even if nightcracker correctly stated that PKI isn't bound to integer factorization per se.

To look for symmetric encryption protocols for authentication you do not have to look further to the market for public transport cards and access cards. Many of these systems rely on a chip card that just rely on random and symmetric operations. A well known example of this is the MIFARE range of products.

With these systems, a lot of security depends on the back-end. For instance, abused or cloned cards could be black listed - which is comparable with revoking a certificate in a PKI scheme. Note that it would be trivial to make cloned cards once the master keys have been compromised.

From a cryptographic point of view, it is much better to rely on PKI than any symmetric scheme for large scale authentication. Secure key management is much harder for symmetric schemes than for PKI. Even if standard RSA and DH have been broken, you really don't want to rely on shared secrets for your key management scheme.

share|improve this answer
If you are looking for transport layer level security then I cannot help you with a known protocol. Almost any protocol relies at least on DH. You could adapt a smart card layer protocol for use on sockets, e.g. the AES secure channel in the ICAO SAC specifications (don't use the 3DES one as it fails with regard of the use of the IV). Or you could adapt TLS and remove the DH key exchange, creating session keys with a challenge/response protocol. – Maarten Bodewes Dec 22 '13 at 13:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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