2018-03-09
328
Один из методов генерации последовательности элементов гаммы, длина которых превышает размер шифруемых данных – это датчики псевдослучайных чисел (ПСЧ). На основе теории групп разработано несколько типов таких датчиков.
Наиболее доступными и эффективными являются конгруэнтные генераторы ПСЧ. Для этого класса генераторов можно сделать математически строгое заключение о том, какими свойствами обладают выходные сигналы этих генераторов с точки зрения периодичности и случайности.
Одним из хороших конгруэнтных генераторов является линейный конгруэнтный датчик ПСЧ. Он вырабатывает последовательности псевдослучайных чисел γ i, описываемые соотношением
γ i+1 = (а γ i + b)mod m, i =1,2, …,M.
где а и b – константы, γ0 – исходная величина, выбранная в качестве порождающего числа. Эти три величины и образуют ключ. Значение m обычно устанавливается равным 2 n-1, где n – длина машинного слова в битах (m – максимально возможное число различных чисел, записанных с помощью n бит).
Из приведенной формулы следует, что как только мы получим в качестве очередного элемента γ М= γ0, элементы последовательности начнут повторяться. Значение М называют периодом датчика ПСЧ. Этот период зависит от значений а и b, которые желательно выбрать так, чтобы период был максимальным (М= 2 n-1). Как показано Кнутом [11], линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда b – нечетное и взаимно простое с m и величина, а mod 4 = 1. По другим рекомендациям b – взаимно простое с m и а нечетное.
|
|
|
Также популярны так называемые М-последовательности благодаря относительной легкости их реализации. М-последовательности представляют собой линейные рекуррентные последовательности максимального периода, формируемые k -pазpядными генераторами на основе регистров сдвига. На каждом такте поступивший бит сдвигает k предыдущих и к нему добавляется сумма этих бит по модулю 2. Вытесняемый бит добавляется к гамме. Более подробно этот метод будет рассмотрен далее.
Также перспективными представляются нелинейные датчики ПСЧ (например, сдвиговые регистры с элементом «И» в цепи обратной связи), однако их свойства еще недостаточно изучены. Возможны и другие, более сложные варианты выбора порождающих чисел для гаммы шифра.
Модели шифров по Шеннону
