RSA и алгоритмы простого генератора

Ответ 1

1. О вероятностных тестах прочности

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

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

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

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

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

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

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

2. Плохая клавиша

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

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

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

Ответ 2

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

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

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

Ответ 3

ive узнал, что вы можете использовать rsa как это:

p = prime
q = prime
n = p * q

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

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

Ответ 4

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

Ответ 5

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

Также RSA находится в курсе.