Return to BSD News archive
Path: euryale.cc.adfa.oz.au!newshost.anu.edu.au!newshost.telstra.net!asstdc.scgt.oz.au!metro!metro!munnari.OZ.AU!news.ecn.uoknor.edu!news.cis.okstate.edu!news.ksu.ksu.edu!news.mid.net!newsfeeder.gi.net!newsfeed.internetmci.com!in2.uu.net!aesop.synopsys.com!news.synopsys.com!jbuck From: jbuck@synopsys.com (Joe Buck) Newsgroups: comp.os.linux.misc,comp.os.linux.development.system,comp.os.linux.networking,comp.unix.bsd.bsdi.misc,comp.unix.bsd.netbsd.misc,comp.unix.bsd.freebsd.misc Subject: Re: need secure OS to entrust millions to Date: 12 Mar 1996 18:37:10 GMT Organization: Synopsys Inc., Mountain View, CA 94043-4033 Lines: 57 Message-ID: <4i4g8m$gms@hermes.synopsys.com> References: <4gi6t6$3h9@lace.colorado.edu> <nc0453Dn96w6.93F@netcom.com> <4hhp71$cv9@senator-bedfellow.MIT.EDU> <4hsun4$d3h@park.uvsc.edu> NNTP-Posting-Host: deerslayer.synopsys.com Xref: euryale.cc.adfa.oz.au comp.os.linux.misc:92190 comp.os.linux.development.system:19396 comp.os.linux.networking:31775 comp.unix.bsd.bsdi.misc:2665 comp.unix.bsd.netbsd.misc:2475 comp.unix.bsd.freebsd.misc:15490 >] I expected more from you than argument by unconventional definition, >] Terry. Terry Lambert <terry@lambert.org> writes: >Your definition is predicated on the obscurity of a fast-factoring >algorithm. This is the unconventional definition. It isn't that the fast factoring algorithm is obscure, but that it is *unknown* and may not exist. >Is it your claim that such an algorithm is impossible? If by "fast factoring" you mean an algorithm that is not exponential in the length of the numbers to be factored, I would only claim that such an algorithm *may* be impossible. >I refer you to Godel's Theorem. Goedel's work isn't relevant, as factoring is decidable. Complexity theory is more relevant: if P = NP, then there is a polynomial-time factoring algorithm, and it is unknown whether P = NP. Since factoring is not known to be NP-complete, the reverse is not true; a fast factoring algorithm would not imply P = NP. >Typical "security through obscurity" is hiding a key in a >search space, but not securing the location of the key itself. Again, this is an unconventional definition. Security through obscurity means that someone with the source code or schematic diagram of the encryption device can break the system fairly easily, without possessing the key. >You see, I believe the NSA already has fast-factoring >capability based on the questions Robert Morris Senior (formerly >of the NSA) posed at a recent security conference. While I can't say "that's impossible", I strongly doubt it. Mathematicians have been working on factoring for hundreds of years. Yes, breakthroughs can happen, but the likelihood that the breakthrough would happen within NSA, but not anywhere else, even though a fast factoring algorithm would mean international honors to its discoverer, strikes me as just paranoia. >All that's required to crack RSA is massive parallelism and a >willingness to epend the effort, and that's assuming nothing >more than a brute-force attack. But as long as only exponential algorithms are known, adding only one bit to the key length doubles the required effort. Massive parallelism doesn't help. -- -- Joe Buck <jbuck@synopsys.com> (not speaking for Synopsys, Inc) Work for something because it is good, not just because it stands a chance to succeed. -- Vaclav Havel