RSA vs Elliptic Curve

RSA 4096

Тормоза на ровном месте.

работает даже на говне мамонта

Для говна мамонта можно оставить RSA-ключ.

новомодных кривых

Они были новомодными сколько лет назад? Десять? ECDSA уже успел устареть.

ECDSA уже успел устареть.

Мне казалось, что устарел только DSA.

Что, ректально-термический криптоанализатор уже удалось обойти?

Если стоит вопрос выбора - выбираю RSA всегда. Но иногда не глядя дефолт а там и EC бывает.

Повсеместная агитация за EC без технических на то обоснований (время, затраченное на ssh-логин, очевидно таковым не является) вызывает подозрение в наличии заинтересованных лиц.

У курв как минимум плюс в длине ключа. Он и правда одну строку в authorized_keys занимает и можно перенести на бумажке и перепечатать.

Да, вот тоже подозрения какие-то. В теории, EC более устойчив к перебору квантовыми суперкомпьютерами в будущем. Но на практике, что мешает уже сейчас использовать более длинный ключ RSA? А мощности устройств, позволяют использовать RSA алгоритмы, без настолько сильной просадки.

А с технической точки зрения, в чем преимущества?

Да, отдельный физический токен, который намеренно ломаешь, если тебе настойчиво выбивают дверь. Дальше можно сколько угодно ковырять тебя паяльником.

От китайских ботов брутящих ssh защита от него не нужна. Большинство пользователей неуловимые Джо и защита идёт от автоматизированных атак. Терморектальных криптоанализатор пока не автоматизирован.

И вообще, ничего же не изменилось, с момента написания статьи?

Теперь возникает следующий вопрос: откуда берутся случайные порождающие значения для кривых NIST? Ответ: к сожалению, мы не знаем. Эти значения не имеют никакого обоснования.

Возможно ли, что NIST обнаружил «значительно большой» класс слабых эллиптических кривых, попробовал различные возможные варианты порождающих значений и нашёл уязвимую кривую? Я не могу ответить на этот вопрос, но это закономерный и важный вопрос. Мы знаем, что NIST как минимум успешно стандартизировал уязвимый генератор случайных чисел (генератор, который, как ни странно, основан на эллиптических кривых). Возможно, он успешно стандартизировал и множество слабых эллиптических кривых? Как это проверить? Да никак.

А проверка анононимуса показывает следующее:

Команда для измерения скорости работы алгоритмов в OpenSSL v1.1.1: openssl speed -seconds 5 -multi 12 ecdsap384 ecdsap256 ed25519 rsa2048 rsa3072 rsa4096. Ключ -multi 12 означает, что тест распараллеливается по 12 процессам. Тест выполнялся на сервере с двумя процессорами Intel® Core™ i7-6900K, всего 16 ядер или 32 потока. Результат:

                  sign    verify    sign/s verify/s
rsa 2048 bits 0.000074s 0.000002s  13565.2 491119.6
rsa 3072 bits 0.000211s 0.000004s   4749.4 241443.6
rsa 4096 bits 0.000474s 0.000007s   2107.9 142365.4
                              sign    verify    sign/s verify/s
 256 bits ecdsa (nistp256)   0.0000s   0.0000s 367450.0 124632.8
 384 bits ecdsa (nistp384)   0.0001s   0.0001s   8689.6  11658.6
                              sign    verify    sign/s verify/s
 253 bits EdDSA (Ed25519)      infs   0.0000s      0.0 199860.0

Авторы Википедии считают, что RSA с ключом 3078 бит соответствует эллиптической кривой над полем с характеристикой размером 256 бит:for example, a 256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key. Получается, RSA в два раза быстрее вычислений над эллиптической кривой. Вычисления над кривой Эдвардса более чем на 60% производительнее вычислений над эллиптической кривой, но всё равно не дотягивает до RSA.

Моя история SSH-ключиков:

• ~1998-2001: RSA-1024 или DCC? Уже не помню.
• ~2002-2009: RSA-2048
• ~2010-2020: RSA-8192 (всё норм было, делал так сказать с запасом)
• ~2020-…: ED25519-256

RSA-1024 сегодня выводят из употребления, однако их взлом произвольных RSA-1024 ключей всё ещё усложнён до предела.

https://en.wikipedia.org/wiki/RSA_numbers#RSA-1024

RSA-1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604
           859533833940287150571909441798207282164471551373680419703964191743046496589
           274256239341020864383202110372958725762358509643110564073501508187510676594
           629205563685529475213500852879416377328533906109750544334999811150056977236
           890927563

Разложите это число и получите $100,000, чтобы опровергнуть

А как ты выбираешь простые числа для RSA? На сколько в используемом тобой софте большая вариативность в их выборе?

В некоторых сертификатах до сих пор RSA-2048 и норм.

Разложите это число и получите $100,000, чтобы опровергнуть

Ага, щщас. Дружище, у тебя совершенно точно нет свободных $100,000.

А RSA открестилась от продолжения челленджа ещё в 2007. После того, как в 2005 были факторизованы сразу RSA200 и RSA640. Всего–то на нескольких стойках обычного серверного железа (не специализированных числомотилок!). В течении нескольких месяцев (не лет!).

С тех пор каждые несколько лет кто–нибудь расковыривает очередное задание из исходного пула RSA, но астрономических наград за это уже не выплачивают.

В наши дни вычислительные мощности стало возможным арендовать в практически неограниченных объёмах. Поэтому доступны такие развлечения далеко не только госам и крупным институтам. Вопрос лишь в том, окупится ли мероприятие.

Оба варианта так себе. RSA будет поломан квантовым компьютером рано или поздно, т.е. долгосрочно им шифровать (для холодного хранилища) что-то шляпная идея. Эпилептические кривые - слишком агрессивно их втюхивают в крипто/иб сообществах. Такое чувство что есть какая-то математика, известная некоему/неким заинтересованному лицу/заинтересованным лицам, которая позволяет на лету проводить дешифровку. Т.е. всё зависит от степени твоей паранойи. Если от соседа Васи, то вообще пофиг у него нет и не будет в ближайшие годы квантового компа, как и доступа к интересной математике, если от кого посерьёзнее, то я бы 10 раз подумал, как по мне и первое и второе не очень. Лучше правда ничего не посоветую.

вызывает подозрение в наличии заинтересованных лиц.

Так-то оно может быть и так, но потом ты просыпаешься и вспоминаешь, что президент США со своими подчиненными ведут переписку в сигнале и слуйчайно приглашают к себе какого-то прохожего. Вспоминаешь, как Хиллари Клинтон в своём туалете разместила личный незашифрованный почтовый сервер, где, как госсекретарь, вела всю переписку. Вспоминаешь, как на СВО пользовались дискордом и продолжают пользоваться телеграммом, потому что ГОСТовское хуже, чем мессенджеры для игрулек и прочего.

Так что, если эти заинтересованные где-то есть, то только на Нибиру, не иначе. Среди нас идиотов, таких молодцов нет.

… Вспоминаешь, как на СВО пользовались дискордом и продолжают пользоваться телеграммом, потому что ГОСТовское хуже, чем мессенджеры для игрулек и прочего.

Потому что своего просто нет. … Поэтому на средства собранные волонтёрами строят системы связи на базе коммерческого DMR стандарта.

Каком ещё выборе? Их не выбирают, их генерируют рандом-генератором. Вопросы могут быть только к алгоритму проверки простоты, я до конца не понял на чём основано заявление что он без ложных срабатываний.

По алгоритму Шора циферки там: https://arxiv.org/abs/1706.06752

По алгоритму Регева оценок не видел. Но и предложен он был недавно, пару лет назад. Да, тем самым Регевым, который придумал LWE шифрование на решётках.

Со старомодных эллиптических кривых все разбрегаются кто куда.

В этом и проблема – как выбирают.

Алгоритм выбора этих пар, алгоритм проверки простоты… Если просто случайно брать большое число и проверять его на простоту, то ты довольно долго будешь перебирать составные числа (асимптотика количества простых чисел меньше x = x/ln(x)). Соотв. ты выбираешь кандидатов по какому-то заранее известному, зашитому в твой софт алгоритму, соответственно, это должно резко сужать круг простых чисел, которые ты используешь в схеме.

Вот про это я и спрашивал – какая там вариативность в софте при выборе пар больших простых чисел.

ни в чем :)
несимметричный ключ используется крайне редко, для запуска и обновления длинного симметричного сессионного ключа. криптография давно уж хибридная. выигрыш м-м-м-м наверн вычислить можно…

256 битный ECDSA сколь помню используется в биткоине.
и мильён бетховенов лежащих в «первых» кошельках Сатоши почему-то до сих пор лежат, ~милъярд доларов я думаю хорошая цена за нахождения закрытого ключа :) но что-то вот никто не торопитца

то ты довольно долго будешь перебирать составные числа (асимптотика количества простых чисел меньше x = x/ln(x)).

Так оно и перебирает долго. Ты когда-нить openssl genrsa запускал?

Если rsa4096 то надо сгенерировать пару примерно 2048-битных чисел. ln (2^2048) = 1420 - вот столько чисел надо перебрать в среднем. Не так уж и много, при том что всякие деления на 2 3 5 7, очень быстрые, сразу отсеивают этот список в 4-5 раз, остаётся около 300, чем он собственно и занимается заметное время.

Меня больше интересовало, каким образом он надёжно проверяет что число не делится на какое-нить другое простое 1000-битное. Там есть какие-то «признаки», даже со ссылками на литературу, но они выглядят вероятностными а не 100% гарантирующими. Надо вникать во всю эту математику чтобы дать точный ответ.

Алгоритм тут https://github.com/openssl/openssl/blob/master/crypto/bn/bn_prime.c

хм. ну в целом, да. Вероятность найти с первой попытки 1/1024, для критерия трех сигм получим вполне небольшое значение.

Вероятностная проверка на простату довольно быстрая, меньше O(n).

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

PS: в коде коммент что тест Миллера-Рабина делается для вероятности 2^-256 ложноположительного срабатывания.

Если ложно положительное срабатывание, т.е. ты посчитал число простым, а оно не простое, то схема шифрования может привести к необратимому результату, т.е. невозможности расшифровки, для некоторых данных, это можно проверить на этапе шифрования (если эти твои данные такие удачные) и тогда все хорошо – ты выбираешь другую пару чисел

Мне кажется шанс запороть данные из-за непростого числа примерно обратно пропорционален множителю, который из него можно выделить (например шифруемый блок должен делиться на этот множитель без остатка или что-то похожее). То есть если взять произведение четырёх 1024-битных чисел вместо двух 2048-битных - никаких повреждений данных ты никогда не заметишь, но вот взломать такое будет проще т.к. настоящая битность шифра снижена в 2 раза. Вот если там маленький множитель (16-битный), то это быстро обнаружится, но такой на этапе генерации гарантированно отсеивается. Если что, это всё мои домыслы и на практике я это не тестировал, но скорее всего так и есть.

Да, шанс запороть ничтожен.

В целом, шанс, что при выборе 2048 битного шифрования ты получишь хотя бы одно не простое число меньше, чем 2^-254, шанс, что ты при этом получишь факторизацию с множителем меньше 256 бит, мне кажется, будет меньше 2^-512.

Мне когда-то говорили, что шанс, что тебе в комнату влетит метеорит в ближайший час больше, чем 2^-64. Поэтому, подобной вероятностью можно пренебрегать. Опять же, надежность вычислений в процессоре хуже.

Прочитал блог. Думаю, Ed25519 можно использовать.

Вместо ECDSA теперь рекомендуют Ed25519

У меня один ключ ECDSA (надо бы его тоже поменять, но влом), остальные Ed25519. Проблем кроме как с древним говном или махровым энтерпрайзом - нет.

Если у тебя где-то есть свичи из середины 2010-ых, то там вполне может царствовать RSA и никаких позиций не сдавать. И дай б-г чтобы хотя бы 2048 бит поддерживалось.

В противном случае на всех актуальных Linux/Windows(как там у BSD - хз, не проверял) уже давно Ed25519 работает хорошо, быстро и стабильно.

Есть ли смысл перекатываться на elliptic curve ключи?

да. эллиптическая криптография существует лет 35, больше, чем существовал RSA, когда его начали активно использовать в интернете

для меня, пока, RSA простой, надёжный, работает даже на говне мамонта.

у RSA при этом есть вагон проблем, начиная с того, что textbook RSA небезопасен, проблемы PKCS паддинга тоже известны, как справедливо сказали, выбор простых непрост (см., например https://factorable.net/weakkeys12.conference.pdf), длинные ключи, типа RSA 4096, работают медленно.

В отличии от новомодных кривых.

«новомодные» кривые неновомодны, математика достаточно хорошо изучена, не обязательно выбирать P256, если параноики про АНБ, можно выбрать 25519, можно выбрать Brainpool. Проблема генерации случайного числа на каждую подпись существует, но проблема генерации случайного числа в любом случае существует на практике, если нужен PFS. При этом, работает быстрее, с паддингом проблем нет.

И ECC, и RSA одинаково нестойки к Шору, тут принципиальной разницы нет.

проверка на простату довольно быстрая

Чувак, ты сделал этот день!

Ну так, если целыми днями канпелять, можно заработать простатит. Потому проверка на простату, должен уметь каждый линуксоид. Что бы не обращаться к проприеритарным врачам.

Я не верю всему тому что выливают в СМИ. Мало-ли что там рассказали для прессы.

Повсеместная агитация за EC без технических на то обоснований (время, затраченное на ssh-логин, очевидно таковым не является) вызывает подозрение в наличии заинтересованных лиц.

Анон с опеннета в модных хешах заподозрил неладное: https://www.opennet.ru/openforum/vsluhforumID10/5638.html

Некоторый софт пока элиптику не поддерживает, по этому системное Integrity сидит все на RSA.

Коню уже понятно, что закладки есть всюду. Можно использовать два или больше вложенных шифрования, например ГОСТ с AES. И веровать, что мы действительно поругались с США настолько, что алгоритмы расшифровки не передаём…

Коню уже понятно, что закладки есть всюду

Какие ваши доказательства?

Исходя из давних традиций «эшелонов», «пяти глаз», …. чувствуется, что без быстрого и простого для аппаратной реализации, алгоритма расшифровки стандартизацию AES не пройти. ;)

AES - быстрый, имеет аппаратное ускорение и для шифрования дисков, трафика Вася его использует (оставляет выбор по умолчанию).

Думается сегодня надо копать в сторону дополнительных слоев шифрования другим стандартом. Например, дополнительно шифровать /home и VPN между офисами не AES. При этом использовать стандартное полнодисковое шифрование и шифрование на уровни приложения AES.

По аналогии с ключами. Создавать минимум два ключа в разных стандартах и заверять их кросиподписями. Подписывать обеими ключами.

RSA в целом не взломан. 2048 битов хватает с запасом, 4096 битов хватает с огромным запасом. То же и про EC алгоритмы можно сказать. Поэтому принципиальной разницы между ними нет.

Из проблем RSA можно указать то, что в реализации алгоритмов легко допустить ошибку, которая приведёт к компрометации системы. С EC в этом плане проще. Поэтому, несмотря на то, что в целом всё нормально, современные криптографы рекомендуют использовать EC.

Из других преимуществ EC можно отметить небольшие ключи и более высокую скорость работы.

В общем и целом, если использовать надёжный отлаженный софт вроде OpenSSH, то выбирать можно исключительно из личных предпочтений. Для реализации своих протоколов лучше выбирать EC.

А в связи с предположительным приходом квантовых компьютеров, стоит задумываться уже и о пост-квантовой криптографии. И RSA и EC взламываются гипотетическими квантовыми компьютерами.

чувствуется

Криптоаналитика на вайбах, понятно.

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

Из проблем RSA можно указать то, что в реализации алгоритмов легко допустить ошибку

Ошибка в RSA (если ты неправильно реализуешь умножение/возведение в степень длинных чисел) сразу устроит тебе битые данные. Небитые данные но ослабленное шифрование может быть только если ошибка в генераторе ключа. Что же касается высокоуровневого алгоритма то RSA максимально тривиален и где там можно ошибиться не представляю.

С EC в этом плане проще. Поэтому, несмотря на то, что в целом всё нормально, современные криптографы рекомендуют использовать EC.

Так что вот это ^ враньё. Зачем?

И RSA и EC взламываются гипотетическими квантовыми компьютерами.

А мой гипотетический магический компьютер взламывает даже одноразовые xor-шифры.

Тем не менее, AES это стандарт для защиты гостайны в США, и там такие решения принимают не бэкдоролюбы из NSA, а более вменяемые люди из DoD. То, что спецслужбы готовы пожертвовать безопасностью своих граждан, включая высшее руководство, ради возможности прослушки в широком смысле, для меня всегда было и будет дичью. Больные люди.

думаю это дурацкое желание (не финансово, не технологически не обоснованое) проталкнуть свою хрень (имя), ну может заработать на внедрении.

