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×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 подается на вход функции хэширования. Если этого не сделать, то возможна атака, подобная атаке на шифр Эль-Гамаля.

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


 

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

41506. ТЕХНОЛОГИЯ РАБОТЫ ПАРКОВ ОТПРАВЛЕНИЯ 144.5 KB
  На сортировочной станции А производится смена поездных локомотивов у всех поездов как транзитных так и прибывших в расформирование. На сортировочной станции Б четные и нечетные поезда отправляются с локомотивами депо 1; у транзитных поездов смена локомотивов не производится только смена бригад. Могут быть любые другие сочетания участков обращения локомотивов с участками работы локомотивных бригад. В зависимости от схемы обслуживания поездов поездными локомотивами и локомотивными бригадами на сортировочных станциях с локомотивами могут...
41507. ТЕХНОЛОГИЯ РАБОТЫ СОРТИРОВОЧНЫХ ПАРКОВ. ПРОЦЕСС НАКОПЛЕНИЯ ВАГОНОВ В СОРТИРОВОЧНОМ ПАРКЕ 109 KB
  Процесс накопления вагонов отдельного назначения его показатели. Процесс накопления вагонов отдельного назначения его показатели. График накопления вагонов отдельного назначения.
41508. Технология работы станции с местными вагонами 120 KB
  Планирование и организация подачи и уборки вагонов на грузовой пункт. По характеру грузовых операций различают 4 вида местных вагонов: прибывшие в груженом состоянии под выгрузку; прибывшие в порожнем состоянии под погрузку; прибывшие гружеными выгруженными загруженные вновь со сдвоенными операциями; сборные вагоны и вагоны с контейнерами проходящие грузосортировку. С ними выполняются те же операции что и с транзитными вагонами с переработкой но кроме того с местными вагонами производятся: подача к грузовым пунктам...
41509. График движения поездов 174.5 KB
  Он представляет собой графическое изображение следования поездов на масштабной сетке на которой движение поездов изображаются прямыми наклонными линиями линиями хода поездов. Графики движения поездов различают: в зависимости от соотношения скоростей движения разных поездов по одному и тому же перегону параллельные и непараллельные. В параллельных графиках поезда имеют одинаковую скорость и линии их хода на данном перегоне параллельны а в непараллельных графиках линии хода поездов с разными скоростями; по числу...
41510. ЗАКРЕПЛЕНИЕ ВАГОНОВ 33 KB
  При уходе подвижного состава на перегон ДСП обязан используя все имеющиеся в его распоряжении средства сообщить об этом машинистам поездов находящимся на перегоне ДПИ дежурным путевых постов соседней станции переездов и другим работникам чтобы задержать встречные поезда и принять меры к остановке ушедших вагонов. При закреплении составов поездов: на главные и к о путях руководство и контроль за закреплением осуществляет ДСП в отдельных маневровых районах ДСЦ; ДСП может разрешить отцепку локомотива только после убеждения в...
41511. ОРГАНИЗАЦИЯ РАБОТЫ СТАНЦИОННЫХ ТЕХНОЛОГИЧЕСКИХ ЦЕНТРОВ 49.5 KB
  Назначение и размещение СТЦ и ИЦ. Операции выполняемые в СТЦ и ИЦ. Оборудование СТЦ. Назначение и размещение СТЦ и ИЦ.
41512. ОСНОВНЫЕ ПОКАЗАТЕЛИ ЭКСПЛУАТАЦИОННОЙ РАБОТЫ 100 KB
  Качественные показатели использования вагонов и локомотивов. Подача вагонов по стыковым пунктам дорог где n число стыковых пунктов; . число вагонов переданных за сутки в сумме чётного и нечётного направлений. По каждому стыковому пункту выделяют общий приём Uпр состоящий из суммы приёма гружённых и порожних а также общую сдачу складывающуюся из сдачи гружёных и порожних вагонов .
41513. Психологія особистості керівника 311 KB
  Феномен керівника в історії розвитку суспільства Мотиваційна сфера особистості керівника Труднощі вимоги та обмеження у роботі керівників Якості і риси керівника Проблема статі в управлінні Ортобіоз особистості керівника Регресивний розвиток керівника та управлінська деформація 1.Феномен керівника в історії розвитку суспільства Давні історичні політичні та соціальні вчення Єгипту Китаю Греції Риму та інших країн відображали не лише основні риси ранніх типів суспільства а й певні характерологічні особливості правителів...
41514. ПСИХОЛОГІЧНІ ЧИННИКИ ОЦІНЮВАННЯ УПРАВЛІНСЬКИХ КАДРІВ 110.5 KB
  Роль оцінювання працівників у процесі управління Соціальнопсихологічні завдання оцінювання Оцінювання за головними параметрами діяльності класифікація характеристика елементів класифікації Установки і форми поведінки керівників під час оцінювання підлеглих Характеристика сучасного менеджера управлінця 1. Роль оцінювання працівників у процесі управління Оцінювання працівників є складовою процесу управління. Головна мета оцінювання: 1.