Преподаватель: Преподаватель




НазваниеПреподаватель: Преподаватель
Дата конвертации15.03.2013
Размер445 b.
ТипПрезентации


Преподаватель:

  • Преподаватель:

  • Воронов Р. В.




Вопросы:

  • Вопросы:

  • Насколько надежна система, если неограниченные ресурсы?

  • Имеет ли криптосистема единственное решение, если нет, то сколько?

  • Какой объем текста нужно перехватить чтобы система имела единственное решение?

  • Существуют ли секретные системы, в которых нельзя найти единственное решение независимо от объема перехваченной криптограммы?

  • Существуют ли секретные системы, в которых противник не получает никакой информации независимо от объема перехваченного материала?



Опр.: Система называется совершенно секретной, если для любого E и для любого М выполняется: PE(M)=P(M)

  • Опр.: Система называется совершенно секретной, если для любого E и для любого М выполняется: PE(M)=P(M)

  • P(M) – априорная вероятность сообщения М

  • PM(E) – условная вероятность криптограммы Е при условии, что выбрано сообщение М

  • P(E) – вероятность получения криптограммы Е

  • PE(M) – апостериорная вероятность сообщения М при условии, что перехвачена криптограмма Е



Теорема: система совершенно секретна тогда и только тогда, когда при любом M и любом Е выполняется PM(E)=P(E).

  • Теорема: система совершенно секретна тогда и только тогда, когда при любом M и любом Е выполняется PM(E)=P(E).

  • Док-во:

  • По свойству вер-ти

  • если ,

  • тогда P(M)≠0 =>



Полная вероятность всех ключей, переводящих сообщение Mi в данную диаграмму Е, равна полной вероятности всех ключей, переводящих сообщение Mj в ту же самую криптограмму E для всех Mi, Mj и Е.

  • Полная вероятность всех ключей, переводящих сообщение Mi в данную диаграмму Е, равна полной вероятности всех ключей, переводящих сообщение Mj в ту же самую криптограмму E для всех Mi, Mj и Е.

  • Для любого сообщения должен быть свой ключ: |K| >=|E|



Пример:

  • Пример:

  • |K| =|M|=|E| ; TiMj = Es ;

  • S=(i+j)mod n ; нумерация от 0

  • При этом PE(M)=1/n. (n=3)



Одноразовый блокнот:

  • Одноразовый блокнот:

  • Длина ключа равна длине сообщения.

  • Ключ абсолютно случаен.

  • Ключ используется только один раз.



Энтропия – мера неопределенности.

  • Энтропия – мера неопределенности.

  • Пусть имеется n объектов с вероятностями p1,..,pn , тогда связанная с ними энтропия равна:

  • Если pi =1, а все остальные pj =0, то H=o.



Когда энтропия равняется 0, это говорит о полной осведомленности системы.

  • Когда энтропия равняется 0, это говорит о полной осведомленности системы.

  • Энтропия принимает максимальное значение , если p1=p2=..=pn=1/n

  • Энтропия уменьшается с увеличением наших знаний о системе.



Пример: секретная система включает в себя два статистических выбора:

  • Пример: секретная система включает в себя два статистических выбора:

  • энтропия ключа :

  • энтропия сообщ.:

  • Количество неопределенности в системе не может быть больше энтропии ключа.



Шифр Цезаря.

  • Шифр Цезаря.

  • функции от N





Криптоаналитику интереснее работать не с энтропией H(M) и H(K) ,а с так называемыми условными энтропиями сообщения и ключа.

  • Криптоаналитику интереснее работать не с энтропией H(M) и H(K) ,а с так называемыми условными энтропиями сообщения и ключа.

  • Ненадежности:

  • HE (M) - условие энтропии сообщения

  • HE (K) - условие энтропии ключа



Теорема: Ненадежность ключа HE(K,N) – невозрастающая функция от N. Ненадежность первых А букв сообщения является невозрастающей функцией N. Если перехвачено N букв ,то ненадежность первых N букв сообщ. меньше или равна ненадежности ключа.

  • Теорема: Ненадежность ключа HE(K,N) – невозрастающая функция от N. Ненадежность первых А букв сообщения является невозрастающей функцией N. Если перехвачено N букв ,то ненадежность первых N букв сообщ. меньше или равна ненадежности ключа.

  • Полная избыточность для N букв сообщений

  • DN = log G - H(M) ,где G- полное число сообщений длины N.