вменяемые люди из DoD

Создали «эшелон», «пять глаз», … родили и воспитали АНБ, …

спецслужбы готовы пожертвовать безопасностью своих граждан, включая высшее руководство, ради возможности прослушки в широком смысле

Прослушивая ВСЕХ, включая высшее руководство, спецслужбы СОЗДАЮТ безопасность!

А с вашим шифрованием какая безопасность будит? Никакой! Одни террористы, наркодилеры, бандиты с агентами ВСУ разведутся и прочие угрозы национальной безопасности…

Вспомнил слова из выступления британского премьера в Брюсселе, где он заявил: «шифрование которое нельзя расшифровать надо запретить!!!». Вот что значит умный человек, который разбирается в безопасности. А глупых, которые в безопасности не разбираются, на верх уже давно во всем мире не пропускают.

Average Elliptic Curve Fan vs Average RSA Enjoyer :P

https://blog.trailofbits.com/2019/07/08/fuck-rsa/ тут можно почитать, почему лучше избегать RSA.

Если вкратце - можно неудачно выбрать параметры, можно неправильно реализовать выравнивание и все эти проблемы повторяются раз за разом в разном ПО, т.е. это не теоретические опасения, а опыт исследования проблем в существующих программах.

Иными словами использование RSA это хождение между множества разложенных граблей. Если ты эксперт в криптографии или твой код просмотрят достаточно экспертов в криптографии, то можно и так делать. Или же использовать готовые качественные реализации высокого уровня вроде протокола TLS с реализацией вроде OpenSSL, где все проблемы решены за тебя, тебе остаётся лишь подавать и принимать незашифрованные данные в библиотеку.

Если вкратце - можно неудачно выбрать параметры, можно неправильно реализовать выравнивание и все эти проблемы повторяются раз за разом в разном ПО, т.е. это не теоретические опасения, а опыт исследования проблем в существующих программах.

вкратце вся статья: нужен хороший генернатор белого шума (случайных чисел) и всё.

Нет. Генератор случайных или псевдо-случайных чисел нужен практически для любой криптографии.

Если вкратце - можно неудачно выбрать параметры

Не «параметры» а «приватный ключ» (параметры - это у DH, он очень похож на RSA, но он используется не для шифрования, а для генерации приватного ключа на лету, для другого шифра). Ну и собственно да, приватный ключ надо генерировать аккуратно (я в предыдущем сообщении с этим уже согласился, зачем ещё раз повторять?), иначе он может оказаться слабым. Но генератор ключей почти всегда используется openssl-ный, даже если твоя реализация на openssl не основана (как например openssh).

Иными словами использование RSA это хождение между множества разложенных граблей.

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

Если ты эксперт в криптографии или твой код просмотрят достаточно экспертов в криптографии, то можно и так делать.

Нет, экспертом тут быть не требуется. Эксперт - это тот, кто может самостоятельно придумать надёжный криптографический алгоритм с нуля (как авторы RSA), или хотя бы провести криптоанализ имеющегося (видимо, профессиональный математик с уклоном в эту область). Я например, ни первое ни второе не умею. Но соблюсти элементарные меры предосторожности может любой более-менее разумный программист.

Нет, экспертом тут быть не требуется.

Ну да, а потом «более-менее разумный программист»© ухитряется из готовой криптографии сделать непонятное говно.

Глянул https://ru.onlinemschool.com/math/library/divisibility_rule/#h8 и смогу легко написать прогу сплошного поиска точных простых чисел перебором без пропусков начиная с любого большого рнадомного числа.

1. Вопросы их можно как параметры для создания приватного ключа где-то использовать?
2. Как посмотреть простые числа своего приватного и публичного ключей, для проверки их простоты?
3. Сколько времени у меня займет поиск простого числа для RSA8000, RSA16000? Прога на питоне в лоб.

Из того, что по ссылке, большие простые числа ты не сделаешь. Проверка делимости на всё подряд в лоб у тебя займёт примерно бесконечное время, даже для RSA512.

хотя бы провести криптоанализ имеющегося (видимо, профессиональный математик с уклоном в эту область)

Нет, мне кажется это сложно. Читал пару статей математиков по крыптоанализе неких алгоритмов. Все равно что ЛОР почитать. Так просто, с наскока, современную криптуху взять сложно.