Криптография без секретов

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

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

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

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

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

Итак, пусть име­ют­ся два поль­зо­ва­те­ля Александр и Борис. От ка­ких на­ру­ше­ний и дей­ст­вий зло­умыш­лен­ни­ка долж­на за­щи­щать сис­те­ма ау­тен­ти­фи­ка­ции.

Александр за­яв­ля­ет, что он не по­сы­лал со­об­ще­ние Борису, хо­тя на са­мом де­ле он все-та­ки по­сы­лал.

Для ис­клю­че­ния это­го на­ру­ше­ния ис­поль­зу­ет­ся элек­трон­ная (или циф­ро­вая) под­пись.

Мо­ди­фи­ка­ция (пе­ре­дел­ка).

Борис из­ме­ня­ет со­об­ще­ние и ут­вер­жда­ет, что дан­ное (из­ме­нен­ное) со­об­ще­ние по­слал ему Александр.

Борис фор­ми­ру­ет со­об­ще­ние и ут­вер­жда­ет, что дан­ное (из­ме­нен­ное) со­об­ще­ние по­слал ему Александр.

Владимир пе­ре­хва­ты­ва­ет со­об­ще­ния ме­ж­ду Александром и Борисом с це­лью их скры­той мо­ди­фи­ка­ции.

Для за­щи­ты от мо­ди­фи­ка­ции, под­дел­ки и мас­ки­ров­ки ис­поль­зу­ют­ся циф­ро­вые сиг­на­ту­ры.

Мас­ки­ров­ка (ими­та­ция).

Владимир по­сы­ла­ет Борису со­об­ще­ние от име­ни Александра .

В этом случае для за­щи­ты так­же ис­поль­зу­ет­ся элек­трон­ная под­пись.

По­втор.

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

Наи­бо­лее дей­ст­вен­ным ме­то­дом за­щи­ты от по­вто­ра яв­ля­ют­ся

• 
  ис­поль­зо­ва­ние ими­тов­ста­вок,
  
• 
  учет вхо­дя­щих со­об­ще­ний.
  

Электронная подпись на основе алгоритма RSA

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

Предположим, что

d,p,q - секретные, а е, n=pq - открытые.

Замечания.

1. Разложение по n дает: (n)=(p-1)(q-1); зная (n) и e, можно найти d.

2. Из e и d можно найти кратность (n); кратность (n) позволяет определить делители n.

Пусть DATA - передаваемое Александром Борису сообщение.

Александр подписывает DATA для Бориса при передаче :

Ee_B,n_B { Ed_A,n_A {DATA}}.

При этом он использует:

• 
  закрытый ключ Ed_A,n_A Александра,
  
• 
  открытый ключ Ee_B,n_B Бориса.
  

Борис может читать это подписанное сообщение сначала при помощи закрытого ключа Ed_В,n_В Бориса с целью получения

Ed_A,n_A {DATA} = Ed_B,n_B {Ee_B,n_B {Ed_A,n_A {DATA}}}

и затем - открытого ключа Ee_A,n_A Александра для получения

DATA = Ee_A,n_A { Ed_A,n_A {DATA}}.

Таким образом, у Бориса появляется сообщение DATA, посланное ему Александром.

Очевидно, что данная схема позволяет защититься от нескольких видов нарушений.

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

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

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

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

Исходный текст

Исходный текст

Исходный текст

Подпись

Исходный текст ’






В 1991 г. Национальный институт стандартов и технологии (NIST) предложил для появившегося тогда алгоритма цифровой подписи DSA (Digital Signature Algorithm) стандарт DSS (Digital Signature Standard), в основу которого положены алгоритмы Эль-Гамаля и RSA. ¹³

Цифровая сигнатура

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

Цифровая сигнатура - это строка символов, зависящая как от идентификатора отправителя, так и содержания сообщения.

сообщение

сигнатура








Цифровая сигнатура

Ни­кто при этом кро­ме поль­зо­ва­те­ля А не мо­жет вы­чис­лить циф­ро­вую сиг­на­ту­ру А для кон­крет­но­го со­об­ще­ния. Ни­кто, да­же сам поль­зо­ва­тель не мо­жет из­ме­нить по­слан­но­го со­об­ще­ния так, что­бы сиг­на­ту­ра ос­та­лась не­из­мен­ной. Хо­тя по­лу­ча­тель дол­жен иметь воз­мож­ность про­ве­рить яв­ля­ет­ся ли циф­ро­вая сиг­на­ту­ра со­об­ще­ния под­лин­ной. Что­бы про­ве­рить циф­ро­вую сиг­на­ту­ру, поль­зо­ва­тель В дол­жен пред­ста­вить по­сред­ни­ку С ин­фор­ма­цию, ко­то­рую он сам ис­поль­зо­вал для ве­ри­фи­ка­ции сиг­на­ту­ры.

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

Рас­смот­рим ти­пич­ную схе­му циф­ро­вой сиг­на­ту­ры.

Пусть Е - функция симметричного шифрования и f - функция отображения некоторого множества сообщений на подмножество мощности р из последовательности {1, ..., n}.

Например р=3 и n=9. Если m - сообщение , то в качестве f можно взять функцию f(m) = {2, 5, 7}.

Для каждого сообщения пользователь А выбирает некоторое множество ключей K=[K₁, ..., K_n} и параметров V={v₁, ...,v_n} для использования в качестве пометок сообщения, которое будет послано В. Множества V и V’={E(v₁,K₁) ..., E(v_n,K_n)} посылаются пользователю В и заранее выбранному посреднику С.

Пусть m - сообщение и idm - объединение идентификационных номеров отправителя, получателя и номера сообщения. Если f({idm, m}), то цифровая сигнатура m есть множество K’=[K_i, ..., K_j}. Сообщение m, идентификационный номер idm и цифровая сигнатура К’ посылаются В.

V, V'


сообщение, K'




V, V'

Получатель В проверяет сигнатуру следующим образом. Он вычисляет функцию f({idm, m}) и проверяет ее равенство К’. Затем он проверяет, что подмножество {v_i, ...,v_j} правильно зашифровано в виде подмножества {E(v_i,K_i) ..., E(v_j,K_j)} множества V’.

В кон­фликт­ной си­туа­ции В по­сы­ла­ет С сообщение m, иден­ти­фи­ка­ци­он­ный но­мер idm и мно­же­ст­во клю­чей K’, ко­то­рое В объ­яв­ля­ет сиг­на­ту­рой m. То­гда по­сред­ник С так же, как и В, бу­дет спо­со­бен про­ве­рить сиг­на­ту­ру. Ве­ро­ят­ность рас­кры­тия двух со­об­ще­ний с од­ним и тем же зна­че­ни­ем функ­ции f долж­на быть очень ма­ла. Что­бы га­ран­ти­ро­вать это, чис­ло n долж­но быть дос­та­точ­но боль­шим, а чис­ло р долж­но быть боль­ше 1, но мень­ше n.

Ряд не­дос­тат­ков этой мо­де­ли оче­ви­ден:

• 
  долж­но быть третье ли­цо - по­сред­ник, ко­то­ро­му до­ве­ря­ют как по­лу­ча­тель, так и от­пра­ви­тель;
  
• 
  по­лу­ча­тель, от­пра­ви­тель и по­сред­ник долж­ны об­ме­нять­ся су­ще­ст­вен­ным объ­е­мом ин­фор­ма­ции, пре­ж­де чем бу­дет пе­ре­да­но ре­аль­ное со­об­ще­ние;
  
• 
  пе­ре­да­ча этой ин­фор­ма­ции долж­на осу­ще­ст­в­лять­ся в за­кры­том ви­де;
  
• 
  эта ин­фор­ма­ция ис­поль­зу­ет­ся край­не не­эф­фек­тив­но, по­сколь­ку мно­же­ст­ва K, V, V’ ис­поль­зу­ют­ся толь­ко один раз.
  

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

Хэш-функции

Использование цифровой сигнатуры предполагает использование некоторых функций шифрования:

S = H(k, T),

где S - сигнатура, k - ключ, T - исходный текст.

Функция H(k, T) - является хэш-функцией, если она удовлетворяет следующим условиям:

1. 
   исходный текст может быть произвольной длины;
   
2. 
   само значение H(k, T) имеет фиксированную длину;
   
3. 
   значение функции H(k, T) легко вычисляется для любого аргумента;
   
4. 
   восстановить аргумент по значению с вычислительной точки зрения - практически невозможно;
   
5. 
   функция H(k, T) - однозначна¹⁴.
   

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

Наиболее известные из хэш-функций - MD2, MD4, MD5 и SHA.

Три алгоритма серии MD разработаны Ривестом в 1989-м, 90-м и 91-м году соответственно. Все они преобразуют текст произвольной длины в 128-битную сигнатуру.

Алгоритм MD2 предполагает:

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

Алгоритм MD4 предусматривает:

• 
  дополнение текста до длины, равной 448 бит по модулю 512;
  
• 
  добавляется длина текста в 64-битном представлении;
  
• 
  512-битные блоки подвергаются процедуре Damgard-Merkle¹⁶, причем каждый блок участвует в трех разных циклах.
  

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

Алгоритм SHA (Secure Hash Algorithm) разработан NIST (National Institute of Standard and Technology) и повторяет идеи серии MD. В SHA используются тексты более 2⁶⁴ бит, которые закрываются сигнатурой длиной 160 бит. Данный алгоритм предполагается использовать в программе Capstone¹⁷.

жүктеу/скачать 293.5 Kb.

Достарыңызбен бөлісу: