Как передать нужную информацию нужному
Как передать нужную информацию нужному адресату в тайне от других?
Каждый из читателей в разное время и с разными целями наверняка пытался решить для себя эту практическую задачу (для удобства дальнейших ссылок назовем ее ``задача ТП'', т. е. задача Тайной Передачи). Выбрав подходящее решение, он, скорее всего, повторил изобретение одного из способов скрытой передачи информации, которым уже не одна тысяча лет.
Размышляя над задачей ТП, нетрудно прийти к выводу, что есть три возможности.
1. Создать абсолютно надежный, недоступный для других канал связи между абонентами.
2. Использовать общедоступный канал связи, но скрыть сам факт передачи информации.
3. Использовать общедоступный канал связи, но передавать по нему нужную информацию в так преобразованном виде, чтобы восстановить ее мог только адресат.
Прокомментируем эти три возможности.
1. При современном уровне развития науки и техники сделать такой канал связи между удаленными абонентами для неоднократной передачи больших объемов информации практически нереально.
2. Разработкой средств и методов скрытия факта передачи сообщения занимается стеганография.
Первые следы стеганографических методов теряются в глубокой древности. Например, известен такой способ скрытия письменного сообщения: голову раба брили, на коже головы писали сообщение и после отрастания волос раба отправляли к адресату.
Из детективных произведений хорошо известны различные способы тайнописи между строк обычного, незащищаемого текста: от молока до сложных химических реактивов с последующей обработкой.
Также из детективов известен метод ``микроточки'': сообщение записывается с помощью современной техники на очень маленький носитель (микроточку), который пересылается с обычным письмом, например, под маркой или где-нибудь в другом, заранее обусловленном месте.
В настоящее время в связи с широким распространением компьютеров известно много тонких методов ``запрятывания'' защищаемой информации внутри больших объемов информации, хранящейся в компьютере. Наглядный пример запрятывания текстового файла в графический можно найти в Интернете1); он же приведен в журнале ``Компьютерра'', # 48 (225) от 1 декабря 1997 г., на стр. 62. (Следует отметить, что авторы статьи в журнале ошибочно относят стеганографию к криптографии. Конечно, с помощью стеганографии можно прятать и предварительно зашифрованные тексты, но, вообще говоря, стеганография и криптография - принципиально различные направления в теории и практике защиты информации.)
В теоретической криптографии существуют два основных подхода к определению стойкости криптосистем и криптографических протоколов (в дальнейшем мы будем также использовать общий термин - криптографические схемы): теоретико-информационный и теоретико-сложностной. Теоретико-информационный подход предполагает, что противник, атакующий криптографическую схему, не имеет даже теоретической возможности получить информацию, достаточную для осуществления своих целей. Классическим примером здесь может служить с одноразовыми ключами, абсолютно стойкий против пассивного противника.
Подавляющее большинство используемых на практике криптографических схем не обладает столь высокой стойкостью. Более того, обычно бывает несложно указать алгоритм, который выполняет стоящую перед противником задачу, но не практически, а в принципе. Рассмотрим следующий пример.
Пример 1. (Криптосистема с открытым ключом)
полностью определяется тремя алгоритмами: генерации ключей, шифрования и дешифрования. Алгоритм генерации ключей
общедоступен; всякий желающий может подать ему на вход случайную строку надлежащей длины и получить пару ключей . Открытый ключ публикуется, а секретный ключ и случайная строка хранятся в секрете. Алгоритмы шифрования и дешифрования таковы, что если - пара ключей, сгенерированная алгоритмом , то для любого открытого текста . Для простоты изложения предполагаем, что открытый текст и криптограмма имеют одинаковую длину . Кроме того, считаем, что открытый текст, криптограмма и оба ключа являются строками в двоичном алфавите.
Предположим теперь, что противник атакует эту криптосистему. Ему известен открытый ключ , но неизвестен соответствующий секретный ключ . Противник перехватил криптограмму и пытается найти сообщение , где . Поскольку алгоритм шифрования общеизвестен, противник может просто последовательно перебрать все возможные сообщения длины , вычислить для каждого такого сообщения криптограмму и сравнить с . То сообщение, для которого , и будет искомым открытым текстом. Если повезет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка , где - время, требуемое для вычисления функции от сообщений длины . Если сообщения имеют длину порядка 1000 битов, то такой перебор неосуществим на практике ни на каких самых мощных компьютерах.
Математическая криптография возникла как наука о шифровании информации, т.е. как наука о криптосистемах. В классической шенноновской модели системы секретной связи имеются два полностью доверяющих друг другу участника, которым необходимо передавать между собой информацию, не предназначенную для третьих лиц. Такая информация называется конфиденциальной или секретной. Возникает задача обеспечения конфиденциальности, т.е. защиты секретной информации от внешнего противника. Эта задача, по крайней мере исторически, - первая задача криптографии. Она традиционно решается с помощью криптосистем.
Представим теперь себе следующую ситуацию. Имеются два абонента и сети связи, скажем, компьютерной сети. - это банк, в котором у имеется счет и хочет переслать по сети в электронной форме платежное поручение перевести, например, 10 фантиков со своего счета на счет другого клиента . Нужна ли в данном случае криптографическая защита? Предлагаем читателю самостоятельно поразмышлять и убедиться, что такая защита и в самом деле необходима. Но здесь следует отметить следующий очень важный момент: у и нет никакой конфиденциальной информации. В самом деле, клиенты пересылают банку в качестве сообщений платежные поручения, содержание которых стандартно и общеизвестно. Для банка важно убедиться в том, что данное сообщение действительно исходит от , а последнему, в свою очередь, необходимо, чтобы никто не мог изменить сумму, указанную в платежном поручении, или просто послать поддельное поручение от его имени. Иными словами, требуется гарантия поступления сообщений из достоверного источника и в неискаженном виде. Такая гарантия называется обеспечением целостности информации и составляет вторую задачу криптографии.
Нетрудно видеть, что при пересылке платежных поручений в электронной форме возникает еще и совершенно иной тип угроз безопасности клиентов: всякий, кто перехватит сообщение от к , узнает, что получил от 10 фантиков. А что будет, если эта информация попадет в руки мафии? Возможно, кто-то из читателей скажет, что здесь как раз и требуется конфиденциальность. И будет неправ! На самом деле клиентам необходимо нечто, аналогичное свойству анонимности обычных бумажных денег. Хотя каждая бумажная купюра имеет уникальный номер, определить, кто ее использовал и в каких платежах, практически невозможно. Аналог этого свойства в криптографии называется неотслеживаемостью. Обеспечение неотслеживаемости - третья задача криптографии.
Вопрос ``как сосчитать?'' всегда сопутствовал теоретико-числовым исследованиям. Труды Евклида и Диофанта, Ферма и Эйлера, Гаусса, Чебышева и Эрмита содержат остроумные и весьма эффективные алгоритмы решения диофантовых уравнений, выяснения разрешимости сравнений, построения больших по тем временам простых чисел, нахождения наилучших приближений и т.д. Без преувеличения можно сказать, что вся теория чисел пронизана алгоритмами. В последние два десятилетия, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ, исследования по алгоритмическим вопросам теории чисел переживают период бурного и весьма плодотворного развития. Мы кратко затронем здесь лишь те алгоритмические аспекты теории чисел, которые связаны с криптографическими применениями.
Вычислительные машины и электронные средства связи проникли практически во все сферы человеческой деятельности. Немыслима без них и современная криптография. Шифрование и дешифрование текстов можно представлять себе как процессы переработки целых чисел при помощи ЭВМ, а способы, которыми выполняются эти операции, как некоторые функции, определенные на множестве целых чисел. Все это делает естественным появление в криптографии методов теории чисел. Кроме того, стойкость ряда современных криптосистем обосновывается только сложностью некоторых теоретико-числовых задач (см. []).
Но возможности ЭВМ имеют определенные границы. Приходится разбивать длинную цифровую последовательность на блоки ограниченной длины и шифровать каждый такой блок отдельно. Мы будем считать в дальнейшем, что все шифруемые целые числа неотрицательны и по величине меньше некоторого заданного (скажем, техническими ограничениями) числа . Таким же условиям будут удовлетворять и числа, получаемые в процессе шифрования. Это позволяет считать и те, и другие числа элементами кольца вычетов . Шифрующая функция при этом может рассматриваться как взаимнооднозначное отображение колец вычетов
а число представляет собой сообщение в зашифрованном виде.
Рассмотрим следующую, в наше время вполне реальную ситуацию. Два совладельца драгоценности хотят положить ее на хранение в сейф. Сейф современный, с цифровым замком на 16 цифр. Так как совладельцы не доверяют друг другу, то они хотят закрыть сейф таким образом, чтобы они могли открыть его вместе, но никак не порознь. Для этого они приглашают третье лицо, называемое дилером, которому они оба доверяют (например, потому что оно не получит больше доступ к сейфу). Дилер случайно выбирает 16 цифр в качестве ``ключа'', чтобы закрыть сейф, и затем сообщает первому совладельцу втайне от второго первые 8 цифр ``ключа'', а второму совладельцу втайне от первого - последние 8 цифр ``ключа''. Такой способ представляется с точки здравого смысла оптимальным, ведь каждый из совладельцев получил ``полключа'' и что может быть лучше?! Недостатком данного примера является то, что любой из совладельцев, оставшись наедине с сейфом, может за пару минут найти недостающие ``полключа'' с помощью несложного устройства, перебирающего ключи со скоростью 1МГц. Кажется, что единственный выход - в увеличении размера ``ключа'', скажем, вдвое. Но есть другой, математический выход, опровергающий (в данном случае - к счастью) соображения здравого смысла. А именно, дилер независимо выбирает две случайные последовательности по 16 цифр в каждой, сообщает каждому из совладельцев втайне от другого ``его'' последовательность, а в качестве ``ключа'', чтобы закрыть сейф, использует последовательность, полученную сложением по модулю 10 соответствующих цифр двух выбранных последовательностей. Довольно очевидно (и ниже мы это докажем), что для каждого из совладельцев все возможных ``ключей'' одинаково вероятны и остается только перебирать их, что потребует в среднем более полутора лет для устройства, перебирающего ключи со скоростью 100МГц.
И с математической, и с практической точки зрения неинтересно останавливаться на случае двух участников и следует рассмотреть общую ситуацию. Неформально говоря, ``схема, разделяющая секрет'' (СРС) позволяет ``распределить'' секрет между участниками таким образом, чтобы заранее заданные разрешенные множества участников могли однозначно восстановить секрет (совокупность этих множеств называется структурой доступа), а неразрешенные - не получали никакой дополнительной к имеющейся априорной информации о возможном значении секрета. СРС с последним свойством называются совершенными (и только они, как правило, рассматриваются в этой статье).
Если вы хотите передать свое текстовое сообщение (последовательность символов некоторого алфавита) адресату так, чтобы оно осталось тайным для посторонних лиц, то у вас есть, по крайней мере, две возможности. Вы можете попытаться скрыть сам факт передачи текста, то есть прибегнуть к методам , в арсенале которой - симпатические (невидимые) чернила, и тому подобные средства. Другая возможность заключается в попытке скрыть смысл сообщения от посторонних лиц, случайно или намеренно познакомившихся с передаваемым текстом. В этом случае вы можете прибегнуть к . Термин ``криптография'' происходит от двух греческих слов: ``криптос'' - тайна и ``графейн'' - писать, и означает тайнопись. ``Тайнопись'' как раз и подразумевает, что вы скрываете смысл своего сообщения.
Сообщение, которое вы хотите передать адресату, будем называть . Например, в задаче (раздел ``Условия задач'') одним из открытых сообщений является фраза:
КОРАБЛИ ОТХОДЯТ ВЕЧЕРОМ
Для сохранения сообщения в тайне оно преобразуется криптографическими методами и только после этого передается адресату. Преобразованное сообщение будем называть шифрованным сообщением (или зашифрованным сообщением). Другое название зашифрованного сообщения - криптограмма (или ). В задаче зашифрованное сообщение выглядит так:
ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ
Зашифрованное сообщение не обязательно должно быть последовательностью букв, как в указанной выше задаче. Часто зашифрованное сообщение может представлять собой последовательность цифр или специальных знаков (например, ).
Процесс преобразования открытого сообщения в шифрованное будем называть или зашифрованием. Адресату заранее сообщается, как из шифрованного сообщения получить открытое. Этот процесс получения исходного сообщения называют .
При выборе правила шифрования надо стремиться к тому, чтобы посторонние лица, не знающие правила расшифрования, не смогли восстановить по криптограмме открытое сообщение. В этом случае вы скроете смысл сообщения и обеспечите ``тайнопись''.
Рассмотрим вопросы, связанные с ``теоретической секретностью'' систем. Насколько устойчива некоторая система, если шифровальщик противника не ограничен временем и обладает всеми необходимыми средствами для анализа криптограмм? Имеет ли криптограмма единственное решение (даже если для нахождения этого решения может потребоваться такой объем работ, что его практически нельзя будет выполнить), а если нет, то сколько она имеет приемлемых решений? Какой объем текста, зашифрованного в данной системе, нужно перехватить для того, чтобы решение стало единственным? Существуют ли секретные системы, в которых вообще нельзя найти единственного решения независимо от того, каков объем перехваченного зашифрованного текста? Существуют ли секретные системы, в которых противник не получает никакой информации, сколько бы он ни перехватывал зашифрованного текста? В анализе этих вопросов найдут широкое применение понятия энтропии, избыточности, а также и другие понятия, введенные в работе ``Математическая теория связи''1).
Next: 10. Совершенная секретность
Up: Часть II. ТЕОРЕТИЧЕСКАЯ СЕКРЕТНОСТЬ
Previous: Часть II. ТЕОРЕТИЧЕСКАЯ СЕКРЕТНОСТЬ
Contents:
