30542

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

Доклад

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

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

Русский

2013-08-24

43.95 KB

42 чел.

  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.


 

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

59319. Сценарій свята осені 55.5 KB
  Баба й дід розповідали: Перси гарбузом назвали Не мене а жовту диню Мою славну господиню. Мене завезли сюди триста літ тому. Ну коли ти капусто така справедлива то скажи щось і про мене. Мене їсть худоба сирою а люди варять мене або квасять.
59321. Танцювальний марафон 86 KB
  Танець знаний як повільний англійський вальс чи вальсбастон його друга назва родина якого Англія і який там популярний серед всіх своїх середовищ. Цей американський танець здобув популярність ще в Англії де дуже оберігався від впливу джазових та пластики.
59322. Сценарний план конкурсу акторських здібностей 45 KB
  В результаті чого король щоб виконати бажання принцеси видає указ про створення театру і слуга оголошує конкурс акторських здібностей. для того щоб визначити переможця Конкурсу акторських здібностей ми запропонуємо нашим учасникам ряд конкурсів які і будуть орієнтиром у визначенні...
59323. Населення України 57 KB
  Формування особистісно значущої для учнів мети відбувається методом проблематизації: Чому зменшується кількість населення України Шляхи вирішення цієї проблеми. Ми сьогодні підібє підсумок з теми Населення України. На уроці пропоную обговорити проблему...
59324. Особистісно-орієнтоване навчання. Нове ?! Цікаве?! Потрібне?! 103 KB
  Забороняється: Висловлюватись образливо про будького; Під час обговорення питання переходити на особистість опонента; Переривати співрозмовника; Бути категоричним; Висміювати думку опонента чи доводити її до абсурду; Спрямовувати розмову в інший бік коли немає аргументів...
59325. Шануй батька й неньку 103 KB
  Формувати почуття обов‘язку перед батьками довести всім присутнім на святі що батьки і діти це Одне ціле. Діти. Ви нас теж любіть рідненькі Бо ми діти дорогенькі Хочем бути на вас схожі І як ви такі ж хороші. Так любі діти батько й мати найрідніші найближчі кожному з нас люди.
59326. Сценарій новорічного свята 51.5 KB
  Добрий вечір вам малята любі хлопці тай дівчата. добрий вечір шановне панство В. Добрий вечір пані та панове О. Як ви хочете щоб ми провели сьогоднішній вечір урочисто Чи так щоб всім сподобалось...
59327. Сценарій фестивалю “Повір у себе” 32.5 KB
  Весна. Цвіте на землі і летить у небесах, як сонячна богиня волі, розбуджує природу, звільняє від снігів і морозів землю, розсіває квіти і квітчає сади. Весна – це поклик молодості, голос радості й щастя, віри й любові, надії й краси, поезії й пісні.