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.

Printable View

- October 18th 2006, 09:34 AMjedoobRSA 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. - October 18th 2006, 10:44 AMCaptainBlack
The RSA key generation algorithm is:

- 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]. - Compute n = pq and (φ) phi = (p-1)(q-1).
- Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1. [See note 2].
- Compute the secret exponent d, 1 < d < phi, such that

ed ≡ 1 (mod phi). [See note 3]. - 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.

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 - Generate two large random primes, p and q, of approximately equal size such that their product
- October 18th 2006, 11:09 AMjedoobRSA 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. - October 18th 2006, 11:28 AMCaptainBlack
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