Volker.haas

Предстои допълнително редактиране...

Въведение в криптографията

Криптографията(от гръцката дума криптос – скрит и графо - пиша) се използва още от древността, но и намира огромно приложение в областта на компютърните науки в наше време. Мрежовата сигурност, компресирането, интернет достъпа, заключването на персоналните компютри и криптирането на секретни съобщения са немислими без тази наука. И все пак, основната функция на криптографията си остава скриване на значението на съобщения, както и в някои случаи скриване на самите съобщения (стеганография). Този процес се нарича криптиране, а обратната дейност се нариче декриптиране. Следващият важен термин, с който трябва да се запознаем, е криптоанализът (от гръцки криптос – скрит и анализ – развързвам, разплитам), казано по-друг начин - „разбиване” на кодове. Криптоанализът се занимава с декриптирането на съобщение, без знание за секретната информация (ключ), необходима за това. Но при тази техника се избягват „атаки”, които не са пряко насочени към слабостите в шифъра. Повече внимание на криптоанализа ще обърнем в VI глава.

Разбира се има и други методи за разбиване на даден шифър, които нямат общо с криптографията, и все пак се вземат в предвид при съставяне на криптиращите алгоритми, като подкупване (на хора, имащи ключа), измъчване, промъкване в мястото, където е държана информация за ключа и изобщо методи, на които няма да обърнем специално внимание в настоящият проект. Друг метод за разбиване на даден шифър, без знание на ключа е груба-сила. За този метод обикновено е нужен огромен изчислителен ресурс, защото се състои в изчерпване на различните възможности за ключа. Следващите термини, с които трябва да се запознаем са plaintext и ciphertext, които при криптиране са съответно вход и изход.

Друг изключително важен термин е шифър. Той представлява чифт алгоритми - един за криптирането и един за декриптирането. Ключ е тайният параметър (известен само на кореспондиращите страни), който се използва в шифъра. Терминът кодиране, много често бъркано с криптиране, код в криптографията има точно определено значение – шифър, при който всяка дума, или фраза, се заменя с кодова дума, или фраза, обикновено според книга с кодове. Например - „кучето излезе на разходка” значи „агентите следят целта”. Но кодирането вече не се използва в сериозната криптография, тъй като вече има много по-сигурни методи за криптиране. Един много важен шифър е така нареченият one-time-pad. Неговата идея е, че на всеки символ от шифър-текста има съпоставен ключ, и по този начин, чрез метода груба-сила, при криптирането на пет-буквена дума на английски език, ще се получат всички комбинации от 5 букви, измежду тях и много смислени. По този начин е трудно да се разбере кое всъщност е криптираното съобщение.

Развитие на криптографията

Минало

Криптографията е наука, използвана още от древността, поради широкото й приложение. Воините, неизменна част от човешката история, винаги са се нуждаели от нея. Кореспонденцията между висшестоящи и полеви командири, както и информацията получавана от и изпращана до шпионите имат нужда от сигурно криптиране, в противен случай всичко би могло да стигне до врага, и така войната да бъде изгубена. Ярък пример за това е методът, използван от спартанската армия, който е много лесен. Вземат се кожена лента и пръчка, около която се навива кожата, и тогава се написва съобщението (заповедта). След развиване на лентата, съобщението е неразчетимо, освен ако не се увие около пръчка със същия, или поне много близък диаметър. Разбира се, това е прост разместващ шифър, и не е трудно неговото разбиване, но макар и ненадежден, е достатъчен по-времето на Спарта. Около 500-600 години преди новата ера, еврейски учени измислят прост азбучен заместващ шифър, в който всяка буква се замества с друга, няколко позиции назад или напред в азбуката. Например „к” става „л”, „о” – „п”, „л” – „м” и „а” – „б”, така „кола” се криптира като „лпмб”. По късно, Юлий Цезар използва този шифър за да кореспондира с генералите си. Също така криптографията е препоръчана в Кама-Сутра, индийското изкуство на любовта, като начин за комуникация между любовници, без да бъдат разкрити. Следващата стъпка в развитието на криптографията е изобретяването на честотния анализ през Средновековието, или по-точно през 1000 година. Честотният анализ е нововъведение в криптоанализа, и един изключително добър начин за разбиване на азбучни шифри. Използва честотата, с която се среща дадена буква или букви в езика, на който е написано криптираното съобщение. След това, според честотата с която се среща даден символ от шифър-текста най-често, се замества буква от азбуката, и по този начин се декриптира съобщението (по-подробно разяснение има по-надолу в проекта). Тогава всички шифри станали уязвими и несигурни, чак до измислянето на многоазбучният шифър, от Леоне Батиста Алберти, около 1465 година. Леоне Алберти е италиански поет, художник, лингвист, философ, криптограф, музикант, архитект, по-кратко казано – polymath. Многоазбучният шифър обикновено ползва някакъв ключ, по-просто може да се опише като последователно прилагане на различни азбучни шифри (цезарови). По-късно, тези нови криптографски подходи се използват в Заговора Бабингтан , както и в други подобни. В други части на света, Япония например, криптографията не е била използвана до 1510 година, а някакви по-напреднали техники за криптиране са използвани чак след отварянето на страната към Европа и САЩ – а именно 1860 година. Макар и с доста дълга история, криптографията няма сериозен напредък до 19 век. Тогава английският математик Чарлз Бабидж разработва тест, с който да разбива Шифърът на Вигенере, прост многоазбучен шифър, който може да открие дължината на ключа, и тогава разглежда шифъра като сбор на обикновени Цезарови Шифри. Малко по-късно, Августе Керковс, холандски лингвист и криптограф, написва шест принципа за създаването на криптиращи алгоритми:

