AnsweredAssumed Answered

How is c (encrypted message) decrypted by private key in RSA?

Question asked by 9jwVaYOznFVoYr17RUT3d9qHcGmicgBtbdBiyKT3igU= on May 14, 2019
Latest reply on May 15, 2019 by David Waugh

I've been studying the concept of RSA algorithm today, And this is what i understood.

To generate keypair -

  • Two prime numbers (p1 = 53, p2 = 59 for example) are multiplied to generate n (which will be utilized as the public modulus)
  • We use Euler's totient function on our n variable and define a new variable phi.
  • We generate a public exponent e in condition that it must be small odd number not sharing factor with our phi variable.
  • Private key d is generated from this formula:

    enter image description here

    or d = (k * (phi(n)) + 1) / e.

  • We substitute variables with numbers and get private key:

    enter image description here

    or d = (2 * (3016) + 1) / 3 = 2011

    We substitute -

  • k with 2 (by my knowledge k must be more than 0 and less than phi(n))

  • phi(n) with 3016 (Because p1 * p2 = 3127 and since the result is a prime number, We get its phi easily using p1 and p2. (phi(n) = (p1-1) * (p2-1))

  • e the exponent with 3 (Because it does not share any factors with 3016 and it's an odd number)

To use the public key -

Afterwards we can share our e and n since computers would take decades to get private key from big n.

Our communicator encodes message the into the hex and afterwards converts it to base10 integer. Communicator may also add random integer padding for protection.

When message is turned into the number, Modular exponentiation is performed mcdvoice on it:

[![enter image description here][3]][3]

So if message in numbers is 89 for example, If we do modular exponentiation on it we would get:


The Question -

If our communicator sends us 1394 which is encrypted 89 (89^3 * mod(59 * 53) = 1394), How do we use our private key to decrypt this message automatically? Is there some specific formula that must be used?

Thank you a lot for reading.