Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!columbia!tom.columbia.edu!eppstein From: eppstein@tom.columbia.edu (David Eppstein) Newsgroups: sci.crypt Subject: DES info wanted (really what it takes to break public keys) Message-ID: <4594@columbia.UUCP> Date: Fri, 8-May-87 12:40:17 EDT Article-I.D.: columbia.4594 Posted: Fri May 8 12:40:17 1987 Date-Received: Sat, 9-May-87 18:42:15 EDT References: <5845@brl-smoke.ARPA> Sender: nobody@columbia.UUCP Distribution: world Organization: Columbia University CS Department Lines: 31 In <5845@brl-smoke.ARPA>, gwyn@brl.arpa (Doug Gwyn (VLD/VMB) ) writes: > "Sufficient cleverness" was mostly an oblique reference to the widely- > held idea that one would have to factor the product of two large > primes to crack a public-key system. Some people have maintained that > any algorithm for cracking such a system amounts to an algorithm for > the factorization, but I haven't been convinced that this conclusion > is warranted. For RSA I agree with you, but there is for instance a cryptosystem such that ability to break it is provably equivalent to testing for quadratic residuosity modulo a certain number (the public key). Galil, Haber, and Yung, FOCS 1985. This is not quite the same as factoring, but actually taking square roots rather than merely knowing whether one exists is in fact random time equivalent to factoring, so this is evidence that residuosity is hard. Of course this depends on interaction rather than the more common method of one party encrypting, sending the whole thing at once, and then the other party decrypting. And it's not very practical. But it is provable. So in this case "sufficient cleverness" would have to involve some breakthroughs in number theory, not just in cryptology. Disclaimer: Galil is my advisor, and I also work with Haber and Yung. There may be other systems provably equivalent to simple number theoretic functions, but this is the one I'm most familiar with. Note to people who think they know a little number theory: residuosity is only the same as the Jacobi symbol when n is prime. The Jacobi symbol is easy to compute, but residuosity modulo composites is (apparently) not. -- David Eppstein, eppstein@cs.columbia.edu, Columbia U. Computer Science Dept.