Безопасность программного обеспечения компьютерных систем
       

Краткое описание криптографических средств контроля целостности и достоверности программ


Основные положения криптологии и базовые криптографические понятия

Термин "криптология" происходит от двух греческих слов: "крипто", что означает "тайный" и "логос", т.е. - учение.

Криптология как наука, состоит из двух тесно теоретически и практически связанных дисциплин: криптографии и криптоанализа. Криптография - наука о способах преобразования (шифрования) информации с целью ее защиты от незаконных пользователей. Криптоанализ - наука (и практика ее применения) о методах и способах вскрытия шифров. Криптография и криптоанализ очевидным образом связаны друг с другом, так как не бывает хороших криптографов, не владеющих методами криптоанализа, и наоборот - хороший криптоаналитик должен быть знаком со всеми известными способами построения шифров. Ниже даются базовые понятия и определения криптологии, в т.ч. используемые и в настоящем разделе.

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

Шифрование - процесс применения шифра к защищаемой информации, т.е. преобразование информации в шифрованное сообщение с помощью определенных правил, содержащихся в шифре.

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

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

Под ключом в криптографии понимают сменный элемент шифра, который применен для шифрования конкретного открытого текста (сообщения).

В криптографии обычно общепринято следующее допущение.


Криптоаналитик (противник) почти всегда имеет полный шифртекст. Помимо этого в криптографии принято правило Керкхоффа, которое гласит, что "стойкость шифра должна определяться только секретностью его ключа".

В этом случае задача противника сводится к попытке раскрытия шифра (попытке осуществления атаки) на основе шифртекста. Если же противник имеет к тому же некоторые отрывки открытого текста и соответствующие им элементы шифртекста, тогда он пытается осуществлять атаку на основе открытого текста. Атака на основе выбранного открытого текста заключается в том, что противник, используя свой открытый текст, получает правильный шифртекст (например, используя "вслепую" некоторую шифрмашину) и пытается в этом случае вскрыть шифр. Попытку раскрытия шифра можно осуществить, если противник подставляет свой ложный шифртекст и при дешифровании получает необходимый для раскрытия шифра открытый текст. Такой способ раскрытия называется атакой на основе выбранного шифртекста.

Теоретически существует абсолютно стойкий шифр, но единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования (или так называемый "одноразовый блокнот"), в которой открытый текст "объединяется" с полностью случайным ключом такой же длины. Этот результат был доказан К. Шенноном с помощью разработанного им теоретико-информационного метода исследования шифров.

Для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования:





  • полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства);


    • равенство длины ключа и длины открытого текста;

    однократность использования ключа.


В то же время, именно эти условия и делают абсолютно стойкий шифр очень ресурсозатратным и непрактичным. Прежде чем пользоваться таким шифром, необходимо обеспечить всех абонентов достаточным запасом случайных ключей и исключить возможность их повторного применения.



А это сделать необычайно трудно и дорого. В силу данных причин абсолютно стойкие шифры применяются только в сетях связи с небольшим объемом передаваемой информации, обычно это сети для передачи особо важной государственной информации.

В 1976 г. опубликовав свою работу "Новые направления в криптографии", американские ученые У. Диффи и М. Хеллман выдвинули следующую удивительную гипотезу: "Возможно построение практически стойких криптосистем, вообще не требующих передачи секретного ключа". Такие криптосистемы, получившие название криптосистем с открытым ключом, основываются на введении понятий "односторонней функции" и "односторонней функции с секретом". Понятие односторонней функции было введено в подразделе 2.4

Вопрос о существовании односторонней функции с секретом является столь же гипотетическим, что и вопрос о существовании односторонней функции. Для практических целей было построено несколько функций, которые могут оказаться односторонними, а это означает, что задача инвертирования эквивалентна некоторой давно изучаемой трудной математической задаче (см., например, ).

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

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

Далее рассмотрим базовые криптографические методы, широко применяющиеся в современных системах обеспечения безопасности информации.

Краткое описание основных криптографических методов защиты данных



Симметричный шифр ГОСТ 28147-89

Пусть L и R - последовательности битов, LR означает их конкатенацию. Под обозначением

A[+]B=AB < 232

A[+]B=AB

Символом {+} обозначается операция сложения по модуль 232-1 двух 32-разрядных чисел. Правила суммирования чисел следующие:

A{+}B=AB < 232-1

A{+}B=AB

Во всех режимах работы алгоритма используется ключ длиной 256 битов, который представляется в виде восьми 32-разрадных чисел X(i).Если обозначить ключ через W, то

