Получение случайного простого числа

[uni]

Доброго. Ищу программную рализацию формирования случайного простого числа. Я не математик, поэтому заумных фраз про "поле вычетов" и "появляется надежда на то..." не понимаю.
В "Конкретной математике" прочитал, что формулы такой нет (в смысле генерации простых чисел, на стр. 132 русского перевода). В Википедии приводится два "типовых" алгоритма:
Случайное_простое_число

Честно скажу, ни первого, ни второго не понял. Особенно второго алгоритма. На стр. 100 книжки "Введение в криптографию" под ред. В. В. Ященко (см. на bookfi.org) есть описание, сслыку на которое можно увидеть в Википедии.

Нужно для изучения на примере криптосистемы с открытым ключом Эль-Гамаля, где первым пунктом идёт:
1. Генерируется случайное простое число p длины n битов.

В описании обоих алгоритмов я так и не понял: даётся ли гарантия простоты получаемого числа? Почему нельзя написать просто: "полученное число является простым". Так нет, всё только с какой-то степенью вероятности. Особенно поразила фраза в книжке по криптографию "В этом случае появляется надежда на то, что N - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2." Интересно, как это можно оформить в виде алгоритма? Почему "надежда" и почему "попытаться"?

В общем, какой-то тёмный лес. Пока сделаю на заранее извесных табличных данных, но всё-таки хотелось бы узнать как это выглядит в программной реализации. Эта генерация - единственное чего я не смог реализовать, а фишка криптосистемы в том, что "случайность" должна быть "как бы настоящая".

Да, кстати, если в CryptoAPI есть такой генератор, то тоже хотелось бы знать какой функцией он вызывается. Что-то с ходу не нашёл.

[nnosipov]

uni в сообщении #490835 писал(а):

Особенно поразила фраза в книжке по криптографию "В этом случае появляется надежда на то, что N - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2." Интересно, как это можно оформить в виде алгоритма? Почему "надежда" и почему "попытаться"?

Указанным способом действительно строятся настоящие простые числа (теорема 2 и её следствие дают гарантию простоты). Сам алгоритм построения нетрудно реализовать; на обычном бытовом компьютере построение 1000-значного простого числа займёт несколько минут. Другое дело --- сгодятся ли так построенные простые числа для разнообразных криптографических нужд.

[uni]

Уже хорошо, а то я был в неуверенности, т.к. не смог понять математических выкладок. Значит есть смысл понять что всё-таки там такое описано. Жаль, что в Википедии не нашлось никого, кто бы эти "типовые" алгоритмы понял и написал "типовые" реализации, а то как-то странно. Для многих других типовых тем таковые реализации есть.

[nnosipov]

Вот реализация этого алгоритма в системе компьютерной алгебры Maple:

GenPrime:=proc(p,k)
local i,S,S_next,R,a;
S:=p;
for i from 1 to k do
R:=2*rand((S+1)/2..2*S+1)();
S_next:=S*R+1;
a:=rand(1..10^5)();
while a&^(S*R) mod S_next>1 or igcd(a&^R mod S_next-1,S_next)>1 do
R:=2*rand((S+1)/2..2*S+1)();
S_next:=S*R+1;
a:=rand(1..10^5)()
end do;
S:=S_next;
end do
end proc:

А вот пример работы:

GenPrime(2011,8);
  5095690943062718249685539246930843211597757758480712682455292649\
        1515923215684665296040406306720212279260074741916237739598\
        0605134590838127279102470370148615930205662427904633378589\
        6847560315249467448147322313924286444289104055399776432276\
        0564574078736162536430796025571747514793507499823426588156\
        2525437057175944003809239881555530164691001772303375035483\
        8019153778454697536621837377298109042407530981177139060497\
        7924235579528414742765527630844960382611776950773933419082\
        1259874247062795956543428070728638346912819806075131327217\
        7912430468015161473960144229573493768851486188204162816005\
        4486534154987781017505670744423846729278854524336237137219\
        1793880511396512594744147905032523151213459401929070882988\
        2229760418639182409931562971501331759490369103606869721467\
        7400935914206597661072636022464992776016438429259723889430\
        7616198218915381724549816038914196865356659600154717491845\
        3631620000857524455933763223834912384992254514422263069826\
        630224750385779850736047

