Return to BSD News archive
Path: euryale.cc.adfa.oz.au!newshost.anu.edu.au!harbinger.cc.monash.edu.au!news.mira.net.au!news.mel.connect.com.au!munnari.OZ.AU!news.ecn.uoknor.edu!solace!nntp.uio.no!news.cais.net!bofh.dot!news.mathworks.com!newsfeed.internetmci.com!uwm.edu!msunews!news From: dunham@gdl.msu.edu (Steve Dunham) 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: 16 May 1996 12:56:00 -0400 Organization: Michigan State University Lines: 34 Sender: dunham@notung.msu.edu Message-ID: <m2d9441rrz.fsf@notung.msu.edu> References: <4gi6t6$3h9@lace.colorado.edu> <4h7rdd$qeu@park.uvsc.edu> <GUTSCHK.96Mar3112617corpus@uni-muenster.de> <GHSU.96Mar7051927@unstable.nswc.navy.mil> <4ndkav$f2@pixar.com> NNTP-Posting-Host: pm131-05.dialip.mich.net X-Newsreader: September Gnus v0.40/XEmacs 19.13 Xref: euryale.cc.adfa.oz.au comp.os.linux.misc:104083 comp.os.linux.development.system:23993 comp.os.linux.networking:38648 comp.unix.bsd.bsdi.misc:3758 comp.unix.bsd.netbsd.misc:3625 comp.unix.bsd.freebsd.misc:19496 In article <4ndkav$f2@pixar.com> markv@pixar.com (Mark VandeWettering) writes: > In article <GHSU.96Mar7051927@unstable.nswc.navy.mil>, > Guan-Hsong Hsu <ghsu@relay.nswc.navy.mil> wrote: > >> The questions whether public key encryption is secure, is not related > >> to it being public. The security of RSA is based on the assumption > >> that there is no good algorithm for factorizing large prime > >> numbers. ......... > >Perhaps you meant "no good algorithm to determine if a large number is > >prime" or "no good algorithm to factorize an arbitrary large number by > >primes"? In either case, there are some standard algorithms that > >seems to work fine. So perhaps you meant something else, didn't you? > Umm, actually there are some very good probabalistic primality tests > which form the basis for key generation. There are no "good" algorithms for > determining the prime factors of a very large number however. RSA exploits > this for security. You can easily find two several hundred digit primes > and multiply them together to form the basis of your public key. To convert > this number back into the original prime factors is quite difficult. In 'Algotithms for Quantum Computation: Discrete Log and Factoring' by Peter Shor of AT&T Bell Labs (1994), the author details a polynomial-time algorithm that factors numbers into primes. The catch? The algorithm runs on a quantum mechanical touring machine, which on convential computers takes exponential time to emulate. Physicists are still trying to figure out if and how such a device can be built. Steve dunham@gdl.msu.edu