Главная | Обратная связь

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

Система шифрования была представлена Мишелем Абдаллой, Михиром Беллэром и Филлипом Рогэвэем в рамках европейского проекта 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×Msg→Tag и может быть вероятностным. Алгоритм верификации 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×Coins→Ctext , алгоритм расшифрования является отображением

SYM.dec(k,y):eKey ×Ctext→MsgUu{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×Coins→Ctext ,а расшифрования: ASYM.enc(sk,y):SK ×Ctext→MsgUu{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.

 

47)

Система открытого шифрования RSA, атаки на RSA.

В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA, названный так по начальным буквам фамилий ее изобретателей (Rivest, Shamir и Adleman) и представляющую собой криптосистему, стойкость которой основана на сложности решения задачи разложения числа на простые сомножители..

Под простым числом будем понимать такое число, которое делится только на единицу и на само себя. Взаимно простыми числами будем назы­вать такие числа, которые не имеют ни одного общего делителя, кроме единицы.

Под результатом операции i mod j будем считать остаток от целочис­ленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги:

• выберем два очень больших простых числа p и q;

• определим n как результат умножения p на q (n = p Ч q);

• выберем большое случайное число, которое назовем d (оно должно быть взаимно простым с m результатом умножения (р – 1) × (q – 1));

• определим такое число e, для которого является истинным следую­щее соотношение: (e Ч d) mod (m) =1 или e = (1 mod (m))/d.

Открытым ключом будут числа e и n, а секретным ключом – числа d и n.

Теперь, чтобы зашифровать данные по известному ключу {e, n}, необ­ходимо сделать следующее:

• разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа М(i) = 0, 1, …, n – 1;

• зашифровать текст, рассматриваемый как последовательность чисел М(i) по формуле С(i) = (М(i)^e) mod n.

Чтобы расшифровать данные, используя секретный ключ {d, n}, необ­ходимо выполнить следующие вычисления: М(i) = (С(i)^d) mod n. В резуль­тате получится множество чисел М(i), которые представляют собой исход­ный текст.

Криптостойкость алгоритма RSA основывается на проблеме факторизации больших простых чисел. Действительно, если злоумышленнику удастся разложить число n на простые множители p и q, то для него не составит труда вычислить j(n), а затем и определить секретный ключ пользователя. Однако нахождение секретного ключа RSA не эквивалентно проблеме факторизации. Это означает, что T(RSA)<=T(факторизации), где T(RSA) – трудоемкость определения секретного ключа RSA, а T(факторизации) – трудоемкость факторизации числа n. То есть, могут быть найдены эффективные алгоритмы определения секретного ключа алгоритма RSA, причем проблема факторизации при этом не будет разрешена.

Если сообщение невелико, то злоумышленник может попытаться подобрать открытый текст путем перебора всех возможных вариантов и шифрования их на открытом ключе абонента e до тех пор, пока не будет получен перехваченный шифртекст c.

Схема шифрования RSA несостоятельна при использовании абонентами общих модулей n. Допустим, что имеются 2 абонета A и В с открытыми ключами (e₁,n) и (e₂,n). Центр (например, общий сервер) желает послать обоим абонетам одно и то же сообщение m. Он получает m^e1=c₁(mod n) и m^e2=c₂(mod n) и посылает c₁ и c₂ абонентам А и В соответственно. Положим, что противник перехватывает эти сообщения. Затем, если (e₁,e₂)=1, то с помощью расширенного алгоритма Евклида можно найти такие k₁ и k₂, для которых e₁k₁+e₂k₂=1. И, соответственно, m^e1k1m^e2k2=m. Найдя такие k₁ и k₂ (это можно сделать, ведь открытые ключи противнику известны), противник вычислит собщение: (c₁)^k1(c₂)^k2 = m.

 

48)

Система электронной подписи Эль Гамаля (EGSA - ElGamal Signature Algorithm)

 

Очень часто бывает желательно, чтобы электронная цифровая подпись была разной, даже если дважды подписывается одно и то же сообщение. Для этого в процесс выработки ЭЦП необходимо внести элемент "случай­ности". Конкретный способ был предложен Эль-Гамалем аналогично тому, как это делается в системе шифрования, носящей его имя.

Выбирается большое простое число р и целое число g, являющееся примитивным элементом в Z_p. Эти числа публикуются. Затем выбирается секретное число х и вычисляется открытый ключ для проверки подписи y=g^x(mod p)

Далее для подписи сообщения М вычисляется его хэш-функция т = h(M). Выбирается случайное целое k:1<k<(p-1), взаимно простое с р–1, и вычисляется r=g^k(mod p). После этого с помощью расширенного алгоритма Евклида решается относительно s уравнение m=xr+ks(mod(p-1)). Подпись образует пара чисел (r,s). После выработ­ки подписи значение k уничтожается.

Получатель подписанного сообщения вычисляет хэш-функцию со­общения m=h(M) и проверяет выполнение равенства y^rr^s=g^xrg^ks=g^xr+ks=g^m(mod p). Корректность этого уравнения очевидна.

 

 

49)