*BSD News Article 63047


Return to BSD News archive

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
Path: euryale.cc.adfa.oz.au!newshost.anu.edu.au!newshost.telstra.net!act.news.telstra.net!psgrain!newsfeed.internetmci.com!howland.reston.ans.net!torn!watserv3.uwaterloo.ca!undergrad.math.uwaterloo.ca!vluu
From: vluu@undergrad.math.uwaterloo.ca (Viet-Trung Luu)
Subject: Re: need secure OS to entrust millions to
Sender: news@undergrad.math.uwaterloo.ca (news spool owner)
Message-ID: <DnxE9H.nBB@undergrad.math.uwaterloo.ca>
Date: Fri, 8 Mar 1996 01:46:29 GMT
References: <4gi6t6$3h9@lace.colorado.edu> <4h7rdd$qeu@park.uvsc.edu> <GUTSCHK.96Mar3112617corpus@uni-muenster.de> <GHSU.96Mar7051927@unstable.nswc.navy.mil>
Nntp-Posting-Host: lagrange.uwaterloo.ca
Organization: University of Waterloo
Lines: 68
Xref: euryale.cc.adfa.oz.au comp.os.linux.misc:90489 comp.os.linux.development.system:18887 comp.os.linux.networking:30993 comp.unix.bsd.bsdi.misc:2577 comp.unix.bsd.netbsd.misc:2409 comp.unix.bsd.freebsd.misc:15075

In article <GHSU.96Mar7051927@unstable.nswc.navy.mil>,
Guan-Hsong Hsu <ghsu@relay.nswc.navy.mil> wrote:
>
>   All these discussion of security is very interesting.  I am not
>familiar with either security or encryptions so it is very interesting
>to follow all these.  There is, hoever, an error that need to be
>corrected at least to clarify it for myself :
>
>In article <GUTSCHK.96Mar3112617corpus@uni-muenster.de> gutschk@uni-muenster.de (Markus Gutschke) writes:
>
>> ................................................... header deleted 
>> 
>> 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.  .........
> ^^^^^^^^^ 
>
>   Markus, there must be a mistake here.  By definition, prime numbers
>are numbers that can only be devided by itself.  So there is no
>algorithm to factorize prime numbers, period.  I might not know
>anything about encryption, but I definitely got my math right.
>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? 

That should probably be "no good algorithm for factorizing large
numbers". Oh, and your definition of prime is slightly (in a pretty
unimportant way) off (numbers > 1 whose only positive factors are 1 and
itself or something similar would do it). It's very easy to factorize a
prime number: +/-1 and +/-itself.

However, there are *no* known algorithms for factoring numbers that are
anywhere near fast enough. It's relatively trivial to generate large
prime numbers (and being 99.9999...% sure that they're prime), and by
large, we mean hundreds or even thousands of digits. My computer can
easily generate very large primes (hundreds of bits long). However, not
even the fastest supercomputers can factor numbers this size (actually
larger, since we take two large primes and multiply) in a reasonable
amount of time.

Of course, computers get faster. We are able to factor numbers that
people thought could never be factored, due to improvements in computers
and algorithms. Thus safeguarding old data with RSA encryption might not
be a good idea... however, as long as factoring algorithms remain much
slower than primality tests (which are used to generate large primes),
RSA will remain practical.

I believe that if you check again, you won't find any "standard
algorithms" that are able to factor a 1024-bit number in a reasonable
amount of time.

>    Could someone suggest a good source where I might start reading
>about the theory or the algorithm for RSA and/or encrytion in general.
>OK, if I ask people to suggest references, I should tell people what
>kind of background I have.  I have a PhD in mathematics and I am a
>researcher for US Navy on subjects unrelated to security issues.  I
>know UNIX and TCP/IP network security issues pretty well (at least for
>those affects my HP cluster) but know practically nothing about
>encryption.  But I can be taught!   

Sorry, I can't help you there... I learned most of this stuff in my
algebra class, but my notes are not with me at this time. :-( (And I
don't feel confident enough to reproduce the algorithm offhand.)

- Trung