Наши лекции Компы Криптография / 2- crypto1

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Лекции по курсу Защита и Безопасность Информации

Составила:

Пестунова Тамара Михайловна

Новосибирск, 2002

Лекция 1-крипто

Основы криптографической защиты

Исторически первые сведения об использовании шифрованных писем относятся к древним цивилизациям Египта, Китая, Месопотамии (~ IV в. до н.э.). Одно из наиболее известных – глиняная табличка, Месопотамия, клинопись, рецепт глазури для гончарных изделий. В этом тексте использовались редко употребляемые значки, игнорировались некоторые буквы, вместо имён употреблялись цифры.

Древний Египет – шифрованные религиозные тексты и мед. прописи.

Библия – некоторые фрагменты библиотечных текстов зашифрованных шифром "атбаш": i-ый символ заменён на (n-i+1)–ый, где n – число букв в алфавите.

Название: Алев (первая), Так (последняя), Вета (вторая), Шин (предпоследняя) – древнесемитский алфавит.

Древняя Греция "Султала"

Жезл цилиндрический, наматывалась пергаментная лента. Письмо вдоль жезла. Лента снималась. Расшифровка – наматывали на жезл того же диаметра.

Вскрытие "султалы" – конусовидный жезл. Лента наматывается и постепенно сдвигается от малого диаметра к большому до появления осмысленного текста – так определяли диаметр.

Табличка Энея. Горизонтально – алфавит, сбоку – выемки для нити. Нить наматывается и на каждом обороте – узелки против нужной буквы. Ключ – геометрическая разметка талл. + порядок букв.

Квадрат Полибия

	1	2	3	4	5
1	A	B	C	D	E
2	F	G	H	I,J-	K
3	L	-	-	-
4
5					Z

буква = (i, j).

Передача сигналов с помощью горящих факелов в каждой руке. Усложнённый вариант – с ключом.

Шифр Цезаря "Записки о галльской войне" Iв. до н.э.

Гай Светоний: существуют и его письма к Цицерону и письма к близким о домашних делах: в них он пользовался тайнописью, т.е. менял буквы так, что у них не складывалось ни одного слова. Чтобы разобрать и прочитать их нужно читать четвёртую букву вместо первой (D вместо A), и так далее.

Т.е. это подстановка с циклическим сдвигом на 3 буквы.

В 1412г. в 14-томной энциклопедии (арабская) "Шауба-аль-Аша" – специальный раздел о криптографии. – 7 способов. И впервые говориться о примерах раскрытия шифров методом частотного анализа.

1466 – Леон Альберти. Шифровальный диск.

Решётка Кордано

7х10.

(1,8), (2,9) (3,6) (4,5) (4,6)

(5,1) (5,6) (5,7) (5,9)

(6,2) (6,10) (7,9) (7,10)

Число квадратов решёток

Шифр Вижинере

Шифрование по ключу слож _N.

Шифр – семейство обратимых преобразований, каждое из которых определяется некоторым параметром (ключом) и порядком применения (режимом шифрования).

Преобразование описывается в виде криптографического алгоритма один и тот же алгоритм может применяться в различных режимах. Выбор режима зависит от конкретной ситуации.

Криптосистема – пара алгоритмов (шифр – расшифр).

Противник – любой субъект, не имеющий права ознакомления с содержанием передаваемой информации.

Атака – действие противника, направленные на завладение защищаемой информацией.

• пассивные атаки (прослушивание, анализ трафика; перехват, запись и дешифровка сообщений)

• активные атаки (связаны с прерыванием сеанса связи и содержанием поддельных сообщений – имитация или модификацией сообщения - подмена)

Пусть М – открытое, С – шифрованное сообщение, тогда процессы зашифровки – расшифровки можно записать в виде:

E – алгоритм зашифровки, D – алгоритм расшифровки, K₁ – ключ шифровки, K₂ - ключ расшифровки.

Должно выполнятся условие

Какой из ключей k₁или k₂ делать секретным – зависит от ситуации.

Не существует единого шифра на все случаи жизни. Выбор способа шифрования (алгоритм + режим) зависит от особенностей передаваемой информации (ценность, объём, способ представления, необходимый способ передачи) и возможностей владельцев по защите своей информации (стоимость технических устройств, удобство использования, надёжность функционирования и т.п.)

Следует помнить, что даже высокостойкие, надёжные алгоритмы при неправильном использовании теряют свои свойства.

Криптоанализ в значительной степени использует тот факт, что пользователи всегда допускают ошибки.

Формальные модели шифров

Шифрование предполагает наличие множества обратимых преобразований. Выбор ключа определяет функцию

