Results 1 to 4 of 4

Math Help - RSA Encryption

  1. #1
    Junior Member
    Joined
    Feb 2006
    Posts
    32

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jedoob View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2006
    Posts
    32

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jedoob View Post
    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
    Last edited by CaptainBlack; October 18th 2006 at 01:13 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. RSA Encryption
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 18th 2011, 07:52 PM
  2. Encryption
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2010, 05:47 AM
  3. RSA encryption process
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 20th 2010, 02:37 AM
  4. encryption vig
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 11th 2010, 11:31 PM
  5. RSA encryption
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2006, 07:24 PM

Search Tags


/mathhelpforum @mathhelpforum