Шифрование с использованием открытых ключей успешно, только если владелец личного ключа может контролировать его: всегда иметь под рукой, но не раскрывать никому. Существует несколько способов достичь этого:
Еще до возникновения проблемы защиты личных ключей возникает проблема их генерации.
Если используется алгоритм с ключом на основе возведения в степень по модулю (Диффи-Хелмана или DSS), то это просто вопрос выбора подходящего большого случайного числа.
Если же используется алгорит RSA, то необходимо выбрать два больших простых числа. И это само по себе проблема. Математически оперировать с большими простыми числами непросто, и именно поэтому они обеспечивают такую хорошую защиту. Но качество защиты зависит от выбора чисел, которые действительно являются простыми.
Стандартный подход к выбору простых чисел состоит в конструировании случайного числа, которое может быть простым, с последующей математической проверкой. Число отбрасывается, если в результате проверки не оказывается простым. К сожалению, нет практичных математических способов проверки, которые бы позволили точно сказать, что число действительно простое. Чтобы добиться этого, надо провести полное разложение числа на сомножители, а это не должно быть практически реализуемой вычислительной задачей для тех чисел, которые используются в качестве RSA-ключей. Иначе можно было бы самим использовать такие вычисления для взлома RSA-ключей.
Для обнаружения возможных сомножителей числа делается несколько проверок различными способами. Если такие сомножители не обнаружены, то делается вывод о том, что число - простое. Использование нескольких различных проверок снижает вероятность ошибки, ведь если в RSA-ключе есть дополнительные сомножители, то взломщику будет легче взломать его.
Первым шагом в конструировании простого числа является генерация случайного двоичного числа желаемого размера. После этого старший и младший биты устанавливаются в значение единица. Установка старшего бита в единицу гарантирует, что число будет иметь желаемый размер. Установка младшего бита в единицу гарантирует нечетность числа, ведь четное число явно не будет простым.
После построения такого числа осуществляется проверка его простоты. Обычно проверяется его делимость на "малые" простые числа (меньшие 2000).
На следующем шаге проводится вероятностный тест простоты числа. Существует нескоьлко вероятностных тестов, и все они работают путем выбора случайного числа, относительно которого затем осуществляется систематическая проверка простого числа. Наиболее эффективен тест Миллера-Рабина (Miller-Rabin test). Прогоняя алгоритм Миллера-Рабина четыре раза, можно добиться чрезвычайно высокой степени уверенности в том, что число является простым.
По сути такой же подход используется для генерации RSA-ключей в пакете PGP. Сначала PGP конструирует простое число. Для проверки наличия у числа сомножителей PGP использует таблицу первых ста простых чисел (до 541). PGP случайным образом выбирает из таблицы значения и вычисляет остатки, выполняя поиск сомножителей в остатках. Наконец, PGP четыре раза прогоняет алгоритм вероятностной проверки на простоту числа. Эта операция выполняется в пакете PGP два раза, в результате чего оказываются сгенерированными два простых числа, которые и выбираются в качестве составляющих RSA-ключа.
|
-
HEALTH COACH: нутрициолог цена онлайн;Юлия Нуруллаева: клинический нутрициолог услуги |