Photo by Michael Dziedzic on Unsplash

Homomorphic Encryption For Division With RSA

With RSA, we have a partially homomorphic crypto-system, where we can take two values and then cipher them. Next we can divide them, and the deciphered result will be the integer division of the two values. For this we use the extended euclidean algorithm to find the inverse mod N value of cipher which performs the division.

RSA is a partially homomorphic crypto system. By the wonder of John Napier we get:

Cipher1=Vª (mod N)

Cipher2=Vᵇ (mod N)

Cipher1÷Cipher2=Vª÷Vᵇ (mod N) =(Vª× (Vᵇ)^{-1}) (modN)

To perform (Vᵇ)^{-1}, we determine the inverse of Vᵇ (mod N) [example].

An example of an encryption key is (79,3337) and a decryption key of (1019,3337). If we take 12 divided by 6 we get:

========
e is= 79
d is= 1019
n is= 3337
========
val1 is= 12
val2 is= 6
========
Cipher1 is= 760
Cipher2 is= 2086
Inverse of  2086 (mod  3337 ) is  1115
Cipher fusion is= 3139
========
Result is= 2

e=65,537 is the most commonly used exponent value in RSA, so we can try a few examples:

• val1=”130", val2=”10", e=”65,537", d=”7,240,121", n=”93,663,683" Try!
• val1=”500", val2=”25", e=”65,537", d=”428,635,793", n=”1,579,584,911" Try!