Генерация простого числа заданного размера?

Первый шаг работы алгоритма RSA — генерация двух простых чисел p и q заданного размера (например, 1024 бита каждое — одинаковый размер повышает криптостойкость).


Насколько я понял, для решения задачи перебора простых чисел до некоторого заданного предела предназначены:


Решето Эратосфера

Решето Сундамана

Решето Аткина (быстрый, современный)


Однако задача генерации простого числа заданного размера решается обычно (?) методом проб, т.е.


1) Генерируем случайное целое число заданного размера;

2) Проверяем его на простоту;

3) Если простое — PROFIT, если не простое — посторяем с п. 1.


Проверка на простоту в п. 2 осуществляется уже при помощи других методов.


Так вот, мне интересна наиболее быстрая имплементация (желательно Python) какого-либа из подходов, т.е. функция


def get_prime(nbits):

""" Вот это интересно """


а также любая другая помощь/информация по теме.
  • Вопрос задан
  • 30132 просмотра
Решения вопроса 1
afiskon
@afiskon
У Шнайера этот вопрос хорошо освящен (стр 296 «Прикладной криптографии» — pdf легкой найти). Генерируете случайное p. Сначала проверяете p на четность (по младшему биту). Затем проверяете остаток от деления на 3,5,7,… — первые простые числа кроме 2, меньше 2000. Затем прогоняете 5 тестов Рабина-Миллера (google) для 5 разных случайных чисел a. Если прошел все 5 — можно считать число простым. В целях эффективности можно генерировать небольшие a.

Еще, возможно, вас заинтересует статья об эллиптических кривых — http://eax.me/elliptic-curves-crypto/. Криптография на ЭК не менее безопасна, чем RSA, но существенно проще в реализации и более эффективна благодаря тому, что ключи длиной 256 бит так же надежны, как RSA ключи длиной 4096 бит.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 9
@s0rr0w
Первое, что приходит на ум, это скачать где-то уже вычисленный массив простых чисел и уже с ними работать. Так будет не просто в разы быстрее, а катастрофически быстрее предложенного вами способа.
Ответ написан
@MikhailEdoshin
Вот сниппет непосредственно из реализации RSA:

def rmspp(number, attempts=28):
    """
    rmspp(n, attempts=28) -> True if n appears to be primary, else False
    rmspp: Rabin-Miller Strong Pseudoprime Test
    http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
    """
    if number < 2:
        return False
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    # Given an odd integer n, let n = 2**r*s+1, with s odd... 
    s = number - 1
    r = 0
    while s % 2 == 0:
        r += 1
        s /= 2
    while attempts:
        # ... choose a random integer a with 1 ≤ a ≤ n-1
        a = randint(1, number-1)
        # Unless a**s % n ≠ 1 ...
        if mod_exp(a, s, number) != 1:
            # ... and a**((2**j)*s) % n ≠ -1 for some 0 ≤ j ≤ r-1 
            for j in range(0, r):
                if mod_exp(a, (2**j)*s, number) == number-1:
                    break
            else:
                return False
        attempts -= 1
        continue
    # A prime will pass the test for all a.
    return True

def mod_exp(base, exponent, modulus):
    """
    mod_exp(b, e, m) -> value of b**e % m
    Calculate modular exponentation using right-to-left binary method.
    http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
    """
    result = 1L
    while exponent > 0:
        if (exponent & 1) == 1:
            result = (result * base) % modulus
        exponent >>= 1
        base = (base * base) % modulus
    return result

Вызывается он внутри генерации ключей (с дополнительными оптимизациями) примерно так:

