Сегодня, в день защиты информации, хочу поговорить об одном из самых популярных алгоритмов шифрования данных на сегодняшний день - алгоритме RSA, основанном на элементарной математике.
Итак, алгоритм шифрования RSA строится на очень простом принципе. Не будем погружаться в детали, просто в общих чертах определим, что это такое.
При шифровании методом RSA, если рассматривать его самую базовую версию, используется два ключа - открытый и закрытый:
Открытый ключ содержит два числа (А и B). Этот набор можно показать всем.
Закрытый ключ содержит числа (С и B). Его должен знать только тот, кому предназначаются данные.
Таким образом, единственное, что удерживает данные от раскрытия - это число С. Но его можно получить из B и А. Про B известно, что оно раскладывается на произведение двух простых чисел. Найдя эти два простых множителя числа B, число С ищется уже довольно легко. И, в общем-то всё. Дальше - только механика делимостей и остатков от деления, которая нам тут в данной статье не очень важна.
Так в чём же тогда смысл шифрования?
Ведь можно просто перебрать множители числа B и подобрать ключ! Если я знаю, что число B - это, например, 247, я вижу, что оно на 2 не делится, на 3 не делится, на 5 не делится, на 7 (кто помнит признак делимости на 7?) - тоже не делится, на 11 не делится, на 13... О! На 13 делится. Получилось 19. Второе простое число. Как только я узнал простые множители далее не очень сложным перебором находится число С. Могу рассказать как именно в следующий раз, если хотите)
Если вы сможете подобрать два простых множителя, которые при произведении дают B, вы откроете любые двери, прочтёте любые сообщения в интернете, снимете деньги с любого счёта в любом банке! И число B вам будет передано в открытую. Просто подберите множители!
Но вы не можете.
Пока ещё.
Потому что в качестве числа B используются очень большие числа. Самый надёжный алгоритм RSA на сегодня, использует 617-значные числа в качестве B.
Вам может показаться, что 617 знаков - это не очень-то много. Вернее, много, но не умопомрачительно.
Да, это так. Но давайте проведём простую симуляцию.
Возьмём числа от маленьких к большим и будем раскладывать их на множители. Не на простые, а просто на множители - это чуть более простая операция, но затраты времени на неё сопоставимы. Посчитаем, сколько времени уйдёт на нахождение множителей различных чисел. Посмотрим, как быстро мы сможем раскладывать числа на множители и как быстро у нас начнутся вычислительные проблемы.
Напишем небольшую программку и визуализируем на графике.
По горизонтали - количество знаков в числе
По вертикали - количество затраченных секунд на нахождение всех делителей.
Ну что же, видно, что уже на 20-значных числах приходится ждать не секунды, а минуты (190 секунд последнее вычисление из тех, которых я дождался). И это время растёт экспоненциально. В рамках эксперимента, 21-значного числа я не увидел. Остановил выполнение через 7 минут работы над ним. Конечно, можно было бы запустить программу на ночь и подождать, но при таком резком замедлении процесса при увеличении чисел, очевидно, что даже 30 знаков для текущей программы, пусть даже неоптимальной, и для текущего слабенького компьютера - недостижимы. Почему?
Что именно мы делаем в данном конкретном случае? Мы берём число U и перебираем все числа от 1 до √U, проверяя каждое, делится ли на него U?
Почему именно до корня? Представьте себе число 36.
Перебираем числа, на которые делится 36:
1 (36:1 = 36)
2 (36:2 = 18)
3 (36:3 = 12)
4 (36:4 = 9)
6 (36:6 = 6)
А дальше - можно не смотреть. Ведь следующее число - это 9. А мы его уже находили, когда рассматривали делитель 4. Так что перебор можно осуществлять не по всем числам, а только до корня. Это несколько ускоряет алгоритм. Но, как видно, недостаточно. Мы всё равно делаем √U операций. Это очень много. Для нахождения делителей 100-значного числа, придётся сделать ~50-значное количество операций. А для 600-значного числа, ~300-значное количество операций. Именно поэтому работа так сильно замедляется с увеличением чисел.
Очень быстро становится неинтересно смотреть и новые строчки не появляются. А из предыдущего абзаца понятно, что замедление при добавлении каждого следующего разряда, будет колоссальным.
Таким образом, разложить 617-значное число на простые множители - это задача настолько неподъёмная, что за её решение даже выдаются немалые денежные вознаграждения, но никто не может с этим справиться. Пока.
Как вообще эту задачу решать? Если этим займётся один человек на одном компьютере, ему понадобятся тысячелетия.
Поэтому, эту задачу решают сразу сотни компьютеров.
Просто последовательно раскладывают на простые множители всё большие и большие числа на многих компьютерах по всему миру, собирают эту информацию друг у друга и, в конце-концов, по текущим прогнозам, к 2030 году, алгоритм станет теоретически небезопасным, потому что уже достаточная масса чисел будет факторизована (разложена на простые множители)
Например, сейчас разложены на простые множители уже 250-значные числа. Много, но, как видите, есть ещё над чем работать.
А что будет потом? А потом количество знаков в алгоритме просто увеличат. Это делали уже много раз.
Первые числа, используемые при шифровании RSA были 100-значными. Но их научились раскладывать на множители ещё в 1991 году.
С каждым годом каждый следующий знак даётся всё сложнее, так что пока наши данные в безопасности. А когда перестанут быть в безопасности, увеличим количество знаков и снова будет всё хорошо. И так - до бесконечности.
Так могло бы быть.
Если бы не квантовые компьютеры.
С начала 2000-х годов нарастают квантовые мощности, которые позволяют раскладывать на простые множители гораздо быстрее. Гораздо быстрее!
При текущей интерпретации квантовой механики (та самая мультивселенная), считается, что квантовые вычисления производятся сразу в миллиардах параллельных вселенных и в нашу вселенную мгновенно проскакивают уже результаты миллиардов миллиардов таких вычислений, сделанных не здесь. Вы думаете, это сказочки? Почитайте Дэвида Дойча. Всё вполне научно, хоть и совершенно непонятно обывателю. Я вот - тоже обыватель, мне тоже непонятно) Но это работает.
Например, 617-значное число квантовый компьютер разложит на простые множители, при помощи так называемого алгоритма Шора, за 8 часов. И после этого, увеличивать количество знаков станет бесполезно. Потому что на 800 знаков квантовому компьютеру понадобится ещё несколько часов. А на 2000 знаков ещё пара дней. Считать RSA безопасным станет невозможно ни при каких размерах чисел.
Одна лишь загвоздка заключается в том, что для такой операции квантовым компьютерам нужно ещё немного помощнеть. 8-часовой взлом всех шифров на земле будет произведён квантовым компьютером, обладающим 20 млн. кубитов (квантовые биты).
А самый мощный квантовый компьютер, существующий на сегодняшний день - гордый обладатель всего лишь 433 кубитов.
Так что прямо сейчас, в 2023 году, наши данные и правда в безопасности и будут в этом состоянии ещё какое-то время.
Но эта квантовая угроза, несомненно, проявит себя в перспективе ближайших 20-30 лет. Ведь количество кубитов в квантовых компьютерах нарастает с ускорением.
Ну а пока - можете смело нажимать "сохранить пароль"/"сохранить банковскую карту" в своём браузере.
Пока ещё можно)