1. „Системата трябва да бъде, ако не теоретично, то поне практически неразбиваема.”
2. „Системата не трябва да затруднява потребителя, и не трябва да изисква твърде голяма сигурност”
3. „Ключът трябва да може да се запомни без бележки и да се сменя лесно.”
4. „Шифрованият текст трябва да може да бъде изпращан с телеграф.”
5. „Апаратурата трябва да бъде лесно преносима, от сам-човек.”
6. „Системата трябва да е проста, да не изисква някакви знания или дълъг списък с правила, или въобще много мислене.”

От тези правила, най-известно е второто, под името Принцип на Керковс. Друг изявен криптограф от това време е Едгар Алан По, който написва есе, в което описва методи за разбиване на шифри, оказали се полезни за дешифриране на немските кодове през Първата Световна война.

Криптографията прави своя огромен скок по време на Втората Световна война, когато се произвеждат много електро-механични криптиращи машини. Същевременно се наблюдава изумителен напредък в разбиването на шифри. Всичко това е засекретено, но след изтичането на 50 годишният период при Великобритания, и отварянето на архивите на САЩ, информацията, свързана с криптографията през Втората световна война, става достъпна. Тогава немската армия използва електро-механичната роторна машина Енигма, която претърпява няколко подобрения по-време на войната.

През 1932 година, с помощта на доставените сведения от капитан Густав Бертранд, от френското разузнаване, полският криптограф Мариан Райевски, от Шифър Бюро, успява да направи копие на немската Енигма. Това е може би най-големият криптографски пробив в историята. Той и неговите колеги – Йежъ Ружетски и Хенрйък Зйъгалски – започват да разчитат немските съобщения, като същевременно са в крачка с промените в Енигма. Когато по време на войната, Полша става в неизгодна позиция, Генералният Щаб заповядва британските и френските разузнавателни служби да бъдат посветени в тайната, за разчитане съобщенията на немската армия, както и става. От там нататък с декриптирането се заема основно Блетчли Парк, Англия, където работили истински светила на тогавашната криптография, като Гордън Уелчмен и разбира се, Алан Търнинг, считан за бащата на съвременната компютърна наука. Войната в криптографията е не по-малко ожесточена от тази на бойните полета. Много средства и сили се хвърлят в тази насока, и доста битки са решени благодарение на това.

Другите страни, участващи във войната, също ползват електро-механични устройства за криптиране. Съюзниците притежавали британски TypeX и американския SIGABA. Също така, британските Special Operations Executive (SOE) агенти, използват наизустени поеми за ключ към шифри, но по-късно преминават към one-time-pad. Германия също прави няколко механични опита за one-time-pad, които са наречени от съюзническите войски Fish ciphers.

Настояще

