Multiplicative inverse of n mod m ((Euclidean algorithm))In cryptography, we often need \(n^{−1}\), which is a multiplicative inverse of n mod m, i.e. \(n/(n^{−1}) = 1 \mod m\). It is used in the calculation of the decryption key in RSA, and in other cryptography methods. With RSA, we get (e x d) mod (N) = 1, where we have e and N, and must calculate d using the multiplicative inverse of n mod m. |
Quiz
So I select two prime numbers of 13 and 17, and my value of N becomes (13-1)x (17-1) = 192. So can you determine what my decryption key is if my encryption key is 71 and N is 192 (e x d Mod N =1)? [Answer]
Examples
The following are some examples:
- Inverse of 53 mod 120 (Ans: 77)?. Try [Check]
- Inverse of 31 mod 110 (Ans: 71)?. Try [Check]
- Inverse of 3 mod 20 (Ans: 7)?. Try RSA Ex 1 for d: [Check]
- Inverse of 7 mod 20 (Ans: 3)?. Try RSA Ex 2 for d: [Check]
- Inverse of 7 mod 120 (Ans: 103)?. Try RSA Ex 3 for d: [Check]
- Inverse of 79 mod 3220 (Ans: 1019)?. Try RSA Ex 4 for d: [Check]
- Inverse of 7 mod 880 (Ans: 503)?. Try RSA Ex 5 for d: [Check]
- Inverse of 17 mod 3120 (Ans: 2753)?. Try RSA Ex 6 for d: [Check]
For example is we have n of 53 and m of 120:
\(n^{-1} = 53^{-1} \pmod {120}\)
\( 53 \times (n^{-1}) \pmod {120} = 1 \)
Let's try 77:
\( 53 \times 77 \pmod {120} = 4081 \pmod {120} = 1 \)
Code
The following is an outline of the code:
string get_inv(long _e, long _PHI) { BigInteger e = new BigInteger(Convert.ToString(_e)); BigInteger PHI = new BigInteger(Convert.ToString(_PHI)); BigInteger[] u = new BigInteger[3]; BigInteger[] v = new BigInteger[3]; BigInteger q, temp1, temp2, temp3; u[0] = new BigInteger("1"); u[1] = new BigInteger("0"); u[2] = PHI; v[0] = new BigInteger("0"); v[1] = new BigInteger("1"); v[2] = e; while (!v[2].Equals(new BigInteger("0"))) { q = u[2].Divide(v[2]); temp1 = u[0].Subtract(q.Multiply(v[0])); temp2 = u[1].Subtract(q.Multiply(v[1])); temp3 = u[2].Subtract(q.Multiply(v[2])); u[0] = v[0]; u[1] = v[1]; u[2] = v[2]; v[0] = temp1; v[1] = temp2; v[2] = temp3; } long val = Convert.ToInt64(Convert.ToString(u[1])); _PHI = Convert.ToInt64(Convert.ToString(PHI)); return (Convert.ToString(u[1])); //if (val < 0) return (val + _PHI); //else return (val); }