На главную | Содержание | Назад | Вперёд
Наши друзья

 

 

НОВЫЕ ВЕЯНИЯ в КОДИРОВАНИИ:
ШИФРОВАНИЕ   С  ПОМОЩЬЮ   ЭЛЛИПТИЧЕСКИХ КРИВЫХ

Как известно, все современные методы шифрования построены на базе взятия по модулю (использование остатка от целочисленного деления), подробно об­суждавшегося в предыдущих частях этой главы. Однако в середине 80-х годов многие исследователи обнаружили, что есть еще один претендент на роль мощ­ного алгоритма шифрования — эллиптические кривые. Это обширные математи­ческие структуры, сделавшие неоценимый вклад в некоторых приложениях, вклю­чая анализ простых чисел (т. е. определения, является ли число простым) и разбиение чисел на множители. Одним из возможных применений эллиптичес­ких кривых являются системы шифрования с открытым ключом. Эллиптические кривые могут привести к открытию новых разновидностей современных систем шифрования, которые основаны на какой-либо сложной математической про­блеме.
В этой части главы приводится краткий обзор различий между системами шифро­вания, основанных на эллиптических кривых (ЕСС — Elliptic-Curve Cryptography), и обычными системами (основанными на операции взятия по модулю). Я не привожу здесь математические подробности алгоритма эллиптических кривых -они слишком сложны и требуют специальных знаний высшей математики.
Сразу отметим, что, новые системы шифрования являются аналогами уже суще­ствующих. Оказывается, что можно достаточно просто перенести все наработки современных систем шифрования на новые алгоритмы. Более того, существует возможность определить системы шифрования с открытым ключом, являющие­ся аналогом систем, основанных на проблеме дискретных логарифмов. Подоб­ные аналоги условно подразделяют на два класса. Первый класс основан на ограниченном поле с нечетными математическими характеристиками (обычно это большие простые числа), а второй — на поле с математически четными характеристиками. На первый взгляд все это кажется лишь техническими разли­чиями, но на самом деле выбор поля может повлиять как на безопасность, так и на эффективность системы шифрования. Это различие очень напоминает то, которое встречается в системах с дискретными логарифмами.
Вы, возможно, уже обратили внимание на то, что проблемы нахождения про­стых сомножителей и дискретных логарифмов над полем простых чисел прибли­зительно одинаковы по сложности. Поэтому можно попытаться приспособить методы решения одной проблемы для решения другой. Действительно, суще­ствуют построенные на эллиптических кривых аналоги алгоритма RSA, Однако все они представляют собой только академический интерес, так как не обладают преимуществами по отношению к этому алгоритму. Дело в том, что эти аналоги построены на той же проблеме, что и сам алгоритм RSA, — на проблеме разло­жения на множители.
Совсем другими возможностями обладают аналоги систем шифрования, осно­ванных на дискретных логарифмах. Безопасность подобных аналогов основыва­ется на новом определении проблемы дискретных логарифмов по отношению к эллиптическим кривым. Новое определение проблемы построено так, что со­зданные к настоящему моменту алгоритмы решения проблемы обычных дискрет­ных логарифмов (они называются субэкспоненциальным временем) ни в коей мере не упрощают решение подобной проблемы для эллиптических кривых. Наобо­рот, для нахождения дискретных логарифмов на эллиптических кривых подходят более общие методы, известные под названием экспоненциального времени.
Вы должны четко понимать, что на функциональном уровне механизмы шифро­вания или создания цифровых подписей могут быть разработаны так, чтобы они
зависели только от одной из трех рассмотренных выше проблем — разбиения целого числа на простые множители, обычных дискретных логарифмов и диск­ретных логарифмов на эллиптических кривых.
безопасность   систем на   эллиптических кривых
При обсуждении какой-либо проблемы в качестве показателя ее сложности мы использовали понятие «трудность взлома». Для систем с открытым ключом слож­ность решения проблемы напрямую связана с числом п — длиной ключа. Для систем шифрования на эллиптических кривых показателем сложности является число N — количество точек в открытой группе. Однако для упрощения рассуж­дений будем считать, что количество точек в этой группе равняется размеру базового поля (понятие базового поля будет определено в следующей части главы).
Проблема дискретных логарифмов на эллиптических кривых достаточно сложна.
Основанные на этой проблеме программы шифрования могут использовать не­сколько алгоритмов, время вычисления которых пропорционально квадратному корню из N. В операциях с эллиптическими кривыми N — это число точек в группе, используемой для вычислений.
Считается, что системы шифрования на эллиптических кривых, использующие 160-битные поля GF(2m) обеспечивают такую же стойкость к взлому, как и 1024-битные ключи RSA. Таким образом, эти системы позволяют использовать более короткие ключи, чем в алгоритме RSA, а это может сильно повлиять на стойкость и производительность систем шифрования в целом.
Те же расчеты показывают, что системы шифрования на эллиптических кривых над 136-битным полем GF(2'M) обеспечивают приблизительно такую же стой­кость к взлому, как и 768-битные ключи RSA.
математические с
Математические принципы ЕСС слегка отличны от алгоритмов RSA и Диффи— Хеллмана.
В функции ЕСС группа — это множество элементов с некоторым образом опре­деленными арифметическими операциями над ними. Поле — это множество элементов с некоторым образом определенными арифметическими операциями над ними. Однако на арифметические операции в поле наложены более строгие усло­вия, чем на операции в группе. Элементами группы эллиптических кривых яв­ляются наборы из двух чисел - (х,у). Эти наборы называют точками.
Значения х и у могут быть обычными (действительными) числами, а могут яв­ляться членами из ограниченного поля вроде F (р — простое число). Подобные поля называются базовыми полями (или базой) группы эллиптических кривых. Вы­бор базового поля влияет на количество точек группы, скорость вычислений и трудность связанной с группой проблемы дискретных алгоритмов. Таким обра­зом, выбор базового поля в программе шифрования непосредственным образом
влияет на размер ключа, вычислительную мощность системы и стойкость к взло­му. Выбор различных базовых полей предоставляет возможность выбора огром­ного количества различных эллиптических кривых.
ЕС С И  СОВРЕМЕННЫЕ   СИСТЕМЫ ШИФРОВАНИЯ
Алгоритм ЕСС хорош тем, что он обеспечивает такую же стойкость к взлому при размере ключа гораздо меньшем, чем у современных алгоритмов шифрования. Кроме того, реализация некоторых вычислений с эллиптическими кривыми может оказаться проще, чем у алгоритмов RSA или Диффи-Хеллмана.
Меньшие размеры ключей и более простая реализация предоставляют методу ЕСС большие возможности по сравнению с современными системами шифрова­ния. Например, новый алгоритм мог бы успешно применяться в сотовой связи, где существуют определенные ограничения по мощностт процессора и объему памяти.
Однако в течение ближайших нескольких лет эти методы не смогут найти серьез­ного применения в коммерческих продуктах. Потребуется еще очень много вре­мени и сил для реализации этого алгоритма. Но не стоит забывать, что жизнь полна неожиданностей; поэтому вам нужно постоянно быть в курсе всех иссле­дований в области эллиптических кривых.

 

На главную | Содержание | Назад | Вперёд
 
Яндекс.Метрика