1
$\begingroup$

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, where 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;

where e is the RSA encryption exponent and p 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 e, p and 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).

Example:

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 p and 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.

$\endgroup$
8
  • $\begingroup$ Be aware that this is not a programming site, and most people here will not necessarily know Java. $\endgroup$ Sep 24 '16 at 22:53
  • $\begingroup$ My question has little or nothing to do with Java. I mentioned Java for context. I'm actually looking for a simple way to compute k WITHOUT using any special Java libraries (or any other special programming techniques). $\endgroup$
    – MountainX
    Sep 24 '16 at 22:55
  • $\begingroup$ @Moo I'm not sure what you are saying. I need simple answers. If you are saying that only certain values of k produce an integer result, that's exactly why I am asking my question. In essence, I'm asking how to compute a k that gives an integer result. (I'm only interested in working with small integers.) Or did I misunderstand you completely? $\endgroup$
    – MountainX
    Sep 24 '16 at 23:05
  • $\begingroup$ @Moo Calcluating (k * (p - 1) * (q - 1) + 1) / e for k=1...72 gives 15 integers. However, any of these integer values seem to work correctly as the decryption exponent. (So far I have only tested a few and I'll test more.) Could you please make your point more directly? Thanks $\endgroup$
    – MountainX
    Sep 24 '16 at 23:21
  • $\begingroup$ @ Moo: 15 of those give result = 1. They are the same 15 values where (k * (p - 1) * (q - 1) + 1) / e results in an integer. That's not surprising, but I was hoping for a way to find an integer k without iterating. Are you suggestion there isn't such a way? $\endgroup$
    – MountainX
    Sep 24 '16 at 23:52
2
$\begingroup$

For such small values, of course iteration is the simplest method. But for larger parameters, the standard procedure (probably used by Java's modInverse method) is the extended Euclidean algorithm for computing modular inverses. This is not especially complicated, but neither is it trivial to program. Have fun!

$\endgroup$
1
  • $\begingroup$ If I understand it correctly, the extended Euclidean algorithm is an iterative function. Is that correct? If so, I assume that means there is no non-iterative approach that will work. Thanks. $\endgroup$
    – MountainX
    Sep 25 '16 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.