Криптосистема Месси-Омуры

А	В
-секретные

Видимо, объяснение, почему эта схема работает:

Далее в лекциях следующее (видимо это объяснение, что сложность вскрытия не больше сложности логарифмирования):

Схема Меркля

Шарады Меркля:

Абонент А	Абонент Б
1. Формируем n блоков вида: Mi=(Ki,0^32), где i=1,…,n, Ki – разные ключи.
2. Шифруем блоки Mi на разных ключах K’j с H(K’j)=20 (например ключи, у которых только первые 20 битов значащие, остальные нули) EK’j(Mi), где j=1,…,n.
3. Передаём все зашифрованные блоки {EK’j(Mi)} другой стороне. 	4.  Получает {EK’j(Mi)}
	5. Выбирает любой j, и взламывает шифр, т.е. находит Mi=(Ki,0^32), для этого придётся перебрать все ключи с H(K)=20 (Т.е. порядка миллиона ключей)
7. С=EKi(M) Получает зашифрованный на одном из Ki текст	6. С=EKi(M) Зашифровывает текст на выбранном ключе и передаёт.
8. Перебирает все n ключей и находит, таким образом, о.т.

Сложность

Если элементарной операцией считать операцию зашифрования, то:

• Абоненту А необходимо сделать следующие вычисления: зашифровать n блоков (Шаг 2), перебрать n ключей в шаге 8. Т.е. порядка O(n)

• Абоненту Б необходимо сделать следующие вычисления: перебрать 2^H(K’) ключей в шаге 5. Т.е. порядка O(2^H(K’))

• Т.к. злоумышленник не знает какой j выбрал Б, то ему придётся взломать все блоки. Т.е. порядка O(n*2^H(K’))

Т.е. если n=10⁶, H(K’)=20, т.е. количество ключей =2²⁰10⁶, то аб.А и Б сделают порядка O(10⁶) операций, а злоумышленник порядка O(10¹²)

Вопрос 20.1. Шифрсистемы поточного шифрования (синхронные и асинхронные). Требования к гамме, вырабатываемой генератором синхронной поточной системы (периоды, линейная сложность, статистические свойства)

Поточные шифры

• Синхронные (СПШ)

• Самосинхронизирующиеся (СсПШ)

СПШ

математически процесс шифрования/расшифрования можно описать следующим образом:

(O_i + γ_i ) mod m = C_i

(C_i + γ_i ) mod m = O_i

или при помощи автоматов:

(X,Y,Z,S,h,f) где X – открытый текст, Y- шифр текст, Z – ключ, S – внутреннее состояние, h – функция перехода, f – функция выхода.

S_i+1=h(K_i,S_i) S₀-начальное состояние генератора

γ_i=f(K_i,S_i)

Особенности

• Начальное заполнение 1. Необходимо выставлять начальное значение шифратора 2. Вставка в сообщение специальных служебных символов (маркеров) - т.е. либо п.1 либо п.2 либо оба вместе - ???

• Неразмножение единичной ошибки, имитостойкость. Защищает от вставки и удаления символов, но не защищает от замены (равной по длине)

• Характеристики выходной последовательности ЗАВИСЯТ ОТ ГАММЫ. Выходной последовательность должна быть статистически близка к случайной равновероятной.

• Запрет на использование последовательностей с одинаковыми отрезками (длинными).

СЛЕДОВАТЕЛЬНО, период выходной последовательности должен быть заведомо больше длины любого передаваемого сообщения.

ССПШ

C_i = O_i + γ_i

S_i =F(C_i-1, C_i-2,…,C_i-n)

Знаки шифр текста заводятся на состояние генератора