W=X(7)X(6)X(5)X(4)X(3)X(2)X(1)X(0).

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

Описание режима простой замены. Код программы T разбивается на блоки по 64 бита в каждом, которые обозначаются T(j). Очередная последовательность битов T(j) разбивается на две последовательности B(0) (левые или старшие биты) и A(0) (правые или младшие биты), каждая из которых содержит 32 бита. Затем выполняется итеративный процесс шифрования, который описывается следующими формулами:

при i=1,2,...,24; j=i-1(mod 8) A(i)=f(A(i-1)[+]X(j)(+)B(i-1)); B(i)-A(i-1); при i=25,26,...,31; j=32-i A(i)=f(A(i-1)[+]X(j)(+)B(i-1)); B(i)-A(i-1); при i=32 A(32)=A(31); B(32)=f(A(31)[+]X(0)(+)B(31)),

где i обозначает номер итерации (i=1,2,...,32). Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 232 числа A(i), полученного на предыдущем шаге итерации, в числа X(j) ключа (размерность каждого из этих чисел 32 знакам).

Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой K. Блок подстановки K состоит из восьми узлов замены K(1)...K(8) с памятью 64 бита каждый.



Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4- разрядных векторов, каждый из которых преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0,...,15.

Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-разрядные выходные векторы последовательно объединяются в 32-разрядный вектор. Таблицы блока подстановки блока подстановки K содержат редко изменяемые ключевые элементы, общие для некоторой компьютерной системы.

Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки K. 64-разрядный блок зашифрованных данных Тш представляется в виде:

Тш=A(32)B(32).

Остальные блоки кода программы в режиме простой замены шифруются аналогично.

Режим генерации имитовставки. Для получения имитовставки код программы представляется в виде 64-разрядных блоков T(i), =1,2,..,m. Где m определяет объем кода программы. Первый блок кода программы T(i) подвергается преобразованию, соответствующему первым 16 циклам алгоритма шифрования в режиме простой замены, причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.

Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком открытых данных T(2). Результат суммирования снова подвергается преобразованию, соответствующему 16 циклам алгоритма шифрования в режиме простой замены. Полученное 64-разрядной число суммируется по модулю 2 с третьим блоком данных T(3) и т.д. Последний блок T(m), при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего шифруется в режиме простой замены по первым 16 циклам алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р битов. Данный отрезок и является имитовставкой Ир, полученной для кода программы T.

Открытый ключевой обмен Диффи-Хеллмана и криптосистемы с открытым ключом



Основная задача ключевого обмена Диффи-Хеллмана заключается в следующем: " Каким образом можно установить секретный ключ между абонентами А и В по открытому каналу связи а затем использовать его для шифрованной передачи сообщений?" Для этих целей, пусть абонент A выбирает какую-нибудь функцию fk с секретом k. Он публикует в открытом сертифицированном справочнике описание функции fk в качестве своего алгоритма шифрования. Однако, значение секрета k он никому не сообщает, т.е. держит его в тайне от других.

Если абонент B хочет послать А защищаемую информацию xA. Поскольку A для своего секрета k умеет инвертировать fk, то он вычисляет x по полученному y. Так как никто другой не знает k и поэтому в силу свойств функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению y вычислить защищаемую информацию x.

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

Электронная цифровая подпись

Основные определения, обозначения и алгоритмы. Для реализации схем электронной цифровой подписи (или просто цифровой подписи) требуются три следующих эффективно функционирующих алгоритма:



  • Ak - алгоритм генерации секретного и открытого ключей для подписи кода программы, а также проверки подписи, - s и p соответственно;


    • As - алгоритм генерации (проставления) подписи с использованием секретного ключа s;

    Ap - алгоритм проверки (верификации) подписи с использованием открытого ключа p.




Алгоритмы должны быть разработаны так, чтобы выполнялось основное принципиальное свойство, - свойство невозможности получения нарушителем (противником) алгоритма As из алгоритма Ap.

Таким образом, если Ak - алгоритм генерации ключей, тогда определим значения (s,p)=Ak(?,?) как указанные выше сгенерированные ключи, где ? - некоторый параметр безопасности (как правило, длина ключей), а ? - параметр, характеризующий случайный характер работы алгоритма Ak при каждом его вызове.

Ключ s хранится в секрете, а открытый ключ p делается общедоступным. Это делается, как правило, путем помещения открытых ключей пользователей в открытый сертифицированный справочник. Сертификация открытых ключей справочника выполняется некоторым дополнительным надежным элементом, которому все пользователи системы доверяют обработку этих ключей. Обычно этот элемент называют Центром обеспечения безопасности или Центром доверия.

Непосредственно процесс подписи осуществляется посредством алгоритма As. В этом случае значение c=As(m) - есть подпись кода программы m, полученная при помощи алгоритма As и ключа s.

Процесс верификации выполняется следующим образом. Пусть m* и c* - код программы и подпись для этого кода соответственно, Ap - алгоритм верификации. Тогда, выбрав из справочника общедоступный открытый ключ p, можно выполнить алгоритм верификации: b=Ap(m*,c*), где предикат b

Примеры схем электронной цифровой подписи. К наиболее известным схемам цифровой подписи с прикладной точки зрения относятся схемы RSA, схемы Рабина-Уильямса, Эль-Гамаля, Шнорра и Фиата-Шамира , а также схема электронной цифровой подписи отечественного стандарта ГОСТ Р 34.10-94 .

Рассмотрим несколько подробнее четыре наиболее известные схемы цифровой подписи:



Подпись RSA: Вход: Числа n, p, q, где p и q - большие l - разрядные простые числа, n=pq. Открытый ключ p=(e,n), секретный ключ s=d, такой, что ed

Генерация ключей:(d,(e,n))=Ak(l,b). Подпись:As: 1.md(mod n)

кода программы m. Верификация:Ap: 1.[c*]e(mod n)

Подпись Эль-Гамаля: Вход: Числа p и g, где p - простое l - разрядное число, а g - первообразный корень по модулю p. Секретный ключ s=d, открытый ключ p=e, такой, что e

Генерация ключей:(d,(e,g,p))=Ak(l,b).

Подпись: As: 1.rRZp-1;

2.находится такое c, что

m

где (c,r) - подпись кода m.

Верификация:Ap: 1.если gm*=errc*(mod p),
то подпись верна.

Подпись Фиата - Шамира: Вход: Числа n, p, и q, где p и q большие l - разрядные простые числа, открытый ключ p есть вектор (v1,v2,...,vk), где vj - квадратичные вычеты по модулю n, j=

Подпись: As: 1.xi RZn;

2.вычисляется значение

a=f(m,x1,x2,...,xt);

3.выбирается первые kt битов числа a как
матрица

4.вычисляется:

где

Тогда (eij,yi) - подпись кода m.
Верификация:

2.если первые kt битов значения

функции f(m*,z1,z2,...,zt) равны e*ij,

подпись верна.
Подпись стандарта ГОСТ Р 34.10-94. Вход: Числа p, g и q где p - простое l -разрядное число, g - первообразный корень по модулю p, а q - большой простой делитель p-1. Пусть также gq1. Секретный ключ подписи x (1 < x < q) и открытый ключ y

Генерация ключей: (x,(g,p,q,y))=Ak(l,b).
Подпись: Ax: 1.rRZq.

2.s
Верификация: Ay: 1.v

2.u
<



/p>

Под стойкостью схемы цифровой подписи понимается стойкость в теоретико-сложностном смысле, то есть, как отсутствие эффективных алгоритмов ее подделки и (или) раскрытия . По-видимому, до сих пор основной является следующая классификация:



  • атака с открытым ключом, когда противник знает только открытый ключ схемы;


    • атака на основе известного открытого текста (известного кода программы), когда противник получает подписи для некоторого (ограниченного) количества известных ему кодов (при этом противник никак не может повлиять на выбор этих кодов);

    атака на основе выбранного открытого текста, когда противник может получить подписи для некоторого ограниченного количества выбранных им кодов программы (предполагается, что коды выбираются независимо от открытого ключа, например, до того как открытый ключ станет известен);

    направленная атака на основе выбранного открытого текста (то же, что предыдущая, но противник, выбирая код программы, уже знает открытый ключ);

    адаптивная атака на основе выбранного открытого текста, когда противник выбирает коды программы последовательно, зная открытый ключ и зная на каждом шаге подписи для всех ранее выбранных кодов.


Атаки перечислены таким образом, что каждая последующая сильнее предыдущей.

Угрозами для схем цифровой подписи являются раскрытие схемы или подделка подписи. Определяются следующие типы угроз:



  • полного раскрытия, когда противник в состоянии вычислить секретный ключ подписи;


    • универсальной подделки, когда противник находит алгоритм, функционально эквивалентный алгоритму вычисления подписи;

    селективной подделки, когда осуществляется подделка подписи для кода программы, выбранного противником априори;

    экзистенциональной подделки, когда осуществляется подделка подписи хотя бы для одного кода программы (при этом противник не контролирует выбор этого кода, которое может быть вообще случайным или бессмысленным).


Угрозы перечислены в порядке ослабления. Стойкость схемы электронной подписи определяется относительно пары (тип атаки, угроза).



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

Разновидности схем подписи электронных сообщений. Для обеспечения целостности и достоверности информации при ее передаче и хранении, а также для проведения аутентификации абонентов системы и решения других задач защиты существует достаточно много всевозможных разновидностей схем подписи . Без подробного описания ниже приводится одна из разновидностей схем подписи, которая, как правило, использует рассмотренный выше математический аппарат и может использоваться для защиты программ.

Схема подписи с верификацией по запросу. В работах Д. Шаума (см., например, [,]) впервые была предложена схема подписи с верификацией по запросу, в которой абонент V не может осуществить верификацию подписи без участия абонента S. Такие схемы могут эффективно использоваться в том случае, когда фирма - изготовитель поставляет потребителю некоторый информационный продукт (например, программное обеспечение) с проставленной на нем подписью указанного вида . Однако проверить эту подпись, которая гарантирует подлинность программы или отсутствие ее модификаций, можно только уплатив за нее. После факта оплаты фирма - изготовитель дает разрешение на верификацию корректности полученных программ.

Схема состоит из трех этапов (протоколов), к которым относятся непосредственно этап генерации подписи, этап верификации подписи с обязательным участием подписывающего (протокол верификации) и этап оспаривания, если подпись или целостность подписанных сообщений подверглась сомнению (отвергающий протокол).

I. Генерация подписи. Пусть каждый пользователь S имеет один открытый ключ P и два секретных ключа S1 и S2. Ключ S1 всегда остается в секрете, - он необходим для генерации подписи.



Ключ S2 может быть открыт для того, чтобы конвертировать схему подписи с верификацией по запросу в обычную схему электронной цифровой подписи.

Вместе с обозначениями секретного и открытого ключей xRZ*p (взятых из отечественного стандарта на электронную цифровую подпись) введем также обозначения S1=x и S2=u, ugu(mod p). Открытый ключ P публикуется в открытом сертифицированном справочнике.

Подпись кода m вычисляется следующим образом. Выбирается kgk(mod p). Затем вычисляется sgswy-rw , где w

Проверка подписи (с участием подписывающего) осуществляется посредством следующего интерактивного протокола.

II. Протокол верификации. Абонент вычисляет ?logr(p)?. Для этого:

  • Абонент V выбирает a,bragb(mod p) и посылает ? абоненту S.
  • Абонент S выбирает t?g1(mod p), h2V.
  • Абонент V высылает параметры a и b.
  • Если ?
  • Абонент V проверяет выполнение равенств h1?awb+1(mod p) .

    Если проверка завершена успешно, то подпись принимается как корректная.

    III. Отвергающий протокол. В отвергающем протоколе S доказывает, что logg(p)w

  • Абонент V выбирает d,e1, ?ge(mod p), bre(mod p) , bS значения a, b, d.
  • Абонент S проверяет соотношение au(mod p)RZq, вычисляет cV значение c.
  • Абонент V посылает абоненту S значение e.
  • Абонент S проверяет, что выполняются соотношения из следующих двух их пар: awe(mod p) и a?e(mod p).



    Если да, то посылает V значение R. Иначе останавливается.
  • Абонент V проверяет, что d?gR

    Если во всех l циклах проверка в п. 5 выполнена успешно, то абонент V принимает доказательства.

    Таблица 3.1. Протокол верификации является интерактивным протоколом доказательств с абсолютно нулевым разглашением.

    Доказательство. Требуется доказать, что вышеприведенный протокол удовлетворяет трем свойствам: полноты, корректности и нулевого разглашения [,].

    Полнота означает, что если оба участника (V и S) следуют протоколу и (r,s) - корректная подпись для сообщения m, то V примет доказательство с вероятностью близкой к 1. Из описания протокола верификации очевидно, что абонент S всегда может надлежащим образом ответить на запросы абонента V, то есть доказательство будет принято с вероятностью 1.

    Корректность означает, что если V действует согласно протоколу, то какие действия не предпринимал бы S, он может обмануть V лишь с пренебрежимо малой вероятностью. Здесь под обманом понимается попытка S доказать, что logg(p)w

    Предположим, что logg(p)w



    где a1

    logg(p)rlogw(p)?.

    Отсюда, очевидно, следует, что logg(p)wlogg(p)r



    что противоречит предположению. Следовательно, какие бы h1, h2, t1 и t2 не выбрал S, проверка, которую проводит V, может быть выполнена только для одного значения a. Отсюда вероятность обмана не превосходит 1/q. Отметим, что протокол верификации является безусловно стойким для абонента V, то есть доказательство корректности не зависит ни от каких предположений о вычислительной мощности доказывающего (S).

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



    Для доказательства нулевого разглашения необходимо для любого возможного проверяющего V* построить моделирующую машину MV , которая является вероятностной машиной Тьюринга, работает за полиномиальное в среднем время и создает на выходе (без участия S) такое же распределение случайных величин, которое возникает у V* в результате выполнения протокола. В нашем случае, случайные величины, которые "видит" V*, - это h1, h2, и t. Необходимо доказать, что протокол верификации является доказательством с абсолютно нулевым разглашением, то есть моделирующая машина создает распределение случайных величин (h1,h2,t), которое в точности совпадает с их распределением, возникающим при выполнении протокола. Моделирующая машина MV использует в своей работе V* в качестве "черного ящика".

    Моделирующая машина

  • Запоминает состояние машины V*, то есть содержимое всех ее лент, внутреннее состояние и позиции головок на лентах. Затем получает от V* значение ? и после этого снова запоминает состояние машины V*.
  • Выбирает ?g?(modp) и h`2`
  • Получает от V* значения a и b. Если ?
  • Машина MV` "отматывает" V* на состояние, которое было запомнено в конце шага 1. Выбирает tragb+1(modp) и h2
  • Машина MV` передает V* h1, h2 и получает ответ (a`,b`). Возможны два варианта:
      5.1. a=a` , b=b` . В этом случае моделирование закончено и MV` записывает на выходную ленту тройку (h1,h2,t) и останавливается.

      5.2. ab` . Отсюда следует, что ?ra`gb`(modp) . Предположим, что ba`. Следовательно, MV` может вычислить r


  • Машина MV` "отматывает" V* на состояние, которое было за-полнено в начале шага 1. Получает от V* значение ?.
  • Выбирает ?g?(modp) и h2
  • Получает от V* значения a и b. Если ?



    В противном случае вычисляет t=[?-al-b](mod q), выдает (h1,h2,t) на выходную ленту и останавливается.

    К пп. 7 и 8 необходимо сделать следующее пояснение. Поскольку logg(p)wlogg(p)r. Отсюда

    h2wb+1wal

    Из описания моделирующей машины MV` очевидно, что она работает за полиномиальное время. Величины (h1,h2,t) на шаге 5.1 выбираются в точности как в протоколе и поэтому имеют такое же распределение вероятностей. Кроме того, значения (h1,h2), выбираемые на шаге 7, имеют такое же распределение, как и в протоколе. Чтобы показать что и t имеет одинаковое распределение, достаточно заметить, что машина V* не может по h1 и h2 определить, с кем она имеет дело - с S или MV`.Поэтому, даже если бы V* могла каким-либо "хитрым" образом строить a и b с учетом (h1,h2), распределение вероятностей величин a и b в обоих случаях одинаковы. Но значение t определяется однозначно четверкой величин a, b, h1, h2, при условии выполнения проверки на шаге 5 протокола.

    Таблица 3.2. Отвергающий протокол является протоколом доказательства с абсолютно нулевым разглашением.

    Доказательство. Полнота протокола очевидна. Если абоненты S и V следуют протоколу, тогда абонент V всегда примет доказательства абонента S.

    Для доказательства корректности прежде всего заметим, что если logg(p)w

    Если же S может сгенерировать c таким образом, что с вероятностью, которая не является пренебрежимо малой, он может на шаге 4 "открыть" оба значения ?, то есть найти R1 и R2 такие, что , то алгоритм, который использует S для этой цели, можно использовать для вычисления дискретных логарифмов: loggd=R2-R1.



    Так как при случайном выборе значения d логарифм loggd может быть вычислен с вероятностью, которая не является пренебрежимо малой, это противоречит гипотезе о трудности вычисления дискретных логарифмов.

    Далее доказывается, что отвергающий протокол является доказательством с абсолютно нулевым разглашением. Для этого необходимо для всякого возможного проверяющего V* построить моделирующую машину MV`, которая создает на выходе (без участия S) такое же распределение случайных величин (в данном случае, c и R), какое возникает у V* в результате выполнения протокола.

    Моделирующая машина

    Следующие шаги выполняются в цикле l раз.

  • Машина MV` запоминает состояние машины V*.
  • Получает от V* значения a, b и d.
  • Выбирает ?RZq и вычисляет cV* значение c.
  • Получает от V* значение e.
  • Проверяет, было ли "угадано" на шаге 2 значение ? (это значение было "угадано", если awe(modp) и ?=0, либо ??e(modp) и ?=1). Если да, то записывает на входную ленту значение (c,R). В противном случае "отматывает" V* на то состояние, которое было запомнено на шаге 1, и переходит на шаг 2.

    Легко видеть, что распределения случайных величин (c,R), возникающее в процессе выполнения протокола и создаваемые моделирующей машиной MV`, одинаковы, поскольку R в обоих случаях - чисто случайная величина, а величина c записывается на выходную ленту машины MV` только тогда, когда ? совпало с ?.

    Поскольку значение ? выбирается машиной MV` на шаге 3 случайным образом, а c не дает V* никакой информации о значении ?, на каждой итерации ? будет угадано с вероятностью 1/2. Отсюда следует, что машина MV` работает за полиномиальное в среднем время.

    В работе показано, как строить схемы конвертируемой и селективно конвертируемой подписи с верификацией по запросу на основе отечественного стандарта ГОСТ Р 34.10-94. В таких схемах открытие определенного секретного параметра некоторой схемы подписи с верификацией по запросу позволяет трансформировать последнюю в обычную схему цифровой подписи.



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

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

    В случае возникновения проблемы по поводу корректности подписи основные действия участников процесса должны сводиться к следующему:

  • Абонент V предъявляет арбитру сообщение и его подпись.
  • Арбитр требует предъявить секретный ключ подписи абоненту S. Если абонент S отказывается, тогда арбитр дает заключение, что подпись подлинная. (То есть, в данном случае возможное нарушение сводится к тому, что абонент отказывается признать представленную подпись своей).
  • Арбитр выбирает из открытого сертифицированного справочника открытый ключ абонента S и проверяет его соответствие секретному ключу подписи. При обнаружения несоответствия (например, по вине службы ведения такого справочника) арбитр признает подпись, предъявленную абонентом V, подлинной.
  • Арбитр проверяет корректность подписи при помощи проверочных соотношений, используемых как при генерации, так и при верификации данной подписи.

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



    Хэш-функции

    Основные определения, обозначения и алгоритмы. Под термином "хэш-функция" понимается функция, отображающая электронные данные произвольной длины (иногда длина ограничена, но достаточно большим числом), в значения фиксированной длины. Последние часто называют хэш-кодами. Таким образом, у всякой хэш-функции h имеется большое количество коллизий, то есть пар значений x и y таких, что h(x)=h(y). Основное требование, предъявляемое криптографическими приложениями к хэш-функциям, состоит в отсутствии эффективных алгоритмов поиска коллизий. Хэш-функция, обладающая таким свойством, называется хэш-функцией, свободной от коллизий. Кроме того, хэш-функция должна быть односторонней, то есть функцией, по значению которой вычислительно трудно найти ее аргумент и, в то же время, функцией, для аргумента которой, вычислительно трудно найти другой аргумент, который давал бы то же самое значение функции.

    Таким образом, хэш-функции вместе со схемами электронной цифровой подписи предназначены для решения задач обеспечения целостности и достоверности электронных данных. В прикладных компьютерных системах требуется применение так называемых криптографически стойких хэш-функций. Под термином "криптографически стойкая хэш-функция" понимается функция h, которая является односторонней и свободной от коллизий.

    Введем следующие обозначения. Хэш-функция h обозначается как h(?) и h(?,?) для одного и двух аргументов соответственно. Хэш-код функции h обозначается как H. При этом H0=I обозначает начальное значение (вектор инициализации) хэш-функции. Под обозначением

    Для лучшего понимания дальнейшего материала приведем небольшой пример построения хэш-функции. Предположим нам необходимо получить хэш-код для некоторой программы M. В качестве шифрующего преобразования в хэш-функции будут использоваться процедуры шифра DES с ключом k.



    Тогда, чтобы получить хэш-код H программы M при помощи хэш-функции h необходимо выполнить следующую итеративную операцию:



    где код программы M разбит на n 64-битных блока. Хэш-кодом данной хэш-функции является значение H=h(M,I)=Hn.

    Стойкость (безопасность) хэш-функций. Один из основных методов криптоанализа хэш-функций заключается в проведении криптоаналитиком (противником) атаки, основанной на "парадоксе дня рождения", основные идеи которой, излагаются ниже. Для понимания сущности предлагаемого метода криптоанализа достаточно знать элементарную теорию вероятностей.

    Атака, основанная на "парадоксе дня рождения", заключается в следующем. Пусть a

    Практически это означает, что в случайно подобранной группе из 24 человек вероятность наличия двух лиц с одним и тем же днем рождения составляет значение примерно 1/2. Этот старый и хорошо изученный парадокс и положен в основу криптоанализа хэш-функций.

    Например, для криптоанализа хэш-функций, основанных на использовании криптоалгоритма DES, указанная атака может быть проведена следующим образом. Пусть n - мощность области хэш-кодов (для криптоалгоритма DES она равна 264). Предположим, что есть две программы m1 и m2. Первая программа достоверна, а для второй криптоаналитик пытается получить то же самое значение хэш-кода, выдав таким образом программу m1 за программу m2 (то есть криптоаналитик пытается получить коллизию). Для этого криптоаналитик подготавливает порядка

    К основным методам предотвращения данной атаки можно отнести: увеличение длины получаемых хэш-кодов (увеличение мощности области хэш-кодов) и выполнение требования итерированности шифрующего преобразования.



    Методы построения криптографически стойких хэш-функций. Практические методы построения хэш- функций можно условно разделить на три группы: методы построения хэш-функций на основе какого-либо алгоритма шифрования (пример, приведенный выше), методы построения хэш-функций на основе какой-либо известной вычислительно трудной математической задачи и методы построения хэш-функций "с нуля" .

    Рассмотрим примеры построения хэш-функций на основе алгоритмов шифрования. Наряду с примером, приведенным выше, покажем, как строить хэш-функции на основе наиболее известных блочных шифров ГОСТ 28147 - 89, DES и FEAL. В качестве шифрующего преобразования будут использоваться некоторые режимы шифров ГОСТ 28147-89, DES и FEAL с ключом k. Тогда, чтобы получить хэш-код H программы M при помощи хэш-функции h, необходимо выполнить следующую итеративную операцию (например, с использованием алгоритма ГОСТ 28147-89):



    Таким образом, хэш-кодом данной хэш-функции является значение H=h(M,I)=Hn. При этом используется режим выработки имитовставки ГОСТ 28147-89, а шифрующее преобразование 64-битных блоков заключается в выполнении 16 циклов алгоритма шифрования в режиме простой замены.

    Алгоритм ГОСТ 28147-89 в качестве базового используется в хэш-функции отечественного стандарта на функцию хэширования сообщений ГОСТ Р 34.11-94, являющегося основным практическим инструментом в компьютерных системах, требующих обеспечения достоверности и целостности электронных данных.

    Алгоритм DES (в режиме CFB) можно использовать в качестве базового, например, в следующей хэш-функции (с получением хэш-кода H=h(M,I)=Hn):



    Другие примеры хэш-функций на основе алгоритмов шифрования. N-хэш алгоритм разработан фирмой Nippon Telephone Telegraph в 1990 году. N-хэш алгоритм использует блоки длиной 128 битов, шифрующую функцию, аналогичную функции алгоритма шифрования FEAL, и вырабатывает блок хэш-кода длиной 128 битов. На вход пошаговой хэш-функции в качестве аргументов поступают очередной блок кода Mi длиной 128 битов и хэш-код Hi-1 предыдущего шага также размером 128 битов.



    При этом H0=I, а Hi=Ek(Mi,Hi-1)Hi-1. Хэш- кодом всего кода программы объявляется хэш-код, получаемый в результате преобразования последнего блока текста.

    Идея использовать алгоритм блочного шифрования, стойкость которого общеизвестна, для построения надежных схем хэширования выглядит естественной. Однако для некоторых таких хэш-функций возникает следующая проблема. Предлагаемые методы могут требовать задания некоторого ключа, на котором происходит шифрование. В дальнейшем этот ключ необходимо держать в секрете, ибо противник, зная этот ключ и значение хэш-кода, может выполнить процедуру в обратном направлении. Еще одной слабостью указанных выше схем хэширования является то, что размер хэш-кода совпадает с размером блока алгоритма шифрования. Чаще всего размер блока недостаточен для того, чтобы схема была стойкой против атаки на основе "парадокса дня рождения". Поэтому были предприняты попытки построения хэш-функций на базе блочного шифра с размером хэш-кода в k раз (как правило, k=2) большим, чем размер блока алгоритма шифрования.

    В качестве примера можно привести хэш-функции MDC2 и MDC4 фирмы IBM. Данные хэш-функции используют блочный шифр (в оригинале DES) для получения хэш-кода, длина которого в два раза больше длины блока шифра. Алгоритм MDC2 работает несколько быстрее, чем MDC4, но представляется несколько менее стойким.

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

    В качестве примера хэш-функций, построенных на основе вычислительно трудной математической задачи можно привести функцию из рекомендаций MKKTT X.509.

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



    Следует отметить, что задача разложения числа на простые множители эквивалентна следующей труднорешаемой математической задаче. Пусть n=pq произведение двух простых чисел p и q. В этом случае можно легко вычислить квадрат числа по модулю n: x2(mod n), однако вычислительно трудно извлечь квадратный корень по этому модулю.

    Таким образом, хэш-функцию МККТТ X.509 можно записать как:



    длина блока Mi представляется в октетах, каждый октет разбит пополам и к каждой половине спереди приписывается полуоктет, состоящий из двоичных единиц; n - произведение двух больших (512-битных) простых чисел p и q.

    По-видимому, наиболее эффективными на сегодняшний день с точки зрения программной реализации и условий применения оказываются хэш-функции построенные "с нуля".

    Алгоритм MD4 (Message Digest) был разработан Р. Ривестом [,]. Размер вырабатываемого хэш-кода - 128 битов. По заявлениям самого разработчика при создании алгоритма он стремился достичь следующих целей:

    После того, как алгоритм был впервые опубликован, несколько криптоаналитиков построили коллизии для последних двух из трех раундов, используемых в MD4. Несмотря на то, что ни один из предложенных методов построения коллизий не приводит к успеху для полного MD4, автор усилил алгоритм и предложил новую схему хэширования MD5.

    Алгоритм MD5 является доработанной версией алгоритма MD4. Аналогично MD4, в алгоритме MD5 размер хэш-кода равен 128 битам.

    После ряда начальных действий MD5 разбивает текст на блоки длиной 512 битов, которые, в свою очередь, делятся на 16 подблоков по 32 бита. Выходом алгоритма являются 4 блока по 32 бита, конкатенация которых образует 128-битовый хэш-код. В 1993 году Национальный институт стандартов и технологий (NIST) США совместно с Агентством национальной безопасности США выпустил "Стандарт стойкой хэш-функции" (Secure Hash Standard), частью которого является алгоритм SHA. Предложенная процедура вырабатывает хэш-код длиной 160 битов для произвольного текста длиной менее 264 битов.



    Разработчики считают, что для SHA невозможно предложить алгоритм, имеющий разумную трудоемкость, который строил бы два различных набора данных, дающих один и тот же хэш-код (то есть алгоритм, находящий коллизии). Алгоритм SHA основан на тех же самых принципах, которые использовал Р. Ривест при разработке MD4, более того, алгоритмическая структура SHA очень похожа на структуру MD4. Процедура дополнения хэшируемого текста до кратного 512 битам полностью совпадает с процедурой дополнения алгоритма MD5.

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



    • любой из известных алгоритмов построения коллизий не должен быть эффективнее метода, основанного на "парадоксе дня рождения";


      • алгоритм должен допускать эффективную программную реализацию на 32-разрядном процессоре;

      алгоритм не должен использовать сложных структур данных и подпрограмм;

      алгоритм должен быть оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.


    Криптографические протоколы

    Базовым объектом исследований в криптологии являются криптографические протоколы. Криптографические протоколы относится к сравнительно новому направлению в криптографии, которое в последнее время переживает бурное развитие. В то же время, они являются весьма нетривиальным объектом исследований. Даже их формализация на сегодняшний день выглядит весьма затруднительной. Тем не менее, неформально под протоколом будем понимать распределенный алгоритм, т.е. совокупность алгоритмов для каждого из участников вычислений, плюс спецификации форматов сообщений, пересылаемых между участниками, плюс спецификации синхронизации действий участников, плюс описание действий при возникновении сбоев .

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

    Приведенная выше схема подписи с верификацией по запросу, а также схемы, представленные в разделе 2.4. есть не что иное, как сложные двухсторонние или многосторонние протоколы, которые используют, в том числе и криптографические примитивы.


    Содержание раздела