# RSA Encryption

• Oct 18th 2006, 08:34 AM
jedoob
RSA Encryption
Hi,

Given that an RSA public key is (77,7).

How can I find the private key for this? Please could you show step by step, how this is done.

Thanks.
• Oct 18th 2006, 09:44 AM
CaptainBlack
Quote:

Originally Posted by jedoob
Hi,

Given that an RSA public key is (77,7).

How can I find the private key for this? Please could you show step by step, how this is done.

Thanks.

The RSA key generation algorithm is:
1. Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits. [See note 1].
2. Compute n = pq and (φ) phi = (p-1)(q-1).
3. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1. [See note 2].
4. Compute the secret exponent d, 1 < d < phi, such that
ed ≡ 1 (mod phi). [See note 3].
5. The public key is (n, e) and the private key is (n, d). The values of p, q, and phi should also be kept secret.
• n is known as the modulus.
• e is known as the public exponent or encryption exponent.
• d is known as the secret exponent or decryption exponent.
We are given the public key (n, e)= (77, 7)

Now p and q are primes such that pq=n, so p=11, q=7 (the order does not
matter). So phi = 60.

We know e=7, so we seek a d such that ed=1 mod 60, well d=9 will do,
and so the private key is (77, 9).

RonL
• Oct 18th 2006, 10:09 AM
jedoob
RSA Encryption
Thanks.

How would I go about doing this, for larger values of n? e.g with 3 figures, where the primes cannot be so easily found.
• Oct 18th 2006, 10:28 AM
CaptainBlack
Quote:

Originally Posted by jedoob
Thanks.

How would I go about doing this, for larger values of n? e.g with 3 figures, where the primes cannot be so easily found.

The idea is that for large n factoring it should be hard, otherwise you don't
have much of a cypher.

However three figures is not large enough to make this difficult and it can still
be done with a bit of persistence. In fact with a modern desk top PC and a C
compiler I would have thought 10 digits is still a piece of cake, and 12 if you
don't mind waiting a bit.

n should always be the product of two similarly sized primes, as one of
the must be < sqrt(n), so with three digits for n that leaves you with one
of the primes is <32 which is not a lot of work to check, just divide n by
each of the primes <32 until you find one that divides n, and do the division
to find the other prime factor.

RonL