Иванов Разрушаюсчие программные воздействия 2011

Приложение 1

КРИПТОСИСТЕМА ПАЙЕ

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

В данном приложении рассматриваются процедуры генерации ключа, зашифрования и расшифрования. Доказательство основных свойств и более подробное описание криптосистемы Пайе можно найти в первоисточнике (Paillier P. Public-key cryptosystems based on composite degree residue classes // Advances in Cryptology — Eurocrypt '99, Springer-Verlag, Lecture Notes in Computer Science No. 1592, 1999, p. 223-238).

Генерация ключа

1.Выбрать два простых числа p и q случайно и независимо друг от друга.

2.Вычислить n = p q и λ= НОД (p −1, q −1).

3.Выбрать случайное число g, g Zn2 .

4.Удостовериться в делимости степени g на n, проверив существование обратного числа μ= ( L ( gλ mod n2 ) )−1 mod n ,

где функция L (u)= (u −1) / n . Открытый ключ = {n, g}. Секретный ключ = {λ, μ}.

Зашифрование

3.Пусть m — исходное сообщение, m Zn .

4.Выбрать случайное число r, r Zn .

5. Вычислить криптограмму c = gm rn mod n2 .

311

Расшифрование

1.Пусть c — зашифрованное сообщение, c Zn2 .

2.Расшифровать исходное сообщение

m = L (cλ mod n2 ) μ mod n .

Данная криптосистема обладает рядом полезных гомоморфных свойств:

1) Аддитивный гомоморфизм

Произведение криптограмм равно криптограмме суммы:

D(E (m1,r1) E (m2 ,r2 )mod n2 )= m1 + m2 mod n .

Произведение криптограммы на агрегат сообщения равно криптограмме суммы:

D(E (m1 ,r1) g m2 mod n2 )= m1 + m2 mod n .

2) Мультипликативный гомоморфизм

Криптограмма в степени сообщения равна криптограмме произведения:

D(E (m1 ,r1 )m2 mod n2 )= m1m2 mod n ;

D(E (m2 ,r2 )m1 mod n2 )= m1m2 mod n .

В общем случае, криптограмма в степени k равна криптограмме произведения:

D(E (m, r)k mod n2 )= km mod n .

312

Приложение 2

ПРОБЛЕМА ϕ-СКРЫТИЯ

Криптографический протокол конфиденциального получения информации опирается на так называемую проблему ϕ-скрытия (phi-hiding). Впервые эта задача была представлена на конференции Eurocrypt ' 99. Было показано, что она вычислительно неразрешима наравне с задачами дискретного логарифмирования и факториза-

ции больших чисел (Cachin С., Micali S., Stadler M. Computationally private information retrieval with polylogarithmic communication // Advances in Cryptology — Eurocrypt '99, Springer-Verlag, Lecture Notes in Computer Science No. 1592, 1999, p. 402–414).

Пусть m – это результат произведения двух больших простых чисел p и q, а p0 и p1 – это b-битные простые числа, такие что только одно из них нацело делит ϕ(m). Проблема ϕ-скрытия формулируется таким образом: по заданным m, p0 и p1 определить, какое из чисел {p0, p1} делит ϕ(m) нацело. Говорят, что составное число m ϕ-скрывает p0, если ϕ(m) кратно p0.

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

Таблица П2.1

	Используемые множества
Множество	Элементы множества
PRIMES b	Простые числа размерностью b бит

313

			Продолжение табл. П2.1
	Ha		Произведения pq, где | p |= | q |= a
	H b (m)		b-битные простые числа, ϕ-скрытые m
		(m)	PRIMESb − H b (m)
	H b
	H b		Все m Ha , ϕ-скрывающие простое b-битное
	a		число

Гипотеза ϕ-скрытия:

e, f,g,h > 0 : k > h, 2ek – элементной логической цепи С после последовательного выполнения следующего шагов:

•выбрать случайное составное число m, m Hkkf ;

•сформировать случайное p0, p0 H k (m) ;

•сформировать случайное p1, p1 H k (m);

•получить случайный бит b;

1 1

вероятность того, что C (m, pb )= b , меньше 2 + 2gk .

314

Приложение 3

КРИПТОСИСТЕМА ЭЛЬ-ГАМАЛЯ

Криптосистема Эль-Гамаля – асимметричная криптографическая схема шифрования, предложенная Тахиром Эль-Гамалем в

1984 г.

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

Алгоритм генерации ключей

1.Породить мультипликативную циклическую группу G степени q с образующей g:

1.1.Выбрать простое число q – степень криптосистемы;

1.2.Сформировать случайное g, g < q.

2.Выбрать случайное x, x < q.

3.Вычислить h = gx mod q.

Открытый ключ = (h, g, q). Закрытый ключ = x.

Алгоритм зашифрования

1.Подготовить сообщение m, m < q.

2.Выбрать случайное y, y < q.

3.Вычислить с1 = gx mod q, c2 = m hy mod q.

Криптограмма = (с1, с2).

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

1.Вычислить m = c2 c1x mod q .

Расшифрование будет верным, поскольку m = c2 c1x = mh y g xy = mg xy g xy = m .

315

Криптостойкость системы Эль-Гамаля зависит от свойств группы G и особенностей конкретной реализации. Схема уязвима к атакам с подобранным шифротекстом. К примеру, имея криптограмму (с1, с2) некоторого (возможно, неизвестного) сообщения m, легко создать криптограмму (с1, 2с2) сообщения 2m.

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

316

Список используемых сокращений

ВП – вредоносная программа; ИИС – искусственная иммунная система; КВ – компьютерный вирус; КС – компьютерная система; ЛОА – ложный объект атаки; МЭ – межсетевой экран;

НСД – несанкционированный доступ (к информации); ОБИ – обеспечение безопасности информации; ОС – операционная система; ПО – программное обеспечение; ПС – программная система;

ПСП – псевдослучайная последовательность; ПСЧ – псевдослучайные числа; РПВ – разрушающее программное воздействие;

СОВ – система обнаружения вторжений; ЭЦП – электронная цифровая подпись; AIS – Artificial Immune System;

MAC – Message Authentication Code.

Список терминов

Антиген – вещество, распознаваемое адаптивной иммунной системой и вызывающее защитную реакцию организма.

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

Атака типа «replay» (атака перехвата и повтора) – попытка вторжения в систему или подделки финансовых средств оплаты с использованием ранее использованных реквизитов доступа или других ранее использованных данных.

Аутентификация объекта (информационного взаимодейст-

вия) – процедура установления целостности массива данных или полученного сообщения; а также в большинстве случаев – установление их принадлежности конкретному автору.

317

Аутентификация субъекта (информационного взаимодейст-

вия) – процедура установления подлинности пользователя (абонента сети), программы или устройства.

Вирус (компьютерный вирус) – программа, которая может

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

Врожденный иммунитет – система проактивных защитных факторов организма, присущих данному виду, как наследственно обусловленное свойство.

Генератор ПСЧ – устройство или программа, формирующие последовательность ПСЧ; именно качеством используемых генераторов ПСЧ определяется надежность стохастических методов защиты.

Детектор (вирусов) – антивирусная программа, идентифицирующая вирусы по сигнатурам или методами эвристического анализа; см. также сканер.

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

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

Дроппер (вируса) (от англ. dropper) – программа, содержащая в себе КВ и заражающая им систему, сам вирус при этом управления не получает.

Зашифрование – процесс преобразования открытых данных в закрытые (зашифрованные).

Криптоалгоритм – алгоритм криптографического преобразования.

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

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

318

Криптографический протокол – протокол, использующий криптографическое преобразование.

Криптографическое преобразование – специальное преобра-

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

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

Криптографический примитив – «строительный блок» (опе-

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

Криптостойкость (стойкость к криптоанализу) – способ-

ность криптосистемы противостоять различным атакам на нее. Криптосчетчик – счетчик, состояние которого можно инкре-

ментировать, не раскрывая его зашифрованного значения. Криптотроян – вредоносная программа, зашифровывающая

данные пользователя-жертвы.

Логическая бомба – программный код, внедренный в какую-то полезную программу, который должен «взорваться» при выполнении определенных условий; примеры таких условий: присутствие или отсутствие каких-либо файлов, наступление определенной даты, имя пользователя, запустившего приложение, и др.

Макро-вирус – программа вредоносного характера на языке (макроязыке), встроенном в прикладную систему (текстовый редактор, электронную таблицу и пр.).

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

Межсетевой экран (firewall) – средство обеспечения безопасности сегмента IP-сети; Firewall обеспечивает контроль за

319

безопасностью в защищаемом сегменте сети и связь данного сегмента с внешним миром; основной недостаток существующих систем Firewall – это то, что их разработчики смотрят на проблемы защиты IP-сетей не с точки зрения взломщика, а с точки зрения пользователя.

Метод грубой силы (brute force attack) — метод преодоления криптографической защиты перебором большого числа вариантов; например, перебор всех возможных ключей для расшифрования сообщения или всех возможных паролей для неавторизованного входа в систему.

Монитор – программа, работающая в фоновом режиме и активизирующаяся при доступе к защищаемому ресурсу; перехватывает «вирусо-опасные» ситуации (вызовы на открытие для записи в выполняемые файлы, запись в boot-секторы дисков или MBR винчестера и другие, иначе говоря, вызовы, характерные для вирусов в моменты их функционирования) и сообщает о них пользователю (пример – SpIDer Guard).

Недоказуемое шифрование (questionable encryption) – стохас-

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

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

Обеспечение доступности – исключение возможности атак, вызывающих отказ в обслуживании (DoS-атак).

Обеспечение секретности – исключение возможности пассивных атак на передаваемые или хранимые данные.

320