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:
- 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.
We are given the public key (n, e)= (77, 7)
- 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
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