Регистрация Войти
Рейтинг:2
James avatar Crypto

Криптография на основе эллиптических кривых

флаг br
James

Я новичок в изучении криптографии на эллиптических кривых, и поэтому я могу спросить что-то с мирским решением, но я не могу легко найти такое решение в Интернете. Насколько я понимаю ECC, вы можете сгенерировать закрытый ключ (некоторый целочисленный $к$), начальная точка на кривой ($G$) и уравнение кривой, а затем сгенерировать открытый ключ, найдя $кГ$. Насколько я понимаю, ваш компьютер будет выполнять любое количество операций, необходимых для поиска $кГ$ (если $к$ было 16, то это было бы четыре операции).

С этими данными отправная точка $G$, уравнение кривой и открытый ключ становятся общедоступными. Мне интересно, почему злоумышленник не может попытаться узнать, что такое закрытый ключ? $к$ просто есть, взять начальную точку и выполнять операции до тех пор, пока они не достигнут открытого ключа и, таким образом, знать, что $к$ является? Основано ли оно на том, что отправителю нужно всего 4 операции для вычисления $кГ$ тогда как злоумышленнику потребуется 16 операций (для данного примера)?

1127
1 + 7
флаг ca
MaiaVictor
Вам нужно угадать закрытый ключ, прежде чем вы начнете выполнять операции. Если мы говорим о 256-битных закрытых ключах, можно попробовать 2^256 ключей. Вы достигнете открытого ключа цели, только если угадали правильный закрытый ключ. Это означает, что если вы выбираете случайный закрытый ключ и выполняете операции, надеясь получить открытый ключ цели, существует только «0,0000000000... (+66 нулей)... 8» шансов на успех за попытку.
1
Ответить
James avatar
флаг br
James
Но если компьютеру пользователя, например, потребовалось 10 вычислений для вычисления открытого ключа (упрощенный пример), компьютеру злоумышленника нужно было бы только начать с $G$ и выполнить около 1024 вычислений, чтобы достичь точки $kG$. Я вижу, что это потенциально довольно большая разница, но похоже, что суперкомпьютер может выполнить более крупный пример за конечное время (недели или около того).
0
Ответить
dave_thompson_085 avatar
флаг cn
dave_thompson_085
Для размеров, которые в настоящее время считаются безопасными (256 или 255 бит), эта «атака» требует больше энергии, чем существует во Вселенной. Вам нужно контролировать огромное количество — триллионы триллионов — других вселенных, а это значит, что вы должны быть богом, а ваш профиль не идентифицирует вас как бога. См. https://crypto.stackexchange.com/questions/58373/how-to-calculate-a-private-key-from-public-key-on-elliptic-curve и другие ссылки.
1
Ответить
fgrieu avatar
флаг ng
fgrieu
См. притчу [пшеница и шахматная доска](https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem), только с большей шахматной доской, когда дело доходит до фактически используемых эллиптических кривых (где $k$ может занять $n\приблизительно2^{ 256}$ значений). Кстати, «брать исходную точку и выполнять операции, пока они не достигнут открытого ключа» — далеко не лучшая стратегия: при $n$ возможных значений $k$ требуется $\Theta(n)$ шагов, когда есть являются стратегиями, требующими всего $\Theta(\sqrt n)$ шагов.
3
Ответить
флаг jp
user253751
@James Хорошо, а что если компьютеру пользователя потребовалось 256 вычислений для вычисления открытого ключа? Сколько вычислений должен сделать компьютер злоумышленника?
0
Ответить
PrincePolka avatar
флаг cn
PrincePolka
"Это основано на том факте, что отправителю нужно всего 4 операции для вычисления kG, тогда как злоумышленнику потребуется 16 операций (для данного примера)?" Да
1
Ответить
James avatar
флаг br
James
Спасибо за все примеры и ответы. Я понимаю, как быстро эта упрощенная атака становится вычислительно нежизнеспособной.
0
Ответить
Рейтинг:5
jjj avatar Crypto
флаг cn
jjj

Вычислить $кГ$ тебе нужно $ О (лог (к)) $ операции. (Для каждого бита удвоить результат и дополнительно добавить $G$ если бит $1$). Как вы упомянули в комментарии около $к=1024$ вам нужно как $10$ операции для вычисления $кГ$. Но этот пример слишком мал для практического использования, и экспоненциальный эффект еще не проявляется. Обычно, когда кривая имеет порядок вокруг $2^n$, $к$ будет такой же величины, как $2^n$.

Итак, для кривых с порядком $2^{256}$вам нужно вокруг $лог(2^{256})=256$ операции для вычисления $кГ$ но $2^{256}$ атаковать его. Есть только проблема с абсурдно маленькими кривыми порядка нескольких миллиардов или триллионов (как в вашем примере).

0 + 3
AAA avatar
флаг nl
AAA
Вы можете добиться большего, чем $2^{256}$. Вы можете использовать baby-step gigan-step, чтобы восстановить $k$ примерно за $2^{128}$ времени. Тем не менее, точка зрения верна: для вычисления $kG$ требуется полиномиальное время, но самые известные атаки требуют экспоненциального времени для восстановления $k$.
3
Ответить
James avatar
флаг br
James
Если мы можем сказать, что, например, компьютер может вычислить 80 000 000 000 операций в секунду (восемьдесят компьютеров выполняют операцию каждую наносекунду), что составляет примерно $2^{36}$ операций в секунду, и самые быстрые атаки могут найти ключ в операциях $2^{n/2}$, где $n$ — размер ключа, не будет ли размера ключа 138 достаточным, чтобы по существу сделать любую атаку нежизнеспособной (для расчета требуется примерно 3200 лет)?
0
Ответить
James avatar
флаг br
James
В качестве дополнительной альтернативы, если есть так много беспокойства о том, что квантовые вычисления, возможно, смогут атаковать шифрование ключей меньшего размера, не будет ли достаточно возможно создать криптосистему на основе эллиптических кривых с ключами больших размеров, не занимая слишком много времени для вычислений (1024). операций не кажется, что современному компьютеру потребуется слишком много времени для выполнения, даже если каждая операция занимает 1 000 000 наносекунд)?
0
Ответить
флаг ag
Gabriel Garrett
@AAA Есть ли какая-либо общеизвестная реализация гигантского шага ребенка для шифрования эллиптических кривых?
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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