🚀 go-pugleaf

In article <AfATsxL0Bwx2F93KFX@transarc.com> 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.
>
Take the modulus after each multiplication, not once after you are finished
with all the multiplications i the exponentiation.

>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?  Is there a better way to
>find the public exponent than just trying all the possible values
>until you find it (which is what I did)?
>
Use Euclid's algorithm; it's easy.

I have a suggestion.  I wrote an article in the May 92 issue of Dr. Dobbs
Journal about public-key cryptography.  It discusses how to do RSA.  There's
one realy irritating typo in the second column of page 26, but other than
that the article gives a good description of how RsA works.

Bruce