def keys(bits):
    """
    keys(bits) -> (public, private)
    Generate public and private RSA keys of the given size.
    """
    # Pragma: use a fixed e, the fourth Fermat prime (0b10000000000000001)
    e = 2**16+1
    while True:
        # Generate two large prime numbers p and q, n = pq and φ = (p-1)(q-1)
        s = bits / 2
        mask = 0b11 << (s - 2) | 0b1 # two highest and the lowest bit
        while True:
            p = getrandbits(s) | mask
            # Pragma: check p % e here to guarantee that φ and e are coprimes
            if p % e != 1 and rmspp(p): 
                break
        s = bits - s
        mask = 0b11 << (s - 2) | 0b1 # same as above, but maybe different s
        while True:
            q = getrandbits(s) | mask
            if q != p and q % e != 1 and rmspp(q): 
                break
        n = p * q
        phi = (p - 1) * (q - 1)
        # Pragma: e is chosen already and is relative prime to φ
        # Compute d, a modular multiplicative inverse to e (i.e. e*d % φ = 1)
        d = mmi(e, phi)
        if d: # if not, the process will repeat
            break
    return (n, e), (n, d)

ef mmi(a, m):
    """
    mmi(a, m) -> x, such as ax % m = 1
    mmi is a Modular Multiplicative Inverse
    See http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
    """
    gcd, x, q = egcd(a, m)
    if gcd != 1:
        # The a and m are not coprimes, so the inverse doesn't exist
        return None
    else:
        return (x + m) % m

def egcd(a, b):
    """
    egcd(a, b) -> d, x, y, such as d == gcd(a, b) == ax + by
    egcd is an Extended Greatest Common Divisor
    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    """
    if b == 0:
        return (a, 1, 0)
    else:
        d, x, y = egcd(b, a % b)
        return d, y, x - y * (a / b)

Насчет «доли вероятности» — насколько я помню, в алгоритме Миллера-Рабина при увеличении числа попыток вероятность ложного срабатывания легко сделать сколь угодно малой (например, меньше чем верояность отказа железа :), и, кроме того, насколько я помню, конкретно в случае с RSA полученные числа будут еще раз проверены при расчете modular multiplicative inverse, а его невозможно будет получить, если число не простое (приведенная функция keys() в таком случае продолжает цикл генерации).
Ответ написан
@BiTHacK
Обычно генерация идёт так: генерируем случайно число заданного размера, проверяем его тестом Миллера-Рабина с кол-вом раундов ln(m), если число составное, то добавляем единицу и проверяем вновь полученное число, в противном случае алгоритм завершён, искомое число получено. Встаёт вопрос, а вдруг полученное число составное? Тест Миллера-Рабина с указанным выше числом раундов даёт надёжность в 4^(-ln(m)), а 100% гарантию на 1024 битное число вы не получите за приемлемое время. m — текущее число.
Ответ написан
apangin
@apangin
Реализацию на Java можно взять в исходниках JDK: $JDK_HOME/src.zip/java/math/BigInteger.java,
функция BigInteger.probablePrime(). Исходники достаточно подробно откомментированы.
А также ту часть алгоритма RSA, где эта функция используется: sun/security/rsa/RSAKeyPairGenerator.java
Ответ написан
Комментировать
@yeputons
Один из самых простых и эффективных — тест Миллера-Рабина, являющийся надстройкой над малой теоремой Ферма. Пишется строк в 10-15.
Ответ написан
Комментировать
@mib431
Если нужно сгенерировать заведомо простое число, то посмотрите на применение методов, использующих разложение числа n-1 на простые множители (так называемые «n-1—методы»). В частности, это тест Поклингтона. С помощью него достаточно легко строится метод построения последовательности простых чисел теоретически любой длины. ЕМНП некоторая модификация этого метода использовалась в старом отечественном ГОСТ'е на цифровую подпись.
Ответ написан
@codecity
Можно определить простое число или нет только с определенной долей вероятности.

Отсеять львиную долю «не простых» чисел можно с помощью малой теоремы Ферма. Но этого достаточно лишь для начала.
Ответ написан
Amper
@Amper
В sage есть cython-обертка для библиотеки PARI, там есть функция isprime, реализующая методы ARP-CL и Поклингтона-Лемера.
Ответ написан
@yruslan
Хорошая реализация криптографических алгоритмов с открытым исходным текстом: PolarSSL. Особенность этой библиотеки в том, что компоненты между собой связаны слабо и легко взять из нее только то, что нужно в данном случае.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы