Малко математика от 1600 г. може да направи това, което

Малко математика от 1600 година може да направи това, което хората изпращат на принтера, по-уязвимо.

В началото на 2022 година експертът по осведомителна сигурност Хано Бьок откри, че някои способи за криптиране могат да бъдат кракнати. По-късно той разказва този способ в обява от 2023 година в електронния списък Cryptology ePrint на Международната асоциация за криптологични проучвания. Интересно е, че корените на този способ могат да бъдат проследени до работата на френския академик Пиер Ферма от XVII век.

Ферма е най-известен със своята загадъчна „ последна теорема “, която от дълго време озадачава математиците. Но през целия си живот той е оставил доста потребни открития – положил е основите на теорията на вероятностите, работил е доста с простите цифри, т.е. тези, които се разделят единствено на 1 и на самите себе си.

Математиците от дълго време подозират, че концепциите на Ферма могат да се приложат за разбиването на шифрите, и Бьок показва по какъв начин това работи на процедура.

Съвременните системи за криптиране се основават на комплицирани математически задания. По създание те са като брава: без съответния ключ е невероятно да я „ отворим “. Един от най-разпространените способи е RSA криптографията, която разчита на свойствата на простите цифри. Разлагането на едно доста огромно число на елементарни множители не е лесна задача, ето за какво тези цифри са доста подобаващи за въпросните ключове.

Простите цифри постоянно се назовават атомите на теорията на числата – всички останали естествени цифри са „ построени “ от тях. Всяко число може да бъде показано като неповторимо произведение от елементарни цифри: да вземем за пример 15 = 3 × 5, а 20 = 2 × 2 × 5. За дребните цифри това е елементарно, само че пробвайте се да разложите, да речем, 7 327 328 314 и бързо ще разберете, че никоя стратегия не може да го направи за рационално малко време.

Именно на това ограничаване се основава RSA. За да разберем по какъв начин работи, дано си представим един елементарен образец. Да предположим, че някой желае да криптира думата SCIENCE, която има седем букви. Той взема седемцифрено число, да вземем за пример 6 743 214, и измества всяка писмен знак от думата със съответния брой позиции: S се измества с 6 и става Y, C се измества със 7 и става J и така нататък Резултатът е думата CJMHPDI. Тя може да бъде изпратена до получатела – никой по пътя няма да разбере, че това е SCIENCE (НАУКА).

Получателят обаче би трябвало да може да декриптира истинското известие. За задачата той се нуждае или от самия ключ (6 743 214), или от опцията да го възвърне. Директното предаване на ключа е рисковано: нападателят може да го прихване. Ето за какво в RSA ключът се основава от обществено налична информация: изпращачът и получателят поотделно употребяват две огромни елементарни цифри, умножават ги и обменят единствено резултата. Без да се знаят първичните елементарни цифри, ключът не може да се получи, а разлагането на това произведение на множители е прекомерно комплицирана задача. (Действителният логаритъм RSA е по-сложен, само че правилото е почти същият.)

Преди съвсем 400 години Ферма към този момент е размишлявал върху разлагането на числата на елементарни множители – тогава от чист интерес, тъй като криптографията към момента не е съществувала.

И той в действителност е намерил метод за разложение на огромните цифри, състоящи се от два елементарни множителя. Методът не е комплициран – с него може да се оправи даже елементарният калкулатор (какъвто Ферма, несъмнено, не е имал). За да впечатли съвременниците си, Ферма употребявал цифрата n = 2 027 651 281.

Същността на метода е следната: вземаме цифрата n и извличаме корен от него. Обикновено това е нецелочислено число – в този случай √2,027,651,281 ≈ 45,029.45. Закръгляме до 45 030, повдигаме го на квадрат и изваждаме n: 45 030² – 2 027 651 281 = 49 619. Проверяваме дали това е квадратът – не е.

Затова дано опитаме още веднъж: вземаме 45 030 + 1, повдигаме го на квадрат и изваждаме n: 45 031² – 2 027 651 281 = 139 680. Отново не е в квадрат. И по този начин нататък.

Очевидно Ферма е бил толерантен. В неговия образец би трябвало да повторите процедурата 12 пъти, до момента в който получите: 45 041² – 2 027 651 281 = 1 040 400 = 1 020².

Какво дава това? Получаваме два квадрата: 45 041² и 1 020², чиято разлика е n. Това подхожда на формулата: y² – x² = n, или (y – x)-(y + x) = n. И това към този момент е факторизация (разлагане на множители): n се разлага на (45 041 – 1 020) = 44 021 и (45 041 + 1 020) = 46 061. И двете стойности са елементарни цифри.

Формално този способ работи за всяко нечетно n. Но има един колорит: компютрите се оправят бързо с факторизацията единствено когато двата елементарни множителя са близки по стойност. Бьок се възползва от тази уязвимост: в една от известните библиотеки, употребявани от разнообразни компании, простите цифри се генерират неслучайно – те постоянно са прекомерно близо едно до друго. Което значи, че методът на Ферма е подобаващ за навлизане.

Бьок разкрил, че криптирането на някои производители на принтери работи точно по този метод. Така да вземем за пример RSA – само че с уязвими ключове – се употребява за отбрана на документите, изпратени за мрежови щемпел. След откриването на казуса през 2022 година производителите издадоха предизвестия, уточнения и актуализации за отстраняването му. Можем единствено да се надяваме, че и другите компании са отстранили други сходни уязвимости.

Така или другояче, през идващите години мнозина ще би трябвало да премислят метода си към криптирането. Дори в случай че стандартните компютри не могат да се оправят с факторизирането на огромните цифри, квантовите компютри могат. Едва ли Ферма си е представял, че съвсем 400 години по-късно концепцията му ще бъде потребна в свят, в който изчисленията се правят благодарение на квантовата механика.