Пример:

  • Пример:

  • N=3; двоичная система; G=8

  • H(M) = - 4*¼ log2 ¼=2

  • DN = log 8-2 =1



Если |E|=|M| (для М), то H(E)<= log G;

  • Если |E|=|M| (для М), то H(E)<= log G;

  • HE(K)=H(K)+H(M)-H(E)

  • Следовательно, ненадежность ключа: HE(K)>=H(K)+H(M)-log G =

  • = H(K)-log G-H(M)= H(K)-DN



Уменьшение надежности ключа после перехвата N букв не превосходит избыточность языка.

  • Уменьшение надежности ключа после перехвата N букв не превосходит избыточность языка.

  • Вывод: только наличие избыточности в исходных сообщениях дает возможность находить решение криптограммы.

  • DN=D*N где D – избыточность на одну букву

  • Если HE(K)=0 следовательно H(K)=DN=DN0

  • H(K)<=HE(K)+DN



Система называется идеальной ,

  • Система называется идеальной ,

  • если HE(K) и HE(M) не стремятся к 0

  • при N ->∞.

  • Система называется строго идеальной, если HE(K)=H(K) при любом N.

  • Пример: простая подстановка, примененная к языку ,в котором все буквы равновероятны и независимы.





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

  • Если объем перехваченной криптограммы меньше точки единственности, то в задачах противника сводится к поиску наиболее вероятных сообщений.

  • Если же объем точки единственности, то всегда существует единственное решение.

  • Но в разных системах требуется разный объем работы для поиска этого решения.

  • W(N) – рабочая характеристика шифра

  • N – число букв в криптограмме



  • Если HE(K) ->0, то для хороших шифров W(N) должна быть высокой таким образом проблема создания хорошего шифра сводится к нахождению наиболее сложной задачи, удовлетворяющему определенным условиям.



Существуют 2 подхода к созданию шифров:

  • Существуют 2 подхода к созданию шифров:

  • Необходимо рассмотреть все известные методы противника и алгоритм, который будет стоек ко всем этим шифрам.

  • Необходимо сделать так, чтобы решение шифра было эквивалентно решению трудноразрешимой проблемы.



Методы противника:

  • Методы противника:

  • Статистический анализ (частоты букв, пар букв, троек букв и т.д.)

  • Метод вероятных слов

  • Методы шифровальщика:

  • Подстановки

  • перестановки





При шифровании любой буквы сообщения используется значительная часть ключа

  • При шифровании любой буквы сообщения используется значительная часть ключа

  • Использование распыления, т.е. для восстановления любой статистики сообщения или ключа нужен большой объем криптограммы

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



Для этих целей Клод Шеннон предлагает использовать перемешивание.

  • Для этих целей Клод Шеннон предлагает использовать перемешивание.

  • Для перемешивания предлагается использовать:

  • Многократное повторение транспозиции (T) (P)

  • Подстановки (S)

  • Линейные операции (L) (+mod, xor)

  • F = LSLST



§4 …..

  • Чем больше размер входа и выхода, тем больше нужна таблица соответствий между входом и выходом.

  • S

  • Вход Выход R = (3 5 4 1 6 2)

  • 000 101 S-блоки должны быть построены так, чтобы

  • 001 110 выход сильно отличался от входа, чтобы при

  • 010 111 изменении 1-го бита входа менялось,

  • 011 000 примерно половина, битов выхода.

  • 100 011

  • 101 010

  • 110 001

  • 111 100



§5 Блочные шифры

  • В блочном шифре сообщения разбиваются на

  • блоки равной длины и каждый блок шифруется

  • отдельно.

  • Размер блока: 64 - 128 бит

  • Размер ключа: 64 – 128 - 256 бит

  • Ek(M) - шифр блока M на ключе k

  • Dk(C) - расшифрование блока C на ключе k



§5 Блочные шифры

  • Концептуально, блочный шифр можно представить

  • в виде таблицы соответствий входных данных и

  • выходных.

  • n – размер блока (в битах)

  • (степень)2n - кол-во сообщений

  • (2n)! Различных перестановок = таблице

  • Каждая конкретная таблица соответствует 1-му

  • ключу.

  • Пространство ключей меньше числа разных

  • таблиц.



