How to calculate the Modular Multiplicative inverse of a number in the context of RSA encryption?
views:
101answers:
3
+2
Q:
How to calculate the Modular Multiplicative inverse of a number in the context of RSA encryption?
+3
A:
Direct Modular Exponentiation
The direct modular exponentiation method, as an alternative to the extended Euclidean algorithm, is as follows:
Source: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
cheers
Daniel
Daniel Gartmann
2010-07-27 14:45:57
This method requires the order of the group in which you take the inverse. In the case of RSA you usually don't know this.
abc
2010-07-28 09:20:16
You know it if the modulus is prime - it's P-1. For an RSA key at the time of key generation you may know it as well (P-1)*(Q-1). Once the key pairs are created, the factorization of the modulus is thrown away, as knowing the order of the group is required to create a key pair and is equivalent to finding the private key.
phkahler
2010-07-28 13:47:56
Since in RSA, to find the private key you need to find the inverse of `e (mod φ(n))`, using this method requires you to calculate `φ(φ(n))`, which is equivalent to factoring `φ(n)`. So, @abc is right: you can't use this method; I did not even think about this earlier.
BlueRaja - Danny Pflughoeft
2010-07-28 21:23:07
It's easy to compute phi(phi(n)) if the RSA primes are safe primes. See my comment to http://stackoverflow.com/questions/3209665/for-rsa-how-do-i-calculate-the-secret-exponent/3209797#3209797. But it's just fun to think about and tinker with, the extended euclidean algorithm always works fast.
GregS
2010-07-29 00:03:35
+2
A:
There are two algorithms explained in detail in the Modular multiplicative inverse Wikipedia article.
Bill the Lizard
2010-07-27 14:47:03
+3
A:
Use the Extended Euclidean Algorithm, which is significantly faster than direct modular exponentiation in practice.
BlueRaja - Danny Pflughoeft
2010-07-27 16:16:47