_IntegerBase.py 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412
  1. # ===================================================================
  2. #
  3. # Copyright (c) 2018, Helder Eijs <helderijs@gmail.com>
  4. # All rights reserved.
  5. #
  6. # Redistribution and use in source and binary forms, with or without
  7. # modification, are permitted provided that the following conditions
  8. # are met:
  9. #
  10. # 1. Redistributions of source code must retain the above copyright
  11. # notice, this list of conditions and the following disclaimer.
  12. # 2. Redistributions in binary form must reproduce the above copyright
  13. # notice, this list of conditions and the following disclaimer in
  14. # the documentation and/or other materials provided with the
  15. # distribution.
  16. #
  17. # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18. # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19. # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  20. # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  21. # COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  22. # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  23. # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24. # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  25. # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26. # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  27. # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28. # POSSIBILITY OF SUCH DAMAGE.
  29. # ===================================================================
  30. import abc
  31. from Crypto.Util.py3compat import iter_range, bord, bchr, ABC
  32. from Crypto import Random
  33. class IntegerBase(ABC):
  34. # Conversions
  35. @abc.abstractmethod
  36. def __int__(self):
  37. pass
  38. @abc.abstractmethod
  39. def __str__(self):
  40. pass
  41. @abc.abstractmethod
  42. def __repr__(self):
  43. pass
  44. @abc.abstractmethod
  45. def to_bytes(self, block_size=0, byteorder='big'):
  46. pass
  47. @staticmethod
  48. @abc.abstractmethod
  49. def from_bytes(byte_string, byteorder='big'):
  50. pass
  51. # Relations
  52. @abc.abstractmethod
  53. def __eq__(self, term):
  54. pass
  55. @abc.abstractmethod
  56. def __ne__(self, term):
  57. pass
  58. @abc.abstractmethod
  59. def __lt__(self, term):
  60. pass
  61. @abc.abstractmethod
  62. def __le__(self, term):
  63. pass
  64. @abc.abstractmethod
  65. def __gt__(self, term):
  66. pass
  67. @abc.abstractmethod
  68. def __ge__(self, term):
  69. pass
  70. @abc.abstractmethod
  71. def __nonzero__(self):
  72. pass
  73. __bool__ = __nonzero__
  74. @abc.abstractmethod
  75. def is_negative(self):
  76. pass
  77. # Arithmetic operations
  78. @abc.abstractmethod
  79. def __add__(self, term):
  80. pass
  81. @abc.abstractmethod
  82. def __sub__(self, term):
  83. pass
  84. @abc.abstractmethod
  85. def __mul__(self, factor):
  86. pass
  87. @abc.abstractmethod
  88. def __floordiv__(self, divisor):
  89. pass
  90. @abc.abstractmethod
  91. def __mod__(self, divisor):
  92. pass
  93. @abc.abstractmethod
  94. def inplace_pow(self, exponent, modulus=None):
  95. pass
  96. @abc.abstractmethod
  97. def __pow__(self, exponent, modulus=None):
  98. pass
  99. @abc.abstractmethod
  100. def __abs__(self):
  101. pass
  102. @abc.abstractmethod
  103. def sqrt(self, modulus=None):
  104. pass
  105. @abc.abstractmethod
  106. def __iadd__(self, term):
  107. pass
  108. @abc.abstractmethod
  109. def __isub__(self, term):
  110. pass
  111. @abc.abstractmethod
  112. def __imul__(self, term):
  113. pass
  114. @abc.abstractmethod
  115. def __imod__(self, term):
  116. pass
  117. # Boolean/bit operations
  118. @abc.abstractmethod
  119. def __and__(self, term):
  120. pass
  121. @abc.abstractmethod
  122. def __or__(self, term):
  123. pass
  124. @abc.abstractmethod
  125. def __rshift__(self, pos):
  126. pass
  127. @abc.abstractmethod
  128. def __irshift__(self, pos):
  129. pass
  130. @abc.abstractmethod
  131. def __lshift__(self, pos):
  132. pass
  133. @abc.abstractmethod
  134. def __ilshift__(self, pos):
  135. pass
  136. @abc.abstractmethod
  137. def get_bit(self, n):
  138. pass
  139. # Extra
  140. @abc.abstractmethod
  141. def is_odd(self):
  142. pass
  143. @abc.abstractmethod
  144. def is_even(self):
  145. pass
  146. @abc.abstractmethod
  147. def size_in_bits(self):
  148. pass
  149. @abc.abstractmethod
  150. def size_in_bytes(self):
  151. pass
  152. @abc.abstractmethod
  153. def is_perfect_square(self):
  154. pass
  155. @abc.abstractmethod
  156. def fail_if_divisible_by(self, small_prime):
  157. pass
  158. @abc.abstractmethod
  159. def multiply_accumulate(self, a, b):
  160. pass
  161. @abc.abstractmethod
  162. def set(self, source):
  163. pass
  164. @abc.abstractmethod
  165. def inplace_inverse(self, modulus):
  166. pass
  167. @abc.abstractmethod
  168. def inverse(self, modulus):
  169. pass
  170. @abc.abstractmethod
  171. def gcd(self, term):
  172. pass
  173. @abc.abstractmethod
  174. def lcm(self, term):
  175. pass
  176. @staticmethod
  177. @abc.abstractmethod
  178. def jacobi_symbol(a, n):
  179. pass
  180. @staticmethod
  181. def _tonelli_shanks(n, p):
  182. """Tonelli-shanks algorithm for computing the square root
  183. of n modulo a prime p.
  184. n must be in the range [0..p-1].
  185. p must be at least even.
  186. The return value r is the square root of modulo p. If non-zero,
  187. another solution will also exist (p-r).
  188. Note we cannot assume that p is really a prime: if it's not,
  189. we can either raise an exception or return the correct value.
  190. """
  191. # See https://rosettacode.org/wiki/Tonelli-Shanks_algorithm
  192. if n in (0, 1):
  193. return n
  194. if p % 4 == 3:
  195. root = pow(n, (p + 1) // 4, p)
  196. if pow(root, 2, p) != n:
  197. raise ValueError("Cannot compute square root")
  198. return root
  199. s = 1
  200. q = (p - 1) // 2
  201. while not (q & 1):
  202. s += 1
  203. q >>= 1
  204. z = n.__class__(2)
  205. while True:
  206. euler = pow(z, (p - 1) // 2, p)
  207. if euler == 1:
  208. z += 1
  209. continue
  210. if euler == p - 1:
  211. break
  212. # Most probably p is not a prime
  213. raise ValueError("Cannot compute square root")
  214. m = s
  215. c = pow(z, q, p)
  216. t = pow(n, q, p)
  217. r = pow(n, (q + 1) // 2, p)
  218. while t != 1:
  219. for i in iter_range(0, m):
  220. if pow(t, 2**i, p) == 1:
  221. break
  222. if i == m:
  223. raise ValueError("Cannot compute square root of %d mod %d" % (n, p))
  224. b = pow(c, 2**(m - i - 1), p)
  225. m = i
  226. c = b**2 % p
  227. t = (t * b**2) % p
  228. r = (r * b) % p
  229. if pow(r, 2, p) != n:
  230. raise ValueError("Cannot compute square root")
  231. return r
  232. @classmethod
  233. def random(cls, **kwargs):
  234. """Generate a random natural integer of a certain size.
  235. :Keywords:
  236. exact_bits : positive integer
  237. The length in bits of the resulting random Integer number.
  238. The number is guaranteed to fulfil the relation:
  239. 2^bits > result >= 2^(bits - 1)
  240. max_bits : positive integer
  241. The maximum length in bits of the resulting random Integer number.
  242. The number is guaranteed to fulfil the relation:
  243. 2^bits > result >=0
  244. randfunc : callable
  245. A function that returns a random byte string. The length of the
  246. byte string is passed as parameter. Optional.
  247. If not provided (or ``None``), randomness is read from the system RNG.
  248. :Return: a Integer object
  249. """
  250. exact_bits = kwargs.pop("exact_bits", None)
  251. max_bits = kwargs.pop("max_bits", None)
  252. randfunc = kwargs.pop("randfunc", None)
  253. if randfunc is None:
  254. randfunc = Random.new().read
  255. if exact_bits is None and max_bits is None:
  256. raise ValueError("Either 'exact_bits' or 'max_bits' must be specified")
  257. if exact_bits is not None and max_bits is not None:
  258. raise ValueError("'exact_bits' and 'max_bits' are mutually exclusive")
  259. bits = exact_bits or max_bits
  260. bytes_needed = ((bits - 1) // 8) + 1
  261. significant_bits_msb = 8 - (bytes_needed * 8 - bits)
  262. msb = bord(randfunc(1)[0])
  263. if exact_bits is not None:
  264. msb |= 1 << (significant_bits_msb - 1)
  265. msb &= (1 << significant_bits_msb) - 1
  266. return cls.from_bytes(bchr(msb) + randfunc(bytes_needed - 1))
  267. @classmethod
  268. def random_range(cls, **kwargs):
  269. """Generate a random integer within a given internal.
  270. :Keywords:
  271. min_inclusive : integer
  272. The lower end of the interval (inclusive).
  273. max_inclusive : integer
  274. The higher end of the interval (inclusive).
  275. max_exclusive : integer
  276. The higher end of the interval (exclusive).
  277. randfunc : callable
  278. A function that returns a random byte string. The length of the
  279. byte string is passed as parameter. Optional.
  280. If not provided (or ``None``), randomness is read from the system RNG.
  281. :Returns:
  282. An Integer randomly taken in the given interval.
  283. """
  284. min_inclusive = kwargs.pop("min_inclusive", None)
  285. max_inclusive = kwargs.pop("max_inclusive", None)
  286. max_exclusive = kwargs.pop("max_exclusive", None)
  287. randfunc = kwargs.pop("randfunc", None)
  288. if kwargs:
  289. raise ValueError("Unknown keywords: " + str(kwargs.keys))
  290. if None not in (max_inclusive, max_exclusive):
  291. raise ValueError("max_inclusive and max_exclusive cannot be both"
  292. " specified")
  293. if max_exclusive is not None:
  294. max_inclusive = max_exclusive - 1
  295. if None in (min_inclusive, max_inclusive):
  296. raise ValueError("Missing keyword to identify the interval")
  297. if randfunc is None:
  298. randfunc = Random.new().read
  299. norm_maximum = max_inclusive - min_inclusive
  300. bits_needed = cls(norm_maximum).size_in_bits()
  301. norm_candidate = -1
  302. while not 0 <= norm_candidate <= norm_maximum:
  303. norm_candidate = cls.random(
  304. max_bits=bits_needed,
  305. randfunc=randfunc
  306. )
  307. return norm_candidate + min_inclusive
  308. @staticmethod
  309. @abc.abstractmethod
  310. def _mult_modulo_bytes(term1, term2, modulus):
  311. """Multiply two integers, take the modulo, and encode as big endian.
  312. This specialized method is used for RSA decryption.
  313. Args:
  314. term1 : integer
  315. The first term of the multiplication, non-negative.
  316. term2 : integer
  317. The second term of the multiplication, non-negative.
  318. modulus: integer
  319. The modulus, a positive odd number.
  320. :Returns:
  321. A byte string, with the result of the modular multiplication
  322. encoded in big endian mode.
  323. It is as long as the modulus would be, with zero padding
  324. on the left if needed.
  325. """
  326. pass