Началото на модерната криптография е положено от Клауд Елуоод Шанън, когато през 1949 година издава книгата си “Communication Theory of Secrecy Systems”, и малко по късно книгата “Mathematical Theory of Communication”, заедно със Уорън Уейвър. След това криптографията преминава в секретните държавни организации, и няма почти никакви публикувани открития до 1970 година.

Седемдесетте години бележат излизането на криптографията от сянката на правителствените организации. Първо е публикуван проекта за DES(Data Encryption Standard) във Федералният Регистър на САЩ, на 17 март 1975 година. Проектът DES е предложен от IBM, по покана на Националното Бюро за Стандартизация (NBS, в момента NIST), в опит за осигуряване на конфиденциалност на комуникациите за бизнеса и финансовите организации, като банките например. NSA(National Security Agency) става първата в света правителствена организация, която „дава своята благословия” за публичен стандарт за криптиране.

DES блоков шифър, който ползва 64 битов ключ, но тъй като 8 бита са използвани за проверка, и реално ключът е 56 битов. Има хипотези, че NSA са оставили задна вратичка чрез която бързо могат да разбиват съобщения на DES.

1976 е публикувана статията „New Directions in Cryptography”(„Нови насоки в криптографията”) от Уитфилд Дифи и Мартин Хелман, една своеобразна революция в развитието на науката. В статията се обсъждат начини за крипто-системи, в които да се осигури разговорът между всеки двама потребители в системата. Тази статия предлага начин, чрез който ключът може да се предава през несигурна мрежа. Това става по-следният начин:

Имаме двама приятели от интернет, Петър и Иван, които искат да си пращат лични съобщения, като за целта ги криптират. И статията на Дифи и Хелмен дава възможност, те да уговорят своя ключ по несигурна мрежа. За целта, се избират едно просто число – p, и една основа q, които биват изпратени през несигурната мрежа. 1) Петър избира числото a, и пресмята qa (mod p) = A, и изпраща А на Иван. 2) Иван от своя страна, избира числото b, пресмята qb (mod p) = B, и изпраща числото B. 3) Петър вече има числото B, за това пресмята k1 = Ba, a Иван пресмята k2 = Ab. Тъй като qab = qba, то k1 = k2 = k. И уговореният ключ е k.

Друга интересна тема, засегната в статията на Дифи и Хелман е, така наречената еднопосочна функция. Така наречените хеш-функции, се използват за лесно и бързо криптиране на дадена информация, но почти, или съвсем, невъзможното й декриптиране. При authentication, паролата на потребителят се криптира посредством дадена хеш-функция, и се получава резултат – хеш-адрес, който се записва в паметта. Когато потребителят иска да ползва потребителското си име, той въвежда парола, тя преминава през същата хеш-функция и полученият резултат се сравнява със запазеният вече в паметта. По този начин се избягва разчитането на запазената парола, от трето, неоторизирано за това лице.

С тези разработки, двамата учени полагат основите на ново поколение от алгоритми – асиметрични. До тогава, всички алгоритми са симетрични – има единствен ключ, който се ползва за криптиране и декриптиране. „New Directions in Cryptography” представя начин, по който може да се използва един ключ за криптиране, и един за декриптиране, така наречената private-public key(публичен-личен ключ) система. Тя ползва два математически свързани ключа, един всеизвестен и един таен. За пример отново ще вземем Петър и Иван. Петър има публичен ключ Ppu и личен Ppr , а Иван има съответно Ipu и Ipr . Тъй като публичните ключове са известни, Петър криптира съобщението си с Ipu и с Ppr, а Иван декриптира полученото съобщение с Ppu и с Ipr. По този начин, Иван може да е сигурен, че съобщението е изпратено от някой, знаещ личния ключ на Петър, и че ако някой се опита да го разчете, ще трябва да знае неговият личен ключ. И тъй като няма обмяна на ключове през мрежата, асиметричните алгоритми могат да се считат за по-сигурни.

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

През 1978 година, Ронълд Ривест, Ади Шамир и Лен Адлеман, от MIT (Massachusetts Institute of Technology), съставят алгоритъма RSA(Rivest, Shamir and Adleman). През 1983 година, DES е потвърден като сигурен. RSA е патентован от MIT. През 1986 година, HBO започва използването на DES за криптиране на сигнала. На 22 януари 1988 година, DES е потвърден за втори път в FIPS PUB 46-1 (Federal Information Processing Standard PUBlication).

През 1991 година, Филип Зимерман създава и публикува свободният софтуер за криптиране PGP(Pretty Good Privacy), което е последвано от тежка борба с Министерство на Правосъдието на САЩ, заради нарушаване ограничението за експорта на криптиращи алгоритми. Тогава САЩ има идеята, да изискват backdoors във всички криптографски решения. 1992 година, Бихам и Шамир публикуват диференциален криптоанализ, първата атака, по бърза от груба-сила. С този криптоанализ, проверките за разбиване на DES са редуцирани до 247 , но това също се оказва недостатъчно.

На 30 декември, 1993 година, DES е потвърден за трети път, като FIPS PUB 46-2. През 1994 година, за първи път се прави криптоанализ с линеен криптоанализ. И в съдбоносният юни, 1997 година, съобщение, криптирано с DES, е разбито. Още следващата година, 1998, EFF(Electronic Frontier Foundation) създават машината Deep Cracker(Дълбоко Разбиване), която успява да разбие, с груба-сила криптирано с DES съобщение за 56 часа. До тогава е смятано, че за да се построи машина, която да разбие DES ще струва прекалено скъпо, а дори да се направи, едва ли ще разбива шифъра достатъчно бързо. За изпробването на всички комбинации са нужни 7.21 × 1016 проверки. Но машината на EFF струва само 250 хиляди долара, и съдържа над 1 800 чипа.

Януари 1999 година, Deep Crack заедно с distributed.net(още информация в следващата глава) успяват да разбият DES за 22 часа и 15 минути.

На 25 октомври, същата година, DES потвърден за четвърти път във FIPS PUB 46-3, но този път е препоръчано ползването на TDES(Triple DES).

TDES представлява три последователни използвания на алгоритъма, което затруднява разбиването му с груба-сила. TDES(k1, k2, k3, x) = DES(k1, DES(k2, DES(k3, x))), където ki е ключ, а x е даден ясен-текст.

На 26 ноември, 2001 година, алгоритъма AES(Advanced Encryption Standard) е публикуван в FIPS 197. Следващата година AES влиза в действие, като стандарт. На 22 юли 2004 година, във Федералния Регистър е предложено отменянето на FIPS PUB 46. На 19 май 2005 година, NIST(National Institute of Standards and Technology) отменя FIPS PUB 46.

Друго, на което ще обърнем внимание са хеш-функциите. Основната цел на тези функции е, да предоставят изход хеш-адрес, чрез които да няма начин да се стигне до входа. За това в труда на Дифи и Хелман са наречени еднопосочни функции. За хеш-функциите е много важно да няма колизии – това явление се появява при препълване на функцията, или по-просто казано – при два различни входа, да се получава един и същ изход – хеш-адрес. Друго важно за хеш-функциите е и свойството, при съвсем малка промяна във входа, да има голяма промяна в изхода. Сега ще разгледаме някой от по-известните хеш-функции.

Една примерна хеш-функция за символен низ, ще наречем h1. Низът “Come here” ще се хешира по следния начин: 67+111+109+101+32+104+101+114+101 = = 840. Лесно се забелязва, че при този метод ще се получат много колизии, така че не е добър вариант.

Друга примерна функция е тази, при която хеш-адресът е остатъкът при деление на входа с някакво число, капацитет на хеш таблицата. Капацитет на хеш-функцията ще наричаме броя на елементите, при които е възможно да няма колизия. Според принципа на Дерихле, когато имаме n чекмеджета, и в тях разпределим (n+1) предмета, то със сигурност ще има чекмедже, с два или повече предмета. Така и когато има препълване, т.е. капацитетът е надхвърлен, задължително настъпва колизия. Тази функция h2, като използваме числото 13, ще даде следните резултати: Вход : 171; Изход : 2; Но в следващият пример: Вход : 158; Изход : 2; Разбира се, колкото по-голям е капацитетът, толкова по-малко ще са колизиите. Може да забележим, че при малка промяна във входа, например „159”, промяната в изхода също ще е малка –„3”, следователно тази функция също не е добра.

Следващата хеш-функция, която ще разгледаме, h3, е така нареченото мултипликативно хеширане. То има вида , където n е капацитет, а е константа, като 0<а<1, {k} e дробната част на k и [k] e цялата част на k. Макар константата а да няма задължителна стойност, Кунт препоръчва да се ползва Сребърното сечение(реципрочно на златното - φ, или φ – 1).

$\ a={\frac {1-{\sqrt {5}}}{2}}\approx 0,6180339887...$

Хеш-функциите са много и най-различни, според това какво трябва да се хешира. Някои са по прости и некачествени, други прекалено сложни. Но има някои, които се ползват в наше време, и са с доказано качество.

MD2(Message Digest Algorithm 2) например, е хеш-функция създадена 1989 година от Роналд Ривест. Следват я MD4 и MD5, понеже тя самата е оптимизирана за 8 битови компютри. Дори MD2 е пример за добра хеш-функция. Но през 2004 година, се оказва че е уязвима от preimage attack, и би могло да бъде разбита(да се намери ключа) със 2104 проверки. А атаката се състои в това, при даден хеш h да се пробват различни съобщения, докато се получи h. След този случай, MD2 се счита за несигурна еднопосочна функция, и все пак още е използвана на места.

През 1990 година, Ривест създава MD4, който е подобрение на старата хеш-функция. Следващата година излиза и MD5. Но след 2004 година, за всичките алгоритми от серията MD, се счита че сигурността им е много спорна.

На хоризонта идва друга хеш-функция – SHA. Алгоритъма е създаден от NSA, и през 1993 година е публикуван от NIST в FIPS PUB 180, като Secure Hash Algorithm След няколко различни промени, в момента съществуват следните разновидности на SHA: SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 и разбира се, първият известен като SHA-0. Ето пример, как действа SHA-256:

SHA256("abc") = ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad SHA256("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") = 248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1

И ето как, една добра хеш-функция отразява малка промяна във входа:

SHA256("The quick brown fox jumps over the lazy dog") = d7a8fbb3 07d78094 69ca9abc b0082e4f 8d5651e4 6d3cdb76 2d02d0bf 37c9e592 SHA256("The quick brown fox jumps over the lazy cog") = e4c4d8f3 bf76b692 de791a17 3e053211 50f7a345 b46484fe 427f6acc 7ecc81be

Приложение

Както вече видяхме в проекта, криптографията има много приложения. В момента, в България постепенно навлиза Интернет Банкирането – начин на управление на сметките чрез персоналния компютър. И както виждате, изключително важно е да се осигури много добра идентификация. Банките ползват няколко нива на защита. Първо, по интернет клиентът на банката изпраща своята заявка, регистрира се с потребителско име и парола. След като въвежда данните си, в някакъв срок в банката му се прави сертификат и му се изпраща пин-код по електронната поща (това е несигурен начин за пращане на информация, така че може да се счита за публична). Тогава, клиентът влиза в сайта на банката и проверява статуса си. Ако му е издаден сертификат, той получава парола, с която да го инсталира, след което трябва да отиде и лично да го вземе от посоченият от него клон, срещу представен документ за самоличност. Сертификатът трябва да бъде инсталиран на компютъра, или на няколко, от които клиентът иска да ползва услугата. За инсталацията се ползва дадената парола. След завършване на всички процедури, клиентът може да ползва интернет банкиране, като въведе своето потребителско име и парола, които е задал при регистрацията. Тук основната защита, е предоставена от SSL Certificate. Той осигурява много добра идентификация на клиента. И понеже се прави персонално за него, дава се лично, е много добра и сигурна защита. SSL Certificate използва асиметричен шифър(RSA, Diffie-Hellman, DSA или Fortezza) за уговорка, така наречената master secret, симетричен шифър(RC2, RC4, IDEA, DES, Triple DES или AES) за прехвърлянето на данни и хеш-функция(MD2, MD4, MD5 или SHA). Следващото ниво на защита е паролата, който клиентът въвежда при регистрация. Информацията, съхранявана в сървъра, като паролите например, са хеширани. Самата банка не знае личния ключ на клиента, за това е важно той да не го губи или забравя. Въпреки всичко това е необходимо, за да не може неоторизирани лица да се възползват от информацията на сървъра.

Криптоанализ

