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)
[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)