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