Както вече споменахме във втора глава, криптоанализът се занимава с внимателно проучване на шифрите, с цел откриване на слабости в тях. Настоящата глава разглежда различните методи, както и криптоанализ на някои от по известните алгоритми.

Криптоаналитични атаки

ciphertext-only attack

В криптоанализа много често се използват ciphertext-only attack. Състои се в това, че опитващият се да разчете съобщението, разполага само с шифър-текстове(възможно е да следи кореспонденция). Ранните шифри са уязвими на тази атака(с помощта на честотен анализ), но по-модерните методи, като Енигма например, правят този вид атака много труден и неефикасен (криптоанализ на Енигма има по-надолу в проекта). Но методи като груба-сила, при положение че ключът е кратък, все още се използват. Например DES, със своя 56 битов ключ е уязвим на такава атака. И тъй като повечето потребители, не използват пълния потенциал на системите си за сигурност(дори при кратък 56 битов ключ, потребителят може да ползва още по-кратък), методът груба-сила си остава ефективен в повечето случаи.

known-plaintext attack

known-plaintext attack (KPA) е метод, при който разбиващият има информация за един ясен-текст и за неговата криптирана версия – шифър-текста. По този начин, той може да получи тайна информация, най-често ключа, за да декриптира и останалите съобщения.

chosen-plaintext attack

chosen-plaintext attack от своя страна, е метод, лесно приложим за сегашните системи. Разбиващият шифъра избира някакъв ясен-текст по свое желание, да го криптира и след това да се опитва да получи някаква секретна информация от това. Атаката е приложима за модерната криптология, защото широко използваните асиметрични шифри, имат публичен ключ за криптиране, и разбиващият шифъра лесно може да криптира съобщение, след което да се опита да разбере личния ключ.

adaptive-chosen-ciphertext attack

adaptive-chosen-ciphertext attack е атака, при която нарушителят изпраща определен брой от пробни шифър-текстове към декриптиращо устройство, като използва получената информация от декриптирането. Този тип атака е считан за чисто теоретичен до 1998 година, когато Даниел Блейченблечър от Bell Labs демонстрира атака срещу система, използваща RSA съвместно с PKCS #1 v1 декриптираща фунция, включително и SSL протокол, използван от хиляди потребители по това време. Атаката му се възползва от слабости в PKCS #1 за да разкрие съдържанието на криптирано с RSA съобщение. За да направи това, той изпраща няколко хиляди пробни шифър-текстове до декриптиращото устройство(интернет сървър, ползващ SSL). Това показва, че SSL ключът може да бъде разбит за разумно дълго време - ден, дори по-малко.

birthday attack

birthday attack е атака за разбиване на блокови шифри и хеш-функции, при който се ползва така наречения birthday парадокс. Всъщност, това не е точно парадокс, проблемът е коренно се различава от човешкото предчувствие, иначе се основава изцяло на математически изчисления на вероятност. Според този „парадокс”, измежду 23-ма произволно избрани хора, шансът да има двама с една и съща рожденна дата е 50%, а също така, ако хората са над 60, шансът е по-голям от 99%. Ето и самият „парадокс”:

birthday парадокс Имаме n човека, и разглеждаме само невисокосните години. Да допуснем, че измежду тях няма двама, с една и съща рожденна дата. Нека означим вероятността за това събитие с p(n). Ако n>365, от Принципа на Дерихле следва, че p(n) = 0. Разглеждаме случая, когато n . Тогава:

${\bar {p}}(n)=1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1-{\frac {n-1}{365}}\right)={365\cdot 364\cdots (365-n+1) \over 365^{n}}={365! \over 365^{n}(365-n)!},$

понеже вторият човек не може да е със същият рожден ден, като първият (364/365), вторият не може да има същият, като първите двама (363/365) и т.н. birthday attack ползва този принцип, като във формулата вместо n – броят на хората, ще пишем H – броят на уникалните изходи, вместо броя на дните в годината ще пишем необходимите проверки, за да се намери колизия.

$p(n)=1-{\bar {p}}(n)\approx 1-e^{-(n(n-1))/2\cdot H}\approx 1-e^{-n^{2}/{2\cdot H}},$

Като обърнем изразяването става:

$n(p)\approx {\sqrt {2\cdot H\cdot \ln \left({1 \over 1-p}\right)}},$

man-in-the-middle attack (MITM)

Тази атака, може да се приложи за система публичен-личен ключ. Криптоаналитикът, трябва да може да спира съобщенията на двете страни, да ги променя. Отново за примера ще използваме Иван и Петър, но този път Стоян ще е криптоаналитикът.

Иван иска да разговаря с Петър, за това му трябва неговия публичен ключ. Петър го изпраща, но Стоян засича съобщението, и се сдобива с публичния ключ на Петър, но освен това го спира, преди да е стигнало до Иван. След което Стоян изпраща на Иван публичен ключ, за който знае личния. Иван си мисли, че е получил ключът на Петър, така че го използва заедно със своя личен ключ и изпраща криптираното съобщение. Стоян отново прихваща съобщението, декриптира го със своя личен ключ, и го запазва някъде, след което криптира отново, използвайки публичния ключ на Петър и своя личен. Този пример илюстрира как работи методът, и начинът за предпазване от него е индентификация, която да гарантира, че ключовете които получава едната страна (Иван), наистина са от другата (Петър).

Методи за Криптоанализ

Честотен анализ

Вероятно първият метод, е така наречения честотен анализ. Той използва статистически данни за езика, на криптираното съобщение. За пример ще вземем английския език. Разполагаме със следното съобщение:

yxszssyqraqkydzdggdutysqaxyqryxszdgrqracgqrayxszdrsoquqwwcgqrayxskyden

В съобщението най-често срещаните букви са „y” и „q”, по 9 пъти, но забелязваме, че най-често срещаното съчетание от три букви е „yxs”, което се среща общо 4 пъти. В английският език, това е “the”, значи „y” е “t”, „x” е “h” и „s” е “e”. Така получаваме следното:

THEzEETqraqkTdzdggdutTEqaHTqrTHEzdgrqracgqraTHEzdrEoquqwwcgqraTHEkTden

Понеже вече имаме първите две най-срещани букви в английския език, а “q” се среща цели 9 пъти. Следователно, вероятно е „а”.

THEzEETАraqkTdzdggdutTEqaHTqrTHEzdgrqracgqraTHEzdrEoquqwwcgqraTHEkTden

Следващата най-често срещана буква в съобщението е “r”, а в английския език е „O” и т.н. По този начин постепенно се разкрива текстът. Разбира се, колкото е по-дълъг текстът, толкова вероятността за грешка е по-малка. Например, в сегашното съобщение, „e” се среща по-рядко от “t”, с предположението че “q” е „а” се оказва грешно, така че в един момент ще трябва да се върнем назад и да опитаме отново. Всъщност, съобщението е:

„Themeetingistomorrowateightinthemorningbringthemoneyiwillbringthestock”

Статистическите данни за даден език са доста. За английският например, има данни за най-често срещано съчетание от две букви, от три, за начална, крайна буква и т.н.

Метод на Бабидж

Метод на Бабидж, по-известен като Метод на Казиски, е един добър начин, за разбиване на многоазбучни шифри. Състои се в търсенето на еднакви поредици от символи(3 букви или по-дълги), с цел намиране дължината на ключа. Ето няколко стъпки, чрез които методът се прилага:

• Криптоаналитикът намира всички повтарящи се поредици от символи, като записва през какъв интервал са повторенията. На пример: trskgsxvrnmtrsp

Тук „trs” се повтаря през 10 символа. Проверяваме интервала между повторенията за колкото се може повече групи в текста, така ще можем да сме по-сигурни.

• Внимателно оглеждаме интервалите, ако някой преобладава, то вероятно това е дължината на ключа, а ако не, то е кратно на дължината на ключа. От горния пример, нека по-нататък в съобщението имаме повторение през 15 символа. Така имаме 10 и 15, следователно ключът трябва да е делител на 10 и на 15, значи е 5. При по-дълъг текст, методът е по-точен, понеже повторения могат да станат и случайно.
• След като знаем дължината на ключа, която е l, разглеждаме съобщението като l съобщения, криптирани с прост Цезаров Шифър.
• След като е разкриптирал съобщението, аналитикът може да използва получените ясен-текст и шифър-текст за да намери ключа, и да разбива и останалите съобщения от кореспонденцията, ако се криптират със същия ключ.

Differential cryptanalysis

