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

1# -*- coding: utf-8 -*- 

2""" 

3@file 

4@brief Implements "homomorphic number". 

5""" 

6import random 

7 

8 

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

16 

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 

27 

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 

36 

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).") 

67 

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) 

74 

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 

90 

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) 

96 

97 def __repr__(self): 

98 """ 

99 Usual 

100 """ 

101 return f'HomomorphicInt({self.V},{self.P},{self.Q},{self.E})'.replace(" ", "") 

102 

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) 

115 

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) 

123 

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) 

131 

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) 

139 

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) 

156 

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) 

165 

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] 

172 

173 def decrypt_mult(self): 

174 """ 

175 Decrypt a number and preserve multiplication. 

176 """ 

177 return self ** self.E[1] 

178 

179 def crypt_add(self): 

180 """ 

181 Simple permutation. 

182 """ 

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

184 

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)