*BSD News Article 68697


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