Презентация - "Лекция 2. Современные системы симметричной криптографии"

Лекция 2.
Современные системы симметричной криптографии

Вероятностная модель шифра
Вероятностной моделью шифра называется алгебраическая модель A=(X,K,Y,f) с заданными дискретными независимыми вероятностными распределениями 𝑃 𝑋 ={𝑃 𝑥 , 𝑥∈𝑋} и 𝑃 𝐾 ={𝑃 𝑘 , 𝑘∈𝐾} на множестве X и K
Вероятностное распределение P(X) и P(K) на X и K порождает вероятностное распределение 𝑃 𝑌 ={𝑃 𝑦 , 𝑦∈𝑌} на Y, совместные распределения P(X, K), P(X, Y), P(Y, K) и условные распределения 𝑃 𝑋 𝑦 = 𝑃 𝑥 𝑦 ,𝑥∈𝑋 и P( K 𝑦 )={𝑃 𝐾 𝑦 ,𝑘∈𝐾}

Вероятностная модель шифра
Пример 1.1
Пусть источник порождает сообщение, состоящие из символов алфавита 𝐴={0,1,2} с вероятностями
𝑃 0 =0,1 𝑃 1 =0,7 𝑃 2 =0,2
Значения символов сообщения генерируется независимо т.е используется источник без памяти.
Пусть использован шифр простой табличной замены, шифр-алфавит которого представляет собой перемешанный нормативный алфавит. Тогда имеется 3!=6 вариантов ключа каждый из которых определяет соответствие между символами нормативного алфавита и шифр-алфавита (обозначим это соответствие →)

Вероятностная модель шифра
Пример 1.1
𝑘 1 0→0, 1→1, 2→2
𝑘 2 0→0, 1→2, 2→1
𝑘 3 0→1, 1→0, 2→2
𝑘 4 0→1, 1→2, 2→0
𝑘 5 0→2, 1→1, 2→0
𝑘 6 {0→2, 1→0, 2→1}

Вероятностная модель шифра
Пример 1.1
Пусть противник перехватил шифротекст 𝑦=2000120. Требуется определить наиболее вероятные значения ключа и соответствующие открытые тексты 𝑥.
Пусть все ключи равновероятны т.е. 𝑃 𝑘 𝑖 = 1 6 ,𝑖=1,2…,6.
Поскольку события 𝑘 𝑖 (выбор ключа шифрования 𝑘 𝑖 ) попарно несовместны и составляют полную группу событий, можно оценить вероятности использования каждого из возможных ключей, используя формулу Байеса

Вероятностная модель шифра
Пример 1.1
𝑃 𝑘 𝑖 𝑦 = 𝑃 𝑦 𝑘 𝑖 𝑃( 𝑘 𝑖 ) 𝑃(𝑦) ,
где 𝑃 𝑦 = 𝑗=1 6 𝑃 𝑘 𝑗 𝑃 𝑦 𝑘 𝑗 , 𝑖=1,2,…,6.
Рассчитаем условные вероятности получения криптограммы y при использовании ключа 𝑘 𝑖 . Поскольку символы сообщения генерируются независимо получаем

Вероятностная модель шифра
Пример 1.1
𝑃 𝑦 𝑘 1 =𝑃 𝑥=2000120 =𝑃 (2) 2 ⋅𝑃 0 4 ⋅𝑃 1 = 0,2 2 ⋅ 0,1 4 ⋅0,7=0,0000028
𝑃 𝑦 𝑘 2 =𝑃 𝑥=1000120 =𝑃 (1) 2 ⋅𝑃 0 4 ⋅𝑃 2 = 0,7 2 ⋅ 0,1 4 ⋅0,2=0,0000098
𝑃 𝑦 𝑘 3 =𝑃 𝑥=2111021 =𝑃 (2) 2 ⋅𝑃 1 4 ⋅𝑃 0 = 0,2 2 ⋅ 0,7 4 ⋅0,1=0,0009604
𝑃 𝑦 𝑘 4 =𝑃 𝑥=1222012 =𝑃 (1) 2 ⋅𝑃 2 4 ⋅𝑃 0 = 0,7 2 ⋅ 0,2 4 ⋅0,1=0,0000784
𝑃 𝑦 𝑘 5 =𝑃 𝑥=0222102 =𝑃 (0) 2 ⋅𝑃 2 4 ⋅𝑃 1 = 0,1 2 ⋅ 0,2 4 ⋅0,7=0,0000112
𝑃 𝑦 𝑘 6 =𝑃 𝑥=0111201 =𝑃 (0) 2 ⋅𝑃 1 4 ⋅𝑃 2 = 0,1 2 ⋅ 0,7 4 ⋅0,2=0,0004802

