Математика и секретная информация
Джорджевич Ирина Николаевна
Самым распространенным и любимым детским развлечением является игра в шпионов, в которой одним из действий является передача секретной информации. Разумеется, никакой угрозы детская забава в себе не несет, но в реальной жизни ситуации намного серьезнее, и секретная информация должна находиться под строгой защитой, дабы не попасть в чужие руки. Именно поэтому стало необходимым искать способы скрыть смысл передаваемых сообщений от посторонних любопытных глаз.
Наукой, занимающейся методами обеспечения конфиденциальности, или же искусством написания и вскрытия шифров является криптография.
Криптография появилась с возникновением самой письменности. Хотя египтяне и жители Месопотамии и использовали какие-то методы шифрования, серьезно занялись криптографией древние греки и римляне, будучи враждующими культурами, для которых тайное общение было ключевым элементом военных успехов. Императоры, торговцы, политики и шпионы также искали способы шифрования своих посланий. К тайнописи – криптографии прибегал Гай Юлий Цезарь, заменяя в своих тайных записях одни буквы другими.
Такая секретность привела к появлению нового типа соперников – криптографов («хранителей тайн») и криптоаналитиков (специалистов по взламыванию шифров).
В 8 веке арабский мудрец Аль-Кинди придумал метод дешифровки, известный как частотный криптоанализ, который вскрывал любое закодированное сообщение. Через несколько столетий от шифровальщиков последовал ответ – изобретение полиалфавитного шифра. Но и на это был придуман метод расшифровки. С тех пор главным оружием, применяемым каждой из сторон, была математика, от статистики и теории до модульной арифметики. Знания математики нужны для того, чтобы найти простую, но надежную систему кодирования, недоступную для расшифровки посторонним лицам, а также найти способы декодирования чужой системы тайнописи, чужих кодов. Например, механическая замена одних букв или чисел другими – подстановки Цезаря – достаточно легко поддается дешифровке. Причем сам процесс декодирования похож на решение неопределенных уравнений со многими неизвестными.
Переломный момент в битве кодирования и расшифровки наступил с появлением первых машин шифрования и, вскоре после этого, первых машин расшифровки. Первая программируемая вычислительная машина, названная Colossus, была создана британцами для взлома сообщений, закодированных немцами посредством их шифровальной машиной «Энигма».
Теория кодирования – довольно молодая наука. Исследование надежности кодов получило новый импульс после создания в 1948 г. Клодом Эльвудом Шенноном теории информации. Для создания кодов необходима система счисления - совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выбираются некоторые символы (слова или знаки), называемые базисными числами, а все остальные числа получаются в результате каких-либо операции из базисных чисел данной системы исчисления. Символы, используемые для записи чисел, могут быть любыми, только они должны быть разными и значение каждого из них должно быть известно.
Универсальной в современном обществе является двоичная система счисления, в которой используются всего лишь две цифры – 0 и 1.
Кодирование имеет значение не только в конспиративных целях для шифровки информации. Так, в математике с помощью кодирования изучение одних объектов заменяют изучением других, более доступных или уже известных. Ярким примером кодирования в математике является метод координат, введенный Декартом, который дает возможность изучать геометрические объекты через их аналитическое выражение в виде чисел, букв и их комбинаций – формул.
За последние годы математические методы защиты информации все шире входят в нашу жизнь и даже быт. Это и пароль при входе в компьютерную сеть, и режим шифрования при отправлении электронной почты, и проверка подлинности банковской карточки.
Первый этап разработки математических методов - построение математической модели той ситуации, в которой требуется обеспечить защиту информации.
На следующем этапе уже в зависимости от построенной модели разрабатываются соответствующие методы. Эти методы сильно отличаются друг от друга, что говорят даже о различных научных дисциплинах. Назовем некоторые из них: теория кодирования, методы разграничения доступа, компьютерная безопасность, стеганография, криптография. В каждой из этих дисциплин разрабатываются свои методы защиты информации и свои методы "взлома" этих методов, адекватные построенной математической модели.
Методы защиты и нападения связаны друг с другом - нельзя построить хорошую защиту, не зная возможных методов нападения; после появления новых методов защиты разрабатываются и соответствующие методы нападения.
Приведем несколько примеров того, как математика помогает защищать информацию.
Теория кодирования
Ситуацию, для которой разрабатываются методы теории кодирования, можно представить следующей схемой:
Главная особенность этой схемы - отсутствие противника. Передаваемую по каналу связи информацию надо защищать только от возможных естественных помех и искажений в канале связи. Конечно, при этом возникают различные ситуации в зависимости от качества канала связи и от требуемой скорости передачи информации.
Для решения различных задач теории кодирования разрабатываются различные коды, обнаруживающие или исправляющие ошибки. Простейшие коды - это код с повторением и код с проверкой четности.
Для построения кодов, обнаруживающих или исправляющих ошибки, используются методы теории чисел, теории конечных полей и других разделов современной математики.
Разграничение доступа
Ситуацию, для которой разрабатываются методы разграничения доступа, можно представить следующей схемой:
Среди пользователей информации могут быть и недобросовестные ("незаконопослушные"), которые стремятся прочитать или исказить "чужую" информацию. Но для защиты от действий таких пользователей в этой модели не рассматриваются методы преобразования самой хранимой информации (шифрование), а ограничиваются лишь построением системы паролей, которая разрешает пользователю работать только со "своей" информацией. Системы паролей хорошо известны любому, кто имеет дело с компьютером.
Стеганография
Ситуацию, для которой разрабатываются стеганографические методы передачи информации, можно представить следующей схемой:
В этой схеме участвует не противник, который стремится получить передаваемую информацию, а надсмотрщик, который пропускает по каналу связи только разрешенные сообщения и не пропускает подозрительные сообщения. (Термин "надсмотрщик" возник из задачи о двух заключенных, которые, сидя в тюрьме, могут, например, разрабатывать план побега.) Для этой ситуации строится стеганографический канал связи, в котором разрешенные сообщения используются в качестве контейнеров и в эти контейнеры упаковываются скрытые сообщения.
Термину "стеганография" уже более 500 лет - этим термином обозначались методы скрытия факта передачи сообщения. Из древности известен, например, такой стеганографический канал - голову раба брили, на коже головы писали сообщение и после отрастания волос раба отправляли к адресату. Из детективных произведений известен современный метод "микроточки": сообщение записывается с помощью современной техники на очень маленький носитель - "микроточку", которая пересылается с обычным письмом, например, под маркой или где-нибудь в другом заранее обусловленном месте. Математические методы стеганографии стали активно разрабатываться в последние годы для целей "запрятывания" защищаемой информации внутри больших объемов информации, хранящейся в компьютере и передаваемой по компьютерным сетям. Сейчас уже известны десятки примеров таких стеганографических каналов, но пока нет достаточно завершенных математических моделей стеганографии, которые позволили бы доказывать надежность этих каналов. Наиболее популярные идеи построения стеганографических каналов.
Визуальный контейнер. Для упаковки скрытого сообщения в картинку или в фотографию (в компьютере) можно использовать небольшие изменения яркости заранее обусловленных точек.
Звуковой контейнер. Для упаковки скрытого сообщения в запись концерта можно использовать изменения младших битов аудиосигнала. Хорошо известно, что такие изменения практически не отражаются на качестве звука и поэтому их трудно обнаружить.
Текстовый контейнер. Для упаковки скрытого сообщения в файл, приготовленный к печати на принтере, можно использовать небольшие изменения стандартов печати (расстояния между буквами, словами и строками, размеры букв, строк и др.).
Криптография
Ситуацию, для которой разрабатываются криптографические методы передачи информации, можно представить следующей схемой:
Недоступный для противника канал связи очень дорогой и медленный, поэтому партнеры используют его только для обмена ключами. С помощью ключа партнеры шифруют информацию, т. е. преобразуют ее по заранее выбранным правилам шифрования, и передают по каналу связи (общедоступному) шифрованную информацию. Получатель информации, зная ключ, делает обратное к шифрованию преобразование и восстанавливает из шифрованной информации переданное сообщение. Противник может перехватить шифрованную информацию, может как-то узнать правила шифрования, но, не зная ключа, не может извлечь из имеющихся у него сведений переданное сообщение. Здесь существенно подчеркнуть, что под словом "противник" подразумевается не любой противник, а только тот, чьи возможности и мощности имелись в виду при разработке системы шифрования. Против более мощного противника система шифрования может оказаться бессильной.
На протяжении многих веков криптография была окутана туманом легенд, поскольку шифры применялись, в основном, для защиты государственных, военных и других секретов. Криптография развивалась не как наука, а как искусство, свой след в истории криптографии оставили многие великие люди (шифр Цезаря, цифирь Петра Великого, решетка Кардано и др.). Понимание математического характера решаемых криптографией задач пришло только в середине XX века - после работ американского ученого К. Шеннона. В одной из работ ("Теория связи в секретных системах") К. Шеннон обобщил накопленный до него опыт разработки шифров и показал, что даже в сложных шифрах в качестве типичных компонентов можно выделить шифры замены, шифры перестановки или их сочетания.
В литературных произведениях, в которых герои сталкиваются с шифрованной перепиской, чаще всего описываются шифры замены (А. Конан Дойл, "Пляшущие человечки"; Э. По, "Золотой жук").
Шифры простой однобуквенной замены уже давно научились вскрывать по известному шифрованному тексту достаточной длины.
Однако более сложные шифры замены или комбинации шифров замены с другими шифрами продолжают с успехом применяться и в настоящее время.
Шифры перестановки. Как видно из самого названия, шифр перестановки осуществляет преобразование перестановки букв в открытом тексте. Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется (т. е. в нем переставляются буквы) независимо. Широкое распространение получили шифры перестановки, использующие какую-нибудь геометрическую фигуру. Например, можно взять прямоугольную таблицу, вписать в нее открытый текст "по строкам", а шифрованный текст считать с нее "по столбцам". Возможны и более хитрые способы (маршруты) вписывания и считывания. Часто используют прямоугольную таблицу (решетку) с вырезанными "окошками", в которые вписываются буквы, а потом таблица поворачивается на 90o и в окошки попадают другие, не заполненные клетки листа бумаги. "Окошки" подбирают так, чтобы после трех поворотов с переворачиванием и вписывания букв все клетки оказались заполненными. Пример такой решетки размера 6x10:
Получатель сообщения, имеющий точно такую же решетку, без труда прочитает исходный текст, наложив решетку на шифрованный текст по порядку четырьмя способами.
Разработчики шифров постоянно совершенствовали свои шифры, стремясь повысить их стойкость.
Стойкость конкретного шифра оценивается путем всевозможных попыток его вскрытия (атак на шифр) и зависит от квалификации криптоаналитиков, атакующих шифр. Такую процедуру называют проверкой стойкости, а стойкостью называют способность шифра противостоять всевозможным атакам на него.
Важнейшим для развития криптографии был результат К. Шеннона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст "объединяется" с полностью случайным ключом такой же длины. Сделать это необычайно трудно и дорого, а значит, оправдано только для особо важной и ценной информации.
Новые направления в криптографии
Решить проблему распределения ключей без использования дорогостоящего, недоступного для противника канала связи долгое время считалось невозможным. Но в 1976 году была опубликована работа американских ученых У. Диффи и М. Э. Хеллмана "Новые направления в криптографии", в которой был предложен принципиально новый способ решения этой проблемы. Идеи У. Диффи и М. Э. Хеллмана не только существенно изменили криптографию, но и привели к появлению и бурному развитию новых направлений в математике. Центральным понятием "новой криптографии" являются понятие односторонней функции.
Отметим, что односторонняя функция существенно отличается от функций, привычных со школьной скамьи, из-за ограничений на сложность ее вычисления и инвертирования. Вопрос о существовании односторонних функций пока открыт.
Еще одним новым понятием является понятие функции с секретом.
Вопрос о существовании функций с секретом тоже пока открыт. Наиболее известной и популярной из них является теоретико-числовая функция, на которой построен шифр RSA, - в ней используется трудная задача разложения большого числа на множители.
Применение функций с секретом в криптографии позволяет:
организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т. е. отказаться от секретных каналов связи для предварительного обмена ключами;
включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;
решать новые криптографические задачи, отличные от шифрования (электронная цифровая подпись и др.).
Традиционные шифры называют симметричными: в них ключ для шифрования и дешифрования один и тот же. Для асимметричных систем алгоритм шифрования общеизвестен, но восстановить по нему алгоритм дешифрования за полиномиальное время невозможно.
Функцию с секретом можно также использовать для цифровой подписи сообщений, которую невозможно подделать за полиномиальное время
Развитие и обобщение идей, использованных при построении схем цифровой подписи, привело к созданию большого нового направления теоретической криптографии - теории криптографических протоколов. Объектом изучения этой теории являются удаленные абоненты, взаимодействующие, как правило, по открытым каналам связи.
Дальнейшее развитие теории криптографических протоколов стимулируется их многочисленными практическими приложениями, особенно в банковских платежных системах, в системах электронного документооборота, в компьютерных сетях и т. д. Осмысление различных протоколов и методов их построения привело в 1985-1986 гг. к появлению двух плодотворных математических моделей - интерактивной системы доказательства и доказательства с нулевым разглашением.
Литература:
В. В. Ященко, Математика и информация, Источник: сайт Cryptography.Ru
