28566

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

Доклад

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

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

Русский

2013-08-20

86.42 KB

6 чел.

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

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


 

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

36517. Самодифузія. Коефіцієнт самодифузії, його залежність від тиску і температури 284.09 KB
  Цикл Карно і його к. Теореми Карно. У циклі Карно задача якомога спрощена. Цикл Карно виглядає наступним чином.
36518. В’язкість (внутрішнє тертя). Коефіцієнт в’язкості, його залежність від тиску і температури. Методи визначення коефіцієнту в’язкості. В’язкісний манометр 163.66 KB
  Коефіцієнт вязкості його залежність від тиску і температури. Методи визначення коефіцієнту вязкості. Коефіцієнтом пропорційності у цьому рівнянні є величина яка має назву коефіцієнта динамічної вязкості або коефіцієнта внутрішнього тертя. За одиницю динамічної вязкості у системі СІ приймається коефіцієнт вязкості такої речовини у якій за одиницю часу при градієнті швидкості рівному 1 с1 через площадку площею 1 м2 переноситься імпульс рівний 1 кгм с.
36519. Обертальний броунівський рух 201.25 KB
  Залежна від цих змінних внутрішня енергія є термодинамічним потенціалом або характеристичною функцією. Зауважте внутрішня енергія є термодинамічним потенціалом лише коли вона залежить від ентропії і температури . Коли внутрішня енергія залежить від інших змінних вона не буде термодинамічним потенціалом. Для адіабатного ізохорного процесу внутрішня енергія .
36521. Флуктуації. Міра флуктуації. Адитивність дисперсії 197 KB
  Фізичні величини що характеризують макроскопічне тіло яке знаходиться у стані рівноваги практично завжди з великою точністю дорівнюють своїм середнім значенням. Але відхилення від середнього значення все ж таки мають місце у звязку із чим виникає питання про знаходження розподілу ймовірностей цих відхилень. Ми ввели середнє значення як . Реальне значення величини практично завжди відрізняється від .
36522. ИННОВАЦИОННЫЙ МЕНЕДЖМЕНТ 60 KB
  Инновация считается осуществленной если она внедрена на рынке или в производственный процесс. Свойства инновации: научнотехническая или организационная новизна производственная применимость коммерческая реализуемость 5 основных признаков инновации по Шумпетеру: новый метод производства использование новой техники новых технологических процессов новый продукт новые свойства известного продукта использование нового сырья новых источников сырья новая или обновлённая структура управления появление новых рынков сбыта. Классификация...
36523. Процедуры общего вида в паскаль 24.5 KB
  Синтаксис: Procedure идентификатор или Procedure идентификатор параметры Замечания: В заголовке процедуры определяются ее идентификатор и набор формальных параметров если таковые есть. Заголовок процедуры сопровождается: 1разделом описаний в котором объявляются локальные объекты 2операторами находящимися между Begin и End которые определяют что должно быть выполнено при вызове процедуры. Вместо частей объявлений и операторов в объявлении процедуры могут присутствовать директивы Forwrd externl или InLine.
36524. Формальные и фактические параметры Правило соответствия 26.5 KB
  В каждую группу включаются параметры одного типа принадлежащие к одной категории. Все формальные параметры можно разбить на четыре категории: 1параметрызначения; 2параметрыпеременные; 2параметрыконстанты 4параметрыпроцедуры и параметрыфункции.
36525. Параметры - переменные, параметры-значения.Механизм передачи в подпрограмму и из нее 28.5 KB
  Список формальных параметров необязателен и может отсутствовать. Если же он есть то в нем должны быть перечислены имена формальных параметров и их типы например: Procedure SB: Rel; b: Integer; с: Chr; Как видно из примера параметры в списке отделяются друг от друга точками с запятой. Несколько следующих подряд однотипных параметров можно объединять в подсписки например вместо Function F: Rel; b: Rel: Rel; можно написать проще: Function Fb: Rel: Rel; Операторы тела подпрограммы рассматривают список формальных параметров как...