28566

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

Доклад

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

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

Русский

2013-08-20

86.42 KB

2 чел.

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

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


 

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

24633. Облік основних засобів 30 KB
  Облік основних засобів.Основні засобиїх класифікація і оцінка Методологією обліку основних засобів визначає ПсБО7Основні засоби. Обєкт основних засобів це закінчений пристрій з усіма пристосуваннями або окремий конструктивно відокремлений предмет що призначений для виконання певних самостійних функцій. Облік основних засобів ведеться на активному балансовому рахунку 10 – основні засоби.
24634. Облік нематеріальних активів 29 KB
  Облік нематеріальних активів Методологію обліку нематеріальних активів визначає ПсБО 8 нематеріальні активи Нематеріальний актив це актив який немає матеріальної форми може бути ідентифікований та утримується підприємством з метою використання на протязі більше одного року. Бух облік немат активів ведеться щодо кожного об’єкта за такими групами: А права користування природними ресурсами Б права користування майном В права на знаки для товарів і послуг тов.знаки торгові марки фірмові назви і т д Г права на об’єкти промислової...
24635. Особливості обліку МШП терміном експлуатації до і більше 1 року 32.5 KB
  Положенням стандартом 9 передбачено що з метою бухгалтерського обліку запаси включають:малоцінні і швидкозношувані предмети які використовуються не більше одного року або одного операційного циклу якщо він більше року. Малоцінні і швидкозношувані предмети строк корисного використання яких більше одного року обліковуються в складі інших необоротних матеріальних активів. Організація обліку малоцінних і швидкозношуваних предметів зі строком корисного використання менше одного року або одного операційного циклу повинна повністю...
24636. Амортизація необоротних активів. Методи нарахування та облік амортизації 30.5 KB
  Амортизація – це систематичний розподіл вартості яка амортизується протягом строку їх корисного використання. Зменшення залишкової вартості – виходить з того що корисність і продуктивність необ. Норма амортизації застосовується не до вартості що амортизується а до балансової залишкової вартості об’єкта на кінець попереднього періоду. Прискореного зменшення залишкової вартості складається у визначенні річної суми амортизації об’єкту основних засобів виходячи з основної вартості такого об’єкту на початок звітного року.
24637. Аналіз власного оборотного капіталу 35 KB
  Аналіз власного оборотного капіталу. Фінансовий стан підприємства залежить від того наскільки раціонально сформовані джерела фінансування поточних активів оборотного капіталу. Поточні активи створюються як за рахунок власного капіталу так і за рахунок короткострокових позикових коштів. Бажано щоб наполовину вони були сформовані за рахунок власного а наполовину за рахунок позикового капіталу.
24638. Аналіз фінансової стійкості підприємства 25.5 KB
  Аналіз фінансової стійкості підприємства. Аналіз фінансової стійкості підприємства здійснюється шляхом розрахунків таких показників: 1.коефіцієнт автономії Кавт – відношення власного капіталу підприємства до підсумку балансу підприємства.Характеризує залежність підприємства від залучених засобів: Кф = ф1 р430 р480 р620 р630 ф1 р380 Нормативне значення Кф = 1 3.
24639. Аналіз платоспроможності і ліквідності підприємства 37 KB
  Аналіз платоспроможності і ліквідності підприємства. В умовах ринкових відносин платоспроиожність підприємства вважається найважливійшою умовою їх господарської діяльності. Платоспроможність підприємства характеризується можливостями його здійснювати чергові платежі та грошові зобов’язання за рахунок наявних грошей і тих грошових засобів і активів які легко мобілізуються. Відповідно на три групи поділяються і платіжні зобов’язання підприємства:1.
24640. Аналіз оборотності оборотних коштів підприємства 27.5 KB
  Аналіз оборотності оборотних коштів підприємства. Величина обігових коштів їхні структура і достатність характеризують кількісний бік обігових коштів проте є і якісний пов'язаний зі швидкістю їх обороту оборотністю. Між сумою обігових коштів та показниками оборотності існують тісні зворотні взаємозв’язки. Прискорення оборотності цих коштів сприяє вирішенню фінансових проблем найбільш зручним способом за рахунок використання існуючих внутрішніх резервів підприємства.
24641. Оцінка витрат на оплату праці 29 KB
  Оцінка витрат на оплату праці. У більшості галузей промисловості витрати на оплату праці мають значно меншу частку в собівартості продукції ніж матеріальні витрати. Проте загальновідомо що одним з найважливіших джерел зниження собівартості продукції є більш швидке зростання продуктивності праці порівняно із середньою оплатою праці. Тому аналізові витрат на оплату праці слід завжди приділяти першочергову увагу.