Криптография и случайность имеют тесную связь. В приложении F, Теория информации , мы упоминали, что совершенная секретность может быть достигнута, если ключ алгоритма шифровки - действительно случайное число. Есть два подхода к получению длинного потока случайных битов.
0
или 1
.Первый подход назван истинным генератором случайных чисел (TRNG - True Random Number Generator).
Второй назван псевдослучайным генератором числа (PRNG - Pseudorandom Number Generator) . Рисунок K.1 показывает эти два подхода.
(рис K.1) Истинный генератор случайных чисел и псевдослучайный генератор чисел При бросании правильной монеты непрерывно возникает совершенный случайный поток битов, но это неприменимо на практике. Есть много естественных источников, которые могут произвести истинные случайные числа, такие как тепловой шум в электрическом резисторе или время ответа механического или электрического процесса после передачи команды. Эти природные ресурсы использовались в прошлом, и некоторые из них были внедрены в коммерческую деятельность. Однако есть несколько недостатков такого подхода. Процесс обычно медленный, и если необходимо, один и тот же случайный поток не может быть повторен.
Случайный поток битов может быть получен с использованием детерминированного процесса при введении короткого случайного потока (начального числа).
Несколько методов используют некоторые конгруэнтные отношения.
В информатике самая общая методика для того, чтобы производить псевдослучайные числа, - линейный конгруэнтный метод, введенный Лехмером (Lehmer).
Рисунок K.2 показывает этот метод, который рекурсивно создает последовательность псевдослучайных чисел, используя линейное конгруэнтное уравнение xi+1 = (axi + b) mod n, где x0 называется начальным числом (seed) - это число между 0 и n - 1.
(рис K.2) Линейный конгруэнтный генератор псевдослучайных чиселПоследовательность является периодической, где период зависит от того, как тщательно выбраны коэффициенты a и b. Идеально период должен быть такого размера, как модуль n.
Пример K.1
Предположим a = 4, b = 5, n = 17 и xi0 = 7. Последовательность - 16, 1, 9, 7, 16, 1, 9, 7..., которая есть явно неудовлетворительная псевдослучайная последовательность; её период - только 4
.
Критерии. Для приемлемого
n
(модулю). Это означает, что прежде чем целые числа в последовательности начинают повторяться, должны быть сгенерированы все целые числа между 0
и n - 1
.Рекомендации , основанные на предыдущих критериях: рекомендуется выбрать коэффициенты конгруэнтного уравнения и значения модуля исходя из следующих соображений.
n
, - это наибольшее простое число, близкое к размеру слова, используемого в компьютере. Рекомендуется использовать тридцать первое простое n = M
31
= 2
31
- 1
.a, должно быть 7 - M31, рекомендуют использовать 7k, где k - целое число, взаимно-простое с ( M31 - 1 ). Некоторые рекомендованные значения для k - это 5 и 13. Это означает, что
( a = 75 ) или ( a = 713 ).b
должно быть нулевым.Линейный конгруэнтный генератор:
xi+1 = axi mod n, где n = 231 - 1 и a = 75 или a = 713
Безопасность.
Последовательность, сгенерированная линейным конгруэнтным уравнением, показывает приемлемую случайность (если следовать предыдущим рекомендациям). Последовательность полезна в некоторых приложениях, где требуется только случайность (таких как моделирование); она бесполезна в криптографии, где желательны и случайность, и безопасность. Поскольку число n общедоступно, последовательность может быть атакована Евой с использованием одной из двух стратегий:
x
0
)
и коэффициент a
, она может легко восстановить целую последовательность;x
0
и a
, она может перехватить первые два целых числа и использовать следующие два уравнения, чтобы найти x0 и a
:x1 = ax0 mod n x2 = ax1 mod n
Чтобы получить менее предсказуемую псевдослучайную последовательность, был введен генератор квадратичных вычетов (см.
лекцию 9), xi+1 = xi2 mod n,
где x0 называют начальным числом, - число между 0 и n -1.
Простой, но эффективный метод создания
BBS использует уравнение квадратичного вычета, но это - псевдослучайный генератор бит вместо 0 или 1 ).
Рисунок K.3 показывает идею этого генератора.
Ниже приведены шаги генерации:
p и q в форме 4k + 3, где k - целое число ( p и q являются конгруэнтными 3 mod 4 ) .n = p x q
.r, которое является взаимно-простым с n.xi+1 = xi2 mod n.
(рис K.3) Blum Blum Shub (BBS) генератор псевдослучайных чиселБезопасность. Может быть доказано, что если p
и q
известны, i
-тый бит в последовательности может быть найден как самый младший бит:
xi = x02^imod[(p-1)(q-1)]
Это означает, что если Ева знает значение p и q, она может найти значение i -того бита, пробуя все возможные значения n (значение n обычно общедоступно). Тем самым сложность у этого генератора - та же самая, как у разложения на множители n. Если n является достаточно большим, последовательность безопасна (непредсказуема). Было доказано, что при очень большом n Ева не может предсказать значение следующего бита в последовательности, даже если она знает значения всех предыдущих битов. Вероятность каждого принятия значений для каждого бита, 0 или 1, - очень близка к 50 процентам.
nКриптографические системы, такие как шифр для процесса шифрования или хэш-функция, могут также быть использованы для генерации случайного потока битов. Мы кратко покажем две системы, которые применяют алгоритмы шифрования.
ANSI X9.17 определяет криптографически сильный K1 и K2 в 3DES ) применяется для всех трех 3DES-шифров.
(рис K.4) ANSI X9.17 генератор псевдослучайных чисел На рис. K.4 конфигурация - режим сцепления блоков шифрованного текста ( CBC ), который мы описали согласно рис. 8.3 в лекции 8 . Режим X9.17 применяет два каскада формирования цепочки блока. Исходный текст для каждого каскада поступает от выхода первого 3DES, который использует дату и время как исходный текст на 64 бита. Зашифрованный текст, созданный вторым 3DES, - случайное число; зашифрованный текст, созданный третьим 3DES, - следующий инициирующий вектор IV для следующего случайного числа.
Строгость X9.17 определяется следующими фактами.
PGP генератор псевдослучайных чисел (PRNG)
PGP (очень хорошая конфиденциальность) берет ту же самую идею, что и X9.17 с несколькими изменениями. Сначала PGP
(рис K.5) PGP-генератор псевдослучайных чисел
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.