Differential cryptanalysis е метод, при който се следи какви отражения върху изхода дават различни промени във входа и е най-вече е използван за блокови шифри и хеш-функции. По принцип, се изпозва при chosen-plaintext attack, макар да е приложима и при known-plaintext attack (KPA).

Линейнеен анализ

Линейнеен анализ е метод, подобен на Differential cryptanalysis, но се състои в това, за даден алгоритъм да се намери приблизително линейно изразяване. При този метод, проверките за DES се свеждат до 243, за разлика то Differential cryptanalysis, където са 247.

mod n cryptanalysis

mod n cryptanalysis е метод, ефективен за блокови шифри, позлващи ротация на битове за своята сигурност. Ротацията ще обясним със пример:

Нека имаме променлива x. Нека y = x<<<1, където с „<<<” означаваме ротацията наляво, в случая един бит. Тогава, y = 2x. И аналогично, ако y = x>>>1, то y = 2-1x.

Груба-сила

Методът груба-сила се състои в това, да се изпробват всички възможности за ключ. Всъщност, „разбиването” на даден шифър се състои в това, да се намери начин, по-бърз от груба-сила. Например, ако един шифър има ключ, с 250 възможности, груба сила очаква разбиването да стане с 249 проверки.

Криптоанализ на някои алгоритми

RSA

RSA е асиметричен алгоритъм за криптиране, и в момента е считан за един от най-добрите. Сигурността на RSA се гради върху два математически проблема – разлагане на прости множители и Проблема RSA. Алгоритъмът е следният:

1. Избират се две големи прости числа p и q.
2. Изчислява се n = pq.
3. Изчислява се функцията $\phi (n)=(p-1)(q-1)\,$.
4. Избира се естествено число e, такова че е и да са взаимно прости.
5. Избира се естествено число d, такова че да удовлетворява условието $de\equiv 1{\pmod {\phi (n)}}\,$.

Публичният ключ е (n, e), a личният е (n, d). Криптирането става по-следния начин: Съобщението M, по някакъв уговорен начин се превръща в число, m, и се изчислява:

c = me mod n

Тогава шифър-текстът c се изпраща.

Декриптирането става по следният начин:

m = cd mod n

Алгоритъма работи, защото $c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}$. Имаме

$ed\equiv 1{\pmod {p-1}}\,$

и

$ed\equiv 1{\pmod {q-1}}\,$

Тогава от малката теорема на Ферма следва:

$m^{ed}\equiv m{\pmod {p}}$

и

$m^{ed}\equiv m{\pmod {q}}$

Тъй като p и q са различни прости числа, от КТО (Китайска Теорема за Остатъците) следва:

$m^{ed}\equiv m{\pmod {pq}}$, което е еквивалентно на

$c^{d}\equiv m{\pmod {n}}$

Проблемът RSA се състои в това, по дадени публичен ключ и шифър-текст, да се намери ясния-текст. Доказано е от Д. Бонех, че при малки стойности на е, сложността на Проблема RSA е по-малка от тази на разлагането на прости множители. Декриптирането на даден шифър-текст, без знание за ключа, може да стане и с разлагане на n, или чрез друг метод, включващ пряко самия алгоритъм, и е напълно възможно, сложността на двата различни подхода да не са еквивалентни. Въпреки това, все още не е доказано, за по-големи стойности на e, че Проблема RSA е по-лесен, или по-труден от разлагането на n. Може да се направи опит, за откриване на d, като се използва discrete logarithm, и тогава е възможно да се намери d по-бързо от колкото при разлагане на n. Тъй като операцията търсене, е по-бърза от изчисленията, би могло да се създаде база данни, която да се състои в произведения на различни двойки прости числа, и разбира се самите прости числа. Така, когато разполагаме с публичен ключ (n, e) бихме могли да осъществим търсене на n в базата данни, и при намирането ще разполагаме с неговите делители. Създаването на такава база ще отнеме неимоверно много време, ще е има огромен размер, и все пак ще съкрати времето за разлагане на n.

DES

DES е блоков шифър, и съществуват няколко атаки, които могат да го разбият по-бързо от груба-сила (вече споменахме, че грубата-сила също е възможен подход). Това са Differential cryptanalysis и Линеен анализ, които свеждат сложността съответно до 247 chosen plaintexts и 243 known plaintexts.