Методът за факторизация на Ферма се превърна в заплаха за RSA – почти 400 години след изобретяването му

Малко математика от 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 години по-късно идеята му ще бъде полезна в свят, в който изчисленията се извършват с помощта на квантовата механика.