A quiet change to RSA

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

Комментарии (35)

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