Основные требования к средствам формирования случайных и псевдослучайных последовательностей. Интересные особенности и недостатки RSA-алгоритма генерации. Задачи, требующие решения при построении компьютерных систем (КС) в защищенном исполнении.
Аннотация к работе
Известно, что при реализации криптографических преобразований, используют псевдослучайные последовательности. Отсюда следует, что стойкость криптопреобразования напрямую зависит от алгоритма формирования случайных чисел и последовательностей, точнее от их степени случайности. Современные компиляторы обладают собственной реализацией генератора псевдослучайных последовательностей, однако с криптографической точки зрения они являются непригодными. Последовательность называется криптографически надежной псевдослучайной последовательностью (КНПСП), если она непредсказуема, т.е. вычислительно неосуществимо предсказать следующий бит, имея полное знание алгоритма (или аппаратуры) и всех предшествующих битов потока. Мы знаем, что на микроуровне случайность существует (квантовая механика), но сохранит ли эта случайность при переходе на макроуровень.В качестве средств формирования случайных и псевдослучайных последовательностей используют устройства или алгоритмы, называют генераторами случайных и псевдослучайных последовательностей. Генератором случайных последовательностей (ГВС) называют устройство или алгоритм, который формирует на своем выходе последовательность статистически независимых символов с основанием алфавита m [1]. Генератором псевдослучайных последовательностей (ГПВП) называют детерминированные алгоритмом, совокупность алгоритмов или совокупность алгоритмов и средств, для заданной последовательности длиной k формируют при своей работе последовательность символов длиной l >> k, которая обладает большинством свойств случайной последовательности. На приведены упрощенную схему генератора псевдослучайных последовательностей, где: 1 - генератор случайной последовательности длиной k; В общем виде псевдослучайную последовательность (ПСП) Y можно задать как зависимость: (1.1) от начальных значений ключа К и параметров П, а также случайных последовательностей.Предлагается классификация генераторов псевдослучайных последовательностей (ПСП), ориентированных на использование в задачах защиты информации. Можно выделить следующие задачи, требующие решения при построении компьютерных систем (КС) в защищенном исполнении: обеспечение работоспособности компонентов КС и системы в целом при наличии случайных и умышленных деструктивных воздействий; обеспечение аутентичности информации (целостности, подлинности и пр. обеспечение юридической значимости пересылаемых электронных документов;Этот алгоритм основывается на том факте, что в настоящее время в криптоанализ RSA не может быть осуществлен с полиномиальной сложностью. RSA-алгоритм генерации двоичной псевдослучайной последовательности состоит из шести шагов. 1) Сгенерировать достаточно большие простые различные числа p,q и вычислить числа , .Алгоритм Блюма - Блюма - Шуба-это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986). Два простых числа, p и q, Должны быть оба Сравнимые с 3 по модулю 4 (это гарантирует, что каждый квадратичные вычет имеет один квадратный корень, который также является квадратичным вычет) и наибольший общий делитель НОД должен быть мал (это увеличивает длину цикла). Интересной особенностью этого алгоритма является то, что для получения xn необязательно вычислить все n - 1 предыдущих чисел, если известно начальное состояние генератора x0 и числа p и q. n-ное значение может быть. псевдослучайный последовательность алгоритмФи-зычный генератор случайных чисел (ФГВЧ)-устройство , который генерирует случайные числа на основе физического процесса (тепловой шум, фотоэлектрический эффект или квантовые явления), который является абсолютно непредсказуемым. В некоторых источниках ФГВЧ называют недетерминированные генератором случайных чисел (НГВЧ) или генератором случайных чисел (ГСЧ). Анализ показал, что в современных криптографических системах скорость генерации случайных последовательностей должна превышать 1Мбит / с. Случайные изменения параметров (тепловой шум) наблюдаются во всех электронных компонентах при температурах выше абсолютного нуля по Кельвином. Например, датчики шума на основе кремний диодов Зенеровського пробой (стабилитроны) генерируют случайный сигнал с равномерным спектром от единиц Гц до десятков МГЦ и амплитудами в десятки МВ.Генератор случайных чисел "Гряда-1" является аппаратным средством формирования, который встраивается, случайных чисел на основе использования физически случайных процессов. Аппаратный датчик случайных последовательностей "Гряда-1" предназначен для работы в составе персонального компьютера, имеющего слот расширения ISA 16. Датчик не использует линии запроса на прерывание (IRQ), каналы прямого доступа к памяти (DMA) и имеет фиксированные адреса портов ввода / вывода (034Ah и 0348h), поэтому перед установкой не нужно дополнительное настройки датчика. Вместе с аппаратным датчиком случайных чисел "Гряда-1" поставляется программное обеспечение для работы в операционных системах Windows 95 и Windows 98. Задайте следующие
Известно, что при реализации криптографических преобразований, используют псевдослучайные последовательности. Отсюда следует, что стойкость криптопреобразования напрямую зависит от алгоритма формирования случайных чисел и последовательностей, точнее от их степени случайности.
Современные компиляторы обладают собственной реализацией генератора псевдослучайных последовательностей, однако с криптографической точки зрения они являются непригодными.
Основная сложность генерации последовательности псевдослучайных чисел на компьютере в том, что компьютеры детерминистичны по своей сути. Компьютер может находиться только в конечном количестве состояний (количество состояний огромно, но все-таки конечно). Следовательно любой датчик случайных чисел по определению периодичен. Все периодическое - предсказуемо, т.е. не случайно.
Лучшее, что может произвести компьютер - это псевдослучайная последовательность. Период такой последовательности должен быть таким, чтобы конечная последовательность разумной длины не была периодической. Относительно короткие непериодические подпоследовательности должны быть как можно более неотличимы от случайных последовательностей, в частности, соответствовать различным критериям случайности.
Генератор последовательности псевдослучаен, если он выглядит случайным, т.е проходит все статистические тесты случайности Для криптографических приложений статистической случайности недостаточно, хотя это и необходимое свойство.
Последовательность называется криптографически надежной псевдослучайной последовательностью (КНПСП), если она непредсказуема, т.е. вычислительно неосуществимо предсказать следующий бит, имея полное знание алгоритма (или аппаратуры) и всех предшествующих битов потока. КНПСП тоже подвержены криптоанализу - как любой алгоритм шифрования. Сформулируем наиболее сильное определение.
Генератор последовательности называется случайным, если он не может быть достоверно воспроизведен, т.е. дважды запуская генератор с абсолютно одинаковыми исходными данными (по крайней мере, на пределе человеческих возможностей), мы получим случайные различные последовательности.
Вопрос существования случайных последовательностей - философский вопрос. Мы знаем, что на микроуровне случайность существует (квантовая механика), но сохранит ли эта случайность при переходе на макроуровень. Дополнительное свойство случайной последовательности: случайная последовательность не может быть сжата. КНПСП не может быть сжата (на практике).
При создании и эксплуатации систем криптографической защиты потока данных приходится сталкиваться с проблемой создания, хранения и распределения ключей или исходной ключевой информации, на основе которой в дальнейшем создаются непосредственно сами ключи. Повышенное внимание к решениям подобных проблем вызвано тем, что злоумышленнику бывает гораздо проще провести атаку на ключевую систему, нежели на криптографические алгоритмы. По своему назначению ключи бывают нескольких типов (в соответствии со стандартом ANSI X9.17): для зашифрования ключей для зашифрования данных
Кроме того, при использовании криптографических средств защиты межмашинного взаимодействия приходится создавать так называемые сеансовые ключи, которые применяются только в рамках одного сеанса связи. В зависимости от того, к какой категории принадлежит ключ, будут меняться и пути решения вышеперечисленных проблем.