ИСПОЛЬЗОВАНИЕ ИЗОГЕНИЙ ДЛЯ РАЗРАБОТКИ КРИПТОСИСТЕМ Российский патент 2009 года по МПК G09C1/00 

РОДСТВЕННЫЕ ПАТЕНТНЫЕ ЗАЯВКИ

Данная заявка испрашивает приоритет предварительной патентной заявки США № 60/517,142 от 3 ноября 2003 г. на "Использование изогений для разработки криптосистем", раскрытие которой включено в данный документ посредством ссылки.

ОБЛАСТЬ ТЕХНИКИ

Данное изобретение относится к криптологии, в частности к использованию изогений для разработки криптосистем.

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

Поскольку цифровая связь становится все более распространенной, потребность в обеспечении защищенности каналов связи становится все более и более важной. Например, современные технологии позволяют пользователю дистанционно обращаться к счетам в банке, медицинским данным и другой частной и конфиденциальной информации.

Криптология широко используется для обеспечения защищенной цифровой связи. Криптология в принципе относится к зашифровыванию (или шифрованию) и расшифровыванию (дешифрованию) сообщений. Шифрование и дешифрование используют некоторую секретную информацию (такую как ключ). В различных методах шифрования единственный ключ или множество ключей могут быть использованы для шифрования и дешифрования.

Одной широко используемой криптосистемой с множественным ключом является система шифрования с открытым ключом. В криптосистеме с открытым ключом отправитель, желающий послать зашифрованное сообщение получателю, получает аутентифицированный (заверенный) открытый ключ для получателя, который генерируется с использованием секретного ключа. Как следует из названия, открытый ключ может быть доступен из общедоступных источников. Кроме того, чтобы избежать попыток взлома криптосистемы с использованием злоумышленником открытого ключа другого человека, часто проводится проверка подлинности открытого ключа. Проверка подлинности открытого ключа может быть реализована при помощи обмена ключами по защищенному каналу, использования защищенного открытого файла, использования защищенного сетевого сервера или использования несетевого сервера и сертификатов.

После получения аутентифицированного (т.е. подлинного) открытого ключа отправитель шифрует исходное сообщение с использованием открытого ключа и генерирует шифротекст. Санкционированный получатель затем использует секретный ключ, чтобы дешифровать шифротекст и извлечь исходное сообщение. Предполагается, что задача расшифровки шифротекста, без доступа к секретному ключу, является нерешаемой. Соответственно, только сторона, имеющая доступ к секретному ключу, может успешно расшифровать шифротекст.

Одним существенным преимуществом систем с открытым ключом над симметричными криптосистемами (например, системами поточного шифрования или блочного шифрования) является то, что при двустороннем обмене информацией только секретный ключ должен храниться в секрете (тогда как в симметричных криптосистемах ключ хранится в секрете обеими сторонами).

