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

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


 

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

65689. ОПТИМІЗАЦІЯ ДИФЕРЕНЦІЙНОЇ ДІАГНОСТИКИ ДОБРОЯКІСНИХ ПУХЛИН ТА ПУХЛИНОПОДІБНИХ УТВОРЕНЬ ЯЄЧНИКІВ 266 KB
  Для досягнення мети поставлені такі задачі: Дати клінічну характеристику пацієнток із доброякісними новоутвореннями яєчників та оцінити діагностичну чутливість та специфічність ультразвукових методів трансабдомінальна трансвагінальна сонографія та допплерометрія...
65690. МОРФОГЕНЕТИЧНІ ПАРАЛЕЛІ РОЗВИТКУ СЕРЦЯ ТА ПЛАЦЕНТИ В ПРЕНАТАЛЬНОМУ ОНТОГЕНЕЗІ 4.49 MB
  Доведено що ембріон людини найбільш чутливий до будь-яких ушкоджувальних чинників у перші дні і тижні його внутрішньоутробного розвитку коли відбувається формування ранньої плаценти структурної основи взаємодії між матірю та ембріоном Петренко В.
65691. ГЕОЛОГО-ЕКОНОМІЧНИЙ АНАЛІЗ МІНЕРАЛЬНО-СИРОВИННОЇ БАЗИ БЕНТОНІТОВИХ ГЛИН УКРАЇНИ 1.86 MB
  Бентонітові глини мінеральна сировина багатоцільового призначення яка характеризується сукупністю корисних фізико-механічних і хімічних властивостей таких як пластичність здатність до набрякання висока сорбційна активність. Всі обєкти мінерально-сировинної бази МСБ бентонітових глин України характеризуються різним ступенем вивченості.
65692. ВІК, ГЕОХІМІЧНІ ОСОБЛИВОСТІ ТА МОЖЛИВІ ДЖЕРЕЛА ПОХОДЖЕННЯ ДЕТРИТОВОГО МОНАЦИТУ ТЕРИТОРІЇ УКРАЇНИ 731 KB
  Однак до сьогоднішнього часу плутонічні породи такого віку на УЩ не знайдені а волинські трапи вулканіти ДніпровоДонецької западини ДДЗ і Донецького басейну дайки відповідного віку УЩ не могли дати такої кількості теригенного монациту оскільки представлені породами переважно основного складу в яких монацит практично відсутній.
65693. СОЦІАЛІЗАЦІЯ ПІДЛІТКІВ НА ОСНОВІ ХУДОЖНЬО-ЕСТЕТИЧНИХ ТРАДИЦІЙ ЕТНОКУЛЬТУРНОЇ СПІЛЬНОТИ ДОНБАСУ 178 KB
  Ринкові пріоритети сучасного суспільства визначають орієнтири соціальних якостей особистості які раніше не висувалися до неї покладання на власні сили ініціативу розширення індивідуальної свободи та відповідальності значущість особистісного успіху що зумовлює змістовну зміну збагачення процесів соціалізації особистості.
65694. ФІЗИЧНА РЕАБІЛІТАЦІЯ ОСІБ З РОЗСІЯНИМ СКЛЕРОЗОМ У КОМПЛЕКСНІЙ ТЕРАПІЇ В УМОВАХ СТАЦІОНАРУ 287.5 KB
  У роботах попередніх років переважали рекомендації щодо обмеження працездатності хворих і встановлення інвалідності при перших проявах захворювання. У роботах останніх років звучать рекомендації щодо підтримки максимальної психо-емоційної...
65695. РОБОТА І РОЗРАХУНОК ЕЛЕМЕНТІВ КІЛЬЦЕВОГО ПЕРЕРІЗУ ЗІ СТАЛЕФІБРОБЕТОНУ ПРИ ПОВТОРНИХ НАВАНТАЖЕННЯХ 1.99 MB
  Так практично не досліджена робота елементів кільцевого перерізу зі сталефібробетону. Відомо що переважна більшість конструкцій піддається дії повторних навантажень це також стосується і елементів кільцевого перерізу. З огляду на наведе дослідження особливостей роботи...
65696. Математичні моделі оцінювання стратегічного потенціалу підприємства та прийняття рішень щодо його підвищення 329 KB
  Велика кількість існуючих моделей та методологічних підходів до визначення СПП дає можливість керівникам здійснити вибір засобів прийняття рішення щодо подальшого розвитку підприємства проте жоден з існуючих підходів не є достатньо ефективним як за критерієм повноти аналізованої інформації...
65697. УДОСКОНАЛЕННЯ ВИЗНАЧЕННЯ СТРАТЕГІЇ ПІДПРИЄМСТВА В УМОВАХ КРИЗИ НА ОСНОВІ ЗБАЛАНСОВАНОЇ СИСТЕМИ ПОКАЗНИКІВ 1.13 MB
  Сучасна фінансова, політична та економічна нестабільність в Україні, головними ознаками якої є високе боргове навантаження на вітчизняну економіку, негативні тенденції на грошово-кредитному ринку, ринку праці та у промисловості – провідній галузі вітчизняної економіки...