30542

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

Доклад

Математика и математический анализ

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

Русский

2013-08-24

43.95 KB

35 чел.

  1.  Криптографические протоколы – основные виды и типы, область применения. Идентификация и аутентификация.

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

Различают прикладные и примитивные протоколы. Прикладной протокол решает конкретную задачу, которая возникает на практике. Примитивные протоколы используют как «строительные блоки» для прикладных.

Виды протоколов:

  1.  Протоколы подбрасывания монеты по телефону

Алиса и Боб решили бросать жребий по телефону. Жребий бросает Алиса. Боб считает, что выпадет решка и сообщает об этом по телефону Алисе, после чего слышит, как Алиса на другом конце провода говорит: «Ну хорошо…Я бросаю…Орел! Ты проиграл!».

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

  1.  Алиса не должна иметь возможности бросать после того, как получила догадку.
  2.  Боб не должен иметь возможности узнать результат бросания до того, как объявит о догадке.

Протокол Блюма-Микали.

Алиса (A) и Боб (B) заранее договариваются о некоторой односторонней функции f : XY, где X – конечное множество натуральных чисел, среди которых равное количество четных и нечетных.

A: выбирает случайным образом число xX, затем вычисляет значение y=f(x)

AB:   y

BA: бит с=0, если догадка «x - четное», c=1, если догадка «x - нечетное».

AB:  x

B:         проверяет f(x)=y.

Возникает вопрос – зачем Алисе брать число xX, не проще ли загадать бит b и вычислить одностороннюю функцию от него - y=f(b)? Дело в том, что множество аргументов односторонней функции должно быть достаточно большим, чтобы исключить подбор y. Ведь бит b может принимать только два значения – «0» и «1». Абоненту B тогда будет достаточно вычислить y0=f(0) и y1=f(1) и определить, которое из них совпадает с y, чтобы догадаться, какое значение принял бит b.

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

Протокол подбрасывания монеты (на основе проблемы дискретного логарифмирования).

Параметры протокола: p – большое простое число, g - порождающий элемент мультипликативной группы Zp*.

А : выбирает случайное xZp, вычисляет y=gx mod p.

AB: y

BA: догадка - бит с.

AB:  x

B:         проверяет gx mod p=y.

  1.  Разделение секрета.

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

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

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

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

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

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

Но что, если заместители договорятся сместить своих начальников и воспользуются своими частями ключа? Тогда для того, чтобы восстановить ключ, злоумышленникам потребуется подобрать всего лишь 32 бита, что потребует всего 232 ≈ 4,3·109 итераций вместо 264≈ 18,5·1018 при подборе 64 битов. Злоумышленники смогут восстановить ключ за вполне обозримое время.

Разумным будет разделить этот 64-битовый ключ k так, чтобы каждому досталось по 64 бита. Как это сделать? Генеральному директору, и заместителям можно выдать по случайной 64-битовой строке s1, s2, s3 соответственно, а супругу(е) главного бухгалтера – строку

s4=ks1s2s3  mod 264.

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

s1+s2+s3+s4 mod 264=k, можно будет однозначно восстановить k.

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

В протоколе разделения секрета имеются n участников, называемых также абонентами (обозначим их P1, P2, … , Pn), и один выделенный участник D, называемый дилером, или раздающим.

Множество всех абонентов обозначим P={P1, P2, … , Pn}.

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

Структурой доступа Г будем называть непустое множество всех групп доступа схемы.

Далее будем полагать, что любой абонент из P входит хотя бы в одну группу доступа, иначе присутствие такого абонента в P бессмысленно. Также считаем, что Г замкнуто, то есть если ABP, и AГ, то BГ. Действительно, если абоненты P1, P2, …, Pk могут совместно восстановить секрет, то, если к ним присоединится еще несколько абонентов Pk+1,…, Pk+t, получившаяся группа тем более сможет восстановить секрет.

Протокол разделения секрета состоит из двух основных фаз.

1. На фазе раздачи, или разделения, секрета дилер, знающий секрет m, генерирует n долей секрета m1, m2, … ,mn и посылает долю mi участнику Pi (i=1,…,n) по защищенному каналу связи. Раздача должна быть организована таким образом, чтобы разрешенные группы участников, собравшись вместе, могли однозначно восстановить секрет m, а неразрешенные – не могли.

2. На фазе восстановления секрета какая–либо группа из структуры доступа Г объединяет свои доли секретов mi (i=1,…,n) так, чтобы получить секрет m.

Далее, в качестве примера, приведем три пороговые схемы разделения секрета.

  1.  Интерактивные системы доказательства

Интерактивной системы доказательства и доказательства с нулевым разглашением.

Под интерактивной системой доказательства (P,V,S) понимают протокол взаимодействия двух абонентов: P - доказывающего и V - проверяющего.

P хочет доказать V истинность утверждения S (например «я – Иван Иванович»). При этом V не может самостоятельно проверить S.

Абонент P может оказаться противником, пытающимся доказать V истинность ложного утверждения S (на самом деле P – Василий Васильевич, который хочет выдать себя за Ивана Ивановича).

Протокол может состоять из многих раундов обмена сообщениями между P и V и должен удовлетворять условиям:

1. Полнота – если S истинно, то P докажет V истинность S с вероятностью 1.

2. Корректность – если S ложно, то P не сможет убедить V в истинности S с вероятностью, близкой к 1.

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

Нулевое разглашение – в результате работы интерактивного протокола с нулевым разглашением (P,V,S) абонент V не увеличит своих знаний об S.

Например, P хочет доказать проверяющему V, что обладает секретным ключом k, но не желает раскрывать значения этого ключа, и хочет, чтобы проверяющий не узнал ни одного бита этого ключа.   

Интерактивная система доказательства представляет собой вероятностный протокол, состоящий из m раундов. На каждом раунде проверяющий V просит доказывающего P установить истинность или ложность какого-то утверждения si. Эти утверждения выбираются проверяющим таким образом, чтобы участник, знающий секрет S, мог установить их истинность точно, а  участник не знающий S, мог ее только угадать.

  1.  Электронная монета.

Итак, задача такова: найти такую схему платежей, при которой:

а) электронный бумажник не был бы связан с банковским счетом;

б) каждая электронная купюра имела бы уникальный номер и была подписана банком;

в) банк не знал бы, какой номер стоит на купюре, выданной данному клиенту.

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

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

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

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

1. снятие со счета;

2. платеж;

3. депозит.

В транзакции снятия со счета покупатель получает подписанную банком электронную банкноту на затребованную сумму. При этом счет покупателя уменьшается на эту сумму.

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

С помощью транзакции депозита, покупатель может положить "сдачу" на свой счет в банке.

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

  1.  Скрытый канал

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

Тогда абонент A, желая отправить абоненту B тайное послание, берет некоторое невинное сообщение (квартальный отчет), подписывает его цифровой подписью, встроив в нее тайное сообщение (фото с Рэдклиффом) и отправляет по открытому каналу связи. Абонент U, перехватив сообщение, проверяет подпись под ним, и, не встретив ничего подозрительного, успокаивается. Абонент B, получив послание, выбрасывает невинное сообщение (кому нужен какой-то там квартальный отчет?) и извлекает из подписи вожделенное тайное послание.

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

  1.  Протоколы идентификации и аутентификации.

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

  1. идентификация на основе обладания чем-либо (электронным ключом, печатью и т.п.);
  2. идентификация на основе знания чего-либо;
  3. идентификация на основе отличительных черт (биометрических данных – голос, сетчатка глаза, отпечатки пальцев).

Для идентификации средствами криптографии все эти три вида могут быть сведены к одному – к идентификации на основе владения какой-либо информацией.

Существует несколько подходов к построению схем идентификации и аутентификации.

Вот эти подходы:

  1.  Парольные схемы идентификации. Парольные схемы, как правило, применяются для аутентификации зарегистрированных пользователей в компьютерной системе. Для того чтобы такую схему можно было использовать, система должна хранить идентификаторы всех зарегистрированных пользователей и их пароли. Разумеется, хранение пароля в системе в открытом виде нежелательно, поэтому пароли, как правило, хранятся в преобразованном виде – шифрованном или хешированном);
  2.  Запрос-ответные схемы. Запрос - ответные схемы применяются для взаимной идентификации абонентов. Для того, чтобы произвести идентификацию, каждый из участников должен предъявить другому какую-то удостоверяющую информацию. Запрос-ответные схемы идентификации используются как элемент протоколов раздачи ключей. Взаимная идентификация может проходить как на основе общего секрета, которым владеют участники (как правило, такой подход используется в системах опознавания «свой - чужой»), так и без общего секрета, но с центром доверия, на котором опубликованы открытые ключи участников. Протоколы, используемые в первом случае, называются протоколами рукопожатия.
  3.  Протоколы идентификации с нулевым разглашением.
  4.  Схема аутентификации Фиата и Шамира

Одна из наиболее известных схем аутентификации - схема Фиата и Шамира.

Центр доверия выбирает два больших простых числа p и q и вычисляет число n=pq. Простые множители p и q являются секретными. 

