Coverage for src/ensae_teaching_cs/td_2a/homomorphic.py: 86%

100 statements

, created at 2023-01-27 05:44 +0100

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)

117 """

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]

180 """

181 Simple permutation.

182 """

183 return HomomorphicInt(self.V * self.E[2], self.P, self.Q, self.E)