Криптографията: как числата пазят тайните ни
Криптографията:
как числата пазят тайните ни
Всеки път, когато изпращате съобщение, отваряте страница с катинар в браузъра, плащате с карта или говорите по видео връзка, някъде във фонов режим работят няколко красиви математически идеи. От разлагането на големи числа до операциите върху елиптични криви, от еднопосочните функции до решетките в многомерното пространство — това е математиката, която пази личния ни живот.
Помислете за един обикновен ден. Сутрин отваряте телефона си, проверявате имейла, влизате в онлайн банкирането, отваряте социалните мрежи. Следобед плащате с карта в магазина, после поръчвате нещо онлайн. Вечер говорите по видео с близък човек в чужбина. За всяко от тези действия се случва едно и също, невидимо за вас: съобщенията ви се превръщат в неразгадаема смесица от числа, пътуват през десетки сървъри на три континента и след това се възстановяват само при правилния получател.
Математиката, която прави всичко това възможно, се нарича криптография — буквално „тайнопис" от гръцките думи κρυπτός (скрит) и γράφω (пиша). Но това отдавна не е просто тайнопис. Съвременната криптография е една от най-красивите области на приложната математика, в която теория на числата, абстрактна алгебра, геометрия на елиптичните криви и дори квантова механика се срещат, за да решат една съвсем практична задача: как двама души, които никога не са се виждали, могат да споделят тайна през публичен канал, достъпен за всеки наблюдател?
Тази статия е за математиката на съвременната криптография — как е устроена и защо работи. Ако ви интересува и историята зад нея — разбитите кодове от Мария Стюарт до Enigma, драмата около телеграмата Цимерман, загадъчните ръкописи, които и до днес не са разчетени — вижте придружаващата статия „Тайни писма: историята на криптографията през вековете".
Защо изобщо ни трябва криптография?
Когато изпращате съобщение по интернет, то не пътува по една права линия до получателя. То се разбива на малки пакети данни, всеки от които минава през няколко различни сървъра — понякога през три-четири държави, понякога през океани и континенти. Всеки от тези междинни сървъри по принцип може да прочете съдържанието на пакета, ако то е написано на обикновен език.
Задачата на криптографията е точно това: да преобразува съобщението в нещо, което изглежда напълно случайно за всеки външен наблюдател, но се възстановява до оригиналния вид само от предвидения получател. Това преобразуване трябва да е толкова сигурно, че дори някой да прихване милиони такива съобщения, пак да не може да разбере и дума от тях.
Съвременната криптография не се занимава само със запазване на тайни. Тя решава поне четири тясно свързани задачи:
• Цялост (integrity) — ако някой промени съобщението по пътя, получателят узнава това.
• Автентичност (authenticity) — получателят е сигурен кой е изпратил съобщението.
• Неотричаемост (non-repudiation) — този, който е подписал съобщението, не може по-късно да отрече, че го е изпратил.
На езика на тази статия, когато говорим за „тайни съобщения", ще имаме предвид всяко от тези неща — от пазенето на парола през удостоверяването на самоличност до цифровия подпис на договор.
Кратка историческа увертюра
Преди да стигнем до математическата сърцевина на съвременната криптография, е полезна кратка историческа ориентация. Първото документирано криптографско средство — шифърът на Цезар (около 58 г. пр.н.е.) — просто премества всяка буква с фиксиран брой позиции напред в азбуката. В латинската азбука (за чиято кореспонденция го използва Цезар) А ставало D, B ставало E и т.н. Ако номерираме буквите от 0 нагоре, шифроването на буква с номер \(x\) с отместване \(n\) е:
\[E(x) = (x + n) \bmod 26.\]
Принципът на шифъра на Цезар върху латинската азбука: всяка буква се премества с 3 позиции — A→D, B→E, C→F... Шифърът има само 25 възможни ключа и може да бъде разбит за секунди.
Цезаровият шифър е тривиален за разбиване по две причини. Първо, има само 25 различни възможни отмествания — пробата на всичките е въпрос на минути. Второ, дори без да пробваме всички, работи и честотен анализ: арабският учен Ал-Кинди (около 850 г.) забелязал, че във всеки език някои букви се появяват по-често от други. В английския например буквата „E" е сред най-често срещаните. Ако най-честата буква в шифрирания текст е „H", това подсказва, че отместването вероятно е такова, че „E" става „H".
След Ал-Кинди идват по-сложни методи — полиалфабетният шифър на Виженер (XVI век), който използва повтаряща се ключова дума, и електромеханичните шифровални машини като Enigma. Всички те обаче споделят един и същ недостатък: използват един и същ таен ключ за шифроване и за разшифроване. А това означава, че двете страни трябва предварително да са си разменили ключа по сигурен канал — което е точно проблемът, който искаме да решим.
Подробна история на тези методи — с разбиването им от Бабидж, Касиски, Тюринг и Фридман — ще намерите в придружаващата статия. Тук ще преминем директно към математическите идеи на съвременната криптография.
Принципът на Керкхоф и съвършената тайна
Преди да преминем към модерната математика на криптографията, трябва да споменем две идеи, които оформят цялата ѝ философска и математическа основа.
Първата е принципът на Керкхоф, формулиран от холандския лингвист Огюст Керкхоф през 1883 г.: сигурността на един шифър не бива да зависи от това, че методът му е таен; тя трябва да идва единствено от тайната на ключа. Този принцип е крайъгълен камък на цялата съвременна криптография. Всеки днешен алгоритъм — AES, RSA, ECDSA, SHA-256 — е напълно открит. Спецификациите му са публикувани, можете да ги прочетете за минути. Точно това позволява на криптографи по целия свят да ги атакуват с пълно знание и да потвърждават, че остават сигурни. Сигурност, която устоява на открита проверка, е единствената, на която можем да вярваме.
Втората идея е още по-фундаментална. През 1949 г. Клод Шанън — бащата на теорията на информацията — публикува статията „Communication Theory of Secrecy Systems", в която дава строга математическа формулировка на това, което нарича съвършена тайна.
\[P(M = m \mid C = c) = P(M = m).\] С други думи, виждайки шифрирания текст, атакуващият не научава абсолютно нищо ново за оригиналното съобщение. Шанън показва, че класическият One-Time Pad е каноничният модел на система със съвършена тайна: ключът трябва да е поне толкова дълъг, колкото съобщението, да е наистина случаен и да не се използва повторно.
One-Time Pad-ът е математически неразбиваем, но има огромен практически недостатък: ключът трябва да е толкова дълъг, колкото съобщението, и трябва да се достави предварително по сигурен канал. Ако имаме сигурен канал за доставка на ключа, защо да не изпратим по него и самото съобщение? Точно този парадокс налага цялата сложност на модерната криптография. Всеки практически шифър — AES, RSA, ECC — жертва съвършената тайна в полза на практичността: използва кратки ключове и разчита не на информационна невъзможност за разбиване, а на изчислителна трудност.
Статията на Шанън превръща криптографията от изкуство в наука — точно както статията на Тюринг от 1936 г. превръща изчислението от занаят в математическа теория. От този момент нататък криптографията вече има точна математическа основа: задачата на добрия шифър е не просто „да изглежда сложен", а да сведе разбиването си до математическа задача, за която знаем или вярваме, че е трудна.
Enigma и идеята за математическа трудност
Най-известната шифровална машина в историята е Enigma — електромеханичното устройство на Германия от Втората световна война. Детайлната история на нейното разбиване от полските математици и по-късно от Алън Тюринг в Блечли Парк заслужава отделна статия, но за нашия математически разказ е важно едно единствено нещо: числата.
Броят 158 квинтилиона начални настройки изглежда астрономически. Германците смятат Enigma за абсолютно сигурна точно заради тази огромна цифра. Но разбиването на Enigma показва нещо дълбоко важно за криптографията: големият брой комбинации сам по себе си не гарантира сигурност. Тюринг и колегите му намират хитрости, които позволяват бързо да се отхвърлят огромни множества от невъзможни настройки. Това, което наистина гарантира сигурност, е не броят на възможните ключове, а математическата трудност на задачата, която атакуващият трябва да реши.
DES и AES: симетричните шифри, които пазят ежедневието
След войната криптографията постепенно излиза от военните тайни и навлиза в гражданския свят. Първата голяма крачка е направена през 1977 г., когато американският Национален институт за стандарти приема DES (Data Encryption Standard) — симетричен шифър, разработен от екипа на IBM под ръководството на Хорст Файстел. DES използва 56-битов ключ, което по онова време се смята за достатъчно. Алгоритъмът се приема от банки, държавни институции и бизнеса по целия свят.
Но законът на Мур не щади никого. Към 1998 г. специализиран компютър на стойност 250 000 долара, наречен Deep Crack, разбива DES за по-малко от три дни чрез атака с груба сила — пробва всички възможни 256 ключа. Стандартът очевидно отмира.
През 1997 г. американският институт NIST обявява публичен конкурс за нов стандарт. От 15 представени кандидати от криптографи по целия свят, през 2000 г. е избран алгоритъмът Rijndael, разработен от двамата белгийски криптографи Йоан Дамен и Винсент Рийман. През 2001 г. той става федерален стандарт на САЩ под името AES (Advanced Encryption Standard). Днес AES е вероятно най-използваният алгоритъм за шифроване в света.
• SubBytes — замяна на байтове по фиксирана таблица (S-box), основана на инверсия в крайното поле \(\text{GF}(2^8)\).
• ShiftRows — циклично разместване на редовете.
• MixColumns — линейна операция върху колоните.
• AddRoundKey — XOR с подключ.
Резултатът е, че всеки бит от входа влияе върху всеки бит от изхода по непредсказуем начин. Дори и най-малка промяна в оригиналното съобщение води до съвсем различен шифрован резултат.
За AES-256 не е известна практическа атака с груба сила и при днешните изчислителни възможности такава атака се смята за практически невъзможна. Дори да пуснем един милиард компютъра, всеки проверяващ един милиард ключа в секунда, това ще отнеме приблизително \(10^{52}\) години — невъобразимо много повече от възрастта на Вселената. Това е магията на експоненциалния растеж: добавянето на един бит към ключа удвоява времето за атака.
AES е симетричен шифър — същият ключ се използва и за шифроване, и за разшифроване. Той е много по-бърз от RSA или ECC, което е удобно за големи обеми данни. Затова модерната криптография обикновено работи хибридно: общ таен ключ се съгласува чрез схеми от типа на (EC)DHE, а удостоверяването често се извършва чрез RSA или ECDSA сертификати; след това реалните данни се шифроват с AES или ChaCha20-Poly1305. Това е моделът, който се крие зад всяко HTTPS съединение в браузъра ви.
Ключът: ахилесовата пета на класическата криптография
Всички шифри, които разгледахме дотук — от Цезар през Виженер до Enigma — имат една обща черта. Те работят със споделен таен ключ: изпращачът и получателят трябва предварително да разполагат с един и същ ключ — число, дума, настройка на ротори. С този ключ единият шифрира, а другият разшифрира. Ако някой трети знае ключа, цялата сигурност се срива.
Това създава една фундаментална трудност, която векове наред никой не знае как да разреши: как двама души да споделят ключ сигурно? Не можем да изпратим ключа по същия канал, по който ще изпратим тайното съобщение — ако подслушвачът хване ключа, той ще разшифрира и всяко следващо съобщение. Не можем да се срещнем лично всеки път — модерният свят просто не работи така. А ако имаме хиляди кореспонденти, ще ни трябват хиляди отделни ключа.
До 70-те години на XX век този проблем се смята просто за неразрешим. Армиите и дипломатическите служби решавали го с физическа доставка — куриери с куфарчета, белязани носители, ежедневни смени на ключовете. Но за гражданското общество, което тъкмо започвало да открива интернет, това е невъзможно. Как Amazon ще размени ключ с всеки от милионите си клиенти? Как банката ще се съгласи за ключ с всяко приложение на всеки телефон?
Решението, когато идва, е толкова неочаквано и елегантно, че и днес звучи като магия.
Революцията на публичния ключ
През 1976 г. двама млади изследователи в Станфордския университет — Уитфийлд Дифи и Мартин Хелман — публикуват статия със заглавие „Нови посоки в криптографията". В нея те предлагат идея, която изглежда невъзможна: да се използват две различни, но математически свързани числа. Едното (публичният ключ) се разпространява свободно — може да се обяви дори във вестник. Другото (частният ключ) се пази само от собственика си.
Магията е в следното: всеки, който знае публичния ключ, може да шифрира съобщение, предназначено за притежателя. Но никой, дори и да има самия шифрован текст и публичния ключ, не може да го разшифрира. Само притежателят на частния ключ може. Това е криптография с публичен ключ.
Може би най-лесно се разбира чрез аналогия с отворени катинари. Представете си, че искате хората да ви изпращат тайни писма. Вие купувате хиляда еднакви катинара с един и същ ключ. Катинарите раздавате свободно на всеки, който иска. Ключът държите в джоба си. Сега всеки може да сложи писмо в кутия, да я заключи с един от вашите катинари и да ви я изпрати. По пътя никой не може да я отвори — но вие, със своя ключ, можете.
Катинарът е публичният ключ. Ключът, с който го отваряте — частният. Всеки може да „заключва" за вас; само вие можете да „отключвате".
• Публичен ключ — разпространява се свободно; с него всеки може да шифрира съобщение към собственика.
• Частен ключ — пази се в тайна от собственика; само той може да разшифрира.
Знанието на публичния ключ не позволява на никого да възстанови частния. Тази асиметрия е сърцевината на системата.
Дифи и Хелман очертават принципа, но не дават конкретна математическа реализация. Въпросът остава открит: коя точно математическа задача е достатъчно „асиметрична", за да изиграе ролята на катинара? Операцията, която е лесна в едната посока, но непосилна в обратната?
Отговорът идва по-малко от година по-късно.
RSA: най-известният алгоритъм в света
През есента на 1976 г. трима млади изследователи в Масачузетския технологичен институт (MIT) четат статията на Дифи и Хелман и се залавят да търсят конкретна реализация. Те са Рон Ривест (компютърен учен), Ади Шамир (математик) и Леонард Адлеман (математик). Следващите няколко месеца Ривест и Шамир предлагат идея след идея за „еднопосочна функция", а Адлеман — със силна подготовка по теория на числата — методично отхвърля всяка от тях.
Решаващата нощ е на 5 април 1977 г. — първата вечер на еврейския Песах. Тримата са на гости у един студент. Ривест се прибира у дома след полунощ, не може да заспи и ляга на дивана с учебник по математика в ръцете. До изгрев слънце е формулирал идеята, която ще стане известна с инициалите им: RSA.
Идеята е дълбока, но се основава на изненадващо прост факт от теорията на числата: много по-лесно е да умножим две големи прости числа, отколкото да разложим произведението им обратно на множители.
За малки числа разликата не е голяма. Но за числа с 600 цифри тя става астрономическа. Умножението отнема части от секундата. Разлагането с най-добрите известни алгоритми би отнело повече време от възрастта на Вселената.
Сърцето на RSA е следната процедура. Алиса иска да получава тайни съобщения. Тя избира две големи прости числа \(p\) и \(q\) (на практика с по няколкостотин цифри) и изчислява тяхното произведение \(N = p \cdot q\). Това число \(N\) е част от нейния публичен ключ — тя го обявява публично. Простите множители \(p\) и \(q\) обаче пази в тайна — те са сърцевината на нейния частен ключ.
Математиката зад шифроването използва една класическа теорема, известна като малката теорема на Ферма и нейното обобщение от Ойлер. Без да навлизаме в детайли, ключовото свойство е следното: можем да намерим две числа \(e\) (част от публичния ключ) и \(d\) (част от частния ключ), такива че за всяко съобщение \(m\):
\[(m^e)^d \equiv m \pmod{N}.\]С други думи, ако шифрираме с \(e\) (публичния експонент) и след това „шифрираме" отново с \(d\) (частния експонент), получаваме обратно оригиналното съобщение. Но за да намерим \(d\), знаейки \(e\) и \(N\), трябва да знаем \(p\) и \(q\) — а те се узнават само като разложим \(N\) на прости множители. Това е трудната задача, която прави RSA сигурен.
Пример за RSA с малки числа. В практиката \(N\) има стотици цифри, така че разлагането му е практически невъзможно с класически компютри.
Има един изключително интересен факт, който остава скрит почти 25 години. През 1973 г. — четири години преди Дифи, Хелман, Ривест, Шамир и Адлеман — британският математик Клифърд Кокс, работещ в разузнавателната агенция GCHQ, открива по същество същия алгоритъм. Но заради секретността, неговата работа остава класифицирана до 1997 г. Така една от най-важните идеи в историята на криптографията фактически е открита два пъти: веднъж в тайна от британското разузнаване и втори път — открито — от тримата учени от MIT. Именно публичното откритие обаче е това, което наистина променя света.
Статията на Ривест, Шамир и Адлеман е публикувана в Communications of the ACM през 1978 г. Междувременно, през август 1977 г., Мартин Гарднър я описва в популярната си рубрика „Mathematical Games" на Scientific American и поставя предизвикателство: да бъде разбито кодирано съобщение, свързано с число от 129 цифри. Обещава награда от 100 долара. Гарднър смята, че задачата ще остане нерешена хилядолетия. Хиляди читатели изпращат самоадресирани пликове, за да получат пълната статия. Един от тях е млад студент в Калифорния на име Стив Джобс.
Днес числото RSA-250 (с 250 десетични цифри, 829 бита) е най-голямото публично разложено RSA число (2020 г.), изискало около 2 700 процесор-години. Съвременните препоръки са за ключове поне с 2048 бита, което прави разлагането с класически компютри практически невъзможно.
RSA остава един от класическите фундаментални алгоритми на публичната криптография, макар в съвременните интернет връзки често да се използват ECC, ECDSA и ECDHE. Всеки път, когато виждате катинарче до адреса в браузъра, всеки път, когато правите банкова операция, всеки път, когато инсталирате приложение с подписан код — някъде в процеса участва RSA или тясно свързан алгоритъм. През 2002 г. тримата му автори получават най-високата награда в компютърните науки — наградата Тюринг.
Дифи-Хелман: размяна на ключ без да си споделяме нищо
Успоредно с RSA, идеята на Дифи и Хелман се реализира и по друг начин. Протоколът Дифи-Хелман решава малко по-различен, но не по-малко фундаментален проблем: как двама души, които никога не са общували, могат да се съгласят за общ таен ключ през публичен канал — така че всеки, който подслушва, да не може да възстанови този ключ.
Идеята отново се основава на еднопосочна математическа операция, но този път съвсем различна. Съществува едно число \(g\) (генератор) и едно голямо просто число \(p\), които са публични — всички ги знаят. Алиса избира тайно число \(a\); Боб избира тайно число \(b\). Алиса изпраща на Боб стойността \(A = g^a \bmod p\); Боб изпраща на Алиса \(B = g^b \bmod p\).
Сега Алиса изчислява \(B^a = (g^b)^a = g^{ab} \bmod p\). Боб изчислява \(A^b = (g^a)^b = g^{ab} \bmod p\). Получават едно и също число! Те са се съгласили за общ таен ключ, без никога да са си го казвали.
• Алиса избира тайно \(a = 6\). Изчислява \(A = 5^6 \bmod 23 = 15625 \bmod 23 = 8\). Изпраща \(A = 8\) на Боб.
• Боб избира тайно \(b = 15\). Изчислява \(B = 5^{15} \bmod 23 = 19\). Изпраща \(B = 19\) на Алиса.
• Алиса изчислява общия ключ: \(K = 19^6 \bmod 23 = 2\).
• Боб изчислява общия ключ: \(K = 8^{15} \bmod 23 = 2\).
Получиха един и същ ключ \(K = 2\), без изобщо да го изпращат. Подслушвачът вижда \(p\), \(g\), \(A = 8\), \(B = 19\) — и трябва да намери \(a\) или \(b\) от \(5^a \equiv 8 \pmod{23}\). За толкова малки числа това е лесно, но за \(p\) с 2048 бита е практически невъзможно.
А подслушвачът, макар да е видял \(g\), \(p\), \(A\) и \(B\), би трябвало да намери \(a\) или \(b\) — а това е задачата за дискретния логаритъм, която се смята за изключително трудна. Това е другата голяма „еднопосочна" функция в съвременната криптография: \(g^x \bmod p\) се изчислява бързо, но от стойността \(g^x \bmod p\) да възстановим \(x\) — задача, за която не е известен ефективен общ алгоритъм.
Една важна практическа разновидност е временният Дифи-Хелман (ephemeral Diffie-Hellman, DHE или ECDHE) — при всяка нова връзка се генерират нови временни ключове, които след това се изтриват. Това осигурява свойство, наречено устойчивост на компрометиране на стари сесии (forward secrecy): дори ако дългосрочният ключ на сървъра бъде откраднат в бъдеще, старите записани разговори остават неразбити. Това е една от причините, поради които съвременните HTTPS връзки са толкова надеждни.
Елиптични криви: малки числа, голяма сигурност
През 1985 г. двама математици — Нийл Коблиц от Университета на Вашингтон и Виктор Милър от IBM — независимо един от друг предлагат нова идея. Вместо да работим с обикновени числа по модул \(p\), защо да не работим с точки върху елиптична крива?
Елиптичната крива е крива, определена от уравнение от вида
\[y^2 = x^3 + ax + b,\]разгледана над някакво крайно поле (например, над остатъците по модул просто число). На пръв поглед това звучи абстрактно, но такива криви имат едно забележително свойство: върху тях може да се дефинира операция „събиране" на точки, която прави множеството от точки математическа структура, наречена група. И върху тази група може да се зададе задача, аналогична на задачата за дискретния логаритъм — но много по-трудна.
„Събиране" на точки върху елиптична крива: прокарваме права през P и Q, намираме третата пресечна точка и я оглеждаме спрямо оста x. Резултатът R = P + Q отново е точка върху кривата. Тази операция дефинира групова структура, върху която почива криптографията с елиптични криви.
Защо елиптичните криви? Защото сигурността, която RSA постига с ключ от 2048 бита, криптографията с елиптични криви (ECC) постига само с около 256 бита. Това е огромно предимство за мобилни устройства, чип-карти, IoT устройства, безконтактни плащания — навсякъде, където памет, енергия и скорост са ограничени.
Днес всеки път, когато използвате iPhone, изпращате съобщение през Signal или WhatsApp, правите Bitcoin транзакция или се свързвате с модерен уебсайт през HTTPS, най-вероятно на ниско ниво се ползват точно елиптични криви. Криптографията тук е направила любопитен завой: идеи от чистата математика от XIX век — елиптичните интеграли, изучавани от Абел, Вайерщрас и Клебш — са се оказали най-практичният инструмент за защита на милиарди съобщения дневно.
Хеш функции: пръстови отпечатъци на данни
Дотук говорихме главно за шифроване — да направиш съобщение нечетимо за чуждо око. Но съвременната криптография се опира на още един фундаментален инструмент: хеш функциите. Хеш функцията приема вход с произволна дължина — цял документ, видеофайл, книга — и произвежда къс уникален „отпечатък" с фиксирана дължина (типично 256 бита за SHA-256 или 512 за SHA-3).
Криптографски добрата хеш функция трябва да има три свойства: да се изчислява бързо; ако промените дори един бит от входа, целият отпечатък трябва да изглежда съвсем различен; и е практически невъзможно да се намерят два различни входа, които дават един и същ хеш (това се нарича устойчивост на колизии).
• Проверка на цялостта — сваляме файл и проверяваме, че хешът му съвпада с обявения.
• Съхранение на пароли — базата данни пази хеш, не самата парола.
• Блокчейн и криптовалути — всеки блок в Bitcoin съдържа хеш на предходния, което прави веригата неизменна.
• Дигитален таймщамп — можем да докажем, че даден документ е съществувал в определен момент, без да разкриваме съдържанието му.
Най-разпространените хеш функции днес са от семействата SHA-2 (създадено от американската Агенция за национална сигурност и стандартизирано през 2001 г.) и SHA-3 (избрано чрез открит международен конкурс през 2012 г., разработено от екипа на Йоан Дамен и Винсент Рийман, автори и на AES).
Цифровият подпис: как математиката създава доверие
Публичната криптография предлага нещо повече от тайно общуване. Тя решава и задачата за цифров подпис — как някой да се удостовери категорично, че даден документ идва точно от него и не е бил променен.
Идеята е обратна на обикновеното шифроване. Алиса иска да подпише документ. Тя изчислява хеша на документа и го „шифрира" със своя частен ключ. Всеки, който знае нейния публичен ключ, може да „дешифрира" този подпис и да го сравни с реалния хеш на документа. Ако двете съвпадат, значи: първо, документът не е бил променен; второ, подписът е направен именно от притежателя на частния ключ.
Цифровите подписи са в основата на огромна част от модерната цифрова инфраструктура. Всеки сертификат на уебсайт (SSL/TLS), всяко ъпдейт-пакетче на операционна система, всяка транзакция в блокчейна, всеки електронен подпис на договор — това са цифрови подписи. Те превръщат математическата строгост в практическо доверие.
HTTPS: как криптографията работи с катинарчето в браузъра
Всеки път, когато виждате малкото катинарче до адреса в браузъра си, под него се изпълнява една от най-красивите хореографии на съвременната криптография — протоколът TLS (Transport Layer Security). HTTPS означава просто HTTP върху TLS. За една част от секундата се случва следното:
- Браузърът ви се свързва със сървъра и му казва какви криптографски алгоритми поддържа.
- Сървърът избира набор от алгоритми и изпраща своя цифров сертификат — документ, подписан от доверен орган (Certificate Authority), потвърждаващ, че точно този сървър притежава точно тази публична ключова двойка.
- Браузърът проверява подписа на сертификата срещу списък от доверени органи, запазен предварително в операционната система.
- Браузърът и сървърът изпълняват размяна на ключове по Дифи-Хелман (обикновено ECDHE — ephemeral elliptic-curve Diffie-Hellman) и се съгласуват за общ таен ключ.
- От този момент нататък цялата комуникация е шифрирана със симетричен шифър (обикновено AES-GCM или ChaCha20-Poly1305). Никой по пътя не може да я прочете.
Забележително е, че това се случва за по-малко от 100 милисекунди. Всяка секунда в света се установяват милиони такива връзки. Без този невидим танц на числата интернет, както го познаваме, просто не би съществувал — никой не би писал паролата си по мрежа, където всеки междинен възел по пътя би могъл да я прочете.
Хибридният модел на HTTPS съчетава силните страни на двата свята: асиметричната криптография решава трудния проблем с размяната на ключове, след което симетричната криптография бързо шифрова реалните данни.
Signal, Tor и блокчейн: криптографията срещу централизацията
Но HTTPS защитава комуникацията ви само до сървъра — после собственикът на сървъра може да прочете всичко. За по-висока степен на защита са възникнали системи с криптиране от край до край (end-to-end encryption), в които дори посредникът не може да прочете нищо.
Най-известният такъв протокол е Signal Protocol, разработен от Моксие Марлинспайк и Тревър Перин през 2013 г. Той комбинира три математически идеи: класически Дифи-Хелман, троен Дифи-Хелман (X3DH) за първоначална установка на връзка и Double Ratchet — механизъм, при който ключовете се обновяват с всяко ново съобщение. Дори ако някой открадне отделен ключ в бъдеще, миналите съобщения остават недостъпни. Същият протокол е внедрен изцяло в WhatsApp, а идеите му оказват влияние и върху други големи платформи за защитена комуникация.
Другата любопитна приложна област е Tor (The Onion Router). Замисълът е прост: вместо да изпращате съобщението директно на получателя, вие го „обвивате" в няколко слоя криптография (оттук и „лук") и го изпращате през верига от доброволчески сървъри. Всеки сървър може да разкрие само своя слой — научава откъде идва пакетът и към кого да го препрати, но не и цялата пътека. Така се постига силна анонимност. Tor е създаден първоначално от американската военноморска изследователска лаборатория, но днес се използва от журналисти, активисти и обикновени хора, които искат да защитят личните си данни от проследяване.
Блокчейнът и криптовалутите са друго забележително приложение. Bitcoin, публикуван през 2008 г. в анонимната статия на Сатоши Накамото, използва три криптографски инструмента: хеш функцията SHA-256 (за свързване на блоковете в неизменна верига), цифрови подписи върху елиптичната крива secp256k1 (за удостоверяване на собственост) и т.нар. доказателство за извършена работа (proof of work) (защита срещу фалшифициране). Всяка Bitcoin транзакция е в основата си цифров подпис, който казва: „притежателят на този частен ключ изпраща тази сума на този получател". Без криптографията с публичен ключ блокчейнът просто не би могъл да съществува.
Нулево знание: как да докажеш нещо, без да разкриеш нищо
Една от най-удивителните и най-елегантни идеи в съвременната криптография е концепцията за доказателство с нулево знание (zero-knowledge proof). Въведена през 1985 г. от Шафи Голдвасер, Силвио Микали и Чарлз Рейкоф, тя отговаря на привидно противоречив въпрос: можем ли да докажем, че знаем нещо, без да разкриваме какво точно знаем? По-късно именно работите на Голдвасер и Микали върху основите на съвременната криптография са отличени с наградата Тюринг.
Класическата аналогия е за пещерата на Али Баба. Представете си пещера с два входа, А и Б, които се свързват чрез тайна врата в дъното. Алиса твърди, че знае думата, която отваря вратата, но не иска да я разкрие. Боб стои пред входовете. Алиса влиза през А или Б (без Боб да види през кой). Боб извиква: „излез през Б!" Ако Алиса знае думата, тя винаги може да изпълни — независимо през кой вход е влязла. Ако не знае, тя може да познае само с вероятност 1/2. Повтарят играта 20 пъти. Ако Алиса излиза правилно всеки път, вероятността тя да е отгатвала е \(1/2^{20} \approx\) 1 на милион. Боб се убеждава, че Алиса знае думата — без самият той да я научи.
Тази идея е не просто математически куриоз. Тя е в основата на модерните анонимни криптовалути (Zcash използва zk-SNARKs), на системи за удостоверяване на възраст, без да се разкрива точната дата на раждане, на онлайн гласуване и на множество други практически приложения. Една от най-активните области в криптографията днес е именно развитието на ефективни zk-системи.
Хомоморфно шифроване: да смяташ върху шифровани данни
Още по-удивителна идея е хомоморфното шифроване. Представете си, че сте болница, която иска да даде данните си на изследователски институт за анализ — но не можете да разкриете индивидуалните записи на пациентите. С хомоморфно шифроване е възможно институтът да извършва сложни изчисления върху шифрованите данни, получавайки шифрован резултат, който след разшифроване от болницата дава същия отговор, все едно анализът е проведен върху откритите данни. Институтът научава резултата, но никога не вижда самите данни.
Идеята е формулирана още през 1978 г. от Ривест, Адлеман и Дертузос, но пълна реализация — т.нар. fully homomorphic encryption (FHE) — беше намерена чак през 2009 г. от Крейг Джентри, тогава докторант в Станфорд. Той показа конструкция, основана на идеални решетки в пръстени. От тогава FHE е претърпял огромен напредък и вече се използва за медицински изчисления, финансов анализ и облачни услуги. Microsoft SEAL и IBM HELib са две от най-известните отворени реализации.
Разделяне на тайни: когато нито един не трябва да знае всичко
През 1979 г. Ади Шамир — същият един от тримата автори на RSA — публикува статия с деликатното заглавие „How to Share a Secret" в списанието Communications of the ACM. В нея той решава един любопитен проблем: представете си, че една институция пази ключ, който дава достъп до особено чувствителен държавен архив. Този ключ е твърде важен, за да бъде доверен на един човек. Но не можем и да го разделим на парчета просто като ножица — тогава всяко парче е почти безполезно само по себе си, а загубата на едно парче прави цялата тайна загубена завинаги.
Идеалното решение би било следното: разделяме тайната между, да речем, 7 души; ако поне 5 от тях се съберат, могат да я възстановят; но 4 или по-малко не научават абсолютно нищо. Такава система се нарича (k, n)-прагова схема — \(n\) е общият брой участници, \(k\) е прагът за възстановяване.
Решението на Шамир е математически красиво до поразително. То използва свойство на полиномите, известно още от училищната геометрия: през две точки минава единствена права, през три точки — единствена парабола, а общо — през всеки \(k\) точки минава единствен полином от степен \(k-1\).
\[f(x) = S + a_1 x + a_2 x^2 + \ldots + a_{k-1} x^{k-1}.\] Забележете, че \(f(0) = S\) — свободният член е самата тайна. Сега на всеки от \(n\)-те участника даваме по една точка от полинома: \((1, f(1))\), \((2, f(2))\), ..., \((n, f(n))\).
• Ако \(k\) от тях съберат точките си, те еднозначно възстановяват полинома (по класическата интерполация на Лагранж) и оттам — стойността \(f(0) = S\).
• Ако имат само \(k-1\) или по-малко точки — за всяка възможна стойност на \(S\) съществува точно един полином, който минава през техните точки и има тази свободна стойност. Значи тайната може да бъде абсолютно всяко число — те не научават нищо.
Забележителното на схемата на Шамир е, че тя е информационно сигурна — сигурна по критерия на Шанън, не зависи от никакви изчислителни предположения. Квантовият компютър не може да я разбие. Никой компютър не може. Математически тя просто не може да бъде разбита с по-малко от прагния брой точки.
Разделянето на тайни днес се използва в много критични системи: за ключовете на DNSSEC (които пазят домейн-имената в интернет), за управление на корпоративни ключове, за биометрични системи, за криптовалутни портфейли с многоподписни схеми. В криптовалутните системи се използват сродни идеи за разпределен контрол върху ключове, но те не бива да се отъждествяват директно със схемата на Шамир.
Удостоверителните органи: кой пази пазачите?
Цялата магия на HTTPS, която описахме по-горе, се опира на един привидно прост въпрос: откъде знам, че публичният ключ, който получавам от „google.com", наистина принадлежи на Google? Какво пречи на атакуващ да подмени пакетите и да ми прати свой публичен ключ, представяйки се за Google?
Отговорът е чрез система от удостоверителни органи (Certificate Authorities, CA) — трети страни, на които всички се доверяват. Удостоверителният орган подписва сертификата, съдържащ публичния ключ на Google. Вашият браузър още от фабрика носи списък с публичните ключове на доверените CA. Когато получите сертификата на Google, браузърът проверява, че той е подписан от CA, на който вече се доверява.
Тази система прилича на йерархично дърво: корен → междинни CA → индивидуални сертификати. Тя обаче има известни слабости. Ако един CA бъде хакнат — а такива инциденти са се случвали, например при DigiNotar през 2011 г. и Comodo същата година — атакуващите могат да издават фалшиви сертификати за всеки домейн в света. Именно затова съвременните браузъри въведоха допълнителни механизми като Certificate Transparency (публичен журнал на всички издадени сертификати, 2013 г.) и HSTS (принудителна HTTPS-връзка).
В края на 2015 г. започва тиха революция: Let's Encrypt — безплатен удостоверителен орган, поддържан от Internet Security Research Group — започва публично да издава сертификати, а през 2016 г. услугата вече се разраства масово.
Случайните числа: невидимата основа на всичко
Цялата криптография, която разгледахме дотук, разчита на едно деликатно изискване: наличие на истински случайни числа. Ключовете, еднократните стойности (nonces), временните параметри, солите за паролите — всичко това трябва да бъде непредсказуемо. Ако атакуващият може да познае дори частично случайните числа, използвани при генерирането на ключовете ви, цялата сигурност рухва.
Проблемът е, че компютрите са детерминистични устройства. Те не могат сами по себе си да произвеждат истинска случайност. Затова в практиката се използва двустъпков подход: събира се ентропия от физическия свят (шум от хардуер, движения на мишката, време между натискания на клавиши, колебания в температурата на процесора) и тя се използва като семе за криптографски сигурен генератор на псевдослучайни числа (CSPRNG).
Съвременните процесори отдавна имат хардуерни генератори на случайни числа — Intel RDRAND (от 2012 г.), ARM TrustZone. Операционните системи поддържат системни генератори (/dev/random и /dev/urandom в Linux). Добрият криптографски код винаги използва тях, никога не разчита на функция като rand() от стандартната библиотека, която е предназначена за игри и симулации, не за сигурност.
Философският въпрос: backdoor-ите и правото на лична неприкосновеност
Криптографията винаги е имала политическо измерение. Още през 90-те години на XX век, когато PGP (Pretty Good Privacy) на Фил Цимерман за първи път прави силна криптография достъпна за обикновените хора, американското правителство завежда срещу него наказателно дело за „износ на оръжие" (криптографията по онова време е класифицирана като военна технология). Цимерман в крайна сметка е оправдан, но въпросът остава.
Днешните дебати са свързани с т.нар. backdoor-и (задни вратички). Правителства и разузнавателни служби настояват, че при разследване на престъпления трябва да могат да получават достъп до шифрована комуникация. Техническото решение би било производителите да вграждат специални „майсторски ключове", с които властите да могат да четат всяко съобщение.
Криптографската общност почти единодушно отхвърля тази идея. Аргументите са два: първо, ако един ключ работи за „добрите", той ще работи и за „лошите" — съществуването на такъв ключ създава точка на компрометация, която е мишена за всеки атакуващ. Второ, ако една държава има такъв ключ, скоро и авторитарни режими ще настояват за същото — и те ще го използват срещу дисиденти, журналисти, активисти.
Класически примери за провал на този подход са хакването на инструмента Clipper Chip (създаден от американската АНС през 90-те с вградена задна вратичка) и скандалът Dual_EC_DRBG от 2013 г., когато се оказа, че стандартизиран от NIST генератор на случайни числа съдържа предполагаема вградена задна вратичка от страна на АНС. След този скандал доверието в официалните криптографски стандарти беше сериозно разклатено и стандартите, в които участва широка публична проверка (например конкурсът за AES или този за пост-квантова криптография), се смятат за много по-надеждни от тези, въведени без такъв дебат.
Криптографът и автор на „Applied Cryptography" Брус Шнайер многократно е изтъквал, че силната криптография не е лукс, а основа на всяка форма на цифрова свобода — свободата да мислиш, да организираш, да изразяваш несъгласие. Ако съществуват вградени задни вратички, ние вече нямаме истинска частна сфера. — по идеи на Брус Шнайер, изразявани в множество публикации и изказвания
Квантовата заплаха: Шор и краят на RSA
Цялата криптография с публичен ключ — RSA, Дифи-Хелман, ECC — стои върху един фундамент: това, че определени математически задачи (разлагане на числа, дискретен логаритъм) са практически неразрешими за класически компютри. Никой не е доказал, че тези задачи са трудни — просто никой не е намерил бърз начин да ги реши.
През 1994 г. математикът Питър Шор от Bell Labs публикува резултат, който подсича в корена тази увереност. Той описва алгоритъм, който — ако се изпълнява върху достатъчно мощен квантов компютър — може да разлага цели числа за време, експоненциално по-малко от най-добрия класически алгоритъм. Задача, която би отнела милиарди години на класически компютър, се свежда до часове или минути на квантов.
Задачата за дискретния логаритъм — върху обикновени числа и върху елиптични криви — пада по аналогичен начин. Значи ако се построи достатъчно мощен квантов компютър, цялата съвременна криптография с публичен ключ ще престане да бъде сигурна. Банкови тайни, здравни досиета, държавни документи, лични комуникации — всичко, което сме защитавали с RSA или ECC, ще стане четимо.
Колко бързо се строят квантовите компютри днес? Отговорът е: достатъчно бързо, за да ускори прехода към пост-квантова криптография, но все още не толкова бързо, че практическото разбиване на RSA да е непосредствено. Тук числата се променят много бързо и не е разумно да се фиксира една-единствена оценка. Различните платформи използват различни метрики — физически кубити, логически кубити, алгоритмични кубити — а нови изследвания редовно променят оценките за нужните ресурси. Затова най-точното обобщение е следното: днес все още няма квантов компютър, способен да разбие практическо RSA, но заплахата вече е достатъчно сериозна, за да кара компании, стандартизиращи организации и държавни институции да ускоряват миграцията към пост-квантови схеми.
Има обаче и обратната страна. Някои изследвания подсказват, че дори с текущите несъвършени квантови устройства могат да бъдат избрани още по-умни начини да се атакуват криптосистеми. През 2024 г. се появиха публикации за хибридни квантово-класически техники, които показват ограничен напредък върху много малки числа, но не представляват реален пробив срещу практическо RSA.
Странични канали: когато математиката е сигурна, но изпълнението не е
Едно от най-важните открития на последните 30 години е, че дори математически безупречен криптографски алгоритъм може да бъде разбит, ако се атакува не математиката, а физическото изпълнение. Тези атаки се наричат атаки по странични канали (side-channel attacks).
През 1996 г. Пол Кохер, тогава млад изследовател в Сан Франциско, публикува статия, която показва как по времето, което компютърът използва, за да извърши криптографска операция, може да се изведе частният ключ. Идеята е проста: някои изчисления, които включват определени битове от ключа, отнемат мъничко повече време от други. Ако можете да измерите тези мъничко по-дълги времена многократно, статистически може да извлечете ключа.
От тогава се откриват още и още странични канали:
- Атаки по време на изпълнение (timing attacks) — по времето на изчислението.
- Анализ на консумираната мощност (power analysis) — по количеството електрически ток, което чипът консумира в различни моменти.
- Електромагнитни емисии (electromagnetic emanations) — по електромагнитното излъчване на устройството.
- Акустични атаки (acoustic attacks) — по звука, който процесорът издава при различни операции (да, това наистина работи — демонстрирано от Adi Shamir и колеги през 2013 г.).
- Атаки чрез кеш-паметта (cache attacks) — по модела на използване на кеш паметта на процесора.
- Spectre и Meltdown (2018) — атаки срещу спекулативното изпълнение в процесорите, които засегнаха почти всички компютри в света.
Затова съвременните криптографски реализации имат изискване за constant-time implementation: операциите трябва да отнемат точно едно и също време, независимо от стойността на тайните данни. Това не е тривиално — нормалният програмист пише „ако битът е 1, направи това, иначе онова", а такъв код има различно време на изпълнение за двете възможности. Криптографският програмист трябва да пренапише алгоритъма, така че и двете ветви да се изпълняват винаги, независимо от битовете на ключа.
Пост-квантовата криптография: новото поколение
Още през 2016 г. американският Национален институт за стандарти и технологии (NIST) обявява публичен конкурс за нови криптографски алгоритми — такива, които да останат сигурни дори пред лицето на бъдещия квантов компютър. Това е пост-квантова криптография (PQC).
В конкурса участват 82 предложения от криптографи по целия свят. През следващите осем години всяко от тях се подлага на строга публична проверка, атакуват го с всички познати методи, включително с помощта на суперкомпютри. Някои кандидати падат бързо — например през 2022 г. алгоритъмът SIKE, който стигна до финала, беше разбит за един час с класически лаптоп, като се използват идеи от 380-годишна математика.
На 13 август 2024 г. NIST публикува първите три окончателни пост-квантови стандарта: FIPS 203 (базиран на CRYSTALS-Kyber, вече под името ML-KEM), FIPS 204 (CRYSTALS-Dilithium, ML-DSA) и FIPS 205 (SPHINCS+, SLH-DSA). През март 2025 г. NIST избра HQC като резервен алгоритъм за капсулиране на ключове (KEM), допълващ ML-KEM. FN-DSA (базиран на FALCON) е в процес на стандартизация като FIPS 206.
• ML-DSA (CRYSTALS-Dilithium) — за цифрови подписи. Решетъчна основа. Основен избор за повечето подписи.
• SLH-DSA (SPHINCS+) — подписи, основани на хеш функции. По-големи подписи, но гарантирана сигурност само от свойствата на хеш функцията.
• FN-DSA (базиран на FALCON) — компактни подписи, основани на NTRU решетки (в процес на стандартизация като FIPS 206).
• HQC — код-основана криптография; избрана от NIST през март 2025 г. като резервен алгоритъм за капсулиране на ключове (KEM), допълващ ML-KEM.
Повечето от тези алгоритми почиват върху решетъчна криптография — област от математиката, изучаваща дискретни решетки в многомерно пространство. Задачата, която лежи в основата им, се нарича „Learning With Errors" (LWE) и беше въведена през 2005 г. от Одед Регев. Тя се свежда до следното: дадени са много линейни уравнения с малки, но неизвестни „грешки"; намерете тайния вектор. Счита се за трудна както за класически, така и за квантови компютри.
Преходът към пост-квантова криптография вече е започнал. Cloudflare — една от най-големите компании за мрежова инфраструктура — обяви, че цели до 2029 г. да премине изцяло на пост-квантови стандарти. Google експериментира с пост-квантова хибридна размяна на ключове в Chrome още от 2016 г.; по-късните тестове и внедрявания вече включват и алгоритми като Kyber. Apple обяви пост-квантово ниво за iMessage (наречено PQ3) през 2024 г. Signal изпревари с въвеждането на хибридно кодиране PQXDH още през 2023 г.
Квантова криптография: сигурност по законите на физиката
Интересното е, че квантовата механика може не само да руши класическата криптография, но и да създаде нов вид — при това с теоретично гарантирана сигурност. Тази област се нарича квантова криптография или по-точно квантова размяна на ключ (QKD, Quantum Key Distribution).
Най-известният протокол — BB84, предложен от Чарлз Бенет и Жил Бросар през 1984 г. — се основава на едно фундаментално свойство на квантовия свят: самото измерване на квантова система я променя. Ако някой подслушва квантов канал, по който се изпращат фотони с определена поляризация, самото му присъствие оставя следа. Алиса и Боб могат статистически да открият подслушването.
Това е принципно нова ситуация: сигурността идва не от сложността на математиката, а от самите физически закони. Експериментални системи за QKD вече работят в Китай, Швейцария и САЩ на разстояния до стотици километри по оптични влакна и дори между сателити. Но технологията все още е сложна, скъпа и ограничена от разстоянието, затова за близко бъдеще пост-квантовата криптография (която работи на обикновени компютри) е по-практичният път.
Банковата карта в джоба ви: малка криптографска крепост
Едно от най-разпространените и най-недооценени приложения на криптографията се намира в джоба на почти всеки възрастен човек. Всяка съвременна банкова карта — дебитна или кредитна — е малко устройство с вграден чип, който съдържа цял криптографски процесор. И всяко едно плащане минава през деликатно балансиран танц на числата, подобен по сложност на HTTPS връзката в браузъра.
Допреди двайсет години картите работеха с магнитна лента, на която данните се записваха в чист вид. Достатъчно беше човек с подходящо устройство да прокара картата през свой четец (скимер) в някой банкомат или ресторант, за да може после да създаде идентично копие. Измамите с клонирани карти бяха огромен проблем в целия свят през 90-те години.
Решението дойде от стандарта EMV — съкращение от Europay, Mastercard и Visa, трите компании, които го разработиха. Първите версии на стандарта EMV се появяват в средата на 90-те години, но масовото разпространение започва около 2005–2015 г. Ядрото на идеята е едно: на картата се вгражда чип, който не е просто пасивен носител на данни, а активен участник в транзакцията. Той има собствена памет, собствен процесор, собствен частен ключ — и никога не разкрива този ключ, дори на собственика на картата.
Когато плащате с карта в магазина, между картата и терминала се изпълнява протокол с три стъпки:
- Удостоверяване на картата — терминалът проверява, че картата не е фалшификат, чрез цифров подпис, издаден от банката-издател. Тук работи RSA или ECC.
- Удостоверяване на притежателя — въвеждате PIN, полагате подпис или се прилага друг позволен метод за потвърждение. В зависимост от режима проверката може да се извърши в самата карта или онлайн при издателя, но чувствителните данни не се предават в открит вид.
- Удостоверяване на транзакцията — чипът подписва конкретна комбинация от сумата, датата и еднократен номер. Този подпис доказва пред банката, че точно тази карта е одобрила точно тази сума.
Най-умното в EMV е, че всяка транзакция е уникална. Дори ако някой прихване сигнала между чипа и терминала, той не може да го използва повторно — подписът е обвързан с еднократен код, който никога не се повтаря. Така клонирането на чип-карта е практически невъзможно, докато клонирането на магнитна лента беше тривиално.
Следващата стъпка беше безконтактното плащане (NFC). Когато допрете карта или телефон до терминал, се изпълнява още по-сложен протокол, но с по-бърза размяна. За допълнителна сигурност Apple Pay и Google Pay въведоха токенизация: вашият истински номер на карта никога не се изпраща до търговеца. Вместо това всяка поръчка получава уникален еднократен „токен", който замества номера и е валиден само за тази транзакция. Дори ако базата данни на търговеца бъде хакната, истинските ви карти остават в безопасност.
Статистиката показва колко ефективни са тези мерки. Преди EMV, САЩ (които закъсняха с прехода чак до 2015 г.) имаха ниво на измами с клонирани карти над 60 центa на 100 долара плащания. След EMV тази стойност спадна под 5 цента. Това са милиарди долари годишно, спестени благодарение на криптографията — и безброй неприятни разговори с банки, които иначе биха последвали.
Една приложна забележка: паролите, които всеки ден ни тормозят
На всекидневно ниво повечето хора се сблъскват с криптографията чрез пароли. Това е едно от най-старите приложения — и парадоксално, едно от най-уязвимите. Ако паролата ви е „123456" или „парола", никоя математика не може да ви защити. Съвременните криптографски добри практики препоръчват дълги пароли с минимум 16 знака или — още по-добре — парольни фрази, съставени от няколко несвързани думи.
Зад кулисите работи цяла верига от криптографски инструменти: паролите се съхраняват като резултат от специална бавна хеш функция (bcrypt, Argon2, scrypt), към тях се добавя случаен „сол" (salt) срещу таблични атаки, а самата връзка между клиента и сървъра обикновено се защитава чрез TLS. Цялото това сложно поведение остава невидимо за потребителя — което е най-добрата похвала за една технология.
Ключови моменти в историята на криптографията
- Юлий Цезар използва шифър на отместване за военната си кореспонденция — първият документиран криптографски метод.
- Ал-Кинди в Багдад развива честотния анализ — първото системно криптоаналитично средство.
- Леон Батиста Алберти предлага полиалфабетен шифър — основата на шифъра на Виженер.
- Писмата на Мария Стюарт са разшифровани от Томас Фелипс — тя е екзекутирана година по-късно.
- Блез дьо Виженер описва „неразбиваемия шифър", който ще устои 3 века.
- Чарлз Бабидж в тишина разбива шифъра на Виженер (неговата работа остава непубликувана).
- Фридрих Касиски публикува метод за разбиване на Виженер — краят на полиалфабетната ера.
- Огюст Керкхоф формулира принципа, че сигурността трябва да зависи само от ключа, не от тайната на метода.
- Работата на Върнам и по-късното развитие на идеята водят до модела One-Time Pad — класически пример за шифър със съвършена тайна.
- Британците разшифроват телеграмата Цимерман; САЩ влизат в Първата световна война.
- Артур Шербиус патентова първата Enigma машина.
- Полските и британските криптоаналитици разбиват Enigma в Блечли Парк.
- Фридман и екипът му разбиват японската машина Purple след 18 месеца усилия.
- Навахо радистите използват родния си език като изключително труден за разчитане военен код.
- Клод Шанън публикува „Communication Theory of Secrecy Systems" — математическата основа на съвременната криптография.
- Дифи и Хелман публикуват „New Directions in Cryptography" — раждане на криптографията с публичен ключ.
- Ривест, Шамир и Адлеман създават RSA в нощта на 5 април.
- DES е приет като федерален стандарт на САЩ.
- Ади Шамир и Джордж Блейкли независимо предлагат схеми за разделяне на тайни.
- Коблиц и Милър независимо предлагат криптография с елиптични криви; Голдвасер, Микали и Рейкоф формулират zero-knowledge доказателства.
- Фил Цимерман публикува PGP — първата масова силна криптография за обикновени потребители.
- Основаване на cypherpunk мейлинг-листата в Сан Франциско.
- EMV стандартът е публикуван; Шор открива квантовия си алгоритъм; Netscape разработва SSL.
- Пол Кохер демонстрира timing атаки срещу криптографски реализации.
- Британското правителство разсекретява работата на Клифърд Кокс от 1973 г. за RSA.
- AES (Rijndael) става федерален стандарт, замествайки DES.
- Сатоши Накамото публикува Bitcoin — първа блокчейн валута, използваща цифрови подписи.
- Крейг Джентри представя първото пълно хомоморфно шифроване.
- Разкритията на Сноудън дават тласък на масовото HTTPS-иране; появява се Signal Protocol; скандалът Dual_EC_DRBG.
- Let's Encrypt започва публично да издава безплатни сертификати и прави силната криптография масово достъпна; през 2016 г. NIST обявява публичния конкурс за пост-квантова криптография.
- SIKE — пост-квантов кандидат — е разбит с метод от 380 години.
- NIST публикува първите пост-квантови стандарти: FIPS 203, 204, 205; Apple въвежда PQ3 за iMessage.
- HQC е избран като пети пост-квантов стандарт за алгоритмично разнообразие.
Защо това е една от най-красивите идеи в науката
Когато през 58 г. пр.н.е. Юлий Цезар измествал буквите с три позиции, той едва ли е подозирал, че принципът, който използва, ще се развие до мрежа от математически идеи, които два хилядолетия по-късно ще защитават всеки наш разговор, всяка транзакция, всяка дума, която пишем в интернет. Когато Ал-Кинди системно броял честотата на буквите в арабските ръкописи, той не е могъл да си представи, че неговите идеи един ден ще водят до разбиването на нацистки тайни в английско имение. Когато Бабидж разбивал Виженер, той не е очаквал, че машината, която проектира едновременно с това, ще стане един от далечните предшественици на компютрите, които сто години по-късно ще разбият Enigma.
Историята на криптографията е история на една безкрайна надпревара между две страни на едно и също умение — способността да се крие и способността да се открива. Всеки нов код ражда нова криптоанализа; всяка нова криптоанализа ражда по-сложен код. Но зад това съперничество стои нещо по-дълбоко: постоянното откритие, че правилната математика може да превърне нещо привидно невъзможно — двама непознати да си споделят тайна през публичен канал — в нещо напълно тривиално.
В едно интервю за Quanta Magazine от 2020 г. Рон Ривест споделя, че криптографията дълго е била изкуство, а не наука — с неточни методи и неверифицирани твърдения. Едва с появата на строга математическа основа тя се превърнала в дисциплина, на която може да се вярва. И точно тогава, по думите му, станала красива. — по интервю с Рон Ривест, Quanta Magazine (2020)
И може би най-дълбокото в историята на криптографията е това: че тя е единствената област, в която чистата математика среща буквалната нужда на милиарди хора всеки ден. Всеки пост в социалните мрежи, всяко видеообаждане с близките, всяко прошепване в интимен чат — всички те минават през математически конструкции, за които повечето хора не знаят. Числата вършат невидимата работа, която пази личното в живота ни.
Квантовите компютри идват, но математиците вече са подготвили отговора. Решетки в многомерно пространство, грешки в линейни уравнения, забележителни свойства на хеш функции — всичко това, което изглежда абстрактно в учебника, утре ще пази вашите деца, когато пишат първите си имейли. Едно е сигурно: числата ще продължат да пазят тайните ни. Само формата, в която го правят, ще продължи да се променя.
Източници
- Plus Magazine (University of Cambridge). Maths in a minute: Cryptography. 12 February 2025. plus.maths.org
- Honner, P. How Does Math Keep Secrets? Quanta Magazine, 1 August 2024. quantamagazine.org
- Houston-Edwards, K. How Public Key Cryptography Really Works. Quanta Magazine, 15 November 2024. quantamagazine.org
- Singh, S. Safety in numbers. Plus Magazine, Issue 21. plus.maths.org (PDF)
- Ekert, A. Cracking codes. Plus Magazine. plus.maths.org
- Plus Magazine. Exploring the Enigma. plus.maths.org
- Plus Magazine. Elliptic cryptography. plus.maths.org
- Plus Magazine. Post-quantum cryptography. plus.maths.org
- Plus Magazine. Lattice-based cryptography. plus.maths.org
- Klarreich, E. Mathematicians Seal Back Door to Breaking RSA Encryption. Quanta Magazine, 17 December 2018. quantamagazine.org
- Brubaker, B. Post-'Quantum' Cryptography Scheme Is Cracked on a Laptop. Quanta Magazine, 24 August 2022. quantamagazine.org
- NIST. NIST Releases First 3 Finalized Post-Quantum Encryption Standards. 13 August 2024. nist.gov
- NIST. NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption. 11 March 2025. nist.gov
- NIST. What Is Post-Quantum Cryptography? nist.gov
- Alagic, G. et al. Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process. NIST IR 8545, 2025.
- Cloudflare. Prepping for post-quantum: a beginner's guide to lattice cryptography. blog.cloudflare.com
- Cloudflare. State of the post-quantum Internet in 2025. blog.cloudflare.com
- Cloudflare. Cloudflare targets 2029 for full post-quantum security. blog.cloudflare.com
- Rivest, R. L., Shamir, A. & Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), February 1978, 120–126.
- Diffie, W. & Hellman, M. New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), November 1976, 644–654.
- Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), 1997, 1484–1509.
- Koblitz, N. Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 1987, 203–209.
- Miller, V. Use of Elliptic Curves in Cryptography. Advances in Cryptology — CRYPTO '85, Springer, 1986, 417–426.
- NSA. Solving the Enigma: History of the Cryptanalytic Bombe. nsa.gov (PDF)
- Gardner, M. A new kind of cipher that would take millions of years to break. Scientific American, August 1977, 120–124.
- Hinsley, F. H. The Influence of ULTRA in the Second World War. Lecture at Cambridge University, 1993.
- Al-Kadi, I. A. The origins of cryptology: The Arab contributions. Cryptologia, 16(2), 1992, 97–126.
- Quanta Magazine. Cryptography Pioneer Seeks Secure Elections the Low-Tech Way. Interview with Ronald Rivest, 12 March 2020. quantamagazine.org
- Shannon, C. E. Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(4), 1949, 656–715.
- Kerckhoffs, A. La cryptographie militaire. Journal des sciences militaires, vol. IX, 1883, 5–83.
- Daemen, J. & Rijmen, V. The Design of Rijndael: AES — The Advanced Encryption Standard. Springer, 2002.
- Goldwasser, S., Micali, S. & Rackoff, C. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1), 1989, 186–208.
- Gentry, C. Fully Homomorphic Encryption Using Ideal Lattices. STOC 2009, 169–178.
- Kocher, P. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO 1996, 104–113.
- Nakamoto, S. Bitcoin: A Peer-to-Peer Electronic Cash System. 2008. bitcoin.org (PDF)
- Marlinspike, M. & Perrin, T. The Double Ratchet Algorithm. Signal Technical Specification, 2016.
- Regev, O. On lattices, learning with errors, random linear codes, and cryptography. STOC 2005, 84–93.
- Shamir, A. How to Share a Secret. Communications of the ACM, 22(11), 1979, 612–613.
- Blakley, G. R. Safeguarding cryptographic keys. Proceedings of the National Computer Conference, 1979, 313–317.
- Friedman, W. F. The Friedman Lectures on Cryptology. NSA Declassified. nsa.gov (PDF)
- NSA. The SIGABA / ECM II Cipher Machine: "A Beautiful Idea." nsa.gov (PDF)
- Scientific American. Cryptography: How to Keep Your Secrets Safe. scientificamerican.com
- Scientific American. How Cryptographic 'Secret Sharing' Can Keep Information Safe. scientificamerican.com
- Schneier, B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. 2nd edition, John Wiley & Sons, 1996.
- Singh, S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Anchor Books, 1999. (Подробен разказ за Мария Стюарт, Виженер, Enigma и още.)
- Apple Security Research. iMessage with PQ3: The new state of the art in quantum-secure messaging at scale. 2024.
- Signal. Quantum Resistance and the Signal Protocol. 2023.
- Tuchman, B. W. The Zimmermann Telegram. Viking Press, 1958.
- Kahn, D. The Codebreakers: The Story of Secret Writing. Macmillan, 1967. (Класическата енциклопедия на историята на криптографията.)
- Hughes, E. A Cypherpunk's Manifesto. 1993. activism.net
- Levy, S. Crypto: How the Code Rebels Beat the Government, Saving Privacy in the Digital Age. Penguin, 2001.
- National Museum of the American Indian. Navajo Code Talkers: World War II Fact Sheet. Smithsonian Institution. americanindian.si.edu
- EMV Co. EMV Integrated Circuit Card Specifications for Payment Systems. emvco.com
- Schmeh, K. The Pathology of Cryptology: A Current Survey. Cryptologia, 2012. (Преглед на нерешени ръкописи, вкл. Voynich.)
- Santos, C. et al. The Voynich Manuscript: Computer Analysis. Proc. SPIE, 2020.
- Singh, S. From Arsenal to RSA: An interview with Marcus du Sautoy. Plus Magazine. plus.maths.org
Още от поредицата „Любопитно от математиката“
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Прием в университети в чужбина (ISEE, SAT, A-Level)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар