Hacker News Digest

RSA-алгоритм изначально использовал функцию Эйлера φ(n), но со временем её заменили на функцию Кармайкла λ(n). Это изменение незаметно для пользователей, но оно важно: λ(n) делит φ(n) и может уменьшить приватный ключ в 2-3 раза, что ускоряет расшифровку. Однако экономия невелика, так как gcd(p-1, q-1) почти всегда равен 2 или 4.

• Обсуждение поднял вопрос о том, что многие курсы и преподаватели обучают RSA без должного фундамента в теории чисел, что может привести к неправильной реализации.
• Участники обсудили, что вместо того, чтобы вводить студентов в детали реализации RSA, включая использование функции Кармайкла и алгоритма Гарнера, часто вместо этого преподают поверхностное понимание алгоритма, что может в будущем привести к небезопасной реализации.
• Также было отмечено, что вместо того, чтобы обучать эллиптическим кривым, которые более современны и просты в реализации, продолжают преподавать RSA, который требует более глубокого понимания теории чисел.
• Несколько участников выразили обеспокоенность тем, что студенты, обучающиеся по таким курсам, могут в будущем реализовывать небезопасные системы, из-за недостаточного понимания криптографических основ.
• В конце обсуждение сошлось на то, что вместо того, чтобы пытаться упростить обучение криптографии, следует требовать от студентов, что они выучат необходимые математические основы, так как в отсутствии этого они не смогут правильно реализовать безопасные системы.

Почему квантовые компьютеры всё ещё не разложили 21 на множители?

В 2001 году удалось разложить 15, но к 2025-му 21 остаётся «недоступным». Это не из-за отсутствия прогресса, а из-за взрывного роста сложности схемы.

• Схема для 15 требует всего 21 запутывающий двух-кубитный гейт (6 CNOT/CPHASE + 2 Toffoli, каждый из которых эквивалентен 6 CNOT).
• Схема для 21 содержит 191 CNOT и 369 Toffoli, то есть ≈ 2405 запутывающих гейтов — в 115 раз больше.

Три причины такой разницы:

1. Большинство констант при 15 равны 1, поэтому умножения «пропускаются».
2. Первое умножение почти бесплатно, так как аккумулятор известен.
3. Оставшееся умножение на 4 по модулю 15 сводится к двум CSWAP.

Для 21 все восемь умножений нужны, и каждое требует полноценного модульного умножения. Даже после агрессивной оптимизации схема остаётся на два порядка дороже.

• Квантовые компьютеры пока не факторизуют даже 21 без «подсказок»; эксперименты с 15 обошлись лишь потому, что задача свелась к сдвигам.
• Для RSA-2048 оценивается ≈ 7 млрд Toffoli-гейтов и миллионы логических кубитов с коррекцией ошибок; RSA-1024 всё ещё вне досягаемости.
• Реальные препятствия — экспоненциальный рост шума и количества физических кубитов, а не просто масштабирование схемы.
• Основной практический путь — квантовая химия и симуляция, а не взлом криптографии; «пост-квантовые» алгоритмы уже снижают мотивацию строить «крипто-разрушители».
• Общий вывод: полезные квантовые вычисления в XXI веке возможны, но факторизация крупных RSA-ключей остаётся гипотетической.