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

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

2. Из e и d можно найти кратность j(n); кратность j(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. [13]

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

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

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

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

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

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

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

Пусть Е - функция симметричного шифрования и 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 и цифровая сигнатура К’ посылаются В.

Получатель В проверяет сигнатуру следующим образом. Он вычисляет функцию 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) - однозначна[14].

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

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

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

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

·   дополнение текста до длины, кратной 128 битам;

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

·   добавление контрольной суммы к тексту;

·   повторное вычисление контрольной суммы.

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

·   дополнение текста до длины, равной 448 бит по модулю 512;

·   добавляется длина текста в 64-битном представлении;

·   512-битные блоки подвергаются процедуре Damgard-Merkle[16], причем каждый блок участвует в трех разных циклах.

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

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

Управ­ле­ние клю­ча­ми

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

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

Управ­ле­ние клю­ча­ми - ин­фор­ма­ци­он­ный про­цесс, вклю­чаю­щий в се­бя три эле­мен­та:

*  ге­не­ра­цию клю­чей;

*  на­ко­п­ле­ние клю­чей;

*  рас­пре­де­ле­ние клю­чей.

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

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

В са­мом на­ча­ле раз­го­во­ра о крип­то­гра­фи­че­ских ме­то­дах бы­ло ска­за­но, что не сто­ит ис­поль­зо­вать не­слу­чай­ные клю­чи с це­лью лег­ко­сти их за­по­ми­на­ния. В серь­ез­ных ИС ис­поль­зу­ют­ся спе­ци­аль­ные ап­па­рат­ные и про­грамм­ные ме­то­ды ге­не­ра­ции слу­чай­ных клю­чей. Как пра­ви­ло ис­поль­зу­ют дат­чи­ки ПСЧ. Од­на­ко сте­пень слу­чай­но­сти их ге­не­ра­ции долж­на быть дос­та­точ­но вы­со­ким. Иде­аль­ным ге­не­ра­то­ра­ми яв­ля­ют­ся уст­рой­ст­ва на ос­но­ве “на­ту­раль­ных” слу­чай­ных про­цес­сов. На­при­мер, поя­ви­лись се­рий­ные об­раз­цы ге­не­ра­ции клю­чей на ос­но­ве бе­ло­го ра­дио­шу­ма. Дру­гим слу­чай­ным ма­те­ма­ти­че­ским объ­ек­том яв­ля­ют­ся де­ся­тич­ные зна­ки иррациональных чисел, например p или е, которые вычисляются с помощью стандартных математических методов.

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

Накопление ключей

Под на­ко­п­ле­ни­ем клю­чей по­ни­ма­ет­ся ор­га­ни­за­ция их хра­не­ния, уче­та и уда­ле­ния.

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

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

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

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

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

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

Рас­пре­де­ле­ние клю­чей

Рас­пре­де­ле­ние клю­чей - са­мый от­вет­ст­вен­ный про­цесс в управ­ле­нии клю­ча­ми. К не­му предъ­яв­ля­ют­ся два тре­бо­ва­ния:

    Опе­ра­тив­ность и точ­ность рас­пре­де­ле­ния

    Скрыт­ность рас­пре­де­ляе­мых клю­чей.

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

Рас­пре­де­ле­ние клю­чей ме­ж­ду поль­зо­ва­те­ля­ми реа­ли­зу­ют­ся дву­мя раз­ны­ми под­хо­да­ми:

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

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

В обо­их слу­ча­ях долж­на быть га­ран­ти­ро­ва­на под­лин­ность се­ан­са свя­зи. Это мож­но обес­пе­чить дву­мя спо­со­ба­ми:

1. Ме­ха­низм за­про­са-от­ве­та, ко­то­рый со­сто­ит в сле­дую­щем. Ес­ли поль­зо­ва­тель А же­ла­ет быть уве­рен­ным, что со­об­ще­ния ко­то­рый он по­лу­ча­ет от В, не яв­ля­ют­ся лож­ны­ми, он вклю­ча­ет в по­сы­лае­мое для В со­об­ще­ние не­пред­ска­зуе­мый эле­мент (за­прос). При от­ве­те поль­зо­ва­тель В дол­жен вы­пол­нить не­ко­то­рую опе­ра­цию над этим эле­мен­том (на­при­мер, до­ба­вить 1). Это не­воз­мож­но осу­ще­ст­вить за­ра­нее, так как не из­вест­но, ка­кое слу­чай­ное чис­ло при­дет в за­про­се. По­сле по­лу­че­ния от­ве­та с ре­зуль­та­та­ми дей­ст­вий поль­зо­ва­тель А мо­жет быть уве­рен, что се­анс яв­ля­ет­ся под­лин­ным. Не­дос­тат­ком это­го ме­то­да яв­ля­ет­ся воз­мож­ность ус­та­нов­ле­ния хо­тя и слож­ной за­ко­но­мер­но­сти ме­ж­ду за­про­сом и от­ве­том.

2. Ме­ха­низм от­мет­ки вре­ме­ни (“вре­мен­ной штем­пель”). Он под­ра­зу­ме­ва­ет фик­са­цию вре­ме­ни для ка­ж­до­го со­об­ще­ния. В этом слу­чае ка­ж­дый поль­зо­ва­тель ИС мо­жет знать, на­сколь­ко “ста­рым” яв­ля­ет­ся при­шед­шее со­об­ще­ние.

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

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

По­этому в ре­аль­ных ИС, на­при­мер в сис­те­мах оп­ла­ты кре­дит­ных кар­то­чек ис­поль­зу­ет­ся имен­но вто­рой ме­ха­низм ус­та­нов­ле­ния под­лин­но­сти и за­щи­ты от под­де­лок. Ис­поль­зуе­мый ин­тер­вал со­став­ля­ет от од­ной до не­сколь­ких ми­нут. Боль­шое чис­ло из­вест­ных спо­со­бов кра­жи элек­трон­ных де­нег, ос­но­ва­но на “вкли­ни­ва­нии” в этот про­ме­жу­ток с под­лож­ны­ми за­про­са­ми на сня­тии де­нег.

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

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

Алгоритм Диф­фи-Хелл­ма­на

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

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

Если y=a^x,, 1<x<p-1, где - фиксированный элемент поля GF(p), то x=log_{a y} над GF(p). Имея x, легко вычислить y. Для этого потребуется 2 ln(x+y) операций умножения.

Обратная задача вычисления x из y будет достаточно сложной. Если p выбрано достаточно правильно, то извлечение логарифма потребует вычислений, пропорциональных

L(p) = exp { (ln p ln ln p)^0.5 }

Для обмена информацией первый пользователь выбирает случайное число x₁, равновероятное из целых 1...p-1. Это число он держит в секрете, а другому пользователю посылает число

y₁ = a^x mod p

Аналогично поступает и второй пользователь, генерируя x₂ и вычислив y₂, отправляя его первому пользователю. В результате этого они могут вычислять k₁₂ = a^x1^x