§5 Блочные шифры

  • Устройство шифров

  • При построении блочных шифров используется

  • принцип итератирования. Блок обрабатывается

  • многократно в несколько циклов.

  • Один цикл называется – раунд.

  • Каждый раунд состоит в использовании слабого

  • блочного шифра.

  • Обычно на схемах шифра представляют 1 раунд

  • обработки и указывают число раундов.



§5 Блочные шифры

  • На каждом раунде используется раундовый

  • ключ, который получается из основного ключа.

  • Чем больше раундов, тем выше стойкость шифра,

  • но с другой стороны, тем ниже эффективность.

  • При анализе шифра обычно начинаются атаки

  • с меньшим числом раундов.



§5 Блочные шифры

  • Атаки на блочные шифры

  • Виды атаки:

  • По шифротексту - когда известен текст, но не

  • известны ни ключ, ни сообщение.

  • По известному сообщению и шифротексту –

  • известно соответствующее сообщение и текст.

  • По выборочному сообщению – возможно

  • Подсовывать и получать шифротекст.

  • Современные шифры стараются сделать стойкими

  • ко всем трем видам атак.



§5 Блочные шифры

  • Методы криптоанализа

  • Дифференциальный к/а (выясняет отличия)

  • Линейный к/а (строятся отношения)

  • Подстановки

  • Перестановки

  • Шифры, основанные на подстановках и

  • Перестановках, называются – sp-сети.





DES (Data Encryption Standard) - стандарт шифрования данных

  • DES (Data Encryption Standard) - стандарт шифрования данных

    • Опубликован в 1974 г.
    • Стандарт США последней трети XX века
    • Разработчики Фейстель, Копперсмит и др., фирма IBM
    • Основан на шифре Lucifer
    • Размер блока 64 бита
    • Размер ключа 56 бита
    • 16 раундов




ГОСТ 28147 – 89 (GOST)

  • ГОСТ 28147 – 89 (GOST)

    • Ключ – 256 бита
    • Блок – 64 бита
    • Количество раундов – 32
    • В стандарте ничего не сказано как должен выглядеть S-блоки. Но чуть позже было издано дополнения для уточнения S-блоков.






ECB (Electronic Code Book) – Электронная кодовая книга

  • ECB (Electronic Code Book) – Электронная кодовая книга



CBC (Cipher Block Chaining) – сцепление блоков шифра.

  • CBC (Cipher Block Chaining) – сцепление блоков шифра.

    • Два одинаковых блока текста на выходе дадут два разных шифр-блока.
    • С0 – вектор инициализации (в дальнейшем передается как часть шифртекста)


CFB (Cipher Feed Back) – обратная связь по шифртексту

  • CFB (Cipher Feed Back) – обратная связь по шифртексту

    • В этом режиме блочный шифр работает как поточный.


OFB (Output Feed Back) – обработка связь по выходу

  • OFB (Output Feed Back) – обработка связь по выходу

    • Блочный шифр начинает работать в поточном режиме
    • Преимущества: Ключевая последовательность может быть вычислена заранее для шифрования в режиме реального времени




CTR – режим счетчика

  • CTR – режим счетчика

    • Работает также как и OFB, отличается формированием
    • Si = Ek (S0+i)
    • S0 – уникальный номер сообщения


Глава 2 Ассимметричные криптосистемы

  • §1 Теоретико-числовые основы



§1 Теоретико-числовые основы Модулярная арифметика

  • Рассмотрим остатки от деления на n, nЄN

  • a, b – целые числа( b≠0)

  • Целочисленное деление a на b

  • a div b =[a/b]

  • Остаток от деления

  • a mod b = a-b*[a/b]

  • 0<=a mod b



§1 Теоретико-числовые основы Модифицированная процедура вычисления mod

  • MOD (a,b)

  • { c=a%b

  • if c<0 then

  • c+=b

  • return c;

  • }



§1 Теоретико-числовые основы Модифицированная процедура вычисления mod

  • mod n;

  • 0, 1,…,n-1 – остатки от деления на n

  • Zn = {0,1,…,n-1}

  • Операции +, -, *

  • a, b Є Zn

  • C= (a+b) mod n

  • C Є Zn