Вероятностная модель шифра
Пример 1.1
Тогда
𝑃 𝑦 = 𝑗=1 6 𝑃 𝑘 𝑗 𝑃 𝑦 𝑘 𝑗 = 1 6 𝑗=1 6 𝑃( 𝑦 𝑘 𝑗 )≈0,000257
Это априорные вероятности
По формуле Байеса оценим апостериорную вероятность того, что был использован ключ 𝑘 𝑖 , при условии что получена конкретная криптограмма y:

Вероятностная модель шифра
Пример 1.1
𝑃 𝑘 1 𝑦 =( 1 6 ⋅0,0000028)/0,000257≈0,002
𝑃 𝑘 2 𝑦 =( 1 6 ⋅0,0000098)/0,000257≈0,006
𝑃 𝑘 3 𝑦 =( 1 6 ⋅0,0009604)/0,000257≈0,622
𝑃 𝑘 4 𝑦 =( 1 6 ⋅0,0000784)/0,000257≈0,051
𝑃 𝑘 5 𝑦 =( 1 6 ⋅0,0000112)/0,000257≈0,007
𝑃 𝑘 6 𝑦 =( 1 6 ⋅0,0004802)/0,000257≈0,311

Вероятностная модель шифра
Пример 1.1
Наиболее вероятны ключ 𝑘 3 и 𝑘 6 и соответствующие им значения открытого текста 𝑥=2111021 и 𝑥=0111201

Энтропия в криптографии
Понятие теории информации, такие как энтропия были впервые введены К.Шенноном, который предложил использовать их в криптографии.
Количество информации сообщения – это минимальное количество, требуемое для записи всех возможных значений (смыслов) сообщения.
Формально количество информации сообщения x измеряется его энтропией обозначаемой 𝐻 𝑥 .
Энтропией сообщения является количественной мерой его неопределенности.

Энтропия в криптографии
Пусть имеется случайная величина a принимающая значения 𝑎 1 , 𝑎 2 … 𝑎 𝑛 с вероятностями 𝑃 1 , 𝑃 2 ,… 𝑃 𝑛 . Тогда энтропия Шеннона определяется
𝐻 𝑎 =− 𝑖=1 𝑛 𝑃 𝑖 𝑙𝑜𝑔 𝑃 𝑖 ,
Где 0log0=0

Энтропия в криптографии
Неопределенность связанная с выбором ключа k из ключевого пространства K, определяется как
𝐻 𝑘 =− 𝑘∈𝐾 𝑃 𝑘 𝑙𝑜𝑔𝑃(𝑘)
Если выбор ключа из ключевого пространства осуществляется равновероятно, то энтропия криптосистемы максимальна - 𝐻 𝑘 = log 𝐾 . Криптосистема тем надежнее тем больше ее энтропия

Энтропия в криптографии
Интенсивность языка определяется как среднее количество информации (энтропия) на один символ языка 𝑅= 𝐻 𝑥 𝑛 , где n – длина шифруемого сообщения x на этом языке.
Абсолютная интенсивность или максимальная энтропия языка определяется как максимальное количество информации на символ языка в предположении что все последовательности символов равновероятны 𝑅 0 =𝑙𝑜𝑔𝑁, где N-мощность алфавита (число символов) этого языка

