0 0 1 1

V = 1 0 0 0

0 1 0 0

0 0 1 0 .

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

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

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

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

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

p(ak=1)=2m-1 /(2m-1)=1/2 + 1/(2m+1-2),

p(ak=0)=(2m-1-1)/(2m-1) = 1/2-(2m+1 -2)

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

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

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

Использование линейных сдвиговых регистров для создания криптосистем предполагает их уязвимость, если взломщик обладает парой: исходный текст - шифротекст длиной не менее 2m бит. Действительно, имея исходный текст M=(m1,m2, .,m2m) и соответствующий шифротекст C=(c1,c2, .,c2m), мы можем получить К=MÅC=(m1Åc1,m2Åc2, .,m2mÅc2m)=(k1,k2,k3, .,k2m). Тогда задача взлома криптосистемы при известном начальном состоянии сводится к решению системы из m линейных уравнений с m неизвестными, где неизвестными являются коэффициенты порождающего полинома.

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

1k1 Å 2k2Å 3k3 Å . Å mkm =km+1

1k2Å 2k3Å 3k4 Å . Å mkm+1 =km+2

1k3 Å 2k4Å 3k5 Å . Å mkm+2 =km+3

1kmÅ 2km+1Å 3km+2 Å . Å mkm+m-1 =k2m .

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

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

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

Под простым числом будем понимать такое число, которое делится только на 1 и на само себя.

Взаимно простыми числами будем называть такие числа, которые не имеют ни одного общего делителя, кроме 1.

Под результатом операции i mod j будем понимать остаток от целочисленного деления i на j.

Наиболее важной частью алгоритма RSA, как и других алгоритмов с открытым ключем, является процесс создания пары открытый/секретный ключи. В RSA он состоит из следующих шагов.

1. Случайным образом выбираются два секретных простых числа, p и q, p¹q.

2. Вычисляется r=p*q.

3. Вычисляется f=(p-1)*(q-1).

4. Выбираются открытый (Ко) и секретный (Кс) ключи, которые являются взаимно простыми с f и удовлетворяют условию (Ко*Кс) mod f = 1.

Чтобы зашифровать данные открытым ключем Ко, необходимо:

1) разбить исходный текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0, 1, ., n-1;

2) зашифровать последовательность чисел M(i) по формуле

C(i)=(M(i)Ко) mod n,

где последовательность чисел C(i) представляет шифротекст.

Чтобы расшифровать эти данные секретным ключем Кс, необходимо выполнить следующие вычисления:

M(i)=(C(i)Кс) mod n.

В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Приведем простой пример использования метода RSA для шифрования сообщения “CAB”. Для простоты будем использовать малые числа (на практике используются намного большие числа).

1. Выберем p=3, q=11.

2. Вычислим r=3*11=33.

3. Вычислим f=(p-1)*(q-1)=20.

4. Выберем секретный ключ Кс, который является взаимно простым с f, например Кс=3.

5. На основе Кс и f вычислим открытый ключ Ко. Для этого можно использовать расширение алгоритма Евклида:

BEGIN

g0=f; g1=Kc;

u0=1; u1=0;

v0=0; v1=1;

i=1;

while gi¹0 do

begin

gi=uif+viKc;

y=gi-1 div gi;

gi+1=gi-1-ygi;

ui+1=ui-1-yui;

vi+1=vi-1-yvi;

i=i+1;

end;

Kо=vi-1;

if Kо<0 then Kо=Kо+f;

END.

В соответствии с алгоритмом получаем Ко=7.

6. Представим шифруемое сообщение как последовательность целых чисел в диапазоне 2 .28. Пусть букве А соответствует число 2, букве В - число 3, а букве С - число 4. Тогда сообщение “CAB” можно представить в виде последовательности чисел {5, 3, 4}. Зашифруем сообщение, используя открытый ключ Ко=7: