Сравнение ECDSA и RSA

Введение

В последнее время было много дискуссий о плюсах и минусах RSA[01]
и ECDSA[02], в крипто сообществе. Для непосвященных, они два
наиболее широко используемые алгоритмы цифровой подписи, но даже для более технологичных
Сообразительный, это может быть довольно трудно идти в ногу с фактами. Эта статья
попытка упрощения сравнения двух алгоритмов. Хотя это не
глубоко техническое эссе, тем нетерпеливее читатель может проверить конец
статья для быстрого TL; DR таблицы с резюме обсуждения.

ECDSA против RSA

ECDSA и RSA - это алгоритмы, используемые криптография с открытым ключом[03] системы,
обеспечить механизм для идентификация, Криптография с открытым ключом является
наука о разработке криптографических систем, использующих пары ключей: что такое варган?
ключ (отсюда и название), которые могут быть свободно распространены среди всех
соответствующий закрытый ключ, который известен только его владельцу. Аутентификация
относится к процессу проверки того, что сообщение, подписанное закрытым ключом, было
созданный владельцем определенного закрытого ключа. Алгоритмы, используемые для
аутентификация все вместе известны как алгоритмы цифровой подписи [04].

Такие алгоритмы основаны на сложных математических задачах, которые относительно просты
рассчитать в одну сторону, хотя и совершенно нецелесообразно для обратного. Это означает, что для
злоумышленник, чтобы подделать цифровую подпись, без каких-либо знаний частного
ключ, они должны решать сложные математические задачи, такие как целое число
факторизация, для которой не существует известных эффективных решений [05].

В связи с этим, поскольку нет эффективных решений, доступных для
лежащие в основе математических задач, оценка криптографических алгоритмов может
происходят только в отношении деталей их реализации в сочетании с
уровень безопасности, который они обеспечивают. Для этого в этом разделе представлены
сравнение RSA и ECDSA с использованием пяти (или шести) количественных метрик. Каждая метрика
вводится в своем собственном разделе, а также его значение для тех, кто
пытаясь сделать выбор между двумя алгоритмами.

Принятие

RSA уже много лет является отраслевым стандартом криптографии с открытым ключом
в настоящее время. Большинство SSL /TLS сертификаты были (и остаются) подписаны ключами RSA.
Хотя большинство ЦС к настоящему времени внедрили поддержку ECDSA на основе
сертификаты, это долгосрочное принятие привело ко многим устаревшим системам только
поддержка RSA. Поэтому, если поставщик требует обратной совместимости со старым
клиентское программное обеспечение, они вынуждены использовать сертификаты, подписанные с RSA. В наше время,
тем не менее, большинство современных клиентов внедрили поддержку ECDSA, которая
вероятно, удалите это ограничение совместимости в ближайшем будущем.

Стандартная зрелость

RSA был сначала стандартизирован для SSL /TLS в 1994 году [06], в то время как ECDSA была введена
в спецификации TLS 1.2 в 2008 году [07]. Эта разница в возрасте указывает на
несоответствие в зрелости стандартов, которые описывают лучшие практики для
каждый алгоритм. Хотя стандарты RSA были тщательно исследованы и
проверено, ECDSA не видела такого большого внимания. В последнее время пропаганда этого
алгоритм основных центров сертификации и его принятие в большинстве современных SSL /TLS клиенты имеют
привело к опубликованию более обширного исследования, но оно все еще остается
относительно новая схема. Это оставляет место для необнаруженных недостатков дизайна или
ошибочные реализации будут раскрыты в будущем.

Соотношение размера ключа к уровню безопасности

Уровень безопасности [08] является метрикой в ​​криптографии, относящейся к силе
криптографического примитива или функции. Обычно измеряется в «битах»,
обозначает количество операций, которые злоумышленник должен выполнить, чтобы скомпрометировать его
безопасность. Этот показатель может обеспечить количественный метод для сравнения эффективности
различных криптосистем. Следует подчеркнуть, что размер открытого ключа также
измеряется в битах, но это совершенно другая концепция, относящаяся к
физический размер ключа.

В связи с этим общий 2048-битный открытый ключ RSA обеспечивает уровень безопасности
112 бит Однако ECDSA требует только 224-битных открытых ключей для обеспечения
тот же 112-битный уровень безопасности. Эта поразительная разница в размере ключа имеет два
значительные последствия. Для установки ключей меньшего размера требуется меньшая пропускная способность
SSL /TLS поток, что означает, что сертификаты ECDSA идеально подходят для мобильных
Приложения. Более того, такие сертификаты могут храниться в устройствах с большим
более ограничивающие ограничения памяти, факт, который позволяет m /TLS стеки быть
реализовано в устройствах IoT без выделения большого количества ресурсов. опубликованный
исследования даже показывают, что ECDSA более эффективно [09] для реализации во встроенных
устройств.

Производительность и временная сложность

Алгоритмы - это абстрактные рецепты, описывающие метод достижения определенной цели.
В информатике их производительность измеряется путем подсчета количества
элементарные операции, которые необходимы для достижения этого заранее определенного окончания
состояние. Такая метрика называется сложность времени, С разным материалом
размеры требуют различного количества операций, сложность времени обычно
выражается как функция от размера ввода.

Оба алгоритма, о которых идет речь, работают примерно одинаково
математические операции, такие как деления и умножения. Таким образом, размер ввода
(который в данном случае является размером их ключей) остается наиболее значимым
фактор, влияющий на их производительность. Сравнивая два алгоритма, необходимо
Различают подпись сообщения и проверку подписи. В большинстве
В практических реализациях RSA кажется значительно быстрее, чем ECDSA в
проверка подписей, хотя это медленнее при подписании.

Вещи усложняются для более высоких уровней безопасности. Например, в большинстве
общая конфигурация уровня безопасности 112 бит, RSA требует 2048 бит
по сравнению с ECDSA нужны 224-битные ключи. В следующем общем уровне 128 бит, RSA
требуется 3072-битный ключ, в то время как ECDSA только 256-битный. Это приводит к RSA
производительность резко снизится, тогда как ECDSA затронута лишь незначительно. Так как
следствием этой проблемы масштабирования, хотя RSA кажется более производительным на
На данный момент непрерывное повышение требований безопасности вполне может сделать
ECDSA де-факто решение в будущем.

Постквантовое сопротивление

Алгоритм Шора [10] - это хорошо известный алгоритм взлома ключей RSA с использованием
квантовые компьютеры. Поскольку нет (публичных) практических реализаций
такая машина, следующее является гипотезой о будущем открытого ключа
криптография. На момент написания этой статьи лучшая реализация Шора
Алгоритм может победить 15-битный ключ шифрования RSA. Хотя это не звучит
относительно, поскольку все больше исследований направлено на квантовые вычисления, RSA
могут быть серьезные проблемы в любое время.

Сторонники ECDSA не должны спешить праздновать, потому что эллиптические
кривая криптографии также уязвим [11] к модифицированной версии Шора
алгоритм. Следовательно, если оба шифра могут быть взломаны квантовым компьютером,
единственная объективная метрика - сложность, необходимая для реализации такого
атака. Согласно общедоступным исследованиям, 2048-битные ключи RSA требуют 4098 кубитов
(и 5.2 трлн. ворот Тофолли) должны быть побеждены, тогда как ECDSA 256-битные ключи
требуется только 2330 кубитов (и 126 млрд. ворот Тофолли). Следовательно, RSA больше
дорого ломать, используя теоретическую квантовую машину.

Заключение

Хотя это сравнение ни в коем случае не является исчерпывающим, очевидно, что
RSA по праву завоевал свою позицию ведущей цифровой подписи
алгоритм для большинства приложений сертификатов. Тем не менее, поскольку технология всегда
продвижение более непредсказуемым образом, осведомленность о безопасности и потребности также
растет. Чуть более десяти лет назад безопасность встроенных устройств была
художественная литература и в наше время безопасные коммуникации необходимы для любого реального мира
применение. В результате, даже если ECDSA относительно молодой, это чей-либо
угадайте, заменит ли он RSA в качестве стандарта для аутентификации в SSL /TLS
Реализации.

Если вы, читатель, все еще не можете решить, какой алгоритм выбрать, есть
решения для поддержки ECDSA и RSA (в качестве резервного механизма) до
крипто сообщество выбирает победителя. Проверьте этот раздел статьи на будущее
руководство

TL; DR стол

Рекомендации

• [01] Алгоритм RSA
• [02] Алгоритм ECDSA
• [03] Криптография с открытым ключом
• [04] Алгоритмы цифровой подписи
• [05] NP сложность
• [06] SSL v.0.0 RFC
• [07] TLS версия 1.2 RFC
• [08] Уровень безопасности
• [09] RSA против ECC для встраиваемых систем
• [10] Алгоритм Шора
• [11] Квантовые оценки ресурсов для ECDL