Главная / Каталог

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

y1 = (x mod p

Аналогично поступает и второй пользователь, генерируя x2 и вычислив y2, отправляя его первому пользователю. В результате этого они могут вычислять k12 = (x1x2mod p.

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

Не зная x1 и x2, злоумышленник может попытаться вычислить k12, зная только перехваченные y1 и y2. Эквивалентность этой проблемы проблеме вычисления дискретного логарифма есть главный и открытый вопрос в системах с открытым ключом. Простого решения до настоящего времени не найдено. Так, если для прямого преобразования 1000-битных простых чисел требуется 2000 операций, то для обратного преобразования (вычисления логарифма в поле Галуа) - потребуется около 1030 операций.