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, а не о гораздо более вероятном событии аппаратного сбоя (что неизбежно из-за космических лучей, но, к счастью, нет)в любом случае очень часто), тогда вы ошибаетесь в своих приоритетах.