Алгоритмы RSA и первичного генератора

<сильный>1. О вероятностных тестах на простоту

Компьютер — это надежная детерминированная система: для одних и тех же входных данных он будет запускать один и тот же алгоритм для одних и тех же выходных данных. Всегда ли так будет? Почти. По Вселенной бродят частицы высокой энергии, обычно называемые космическими лучами. Когда такая частица попадает в транзистор, спрятанный глубоко внутри ЦП, это может вызвать его икоту — в основном изменить его выходное напряжение очень кратковременным образом, так что в течение одного тактового цикла бит, который представляет выход транзистора, переворачивается.

Теперь рассмотрим некоторый компьютер, на котором работает алгоритм генератора простых чисел, который создает случайные числа и проверяет их на простоту. Проверка простоты — это функция, которая возвращает логическое значение. В какой-то момент результат (логическое значение, которое равно true для «простого», false для непростого) представляет собой постоянное значение, скопированное в регистр. Таким образом, есть окно в несколько тактов, в течение которых результатом является один бит, содержащийся в триггерной структуре (состоящей из 6 транзисторов).

Какова тогда вероятность того, что космический луч перевернет этот критический бит как раз в «правильный» такт, заставив программу считать, что не простое число на самом деле простое? Такая вероятность очень мала. Как я уже сказал, компьютеры — это надежные системы. Тем не менее, эту вероятность можно приблизительно оценить. Обычно считается, что данный ЦП подвергается перевороту битов космических лучей раз в три месяца. Процессор Core2 Duo содержит около 291 миллиона транзисторов и работает, например, на частоте 2,4 ГГц. Если есть один «критический» транзистор, и этот транзистор является критическим в течение одного тактового цикла, то вероятность того, что космический луч превратит не простое число в кажущееся простым, составляет около 1,8 * 10^-24. . Это очень оптимистичная нижняя граница; на практике многие переходники могут быть перевернуты, что подразумевает отказ теста на простоту, а целевое время охватывает несколько циклов, и генератор простых чисел будет проверять несколько десятков не простых чисел для каждого простого поколения. Но будем считать, что нам повезло.

Вероятность 1,8*10^-24 влияет на каждый тест на простоту, независимо от того, является ли он детерминированным или нет.

Обычный генератор простых чисел проведет тест Миллера-Рабина с «определенностью» 2^-100 (тест выполняется 50 раз и имеет вероятность не более 0,25 пропустить не простое число). каждый раз). Число «100» произвольное, но распространенное. Эта вероятность чуть меньше 10^-30. Итак, вот оно: вероятность того, что тест Миллера-Рабина объявит простое число непростым, меньше, чем миллионная часть вероятности того, что космический луч попадет в транзистор и заставит приложение предположить, что число является простым, тогда как тест Миллера-Рабина показал, что это не так.

Короче говоря, если вы получаете не простое число из генератора простых чисел, то это связано с аппаратной проблемой, такой как космические лучи, а не с вероятностным характером теста на простоту.

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

<сильный>2. Неверный ключ

Если вы используете не простое число в ключе RSA, вы получите неверный ключ. Плохой ключ будет генерировать плохие подписи: генератор подписи создаст поток байтов нужной длины, но верификатор подписи объявит подпись недействительной. Примечание: на самом деле подпись может быть действительной, с небольшой вероятностью. Использование «простых чисел» p и q в RSA сродни вероятностному тесту простоты, подобно тесту Миллера-Рабина. Однако есть вероятность, что вскоре обнаружится, что ключ плохо себя ведет. Аналогичное поведение будет наблюдаться и для асимметричного шифрования.

Следует отметить, что создание плохой подписи или невозможность расшифровать сообщение, зашифрованное с помощью RSA, также может произойти из-за еще одного космического луча или даже из-за гораздо более приземленного возникновения плохой ОЗУ.

Суть в том, что если вы беспокоитесь о плохом ключе RSA, но не о гораздо более вероятном сбое оборудования (который неизбежен из-за космических лучей, но, к счастью, не очень распространен), то вы неправильно расставляете приоритеты.

Вы сразу это заметите: секретный ключ будет неправильным.

Если p или q составные, вы выбираете открытый ключ (обычно 65537) и вычисляете свой секретный ключ, используя расширенный алгоритм Евклида: 65537*x mod n = 1. (где n=(p-1)*(q-1))

Но используя секретный ключ x decrypt(encrypt(m)) != m В формуле: (m^65537)^x mod n != m

я узнал, что вы можете использовать rsa следующим образом:

p = prime
q = prime
n = p * q

phi(n) = phi(p) * phi(q) = p-1 * q-1

Но я слышал, что если вы сделаете phi ни одного простого числа, это не простое число -1, поэтому оно вылетит на шаге выше (но я не могу сказать, почему)

Если у вас есть настоящие простые числа, то нет коротких путей, кроме грубой силы. Если вы не уверены на 100%, злоумышленник тоже не будет. Кроме того, вы можете быть достаточно уверены в алгоритмах проверки простых чисел, что риск наличия непростого числа меньше 1 для всего пространства ключей. По сути, вы можете статистически быть уверены, что ваше число является простым. Другими словами, шансы угадать, что это не простое число, должны быть выше, чем угадать правильный ключ. Это просто требует некоторого терпения во время генерации ключа.

Существует простой алгоритм факторизации большого композита (как всегда подозревали). Это известно США и их союзникам с 1989 года. Оно также легко идентифицирует простые числа.

Также RSA в курсе.