# Code source de ensae_teaching_cs.td_2a.homomorphic

# -*- 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)

"""

: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]

"""
Simple permutation.

:githublink:%|py|182
"""
return HomomorphicInt(self.V * self.E[2], self.P, self.Q, self.E)

:githublink:%|py|188