Реферат: Криптографические системы

где k - номер такта; ak{0,1} - биты формируемой последовательности; ai {0,1} - постоянные коэффициенты; ^Å - операция суммирования по модулю 2. Генератор, описываемый отношением (2.1), показан на рис. 2.1.

Свойства генерируемой последовательности определяются постоянными коэффициентами ai. Их можно исследовать, анализируя характеристический полином

g(x) = 1 Å a1 x Å a2 x2Å...Å am-1 xm-1Å am xm.

При соответствующем выборе коэффициентов генерируемая последовательность { ai } будет иметь максимально возможный период, равный 2m-1, где m - разрядность сдвигового регистра и одновременно старшая степень порождающего полинома. Последовательность максимально возможного периода называется M-последовательностью. Основная задача синтеза генератора рассматриваемого типа - нахождение характеристического полинома, формирующего М-последовательность.

Полиномы, формирующие последовательность максимального периода, называются примитивными. С ростом m их количество становится очень большим. Среди множества примитивных полиномов степени m можно найти полиномы с наименьшим числом единичных коэффициентов a_i . Генераторы, построенные на их основе, имеют наиболее простую техническую реализацию. В табл. 2.1 приведен перечень полиномов с минимальным количеством ненулевых коэффициентов для значений m <=16.

Схема четырехразрядного ГК, описываемого примитивным полиномом g(x)=1Å x³ Å x⁴ , приведена на рис. 2.2; его работа показана в табл. 2.2.

Для формирования M-последовательности наряду с примитивным полиномом g(x) может использоваться и обратный ему полином g^-1 (x)=x^m g(x^-1 ). Полученная в этом случае последовательность максимальной длины будет инверсной по отношению к последовательности, формируемой g(x). Например, для полинома g(x)=1Åx³ Åx⁴ обратным полиномом будет g^-1 (x) = x⁴ (1Åx^-3 Åx^-4 )=1 Å x Å x⁴ .

Главное преимущество описываемого метода формирования псевдослучайных последовательностей - простота его реализации. Генератор M-последовательности содержит лишь m-разрядный регистр сдвига и набор сумматоров по модулю два в цепи обратной связи. Регистр сдвига выполняет функции хранения m бит M-последовательности и сдвига m-разрядного кода на один разряд вправо. Сумматоры по модулю два вычисляют очередное значение младшего разряда сдвигового регистра.

Состояние разрядов регистра на каждом такте можно представить в виде m-мерных векторов A(k)=a₁ (k)a₂ (k)a₃ (k)...a_m (k), где k=0,1,2,... - номер такта, a_i (k) - состояние i-го разряда, i=1,m,

Последовательное применение соотношений (1) или (2) для s = 0 позволяет формировать соответственно одно- или многоразрядные псевдослучайные последовательности, которые характеризуется рядом статических свойств.

Рассмотрим наиболее важные свойства М-последовательностей.

1. Период последовательности, описываемой выражением (1), определяется старшей степенью порождающего полинома g(x) и равен L= 2^m -1.

2. Для заданного полинома g(x) существует L различных M-последовательностей, отличающихся фазовым сдвигом. Так, полиному g(x)=1Åx³ Åx⁴ соответствует 15 M-последовательностей.

3. Количество единичных и нулевых символов a_k , k=0,1,..., L-1, M-последовательности соответственно равно 2^m-1 и 2^m-1 -1. Вероятностная оценка частоты их появления определяется следующими выражениями:

p(a_k =1)=2^m-1 /(2^m -1)=1/2 + 1/(2^m+1 -2),

p(a_k =0)=(2^m-1 -1)/(2^m -1) = 1/2-(2^m+1 -2)

и при увеличении m достигает значений, сколь угодно близких к 1/2.

4. Вероятности появления серий из r, r {1,2,...,m-1}, одинаковых символов ( нулей или единиц ) в M-последовательности максимально близки к соответствующим вероятностям для случайной последовательности.

5. Для любого значения s ( 1s<L ) существует такое r s ( 1r<L), что {a_k } + {a_k -s}={a_k -r}. Данное свойство обычно называют свойством сдвига и сложения.

Использование линейных сдвиговых регистров для создания криптосистем предполагает их уязвимость, если взломщик обладает парой: исходный текст - шифротекст длиной не менее 2m бит. Действительно, имея исходный текст M=(m₁ ,m₂ ,...,m_2m ) и соответствующий шифротекст C=(c₁ ,c₂ ,...,c_2m ), мы можем получить К=MÅC=(m₁ Åc₁ ,m₂ Åc₂ ,...,m_2m Åc_2m )=(k₁ ,k₂ ,k₃ ,...,k_2m ). Тогда задача взлома криптосистемы при известном начальном состоянии сводится к решению системы из m линейных уравнений с m неизвестными, где неизвестными являются коэффициенты порождающего полинома.

Данная система имеет вид

₁ k₁ Å₂ k₂ Å₃ k₃ Å ... Å_m k_m =k_m+1

₁ k₂ Å₂ k₃ Å₃ k₄ Å ... Å_m k_m+1 =k_m+2

₁ k₃ Å₂ k₄ Å₃ k₅ Å ... Å_m k_m+2 =k_m+3

.... ....

₁ k_m Å₂ k_m+1 Å₃ k_m+2 Å ... Å_m k_m+m-1 =k_2m .

3. КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ

Первые криптографические системы с открытым ключем появились в конце 1970-х годов. От классических алгоритмов они отличаются тем, что для шифрования данных используется один ключ (открытый ), а для дешифрования - другой (секретный ). Данные, зашифрованные открытым ключем, можно расшифровать только секретным ключем. Следовательно, открытый ключ может распространяться через обычные коммуникационные сети и другие открытые каналы. Таким образом, устраняется главный недостаток стандартных криптографических алгоритмов: необходимость использовать специальные каналы связи для распределения ключей. Разумеется, секретный ключ не может быть вычислен из открытого ключа.

В настоящее время лучшим криптографическим алгоритмом с открытым ключем считается RSA (по имени создателей: Rivest, Shamir, Adelman). Перед изложением метода RSA определим некоторые термины.