Homomorphic Encryption For Division With RSA

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!
• val1=”9999", val2=”33", e=”65,537", d=”3,046,673,861", n=”8,185,720,441" Try!

An outline of the code is here:

import sys

e=79
d=1019
n=3337
val1=18
val2=6

def extended_euclidean_algorithm(a, b):
    """
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t

def inverse_of(n, p):
    """
    Returns the multiplicative inverse of
    n modulo p.

    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.
        raise ValueError(
            '{} has no multiplicative inverse '
            'modulo {}'.format(n, p))
    else:
        return x % p

cipher1 = pow(val1,e,n)
cipher2 = pow(val2,e,n)

result = (cipher1 * inverse_of(cipher2,n)) % n

decipher = pow(result,d,n)

print '========'
print 'e is=',e

print 'd is=',d
print 'n is=',n
print '========'
print 'val1 is=',val1
print 'val2 is=',val2
print '========'

print 'Cipher1 is=',cipher1

print 'Cipher2 is=',cipher2
print 'Cipher fusion is=',result
print '========'
print 'Result is=',decipher

Conclusions

RSA can multiply and divide integers by operating on ciphers.