[uni]

Ух ты, спасибо, не ожидал. Выглядит прям как по книжке. На Дельфи перепишу, попробую, покажу потом.

Я там в книжке не понял математической записи второго условия, какие-то скобки... теперь дошло что это означает.

-- Вс окт 09, 2011 12:27:53 --

Пожалуй я ещё обнаглею и спрошу про второй шаг. Далее мне нужно вычислить произвольное целое число g, являющееся первообразным корнем по модулю p. До меня долго доходило что это такое, ещё дольше я искал "типовую" реализацию. Нашёл всё-таки на страничке: Primitive Roots Calculator

Там пришлось вскрыть скрипт и достать оттуда реализацию. Прям скажем по быстродействию вроде не фонтан. Выглядит так:

Используется синтаксис Javascript

function roots(form) {
    var theNum = parseInt(form.inputbox.value);

    if (isNaN(theNum)) {
        alert("Please try again: enter a number.");
        return;
    }
    
    if (aintPrime(theNum)) {
        alert("Sorry, the number must be prime.");
        return;
    }

    form.resultbox.value = "";
    
    var o = 1;
    var k;
    var roots = new Array();
    var z = 0;
    
    for (var r = 2; r < theNum; r++) {
        k = Math.pow(r, o);
        k %= theNum;
        while (k > 1) {
            o++;
            k *= r;
            k %= theNum;
        }
        if (o == (theNum - 1)) {
            //form.resultbox.value += (r + " ");
            //alert(r + " is a primitive root.");
            roots[z] = r;
            z++;
        }
        o = 1;
    }
    
    form.resultbox.value += (theNum + " has " + z + " primitive roots, and they are ");
    z--;
    
    for (var y = 0; y < z; y++) {
        form.resultbox.value += (roots[y] + ", ");
    }
    
    form.resultbox.value += ("and " + roots[z] + ".");
}

function aintPrime(possible) {
    for (var i = 2; i <= Math.sqrt(possible); i++) {
        if (Math.floor(possible / i) == (possible / i)) {
            return true;
        }
    }
    return false;
}

Переписал это дело под Дельфи, вроде работет. Смущает один вопрос. Действительно ли это и есть множество этих самых первообразных корней? Да, кстати, нет ли в Maple функции, чтобы это проверить? А то я собрался отдельно проверять каждое полученное число. Может есть и другие алгоритмы получения первообразных корней?

[nnosipov]

uni в сообщении #490848 писал(а):

Да, кстати, нет ли в Maple функции, чтобы это проверить?

Есть. Во-первых, можно найти какой-нибудь первообразный корень по модулю данного простого числа:

with(numtheory):
g:=primroot(2011);
g:=3

Во-вторых, можно проверить, будет ли какое-то $g$ первообразным корнем по модулю данного простого числа $p$, вычислив порядок $g$ по модулю $p$ (он должен оказаться равным $p-1$):

with(numtheory):
order(3,2011);
2010

[uni]

Ох, спасибо, а я уже другим способом всё проверил :) - сделал шифрование и дешифрование на файлах. Алгоритм работает, значит и мелкие методы пашут.

Но всё равно проверю Maple'ом. Этих корней слишком много для больших простых чисел, потому я ограничился первыми при их вычислении. Тот алгоритм вроде рабочий, на который я ссылался.

Для меня остались загадками некоторые вещи. Уж пусть будет в этой теме. Хоть теперь всё и работает, но я сделал некоторые допущения без какого либо вывода. В книжке написано одно, а вот когда это на ЯВУ пишешь, тут могут быть варианты.

