28566

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

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-08-20

86.42 KB

3 чел.

  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×MsgTag и может быть вероятностным. Алгоритм верификации 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×CoinsCtext , алгоритм расшифрования является отображением

SYM.dec(k,y):eKey ×CtextMsgUu{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×CoinsCtext ,а расшифрования: ASYM.enc(sk,y):SK ×CtextMsgUu{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 подается на вход функции хэширования. Если этого не сделать, то возможна атака, подобная атаке на шифр Эль-Гамаля.

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


 

А также другие работы, которые могут Вас заинтересовать

54910. Житло. Домашні обовязки 99.5 KB
  Today we’ll continue speaking about your home duties. We’re going to lay the table, cook some dishes, do some grammar exercises, listen to the text about different household machines and of cause to have a little rest after hard work.
54911. РОССИЯ ПРИ ПАВЛЕ I 109.5 KB
  Тип урока: комбинированный Цели урока: Образовательные: определить цели задачи осветить основные направления внутренней и внешней политики Павла I и подвести ее итоги; Воспитательные: указать на возможность негативных последствий изоляции ребенка Павла I от родителей постепенно формирующаяся враждебность по отношению к родителям неконтролируемая самостоятельность ожидание подходящего случая все изменить; вызвать сочувствие к судьбе простых людей крестьян и указать на то что облегчение жизни людей зачастую зависит от...
54912. Техники бесшажного хода. Техника одновременного одношажного хода 40.5 KB
  Проверить наличие спортивной одежды соответствие её погодным условиям и видам занятия Проверка исправности и комплектации. В2 одновременным бесшажным ходом 27 минут. 5минут 7минут 10минут 5минут Следим за правильным выполнением техники. Очистка и сдача лыж 5 минут 1 минута 2 минуты 1 минута 1 минута В одну шеренгу.
54913. Внешняя политика России в конце 19 – начале 20 вв. Русско-японская война 1904 – 1905 гг. 35 KB
  Актуализация ЗУН учащихся Задание. слайд 1 Вопросы классу: С чем ассоциируется связана в вашем сознании война Ответы учащихся Слово учителя: Перед нами – проблемное задание: Как отразилась русско –японская война в сознании российского народа слайд 2 На него вы попытаетесь ответить в конце урока. Слайды 34 Основные направления внешней политики России – европейское и дальневосточное работа учащихся в тетрадях Задание: прочитайте материал учебника стр. Задание: Почему Япония стремиться к расширению своего влияния в Восточной...
54914. Гражданское общество и государство 36 KB
  Задачи Образовательная: сформировать представление учащихся о структуре и признаках гражданского общества; Развивающая: развивать умения учащихся анализировать тексты документов делать выводы составлять схемы; Воспитательная: Способствовать формированию у учащихся гражданского самосознания...
54915. Религия древних египтян 95 KB
  Тема урока класс: Религия древних египтян 5 А класс и 5 Б клас; Тип урока: урок повторения и проверки полученных ранее знаний получение новых знаний комбинированный.Вигасина Цели урока: 1. Этапы или ход урока: Время Этап урока Цель этапа урока Деятельность учителя Деятельность учеников 2 Орг.
54916. Портрет в музыке 45.5 KB
  Я а сейчас ребята мы поприветствуем друг друга чтоб подарить каждому однокласснику частичку своего тепла и дружелюбности. А сейчас ребята я спою вам небольшую песенку про вас. Подумайте как она может называться В каком классе вы учитесь Правильно Песенка называется Мы третьеклассники...
54918. Жизнь диких животных осенью 72 KB
  Цели: познакомить учащихся с подготовкой к зиме диких животных кроме насекомых и птиц показать связь изменений в жизни животных осенью с изменениями в живой и неживой природе и в мире растений; создать условия для приобретения новых знаний выявить общий уровень знаний о диких животных; расширить и углубить знания о диких животных и привести их в систему; выявить уровень усвоения понятий; обобщить знания детей по теме “Жизнь диких животных осеньюâ€. Оборудование: кроссворд плакат; слова отгадки; иллюстрации диких...