§1 Теоретико-числовые основы Модифицированная процедура вычисления mod

  • Опр: Будем говорить, что a, b Є Z

  • сравнимы по модулю n

  • a = b (mod n)

  • если a mod n = b mod n



§1 Теоретико-числовые основы Группы вычетов

  • Опр: Группа ( S,°), для которых выполняются аксиомы:

  • 1) Замкнутость, для всех a, b Є S, существует

  • с Є S, c=a°b

  • 2) Ассоциативность, для всех a, b, c

  • (a°b)°c = a°(b°c)

  • 3) Существование нейтрального элемента

  • e Є S для всех a Є S a°e = e°a = a

  • 4) Существование обратного элемента для всех a Є S существует b Є S a°b = b°a = e



§1 Теоретико-числовые основы Группы вычетов

  • Опр: число элементов группы (мультипликативных) вычетов φ (n) = |Zn*| называется функция Эйлера

  • Свойства функции φ (n):

  • 1) Если р – простое, то φ (р) =р-1

  • 2) Если n и m взаимно-просты

  • НОД (n, m) =1, то

  • φ (n*m) = φ (n) *φ (m)



§1 Теоретико-числовые основы Группы вычетов

  • Обратный элемент для a Є Zn* находим при помощи расширенного алгоритма Евклида

  • ax+ny = 1

  • a-1 = x mod n



§1 Теоретико-числовые основы Подгруппы

  • Опр: Пусть (S, °) – это некоторая группа , тогда (S’, °) называется подгруппой группы (S, °), если S’cS и (S’, °) являются группой.

  • Опр: Порядок конечной группы – число ее элементов множества S.

  • Опр: a(k) – k-тая степень элемента а группы (S, °), если a(k) = а°а°а°…°а - k раз

  • Опр: Порядком элемента а конечной группы (S, °) называется наименьшее отрицательное целое число k



§1 Теоретико-числовые основы Подгруппы

  • Степени любого элемента конечной группы образуют подгруппу, для которой исходный элемент называется порождающим; порядок этой подгруппы равен порядку порождающего элемента



§1 Теоретико-числовые основы Подгруппы

  • Теорема Лагранжа: Порядок подгруппы конечной группы делит порядок группы.

  • Следствие: для всех а Є S конечной группы (S, °)

  • a(|S|) = е

  • Теорема Эйлера: если НОД (а, n) = 1 следовательно aφ(n) mod n = 1

  • Малая терема Ферма: если а≠0 (mod p) и р – простое, следовательно aр-1 mod p = 1



§1 Теоретико-числовые основы Китайская теорема об остатках

  • Пример: 109 mod 12=?

  • НОД (3,4)=1

  • 12 3 4 Все пары различны и любая возможная пара

  • 0 0 0 - присутствует.

  • 1 1 1 7+8 mod 12=3

  • 2 2 2 1+2 mod 3=0

  • 3 0 3 3+0 mod 4=3

  • 4 1 0

  • 5 2 1 Решение: 109 mod 12=4

  • 6 0 2 19 mod 3=1

  • 7 1 3 29 mod 4=0

  • 8 2 0

  • 9 0 1

  • 10 1 2

  • 11 2 3



§1 Теоретико-числовые основы Китайская теорема об остатках

  • Вместо выполнения действия над остатками от деления на n, проще выполнять действия над остатками над взаимопростыми множителями.



§2 RSA

  • Обоснование:

  • E(M)= Me mod n –функция зашифрования

  • D(C)= Cd mod n –функция расшифрования

  • Нужно доказать: D(E(M))=M

  • Полагаем, что 1<=M<=n-1

  • D(E(M))= Cd mod n =(Me)d mod n=?

  • (Me)d mod n= Med mod n= (*)



