Repository: Zapix/mtpylon (language: python)

Issue:
Generate prime numbers for PQ 
We need generate prime factors for pq exchange for authorization. p * q must be lesser then 2^63 - 1


Discussion / hints:

Fix patch:
diff --git a/mtpylon/crypto/__init__.py b/mtpylon/crypto/__init__.py
new file mode 100644
index 0000000..40a96af
--- /dev/null
+++ b/mtpylon/crypto/__init__.py
@@ -0,0 +1,1 @@
+# -*- coding: utf-8 -*-
diff --git a/mtpylon/crypto/random_prime.py b/mtpylon/crypto/random_prime.py
new file mode 100644
index 0000000..13fbfaa
--- /dev/null
+++ b/mtpylon/crypto/random_prime.py
@@ -0,0 +1,98 @@
+# -*- coding: utf-8 -*-
+import random
+
+
+first_primes_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
+                     31, 37, 41, 43, 47, 53, 59, 61, 67,
+                     71, 73, 79, 83, 89, 97, 101, 103,
+                     107, 109, 113, 127, 131, 137, 139,
+                     149, 151, 157, 163, 167, 173, 179,
+                     181, 191, 193, 197, 199, 211, 223,
+                     227, 229, 233, 239, 241, 251, 257,
+                     263, 269, 271, 277, 281, 283, 293,
+                     307, 311, 313, 317, 331, 337, 347, 349]
+
+
+def random_odd(n_bits: int) -> int:
+    """
+    Generates random odd number in range [2 ^ (n_bits - 1), 2 ^ (n_bits) - 1]
+    Odd number probably is prime number
+    """
+    assert n_bits > 0
+    value = random.getrandbits(n_bits)
+    value |= (1 << n_bits) | 1
+    return value
+
+
+def is_low_level_test_passed(value: int) -> bool:
+    """
+    Returns True if low level tests has been passed
+    """
+    for prime in first_primes_list:
+        if prime**2 > value:
+            break
+
+        if value % prime == 0:
+            return False
+
+    return True
+
+
+TESTS_COUNT = 20
+
+
+def is_composite_value(value: int, a: int, ec: int, max_pow_2: int) -> bool:
+    """
+    Returns True if value is composite. otherwise false
+    """
+    b0 = pow(a, ec, value)
+
+    if b0 == 1 or b0 == value - 1:
+        return False
+    b_prev = b0
+
+    for _ in range(max_pow_2):
+        bi = pow(b_prev, 2, value)
+
+        if bi == 1:
+            break
+        elif bi == value - 1:
+            return False
+
+        b_prev = bi
+
+    return True
+
+
+def is_miller_rabin_passed(value: int) -> bool:
+    """
+    Checks is value a prime number with Fermat theorem
+    and Miller Rabin algorithm
+    """
+    ec = value - 1
+    max_pow_2 = 0
+    while ec % 2 == 0:
+        ec >>= 1
+        max_pow_2 += 1
+
+    for i in range(TESTS_COUNT):
+        a = random.randint(2, ec)
+
+        if is_composite_value(value, a, ec, max_pow_2):
+            return False
+
+    return True
+
+
+def random_prime(n_bits: int) -> int:
+    """
+    Returns random primary number
+    """
+    while True:
+        possible_prime = random_odd(n_bits)
+
+        if (
+                is_low_level_test_passed(possible_prime) and
+                is_miller_rabin_passed(possible_prime)
+        ):
+            return possible_prime


Test patch:
diff --git a/tests/test_crypto/__init__.py b/tests/test_crypto/__init__.py
new file mode 100644
index 0000000..40a96af
--- /dev/null
+++ b/tests/test_crypto/__init__.py
@@ -0,0 +1,1 @@
+# -*- coding: utf-8 -*-
diff --git a/tests/test_crypto/test_random_prime.py b/tests/test_crypto/test_random_prime.py
new file mode 100644
index 0000000..3ae0e46
--- /dev/null
+++ b/tests/test_crypto/test_random_prime.py
@@ -0,0 +1,60 @@
+# -*- coding: utf-8 -*-
+import pytest
+
+from mtpylon.crypto.random_prime import (
+    random_odd,
+    is_low_level_test_passed,
+    is_miller_rabin_passed,
+    random_prime
+)
+
+
+prime_tests = [
+    (4, False),
+    (7, True),
+    (10, False),
+    (53, True),
+    (23438, False),
+    (1201, True),
+    (7853, True),
+    (121231303, True),
+    (121231304, False),
+    (121234591, True),
+]
+
+
+def test_random_odd():
+    value = random_odd(64)
+
+    assert value % 2 == 1
+    assert value >> 64 == 1
+
+
+@pytest.mark.parametrize(
+    'value,expected',
+    prime_tests,
+    ids=lambda x: x
+)
+def test_is_low_level_test_passed(value, expected):
+    assert is_low_level_test_passed(value) == expected
+
+
+@pytest.mark.parametrize(
+    'value,expected',
+    prime_tests,
+    ids=lambda x: x
+)
+def test_is_miller_rabin_passed(value, expected):
+    assert is_miller_rabin_passed(value) == expected
+
+
+@pytest.mark.parametrize(
+    'n_bits',
+    [64, 128, 1024],
+    ids=lambda x: x
+)
+def test_random_prime(n_bits):
+    prime = random_prime(n_bits)
+
+    assert prime % 2 == 1
+    assert prime >> n_bits == 1