Криптография, лекция 02 (08 октомври)
Материал от wiki на eSyr.
Криптологията се състои от криптография и криптоанализ. Криптографията се занимава със създаването на шифри, разбиването на криптоанализа. Гражданските книги са посветени главно на криптографията. Шифроването е процес на обратимо преобразуване на информация от четлива в нечетлива форма. Информацията в четима форма е текст, в нечетима форма - шифрован текст. Наборът от данни, който прави трансформациите възможни, се нарича ключове за шифър.
Криптовалофията до голяма степен стана гражданска, но още преди това беше формулиран принципът - при изграждането на криптографска система трябва да се разчита на това и само на това, че само ключът ще бъде таен. Пазенето на тайна за структурата на криптосистемата е много по-сложно и е доста трудно да се запази в тайна. Този принцип е доказан в хода на военните действия през деветнадесети век и е формулиран в края им. Следователно обикновено се приема, че само ключовете за криптиране са неизвестни.
Съвременните алгоритми за криптиране се разделят на симетрично и асиметрично криптиране.
Алгоритмите за симетрично криптиране са подредени по очевиден начин. Това е функция, която, когато се приложи към обикновен текст с помощта на ключ, създава шифрован текст. Има функция за декриптиране, обратна на него, която дава обикновения текст със същия ключ. Ключът за криптиране е равен на ключа за декриптиране.
В случай на асиметрична схема ключът за криптиране не е равен на ключа за декриптиране.
Криптирането на потока изглежда малко по-различно. Криптирането на потока е генератор на псевдослучайна последователност, зависим от ключа. Тази последователност обикновено може да има безкрайна дължина, на практика те обикновено са доста големи, т.е. извън границите на текущо съхраняваните данни. Например може да е приемливо да шифровате няколко терабайта данни с един ключ.Шифроването се осъществява чрез побитово добавяне на битове в обикновен текст с битове от псевдослучайна последователност. дешифрирането се извършва по подобен начин по очевидни причини.
Възниква въпросът - как да оценим сигурността и силата на такъв алгоритъм за криптиране. Надежден ли е, от какво зависи надеждността му? От генератор. От какво свойство на генератора? Генераторът трябва да генерира произволна последователност. Какво е произволна последователност? Всеки следващ байт от произволна последователност не може да бъде предвиден въз основа на предишните. Близо, но не байт, а малко. и трябва да се формулира като условна вероятност.
Съдържание
[редактиране] Шифърът на Цезар
За да шифрова съобщенията си, Цезар избра буква три от тази, която искаше да шифрова. A=D, B=E, C=F. Тази система работи достатъчно добре за Цезар, тъй като криптографията не е била развита през първи век пр. н. е. Как ще се счупим сега? Честотен анализ. Честотният анализ е твърде сложен. Дешифрира се чрез обратно заместване.
Как шифърът на Цезар може да бъде направен по-труден? Добавяне на ключ към него. Можете да използвате бутона, за да зададете броя на позициите, към които се преместваме. Как да се счупи? Разбиване на смяна. Има общо 26 опции. Ключовото пространство е много малко.
Едно от условията за добър шифър е ключовото пространство да не е малко и да не позволява изброяване.
Какво е добро пространство за ключове? Невъзможно е да се подреди с разумна технология за разумно време. Неясен. Какво е разумен срок? Каква техника има противникът? Дължината на ключа трябва да е равна на дължината на текста. В следващата лекция ще говорим за Шанън, ще докажем, че в този случай шифърът може да бъде демонстративно надежден. На практика обаче това не е много удобно.И така, има ли други опции? Така че една brute-force атака отнема толкова много време, че след нея защитената информация няма смисъл.
[редактиране] Шифър със случайно заместване
Плоча с произволно съответствие на едни букви с други. Ключово пространство 26!. Това е много голям брой. Дори при съвременната технология по време на такова търсене почти всяка информация ще остарее. Как да се счупи? Все още е честотен анализ. Анализираме базата данни с текстове на желания език и търсим най-популярното писмо. Разглеждаме най-често срещаната буква в шифрования текст. С голяма вероятност това ще бъде таблична двойка. От практическа гледна точка не винаги е удобно да се използват честотите на една буква. Първата ви задача ще бъде честотен анализ.
Ако погледнете таблицата на разпределението на честотите в истински английски, след като изберете гласните, честотите стават слабо различими и правописът става труден за автоматизиране. Ако го счупите ръчно, тогава с дузина налични букви можете да възстановите значението.
Подходът има естествено развитие - вижте най-често срещаните биграми и триграми. На английски най-често срещаната триграма е the, с изключение на текстовете на Хемингуей, където е и, която има за цел да илюстрира скуката на ежедневието.
И така, първата ви задача е да разшифровате шифрования текст на познат език (български или английски), като знаете, че той е шифрован с обикновен заместващ шифър. Ще бъде набор от текстове за изграждане на честотни таблици
Защо простият заместващ шифър се оказва ужасно несигурен? Защото честотата е запазена. Шифъртекстът изглежда като текст на естествен език. Но какъв е тогава идеалният шифър? Шифран текст, в който всички изходни знаци ще бъдат равномерно разпределени. Това би означавало, че вероятносттаполучаването на единица на изхода е равно на вероятността да се получи нула на изхода.
В района на 16-17-ти век, когато непригодността на обикновения заместващ шифър за нещо сериозно стана очевидна за всички, хората започнаха да измислят нови дизайни, опитвайки се да осигурят еднаквост на символите на шифрования текст.
[редактиране] Полиазбучни шифри
Един подход беше класът на полиазбучните заместващи шифри. Представете си, че имаме не една заместваща табела, а няколко. Нека поставим десет от тях. Първата буква с първата, втората с втората, единадесетата с първата и т.н. Механизмът е разбираем, защото очевидно заличава разликите между честотата в изходната азбука - буквата и на различни места ще бъдат заменени с различни знаци.
Шифърът на Виженер стана популярен, който изглеждаше като шифър на Цезар над някаква дума, която беше ключът.
Таблица 26x26, всъщност всички варианти на шифъра на Цезар.
След това беше избрана дума, която беше изписана над обикновения текст.
Ние използваме всяка колона като отделна версия на шифъра на Цезар. a е първият ред на таблицата, b е вторият, c е третият.
Може да се види, че ако ключът е доста голям и шифрованата буква попада под различни букви на ключа, тогава тя ще бъде шифрована в различни букви на шифрован текст и простият честотен анализ няма да работи.
Как да се счупи? Тъй като дължината на ключа не е равна на дължината на текста, ако знаем дължината на ключа, тогава можем да съставим материал за честотен анализ. Вярно е, че трябва да се избере дължината на ключа. Ние итерираме дължините на ключовете, разглеждаме получените честоти и виждаме дали са подобни на честотите на естествения език. Ако си приличат - познахме, правим честотен анализ. Ако не е подобен, опитайте с различна дължина на ключа. Какъв е проблемът? Кратка дължина на клавиша, неравна на дължината на текста. Дойде същата идеянасочете се към всички, които са разгледали тези ключове. Хрумна им идея - система с автоключ.
Как да го разбия? Разбиването на първите герои няма да работи, защото те са най-упоритите. Може би се опитайте да познаете дължината на ключа? Е, нека познаем, какво следва?
Има ли някакъв начин за прилагане на честотен анализ? Знаем, че символът на изходната азбука е символът на входната азбука, добавен към символа на входната азбука, разделени с определен брой позиции. Ако погледнете естествените текстове, можете да видите, че двойки букви на разстояние k също се подчиняват на някои честотни модели.
Повече опций? Вариантът, използван на практика беше следният - ясно е, че докладите обикновено започват с "Ваше Величество", което е доста дълго.
Така че, когато дължината на ключа е равна на дължината на текста, това е добре, но не е достатъчно. Все пак трябва да е произволно.
Ако ключът е случаен, дължината на ключа е равна на дължината на шифрования текст и го прилагаме в режим на поточно предаване, тогава ще се получи добър шифър или не? Защо такъв шифър може да е лош?
[редактиране] Пермутационен шифър
Ние вземаме многострадалния текст и го изписваме в колони
Чупи се много просто - просто познайте дължината.
Как можете да усложните системата?
Ключова смяна.
Сега обикновеното предположение вече няма да ни помогне.
Тук е важно да се отбележи, че всички съвременни симетрични шифри са комбинации от замествания и пермутации.
Почти всички съвременни блокови шифри са многокръгли.
Шифърът се състои от някаква проста функция, която се прилага няколко пъти. Всяко приложение се нарича кръг.
Всяка такава функция може да бъде доста примитивна, състояща се от няколко замествания и пермутации, но тъй като е проектиранатака че кръговете да не се анулират един друг, тогава изходът е добър шифър.
Пример за такъв шифър би бил DES.
[редактиране] DES
Разработено от IBM. NIST, след това ANSI, обяви конкурс за създаване на шифър за използване от търговски организации.
Шифърът е изпратен за анализ в Агенцията за национална сигурност, която прави няколко препоръки, които са взети предвид и стандартът е приет.
Препоръките бяха да се намали ефективната дължина на ключа и вероятно (не е точно известно) s-кутиите бяха заменени с препоръчаните от NSA. Шифърът DES е мрежа на Feistel, виждате го на слайда.
Каква е ползата от мрежа на Feistel в тази форма? Първо, такъв дизайн на шифъра ви позволява да не се притеснявате за това как е подредена кръглата функция F. Тя не трябва да е симетрична, ние винаги я изчисляваме само в една посока, защото, за да декриптирате кръга, е достатъчно да го повторите в другата посока. За да промените шифъра, е достатъчно да промените кръглата функция и това беше използвано, например, в Blowfish.
DES кръгла функция, на слайда.
s-box е справочна таблица за 6-битови вектори.
s-box въвежда нелинейност, заместването се извършва по такъв начин, че да гарантира тази нелинейност. Дизайнът на s-box е ключът към силата на този шифър. Имаше много слухове около избора на s-box.
За да разберете c-кутиите, ще има втора практическа задача.
В реални рундове 16.
Ще бъде създадена уеб услуга, която ще криптира с един кръг на DES. Трябва да възстановите ключа.
Първа задача от седмицата за 4, втора задача от седмици за 6, започвайки от днес.
[редактиране] Диференциален криптоанализ
Изследване на изхода на функция за криптиране, когато входът е умишлено променен.
INВ този конкретен случай би било разумно да се види, че ако подадете нулев вектор като вход, тогава след добавяне по модул две с ключа rhine, ще получите ключа rhine и ще бъде извършена размяна на битове. Ще видите кръглия ключ почти непроменен. След това можете да промените един входен бит и да видите как се променя кръглият ключ. В идеалния случай половината от битовете трябва да се променят. Но ако погледнете как е подредена тази схема, ще видите, че половината от битовете няма да се променят, тъй като към всеки шест бита се прилага отделна c-кутия, несвързана с останалите. Функцията за пермутация е лесно обратима и точното значение на функцията за пермутация е в wikipedia. И дори ще ви изпратим източника на функцията за криптиране. Имате способността да генерирате произволен брой източници, вашата задача е да възстановите ключа.
s-box е фиксиран елемент?
Да, това е част от стандарта.
Фактът, че първо разширяваме блока в процеса и след това го стесняваме, това добра практика ли е?
Това е доста често срещано явление. Това тук осигурява по-високо смесване на въведения текст. От времето на desa той стана доста популярен.