Coverage for src/ensae_teaching_cs/td_2a/homomorphic.py: 85%
100 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief Implements "homomorphic number".
5"""
6import random
9class HomomorphicInt:
10 """
11 Implements an "homomorphic integer".
12 See `Homomorphic encryption
13 <https://en.wikipedia.org/wiki/Homomorphic_encryption>`_.
14 """
15 __slots__ = ['V', 'N', 'P', 'Q', 'E']
17 @staticmethod
18 def pgcd(a, b):
19 """
20 Computes the :epkg:`PGCD`.
21 """
22 while a != b:
23 d = abs(a - b)
24 c = min(a, b)
25 a, b = d, c
26 return a
28 @staticmethod
29 def lcm(a, b):
30 """
31 Computes the least common multiple
32 (:epkg:`PPCM`).
33 """
34 p = HomomorphicInt.pgcd(a, b)
35 return a * b // p
37 @staticmethod
38 def find_e(p, q):
39 """
40 Finds one exposant for the :epkg:`RSA` encryption.
41 """
42 c = HomomorphicInt.pgcd(p - 1, q - 1)
43 qn = (p - 1) * (q - 1) // c
44 i = 0
45 while True:
46 h = random.randint(2, qn - 1)
47 pg = HomomorphicInt.pgcd(h, qn)
48 if pg == 1:
49 e = HomomorphicInt(h, (p - 1) // c, q - 1, (h, h))
50 try:
51 ei = e.inv().V
52 except ZeroDivisionError:
53 i += 1
54 continue
55 h2 = random.randint(2, p * q - 1)
56 e2 = HomomorphicInt(h2, p, q, (h2, h2))
57 try:
58 ei2 = e2.inv().V
59 except ZeroDivisionError:
60 i += 1
61 continue
62 return (h, ei, h2, ei2)
63 i += 1
64 if i > 100:
65 raise ValueError(
66 "Unable to find a number prime with (p-1)(q-1).")
68 def __init__(self, value, p=673, q=821, e=None):
69 """
70 @param value initial value
71 @param p p for RSA
72 @param q q for RSA
73 @param e e for RSA (e, and inverse e)
75 Other prime numbers can be found at
76 `The First 100,008 Primes <https://primes.utm.edu/lists/small/100000.txt>`_.
77 """
78 self.N = p * q
79 self.P = p
80 self.Q = q
81 if self.N <= 2:
82 raise ValueError("p*q must be > 2")
83 self.V = value % self.N
84 if e is None:
85 self.E = HomomorphicInt.find_e(self.P, self.Q)
86 elif not isinstance(e, tuple):
87 raise TypeError("e must a tuple.")
88 else:
89 self.E = e
91 def new_int(self, v):
92 """
93 Returns a @see cl HomomorphicInt with the same encrypted parameters.
94 """
95 return HomomorphicInt(v, self.P, self.Q, self.E)
97 def __repr__(self):
98 """
99 Usual
100 """
101 return f'HomomorphicInt({self.V},{self.P},{self.Q},{self.E})'.replace(" ", "")
103 def __pow__(self, n):
104 """
105 Power operator.
106 """
107 if n == 0:
108 return HomomorphicInt(1, self.P, self.Q, self.E)
109 s = self.V
110 while n > 1:
111 s *= self.V
112 s %= self.N
113 n -= 1
114 return HomomorphicInt(s, self.P, self.Q, self.E)
116 def __add__(self, o):
117 """
118 Addition.
119 """
120 if self.N != o.N:
121 raise ValueError(f"{self.N} != {o.N}")
122 return HomomorphicInt(self.V + o.V, self.P, self.Q, self.E)
124 def __sub__(self, o):
125 """
126 Soustraction.
127 """
128 if self.N != o.N:
129 raise ValueError(f"{self.N} != {o.N}")
130 return HomomorphicInt(self.V - o.V, self.P, self.Q, self.E)
132 def __mul__(self, o):
133 """
134 Multiplication.
135 """
136 if self.N != o.N:
137 raise ValueError(f"{self.N} != {o.N}")
138 return HomomorphicInt(self.V * o.V, self.P, self.Q, self.E)
140 def inv(self):
141 """
142 Inversion. This only works in all cases if *n* is a prime number.
143 We use :math:`a^{-1} \\equiv a^{n-2} \\mod n`.
144 The implementation can be improved (use binary decomposition) and cached.
145 """
146 s = self.V
147 for i in range(1, self.N - 2):
148 s *= self.V
149 s %= self.N
150 if ((self.V * i) % self.N) == 1:
151 return HomomorphicInt(i, self.P, self.Q, self.E)
152 if ((s * self.V) % self.N) != 1:
153 raise ZeroDivisionError(
154 f"Inverse of {self.V} does not exist.")
155 return HomomorphicInt(s, self.P, self.Q, self.E)
157 def __div__(self, o):
158 """
159 Division, implies to find the inverse (so very costly).
160 """
161 if self.N != o.N:
162 raise ValueError(f"{self.N} != {o.N}")
163 i = o.inv()
164 return HomomorphicInt(self.V * i.V, self.P, self.Q, self.E)
166 def crypt_mult(self):
167 """
168 Crypt a number and preserve multiplication.
169 We use `RSA <https://fr.wikipedia.org/wiki/Chiffrement_RSA>`_.
170 """
171 return self ** self.E[0]
173 def decrypt_mult(self):
174 """
175 Decrypt a number and preserve multiplication.
176 """
177 return self ** self.E[1]
179 def crypt_add(self):
180 """
181 Simple permutation.
182 """
183 return HomomorphicInt(self.V * self.E[2], self.P, self.Q, self.E)
185 def decrypt_add(self):
186 """
187 Decrypt a number and preserve multiplication.
188 """
189 return HomomorphicInt(self.V * self.E[3], self.P, self.Q, self.E)