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

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


 

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

13382. ЗНАКОМСТВО С PHOTOSHOP. Растровые графические редакторы 39.09 KB
  Растровые графические редакторы. Работа с растровой графикой Растровая графика представляет изображения в виде массива цифр. Поэтому при большом увеличении все точечные изображения выглядят как мозаика или се
13383. Створення публікацій за допомогою програми Publisher 800.5 KB
  Лабораторна робота № 17 Тема: Створення публікацій за допомогою програми Publisher Мета: Сформувати практичні вміння та навички роботи в програмі Publisher Засвоїти поняття: сценарій публікація рамка текстова рамка шаблон цвіто...
13384. Основи роботи з векторною графікою. Середовище CorelDraw 13.44 MB
  Лабораторна робота № 1 Тема: Основи роботи з векторною графікою. Середовище CorelDraw Мета: Освоїти основні прийоми роботи в середовищі CorelDraw. Навчитися користуватися головним меню програми панелями інструментів та атрибутів. Навчитися будувати основі фігури трансформ...
13385. РОЛЬ МАРКЕТИНГОВЫХ ИССЛЕДОВАНИЙ В РЕАЛИЗАЦИИ СТРАТЕГИЧЕСКИХ НАПРАВЛЕНИЙ РАЗВИТИЯ ПРЕДПРИЯТИЯ 876 KB
  Маркетинг представляет собой нечто большее, чем просто продвижение товаров и услуг на рынок. Заставить покупателя купить то, что может предложить компания задача сбыта. С помощью маркетинга заставляют предприятие делать то, что необходимо потребителю
13386. ДИФФЕРЕНЦИАЛЬНАЯ ДИАГНОСТИКА И ЛЕЧЕНИЕ ПРИ СИНДРОМЕ АРТЕРИАЛЬНОЙ ГИПЕРТЕНЗИИ 168 KB
  Алгоритм дифференциальной диагностики заболеваний, сопровождающихся синдромом артериальной гипертензии. Этиологию, патогенез, клинику и диагностику заболеваний и состояний, сопровождающихся синдромом артериальной гипертензии.
13387. CORELDRAW. ПОСТРОЕНИЕ СЛОЖНЫХ ОБЪЕКТОВ 307.38 KB
  Лабораторная работа N 3 CORELDRAW. ПОСТРОЕНИЕ СЛОЖНЫХ ОБЪЕКТОВ Дополнительные приемы работы с объектами Программа CorelDraw предоставляет большие возможности по созданию и редактированию сложных объектов. Команды позволяющие выполнять различные операции над объектами с...
13388. CORELDRAW. ИНТЕРАКТИВНОЕ ПЕРЕТЕКАНИЕ. ИМИТАЦИЯ ОБЪЕМА 345.39 KB
  Лабораторная работа N 4 CORELDRAW. ИНТЕРАКТИВНОЕ ПЕРЕТЕКАНИЕ. ИМИТАЦИЯ ОБЪЕМА Эффект Интерактивное перетекание Инструмент Интерактивное перетекание относится к категории интерактивных инструментов находящихся на панели инструментов. При помощи данного инстр
13389. CORELDRAW. POWERCLIP. ОБРАБОТКА РАСТРОВЫХ ИЗОБРАЖЕНИЙ 267.4 KB
  Лабораторная работа N 5 CORELDRAW. POWERCLIP. ОБРАБОТКА РАСТРОВЫХ ИЗОБРАЖЕНИЙ Совокупность команд PowerClip Фигурная обрезка Команды находятся в меню Эффекты. Данное подменю содержит четыре команды: Place Inside Container Поместить в контейнер Extract Contents Извлечь содержимое Edit Contents Р...
13390. CORELDRAW. ИНТЕРАКТИВНЫЙ ОБЪЕМ 361.88 KB
  Лабораторная работа N 6 CORELDRAW. ИНТЕРАКТИВНЫЙ ОБЪЕМ Инструмент Интерактивный объем Данный инструмент позволяет создавать иллюзию объема для плоских объектов. Иллюзия возникает изза того что за объектом или перед ним достраивается дополнительная плоскость той же ...