This is a simple exercise to help my personal understanding of RSA. I'm not trying to do anything that will have real world security.
I want to compute the RSA decryption exponent
d = e−1 mod φ(n).
I would prefer to make the calculation using a method similar to this:
int d = (k * (p - 1) * (q - 1) + 1) / e;
e is the RSA encryption exponent and
q are randomly generated primes. I will use small primes (e.g., 7, 13) and I will also pick
e to be something small like 5.
Why do I want to do it similar to that method? Although I am using the Java language, I am looking for a simple "hand calculation" method. In particular I do not want to use something similar to the following method, which is what I find recommended on all the programming-related forums:
BigInteger d = e.modInverse(totient);
I am trying to avoid calling any external functions. To me modInverse() is a "black box" and I'm trying to avoid those so that I can increase my understanding (although I'm working at a simple level of understanding).
Once I have picked
q how do I find
k? Once I have
k, of course, finding
d is trivial in my example.
The value of
k should be an integer (it must result in an integer value of
d, the decryption exponent).
With p=13,q=7,e=5 then
k = 2 (and therefore, d = 29).
I need to find integer
k given any small integer
e, and small primes
q. (Also, I would prefer not to iterate, if possible.)
Please keep the answers simple because I don't have any math background. Thanks.
EDIT: claried based on comments.