🚀 go-pugleaf

tsa@cellar.org (The Silent Assassin) writes:
> > RSA works like this:
> > 1. Pick two large primes p and q (with certain extra properties). Let N=pq.
> 
> What are the extra properties, and how large should they be to be reasonable
> secure?

According to RSA's own info, the primes p and q were once recommended
to be "strong" primes (a prime number p is "strong" if there are no
large prime factors of (p-1) and (p+1)), but they claim that recent
advances in factoring techniques have removed the advantages of using
strong primes.  See the most excellent FAQ document, available for
anonymous FTP from rsa.com, for mre details.

> > 2. Pick random exponent s.  The pair (N, s) will be the public key.
> > 3. Compute secret key t, so that st = 1 mod (p-1)(q-1).  You can do
> >    this efficiently if you know p and q, but it is intractable otherwise.
> 
> Huh?  1 mod x =x, correct?  That is. modulus is the remainder of integer
> division, and when you take 1 and mod it, you will always have a remainder
> equal to your original.

This confused me the first dozen times I read it, too.

The idea is not to compute t such that st = (1 mod (p-1)(q-1)).  You
compute t such that st = 1, when taken mod (p-1)(q-1).  That's the
definition of a multiplicative inverse.  The problem in the
description is simply one of unclear terminology.

--Pat.