RSA

[Simpson, Sam]

Hi Brian,

> -----Original Message-----
> From: brian moore [mailto:bem at cmc.net]
> Sent: 12 February 2000 00:57
> To: s.simpson at mia.co.uk
> Subject: Re: RSA
> 
> 
> On Fri, Feb 11, 2000 at 11:03:52AM +0100, Jan Du¹ek wrote:
> > Hi,
> > I'm from Czech Rep. and I'm trying to make an RSA 
> encrypting algorythm. But
> > I have a little problem. I don't know how to generate 
> prime-number. I found
> > some algorythms, but there's another problem with 
> commensurableness numbers.
> > I don't know how to check if two numbers are 
> commensurableness. (I'm sorry
> > about my English :-))
> 
> Well, you can't really generate a random prime.  In order to do that,
> you'd have to be factoring really large numbers, which is generally
> impracticle (the whole point of RSA is based on the hardness of
> factoring).

Not true...It is possible to deterministically check to see if a number is
prime and the workload is FAR less than testing a primes up to the square
root.

> You'll have to do it the way everyone else does: generate a really big
> number, check it against a few low primes (ie, 2,3,5, etc, maybe up to
> 1000 or so) and then use probability to determine whether 
> it's -likely- > to be a prime or not.

Erm, not true.  It is quicker to use probalistic methods, but if 100%
assurance is required then it is still feasible (on a PC - maybe not in
constrained environments) to produce a number that is *certainly* a prime
with a "deterministic method".  See for example Silvermans posts to
sci.crypt
(http://x28.deja.com/[ST_rn=ps]/getdoc.xp?AN=564819271&CONTEXT=950363781.265
224197&hitnum=2)


> An absolute must-have is Bruce Schneier's Applied Cryptography.  This
> will give you the varying algorithms used to test for primeness.

An even better book (IMHO) for practitioners rather than people with just a
general interest is Handbook of Applied Crypto by 
A.J.Menezes, P.C.van Oorschot and S.A.Vanstone.

> Again, you won't know for certain that 'x' is prime or not... but that
> will have to suffice.  (And as I recall, if the numbers are not prime
> the whole thing doesn't work anyway, so you get an extra 
> check anyway.)


Regards,

Sam Simpson
Communications Analyst
-- http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components.  PGP Keys available at the same site.