Рейтинг:0

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

флаг pk

Допустим, мне нужен определенный уровень безопасности (например, 128 бит) при использовании ECIES, но я также хочу свести к минимуму общение. Влияет ли используемая эллиптическая кривая на размер открытого ключа? Если это имеет значение, каково текущее состояние эллиптических кривых и как они соотносятся с популярными эллиптическими кривыми, такими как Curve25519 или secp256k1?

kelalaka avatar
флаг in
[Вы проводили какое-либо исследование?] (https://crypto.stackexchange.com/questions/80601/what-is-the-key-length-of-shared-secret-by-curve-25519-ecdh) Curve25519 имеет 32 байт для ECDH, а secp256k1 имеет 33 байта для сжатого...
poncho avatar
флаг my
@kelalaka: для ECIES вам не нужна координата y, поэтому для любого из них будет 32 байта ...
kelalaka avatar
флаг in
@poncho да, именно так, поскольку координата $y$ для ECDH не нужна. 33 байта — это стандартный размер открытого ключа Биткойн.
флаг pk
@kelalaka Да, я знаю, что curve25519 использует 32-байтовый ключ, но мне было интересно, есть ли какая-нибудь кривая, которая работает лучше? Я только что прочитал [это] (https://crypto.stackexchange.com/questions/59573/information-theoretical-lower-limit-on-the-size-of-public-and-private-keys) и задался вопросом, есть ли какие-либо кривая делает лучше. Насколько я понимаю, это невозможно, но я не эксперт, и я не мог найти никого, утверждающего это (возможно, это очевидно), поэтому я ищу здесь.
kelalaka avatar
флаг in
Что вы имеете в виду, когда говорите лучше? Общая атака на Dlog снижает безопасность до 128 бит для Curve25619. Вы хотите более низкий уровень безопасности? Настройте свой уровень безопасности и умножьте его на два, ищите такую ​​безопасную кривую на кривых безопасности. Почему 32 байта для вас много? По сравнению с RSA это дешево хранить.
флаг pk
Я должен был уточнить, лучше с точки зрения размеров ключей. Я знаю, что это большое улучшение по сравнению с RSA, но я делаю приложение, в котором пытаюсь минимизировать память, насколько это возможно, сохраняя при этом тот же уровень безопасности.
kelalaka avatar
флаг in
Используйте https://www.keylength.com/en/compare/, чтобы решить, что вам нужно!
Рейтинг:1
флаг my

Если это имеет значение, каково текущее состояние эллиптических кривых и как они соотносятся с популярными эллиптическими кривыми, такими как Curve25519 или secp256k1?

Хорошо, если у вас есть эллиптическая кривая с большой подгруппой размера $q$ (что является простым числом), то мы знаем, как вычислить дискретный логарифм внутри этой подгруппы в $O(\sqrt{q})$ время, и это относится ко всем эллиптическим кривым (фактически ко всем группам).

Итак, чтобы сделать эту атаку $2^{128}$ время, нам нужен $q \приблизительно 2^{256}$.

А по теореме Хассе для простой кривой характеристики $р$, у нас есть $p + 2\sqrt{p} > q$, или другими словами, наименьший $р$ может быть около 256 бит.

Стандартный способ представления открытого ключа — дать $х$ координата как целое число; это значение от 0 до $p-1$; то есть 256-битное значение.

Следовательно, выбор кривой, отличной от Curve25519, secp256k1 или P256, ничего нам не даст; либо эта альтернативная кривая снизила бы безопасность, либо имела бы открытый ключ, который был бы как минимум таким же большим.

О единственном, что можно попробовать придумать урезанный способ передачи $х$ координата; один простодушный подход состоял бы в том, чтобы всегда выбирать $х$ согласовывать с $к$ биты 0 вверху (и просто не передавать те $к$ биты явно); поиск такого ключа с использованием выборки отклонения займет $ О (2 ^ к) $ время и сэкономил бы $к$ бит - возможно, выполнимо, если вам нужно сохранить байт или два - очевидно, невозможно сохранить больше. Я не знаю более умного подхода к поиску открытых ключей, который соответствует аналогичной технике экономии места.

Ответить или комментировать

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