Так вот, пару вопросов, надеюсь я \LaTeX местный вспомню. При шифровании методом Эль-Гамаля, да и не только им применяется один алгоритм для вычисления формулы: $a^x\bmod n$. Он называется: "Возведение в степень путём последовательного возведения в квадрат" и описан, к примеру, в "Алгоритмы. Построение и анализ. 2-е изд, 2005, на стр.985", либо в первом издании на стр. 758 (на русском языке оба).

Так вот, при шифровании сообщения нужно выполнить операцию: $(M\, a^x)\bmod n$. Но алгоритм на ЯВУ в таком виде не вычисляет, поэтому я использую такое выражение: $M (a^x\bmod n$ ) \bmod \, n.

Выглядит это так:

Используется синтаксис Delphi

    // Шаг 1. Выбираем сессионный ключ - случайное целое число k такое, что 1 < k < p - 1
    Randomize;

    k := Random( p - 3 ) + 2;

    Memo1.Lines.Add( 'Шаг 1. Выбираем сессионный ключ - случайное целое число k такое, что 1 < k < p - 1: ' +
        IntToStr(k) );

    // Вычисляем числа a = g^k mod p и b = y^k * M mod p
    a := ModularExponentiation( g, k, p );

    Memo1.Lines.Add( 'Шаг 2. Вычисляем число a = g^k mod p: ' + IntToStr(a) );

    EditAValue.Text := IntToStr(a);

    b := StrToInt( Edit1.Text ) * ModularExponentiation( y, k, p ) mod p;

    Memo1.Lines.Add( 'Шаг 3. Вычисляем число b = M * y^k mod p: ' + IntToStr(b) );

    EditBValue.Text := IntToStr(b);

    // Пара чисел (a, b) является шифротекстом.
    Memo1.Lines.Add( 'Пара чисел (a, b) является шифротекстом: (' +
        IntToStr(a) + ', ' + IntToStr(b) + ')' );
 

Переменная b содержит вторую часть шифротекста. Так вот, насколько это правильно, делать так, как я сделал? Я заранее знаю, что это работает, но вот с модульной арифметикой не очень знаком. Может книжка какая есть? Или это весь курс дискретной математики нужно проходить?

Ещё один вопрос есть, который в Википедии поставил меня в тупик. Там при дешифровке нужно вычислить выражение в виде: $b (a^x)^{-1}\bmod n$. Опять же в книжке я нашёл, что это эквивалентно: $b\, a^{n-1-x} \bmod n$. Это вроде как само собой подразумевается?

[nnosipov]

uni в сообщении #491174 писал(а):

но вот с модульной арифметикой не очень знаком. Может книжка какая есть? Или это весь курс дискретной математики нужно проходить?

Вам достаточно познакомиться с основами теории сравнений, это есть практически в любой книге по элементарной теории чисел (И.М. Виноградов, Основы теории чисел, любое издание). Но лучше взять такую книжку, где бы заодно и про криптографию что-то было. Таких книг тоже очень много. Вот, например, Черёмушкин, Лекции по арифметическим алгоритмам в криптографии.

uni в сообщении #491174 писал(а):

Там при дешифровке нужно вычислить выражение в виде: $b (a^x)^{-1}\bmod n$. Опять же в книжке я нашёл, что это эквивалентно: $b\, a^{n-1-x} \bmod n$. Это вроде как само собой подразумевается?

Да, ведь по малой теореме Ферма имеем $a^{n-1} \bmod{n}=1$, если $n$ простое число и $a$ не делится на $n$.

[uni]

Ага, спасибо, ну я тогда пойду почитаю. Товарищи криптографы много пишут теории, но мало или вообще нет практики. Либо эта практика основана на CryptoAPI, что, конечно, интересно, но не настолько. Наверное по-английски что-то искать придётся тоже, там бывает и теория и практика - всё в одном флаконе.