Ключ, построенный по эллиптической кривой над конечным полем, в три раза короче, чем ключ, построенный по полю целых чисел.
Если вчитаться в это предложение, то любому здравомыслящему человеку оно покажется абсурдным, почему оно короче, а если я хочу длиннее, то оно имеет какое-то ограничение или что? Если переформулировать это и сказать: ключ, построенный на эллиптической кривой над конечным полем, обеспечивает криптостойкость алгоритма, сравнимую с ключом в три раза дольше, но над полем целых чисел это будет звучать более правдоподобно.
Попробуем разобраться, что означает «укорачивание» длины ключа.
Криптографическая стойкость — это не что иное, как сложность вычисления самой трудоемкой обратной операции алгоритма.
В теории односторонних функций, на которой построена асимметричная криптография, предположение о сложности дискретного логарифма представляет собой NP-трудную задачу.
Итак, возведение числа a в степень n в конечном поле и умножение точки эллиптической кривой на число являются основой асимметричного шифрования.
Задача дискретного логарифма на эллиптической кривой над конечным полем состоит в нахождении m в паре mA=P. Где A и P — точки эллиптической кривой.
Ключи m и P являются частными и общедоступными соответственно.
Те.
вся сложность алгоритма основана на предположении, что не существует полиномиального алгоритма нахождения м, зная А и П.
Сложение точек на эллиптической кривой легче всего рассматривать в геометрической интерпретации.
Операция сложения в этой интерпретации представляет собой построение секущей между двумя точками или касательной в случае удвоения точек и результатом сложения будет третья точка, лежащая на пересечении секущей/касательной и кривой.
Скалярное умножение точки реализуется как mA=A+A+.
+A=P, т.е.
группа точек эллиптической кривой над полем является конечно порожденной абаловой группой, т.е.
группа точек эллиптической кривой есть аддитивна, и поэтому на ней определены групповые операции сложения и умножения, основанные на индукции сложения.
Те.
Получить точку P, зная n и A, довольно легко, но алгоритмически сложно найти число m, зная только «конечные» точки.
Теги: #Криптография #эллиптические кривые #Чулан
-
Ии Для Людей: Простыми Словами О Технологиях
19 Oct, 24 -
Парадокс Ферми
19 Oct, 24
