Post #217

Современная криптография стоит на двух математических столпах, которые кажутся простыми, но на деле чрезвычайно сложны для вычисления Факторизация: детская игра, которая ставит в тупик суперкомпьютеры Факторизация — это разложение числа на простые множители Помните школьную математику? Число 12 раскладывается на 2×2×3, число 15 — на 3×5 Просто, правда? А теперь попробуйте разложить на множители число 2057 Не так-то легко! Придётся перебирать делители: 2, 3, 5, 7, 11... Оказывается, это 29×71 Теперь представьте число длиной в 2048 битов — это примерно 617 цифр! Именно такие числа использует криптосистема RSA Даже самые мощные суперкомпьютеры тратят тысячи лет, чтобы разложить подобное число на множители Почему это так сложно? Нет эффективного алгоритма Приходится проверять делители один за другим, а их количество растёт экспоненциально с размером числа Это как искать иголку в стоге сена размером с галактику Дискретный логарифм: ещё одна непобедимая задача Представьте простую операцию: 2 в степени 10 равно 1024 Легко посчитать! А теперь обратная задача: в какую степень нужно возвести 2, чтобы получить 1024? Это и есть логарифм В обычной арифметике логарифмы вычисляются просто Но в модульной арифметике всё меняется кардинально Пример: Возьмём число 3 и будем возводить его в разные степени по модулю 17: 3¹ = 3 (mod 17) 3² = 9 (mod 17) 3³ = 10 (mod 17) 3⁴ = 13 (mod 17) ... Легко вычислить, чему равно 3¹⁰⁰ по модулю 17 Но если дать вам результат — скажем, 13 — сможете ли вы быстро сказать, в какой степени нужно возвести 3, чтобы получить 13 по модулю 17? Это и есть задача дискретного логарифма Почему эти задачи важны Вся современная криптография основана на односторонних функциях — операциях, которые легко выполнить в одну сторону, но практически невозможно обратить Схема RSA использует факторизацию: легко перемножить два больших простых числа, но крайне трудно разложить результат обратно Ваш открытый ключ содержит произведение, а секретный — сами множители Алгоритмы на эллиптических кривых используют дискретный логарифм: Легко «умножить» точку на кривой на большое число, но найти это число по результату — задача на миллионы лет вычислений Реальные масштабы сложности Чтобы понять масштаб проблемы, представьте: если бы каждый атом во Вселенной был компьютером, и все они работали бы с момента Большого взрыва до сегодня, то они всё равно не смогли бы разложить на множители 2048-битное число классическими методами Именно поэтому банки спокойно используют RSA, правительства доверяют эллиптической криптографии, а ваши пароли надёжно защищены Математика работает как непробиваемый щит Что изменят квантовые компьютеры Но есть одна проблема Алгоритм Шора, работающий на квантовом компьютере, может решить обе эти задачи за разумное время Факторизация 2048-битного числа займёт не тысячи лет, а считанные часы Это означает, что как только появятся достаточно мощные квантовые компьютеры, вся существующая криптография станет бесполезной Именно поэтому уже сейчас математики всего мира работают над постквантовой криптографией — новыми задачами, которые будут сложны даже для квантовых машин Факторизация и дискретный логарифм — это два математических титана, которые уже четверть века держат на себе всю цифровую безопасность Но их время подходит к концу