Сегодняшняя тема - КРИПТОГРАФИЯ, наука о кодах, взломах и шифрах. И мы рассмотрим, пожалуй, самый главный и самый распространенный в мире способ шифрования - который называется RSA. Именно этот способ шифрования лежит в основе современного интернета. Именно он защищает онлайн банки, банковские карты и все сайты с адресом, начинающимся на HTTPS://
Школьная задачка - RSA
Такие сайты надежно защищены, и любые данные - которыми Вы обмениваетесь с такими сайтами - не могут быть перехвачены посередине (например, Вашим интернет провайдером). Но самое интересное - что в основе этого всемирного шифрования лежит простая школьная задачка для 5-ого класса. Как только в начальной школе дети научатся делить числа - они быстро поймут - что есть такие числа, которые ни на что не делятся, кроме самих себя и единицы. Эти числа называются “простые” в противовес обычным числам - “составным”.
Вот эти числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ….
Ирония судьбы состоит в том, что “простые” числа на самом деле самые сложные на свете и никому не известна точная закономерность их распределения среди всех чисел.
А теперь задачка для 5-ого класса:
возьмем 2 простых числа и перемножим их, например 137 и 199
решение:
137*199=27263 - делается элементарно в столбик за 1 операцию, под силу любому 5-и класснику
А теперь задачка обратная:
по числу 27263 найти те исходные числа, из которых оно образовано.
решение:
эта задача несоизмеримо сложнее первой, ведь для ее решения надо перебрать все возможные делители числа 27263 и на каждый из них сделать попытку деления. Т.е. сначала надо попробовать поделить 27263 на 2, потом на 3, потом на 4 и т.д. до 27262.
Как видим - прямая задачка потребовала 1 операцию умножения, а обратная требует 27261 операций деления.
Искушенный читатель заметит, что достаточно дойти всего лишь до половины - до числа 13631 в попытках деления, математик скажет что достаточно проверить до корня квадратного из 27263 - т.е. до 165. Но даже при таком раскладе это в 165 раз сложнее прямой задачки 5-ого класса.
Но изначально мы могли брать не 3-х значные простые числа, а скажем 100 значные простые (числа со 100 цифрами) - и тогда обратная задача даже для математика с его квадратным корнем была бы сложнее уже в 100 значное число раз (в 1 и 100 нулей раз)!!! И перебрать 1 и 100 нулей попыток деления немыслимо даже для самого мощного суперкомпьютера.
Сообщения в интернете шифруются за доли секунды, перемножая гигантские простые числа - но все-таки всего за 1 операцию. А для расшифровки требуется по огромному составному числу узнать его простые компоненты. И количество операций, нужных для этого, превышает возраст Вселенной в секундах.
Никто не умеет быстро раскладывать числа на простые множители. Никто не придумал быстрого способа решить задачку уровня 5-и классника. И задача эта остается нерешенной уже более 2-х тысяч лет со времен древних греков.
На том стоит криптография в интернете.
Создатели алгоритма шифрования RSA с момента его создания в 1970 и по настоящий момент - это группа из нескольких математиков из одного из американских университетов. С момента создания алгоритма в качестве патента за использования они получают 1 млрд долларов в год. Это пример того, как математика и программирование сами по себе могут приносить огромные деньги.
Эллиптические кривые (ECC)
Может возникнуть логичный вопрос - ну взломают к примеру когда-нибудь RSA, ну вкрутим другое шифрование интернета, делов-то. Что их мало - что ли алгоритмов похожих на RSA? Да, таких очень мало. Эти алгоритмы используются по системе "открытый ключ" и называются ассиметричными алгоритмами шифрования. И их всего 2, в отличие от симметричных - которых бесконечно много. Но для шифрования интернета нужны именно асимметричные. 2-ой асимметричный алгоритм - это эллиптические кривые (ECC)
И над обоими алгоритмами домокловым мечом весят квантовые компьютеры. Если не удастся изобрести классический способ взлома - то квантовый их оба взломает.
Насколько взлома шифрования RSA с помощью квантового алгоритма ШОРА приблизит нас ко взлому эллептических кривых? Ведь именно они сейчас все больше заменяют повсюду RSA в асимметрическом шифровании? Кстати, почему? Например, в протоколе TLS (основной транспортный протокол) тоже уже не RSA, а эллиптические кривые
1. Алгоритм Шора и RSA
Алгоритм Шора — это квантовый алгоритм, который решает задачу факторизации целых чисел и вычисления дискретного логарифма экспоненциально быстрее, чем классические алгоритмы. А RSA, как известно, держится именно на трудности факторизации больших чисел. Поэтому, когда у нас появится достаточно мощный квантовый компьютер, RSA будет полностью скомпрометирован.
2. Алгоритм Шора и эллиптические кривые (ECC)
Вот ключевой момент: алгоритм Шора взламывает и ECC тоже.
ECC основана на дискретном логарифме на эллиптической кривой (ECDLP). Это аналог дискретного логарифма в мультипликативной группе (классический DLP), только вместо целых чисел используется группа точек на эллиптической кривой. А алгоритм Шора может эффективно решать любую задачу дискретного логарифма, включая ECDLP, если есть достаточное количество кубитов и низкий уровень ошибок.
Вывод: как только появится достаточно мощный квантовый компьютер — и RSA, и ECC — оба пойдут "в утиль". Они оба рухнут примерно одновременно.
3. Почему тогда переходят с RSA на ECC прямо сейчас, если это всё равно временно?
Очень логичный вопрос. Причины практичные:
➤ ECC более эффективна на классических машинах:
- Для того же уровня безопасности ECC требует гораздо меньших ключей.
RSA-2048 ≈ ECC-224 по уровню защиты.
RSA-3072 ≈ ECC-256. - Это значит: меньше трафика, быстрее операции, меньше затрат на вычисления — очень важно для мобильных устройств и IoT.
➤ RSA теряет актуальность из-за своей "тяжеловесности":
- Подписи, шифрование, верификация у RSA медленнее.
- Большие ключи хуже масштабируются и перегружают инфраструктуру (например, в TLS).
➤ ECC уже хорошо стандартизирован (например, через [Curve25519, NIST P-256 и др.]) и легко внедряется в существующие протоколы (TLS 1.3, SSH, Signal).
Что насчёт постквантовой криптографии?
Раз RSA и ECC не выживут в эпоху квантовых компьютеров, уже сейчас разрабатываются PQ (Post-Quantum) алгоритмы:
Lattice-based (например, Kyber, Dilithium — победители конкурса NIST PQC)
Code-based (например, Classic McEliece)
Hash-based (например, SPHINCS+)
TLS уже тестирует гибридные схемы, которые объединяют ECC и постквантовые алгоритмы: например, X25519+Kyber.
По итогу
На своих уроках я научу Вас не только программировать, но и использовать математику для придания реального смысла таким фантастическим закономерностям нашего мира, как простые числа. Сама природа породила такие удивительные законы - запрограммировав которые Вы не только заработаете много денег, но и сможете изменить мир.
Вы можете поддержать автора тут
____________________________________________________________________________________
Привет! Меня зовут Александр Бескодаров, я математик, программист, учитель по призванию.
Как математик обладаю бесценным опытом преподавания в одной из 5-и сильнейших математических школ Москвы - 179-ой.
Как программист являюсь действующим разработчкиком, руководителем разработки образовательной системы PANGEYA с элементами Искусственного Интеллекта.
В своей работе использую уникальную методику преподавания "ВСЕ В ЗАДАЧАХ", которая стимулирует ученика самого изобрести изучаемую область знаний с целью 100% усвоения информации. То, что человек сам придумал - он никогда не забудет и будет понимать до конца.
1.Заходите на мой сайт https://beskodarov.xyz
2.Записывайтесь на мои уроки через Telegram: https://t.me/beskodarovAV
3.Или по номеру телефона +7 977 145 47 27 (Whatsapp,Telegram)
4.Подписывайтесь на мой телеграмм канал, чтобы быть в курсе новых интересных фактов по математике и программированию https://t.me/superteachertg
5.Читайте отзывы обо мне на сайте profi.ru