Силни шифри
Заместващи шифри
Конвенционалните шифри от детективските романи често са подредени по следния начин: всяка буква от съобщението се заменя с определена икона или друга буква. Такива шифри са много ненадеждни и ето защо. Буквите в текстове на български (и изобщо на всеки език) се срещат неравномерно. Например буквата "О" в българските текстове е най-често срещаната от всички останали букви, а буквата "Ъ" е най-рядко срещаната. Всяка буква има своя приблизителна честота на срещане в текста (виж таблицата в полето вдясно).
Комбинациите от букви също се срещат неравномерно (например "ь" изобщо не се среща). Разбира се, всички тези честоти зависят от конкретния текст - например в биологична статия за земните бръмбари буквата "g" ясно ще се появи по-често от обикновено. Но таблицата по-долу е доста подходяща като ориентир.
Така че описаният метод на криптиране не променя честотите - просто сега с подобна честота ще се появи не самата буква, а иконата, която я замества. Чрез изчисляване на честотата на появяване на всяка икона в криптирането и сравняване на получените данни с честотната таблица, можем да направим предположения коя буква на коя икона отговаря. След това се опитваме да заменим иконите една по една с букви, като проверяваме предположенията си, коригираме ги и създаваме нови и постепенно дешифрираме текста. Ако не е твърде кратък, най-вероятно ще го дешифрираме напълно (въпреки че това може да не е лесна задача). Между другото, интервалът, разделящ думите, е много по-често срещан от всяка буква. Следователно, ако интервалът се използва при криптиране и също така е заменен с някаква икона, първо ще го разрешим.
Перфектен шифър
Нека сега опишем шифър, който по принцип не може да бъде дешифриран без да знаем ключа. Свържете всяка буква от българската азбука със собствена последователност от 0 и 1 с дължина 5(петцифрен двоичен код), например: A - 00000, B - 00001, C - 00010 и така нататък (или в някакъв друг ред). Ако буквите E и E са кодирани по същия начин, тогава има достатъчно последователности (има 32 от тях и има 33 букви в азбуката).
Нека заменим всяка буква в текста с нейния двоичен код, получаваме последователност от 0 и 1 (двоичен текст). Това все още не е криптиране - лесно бихме могли да разберем коя буква с коя последователност е заменена (по същия метод, както в случая на замяна на букви с икони).
За да шифроваме, просто добавяме две поредици от нули и единици - двоичния текст на съобщението и ключа: първата цифра с първата, втората с втората и т.н. Но ние добавяме според специални правила:
0 + 0 = 0, 1 + 0 = 1, 0 + 1 = 1, 1 + 1 = 0
(в математиката това се нарича събиране по модул 2).
Получената последователност ще бъде криптираното съобщение. За да го дешифрирате, просто трябва. добавете ключа към него отново! Тогава ние, така да се каже, добавяме ключа към оригиналната последователност два пъти. И според нашите правила, като добавим две еднакви числа, ние не променяме нищо, тоест ще се върнем към оригиналния двоичен текст. Схематично процесът на криптиране и декриптиране може да се опише по следния начин:
текст + ключ = криптиране;
криптиране + ключ = текст + ключ + ключ = текст.
Ясно е, че е невъзможно да се дешифрира съобщение, без да се знае ключа. Сякаш ни е даден сбор от две числа и е невъзможно да възстановим едното от членовете, без да знаем нищо за другото. Имайки под ръка само криптиране, знаем само, че изходният текст може да бъде абсолютно всеки текст с подходяща дължина. Наистина, за всеки такъв текст можете да направите ключ, който ще доведе до абсолютно същото криптиране!
Недостатъкът на описания метод е, че всеки текст изисква нов ключ със същата дължина - ако повтарятеключове, става възможно дешифрирането. Например, можем да опитаме вместо дълъг ключ да използваме ключ от само пет знака, да речем 11010. Разделяме двоичния текст на пет цифри и към всяка пет добавяме 11010. Всъщност просто заместваме всяка петица от цифри с друга фиксирана петица. В този случай дешифрирането на оригиналния текст е толкова лесно, колкото ако просто сме го заменили с двоичен код, без да добавяме никакъв ключ. Използването на дълги ключове, но все пак значително по-къси от текста, също е опасно - има метод за определяне на дължината на ключа и след като се зададе дължината на ключа, може да се приложи честотен анализ.
Следователно е необходимо предварително да се подготви ключ с огромна дължина и само да се посочи, например в началото на криптирането, коя част от ключа се използва. В този случай е много важно ключът да бъде случайна последователност от 0 и 1. Например последователностите 11111111111111111 и 010101010101010 не са произволни. Между другото, измислянето на произволна последователност не е толкова лесно. Дори е трудно (но възможно) да се даде ясна дефиниция кои последователности могат да се считат за случайни.
Малко история и литература
Подобен шифър е използван от Макс Кристиансен-Клаузен, шифровчик на видния офицер от съветското разузнаване Рихард Зорге. Най-често използваните букви от английската азбука s, i, o, e, r, a, t, n бяха заменени с цифри от 0 до 7, а останалите букви - с цифри от 80 до 99 (за да няма объркване, когато числата се изписват подред). Ключът бяха старите издания на Статистическия годишник на Германския райх, с много цифрови данни. Ключът се записва под текста и се добавя, а ако сумата от две цифри надвишава 10, се записва само последната му цифра. Например, вместо 7 + 5, те написаха 2, като изхвърлиха дузина (по математикатова се нарича събиране по модул 10). Оригиналното съобщение беше възстановено чрез "изваждане" на ключа от криптирането. Когато излезе отрицателно число, както, да речем, при изваждане на 5 от 2, беше ясно, че трябва да извадим още 10 от числото, тоест от 12 - така получихме 7.
Шифри с публичен ключ
От 1977 г. започват да се появяват нови шифри, базирани на дълбоките математически идеи, изразени от американските математици Дифи и Хелман две години по-рано. Представете си, че двама бизнесмени искат да си кореспондират, сигурно шифровайки съобщения, но са забравили да се договорят за ключа. Те са в различни държави, цялата им комуникация може да бъде подслушвана от конкуренти. Как да съм тук? Оказва се, че има начини. Ще опишем един от тях, но без подробности, само самия принцип.
Изобретен е метод за криптиране, за който трябва да знаете само произведениетоpqна някои две прости числаpиqи не е необходимо да знаете числатаpиq. Но за да се дешифрира съобщението, е необходимо да има както числотоp, така и числотоq. „Е, какво лошо има в това?“, питате вие. И ето какво. Факт е, че тези прости числа могат да бъдат взети много големи. И тук се сблъскваме с такъв феномен: съвременната компютърна мощност е огромна, но все пак ограничена. Да кажем, че компютърът може да разложи на множители 200-цифрено число за разумно време, но вече не може да разложи на множители 300-цифрени числа (всеки от известните алгоритми ще отнеме много години). Винаги има някаква граница. И за да разберат за едно число, независимо дали е просто или не, компютрите могат много бързо за много по-дълги числа. И така, първият от спътниците може да използва компютър, за да намери произволни две, да речем, 400-цифрени прости числаpиq, да ги умножи и откритоизпратете резултата на втория (и запазете числатаpиqв тайна). След като получи продуктаpq, той ще шифрова съобщението си и ще го изпрати обратно на първия. И първият може лесно да го дешифрира - той знае и двете числаpиq. Но всички видове подслушватели ще трябва да дешифрират продуктаpq, в който има 800 знака - и нито един съвременен компютър не може да се справи с това! Този метод на криптиране се нарича RSA, по първите букви от имената на неговите създатели - Rivest, Shamir и Adleman.
ще успеете ли
Ето текст, който се получава от добре позната замяна на всяка буква с друга. Декодирайте го.
Atokg atsyng tslekytuy tslaueng yi Cholsv, and uimi cholsey umanloti ki eekpv nipeme vmatyfyuem, tsatkzme utochtiyime, zhna ni atyng yimalchiti, andotti atoky dunalakve, mokyy omvki chatado txs, bockvti:
- Piyo d uimam soto in Ukorkayo palatodz, like a dzadatok e svmion, zhna tvzhbo omv kechso e schzng komaron. Цлежекайо ро дуомв аупатпе йолпити, жна уесын в коча д олсьо д чтиив. Esh kisa vsiteng, ekijo ak kepachsi ko schvson zhotadopam, e Ukorkiy palatodi uashlikken kis kem udaf dtiung.
„Ka ko tsamarobg te nz cholso pip-keshvsg vkezhnareng janv dtiung?“
- Wetgkoo, zhom aki oung, s ko machv oh usoting. Ko desebg lido, pip dotepi oh wow? Ko desebg, wife oyo utvrrin e tfse e redankzo? Dosg aki shauiy ashabti tsatudoni! Ko in kiu yikeming oyo uetv! Ueti - doh metam, кодеци sonupam wolsozhpo. Oute aki wimi ko umaron clakepkvng d žolnache Ukorkayo palatodze e dtozhg e wolsii Py aupatpe, on mz e tsasidka oyo ko tsamarom! D sdvsh metysh anufsi kizhekionuy uis Ukorkayo palatodz. Ankoue nvsi sodazhpv, utsvune in schatgbacha pvuni, heron pliukzme ychasime, e, mobpie, daldliyuyuy ashlinka!
U aneme utadimeekpi tsasuiseti Cholswki utsekv atoky, e nan schlauetuy schoring wa duosh kach.