Энтропия в криптографии
Избыточность языка определяется как 𝐷= 𝑅 0 −𝑅. Избыточность является количественной мерой взаимозависимости и неравновероятности символов языка
Расстояние единственности U – это минимальная длина перехваченного шифротекста, при которой может быть практически однозначно определен ключ шифрования.
𝑈=𝐻(𝑘)/𝐷

Энтропия в криптографии
Пример 1.2
Оценить расстояние единственности шифра простой замены из примера 1.1
𝐻 𝑘 =𝑙𝑜𝑔6≈2,58; 𝑅 0 =𝑙𝑜𝑔3≈1,58
Энтропия на символ источника
𝑅=𝐻 𝑎 =− 0,1⋅𝑙𝑜𝑔0,1+0,7⋅𝑙𝑜𝑔0,7+0,2⋅𝑙𝑜𝑔0,2 ≈1,16
𝐷= 𝑅 0 −𝑅≈0,42
Тогда
𝑈=2,58/0,42≈6,1
Таким образом однозначное дешифрование возможно при перехвате не менее 7 символов шифротекста

Энтропия в криптографии
Пример 1.2
Оценить расстояние единственности шифра Виженера со случайным ключевым словом длиной в четыре символа для сообщений на английском языке. Ключ шифра задается последовательностью 𝑘 1 , 𝑘 2 , 𝑘 3 , 𝑘 4 , каждый элемент которой является случайным сдвигом в диапазоне от 0 до 25. Энтропия ключа 𝐻 𝑘 =𝑙𝑜𝑔 26 4 ≈18,8.
В английском языке с 26 буквами абсолютная интенсивность 𝑅 0 =𝑙𝑜𝑔26≈4,7.
Для длинных сообщений на английском языке оценка R составляет от 1 до 1,5

Энтропия в криптографии
Пример 1.2
Взяв значение R=1,5, получим 𝐷= 𝑅 0 −𝑅≈3,2 или удельное значение точности 𝐷/ 𝑅 0 ≈3,2/4,7≈0,68
Расстояние единственности шифра Виженера хорошо аппроксимируется теоретическими значениями полученными для случайного шифра, поэтому можно рассчитать 𝑈=𝐻(𝑘)/𝐷≈18,8/3,2≈5,9 Таким образом однозначное дешифрование шифра Виженера с 4-символьными ключами возможно при длине шифротекста не менее шести символов

Алгоритм шифрования DES
Алгоритм шифрования DES (Data Encryption Standard) был опубликован в 1977 г. и предназначен для защиты важной, но несекретной информации в государственных и коммерческих организациях США.
Шифр DES блочный – преобразования в нем проводятся блоками по 64 бита. Ключ – 56 битный. Могут использоваться 64-битные ключи, но значащими являются только 56 битные

Алгоритм шифрования DES. Подстановка с помощью S-блоков
48-битовый результат сложения расширения правого блока и раундового ключа разбивается на восемь фрагментов по шесть бит, которые подаются на входы соответствующих таблиц замен (S-блоков). У каждого S-блока 6 битовый вход и 4 битовый выход.
Таблицы замен являются фиксированными и содержат четыре строки по 16 значений от 0 до 15 (4 битовые числа). Строки и столбцы таблиц замены нумеруются начиная с нуля.

Алгоритм шифрования DES.
Таблица подстановок

Алгоритм шифрования DES.
Таблица подстановок

Алгоритм шифрования DES. Подстановка с помощью S-блоков
Пример
Пусть на вход шестого блока S попадает 110011. Первый и последний биты объединяясь образуют 11 = 3 что соответствует 3 строке. Средние четыре бита образуют 1001 = 9 что соответствует 9 столбцу. Элемент находящийся на пересечении 3 строки и 9 столбца есть 14 т.е 14 = 1110. Выход –битовая строка 1110