{множество открытых текстов}  множество зашифрованных текстов}

Х К Y

Способ вычисления этой функции для конкретных аргументов – правило зашифровывания.

Выбранный ключ k – ключ зашифровывания

E_k: X  Y, k  K (множество ключей)

E = { E_k: k  K}

E_k(x) = { E_k(x): x  X}

Правило расшифровавания: D_k: E_k(x)  X на ключе k  K

D = { D_k: k  K }.

Если k  K, то k = (k_з, k_р), в общем случае k_з ≠ k_р и поэтому

Определение 1

Шифром (шифрсистемой) называется

_А = (X, K, Y, E, D), т.ч.

1)  x  X_n k  K D_k(E_k(x)) = x

2)

Усл. 1) - однозначность расшифровывания

2) – любой элемент из Y может быть представлен как зашифрованное сообщение при подходящих x  X_n k  K.

Из усл. 1) следует инъективность E_k, т.е. если x₁, x₂  X и x₁ ≠ x₂, то  k  K E_k(x₁) ≠ E_k(x₂)

_A – алгебраическая модель шифра.

Кроме алгебраической модели существует вероятностная модель шифра, основанная на теории информации Шеннона.

Определим P(X) и P(K) – априорные распределения вероятностей на множествах X и K 

 x  X определена вероятность P_x(x)  P(X)

 k  K определена вероятность P_k(k)  P(K).

При этом

и .

_В = (X, K, Y, E, D, P(X), P(K))

Вероятностные характеристики шифров активно используется в криптоанализе при решении задач вскрытия шифров.

Обычно X и Y представляются в виде декартовых произведений:

A, B – алфавиты открытого и шифрованного текста соответственно,  X и Y множества слов длины L и L₁ в этих алфавитах.

Построим модель шифра простой замены в алфавите А.

Определение 2 Пусть ; K  S(A), где S(A) – симметрическая группа подстановок множества А. Тогда  k  K открытого текста x = (x₁,…,x_L) и шифрованного текста y = (y₁, y₂,…,y_L) правила зашифровки и расшифровки определяются формулами:

E_k(x) = (k(x₁), … , k(x_L))

D_k(y) = (k^-1(y₁), … , k^-1(x_l)) | k^-1 – подстановка обратная к k.

В более общей ситуации для шифра простой замены X ≠ Y и , причём |A| = |B|.

K – множество биективных функций A  B

K = {k: A  B, k – биективная}

Правила зашифрования и расшифрования определяются также в соответствии с определением 2.

Шифр перестановки

Определение 3 Пусть X = Y = A^L, K  S_L, где S_L - симметричная группа подстановок на {1, 2, … , L}. Тогда  k  K,  открытого текста x = (x₁,…,x_L) и  зашифрованного текста y = (y₁, y₂,…,y_L)

E_k(x) = (x_k(1), … , x_k(L))

D_k(y) = (y() | k^-1 – подстановка обратная к k.

Другие симметричные шифры – это композиции некоторых шифров замены и перестановки.

Рассмотрим пример модели ассиметричного шифра – RSA (Rivest Shamir Adleman)

Определение 4.

Пусть n = p*q, где p и q – простые числа

X = Y = Z_n – кольцо вычетов по модулю n.

K = {(n, p, q, e, d) = e, d  Z_n, n = p*q, ed  1(mod (n))}, где (n) – функция Эйлера = (p – 1) (q -1).

Рассмотрим k  K в виде k = (k_з, k_р), где k_з = (n, l); k_р (n, p, q, d).

Правила:

Функция Эйлера – число натуральных чисел от 1 до n, взаимно простых с n.

  хорошо вычисляется при известном разложении числа на множители.

Малая теорема Ферма (вычисление обратного элемента по заданному модулю)

Если p – простое число и НОД(a, p) = 1

а^p-1 = 1(mod p)

Обращение

Если НОД(a, p) = 1, то а^p-1 = 1(mod p).

Тогда имеем а^-1 = a^(n)-1(mod n)

Модели открытых текстов

В вероятностной модели – учёт частотных характеристик учёт

k-грамм A = {a₁…a_n} алфавит открытых текстов p(b₁ b₂ … b_k) k  N. b_i  A.

вероятностная модель k-го приближения

c₁, c₂, … , c_k, c_k+1,…

p(c₁ … c_k)  p^k(A)

p(c₂ … c_k+1)  p^k(A) и т.д.

k = 1: p(c_i)  p¹(A).

k = 2 c₁ p(c₁)  p¹ (A)

p(c_i-1)  p¹(A)

Прост. однор. у М.

8