🚀 go-pugleaf

In article <AfATsxL0Bwx2F93KFX@transarc.com>, Pat_Barron@transarc.com writes:
|> I was tinkering around with the RSA algorithm last night [...]
|> 
|> 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?

Yes.  Do the mod operations after each "round" (iteration or recursion)
in your exponentiation algorithm.  See procedure expmod in SICP (*),
page 47.


|> 2)  I chose the private key and public exponent by brute force.  Is
|> a better way to choose the private key than to factor (p-1)(q-1) and
|> choose something with no common factors?

Since factoring is _expensive_ for large (p-1)(q-1), you're better off
by generating a random integer e in some suitable range, say the range
of all the integers which have one digit less than (p-1)(q-1), and then
increment e until the gcd of e and (p-1)(q-1) is 1.  An implementation
of gcd can be found in SICP (*), page 44.

    SICP:  Structure and Interpretation of Computer Programs.
    By H. Abelson and G. Sussman.  MIT Press, 1985.

This is a great introductory book on computer programming.  It uses a
nice little Lisp dialect called Scheme. All Scheme implementations I
know support bignums, so you wouldn't even have to worry about the
size of your integers.

-- 
Robert Marti                    |  Phone:    +41 1 254 72 60
Informationssysteme             |  FAX:      +41 1 262 39 73
ETH-Zentrum                     |  E-Mail:   marti@inf.ethz.ch
CH-8092 Zurich, Switzerland     |