Каждый абонент выбирает случайные числа siZn и вычисляет vi=(si2)-1mod n (i=1,…,k). Числа si образуют секретный ключ абонента, а числа vi - его открытый ключ, который помещается в сертифицированный справочник.

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

Протокол аутентификации P перед V состоит в выполнении следующих шагов в цикле t раз.

1.  PV: x=r2 mod n, где rZn – случайное число;

2.  VP: случайный булев вектор (e1, e2, … , ek); 

3.  PV: y=rmod n

4.  V: проверяет сравнение . 

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

Полнота следует из того, что если  vi=(si2)-1mod n, то есть P действительно обладает секретным ключом s1, s2, …, sk, то 

(mod n).

Корректность следует из того, что злоумышленник, пытающийся выдать себя за P, не сможет вычислить y без знания секретного ключа. Сообщения, ранее перехваченные злоумышленником, не помогут ему узнать секретный ключ или осуществить подмену (послать уже ранее переданное и перехваченное сообщение). Этому помешает наличие в y случайного множителя r, значение которого злоумышленник не знает.

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

Шамиром доказано, что эта схема является системой доказательства с нулевым разглашением.

Протоколы рукопожатия.

Пусть существуют два абонента – A и B. Каждый из них обладает секретной информацией k (тот, кто обладает такой информацией, считается «своим», тот, кто не обладает – «чужим»). Допустим, абоненты A и B хотят начать взаимодействие, но предварительно им надо убедиться, что предполагаемый партнер является «своим», то есть обладает той же секретной информацией k. При этом ни один из абонентов не хочет раскрывать k ни своему vis-à-vis, ни предполагаемому злоумышленнику, который может прослушивать канал связи.

Протокол рукопожатия 2:

Еk(x) – шифрование текста x на ключе k (с использованием симметричной криптосистемы);

k – секретный ключ, которым обладают только «свои» абоненты.

AB: случайное число r1

BA: s1=Ek(r1, r2, B*), где r2 – случайное число, B – идентификатор B 

(* указывает на то, что этот параметр необязательный);

A: вычисляет (r1´, r2´, B*)=Dk(s1) и проверяет равенство r1=r1´. Если равенство неверно, то A определяет В как «чужого» и прерывает протокол. Иначе A определяет B как «своего».

AB: s2=Ek(r2, r1);

B: вычисляет (r2´, r1´)=Dk(s2) и проверяет равенства r1=r1´, r2=r2´. Если равенства неверны, то B определяет A как «чужого». Иначе B определяет A как «своего».

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


 

А также другие работы, которые могут Вас заинтересовать

64174. Проект хлебозавода мощностью 35 т/сутки с цехом бараночных изделий в г. Сыктывкар 1.19 MB
  Наряду с мероприятиями по улучшению ассортимента продолжается работа по рациональному использованию и снижению расхода муки. На ряде предприятий для перемещения муки сахарапеска и других компонентов часто применяют различные виды пневматического транспорта.
64175. Анализ оплаты и организации труда в ОАО «Щомыслица» 536.5 KB
  Понятие оплаты труда её принципы формы и системы оплаты труда Тарифная система функции тарифных ставок и окладов Анализ оплаты и организации труда в ОАО Щомыслица Организационно-производственная характеристика предприятия Совершенствование организации и оплаты труда в АПК на примере ОАО Щомыслица...
64176. Электроснабжение ремонтно-механического цеха ЦРЭО ММК им. Ильича с проектировкой ТП 1.88 MB
  Цех ремонта энергетического оборудования предназначен для ремонта и изготовления различных деталей, необходимых для выполнения функций основных цехов. В цеху содержатся металлообрабатывающие станки, сварочное и грузоподъемное оборудование, а также вентиляторы и кондиционерная установка.
64180. Изучение взаимоотношений агрессивных подростков со сверстниками 850.5 KB
  Достоверно установлено что жестокое обращение с ребенком в семье не только повышает агрессивность его поведения в отношении со сверстниками но и способствует развитию склонности к насилию в более зрелом возрасте превращая физическую агрессию в жизненный стиль личности...
64181. Снижение пожарной опасности на автозаправочной станции «Нефтересурсы» 2.97 MB
  Расчет концентрацию паров бензина при открывании горловины автоцистерны. С целью снижения вредных выбросов автомобилями их стали оборудовать каталитическими системами нейтрализации отработавших газов что потребовало ужесточения требований к качеству применяемого бензина.
64182. Анализ конструктивного оформления стадии копчения мясных изделий 2.75 MB
  В процессе собственно копчения накапливаются и перераспределяются коптильные вещества в продукте. Целью выпускной работы является анализ конструктивного оформления стадии копчения мясных изделий.