home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!noc.near.net!hri.com!spool.mu.edu!darwin.sura.net!mlb.semi.harris.com!rtfm.mlb.fl.us!luckey
- From: luckey@rtfm.mlb.fl.us (Jon Luckey)
- Newsgroups: sci.crypt
- Subject: Re: More RSA questions
- Message-ID: <1992Dec20.182659.7848@rtfm.mlb.fl.us>
- Date: 20 Dec 92 18:26:59 GMT
- References: <AfATsxL0Bwx2F93KFX@transarc.com>
- Organization: We don't need no stinkin' batches!
- Lines: 40
-
- Pat_Barron@transarc.com writes:
-
- >I was tinkering around with the RSA algorithm last night, using really
- >small primes (e.g., 13 and 17) to generate keys. The idea was that I
- >only wanted to use a 16-bit modulus, so I could avoid doing any
- >extended precision arithmetic, and so I could do the exponentation via
- >a naive "compute x^y by looping and multiplying by x, y times
- >(remember, this is just a toy implementation, and it's not intended
- >to do any "real" work). But I ran into a few snags:
-
- >1) During the exponentiation, the numbers get *really* big. Like, I
- >was shocked at how quickly they got big. Is there any shortcut for
- >computing m^e mod n, without actually computing m^e first? Like, can
- >I loop somehow, accumulating partial results, until at the end I have
- >the value m^e mod n, without having actually computed m^e first? Even
- >if I choose, say, 3 or 5 as the private key, the public exponent tends
- >to be big enough that m^e is way beyond the capacity of a 32-bit
- >unsigned integer.
-
- > [another RSA question ommitted]
-
- There are already a few replies to your message giving better
- ways to calculate z=x^y mod n. But if all you want to do is simply
- modify your original program, keeping your brute force expotentiation
- method, then just do a modulus after each multiply.
-
- I.E change your code that looks like
-
- Z:=1;
- FOR I:= 1 TO Y DO Z:= Z*X;
-
- into
- Z:=1;
- FOR I:= 1 TO Y DO Z:= (Z*X) MOD N;
-
- which will keep you from running into interactions with the implict
- modulo that computer interger arithmatic involves.
-
- you might even be able to stay within 16 bit integers and not have to
- worry about 32 bits at all.
-