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

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


 

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

23271. Поняття філософії економіки 29 KB
  По б у то в ий це рівень філософії людини яка прагне шляхом генерування і реалізації своїх ідей забезпечити собі та своїй сімї нормальне життя. Державний рівень церівень державного мислення сконцентрованих дій спрямованих на розвиток економіки всієї країни зростання продуктивних сил і національного багатства підвищення добробуту народу. Державний рівень економічної філософії найважливий рівень який є філософською основою розвитку.
23272. Бальзак 31.47 KB
  На початку 30х років у Бальзака виникає задум створити цикл романів в яких він хотів змалювати сучасну йому Францію дослідити суспільство визначити рушійні сили його розвитку основні типи і характери людей. Остаточно зміст і структуру цього твору Бальзак визначив на початку 40х років тоді ж і виникла назва Людська комедія . Бальзак порівнює життя суспільства з життям природи тому ставить собі за мету описати його визначити основні види типи на які поділяється суспільство. Вміння Бальзака розкривати органічний взаємозв'язок окремого...
23274. Історичні романи В.Скотта 18.43 KB
  Історизм Скотта не тільки антикварний а й те як люди виявляли себе в той чи інший період. Позиція Скотта ніколи не переміщувати обєкт погляду на історію власний погляд на рух історії історія ніколи не йде крайнощами вона завжди знайде десь серединний шлях. В його пригодах найбільше приваблює читача не розповідь про кохання до шляхетної і цнотливої леді Ровени з якою Айвенго врештірешт щасливо одружується а його романтична закоханість у красунюєврейку Ревекку один з найпривабливіших жіночих характерів у Скотта дівчину із...
23275. Гофман 20.18 KB
  Гротескнофантастичний романтизм Гофмана На останньому етапі творчості Гофмана остаточно визначається його гротескнофантастичний романтизм. Але найуживанішим і найефективнішим художнім засобом стає у Гофмана гротескгротеск це вільне й примхливе поєднання різних образів і мотивів вільна гра з ними викличне ігнорування раціоналістичної розсудливості й зовнішньої правдоподібності. У цьому плані дуже характерним твором Гофмана є повістьказка Малюк Цахес яка повністю складається з образівгротесків гротескних ситуацій і вся є...
23276. Гюго 22.53 KB
  Гюго Оди й різні вірші 1822 до якої ввійшли вірші створені переважно за правилами класицизму. Відкинувши класицистичну нормативність Гюго ввів у французьку поезію нові форми й розміри створив нову систему віршування велику увагу приділив звуковій організації вірша його ритмомелодиці. останній роман Гюго присвячений революції 93 рік 1874 р. Поезія Гюго.
23277. Диккенс 23.65 KB
  Діккенса можна поділити на чотири періоди. Показовим для цього періоду творчості Діккенса є побудований на матеріалах побутового нарису роман Посмертні нотатки Піквікського клубу 1837. Другий період творчості Чарлза Діккенса Другий період творчості письменника значною мірою пов'язаний з закордонними подорожами письменника по Італії Швейцарії Франції США. У цей час ще яскравіше проявився талант Діккенсапубліциста Американські замітки майстра нарисів Картини Італії .
23278. Едгар По Творчий доробок 19.49 KB
  По 373839 Творчий доробок його талант багатогранний це проза поезія літкритичні статті рецензії науковоастрономічна поема засновник детективного жанру у літру ввійшов як новеліст 64 новели перша Рукопис знайдений у пляшці одне з найкращий оповідань Золотий жук двотомна збірка оповідань Гротески та арабески поезія Крук Оповідання По відрізняються одне від одного сюжетом настроєм тональністю так що здається важко знайти для них якийсь тематичний і стилістичний спільний знаменник за яким ми пізнаємо руку того...
23279. Творчість Еспронседи (байронізм) 20.43 KB
  Еспронседа не відразу знайшов свій поетичний шлях. Другий період творчості ЕспронседаіДельґадо розпочався у 1833 р. ЕспронседаіДельґадо поет пов'язаний з іспанською національною традицією. У своїй творчості ЕспронседаіДельґадо звертався до змалювання сучасного йому суспільства особливо яскраво це прослідковується у таких його поезіях як Злочинець засуджений до страти Кат Злидар.