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

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

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

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

Схема Меркля

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

Сложность

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

· Абоненту А необходимо сделать следующие вычисления: зашифровать 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)

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

Особенности

· Если произошла рассинхронизация, то через n тактов S заполнятся снова одинаково, т.е. происходит автоматическая синхронизация. Следовательно нет необходимости устанавливать начальное состояние. Перед текстом передается последовательность одинаковых символов для синхронизации.

· Единичная ошибка искажает до n знаков.

· Система уязвима к имитации сообщений, следовательно необходимо вводить временные ограничения по передаче.

· Период гаммы не важен. Стойкость – на основе отображения.

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

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

Для последовательности длины N максимальная линейная сложность N-1

Требования:

· Периоды почти всех вырабатываемых последовательностей должны быть большими.

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

· Выходные последовательности генератора должны обладать теми же свойствами, что и случайные последовательности.

· Зависимость между знаками выходной последовательности должна быть настолько сложной, чтобы ее восстановление по достаточно длинному отрезку являлось вычислительно сложной задачей.