10

Is there a procedure in place to cover the possibility that someone might find an efficient algorithm to factor large numbers and thereby break RSA encryption? This is just an instance of the more general problem where someone wants to publish a result that breaks an encryption standard. It seems like there are two main possibilities (I welcome the consideration of others):

  1. Full publication, say, to a widely-read web site, newsgroup, etc. Likely outcome: chaos on a large scale as criminals break into the private spaces of innocent individuals.

  2. Limited dissemination, perhaps to a few mathematicians or a government agency. Likely outcome: the government grabs control of the algorithm (and potentially its discoverer) and does the unpleasant things governments do with such things.

Of course, possibility 2 could easily devolve into possibility 1 if the algorithm becomes public.

Is there a consensus in the academic world about what to do with this problem?

  • 1
    I almost think this might be a better fit on Cryptography S.E., but for the final question. The question in the first sentence is for sure a better fit on Cryptography S.E. – tonysdg Nov 4 '16 at 3:23
  • 3
    There are safeguards to make sure that three-letter agencies do not take control of the algorithm: for instance, release the paper encrypted and divide the key between several trusted parties, asking them to publish their part of the key in case you "misteriously disappear". – Federico Poloni Nov 4 '16 at 8:56
  • 1
    This question could probably be even more generalized to include any kind of research with potentially nefarious results. I'm thinking here of things like medical research (development of more infectious variants of smallpox/flu/etc) and chemical/nuclear. And in fact, I recall there being discussion on having review committees in place for so-called dual-use research after the controversy over H5N1 flu research a few years back. – user0721090601 Dec 4 '16 at 4:37
  • 1
    The Rain Forest Puppy Guidelines is a protocol for revealing security vulnerabilities in products. I think it might be adapted to deal with vulnerabilities in algorithms, if there isn't already a protocol for that. – mhwombat Dec 4 '16 at 13:26
  • 1
    @mhwombat The problem in adapting it to a widely used algorithm such as RSA is: who is the "vendor" to contact? – Federico Poloni Jan 3 '17 at 13:39
5

You can prove that you have the algorithm without publishing it by publishing the factorization of a large number of well known test cases. Then people have time to adapt to a possible threat. If you are afraid of the government or the mafia, there is a sufficient number of ways to publish the algorithm at a preset date in the future, from cron jobs to hidden messages to good old notaries.

-3

Yup: name the algorithm after its creator.

What you're referring to is called "Shor's Algorithm". It's a (quantum) algorithm for integer factorization that runs in polynomial time. In layman's terms, that's a fancy way of saying it can break most public-key encryption schemes (including RSA) in a feasible, scalable, efficient manner. Of course, the catch here is that it requires a quantum computer of sufficient size -- which doesn't exist yet, but likely will in the foreseeable future.


What follows is more speculation on my part than anything else, but the question itself is (in my opinion) highly speculative, so I figure that's fair.

I imagine a variation of option 1 is the most likely scenario (but instead of a widely-read website, it would be a highly prestigious mathematical journal). Woud mass hysteria follows? I think that's unlikely. For one, symmetric-key encryption (AES) wouldn't be touched. For another, there are other asymmetric-key encryption systems that don't rely on integer factorization but rather another hard mathematical problem. And I think we can safely say that all of those hard problems won't be solved overnight.

And then there's always quantum cryptography. So I think we're going to be fine for a while longer.

  • I'd be interested to hear what the downvote is for, and if I can improve on my answer. – tonysdg Nov 4 '16 at 3:49
  • 3
    I did not downvote, but I don't like the first part of the answer: Shor's algorithm does not seem an appropriate reference here; it does not feasibly "break an encryption standard" with today's computers. And, while it is true that the fix for such a breakthrough would be simply "everybody, please regenerate your keys now with ssh-keygen -t ecdsa", we still need a responsible release strategy or some chaos would ensue in the first days, a bit like 0-days vulnerabilities but worse since it affects all kinds of e-banking. This is what the question asks, and your answer does not address it. – Federico Poloni Nov 4 '16 at 7:30
  • @FedericoPoloni: If the question is asking about how organizations/individuals should reply, then it belongs on InfoSec SE. If the question is asking about the scientific response, it belongs on Cryptography SE (which admittedly is how the first part of my answer approaches the question). But I see your point about not answering the question fully, and I'll attempt to revise it later today. Thanks for the feedback! – tonysdg Nov 4 '16 at 13:11

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.