Существующие в настоящее время криптосистемы с открытым ключом используют эллиптические кривые определенного рода, построенные на конечных полях. Пара опубликованных значений, выведенных на основании уравнения эллиптической кривой, используется в качестве открытого ключа (включая точки на кривой и соответствующие им открытые ключи, сгенерированные при помощи простого (то есть целочисленного умножения на кривой). Верификация производится с использованием билинейных пар для кривой.

В общем случае считается, что эллиптические кривые обеспечивают криптосистемы с относительно более низкими требованиями к процессу передачи информации по сравнению с традиционными криптосистемами типа РША (шифр Ривеста-Шамира-Адлемана с открытым ключом), поддерживая такой же уровень безопасности.

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

Соответственно, требуются криптосистемы с открытым ключом, обеспечивающие дополнительную защищенность.

КРАТКОЕ ОПИСАНИЕ

Заявлены способы, позволяющие создать криптосистему с открытым ключом. Более подробно, изогении абелевых множеств (например, эллиптические кривые в одномерном случае) используются для создания криптосистемы с открытым ключом. Например, изогении допускают использование множества кривых вместо единственной кривой для обеспечения большей защищенности. Способы могут быть использованы для цифровой подписи и/или для способов идентификационного шифрования (IBE). Кроме того, изогении могут быть использованы для других приложений, например "слепой" подписи, иерархических систем, и тому подобных. Кроме того, раскрыты решения для формирования изогений.

В одной из описанных реализаций способ включает в себя опубликование открытого ключа, соответствующего изогении. Далее способ включает дешифрование зашифрованного сообщения с использованием ключа дешифрования, соответствующего изогении (например, ее дуальной изогении).

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Детальное описание приводится со ссылками на прилагаемые чертежи. На чертежах самая левая цифра(цифры) ссылочной позиции указывает на чертеж, на котором данная ссылочная позиция встречается впервые. Использование одинаковых ссылочных позиций на разных чертежах указывает на аналогичные или идентичные объекты.

Фиг.1 иллюстрирует примерный способ использования изогений в криптосистеме.

Фиг.2 иллюстрирует примерное отображение изогений между двумя кривыми.

Фиг.3 иллюстрирует примерный способ подписи сообщения с использованием изогений.

Фиг.4 иллюстрирует примерное отображение изогений между множеством кривых.

Фиг.5 иллюстрирует примерный способ идентификационного шифрования (IBE) с использованием изогений.

Фиг.6 иллюстрирует вычислительную среду 600 общего назначения, которая может быть использована для реализации описанных здесь методик.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Дальнейшее обсуждение подразумевает, что читатель знаком с методами криптографии. Для общего введения в криптографию читатель отсылается к кн.: A Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", пятое изд. (август 2001), выпущенной издательством CRC Press.

Приведенное ниже раскрытие описывает методы улучшения систем с открытым ключом, основанные на множественных эллиптических кривых (или абелевых множествах, в общем случае). Раскрыты различные методы генерирования изогений (или отображений) между кривыми. Сгенерированные изогении допускают использование множества кривых вместо единственной кривой, для того чтобы обеспечить открытость шифрования. Кроме того, эти методы могут быть применены к относительно коротким цифровым подписям (например, введенным пользователем или посланным по узкополосным каналам связи) и/или к методам идентификационного шифрования (например, допускающим запоминающиеся открытые ключи). Так же короткие подписи могут обеспечить дополнительную эффективность за счет комплексной верификации.

Обзор криптосистем с использованием изогений

Фиг.1 иллюстрирует примерный способ 100 использования изогений в криптосистемах. На стадии 102 генерируются изогении (эллиптических кривых, или абелевых множеств, в более общем случае). Изогении могут быть сгенерированы принимающей стороной или другой стороной (например, доверенной стороной, как описано ниже со ссылкой на Фиг.5). На стадии 102 также могут быть сгенерированы соответствующие дуальные изогении для каждой сгенерированной изогении (как описано ниже). Различные способы генерации изогений рассмотрены подробно в соответствующем разделе. Кроме того, как детально описано ниже со ссылкой на Фиг.3 и 5, сгенерированные изогении используются для получения открытых ключей, и эти открытые ключи опубликовываются (104). Открытые ключи могут быть опубликованы передающей стороной или доверительным центром (см., например, описание Фиг.3 и 5).

Затем передающая сторона шифрует (или подписывает) сообщения при помощи ключа шифрования (106). Зашифрованные сообщения на стадии 106 могут быть верифицированы/дешифрованы принимающей стороной при помощи ключа дешифровки, чтобы определить подлинность шифрования или подписи (108). В одной реализации, для проверки зашифрованных сообщений, используется образование пар по Вейлу (как описано в соответствующем разделе), которое, однако, не является единственным примером образования пар, использующегося для верификации или дешифровки. Например, может быть использован другой метод билинейного и/или невырожденного образования пар, например, по Тейту или квадратичное образование пар.

Обзор изогений

Фиг.2 иллюстрирует примерное отображение изогений 200 между двумя кривыми (например, эллиптическими). Как показано, кривая E₁ может отображаться на кривую E₂ посредством изогении ϕ (где ). Фиг.1 также показывает дуальную изогению (где ).

В различных реализациях использования изогений в криптосистемах стараются обеспечить следующие свойства: для данной кривой E₁ генерирование пары (ϕ,E₂) достаточно эффективно, где - изогения, но для заданной пары (E₁, E₂) изогенных кривых предполагается, что достаточно трудно построить ненулевую изогению , которая будет много меньше заданной изогении. Таким образом, если разделить глобальный взлом (определяемый как вычисление, позволяющее взломать любое последующее сообщение в полиномиальное время) и поэтапный взлом, то наилучшая из известных в настоящее время атак на криптосистемы на основе изогений требует или существенно большего времени, чем дискретное логарифмирование, в случае глобального взлома и или одного дискретного логарифмирования на одно сообщение в случае простого поэтапного взлома.

Для примера рассмотрим систему лексем, в которой каждому клиенту выдается определенное снабженное подписью сообщение, предоставляющее доступ к определенному сервису (которое может иметь невысокое значение), клиент может зачитать лексему по телефону уполномоченному лицу, и таким образом цифровые подписи могут быть относительно короткими. В таком случае разумно использовать достаточно большие параметры, с тем чтобы сделать взлом отдельного сообщения более затратным чем стоимость предоставляемого сервиса, сохранив при этом, неприемлемо высокими затраты на глобальный взлом.

Подробное описание изогений

Поле k может быть упорядоченно при помощи характеристики p, содержащей q элементов и имеющее алгебраическое замыкание . Пусть E/k есть эллиптическая кривая, определенная по полю k, и E/k есть группа, определенная по k, и k(E) обозначает поле функции эллиптической кривой. Также пусть [n]_E или [n] обозначает отображение на E, а E[n] обозначает ядро этого отображения.

Изогения есть непостоянный морфизм, преобразующий нулевой элемент E₁ в соответствующий элемент E₂. Если такая изогения существует, можно сказать, что E₁ и E₂ изогенны. Изогения определена по k, если ϕ определяется уравнениями с коэффициентами, принадлежащими k. Также оказывается, что для любой изогении выполняется гомоморфизм групп, то есть для всех , где сложение в левой части есть групповой закон на E_1, а сложение в правой части - на E₂. Следовательно, ядро ϕ является подгруппой E₁.

Пусть обозначает множество изогений от E₁ и E₂, определенных по k. обозначим, как . Для любой изогении существует дуальная изогения такая, что:

и ,

где есть степень изогении. Дуальная изогения удовлетворяет стандартным свойствам

В одной реализации степень ϕ как конечное отображение может быть в дальнейшем определена как степень расширения k(E₁) над прообразом (по ϕ) поля k(E₂), где ϕ определена по k. Удобно рассматривать ее в терминах размера ее ядра (предполагая, что расширение поля функции сепарабельно) или при помощи приведенного выше уравнения. Поэтому говорят, что изогения имеет гладкость B-го порядка, если ее степень имеет гладкость B-го порядка (другими словами, простой дивизор для меньше либо равен B). Множество эндоморфизмов эллиптической кривой обозначим ; это множество имеет циклическую структуру, задаваемую определением:

, .

В общем случае группа является свободным левым и правым модулем кручения. Когда , алгебраическая структура более богата: является циклом (а не просто модулем) без нулевых дивизоров и имеет характеристический ноль.

В одном варианте реализации это может рассматриваться как структура: пусть E есть эллиптическая кривая, определенная по некоторому полю k. Тогда изоморфно или к рангу Z квадратичного мнимого поля, или к максимальному рангу в алгебре кватернионов. Для любых двух эллиптических кривых E₁, E₂ группа является свободным Z-модулем с рангом, не превышающим 4. Если больше чем Z, можно сказать, что E обладает комплексным умножением. Элемент в , соответствующий фробениусовому эндоморфизму , обозначается π и удовлетворяет характеристическому уравнению . Кондуктор эллиптической кривой с равен .

Образование пар по Вейлу

Образование пар по Вейлу представляет собой билинейное, невырожденное отображение со значениями в группе n-ных корней из единицы в k. В одном варианте реализации образование пар по Вейлу используется для выполнения стадии 108 верификации/дешифрования на Фиг.1. Тем не менее, образование пар по Вейлу не является единственным примером образования пар, которое может быть использовано для верификации или шифрования. Например, может быть использован другой метод билинейного и/или невырожденного образования пар, такой как образование пар по Тейту или квадратичное образование пар. Образование пар по Вейлу удовлетворяет следующему уравнению:

, где , ,

здесь есть вычисление для образования пар на E₁, а - на E₂. Заметим, что обе кривые имеют точки кручения n-го порядка, каждая из которых накладывает ограничение на соответствующие порядки групп. Это не создает проблемы, так как по теореме Тейта k(E₁) и k(E₂) изогенны по k тогда и только тогда, когда две группы точек имеют одинаковый порядок.

При образовании пар по Вейлу оценивается идентичность для всех линейно зависимых входных пар. Следовательно, полезен механизм, позволяющий удостовериться в том, что входные пары не являются скалярными произведениями друг друга. Один из подходов заключается в использовании кривой E₂, определенной по конечному полю k, достаточно большому, для того чтобы полная группа точек кручения n-го порядка определялась по k. В этом случае вероятность того, что два случайно выбранных элемента группы линейно зависимы, пренебрежимо мала, порядка 1/n, и таким образом результат образования пар по Вейлу может быть нетривиальным с высокой вероятностью. Приведенное выше уравнение гарантирует, что распределение парных значений на E₁ будет соответствовать распределению на E₂.

В качестве альтернативы может быть использована модифицированная функция пересчета пар , где λ - любой нескалярный эндоморфизм, такой что P и λ(P) линейно независимы и . Такое отображение λ называется дисторсией или изгибом E.

Формирование изогений

В различных вариантах реализации ряд способов может быть использован для построения изогений высокой степени (например, эллиптических кривых или абелевых множеств в более общем случае) и дуальных к ним, как описано со ссылкой на стадию 102, представленную на Фиг.1. Короткая цифровая подпись или идентификационные (IBE) криптосистемы, описываемые здесь, могут придерживаться соглашения о том, что пары значений опубликовываются в качестве открытого ключа, а оценка дуальной изогении является секретным ключом.

В одном из вариантов реализации формирование может быть кратко описано следующим образом: для любого заданного E существует алгоритм построения изогений , степени n которых распределены случайным образом и являются простым числом с вероятностью ; для любой заданной кривой E₁ существует алгоритм формирования случайных изогений, имеющих гладкость B-го порядка, из E₁ к случайным целям за время ; и для заданных E₁, E₂ и двух линейно независимых изогений в , имеющих взаимно простые степени, существует алгоритм формирования изогений с простыми степенями (как описано ниже для независимых изогений).

Комплексное умножение изогений

Пусть, как и ранее, , и предположим, что E₁ обладает комплексным умножением (CM) на мнимый квадратичный порядок O_D с дискриминантом . Вероятностный алгоритм для построений такой кривой E₁ вместе с эндоморфизмом ϕ над E₁ большой простой степени, в полиномиальное по время, может быть описан следующим образом.

1. Вычислить гильбертов полином с дискриминантом D. Пусть K обозначает поле разложения по Q.

2. Выбрать любой корень x полинома и построить эллиптическую кривую E по C, такую, что ее инвариант j равен x. Отметим, что E определена для поля чисел K.

3. Кривая E обладает комплексным умножением на по построению. Используя линейную алгебру q-расширений, найти в явном виде рациональную функцию с коэффициентами из K, соответствующую изогении

4. Выбрать случайные целые a и b до тех пор, пока не станет простым числом. В этом случае изогения будет эндоморфизмом E с простой степенью.

5. Выбрать любой простой идеал P поля K и редуцировать коэффициенты E и I по модулю P. Пусть E₁ обозначает редукцию E, а ϕ - редукцию

Стадии 1-3 данного алгоритма детерминированы и требуют полиномиального по времени. Что касается стадии 4, из теоремы простых чисел в числовом поле следует, что вероятность нахождения , являющегося простым числом, равна , таким образом, для целых чисел a и b мощности n можно ожидать завершения стадии 4 после попыток.

Найденный эндоморфизм ϕ есть эндоморфизм кривой E₁ с простой степенью. Изогения ϕ и дуальная к ней могут быть вычислены, если известны числа a и b, с использованием рациональной функции , комплексного умножения и сложения. Такая изогения ϕ может быть названа CM-изогенией.

Модулярные изогении

Для любого простого числа модулярная кривая задает в неявной форме изоморфизм класса изогений степени . А именно существует полиномиальное уравнение для такое, что E₁ и E₂ -изогенны тогда и только тогда, когда .

Используя полином , можно вычислить -изогенную кривую E₂ для любой E₁ вместе с явным полиномиальным уравнением для степени изогении . Так как модулярный полином симметричен по X и Y, вычисление с обращенными инвариантами j может быть использовано для нахождения дуальной изогении.

На практике лучше не использовать полиномы для реальных вычислений, потому что коэффициенты этих полиномов очень велики. Вместо них могут быть использованы другие эквивалентные полиномиальные модели для с меньшими коэффициентами. Безотносительно к точности, использованной для вычисления модели, изогении, выведенные таким способом, могут называться модулярными изогениями.

Как правило, известные в настоящий момент алгоритмы для вычисления модулярных изогений выполнимы для малых значений . Само по себе использование модулярных изогений малых степеней не сильно увеличивает надежность шифра, так как нарушитель, знающий кривые E₁ и E₂, может проверить, являются ли они -изогенными для каждого , и восстановить -изогению в случае положительного результата проверки. Тем не менее, можно скомпоновать множество модулярных изогений (например, для разных ) в одну изогению ϕ с большой степенью гладкости и использовать ϕ в качестве изогений без раскрытия промежуточных кривых. Нарушитель, способный вычислять в произвольных точках, все еще сможет вывести простые числа при помощи расчета всех точек кручения -го порядка на E₁ и проверки, сводятся ли к нулю какие-нибудь из них при применении ϕ. Тем не менее, если предположить, что проблема вычисления дуальных изогений сложна, нарушитель не сможет вычислить значения ϕ в точках по своему выбору. В процессе реализации, для улучшения, можно скомпоновать результирующую изогению или со скалярными изогениями, или с CM-изогениями, для того чтобы ввести большие негладкие множители степени.

Линейно независимые изогении

В одной из реализаций линейно независимые изогении ϕ и ψ задаются на E₁ и E₂ с взаимно простыми степенями. В результате линейная комбинация имеет степень, задаваемую квадратичной формой с двумя переменными a и b. Заметим, что коэффициенты квадратичной формы - целые числа, так как внешние коэффициенты есть степени ϕ и ψ, а средний коэффициент равен . Так как квадратичная форма является примитивной, она принимает значения, являющиеся простыми числами бесконечно часто, когда a и b изменяются по всем парам . Таким образом, может быть получено множество изогений с большими негладкими (и даже простыми) степенями. Также можно оценить вероятность того, что результирующая степень будет негладкой.

Схемы короткой цифровой подписи с использованием изогений

В возможной реализации описываемые методы могут быть применены к схемам с относительно короткими цифровыми подписями (например, введенными пользователем или посланными по узкополосным каналам связи). Ниже описаны две схемы цифровой подписи, частично базирующиеся на математических свойствах изогений и образовании пар эллиптических кривых.

Цифровая подпись на инвариантах Галуа

Обозначим расширение конечных полей степени n. Возьмем эллиптическую кривую E₁, определенную по F_q, вместе с изогенией , определенной по F_q”, где E₂ есть эллиптическая кривая, определенная по F_q'. В одной реализации кривая E₂ определена для L, а не для подполя от L, тем не менее, возможно использование E₂, определенной только для подполя. Однако изогения ϕ может быть неопределенна по любому надлежащему подполю F_q'. Более того, изогения ϕ может генерироваться в соответствии с методами, описанными выше.

Фиг.3 иллюстрирует примерный метод 300 для подписи сообщения с использованием изогений. Метод 300 включает следующие стадии:

Открытый ключ. Взять случайное и опубликовать (302), где . Заметим, что P определено по F_q, но Q не определено по F_q, так как ϕ не определено по F_q.

Секретный ключ. Дуальная изогения к ϕ.

Цифровая подпись. Пусть H есть (открытый) случайный оракул из пространства сообщения на множество точек кручения k-го порядка на E₂. Для данного сообщения m вычислить (стадия 304, обеспечивающая подпись при помощи секретного ключа, сгенерированного, как описано выше), где π есть фробениусово отображение мощности q, а сумма обозначает сумму эллиптической кривой на E₁. Для удобства обозначим оператор как Tr (от английского слова "trace"). Вывести в качестве подписи. Затем подпись посылается и получается принимающей стороной (306 и 308, соответственно). Заметим, что группа Галуа для F_q'/F_q есть , так что S есть инвариант Галуа, и таким образом определена по F_q.

Проверка. Пусть e₁ и e₂ обозначают пары по Вейлу на и , соответственно. Для данного открытого ключа и пары сообщение-подпись проверить, выполняется ли соотношение (стадия 310, проверяющая полученную сигнатуру с использованием открытого ключа, сгенерированного как описано выше). Соответственно подлинная подпись удовлетворяет данному уравнению, как следует ниже:

Также отображение следа может быть применено к базовому полю, для того чтобы сократить количество точек на эллиптической кривой (или любом абелевом множестве в более общем случае). Другими словами, вывод отображения следа на эллиптические кривые (или абелевых множеств более высокой размерности) может быть использован как способ для укорачивания представления точки по полю расширения с использованием данных по меньшему полю.

Подписание с использованием множественных эллиптических кривых

Другой способ увеличения устойчивости схем, использующих короткую подпись, заключается в применении множественных открытых ключей и сложении результирующих цифровых подписей. Эта модификация может быть использована отдельно или в комбинации с расширением на основе инварианта Галуа, описанного выше.

Со ссылкой на Фиг.4 предположим, что существует семейство изогений и семейство хэш-функций H_i случайного оракула, каждое из которых отображает сообщение m в точку на эллиптической кривой E_i. Аналогично стадиям, обсужденным со ссылкой на Фиг.3:

Открытый ключ. Взять случайное и опубликовать (см., например, 302), где .

Секретный ключ. Семейство изогений ϕ_i.

Цифровая подпись. Для каждого сообщения m цифровой подписью для m(S) является (см., например, 304). Затем подписанное сообщение отправляется принимающей стороне (см., например, 306).

Проверка. Для данной пары (сообщение, подпись) проверить, выполняется ли соотношение (см., например, стадию 306, описанную со ссылкой на Фиг.3). Для подлинной подписи это уравнение имеет место, так как:

.

Предполагается, что такая система по меньшей мере так же надежна, как и система, использующая единственную изогению, так как тот, кто может взломать версию системы, использующую множество изогений, может свести версию, использующую единственную изогению, к множественной, добавлением изогений , по своему усмотрению. Более того, для подобных систем успешная атака на версию системы с множеством изогений требует одновременного взлома всех единичных изогений от ϕ₁ до ϕ_n.

Схема идентификационного шифрования (IBE) с изогениями

Фиг.5 иллюстрирует примерный способ 500 для идентификационного шифрования (IBE) с использованием изогений. Считается, что использование необратимых изогений между эллиптическими кривыми делает схему идентификационного шифрования (IBE) потенциально более надежной, по сравнению с использованием программно реализуемой системы Диффи-Хеллмана (CHD). Схема IBE может быть определена следующим способом.

Отображение в точку: Определим оператор для некоторой кривой E. Более определенно, можно вычислить и использовать полученное значение для определения точки. Можно предположить, что H ведет себя подобно случайному оракулу. В качестве альтернативы, можно поддерживать таблицу точек и хэшировать в случайную последовательность весов, а затем вычислить взвешенную сумму. Также можно предположить, что существуют доверительный центр и конечное множество пользователей с некоторым , при помощи которого можно вычислить соответствующий открытый ключ. Каждый пользователь получает свой секретный ключ после соответствующей идентификации доверительным центром.

Открытый ключ для доверительного центра: , . Соответственно доверительный центр (или другая организация, например, принимающая сторона) обеспечивает и публикует открытые ключи (502). Если используется изгиб λ, можно предположить, что есть скрученный образ некоторой точки α.

Секретный ключ для доверительного центра: Эффективно вычисляемая .

Например, передача зашифрованных данных от Боба к Алисе может быть реализована следующим образом:

Открытый ключ для Алисы: предоставляется, например, посредством функции отображение-в-точку (502) доверительным центром (или другой организацией, например принимающей стороной).

Секретный ключ для Алисы: . Заметим, что атака, направленная на быстрое получение секретного ключа каждого клиента, будет требовать такого же времени, как для глобального взлома системы цифровой подписи (как описано выше). В результате эти системы можно также назвать двухуровневыми системами.

Шифрование, осуществляемое Бобом: Вычислить (стадия 504, которая зашифровывает сообщение при помощи сгенерированного открытого ключа). Пусть сообщение обозначается как m. Выбрать случайное целое r. Послать Алисе пару (506):

Дешифрование, осуществляемое Алисой: Пусть зашифрованный текст будет обозначен как . Отправленное зашифрованное сообщение дешифруется (508) с использованием секретного ключа (510), предоставленного доверительным центром (или другой организацией, например принимающей стороной) после соответствующей идентификации. В результате расшифрованный текст есть:

Эта схема работает, потому что величина, хэшированная на стадии шифрования, есть:

и равна величине, хэшированной на стадии дешифрования. Изогения может быть представлена, как описано ниже (например, с использованием вероятностного подхода, применяющего таблицу записей).

Задание изогений

Если изогения гладкая, то она может быть представлена как композиция изогений малой степени, задаваемых простой программой, представляющей собой вычисление полиномов. Для кривых, определенных по расширениям, представляющим интерес, при реализации достаточно небольшой таблицы пар входных-выходных данных.

Принимая во внимание , может быть рассмотрено конечное расширение поля k, и это расширение может быть задано соответствующим образом. В одной из реализаций изогения определяется ее действием на группу точек в некотором конечном расширении базового поля. Заметим, что две изогении могут совпадать на некоторых расширениях, но при этом отличаться на больших полях. Соответственно, достаточно задать ϕ на наборе генераторов S. Как правило, эта группа циклическая или, как выше, . Считается, что нелегко найти такие генераторы, но возможен случайный выбор S.

Более детально, как абелева группа (напомним: k есть конечная группа, содержащая q элементов) изоморфна к , где , и дополнительно , . Можно вычислить с использованием алгоритма Шуфа, и если факторизация известна, то n может быть получено при помощи рандомизированного полиномиального временного алгоритма. Если и имеют порядок n и m соответственно, они называются ступенчатыми генераторами, исходя из того, что любая точка может быть представлена как , и алгоритм с арифметическими операциями может быть использован для их построения.

Обращаясь к случайным выборкам (Эрдос-Реньи), допустим, что G есть конечная абелева группа, а - случайные элементы G. Существует небольшая константа c такая, что суммы ее подмножества по существу равномерно распределены по G, если . В частности, g_i могут генерировать G. Для уменьшения размера таблицы можно использовать усиленные взвешенные суммы подмножества, а не суммы подмножества, когда порядок группы простое число. Это распространяется и на произвольные порядки с небольшой потерей параметров.

Более того, структура E(k) может быть использована для получения более подробной информации. Можно взять случайные точки P_i, и записать их как . Более подробно, можно выразить каждый ступенчатый генератор линейной комбинацией P_i, если матрица обратима по модулю m (заметим, что ). В этом случае будет генерировать группу. Заметим, что вероятность (для P₁ и P₂ одновременно) попасть в группу, сгенерированную , равна . Аналогично вероятность для группы, сгенерированной , равна . Таким образом, любое из этих двух событий не происходит с вероятностью .

Аппаратная реализация

Фиг.6 иллюстрирует вычислительную среду 600 общего назначения, которая может быть использована для реализации описанных здесь методик. Например, вычислительная среда 600 может быть использована для исполнения инструкций, связанных с выполнением задач, обсужденных со ссылкой на предыдущие чертежи. Более того, каждый объект, упомянутый здесь (например, касательно Фиг.1, 3 и 5, такая как доверительная сторона, принимающая сторона, и/или передающая сторона) может иметь доступ к вычислительной среде общего назначения.

Вычислительная среда 600 является только примером вычислительной среды и не претендует на введение каких-либо ограничений в отношении области использования или функциональности компьютера и сетевой архитектуры. Вычислительная среда 600 не должна интерпретироваться, как имеющая какие-либо зависимости или требования по отношению к какой бы ни было комбинации компонентов, представленных в примерной вычислительной среде 600.

Вычислительная среда 600 включает вычислительное устройство общего назначения в форме компьютера 602. Компоненты компьютера 602 могут включать, но не ограничены упомянутыми, один или более процессоров или центральных процессоров 604 (по выбору, включающих криптографический процессор или сопроцессор), системную память 606 и системную шину 608, которая связывает различные системные компоненты, в том числе и процессор 604, с системной памятью 606.

Системная шина 608 представляет собой одну или более из любых типов шинных структур, включая шину памяти или контроллер памяти, периферийную шину, ускоренный графический порт, и процессорную или локальную шину, использующую любую из возможных шинных архитектур. В качестве примера подобные архитектуры могут включать шину архитектуры, соответствующей промышленному стандарту (ISA), шину микроканальной архитектуры (MSA), шину архитектуры, соответствующей улучшенному промышленному стандарту (ЕISA), локальную шину с архитектурой ассоциации по стандартам в области видеоэлектроники (VESA), 32-разрядную системную шину с возможностью расширения до 64 разрядов (PCI), также известную как шина расширения.

Компьютер 602, как правило, имеет набор машиночитаемых носителей. Подобный носитель может быть любым имеющимся носителем, доступным для компьютера 602, и включает как энергозависимые, так и энергонезависимые запоминающие среды, съемные и несъемные носители.

Системная память 606 включает в себя машиночитаемый носитель в форме энергозависимой памяти, такой как память 610 с произвольной выборкой (RAM), и/или энергонезависимой памяти, такой как постоянное запоминающее устройство 612 (ROM). Базовая система 614 ввода/вывода (BIOS) содержит базовые операции, помогающие передавать информацию между элементами компьютера 602, например, сохраненную в ROM 612, в процессе старта. RAM 610, как правило, содержит данные и/или программные модули, которые непосредственно доступны и/или над которыми по необходимости производятся операции центральным процессором 604.

Также компьютер 602 может включать другие съемные/несъемные энергозависимые/энергонезависимые компьютерные запоминающие среды. В качестве примера на Фиг.6 показан накопитель 616 на жестких дисках для чтения с и записи на несъемный энергонезависимый магнитный носитель (не показан), накопитель 618 на магнитных дисках для чтения с и записи на съемный энергонезависимый магнитный диск 620 (например, дискету), накопитель 622 на оптических дисках для чтения с и/или записи на съемный энергонезависимый оптический диск 624, такой как CD-ROM, DVD-ROM, или другой оптический носитель. Накопитель 616 на жестких дисках, накопитель 618 на магнитных дисках и накопитель 622 на оптических дисках соединены с системной шиной 608 при помощи одного или нескольких интерфейсов 626 цифровых носителей. Альтернативно накопитель 616 на жестких дисках, накопитель 618 на магнитных дисках и накопитель 622 на оптических дисках могут быть соединены с системной шиной 608 при помощи одного или нескольких интерфейсов (не показаны).

Дисковые накопители и относящиеся к ним машиночитаемые носители обеспечивают энергонезависимое сохранение машиночитаемых инструкций, структур данных, программных модулей и других данных в компьютере 602. Хотя данный пример иллюстрирует накопитель 616 на жестких дисках, накопитель 618 на магнитных дисках и накопитель 622 на оптических дисках принимается во внимание, что другие машиночитаемые носители, способные сохранять доступные компьютеру данные, такие как магнитные кассеты или другие магнитные запоминающие устройства, платы флэш-памяти, CD-ROM, универсальные цифровые диски (DVD) или другие оптические запоминающие устройства, память с произвольной выборкой (RAM), постоянные запоминающие устройства (ROM), электронно-перепрограммируемая постоянная память (EEPROM) и другие также могут быть использованы для реализации примерной вычислительной системы и среды.

Любое количество программных модулей может быть сохранено на жестком диске 616, магнитном диске 620, оптическом диске 624, ROM 612 и/или RAM 610, включая, в качестве примера, операционную систему 625, одну или более прикладную программу 628, другие программные модули 630 и данные 632 программ. Каждая из такой операционной системы 625, одной или более прикладной программы 628, других программных модулей 630 и данных 632 программ (или некоторая их комбинация) может реализовывать все или часть резидентных компонент для поддержки распределенной файловой системы.

Пользователь может вводить команды и информацию в компьютер 602 посредством устройств ввода, таких как клавиатура 634 и координатно-указательное устройство 636 (например, мышь). Другие устройства ввода 638 (не показаны подробно) могут включать микрофон, джойстик, игровую панель, спутниковую антенну, последовательный порт, сканнер и/или тому подобное. Эти и другие устройства ввода соединены с процессором 604 посредством интерфейса 640 ввода/вывода, который связан с системной шиной 608, но могут быть соединены при помощи других интерфейсов и шинных структур, таких как параллельный порт, игровой порт, универсальная последовательная шина (USB).

Монитор 642 или устройство отображения информации другого типа также может соединяться с системной шиной 608 через интерфейс, например видеоадаптер 644. В дополнение к монитору 642 другие периферийные устройства вывода могут включать такие компоненты, как динамики (не показаны), принтер 646, который может быть соединен с компьютером 602 через интерфейс 640 ввода/вывода.

Компьютер 602 может функционировать в сетевой среде посредством логических соединений с одним или более удаленными компьютерами, такими как удаленное вычислительное устройство 648. В качестве примера удаленное вычислительное устройство 648 может быть персональным компьютером, портативным компьютером, сервером, маршрутизатором, сетевым компьютером, одноранговым устройством, общим сетевым узлом, игровой консолью и так далее. Удаленное вычислительное устройство 648 проиллюстрировано как портативный компьютер, который может включать несколько или все элементы и возможности, описанные здесь касательно компьютера 602.

Логические соединения между компьютером 602 и удаленным компьютером изображаются как локальная сеть (LAN) 650 и как глобальная сеть (WAN) 652. Такие сетевые среды широко распространены в офисах, в сетях масштаба предприятия, в корпоративных локальных сетях и Интернете.

При реализации в локальной сетевой среде компьютер 602 соединяется с локальной сетью 650 через сетевой интерфейс или адаптер 654. При реализации в глобальной сетевой среде компьютер 602, как правило, имеет модем 656 или другое средство для установления соединения через глобальную сеть. Модем 656, который может быть внешним или внутренним по отношению к компьютеру 602, может соединяться с системной шиной 608 через интерфейс 640 ввода-вывода или другим подходящим способом. Следует иметь в виду, что описанные сетевые соединения являются примерными и что могут быть применены другие средства для установления канала(ов) связи между компьютерами 602 и 648.

В сетевой среде, например в проиллюстрированной вычислительной среде 600, программные модули, изображенные как относящиеся к компьютеру 602, или их части могут быть сохранены на съемных запоминающих устройствах. Для примера, удаленная прикладная программа 658 располагается в запоминающем устройстве компьютера 648. Для наглядности прикладные и другие исполняемые программные компоненты, такие как операционная система, проиллюстрированы здесь как дискретные блоки, хотя понятно, что такие программы и компоненты располагаются в разное время на разных запоминающих компонентах вычислительного устройства 602 и выполняются процессором(процессорами) данных компьютера.

Различные модули и методы могут быть описаны в данном документе в общем контексте машиноисполняемых инструкций как программные модули, исполняемые одним или более компьютерами или другими устройствами. В общем случае программные модули включают операции, программы, объекты, компоненты, структуры данных, и т.п., которые выполняют определенные задачи или реализуют определенные абстрактные типы данных. Как правило, функциональность программных модулей может свободно комбинироваться или распределяться, как это требуется в различных реализациях.

Реализация этих модулей и методов может быть сохранена или передана через некоторую форму машиночитаемой среды. Машиночитаемой средой может быть любой имеющийся носитель, доступный компьютеру. Для примера, но без ограничения общности, машиночитаемая среда может содержать "компьютерное запоминающее устройство" и "средства связи".

"Компьютерные запоминающие устройства" включают энергозависимые или энергонезависимые, съемные или несъемные носители, реализованные с использованием какого-либо метода или технологии для сохранения информации, такой как машиночитаемые инструкции, структуры данных, программные модули или другие данные. Компьютерные запоминающие устройства включают, но не ограничиваются перечисленным, RAM, ROM, EEPROM, флеш-память или другие технологии памяти, CD-ROM, универсальные цифровые диски (DVD) или другие оптические запоминающие устройства, магнитные кассеты, магнитные ленты, запоминающие устройства на магнитных дисках или другие магнитные запоминающие устройства или любой другой носитель, который может быть использован для сохранения желаемой информации и который доступен компьютеру.

"Средства связи", как правило, включают машиночитаемые инструкции, структуры данных, программные модули или другие данные в модулированном информационном сигнале, таком как сигнал с несущей частотой или другой механизм передачи. Также "средства связи" включают какую-либо среду передачи информации. Термин "модулированный информационный сигнал" означает сигнал, у которого одна или более характеристик устанавливаются или изменяются так, чтобы зашифровать информацию в сигнале. Для примера, но без ограничения общности, средства связи включают носители информации в виде провода, например проводную сеть или прямое проводное соединение, и беспроводные носители информации, такие как акустические, радиочастотные (РЧ), инфракрасные (ИК), беспроводные высокой точности воспроизведения (например, беспроводная сеть на основе стандарта IEEE 802.11b) (Wi-Fi), сотовые, созданные на основе Bluetooth, и другие беспроводные средства связи. Комбинации любых вышеприведенных средств также попадают под определение машиночитаемых носителей.

ЗАКЛЮЧЕНИЕ

Хотя изобретение описано в терминах, характерных для структурных признаков и действий способа, понятно, что изобретение, определенное нижеследующей формулой изобретения, не обязательно ограничено описанными конкретными признаками и действиями. Напротив, эти конкретные признаки и действия раскрываются как примерные формы реализации заявляемого изобретения. Например, эллиптические кривые, описанные в данном документе, являются одномерным случаем абелевых множеств. Также изогении могут применяться в других приложениях, например с использованием слепой подписи в иерархических системах, и тому подобных. По существу описанные методы могут быть применены к абелевым множествам более высокой размерности.

Изобретение относится к области шифрования с открытым ключом. Технический результат заключается в повышении защищенности криптосистем. Сущность изобретения заключается в том, что изогении абелевых множеств (например, эллиптических кривых, в одномерном случае) используются для обеспечения системы шифрования с открытым ключом. Например, изогении допускают использования множества кривых вместо единственной кривой для обеспечения большей надежности. Данные методы могут быть применены в способах идентификационного шифрования (IBE) и цифровой подписи. Кроме того, изогении могут быть использованы в других приложениях, таких как слепая подпись, иерархических системах и тому подобном. Дополнительно раскрыты решения для генерации изогении. 4 н. и 31 з.п. ф-лы, 6 ил.

1. Способ шифрования сообщений, содержащий:
генерацию изогении, отображающей множество точек от первой эллиптической кривой на вторую эллиптическую кривую;
опубликование открытого ключа, соответствующего изогении;
шифрование сообщения с использованием ключа шифрования, соответствующего изогении; и
дешифрование зашифрованного сообщения при помощи ключа дешифрования, соответствующего изогении,
при этом, по меньшей мере, один из ключа шифрования или ключа дешифрования является секретным ключом, причем секретный ключ является дуальной изогенией к упомянутой изогении.

2. Способ по п.1, в котором изогения генерируется с использованием метода, выбранного из группы, содержащей генерацию при помощи комплексного умножения, модулярную генерацию, линейно независимую генерацию и их комбинации.

3. Способ по п.1, в котором генерация отображает множество точек от первой эллиптической кривой на множество эллиптических кривых.

4. Способ по п.1, в котором дешифрование выполняется при помощи билинейного образования пар.

5. Способ по п.4, в котором билинейное образование пар выбрано из группы, содержащей образование пар по Вейлу, образование пар по Тейту и квадратичное образование пар.

6. Способ по п.1, в котором способ применяется с использованием абелевых множеств.

7. Способ по п.1, в котором способ используется для подписи сообщения.

8. Способ по п.1, в котором способ обеспечивает идентификационное шифрование.

9. Способ по п.1, дополнительно включающий формирование множества модулярных изогений для обеспечения изогении без раскрытия промежуточных кривых.

10. Способ по п.1, дополнительно включающий использование отображения следа на базовое поле для уменьшения количества точек на эллиптической кривой, отображаемых изогенией.

11. Способ по п.1, дополнительно включающий использование отображения следа для уменьшения точек на абелевом множестве.

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

13. Способ по п.12, в котором изогения генерируется с использованием методов, выбранных из группы, содержащей генерацию при помощи комплексного умножения, модулярную генерацию, линейно независимую генерацию и их комбинации.

14. Способ по п.12, в котором изогения отображает множество точек от первой эллиптической кривой на множество эллиптических кривых.

15. Способ по п.12, в котором дешифрование выполняется при помощи билинейного образования пар.

16. Способ по п.15, в котором билинейное образование пар выбрано из группы, содержащей образование пар по Вейлу, образование пар по Тейту и квадратичное образование пар.

17. Способ по п.12, в котором способ применяется с использованием абелевых множеств.

18. Способ по п.12, в котором способ используется для подписи сообщения.

19. Способ по п.12, в котором способ обеспечивает идентификационное шифрование.

20. Способ по п.12, дополнительно включающий использование отображения следа на базовое поле для уменьшения количества точек на эллиптической кривой, отображаемых изогенией.

21. Система шифрования сообщений, содержащая: первый процессор;
первую системную память, соединенную с первым процессором, причем первая системная память хранит открытый ключ, соответствующий изогении, отображающей множество точек от первой эллиптической кривой на вторую эллиптическую кривую;
второй процессор;
вторую системную память, соединенную со вторым процессором, причем вторая системная память хранит зашифрованное сообщение и ключ дешифрования, соответствующий изогении, для дешифрования сообщения;
при этом зашифрованное сообщение зашифровано с использованием ключа шифрования, и
при этом, по меньшей мере, один из ключа шифрования или ключа дешифрования является секретным ключом, причем секретный ключ является дуальной изогенией к упомянутой изогении.

22. Система по п.21, в которой изогения отображает множество точек от первой эллиптической кривой на множество эллиптических кривых.

23. Система по п.21, в которой дешифрование выполняется при помощи билинейного образования пар.

24. Способ по п.23, в котором билинейное образование пар выбрано из группы, содержащей образование пар по Вейлу, образование пар по Тейту и квадратичное образование пар.

25. Машиночитаемый носитель, имеющий инструкции, сохраненные на них, которые при исполнении предписывают компьютеру выполнение действий, включающих в себя:
опубликование открытого ключа, соответствующего изогении, отображающей множество точек от первой эллиптической кривой на вторую эллиптическую кривую; и
дешифрование зашифрованного сообщения с использованием ключа дешифрования, соответствующего изогении,
при этом ключ дешифрования является секретным ключом, причем секретный ключ является дуальной изогенией к упомянутой изогении.

26. Машиночитаемый носитель по п.25, причем изогения генерируется с использованием метода, выбранного из группы, содержащей генерацию при помощи комплексного умножения, модулярную генерацию, линейно независимую генерацию и их комбинации.

27. Машиночитаемый носитель по п.25, причем изогения отображает множество точек от первой эллиптической кривой на множество эллиптических кривых.

28. Машиночитаемый носитель по п.25, причем дешифрование выполняется при помощи билинейного образования пар.

29. Машиночитаемый носитель по п.28, причем билинейное образование пар выбирается из группы, содержащей образование пар по Вейлу, образование пар по Тейту и квадратичное образование пар.

30. Машиночитаемый носитель по п.25, причем упомянутые действия выполняются с использованием абелевых множеств.

31. Машиночитаемый носитель по п.25, причем упомянутые действия дополнительно включают применение отображения следа на базовое поле для уменьшения количества точек на эллиптической кривой, отображаемых изогенией.

32. Машиночитаемый носитель по п.25, причем упомянутые действия дополнительно включают формирование множества модулярных изогений для обеспечения изогений без раскрытия промежуточных кривых.

33. Машиночитаемый носитель по п.25, причем упомянутые действия дополнительно включают использование отображения следа для уменьшения точек на абелевом множестве.

34. Машиночитаемый носитель по п.25, причем упомянутые действия используются для подписи сообщения.

35. Машиночитаемый носитель по п.25, причем действия обеспечивают идентификационное шифрование.