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

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


 

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

71158. Произвольная память младших школьников с нарушениями интеллекта в игровой деятельности 373 KB
  Важнейшая особенность психики состоит в том, что отражение высших воздействий используется индивидом в его дальнейшем поведении. Постепенное усложнение поведения осуществляется за счет накопления индивидуального опыта. Формирование опыта было бы невозможно,...
71159. Формирование познавательных универсальных учебных действий у учащихся младших классов на уроках математики с применением средств информационных и коммуникационных технологий 1.66 MB
  Понятие системы универсальных учебных действий учащихся младших классов. Функции универсальных учебных действий. Возрастные особенности формирования познавательных универсальных учебных действий у младших школьников.
71160. Структура и семантика терминологических словосочетаний по экономике в аналитической статье англоязычной прессы 407 KB
  Цель данного исследования выявить наиболее употребительные структурные модели терминологических словосочетаний по экономике в англоязычном газетном тексте установить закономерности их перевода на русский язык а также особенности их функционирования в текстах СМИ.
71162. Разработка предложений по повышению уровня кадрового потенциала и совершенствованию кадровой политики на ТОО «Крендель» 791.5 KB
  В современных экономических условиях для государства важно присутствие у рычагов управления предприятиями опытных руководителей способных использовать свои возможности в нужном направлении умеющих эффективно использовать кадровый потенциал предприятия.
71163. Основные особенности гражданско-правовой ответственности в РФ 127.11 KB
  Из них социальная ответственность обобщающее понятие включающее все виды ответственности в обществе а сама юридическая ответственность разновидность форма социальной ответственности. В праве говоря об ответственности имеют в виду как правило юридическую ответственность...
71164. Отличия учетной политики для целей налогообложения от учетной политики для целей бухгалтерского учета 44.32 KB
  Термин «учетная политика предприятия» вошел в употребление в конце восьмидесятых годов в качестве вольного перевода на русский язык словосочетания «accounting policies», употребляемого в стандартах, издаваемых Комитетом по международным стандартам бухгалтерского учета.
71165. Инвестиционная деятельность коммерческих банков на рынке ценных бумаг 633.5 KB
  Актуальность дипломной работы в том, что инвестиционные портфели активов выполняют ряд важнейших функций, обеспечивая банкам доходность, ликвидность и диверсификацию с целью снижения риска, а также выводя часть доходов банка из-под налогообложения.
71166. Понятие и виды пособий по действующему российскому законодательству 404.5 KB
  По продолжительности выплаты сохранились социальные пособия ежемесячные ежемесячные пособие на ребенка и по уходу за ребенком единовременные пособия при рождении ребенка при передаче ребенка на воспитание в семью и периодические пособие по беременности...