# -*- coding: utf-8 -*-
"""
Implements "homomorphic number".
:githublink:`%|py|6`
"""
import random
[docs]class HomomorphicInt:
"""
Implements an "homomorphic integer".
See `Homomorphic encryption
<https://en.wikipedia.org/wiki/Homomorphic_encryption>`_.
:githublink:`%|py|14`
"""
__slots__ = ['V', 'N', 'P', 'Q', 'E']
[docs] @staticmethod
def pgcd(a, b):
"""
Computes the :epkg:`PGCD`.
:githublink:`%|py|21`
"""
while a != b:
d = abs(a - b)
c = min(a, b)
a, b = d, c
return a
[docs] @staticmethod
def lcm(a, b):
"""
Computes the least common multiple
(:epkg:`PPCM`).
:githublink:`%|py|33`
"""
p = HomomorphicInt.pgcd(a, b)
return a * b // p
[docs] @staticmethod
def find_e(p, q):
"""
Finds one exposant for the :epkg:`RSA` encryption.
:githublink:`%|py|41`
"""
c = HomomorphicInt.pgcd(p - 1, q - 1)
qn = (p - 1) * (q - 1) // c
i = 0
while True:
h = random.randint(2, qn - 1)
pg = HomomorphicInt.pgcd(h, qn)
if pg == 1:
e = HomomorphicInt(h, (p - 1) // c, q - 1, (h, h))
try:
ei = e.inv().V
except ZeroDivisionError:
i += 1
continue
h2 = random.randint(2, p * q - 1)
e2 = HomomorphicInt(h2, p, q, (h2, h2))
try:
ei2 = e2.inv().V
except ZeroDivisionError:
i += 1
continue
return (h, ei, h2, ei2)
i += 1
if i > 100:
raise ValueError(
"Unable to find a number prime with (p-1)(q-1).")
[docs] def __init__(self, value, p=673, q=821, e=None):
"""
:param value: initial value
:param p: p for RSA
:param q: q for RSA
:param e: e for RSA (e, and inverse e)
Other prime numbers can be found at
`The First 100,008 Primes <https://primes.utm.edu/lists/small/100000.txt>`_.
:githublink:`%|py|77`
"""
self.N = p * q
self.P = p
self.Q = q
if self.N <= 2:
raise ValueError("p*q must be > 2")
self.V = value % self.N
if e is None:
self.E = HomomorphicInt.find_e(self.P, self.Q)
elif not isinstance(e, tuple):
raise TypeError("e must a tuple.")
else:
self.E = e
[docs] def new_int(self, v):
"""
Returns a :class:`HomomorphicInt <ensae_teaching_cs.td_2a.homomorphic.HomomorphicInt>` with the same encrypted parameters.
:githublink:`%|py|94`
"""
return HomomorphicInt(v, self.P, self.Q, self.E)
[docs] def __repr__(self):
"""
Usual
:githublink:`%|py|100`
"""
return 'HomomorphicInt({},{},{},{})'.format(self.V, self.P, self.Q, self.E).replace(" ", "")
[docs] def __pow__(self, n):
"""
Power operator.
:githublink:`%|py|106`
"""
if n == 0:
return HomomorphicInt(1, self.P, self.Q, self.E)
s = self.V
while n > 1:
s *= self.V
s %= self.N
n -= 1
return HomomorphicInt(s, self.P, self.Q, self.E)
[docs] def __add__(self, o):
"""
Addition.
:githublink:`%|py|119`
"""
if self.N != o.N:
raise ValueError("{0} != {1}".format(self.N, o.N))
return HomomorphicInt(self.V + o.V, self.P, self.Q, self.E)
[docs] def __sub__(self, o):
"""
Soustraction.
:githublink:`%|py|127`
"""
if self.N != o.N:
raise ValueError("{0} != {1}".format(self.N, o.N))
return HomomorphicInt(self.V - o.V, self.P, self.Q, self.E)
[docs] def __mul__(self, o):
"""
Multiplication.
:githublink:`%|py|135`
"""
if self.N != o.N:
raise ValueError("{0} != {1}".format(self.N, o.N))
return HomomorphicInt(self.V * o.V, self.P, self.Q, self.E)
[docs] def inv(self):
"""
Inversion. This only works in all cases if *n* is a prime number.
We use :math:`a^{-1} \\equiv a^{n-2} \\mod n`.
The implementation can be improved (use binary decomposition) and cached.
:githublink:`%|py|145`
"""
s = self.V
for i in range(1, self.N - 2):
s *= self.V
s %= self.N
if ((self.V * i) % self.N) == 1:
return HomomorphicInt(i, self.P, self.Q, self.E)
if ((s * self.V) % self.N) != 1:
raise ZeroDivisionError(
"Inverse of {0} does not exist.".format(self.V))
return HomomorphicInt(s, self.P, self.Q, self.E)
[docs] def __div__(self, o):
"""
Division, implies to find the inverse (so very costly).
:githublink:`%|py|160`
"""
if self.N != o.N:
raise ValueError("{0} != {1}".format(self.N, o.N))
i = o.inv()
return HomomorphicInt(self.V * i.V, self.P, self.Q, self.E)
[docs] def crypt_mult(self):
"""
Crypt a number and preserve multiplication.
We use `RSA <https://fr.wikipedia.org/wiki/Chiffrement_RSA>`_.
:githublink:`%|py|170`
"""
return self ** self.E[0]
[docs] def decrypt_mult(self):
"""
Decrypt a number and preserve multiplication.
:githublink:`%|py|176`
"""
return self ** self.E[1]
[docs] def crypt_add(self):
"""
Simple permutation.
:githublink:`%|py|182`
"""
return HomomorphicInt(self.V * self.E[2], self.P, self.Q, self.E)
[docs] def decrypt_add(self):
"""
Decrypt a number and preserve multiplication.
:githublink:`%|py|188`
"""
return HomomorphicInt(self.V * self.E[3], self.P, self.Q, self.E)