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