ID: 28566

Название работы: Проблема дискретного логарифмирования, аутентификация

Категория: Доклад

Предметная область: Информатика, кибернетика и программирование

Описание: Система строится из криптографических примитивов низкого уровня:групповой операции симметричного шифра функции хэширования и алгоритма вычисления кода аутентификации сообщенияимитовставки MAC. Код аутентификации сообщения позволяет пользователям обладающим общим секретным ключом выработать битовую строку для аутентификации и проверки целостности данных Пусть Msg = {01} пространство сообщений mKey = {01}mLen пространство ключей для вычисления MAC для некоторого mLen N Tag = {01}tLen включающее множество всех возможных...

Язык: Русский

Дата добавления: 2013-08-20

Размер файла: 86.42 KB

Работу скачали: 4 чел.

1.  Проблема дискретного логарифмирования, аутентификация

Система шифрования была представлена Мишелем Абдаллой, Михиром Беллэром и Филлипом Рогэвэем в рамках европейского проекта NESSIE (New European Schemes for Signatures, Integrity and Encryption). Она столь же эффективна, что и система Эль-Гамаля, но обладает дополнительными свойствами безопасности.

Данная криптосистема реализуема на основе любой циклической группы, для которой может быть  сформулирована проблема Диффи-Хеллмана, например в {Zp*} или в группе точек на эллиптической кривой.Система строится из криптографических примитивов низкого уровня:групповой операции, симметричного шифра, функции хэширования и алгоритма вычисления кода аутентификации сообщения-имитовставки (MAC). Стойкость доказывается на основе предположения о сложности решения соответствующей проблемы Диффи-Хеллмана и предположения о стойкости входящих в схему симметричных примитивов.Опишем криптографические примитивы, входящие в схему.

Циклическая группа G = {g}. Далее будем использовать мультипликативную запись групповой операции. Алгоритмы, реализующие эту операцию, будут работать с представлениями элементов группы в виде битовых строк фиксированной длины gLen € N. Способ кодирования G →{0,1}gLen не фиксируется и может быть выбран из соображений эффективности.

Код аутентификации сообщения позволяет пользователям, обладающим общим секретным ключом, выработать битовую строку для аутентификации и проверки целостности данных Пусть Msg = {0,1}* – пространство сообщений, mKey = {0,1}mLen – пространство ключей для вычисления MAC для некоторого mLen € N, Tag = {0,1}tLen – включающее множество всех возможных значений MAC для некоторого tLen €N. В этих обозначениях код аутентификации сообщений представляет собой пару алгоритмов MAC =

{MAC.gen, MAC.ver}. Алгоритм генерации MAC определяется как отображение MAC.gen(k,x):mKey×Msg→Tag и может быть вероятностным. Алгоритм верификации MAC является отображением со свойством MAC.ver(k,x,MAC.gen(k,x))=1.

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

Симметричный шифр позволяет пользователям, обладающим общим секретным ключом, обеспечить секретность. Пусть Msg, как и ранее, пространство сообщений, eKey = {0,1}eLen – пространство ключей для некоторого eLen € N, Ctext = {0,1}* – включающее множество всех возможных значений шифрованного текста и Coins = {0,1}∞ – множество строк бесконечной длины. В этих обозначениях шифр представляет собой пару алгоритмов SYM = {SYM.enc, SYM.dec}. Алгоритм зашифрования определяется как отображение

SYM.enc(k,x,r):eKey ×Msg×Coins→Ctext , алгоритм расшифрования является отображением

SYM.dec(k,y):eKey ×Ctext→MsgUu{BAD}, где значение BAD выдается, если шифртекст у не является результатом зашифрования никакого открытого текста.

Асимметричный шифр. Пусть Msg, Ctext, Coins определены как и ранее, PK G{0,1}* , SK G{0,1}* – множества открытых и секретных ключей.Асимметричный шифр определяется как тройка алгоритмов

ASYM ={ASYM.enc, ASYM.dec, ASYM.Key}. Алгоритм зашифрования является отображением

ASYM.enc(pk,x,r):PK × Msg×Coins→Ctext ,а расшифрования: ASYM.enc(sk,y):SK ×Ctext→MsgUu{BAD}.

Алгоритм выработки ключа в качестве аргумента берет строку r €Coins и выдает пару ключей

pk, sk € PK × SK . При этом должно выполняться следующее свойство:

@ (pk,sk): r’€ Coins: (pk,sk)= ASYM.key (r’), @ r €Coins

@x €Msg ASYM.dec( sk, ASYM.enc( pk, x, r))=.

Функция хэширования является отображением следующего вида: H :{0,1)2gLen →{0,1)mLen+eLen .

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

Рис. 3.2. Процесс зашифрования

Все ключевые пары в данном алгоритме выбираются так же, как и в криптосистеме Эль-Гамаля, т.е. пара (pk, sK) = (gv, v) для некоторого случайного v. При отсылке сообщения выбирается некоторое случайное значение и и получателю отсылается gu, что обеспечивает неявный обмен ключами по сxеме Диффи-Хеллмана. Таким образом, зашифрованное сообщение состоит из одноразового открытого ключа, текста, зашифрованного симметричным шифром, и кода аутентификации сообщения, выработанно-

го с помощью алгоритма MAC.gen.

Процесс расшифрования и аутентификации графически представлен на рис. 3.3. Элементы принятого сообщения также выделены двойной рамкой.

Рис. 3.3. Процесс расшифрования и аутентификации

Рассмотренная криптосистема является семантически стойкой и неделимой. В частности, неделимость обеспечивается тем, что значение gu подается на вход функции хэширования. Если этого не сделать, то возможна атака, подобная атаке на шифр Эль-Гамаля.

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