Потоковые шифры. (Лекция 6)

Действия противника:

E1 + E2 = M1+γ+M2+γ= M1+M2;
Т.о. Противник свел потоковый шифр

Подход к вскрытию книжного шифра

M1=влесуродиласьелочкавлесуона
M2=россиясвященнаянашадержавар
Е =xxxxxxxxxxxxxxxxxxxxxxxxxxx
Для вскрытия может использоваться частотный словарь

Перебор слов

Е =xxxxxxxxxxxxxxxxxxxxxxxxxxx
1 елочка
елочка
...
елочка
аянаша
2 родилась
ясвященн
3 держава

Потоковые шифры

Посимвольное шифрование.
Каждый символ сообщения (независимо от других) преобразуется в символ

Потоковое шифрование

Генератор Г(K)

Г – шифрующая последовательность

Гi

Mi

Ei

Генератор Г(K)

Гi

Ei

Mi

К – по секретному каналу

E

Потоковые шифры

Большинство потоковых шифров – аддитивные (шифрование по модулю 2)
Отличаются друг

LSFR

Для формирования последовательности часто используют:
ЛРР линейные рекуррентные регистры или иначе LSFR

LSFR

a5

a4

a3

a2

a1

С любым ЛРР(LFSR) можно сопоставить полином обратных связей (для математического изучения

Свойства LSFR:

Период выходной последовательности T<=2n-
Максимальный период (2n-1) достигается если ЛРР основан

Выходная последовательность ЛРР, основанного на примитивном полиноме обладает свойствами:
баланса – равенство

Свойство окна

110
101
111
001
011
010
001
110101111001011010001110101111001011010001

1

1

0

Обратная связь

Недостаток генератора Г на основе ЛРР

Непосредственно использовать ЛРР для шифрования нельзя,

Полиномиальная сложность восстановления регистра по выходной последовательности обусловлена его линейностью.
Для устранения

НУУ (нелинейные узлы усложнения)

Схема И Генератор Джеффа(Гефа)

Ввод нелинейности (комбинация методов)

ЛРР1

ЛРР2

Управление тактовыми импульсами. Один LSFR (ЛРР) управляет тактированием другого …

ЛРР3

1

1

0

Обратная

Эквивалентный регистр

Любой совокупности ЛРР и НУУ можно сопоставить один эквивалентный ЛРР

Свойства потоковых шифров*

Простота схем и низкая стоимость
Высокая скорость
Нет размножения ошибок
Нет задержек
Проще

Примеры потоковых шифров

A5 (шифрование в GSM)

ЛРР(22)

ЛРР (19)

ЛРР(23)

Схема упр. тактированием

8

10

10

Особенности A5 (недостатки)

Первоначально секретный алгоритм
A5/1 ~ 240 *
A5/2 менее стойкий ~218 *
* - при атаке

RC4

Ривест (Райвест):

Q1

Q2

S(Q1)

S(Q2)

S(T)

T

γ

Q1 Q2 – счетчики – для постоянного изменения таблицы замен.
S(

RC4

Q1=(Q1+1)mod 28
Q2=(Q2+S[Q1])mod 28
S[Q1] <--> S[Q2] - обмен значениями
Т= (S[Q1]+S[Q2])mod 28
γ =