Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Схема цифровой подписи

Определение. Схема цифровой подписи представляет собой конструкцию вида (K,{M_k},{A_k},S_k, V_k), где

• К — пространство ключей, элементы К имеют вид k=(e,d), e называется открытым ключом или открытой компонентой ключа (public key), d называется закрытым ключом или закрытой компонентой ключа (secret key);

• {M_k}_k_K — пространства сообщений; [A_k}_k_K — пространства подписей;

• функция построения подписи S_k:M_k A_k эффективно строится по закрытому ключу d;

• функция проверки подписи V_k :M_k A_k  {0,1} такая, что V_k(m,s)=1 в том и только том случае, если s=S_k(m), эффективно строится по открытому ключу е;

• не существует эффективного способа найти без знания закрытого ключа значение s для заданного т так, чтобы V_k(m,s)=l.

Схемой цифровой подписи удобно пользоваться, если для любых ключей k₁,k₂ K выполняется M_k1 =M_k2 и A_k1 =A_k2 .

Последнее требование к цифровой подписи может быть усилено, а именно: требуется невозможность найти хотя бы одну пару (m,s) такую, что V _k (т, s) =1 («экзистенциальная подделка» ).

Цифровая подпись позволяет участнику А передать участнику В сообщение в виде (m,S_A(m)). Тогда получатель может быть уверен, что сообщение отправлено именно владельцем закрытого ключа, и даже доказать это в суде.

Если цифровая подпись используется совместно с шифрованием, следует передавать сообщение в виде E_B(m,S_A(m)), а не (E_B(m),S_A(E_B(m))). Иначе не удается хранить расшифрованные сообщения вместе с подписями. Кроме того, в этом случае от используемой криптосистемы требуется стойкость к атакам с известным сообщением. В противном случае, если по заданной шифрограмме с и заданному сообщению т можно подобрать ключ k такой, что Е_k(m)=с, злоумышленник С может перехватить подпись s = D_A(E_B(m)), для любого сообщения т' подобрать ключ k такой, что E_k(m ')=E_B(m), зарегистрировать этот ключ в качестве своего и утверждать, что А послал ему сообщение с

s=D_A(E_k (m')). Для построения цифровых подписей можно использовать криптосистему с открытым ключом, если функция шифрования E_k отображает пространство сообщений M_k на пространство шифрограмм C_k. В данном случае для m C_k положим

Тогда получатель В может взять произвольное значение с и утверждать, что А подписал Е_А(с). Обычно в качестве подписи используют S_k(m)=D_k(h(m)), где h— криптографически стойкая хэш-функция. При этом к функции h применяются обычные требования, что позволяет, во-первых, избавиться от только что описанной атаки со стороны В, а во-вторых, подписывать сообщения, более длинные, чем возможный аргумент функции D_k..

Если длина результата хэш-функции меньше длины аргумента функции D_k, стандарт PKCS#1 рекомендует помещать h (т) в младшие байты аргумента, а в старшие — значение 0001FF...FF00₁₆. Альтернативно можно вычислять

Определение. Схема цифровой подписи (K,S,V) называется стойкой, если для любого вероятностного алгоритма F, использующего оракул для построения правильных подписей и выдающего в качестве результата пару (m,s) такую, что m не было аргументом оракула, для
любого многочлена q, для достаточно больших n

,

где (e,d)=K(1ⁿ) и (m,s)=F^B —случайные величины, В — любой алгоритм, дающий по сообщению т правильную подпись, V(e, m, B(m))= l. [1]

Вопрос 6

Криптосистемы с открытым ключом

Определение. Криптосистемой с открытым ключом, или асимметричной, называется конструкция вида (K,{M_k},{C_k},E_k,D_k), где

• К — пространство ключей, элементы К имеют вид k=(e,d), e называется открытым ключом или открытой компонентой ключа (public key), d называется закрытым ключом или закрытой компонентой ключа (secret key);

• {M_k}_k_K— пространства сообщений; [C_k}_k_K— пространства шифрограмм;

• взаимно однозначная функция шифрования E_k:M_kC_k эффективно строится по открытому ключу е и является односторонней с ловушкой d;

• функция дешифрования D_k:C_kM_k эффективно строится по закрытому ключу d;

• для любого тM_k справедливо равенство D_k(E_k(m))=m.

Хорошо, если для любых k_1,k₂K выполняется M_k1 =M_k2 C_k1 =C_k2 .

Также для сокращения записи будут использоваться следующие обозначения:

k(m) = E_k(m) — шифрование открытой компонентой ключа k;

k ^-1(c) = D_k(c) —дешифрование закрытой компонентой ключа k.

Вопрос 7

Факторизация

Для пары простых чисел (p,q) положим f(p,q)=pq. Тогда в качестве трудновычислимой функции рассматривается обратная функция f^-1(n) — факторизация.

Наилучший из известных алгоритмов разложения числа общего вида на множители называется general number field sieve и имеет асимптотическую оценку времени работы:

Последний на момент написания данной работы рекорд— в 1996 г. разложено на множители число, состоящее из 130 десятичных цифр.

Если простые сомножители имеют специальный вид, известны более эффективные алгоритмы факторизации:

• если р-1 «гладкое», т. е. имеет только малые простые делители, может применяться алгоритм Полларда;

• если р+1 «гладкое», т. е. имеет только малые простые делители, может применяться алгоритм "р+1".

Некоторое время назад в литературе рекомендовалось при построении криптосистем на основе факторизации выбирать в качестве простых сомножителей р и q сильные простые числа (strongprimes), т, е. такие, что р±1 и q±1 имеют большие простые делители. Иногда от этих делителей требуют наличия того же свойства. Однако с появлением алгоритма факторизации с использованием эллиптических кривых, класс чисел, допускающих быструю факторизацию, расширился и простые критерии проверки принадлежности данному классу утратили свою значимость. Поэтому, единственным разумным критерием может служить размер простых множителей, поскольку с увеличением размера уменьшается вероятность выбрать число специального вида. В 1995 г. корпорация RSA Data Security рекомендовала выбирать размер п равным 1024 или 2048 битам.

Вопрос 8

Дискретный логарифм

Пусть G— некоторая циклическая конечная группа. Для aG, xN положим g_a(x)=a^x. Тогда трудновычислимой считается обратная функция g_a^-1 — дискретный логарифм. Обычно в качестве элемента а берется образующий элемент группы G. При этом дискретный логарифм можно вычислять для любого элемента группы и все возможные значения показателя х образуют группу Z_|G| с операцией сложения, где | G | — порядок группы. Дискретный логарифм в общем случае трудно вычислить во всех группах, перечисленных в п. 3.1. Наилучший из известных алгоритмов вычисления дискретного логарифма в произвольной абелевой группе G имеет асимптотическую оценку времени исполнения O(q^1/'²), где q — наибольший простой делитель порядка группы | G |. Следовательно, для того чтобы дискретный логарифм в Z_p^* было трудно вычислить, р должно быть равно qt+1, где q — большое простое число.

Наилучший из известных на сегодняшний день алгоритмов вычисления дискретного логарифма в Z_p^* называется general number field sieve, основывается он на тех же принципах, что одноименный алгоритм факторизации, и имеет аналогичную асимптотическую оценку времени работы:

. [1]

Вычисление дискретного логарифма

Определение. Пусть G = < G; •, 1 > - конечная группа, а и b -элементы группы G; r = ordb. Натуральное число l называют дискретным логарифмом элемента а при основании b, если

(1.1)

Замечания.

а) В качестве группы G избираем мультипликативную группу из ненулевых элементов конечного поля F_r

б) Если q = р - простое число и b - первообразный корень по модулю р, то число l, определяемое условием (1.1), называют индексом числа а при основании b по модулю р.

в) Вместо термина "дискретный логарифм элемента а при основании b" употребляют также термин " индекс элемента а при основании b".

Обозначение. ind_ba - дискретный логарифм элемента а при основании b. (Группа G обычно подразумевается из контекста.)

Задача определения дискретного логарифма элемента конечной группы может быть легко решена, если порядок группы не слишком велик и для этой группы составлена таблица индексов. При отыскании логарифма положительного действительного числа, если нет таблицы логарифмов или она недоступна, можно воспользоваться методом последовательного приближения. Он состоит в следующем. На каждом шаге применения этого метода интервал границ значения арифметического логарифма сужают вдвое. Так продолжая, легко определить значение этого логарифма с любой заранее объявленной точностью. Успех применения этого метода основан на использовании свойств неравенств. Ничего подобного нет в конечном поле. Точнее говоря, в конечном поле нельзя построить метод вычисления дискретного логарифма, подобный методу последовательного приближения. В самом деле, в конечном поле нельзя определить антисимметричное, транзитивное, связное бинарное отношение, согласованное с какой-нибудь операцией.

Алгоритм перебора - метод, который хотя бы теоретически может всегда привести к успеху. Он состоит в следующем. Пусть b -примитивный элемент данного конечного поля и a - другой какой-нибудь элемент того же поля. Чтобы найти ind_ba, начиная, например, с п = 0, сравниваем элемент а с элементом bⁿ, если a = bⁿ, то ind_ba = п, в противном случае находим b^п+1 = bⁿ • b и опять сравниваем элемент а с элементом b^п+1 и т.д. Если число элементов поля 2¹⁰⁰ или больше, то количество операций (умножений), необходимое для вычисления дискретною логарифма произвольного элемента конечного поля в приемлемое время, чрезвычайно велико и находится за пределами возможностей современных вычислительных машин.

Алгоритм согласования

Теорема 1. Пусть t, r - натуральные числа, r² t . Для любого целого l можно указать целые числа х и у такие, что

Характеристики

Список файлов ответов (шпаргалок)