§2 RSA

  • (*)= M(p-1)(p-1)y+1 mod n=((Mp-1)(q-1)yM) mod n

  • Mp-1 mod p = {1, если M mod p≠0

  • {0, если M mod p=0

  • Аналогично:

  • Mq-1 mod q = {1, если M mod q≠0

  • {0, если M mod q=0

  • По следствию к китайской теореме об остатках:

  • n=pq

  • y=x (сравнимо с x) mod p <=> y=x mod n

  • y=x mod q



§2 RSA

  • (Mp-1)(q-1)y M mod p = M mod p

  • Аналогично:

  • (Mq-1)(p-1)y M mod q = M mod q

  • Вывод:

  • M(p-1)(q-1)y M mod n = M mod n



§2 RSA

  • Особенности реализации:

  • Владелец секретного ключа знает разложение n на множители, т.е. p и q (n=pq). Значит можно использовать Китайскую теорему об остатках для расшифрования и ускорения процесса.

  • M=Cd mod n

  • M1=Cd mod p Находим M

  • M2=Cd mod q

  • В этом случае секретный ключ становится длиннее



§2 RSA

  • Если e – мало и M – мало, то может оказаться, что Me

  • Для повышения стойкости существуют специальные рекомендации для p и q.



§2 RSA

  • Атаки на RSA:

  • Противник знает открытый ключ (e,n).

  • Для нахождения закрытого числа можно

  • попытаться найти разложение n на множители

  • - Задача Факторизации.



§3 Криптосистема Диффи - Хелманна

  • Задача криптосистемы состоит в создании общего секретного ключа, где используются параметры:

  • p – большое простое число,

  • q – некоторое большое число,

  • pg – известные, общие.

  • Есть 2 участника протокола – A и B

  • A: генерирует секретное большое число x

  • X = gx mod p

  • x->B



§3 Криптосистема Диффи - Хелманна

  • B: y; y = gy mod p , y->A

  • A: k = yx mod p

  • B: k’ = xy mod p

  • K = yx = gyx (mod p)

  • k’ = xy = k (mod p)

  • R – общий ключ

  • x = gx mod p



§3 Криптосистема Диффи - Хелманна

  • Все различные степени элемента g образуют подгруппу группы Zp*.

  • Метод повторного возвращения в квадрат.

  • Алгоритм работает за полиномиальное время от длины x.

  • Неизвестно полиномиальный алгоритм, который по x вычисляет k.

  • Такие функции, которые в одну сторону вычисляются легко, а в обратную трудно, называются односторонними.



§3 Криптосистема Диффи - Хелманна

  • Проблема вычисления x по X называется задачей

  • Дискретного логарифмирования.

  • Противник кроме p и g знает X,Y.

  • Т.О. сложность этого алгоритма основана на сложности дискретного логарифмирования.

  • Однако противник может попытаться найти x путем перебора всех элементов подгруппы, порождаемой элементом g.



Похожие:

Преподаватель: Преподаватель iconПреподаватель Бойко Е. Н. Преподаватель Бойко Е. Н
Истребление чиновников и дворян, как главных «возмутителей империи и разорителей крестьян»
Преподаватель: Преподаватель iconПреподаватель: преподаватель
Алавердов Ашот Робертович почетный работник высшего профессионального образования рф, доктор экономических наук, профессор, заведующий...
Преподаватель: Преподаватель iconBB24FC9C-57E2-478F-954c-f80F892F841C
Владивостокский государственный университет экономики и сервиса Институт международного бизнеса и экономики Кафедра «Финансы и налоги»...
Преподаватель: Преподаватель iconКафедра «Финансы и налоги» Преподаватель: Просалова Вероника Сергеевна, к э. н., доцент «бюджетное планирование и прогнозирование »
Кафедра «Финансы и налоги» Преподаватель: Просалова Вероника Сергеевна, к э н., доцент
Преподаватель: Преподаватель iconОбразование высшее, мгпи, 2000 г., Ифф, преподаватель истории. Образование высшее, мгпи, 2000 г., Ифф, преподаватель истории
А. А. Данилова, Л. Г. Косулина) «История Отечества» (А. А. Преображенский, Б. А. Рыбакова) Рабочая тетрадь по Истории Отечества В....
Преподаватель: Преподаватель iconЛ. А. Дементьева, ст преподаватель Л. А. Дементьева, ст преподаватель

Преподаватель: Преподаватель iconПреподаватель: Сидоренко Н. А

Преподаватель: Преподаватель icon«Субкультура протест или отличие в образе жизни?» Малева Е. А. Преподаватель психологии
...
Преподаватель: Преподаватель iconСоловьёва М. А., старший преподаватель кафедры гуманитарных дисциплин

Преподаватель: Преподаватель iconАвтор: Шиварев Павел Васильевич Старший преподаватель

Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница