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

Атаки CPA и CCA изначально предназначались для активного криптоанализа криптосистем с секретным ключом. Целью этого криптоанализа является взлом криптосистемы с помощью пар открытых и зашифрованных сообщений, получаемых в ходе атаки. Затем они были адаптированы для криптоанализа криптосистем с открытым ключом. Следует отметить три особенности криптосистем с открытым ключом.

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

Как правило, криптосистемы с открытым ключом имеют стройную алгебраическую структуру, обладающую свойствами замкнутости, ассоциативности, гомоморфизма и т.п. Атакующий может использовать эти свойства и взломать зашифрованный текст с помощью хитроумных вычислений. Если атакующий имеет доступ к блоку расшифровки, его вычисления могут дать представление об исходном тексте и даже взломать всю криптосистему. Следовательно, криптосистемы с открытым ключом особенно уязвимы для атак CCA и CCA2. Исходя из этого можно сформулировать следующее правило, владелец открытого ключа никому не должен предоставлять услуги расшифровки. Это условие должно выполняться во всех криптосистемах с открытым ключом.

На первый взгляд, атака CCA слишком ограничивает возможности атакующего. В приложениях пользователь, подвергающийся атаке (то есть пользователь, к которому обратились за расшифровкой сообщения), на самом деле не знает об этом. Следовательно, пользователю не известно, когда ему следует прекратить расшифровку. Как правило, предполагается, что пользователь слишком наивен и не предполагает о существовании атакующего, а значит, должен предоставлять услуги по расшифровке сообщений постоянно. С другой стороны, любая криптосистема с открытым ключом должна быть устойчивой к атакам CPA, поскольку атакующий может сам зашифровывать подобранные открытые сообщения. По этой причине, в основном, мы будем рассматривать средства защиты от атаки CCA2.

Задача RSA

Средства защиты криптосистемы RSA от атак CPA основаны на сложности вычисления корня e-й степени шифрованного текста c по составному целочисленному модулю n. Это так называемая задача RSA.

Исходные данные:

e: целое число, удовлетворяющее условию НОД(e, (p-1)(q-1)) = 1.

c принадлежит множеству целых чисел по модулю N.

Результат:

Единственное целое число m, принадлежащее множеству целых чисел по модулю N, удовлетворяющее условию me ?c(mod N)

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

Условие неразрешимости задачи RSA. Алгоритмом решения задачи RSA называется вероятностный полиномиальный алгоритм A с преимуществом е > 0:

е = P[m<A(N,e, me (mod N))],

где входные данные A определены выше.

Пусть имеется генератор вариантов задачи RSA - IG, получающий на вход число 1k, время работы которого является полином от параметра k, а результатом - 1) 2k - битовый модуль N = pq, где p и q - два разных равномерно распределенных случайных простых числа, состоящих из k бит, и 2) e принадлежит множеству целых чисел по модулю (p-1)(q-1).

Будем говорить, что генератор IG удовлетворяет условиям неразрешимости задачи RSA, если для вариантов IG(1k) не существует алгоритма решения с преимуществом е > 0, которое не является пренебрежимо малым по отношению ко всем достаточно большим числам k.

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

Следует отметить, что вероятностное пространство в этом условии включает в себя пространство вариантов, пространство исходных сообщений и пространство случайных операций рандомизированного алгоритма решения задачи RSA. Кроме того, в условии неразрешимости задачи RSA на вход предполагаемого алгоритма поступает показатель степени e, используемый при шифровании. Это ясно очерчивает цель атаки: решить задачу RSA при заданном показателе степени e. Существует альтернативная постановка задачи RSA, которая называется сильной задачей RSA. Ее цель - найти некоторый нечетный показатель степени e > 1 и решить задачу RSA для этого показателя. Очевидно, что решить сильную задачу RSA проще, чем обычную задачу RSA, в которой показатель степени e фиксирован. Считается, что сильная задача является трудноразрешимой. Условие трудной разрешимости сильной задачи RSA легло в основу некоторых алгоритмов шифрования и криптографических протоколов.

Уязвимость учебного алгоритма RSA

Рассмотрим свойства, обуславливающие стойкость (или нестойкость) учебного алгоритма RSA.

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

Теорема: Криптосистема RSA устойчива к атаке на основе подобранного открытого текста по принципу «все или ничего» тогда и только тогда, когда выполняются условия неразрешимости задачи RSA.

Принцип «все или ничего»:

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

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

Принцип пассивной атаки:

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

Во-первых, рассмотрим принцип «все или ничего». Слово «все» означает, что при расшифровке восстанавливается весь блок исходного сообщения: размеры сообщения и модуля совпадают. В приложениях это условие выполняется не всегда. В реальных системах исходный текст, как правило, содержит определенную часть открытой информации, известной атакующему. Учебный вариант RSA не скрывает эту информацию. Например, если известно, что зашифрованный текст представляет собой число, не превосходящее 1 000 000 (например секретное предложение цены или оклада), то, имея зашифрованное сообщение, атакующий может восстановить исходный текст менее чем за 1 000 000 попыток. Как правило, текс, зашифрованный алгоритмом RSA трудно разложить на простые множители из-за перемешивающего свойства функции шифрования, которое практически всегда приводит к тому, что размер зашифрованного текста равен размеру модуля. Однако из мультипликативного свойства следует, что если исходный текст поддается факторизации, то и зашифрованный текст - тоже. Факторизация небольшого исходного сообщения не является трудноразрешимой задачей, и использовали мультипликативное свойство функции RSA:

(m1*m2)e ?m1e*m2e?c1*c2(mod N)

Реализация протокола электронного голосования с помощью алгоритма RSA

Рассмотрим протокол электронного голосования. Электронное голосование должно удовлетворять следующим требованиям:

Голосовать могут только те, кто имеет на это право.

Каждый имеет право изменить свой голос.

Никто не может узнать, за кого проголосовал конкретный избиратель.

Никто не может проголосовать вместо другого.

Никто не может тайно изменить чей-то голос.

Каждый голосующий может проверить, что его голос учитывался при подведении итогов голосования.

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

Каждый может голосовать не более одного раза.

Каждый знает, кто голосовал, а кто нет.

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

Регистрация

Тайность

Анонимность

Полный контроль своего голоса

Полное доверие

В данной курсовой работе рассматривается имитационное отношение между Центром голосования и голосующим.

Голосование проводилось обычным образом в 3 этапа:

1) инициализация: объявление вопроса, составление списка голосующих, генерирование ключей для криптосистем;

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

3) подсчёт голосов: организаторы вычисляют и публикуют результат выборов, желающие проверяют честность выборов.

В нашем протоколе используется протокол анонимного распределения ключей. Рассмотрим данный протокол:

Центр голосования публикует список всех правомочных участников.

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

Центр голосования публикует список пользователей, участвующих в голосовании.

Каждый участник получает идентификационный номер I, с помощью протокола анонимного распределения ключей.

Каждый участник генерирует пару открытый ключ/закрытый ключ : e, d. Если v - это бюллетень, то голосующий создает и посылает в центр голосования следующее сообщение: I, Ee(I, v). Это сообщение должно быть послано анонимно.

Центр голосования подтверждает получение бюллетеня, публикуя: Еe(I, v).

Каждый голосующий посылает в центр голосования: I, d.

Центр голосования расшифровывает бюллетени. В конце голосования он публикует их результаты и, для каждого варианта ответа, список соответствующий значений Еe(I, v).

Если участник обнаруживает, что его бюллетень подсчитан неправильно, он протестует, посылая центру голосования: I, Еe(I, v), d.

Если участник хочет изменить свой бюллетень с v на v', он посылает центру голосования: I, Еk(I, v'), d.

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

Этапы 1 - 3 являются предварительными. Их цель состоит в том, чтобы узнать и опубликовать всех действительных участников. Хотя некоторые из них, вероятно, не примут участи в голосовании, это уменьшает возможность центра голосования добавить поддельные бюллетени. На этапе 4 два участника могут получить один и тот же идентификационный номер. Эта возможность может быть минимизирована, если число возможных идентификационных номеров будет гораздо больше, чем число реальных участников. Если два участника присылают бюллетени с одинаковым идентификатором, ЦИК генерирует новый идентификационный номер I', выбирает одного из участников и публикует: I', Еk(I, v). Владелец этого бюллетеня узнает о произошедшей путанице и посылает свой бюллетень снова, повторяя этап 5 с новым идентификационным номером I'. Этап 6 дает каждому участнику возможность проверить, что центр голосования правильно получила его бюллетень. Если его бюллетень неправильно подсчитан, он может доказать это на этапе 9. Предполагая, что бюллетень голосующего на этапе 6 правилен, сообщение, которое он посылает на этапе 9 доказывает, что его бюллетень был неправильно подсчитан.

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

Еще одной, более серьезной проблемой является то, что центр голосования может не подсчитать какой-нибудь бюллетень: Алиса утверждает, что центр голосования намеренно пренебрег ее бюллетенем, а центр голосования утверждает, что Алиса никогда не голосовала и Алиса не сможет этого опровергнуть.

Использование «открепительного талона» в протоколе электронного голосования

В «открепительном талоне» будем использовать криптосистему RSA. Будем также считать, что у нас есть 2 лица Центр и Участник.

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

Тем временем, у Участника есть:

n - его секретное случайное число ( он его сам выбирает)

f(n) =an(mod P) - некоторая хеш-функция,

где P - некоторое простое число

r - случайное число (маскирующий множитель) вычисляет значение

r-1 из r*r-1 = 1 (mod N)

r` = f(n)*re(mod N)

При этом действия Участника не анонимны, за исключением выбора числа n.

Далее, Участник отправляет Центру сообщение, зашифрованное с помощью своего секретного ключа в следующем виде: r`d1(mod N)

Центр расшифровывает его с помощью открытого ключа e1:

(r`d1)e1(mod N) = r`

Центр вычисляет r`` = r`d(mod N) и передает его Участнику. - Это и есть подпись вслепую)

Участник вычисляет следующее:

r``de(mod N) = r`d = (f(n))d*red= (f(n))d*r(mod N)

(f(n))d*r*r-1(mod N) = (f(n))d(mod N) -

подписанный открепительный талон Центром

C этого момента пара чисел {n, (f(n))d} будут являться открепительным талоном.

Этап голосования:

Голосование проходит анонимно.

Участник содержит Ф-результат своего голоса и открепительный талон {n, (f(n))d} и передает этот набор Центру. И Центр производит проверку этого набора:

Вычисляет f(n)

Проверяет на равенство выражение (f(n)d)e(mod N) ==f(n), если да, то открепительный талон является подлинным и в базу данных Центра заносится результат голосования Участника, а именно Ф.

Приложение

1), 2), 3) - отображение web-страниц.

Литература

1. Баричев С. Криптография без секретов.

2. Ященко В.В. Введение в криптографию

3. Венбо Мао Современная криптография «теория и практика»

Страницы: 1, 2, 3, 4