Шифрование как метод скрытия содержимого сообщения
Перейти к содержимому

Шифрование как метод скрытия содержимого сообщения

  • автор:

Шифрование как метод скрытия содержимого сообщения

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

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

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

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

Один из самых известных методов шифрования является метод Цезаря, который римский император если и не изобрел, то, по крайней мере, активно им пользовался. Не имея доверия к своим посыльным, он шифровал письма элементарной заменой А на D, В на Е и так далее по латинскому алфавиту. К примеру, при таком кодировании последовательность ABC была бы записана как DEF.

Спустя пол века шифрование стало использоваться уже повсеместно при составлении текстов религиозного содержания, молитв и важных государственных документов.

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

Основные термины и определения криптографии

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

Некоторые основные понятия и определения.

Алфавит — законченное множество используемых для кодирования информации символов.

Текст — упорядоченный последовательность из символов алфавита.

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

  • алфавит Z33 — 32 буквы русского алфавита и пробел;
  • алфавит Z256 — символы, входящие в стандартные кодировки ASCII и КОИ-8;
  • бинарный алфавит — Z2 = ;
  • восьмеричный алфавит или шестнадцатеричный алфавит;

Шифрование — процесс преобразования исходного текста (который носит также название открытого текста) в зашифрованный.

Дешифрование — обратный шифрованию процесс. На основе ключа зашифрованный текст преобразуется в исходный.

Ключ — информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляет собой семейство T преобразований открытого текста. Составные этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K — это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптографичекие системы делят на симметричные и ассиметричные(шифрование с открытым ключом) .

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

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

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

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

Криптостойкостью является характеристика шифра, определяющая его стойкость к дешифрованию без наличия ключа (криптоанализу). Существует несколько факторов криптостойкости, например:

  • общее количество всех возможных ключей;
  • среднее время, необходимое для дешифрования сообщения.

Преобразование Tk определяется соответствующим алгоритмом и значением параметра k. Эффективность шифрования с целью защиты информации зависит от сохранения тайны ключа и криптостойкости шифра.

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

Для современных криптографических систем информационной безопасности определены следующие общие требования:

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

Шифрование файлов

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

Однако, многие могут возразить «а в чём же тогда эффективность и сложность шифрования?» А вот в подборе алгоритма она и заключена. На данный момент существует огромное количество систем шифрования и шифров. И каждый из них необычайно эффективен и сложен в определённой мере. Однако все они классифицируются по двум основным категориям: симметричные и ассиметричные шифры. Дальше речь пойдёт именно о них. И уже разбирая пример, мы покажем, что такое шифрование данных.

Симметричные шифры

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

Ассиметричные шифры

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

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

Программы, обеспечивающие шифрование и скрытие данных под паролем

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

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

Hide Folder

Пользовательский интерфейс программы HideFolder

Простая программа с многолетней историей. Она позволяет скрывать папки и файлы в них от посторонних глаз. Для доступа к самой программе нужно знать пароль пользователя. Реализовано просто и со вкусом, один из редких случаев, когда краткость сестра таланта. Не обеспечивает шифрования данных, но вот спрятать от ребёнка коллекцию непристойных фото позволит.

Как можно увидеть на изображении, интерфейс программы прост и интуитивно понятен. Добавляем файл, выбираем, что нам нужно – спрятать его или открыть к нему доступ, после чего он пропадает или отображается через проводник или любой файловый менеджер. Можно убрать файл из списка скрываемых файлов или сменить пароль. Важно, что пароль выбирается для входа в программу, что ставит под вопрос её надёжность.

Files Cipher

Пользовательский интерфейс программы FilesCipher

Более сложная программа, которая уже производит шифрование файла. Выполнена довольно понятно – выбрали файл, ввели ключ к нему и таким образом… а вот тут и первый недостаток. Алгоритм, который использует программа, разработан специально для неё и сложно поверить в то, что он действительно эффективен. Однако на помощь приходит огромный размер ключа (от 4 до 255 символов). Также стоит отметить, что этот ключ не шифруется вместе с файлом, а значит, повышает надёжность шифра. Расшифровать файл можно только при наличии этой программы, и зная пароль, другие способы займут огромное количество времени.

Как можно заметить, при взгляде на интерфейс программы в ней также имеется возможность архивирования файлов. Архивирование происходит с всё тем же паролем, и архив остается, защищён им. Несложно понять, что данная программа довольно хороша для работы с файлами и отдельными папками, для повышения безопасности собственного ПК.

TrueCrypt

Пользовательский интерфейс программы TrueCrypt

Еще более сложная программа из числа программ для шифрования данных. Её отличительной чертой является не удобный интерфейс и не бесплатность, а многофункциональность. В пределах этой программы реализована львиная доля существующих на сегодня криптографических систем (методов шифрования). В последних версиях программы можно встретить алгоритмы начиная с банальной Перестановки символов и заканчивая сложнейшими AES и ГОСТ 28147-89.

Вторым достоянием программы является наличие режима Portable, который позволяет установить её на флеш-накопитель и использовать для безопасного переноса данных с одного компьютера на другой. Также эта программа отличается бесплатным пользованием и наличием русскоязычного интерфейса. Помимо прочего позволяет надёжно зашифровывать как отдельные файлы и папки, так и целые локальные диски. Зашифрованным файлам присваивается характерное расширение, после чего попытки открыть их не принесут успеха (блокнот выдаёт жуткую кашу, а WINRar и аналоги не признают файл архивом).

File Vault

Пользовательский интерфейс программы FileVault

Не так давно MAC OS стала дополняться специальным плагином FileVault (с английского – Хранилище файлов), позволяющим зашифровать любую часть жёсткого диска, а то и вовсе весь диск. Работает данная штука довольно просто, интегрирована в ядро ОС и производит шифрование/дешифрование в фоновом режиме, практически не загружая систему и позволяя при этом спокойно заниматься своими делами.

Для произведения шифрования данных необходимо, прежде всего включить плагин, что можно сделать зайдя в меню и выбрав пункты Системные настройки –> Безопасность ( System preferences -> Security). После этого нам предлагается ввести мастер-пароль, который позволяет разблокировать любую шифровку (полезно, если вы, например, забыли пароль от зашифрованной информации). Стоит заранее заметить, что если вы не сможете вспомнить мастер-пароль и при этом забыли пароль от шифротекста, то тогда с данными предстоит распрощаться, восстановить их как-то иначе не представляется возможным.

Собственно шифрование и алгоритм работы весьма эффективен и привязан к текущему пользователю. Зайдя под другой учётной записью, даже с правами администратора, невозможно пробиться к нужным файлам – доступа не будет вообще. Да и найти этот диск каким-либо другим хитрым способом тоже невозможно, поэтому на сегодняшний день это лучший способ хранения личных данных на собственном ПК!

Шифрование в VPN-соединениях

Нельзя не упомянуть, что соединение через Частную виртуальную сеть (VPN) также обеспечивает шифрование данных. Не на всём пути их следования, а только между VPN-сервером и клиентом, но и это является безусловным плюсом и мощным инструментом по защите данных. Шифрование в VPN всецело зависит от поставщика, некоторые предоставляют довольно посредственное шифрование, некоторые хитро сплетают использование разных протоколов (например, VPN и IPSec) получая в таком случае огромнейший уровень защиты данных, а есть и такие, которые просто пренебрегают возможностью шифрования в VPN соединении.

Смысл шифрования в целом

Если рассмотреть комплексно, то само по себе шифрование отличное средство по защите информации, на подбор шифра, ключа и на взлом может уйти время равное то дням, то тысячелетиям. Но важно помнить о важнейшей вещи, которая сопровождает любую криптографическую систему (систему шифрования) – неосторожное обращение с ключами всегда приводит к взлому. Чем меньше людей знают пароль к данным, тем меньше шансы взломать шифротекст (текст, полученный в результате шифрования). Всегда люди являются основным источником при взломе тех или иных паролей, а знание пароля и вида шифрования позволяет произвести взлом быстрее. Но если взять идеальную ситуацию, когда пароль не разглашается, будем честны, такое бывает редко, то сроки взлома шифротекста порой бывают колоссальными, даже на лучшем оборудовании. Даже слегка устаревший AES (без цифр в названии) позволяет зашифровать текст на малом пароле (4 символа) так, что подбор и аналитические методы решения позволят разобрать исходный текст не ранее чем через 10 лет. Стоит ли говорить что-нибудь о более сложных системах. Но в тоже время важно отметить, что взломщик знающий тип шифрования и пароль разберёт текст за считанные минуты и все труды по шифрованию пойдут прахом.

А еще есть довольно хитрый способ, когда поверх одного шифрования происходит другое и замыкается третьим. Такое обычно происходит при работе с защищёнными соединениями через VPN, по самым скромным прикидкам в слабозащищённой сети пароль от учётной записи автора на одном из ресурсов при транспортировке был зашифрован 5 раз. То есть, как мы понимаем, даже при всех наших стараниях сделать что-то не так, порой оборудование и ОС «думают о нас» на всякий случай лишний раз, защищая наши данные, просто не стоит мешать им.

VMath

Для понимания материалов настоящего раздела крайне желательно ознакомиться с разделом ☞ МОДУЛЯРНАЯ АРИФМЕТИКА.

Криптография

Как сохранить информацию в тайне?

Как передать информацию адресату в тайне от других?

Этим проблемам информационной безопасности насчитывается несколько тысяч лет.

Способы решения этих проблем можно условно разбить на три группы:

1. cоздание абсолютно надежного хранилища или недоступного для других канала связи между абонентами;

2. маскировка или скрытие фактов наличия информации или ее передачи по общедоступному каналу связи;

Разработкой средств и методов скрытия факта передачи сообщения (тайнописи) занимается стеганография 1) .

Историческая справка. Первые с леды стеганографических м етодов теряются в глуб о кой древнос т и.

Греку Гистиею, жившему при дво р е персидского царя Дари я , нужно было переслать важное сообщение своему родс т веннику — тирану Милета Аристагору. Гистией не мог послать письмо: его бы перехватили по дороге. Тогда он обрил голову своего в ерного раба, наколол на голой коже его черепа сообщение татуировкой и подождал пока отра с тут волосы. После этого послал раба в Милет. По прибытии раб склонился перед Аристагором и сказал: «Обрей меня». Сд е лав это, Аристагор прочитал: «Восставай».

Из детективов из в естны различные способы тайноп и си меж д у строк обычного, незащищаемого текста: молоком — с нагреванием письма получателем (см. ☞ milk.doc) или специальными химическими составами, предполагающими более сложную обработку после доставки. Оп я ть же из детективов известен метод микроточки: с помощью современной т ехники сообщение за н осится на очень маленький носит е ль ( м икроточку), который пересылается обычным письмом, н апример, под марк о й или в каком-нибудь дру г ом, предвар и тельно обусловленном мест е .

Хорошая обзорная статья по современным методам стеганографии ☞ [1].

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

Криптография 2) — наука о способах преобразования (шифрования) информации с целью обеспечения ее конфиденциальности: защиты ее от несанкционированного доступа.

Что общего у криптографии с деревом кедр ?

ИСТОРИЯ. КРИПТОГРАФИЯ С СЕКРЕТНЫМ КЛЮЧОМ

Истоки криптографии также можно найти в глубокой древности [2]. Шифры создавали многие — ученые, дипломаты, cвященнослужители, пираты, военные и, разумеется, разведчики. Приведем примеры нескольких классических шифров, интересных и с методической точки зрения. По ходу изложения будем вводить и терминологию.

Открытым текстом будем называть сообщение, которое подлежит шифрованию, а результат применения к нему алгоритма шифрования будем называть шифровкой. Будем обозначать элемент открытого текста через $ x_<> $, а шифровки — через 3) $ c_<> $.

Шифр Цезаря

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

a б в г ь э ю я
$ \downarrow $ $ \downarrow $ $ \downarrow $ $ \downarrow $ $ \downarrow $ $ \downarrow $ $ \downarrow $ $ \downarrow $
г д е ё я а б в

Если закодировать буквы русского алфавита числами в десятичном представлении:

a б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

то шифр Цезаря можно представить в виде функции $$x \mapsto c=x+3 \pmod \ , $$ где $ x_<> $ — номер буквы открытого текста в алфавите. Здесь число $ 3_<> $ указывает величину сдвига алфавита; понятно, что она могла быть выбранной любой: $$x \mapsto c=x+k \pmod \ , $$ лишь бы только число $ k\in \ $ было известно адресату. Дешифрование им полученного текста производится «сдвигом» в противоположную сторону: $$ x=c — k \pmod \ \iff \ x = c + (33-k) \pmod . $$ Здесь $ c $ означает номер буквы шифровки в алфавите. ♦

Шифр Цезаря относится к классу шифров замены. Тривиальный шифр замены:

буква $ \mapsto $ произвольный (фиксированный) символ

«взламывается» частотным анализом достаточно длинного шифрованного сообщения. Известна [7]

Частота встречаемости букв в обычном (неспециальном) тексте (без учета пробелов):

a б в г д е,ё ж з и й к л м н о п р с т
0.075 0.017 0.046 0.016 0.03 0.087 0.009 0.018 0.075 0.012 0.034 0.042 0.031 0.065 0.110 0.028 0.048 0.055 0.065
у ф х ц ч ш щ ъ,ь ы э ю я
0.025 0.002 0.011 0.005 0.015 0.007 0.004 0.017 0.019 0.003 0.007 0.022

Следовательно, имеет смысл посчитать количества совпадающих символов в шифровке и ранжировать полученное: наиболее часто встречаемый символ, скорее всего, соответствует букве 5) о, следующий по частоте — возможно, букве е и т.д.

На всякий случай, я поставил собственный эксперимент, результаты которого можно посмотреть ☞ ЗДЕСЬ. Статистику для некоторых книг можно найти ☞ ЗДЕСЬ. Кажется, что при переходе от века XIX-го к XX-му частота встречаемости буквы а постепенно становится выше, чем е

NEGJVEGHJUHFVVBCNEBRKFDBFNEHFYTGJVJUFTN.

Открытый текст представляет собой фразу на русском языке.

Можно повысить безопасность шифра Цезаря, сделав величину $ k_<> $ контекстно зависимой, т.е. зависящей от места буквы в открытом тексте.

Шифр Виженера

как раз и реализует это. Для шифрования некоторого сообщения, например:

OБ АЛГЕБРАИЧЕСКИХ ПРЕОБРАЗОВАНИЯХ

выбираем произвольное сочетание букв, скажем, КРИПТО, которое предполагается секретным для всех, кроме адресата. Буква сообщения сдвигается по алфавиту на величину, равную порядковому номеру в алфавите соответствующей буквы секретного слова:

15 $ ^1 $ 0 $ ^ $ 3 $ ^5 $
О Б А Л Г Е Б Р А И Ч Е С К И Х П Р Е О Б Р А З О В А Н И Я Х
К Р И П Т О
11 $ ^ $ 9 $ ^ $ 19 $ ^ $
Щ С И Ы Х У
26 $ ^ $ 9 $ ^ $ 22 $ ^ $

Итак, первые 6 букв сообщения зашифрованы. Как поступить с оставшимися? Можно зашифровать их с помощью того же секретного слова:

1 $ ^ $ 0 $ ^9 $ 24 $ ^5 $ 18 $ ^ $ 9 $ ^ $ 16 $ ^ $ 5 $ ^ $ 1 $ ^ $ 0 $ ^8 $ 15 $ ^2 $ 0 $ ^ $ 9 $ ^ $ 22
О Б А Л Г Е Б Р А И Ч Е С К И Х П Р Е О Б Р А З О В А Н И Я Х открытый текст
К Р И П Т О К Р И П Т О К Р И П Т О К Р И П Т О К Р И П Т О К
11 $ ^ $ 9 $ ^ $ 19 $ ^ $ 11 $ ^ $ 9 $ ^ $ 19 $ ^ $ 11 $ ^ $ 9 $ ^ $ 19 $ ^ $ 11 $ ^ $ 9 $ ^ $ 19 $ ^ $ 11
Щ С И Ы Х У Л Б И Ш Й У Ь Ы С Е В Я П Я Й А Т Ц Щ Т И Э Ы Н А шифровка
12 $ ^ $ 9 $ ^ $ 43 $ ^ $ 29 $ ^ $ 18 $ ^ $ 35 $ ^ $ 16 $ ^ $ 10 $ ^ $ 19 $ ^ $ 26 $ ^ $ 9 $ ^ $ 28 $ ^ $ 33
$ ^ $ $ ^ $ $ ^ $ $ ^ $ $ ^ $ $ ^ $ $ ^ $

Аналитическое задание этого шифра: $$x_ \mapsto c_= x_+ \varepsilon_i \pmod \ , $$ где $ i\in \ \, , k\in \ $, а число $ \varepsilon_i $ определяется как номер $ i $-й буквы секретного слова в алфавите. Ту же формулу можно записать в еще более компактном виде $$x_i \mapsto c_= x_i + \varepsilon_> \pmod \ , \quad npu \quad i\in \ \ . $$ Для дешифрования получателю достаточно применить обратное преобразование: $$x_=c_ — \varepsilon_i \pmod \ \iff \ x_=c_+ (33- \varepsilon_i) \pmod \ ,$$ т.е. ему необходимо знать либо секретное шифрующее слово, либо же дешифрующее слово, образованное как раз из букв, соответствующих числам $ 33- \varepsilon_i $, т.е. ХПЧРНС:

26 $ ^ $ 9 $ ^ $ 22 $ ^ $ 12 $ ^ $ 9 $ ^ $ 43 $ ^ $ 29 $ ^ $ 18 $ ^ $ 35 $ ^ $ 16 $ ^ $ 10 $ ^ $ 19 $ ^ $ 26 $ ^ $ 9 $ ^ $ 28 $ ^ $ 33
Щ С И Ы Х У Л Б И Ш Й У Ь Ы С Е В Я П Я Й А Т Ц Щ Т И Э Ы Н А
Х П Ч Р Н С Х П Ч Р Н С Х П Ч Р Н С Х П Ч Р Н С Х П Ч Р Н С Х
22 $ ^ $ 24 $ ^ $ 14 $ ^ $ 22 $ ^ $ 24 $ ^ $ 14 $ ^ $ 22 $ ^ $ 24 $ ^ $ 14 $ ^ $ 22 $ ^ $ 24 $ ^ $ 14 $ ^ $ 22 $ ^ $ 24 $ ^ $ 14 $ ^ $ 22
О Б А Л Г Е Б Р А И Ч Е С К И Х П Р Е О Б Р А З О В А Н И Я Х
15 $ ^1 $ 0 $ ^ $ 3 $ ^5 $ 1 $ ^ $ 0 $ ^9 $ 24 $ ^5 $ 18 $ ^ $ 9 $ ^ $ 16 $ ^ $ 5 $ ^ $ 1 $ ^ $ 0 $ ^8 $ 15 $ ^2 $ 0 $ ^ $ 9 $ ^ $ 22

Фактически шифр Цезаря является вырожденным, частным случаем шифра Виженера, когда секретное слово тривиально состоит из одной только буквы г. Другая крайность заключается в использовании достаточно длинной секретной фразы:

1 $ ^ $ 0 $ ^9 $ 24 $ ^5 $ 18 $ ^ $ 9 $ ^ $ 16 $ ^ $ 5 $ ^ $ 1 $ ^ $ 0 $ ^8 $ 15 $ ^2 $ 0 $ ^ $ 9 $ ^ $ 22
О Б А Л Г Е Б Р А И Ч Е С К И Х П Р Е О Б Р А З О В А Н И Я Х
К Р И П Т О Г Р А Ф И Я Д О Л Ж Н А Б Ы Т Ь Э К О Н О М Н О Й секретная фраза
3 $ ^ $ 0 $ ^ $ 9 $ ^ $ 4 $ ^ $ 12 $ ^ $ 14 $ ^ $ 1 $ ^ $ 19 $ ^ $ 30 $ ^ $ 15 $ ^ $ 15 $ ^ $ 14 $ ^ $ 10
Щ С И Ы Х У Д Б А Э А Д Х Щ Ф Ь Э Р Ё Й У М Э Т Э П О Ъ Ц Н Я шифровка
4 $ ^1 $ 0 $ ^ $ 0 $ ^4 $ 22 $ ^ $ 21 $ ^ $ 30 $ ^ $ 6 $ ^ $ 20 $ ^ $ 30 $ ^ $ 30 $ ^ $ 15 $ ^ $ 23 $ ^ $ 32

А для шифрования длинного сообщения можно взять отрывок из какой-нибудь книги. Понятно, что законный получатель шифровки должен знать и книгу, и место, с которого ему надо осуществить «привязку» отрывка текста к шифровке. И хотя такой подход кажется очень трудоемким, не будем отметать его сходу… ♦

Шифр Кардано

приписывается итальянскому математику, астрологу, медику и мистику Кардано 6) . Шифр можно рассматривать как вариант шифра Виженера, и начальная стадия у них одинакова: первые буквы отрытого текста шифруются с помощью секретного слова. Остроумие идеи Кардано заключается в том, что шифрование оставшейся части текста осуществляется с помощью самого этого текста:

15 $ ^1 $ 0 $ ^ $ 3 $ ^5 $ 1 $ ^ $ 0 $ ^9 $ 24 $ ^5 $ 18 $ ^ $ 9 $ ^ $ 16 $ ^ $ 5 $ ^ $ 1 $ ^ $ 0 $ ^8 $ 15 $ ^2 $ 0 $ ^ $ 9 $ ^ $ 22
О Б А Л Г Е Б Р А И Ч Е С К И Х П Р Е О Б Р А З О В А Н И Я Х открытый текст
К Р И П Т О О Б А Л Г Е Б Р А И Ч Е С К И Х П Р Е О Б Р А З О секретное слово & открытый текст
15 $ ^1 $ 0 $ ^ $ 3 $ ^5 $ 1 $ ^ $ 0 $ ^9 $ 24 $ ^5 $ 18 $ ^ $ 9 $ ^ $ 16 $ ^ $ 5 $ ^ $ 1 $ ^ $ 0 $ ^8 $ 15
Щ С И Ы Х У П С А Ф Ъ Й Т Ы И Ю Ж Х Ц Щ Й Ё П Ш У Р Б Ю И Ж Д шифровка
16 $ ^ $ 0 $ ^ $ 27 $ ^ $ 19 $ ^ $ 9 $ ^ $ 7 $ ^ $ 23 $ ^ $ 10 $ ^ $ 16 $ ^ $ 20 $ ^ $ 1 $ ^ $ 9 $ ^ $ 4

В самом деле, только зная секретное слово КРИПТО можно восстановить первые $ 6_<> $ букв сообщения, с их помощью можно восстановить следующие $ 6_<> $ букв и т.д. ♦

Под ключом в криптографии понимают сменный элемент шифра, который применяется для шифрования или дешифрования конкретного сообщения.

Например, в шифре Цезаря ключом является $ k_<> $ — величина сдвига алфавита, в шифре Виженера — секретное слово или фраза.

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

буква $ \mapsto $ символ (совокупность символов)

называется кодированием. С формальной точки зрения кодирование можно рассматривать как частный случай шифрования (см. шифр замены ). Однако в современной криптографической литературе эти две операции принято различать по целям их применения: шифрование предназначено для скрытия информации, в то время как кодирование — для удобства ее хранения и передачи. Например, для передачи информации по каналу связи, подверженному воздействию помех (шумов), используются коды, исправляющие ошибки, когда символы сообщения представляются такими цепочками битов, чтобы «порча» любого бита (или фиксированного числа битов) при передаче не помешала получателю однозначно восстановить (декодировать) передаваемый символ.

В дальнейшем мы будем часто использовать кодировку, которую назовем стандартной:

а б в г д е,ё ж з и й к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
пробел
00

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

Шифр Вернама («одноразового блокнота»)

Вернам предложил использовать для шифрования преобразование $$ x_i \mapsto c_i=x_i + \varepsilon_ \pmod \ ,$$ где $ x_i $ представляет бит открытого текста, а $ \varepsilon_ $ — бит ключа; при этом последовательность битов ключа формируется случайным образом. Будем использовать обозначение $ \oplus $ для операции побитного сложения по модулю $ 2_<> $ чисел, представленных в двоичной системе счисления (XOR): если $ A=\underline<<\mathfrak a>_1<\mathfrak a>_2 \dots <\mathfrak a>_s <\mathfrak a>_> $ и $ B=\underline<<\mathfrak b>_1<\mathfrak b>_2 \dots <\mathfrak b>_s <\mathfrak b>_> $ два числа, представленных в такой системе, то $$A\oplus B = \underline<<\mathfrak c>_1<\mathfrak c>_2 \dots <\mathfrak c>_s <\mathfrak c>_> \ , npu \ <\mathfrak c>_j = <\mathfrak a>_j + <\mathfrak b>_j \pmod \ . $$ Таким образом: $$ 0 \oplus 0 = 0,\ 0 \oplus 1 = 1 \oplus 0 =1, \ 1 \oplus 1 = 0 \ , $$ и

0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 открытый текст
1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 ключ
1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 шифровка

Законный адресат (получатель шифровки) должен иметь в своем распоряжении дубликат ключа, т.е. фактически ему должна быть заранее передана последовательность битов, не меньшая (по длине) возможной шифровки. Подобное решение проблемы конфидециальности переписки на первый взгляд кажется порочным кругом: для соблюдения секретности передаваемого сообщения необходимо предварительно передать корреспонденту по абсолютно надежному каналу ключ той же длины. Но противоречие это только кажущееся: на самом деле секрет «разделяется». Ключ передается корреспонденту с надежным курьером — например, с офицером дипломатической почты. После одноразового использования ключа для шифрования и дешифрования сообщения, ключ уничтожается. В случае перехвата курьера потенциальный противник получит в свое распоряжение лишь бессмысленный набор символов, и тогда ключ просто меняется на другой; опасность же возможного копирования ключа (посредством подкупа курьера) может быть заблокирована техническими средствами… Шифр «одноразового блокнота» считается абсолютно надежным, и, по некоторым данным, именно им до последнего времени обеспечивалась секретность канала «горячей линии» между Кремлем и Белым Домом.

Для шифра Вернама ключ дешифрования совпадает с ключом шифрования; так, для приведенного примера получаем:

1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 шифровка
1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 ключ
0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 открытый текст

Исторические заметки о Гильберте Вернаме ☞ ЗДЕСЬ.

Шифр скиталы

известен по крайней мере со времен Пелопоннесской войны (431-404 гг. до н.э.) Спарты потив Афин.

«Вот что такое скитала. Отправляя к месту службы начальника флота или сухопутного войска, эфоры берут две круглые палки совершенно одинаковой длины и толщины. Одну они оставляют себе, другую передают отъезжающему. Эти палки и называют скиталами. Когда эфорам нужно сообщить какую-нибудь важную тайну, они вырезают длинную и узкую, вроде ремня, полосу папируса, наматывают ее на свою скиталу, не оставляя на ней ни одного промежутка, так чтобы вся поверхность палки была охвачена этой полосой. Затем, оставляя папирус на скитале в том виде, как он есть, они пишут на нем то, что нужно, а написав, снимают полосу и без палки отправляют ее военачальнику.»

Источник. Плутарх. Избранные жизнеописания. Лисандр и Сулла.

Итак, скитала — цилиндрический жезл 7) . На него виток к витку наматывалась лента, на которую вдоль оси скиталы записывался открытый текст, например: ТРИСТАСПАРТАНЦЕВИДУТФЕРМОПИЛАМ. Лента разматывалась и получалось, что поперек нее в беспорядке написаны какие-то буквы, что-то наподобие

Эта лента отправлялась адресату.

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

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

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

Для удобства последующего анализа перепишем шифровку, повернув в ней буквы:

ТРИСТАСПАРТАНЦЕВИДУТФЕРМОПИЛАМ $ \mapsto $ ТССРНВУЕОЛРТПТЦИТРПАИАААЕДФМИМ.

К шифру перестановки можно отнести и анаграмму — слово (или словосочетание), образованное перестановкой букв другого слова (или словосочетания). Анаграммы использовались для образования псевдонимов:

ХАРИТОН МАКЕНТИН $ \mapsto $ АНТИОХ КАНТЕМИР 8) ;

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

CCEIIINOSSTTUV $ \mapsto $ UTTENSIOSICVIC 9) .

Cм. также анаграмму основной задачи дифференциального исчисления ☞ ЗДЕСЬ

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

$ ^ $ 1 $ ^ $ 3 $ ^ $ 5 $ ^ $ 7 $ ^ $ 9 $ ^ $ 11 $ ^ $ 13 $ ^ $ 15 $ ^ $ 17 $ ^ $ 19 $ ^ $ 21 $ ^ $ 23 $ ^ $ 25 $ ^ $ 27 $ ^ $ 29
Т Р И С Т А С П А Р Т А Н Ц Е В И Д У Т Ф Е Р М О П И Л А М
0 $ ^ $ 20 $ ^1 $ 11 $ ^ $ 2 $ ^ $ 22 $ ^3 $ 13 $ ^ $ 4 $ ^ $ 24 $ ^5 $ 15 $ ^ $ 6 $ ^ $ 26 $ ^7 $ 17 $ ^ $ 8 $ ^ $ 28 $ ^ $ 19 $ ^ $

Функция, задающая процедуру шифрования, может быть представлена в виде: $$ x \mapsto c=10\,x \pmod \ , $$ где $ x $ — место символа в открытом тексте. Исключением для этой формулы является последняя буква открытого текста М — она остается на месте. Ключом в шифре скиталы является ее диаметр, или — в переводе на язык цифр — сомножитель, на который надо умножить номер буквы в открытом тексте.

Построение обратной, т.е. дешифрующей, функции потребует уже некоторых усилий. Найдем число обратное числу $ 10_<> $ относительно умножения по модулю $ 29_<> $: $$3\times 10 = 30 \equiv 1 \pmod \ .$$ Тогда соотношение $ x \equiv 3\,c \pmod $ позволяет дешифровать полученную шифровку : буква Т, стоящая на нулевом месте в шифровке, останется на том же месте в открытом тексте; буква С, стоящая на $ 1 $-м месте шифровки, должна перейти на $ 3_<> $-е место в открытом, следующая буква С станет $ 6 $-й, и т.д., Ф ($ 26 $-я в шифровке) — $ 20_<> $-й (поскольку $ 3 \cdot 26 \equiv 20 \pmod $). Исключение составляет последняя буква шифровки М: вместо того, чтобы встать в начало открытого текста, она оставляется на месте.

Перехваченное сообщение английского резидента имеет вид:

ПОПЯДЕДРОЕЕГРББТИИЛМРОЕОУАТИЬЬВАЛНДУОНС

Дешифруйте его, если по оперативным данным известно, что в нем упоминается имя секретного агента: БОНД. Найдите функции шифрования и дешифрования.

Рассмотренные выше шифры можно комбинировать, строя из них новые. Так, например, очевидным обобщением шифров Цезаря и скиталы является аффинный 10) шифр, задаваемый функцией $$f(x)=\alpha\, x+\beta \pmod \quad npu \ 0\le \alpha, \beta < M\ u \ \operatorname(\alpha,M)=1 \ .$$ Последнее условие гарантирует существование и единственность решения сравнения $ \alpha\, x+\beta \equiv c \pmod $ во множестве $ \ $, т.е. возможность дешифрования сообщения.

Подведем некоторые итоги. С формальной точки зрения шифрование и дешифрование текстов можно представить себе как операции над целыми числами. Выделяется подходящий математический объект, с помощью которого происходит формализация процедуры шифрования, а именно класс вычетов $ \mathbb Z_M $ по некоторому модулю $ M_<> $; сама процедура шифрования сводится при этом к элементарной алгебраической операции $ f_<>(x) $ над $ x\in \mathbb Z_M $. Эта алгебраическая операция зависит от некоторого параметра — ключа, который предполагается неизвестным противнику. Проблема дешифрования сообщения $ c=f(x) $ заключается в решении уравнения относительно $ x\in \mathbb Z_M $, т.е. нахождении функции, обратной $ f_<>(x) $ по модулю $ M_<> $. Эта обратная функция ищется в том же классе, что и сама функция $ f_<>(x) $, меняется лишь величина ключа. По известному ключу шифрования ключ дешифрования устанавливается практически мгновенно.

Схема шифрования называется схемой симметричных ключей, если для любой соответствующей пары

ключ шифрования $ \leftrightarrow $ ключ дешифрования

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

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

КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ

А можно ли сконструировать функцию $ f_<>(x) $ так, чтобы нахождение дешифрующей функции представляло трудноразрешимую проблему даже при открытом ключе шифрования ?

Односторонняя функция

Рассмотрим некоторую функцию $ F(x)_<> $, определенную на множестве $ \mathbb A_<> $ и отображающую это множество во множество $ \mathbb B_<> $: $ F(x): \mathbb A \mapsto \mathbb B $. Мы не будем заранее предполагать что это отображение взаимно однозначно, поэтому в дальнейшем, говоря об обратимости $ F(x)_<> $, будем иметь в виду — в зависимости от контекста — либо задачу определения всех прообразов данного значения $ y\in \mathbb B $ этой функции, либо задачу нахождения какого-то одного из них. Иначе говоря, идет речь о поиске решений уравнения $ F(x)=y $ относительно $ x\in \mathbb A $ при заданном $ y \in \mathbb B $.

Функция $ F(x)_<> $ называется односторонней, если она обладает свойствами:

1. простоты вычисления: для $ \forall x\in \mathbb A $ значения $ F(x)_<> $ вычисляются просто;

2. сложности обращения : для практически всех значений $ y \in \mathbb B $ нахождение хотя бы одного прообраза представляет вычислительно крайне трудоемкую задачу.

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

Пример. Функция $ f(x) = 3^ \pmod $ отображает множество $ \mathbb A =\ $ в себя:

Односторонней функцией с лазейкой 11) называется односторонняя функция, обладающая еще и свойством

3. при некоторой дополнительной информации о $ F(x)_<> $, обращение этой функции становится простой задачей.

Для пояснения идеи снова обратимся к истории — для определенности до 1700 г. Противник ведет осаду неприступной крепости. Фортификационные особенности допускают единственную тактику приступа: штурмом мощно укрепленных ворот «в лоб». Однако имеется секретный лаз, ведущий из крепости к какому-то укромному месту за ее пределами — например, к реке. Через этот лаз любой защитник крепости может незаметно для осаждающих покинуть ее пределы. Напомним известную классическую сцену осады запорожцами польского города Дубно из повести Н.В.Гоголя «Тарас Бульба».

— Но как ты здесь? Как ты пришла?

— Разве есть подземный ход?

— Ты не выдашь, рыцарь?

— Клянусь крестом святым!

— Спустясь в яр и перейдя поток, там, где тростник.

— И выходит в самый город?

— Прямо к городскому монастырю.

— Идем, идем сейчас!

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

Пример. Найти отображение, обратное отображению

Решение. Нахождение значения $ f(x)_<> $ для заданного $ x_<> $ не представляет трудности: см. ☞ алгоритм «квадрирования-умножения». Таблица значений $$ \begin <|c|c|c|c|c|c|c|c|c|c|c|c|c|>\hline x&0&1&2&3&4&5&6&7&8&\dots &185&186 \\ \hline x^ \pmod &0&1&128&130&115&146&184&182&134&\dots &15&142 \\ \hline \end $$ демонстрирует, во-первых, взаимную однозначность отображения $ x \mapsto f(x) $ множества $ \mathbb A_<> $, и, во-вторых, хорошо организованную хаотичность перемешивания содержимого $ \mathbb A_<> $: близкие числа $ x_ $ отображаются, как правило, в далеко разнесенные $ f(x_j) $, так что практически для любого числа $ y\in \mathbb A $ визуальным наблюдением трудно определить, где искать его прообраз.

Является ли «случайная величина»

$$ \ \pmod\>_^ $$ равномерно распределенной на интервале $ [0, 186] $ ? Вычислить среднее значение и коэффициент корреляции Пирсона для выборок

$$ X=[0,1,\dots,186] \quad u \quad Y=\left[0^ \pmod,1^ \pmod,\dots,186^ \pmod\right] \, . $$

Вместе с тем, в настоящее время известен единственный универсальный алгоритм быстрого обращения степенной функции $ x^n \pmod $ — т.е. вычисления корня степени $ n_<> $ по модулю $ M_<> $ — и этот алгоритм предполагает знание канонического разложения $ M_<> $.

Так, обнаружив, что $ M=187=11 \cdot 17 $, мы, следуя рассуждениям из ☞ ПУНКТА, разобьем сравнение $$ x^7 \equiv y \pmod $$ на два по составляющим модуль множителям: $$ x^7 \equiv y \pmod \quad u \quad x^7 \equiv y \pmod \ . $$ Поскольку $ \operatorname(7,11-1)=1 $ и $ \operatorname(7,17-1)=1 $, то (см. ☞ теорему Эйлера ) каждое из этих сравнений имеет единственное решение во множествах $ \ $ и $ \ $ соответственно, и эти решения могут быть найдены по ☞ алгоритму решения двучленного сравнения: $$ \alpha_1=y^3 \pmod \ u \ \alpha_2 = y^7 \pmod \ . $$ Следовательно, и само сравнение $ x^7 \equiv y \pmod $ при любом $ y_<> $ имеет единственное решение среди чисел множества $ \mathbb A_<> $, и это решение удовлетворяет системе сравнений $$x \equiv \alpha_1 \pmod \ u \ x \equiv \alpha_2 \pmod .$$ С помощью китайской теоремы об остатках мы сможем найти это значение $ x_<> $. Можно получить (см. упражнение ☞ ЗДЕСЬ ) и аналитическое представление для $ x_<> $ как функции от $ y_<> $, т.е. искомой обратной функции для функции $ x^ \pmod $: $$ x=17^ y^3 +11^ y^7 \pmod = 34\, y^3 + 154\, y^7 \pmod \ .$$

Ответ. $ x=34\, y^3 + 154\, y^7 \pmod $.

В следующем пункте будет приведено более компактное представление для корня n-й степени из числа y по модулю $ M_<> $, равном произведению двух простых множителей: оказывается, что функция, обратная $ x^n \pmod $, может быть представлена также степенной функцией $ y^m \pmod $ при некотором $ m\in \mathbb N $. Очевидно, что показатель $ m_<> $ может тогда считаться ключом дешифрования. Пока же подчеркнем еще раз тот факт, что если модуль $ M_<> $ является произведением различных простых и достаточно больших (порядков $ 10^ $) множителей, и эти множители известны, то обращение функции $ f(x)=x^ \pmod $ не составит большой вычислительной трудности — хотя бы по алгоритму, использованному при решении предыдущего примера. Если же эти множители заранее не известны, то практически для всех значений $ y\in \ $ — даже с использованием современных вычислительных мощностей — крайне трудно решить сравнение $$y\equiv x^ \pmod $$ относительно $ x_<> $. Таким образом, структура канонического разложения $ M_<> $ оказывается секретной лазейкой для односторонней функции $ f(x)=x^ \pmod $.

Алгоритм RSA

Теперь осталось формализовать идею последнего примера и показать, как можно использовать одностороннюю функцию с лазейкой для решения проблемы шифрования. В качестве такой функции, действующей на множестве $ \mathbb A = \ $ , предлагается взять степенную $$ f(x)= x^ <\mathbf E>\pmod $$ при некотором фиксированном показателе $ \mathbf E $ и некотором составном модуле $ M_<> $. При определенных условиях на указанные числа эта функция взаимно-однозначно отображает множество $ \mathbb A_<> $ в себя и тогда ею можно шифровать закодированные открытые тексты: $$ x \mapsto c =x^ <\mathbf E>\pmod \quad npu \quad \forall x \in \mathbb A \ .$$ Дешифрование сообщения $ c=f(x) $ сводится к решению сравнения $$ x^ <\mathbf E>\equiv c \pmod \ , $$ которое имеет единственное решение $ x \in \mathbb A $.

Подчеркнем еще раз, принципиальной особенностью этого алгоритма шифрования является открытость ключа шифрования для любого желающего, т.е. пара $ M_<> $ и $ \mathbf E $ считается доступной даже для потенциального злоумышленника, стремящегося ознакомиться с перепиской между создателем (владельцем) ключа — и его «законным» корреспондентом. Любой желающий может зашифровать свой открытый текст нашим шифром. Но вот дешифровать чужой текст 12) , зашифрованный тем же шифром, ему будет весьма трудно, поскольку структура канонического разложения $ M_<> $ не известна никому кроме создателя ключа. Теперь осталось только выяснить как владельцу ключа воспользоваться этой информацией (секретной лазейкой) для того, чтобы дешифровать сообщение $ c_<> $, которое он получил от своего корреспондента (или любого желающего), зашифровавшего открытым ключом свое сообщение. В самом деле, создатель ключа шифрования должен же сам обладать ключом дешифрования!

построения ключей шифрования и дешифрования.

1. Случайным образом выбираются два достаточно больших простых числа $ p_1 $ и $ p_2 $ и вычисляется их произведение: $$M=p_1\cdot p_2 \ ;$$ число $ M_<> $ не скрывается (открыто), но его множители $ p_1,p_2 $ держатся в секрете.

2. Случайным образом выбирается достаточно большое число $ \mathbf D $, взаимно простое с $ (p_1-1)(p_2-1) = \phi(M) $ (здесь $ \phi(M) $ означает функцию Эйлера от числа $ M_<> $): $$\operatorname \left( \mathbf D, \phi(M) \right)=1 \ ; $$ число $ \mathbf D $ держится в секрете.

3. Вычисляется число $ \mathbf E $ обратное $ \mathbf D $ относительно умножения по модулю $ \phi(M) $: $$ \mathbf E \cdot \mathbf D \equiv 1 \pmod <\phi(M)>\ ; $$ число $ \mathbf E $ не скрывается (открыто).

Пара $ ( \mathbf E,M) $ составляет ключ шифрования , а пара $ (\mathbf D,M) $ — ключ дешифрования 13) .

Теорема. При числе $ \mathbf E $, выбранном по алгоритму RSA, сравнение

$$ x^ <\mathbf E>\equiv c \pmod $$ имеет единственное решение, которое может быть найдено по формуле $$ x=c^ <\mathbf D>\pmod \, .$$

Доказательство ☞ ЗДЕСЬ.

Ключ дешифрования неединствен! Во множестве чисел $ \ < 0,1,\dots,\phi(M)-1\>$, наряду с $ \mathbf D $ существует еще, по крайней мере, одно число $ \tilde <\mathbf D>$ такое, что $ x=c^<\tilde<\mathbf D>> \pmod $. Подробнее ☞ ЗДЕСЬ.

Показать, что число $ \mathbf E $, выбираемое по алгоритму RSA, не может быть четным.

Указать явное выражение $ \mathbf D $ через $ \mathbf E $ и функцию Эйлера

Показать, что при

$$ \operatorname ( p_1-1, 3)=\operatorname ( p_2-1, 3)=1 $$ ключу шифрования $ <\mathbf E>=3 $ соответствует ключ дешифрования, вычисляемый по формуле $$ <\mathbf D>=\phi (M)-\frac\left(\phi (M)-1 \right)\ . $$

Примеры

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

Пример 1. Резидент разведки хочет секретно переслать Центру сообщение, состоящее из одного слова РЯД. Опишем действия участников процесса.

1. Работа Центра. Случайным образом выбираются простые числа $ p_1 $ и $ p_2 $. Например: $$p_1=23,p_2=43 \quad \Rightarrow \quad M=989,\quad \phi (M)=(23-1)\times (43-1)=924 \ . $$ Далее случайным образом выбирается ключ дешифрования $ \mathbf D $ из единственного ограничения $ \operatorname (\mathbf D ,\phi (M))=1 $. Такому условию удовлетворяет, например, $ \mathbf D=47 $. В качестве ключа шифрования $ \mathbf E $ берется обратное числу $ \mathbf D $ относительно умножения по модулю $ \phi (M) $. Алгоритм, приведенный ☞ ЗДЕСЬ, даст $ \mathbf E=59 $. Ключ шифрования $ (\mathbf E,M) $ сообщается резиденту (возможно, и по открытому каналу связи — т.е. специальные меры его защиты не предпринимаются).

2. Работа резидента. Получив ключ шифрования (и удостоверившись, что этот ключ принадлежит, действительно, Центру), резидент сначала кодирует сообщение: $ x=173205 $. Далее он обращает внимание на то, что $ x>M $, и если он формально зашифрует открытый текст по схеме алгоритма RSA, т.е. $ x \mapsto c=x^ <\mathbf E>\pmod $, то восстановить открытый текст $ x_<> $ Центр не сможет. В самом деле, указанная схема эквивалентна $$ x \mapsto \left(x \pmod \right)^ <\mathbf E>\pmod M \ , $$ иначе говоря, Центр сможет восстановить только число $ x \pmod $, т.е. остаток от деления $ x_<> $ на $ M_<> $, а вовсе не исходное число $ x_<> $. Итак, резидент разбивает $ x_<> $ на блоки $ x_ $, по величине меньшие модуля $ M_<> $, которые и будет шифровать. Например: $$x=\big[ \underbrace_\big|\underbrace_ \big] \ .$$ Способы разбиения закодированного сообщения на блоки оговариваются заранее между Центром и резидентом.

3. Работа Центра. Получив шифровку и убедившись, что она пришла действительно от резидента, Центр разбивает ее на блоки, дешифрует известным ему ключом дешифрования $ (<\mathbf D>,M) $ (см. пункт 1 решения): $$818^ \equiv_> 173 \ , \quad 421^ \equiv_> 205 \ , $$ и декодирует текст.

Понятно, что если Центру надо послать ответ резиденту, то адресаты меняются ролями: у резидента имеется свой ключ шифрования $ (\tilde<\mathbf E>, \tilde M) $, который он выкладывает для открытого доступа и т.д. ♦

Теперь смоделируем поведение злоумышленника.

Пример 2. Шифровка разведчика

$$c=29002476253519483189074002430375 $$ зашифрована ключом $ \mathbf E=19, M=3233 $. Какие действия для дешифрования может предпринять контрразведчик, перехвативший сообщение?

Решение. По виду модуля контрразведчик может предположить, что шифруемые блоки имеют длину, не большую 4. Разбив шифровку на блоки именно такой длины: $ c=\big[c_1\big|c_2\big|\dots \big|c_8\big] $, он приступает к поиску ключа дешифрования $ \mathbf D $. Он может попытаться найти это число методом «грубой силы», т.е. последовательного перебора: поскольку открытый текст $ x_ $ совпадает с некоторой степенью числа $ c_ $ (по модулю $ M_<> $), то можно пытаться выявить осмысленный текст последовательным вычислением и декодированием блоков $$c_j \pmod, c_j^2 \pmod, c_j^3 \pmod,\dots $$ Можно прикинуть объем необходимых вычислений, посмотрев величину $ \mathbf D $, установленную ниже.

Для установления $ \mathbf D $ умный контрразведчик попытается решить сравнение $$ \mathbf E \cdot \mathbf D \equiv 1 \pmod <\phi(M)>\ , $$ но для этого необходимо сначала разложить $ M_<> $ на множители. В нашем примере это делается быстро: $ p_1=53,\, p_2=61 $ и, таким образом, $ \phi(M)=(p_1-1)(p_2-1)=3120 $. Теперь для решения сравнения $ 19 \cdot <\mathbf D>\equiv 1 \pmod $ вычисляются частные по алгоритму Евклида нахождения $ \operatorname (19,3120) $: $ q_1=164,q_2=4, q_3=1 $. По алгоритму нахождения обратного по модулю: $ \tilde u=-K(q_1,q_2,q_3)=-821 $; и, следовательно, число $ <\mathbf D>=3120-821=2299 $ является искомым ключом дешифрования. Далее — дело техники: $$2900^\equiv_> 1806,\ 2476^\equiv_> 1117,\ 2535^\equiv_> 619=0619, \dots $$ Декодировав открытый текст $$x=1806\ 1117\ 0619\ 1415\ 0600\ 1609\ 1829\ 1315 \ ,$$ контрразведчик узнает исключительно важную информацию… ♦

Теория вскрытия шифра очевидна. Обсудим теперь, какой из ее этапов окажется для противника наиболее трудозатратным. Для вычисления функции $ x^ <\mathbf E>$ достаточно знать числа $ \mathbf E $ и $ M_<> $ открытого ключа шифрования. А вот для вычисления обратной функции требуется знать секретное число $ \mathbf D $. Казалось бы, ничего не стоит, зная число $ M_<> $, разложить его на простые сомножители $ p_ $ и $ p_ $, вычислить затем $ \phi (M)=(p_1-1)(p_2-1) $ и, наконец, решив сравнение $ \mathbf E \cdot \mathbf D \equiv 1 \pmod <\phi(M)>$ относительно $ \mathbf D $ с помощью алгоритма, приведенного ☞ ЗДЕСЬ, восстановить ключ дешифрования. Все шаги этого алгоритма могут быть организованы достаточно быстро за исключением первого. Именно разложение $ M_<> $ на простые множители и составляет наиболее трудоемкую часть вычислений. Можно, разумеется, «просеять» $ M_<> $ сквозь решето Эратосфена, т.е. проверить его на делимость всеми простыми числами от 2 до $ \sqrt $. Используя оценку Чебышева для количества простых чисел в этом промежутке, находим, что при $ M_<> $, записываемом $ 100_<> $ десятичными цифрами, найдется не менее $ 8 \times 10^ $ простых чисел, на которые нам придется поделить. Трудно представить себе таблицу, содержащую все эти числа. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для факторизации числа $ M>10^ $ таким способом потребуется не менее $ 10^ $ лет.

Пример 3. Спецслужбой перехвачена шифровка террориста

$$ c= \ . $$ Известно, что сообщение состоит из одного блока, открытый текст закодирован стандартной кодировкой и зашифрован ключом $$<\mathbf E>=7,\ M=\underbrace>_\ . $$ За какое время спецслужба сможет дешифровать это сообщение, если в ее распоряжении имеется пакет компьютерной алгебры MAPLE V Release $ 12_<> $, установленный на ноутбуке с процессором Core 2 Duo 2 GHz , модель T5750, ОЗУ 2 Gb?

Решение. Программа разложит число $ M_<> $ в произведение двух простых чисел за 2.5 часа.

02 15 13 02 01 00 03 08 15 17 03 06 19 18 32 00 24 06 17 06 08 00 24 01 18
б о м б а в з о р в е т с я ч е р е з ч а с

Его содержание к моменту дешифрования уже потеряет актуальность… ♦

Последний пример и поясняет идеологию открытости ключа шифрования: зачем тратить дополнительные ресурсы на его сокрытие, если даже при его доступности взлом оказывается таким трудоемким делом!

Есть, разумеется, вероятность, что противник, перехвативший сообщение, оказывается исключительно везучим человеком — простым перебором чисел он случайно наткнется на ключ дешифрования $ <\mathbf D>$; случается также, что и обладатель ключа — невнимательный растяпа…

а) найти ключ дешифрования $ <\mathbf D>$ при ключе шифрования $ <\mathbf E>=43 $ (или $ <\mathbf E>=155 $);

б) закодировать сообщение «БУХ» стандартной кодировкой и зашифровать ключом $ <\mathbf E>=29 $.

…однако подобные случаи следует отнести к категории маловероятных: благодать и глупость — это дары Божие и, будучи таковыми, научному анализу не подлежат!

Пример 4. Для иллюстрации надежности RSA, авторы алгоритма в $ 1977 $г. закодировали 14) числом $ x_<> $ некоторую английскую фразу 15) и зашифровали ее ключом $ <\mathbf E>=9007 $,

$$ M= \ . $$ Здесь $ M_<> $ состоит из $ 129 $ знаков. Эти два числа и шифротекст $$ c= $$ были опубликованы известным американским популяризатором науки Мартином Гарднером [9]; дополнительно сообщалось, что $ M=p_1p_2 $, где $ p_ $ и $ p_ $ — простые числа, записываемые $ 64 $ и $ 65 $ десятичными знаками соответственно. Первому, кто дешифрует сообщение была обещана награда в $ 100_<> $ $ $ $ .

Эта история завершилась $ 17 $ лет спустя, в $ 1994 $ г., когда под руководством авторов проекта [10] число $ M_<> $ было факторизовано за $ 220 $ дней работы примерно $ 1600 $ компьютеров и $ 600 $ добровольцев, объединенных сетью Интернет. ♦

В конце 2009 г. группа немецких исследователей объявила о факторизации $ 232 $-значного числа из RSA challenge list; на эту работу было потрачено более двух лет. В настоящее время безопасными к использованию считаются ключи с размером модуля $ M_<> $ от $ 1024 $ бит ($ 309 $ десятичных знаков).

Подбор параметров и используемые алгоритмы

Как найти достаточно большие простые числа?

Действительно, стойкость алгоритма RSA основана на возможности выбора простых чисел, состоящих из не менее $ 100 $ десятичных знаков. Поиск таких чисел последовательным перебором всех нечетных, начиная с некоторого стартового, и последующим «просеиванием» через решето Эратосфена весьма затруднителен. (Известно, например, что для любого натурального $ k_<> $ существует такое натуральное число $ N_<> $, что все числа $ N+1,N+2,\dots,N+k $ будут составными; см. ☞ ЗДЕСЬ.) Проблему решают обходным маневром. Возможного кандидата на простое число подвергают испытанию серией однотипных и легко осуществимых тестов. Положительность результата хотя бы одного теста однозначно свидетельствует о том, что кандидат является числом составным; с другой стороны, отрицательный результат теста не дает абсолютной гарантии простоты кандидата, но свидетельствует о том, что вероятность его быть составным уменьшилась на определенную величину, скажем, в два раза. Тогда с увеличением количества отрицательных результатов все меньше шансов у испытуемого числа оказаться составным. Организовав серию испытаний из большого количества — например, $ 100 $ — тестов и получив все их результаты отрицательными, мы имеем право сказать, что кандидат является скорее всего («вроде бы») простым, с вероятностью не менее $$ (1-0.5^) \approx 99.\underbrace_ \% . $$

Алгоритмы подобных испытаний ☞ ЗДЕСЬ.

Алгоритм ЭльГамаля

Криптоанализ

Как только будет найден быстрый метод факторизации больших целых чисел или изобретен алгоритм решения сравнения $ x^ <\mathbf E>\equiv c \pmod $, не требующий предварительной факторизации модуля $ M_<> $, использование алгоритма RSA для целей криптографии потеряет смысл. Использование этого алгоритма основано на уверенности в том, что уж если за последние три века не было создано универсального способа факторизации, то трудно ожидать, что он будет придуман нашими современниками.

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

Подробнее об потенциальных угрозах взлома ключа или шифровки ☞ ЗДЕСЬ.

Цифровая подпись

Сама идея открытости ключа шифрования была революционной. Оказывается, однако, что ее можно использовать не только для решения задачи конфиденциальности переписки, но и для для другой проблемы — подтверждения авторства и неподдельности полученного сообщения. Грубо говоря, можно попробовать «привязать» автора сообщения к его ключу шифрования — хотя бы для того, чтобы иметь гарантию, что пришедшее какому-то адресату сообщение (даже открытое, нешифрованное) принадлежит именно законному отправителю, а не подменено «по пути».

Подробнее о проблеме подмены сообщения и о цифровой подписи ☞ ЗДЕСЬ.

Источники

[1]. Владимир Николаевич. Тайнопись. «Компьютерра» N 14-15 от 23 мая 2003. Текст ☞ ЗДЕСЬ

[2]. Жельников В. Криптография от папируса до компьютера. М.: АВР,1996.

[3]. Саломаа А. Криптография с открытым ключом. М., 1996.

[4]. Масленников М. Криптография и свобода. 2009 (?) Текст ☞ ЗДЕСЬ

[5]. Введение в криптографию. Под ред. В.В.Ященко. М., 1998.

[6]. Утешев А.Ю., Черкасов Т.М., Шапошников А.А. Цифры и шифры.СПб.: Изд-во СПбГУ, 2001.

[7]. Яглом А.М., Яглом И.М. Вероятность и информация. М. ГТТИ. 1957.

[8]. Menezes A.J., van Oorschot P.C., Vanstone P.C. Handbook of Applied Cryptography. CRC Press, 1996.

[9]. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM. 1978. Vol. 21. N 2. P. 120-126.

[10]. Gardner M. A new kind of cipher that would take millions of years to break. Scientific American. 1977. Vol. 237. N 2. P. 120-124.

[11]. Atkins D., Graff M., Lenstra A.K., Leyland P.C. The magic words are squeamish ossifrage 16) . Advances in Cryptology — ASIACRYPT’94, Lecture Notes in Comput. Sci. Vol. 917. Berlin, 1995. P. 263-277.

$ \sigma \tau \varepsilon \gamma \alpha \nu o \sigma $ — скрытый; $ \gamma \rho \acute \alpha \varphi \omega $ — пишу.

$ \chi \rho \upsilon \pi \tau \acute \varsigma $ — тайный, скрытый; $ \gamma \rho \acute \alpha \varphi \omega $ — пишу.

cipher (англ.) — шифр; арабская цифра.
Понятно, что сам Цезарь применял его к латинскому алфавиту…
При шифровании пробелы часто опускаются.

Кардано Джероламо (1501-1576). «Великое искусство или об алгебраических преобразованиях» — название изданной в 1545 г. книги Кардано, в которой, в частности, приведена формула решения кубического уравнения. Биографические заметки о Кардано ☞ ЗДЕСЬ.

$ \sigma \varkappa \breve \upsilon \tau \acute \alpha \lambda \eta $ — булава, палица, дубина.

Кантемир Антиох (1708-1744) — русский поэт и переводчик. Разрабатывал свою теорию силлабического стихосложения, которую изложил в работе Письмо Харитона Макентина к приятелю о сложении стихов русских.

(лат.) Каково растяжение, такова и сила (формулировка закона Гука)
affinis (лат.) — смежный, соседний, сопредельный; родственник по мужу или жене.

Иногда она называется функцией с ловушкой — trapdoor one way function (англ.), или функцией с секретом.

Можно так просто взять и скрыть информацию

Каждый из читателей наверняка много раз видел фильмы, где супергерой / суперзлодей передавал зашифрованную информацию. Мы привыкли к слову «шифр», «шифрование» и любая тайная передача информации сейчас ассоциируетсяименно с этими словами. Хотя на самом деле, это далеко не так. Безопасная передача информации далеко не ограничивается криптографией (шифрования), а есть еще много методов и средств для этого.

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

Чем это принципиально отличается от криптографии.
В случае с криптографическими преобразованиями факт сокрытия информации очевиден. То есть, когда А передает информацию в Б, то В знает, что информация секретная, но не имеет (в лучшем случае) алгоритмов ее расшифровки, если она попадет ему в руки.

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

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

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

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

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

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

Для начала напишем html страницу без лишнего дизайна (это не урок веб-дизайна все же). Следовательно файл index.php:

Адрес: Код:

Думаю тут особо объяснять не нужно, что в поле «Адрес» будет адрес изображения, а в поле «Код» — небольшая скрытая информация. Назначение кнопок тоже очевидно. В блоке img_new будет помещаться исходная информация, в том числе готовый контейнер с стегосообщением в нем.

При разработке будем использовать фреймворк Ajax, а точнее ровно одну его функцию. Поэтому подключим к index.php этот фреймворк и один наш js файл.

Стегоалгоритмы будут происходить в файлах stego.php и destego.php. Свяжем их с нашим index-ом с помощью двух функций нашего java script: stego (), de_stego ().

stego.js

 function stego (url, code) < $("#img_new").html(""); $.ajax(< type: "POST", url: "stego.php", data: 'url_img='+url+'&stego_code='+code+'', cache: false, success: function(html)< $("#img_new").html(html); >>); > function de_stego (url) < $("#img_new").html(""); $.ajax(< type: "POST", url: "destego.php", data: 'url_img='+url+'&stego_code='+code+'', cache: false, success: function(html)< $("#img_new").html(html); >>); > 

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

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

Теперь перейдем к самому интересному, к стегопреобразованиям. Сначала рассмотрим файл stego.php.

Прежде добавим проверку наличия адреса изображения

if (!$_POST[url_img])

И проверку типа изображения. Будем считать, что пользователь будет использовать только самые распространенные форматы: jpg, gif, png. В противном случае, программа тоже будет пытаться загрузить изображение, но успех зависит от соответствующей сборки PHP.

$type_img = explode (".", $_POST[url_img]); switch(strtolower($type_img[count($type_img)-1]))

Здесь следует заметить, что часто хостеры не включают графическую библиотеку GD в PHP. Если программа у Вас не будет работать — обратитесь с этим вопросом к Вашему хостер-провайдеру.

Выводим изображение пользователя на экран в формате png. Почему именно этот формат? Потому что выводить другое изображение мы будем тоже в png. Так лучше будет сравнивать потом между собой изображения.

imagepng ($img1, "img/img_code1".date(si).".png"); echo "Входное изображение: ";

Далее определяем размер изображения, задаем начальные координаты x, y, узнаем длину сообщения и заносим сообщения в рабочую переменную $code.

$size = getimagesize($_POST[url_img]); $w = $size[0]; $h = $size[1]; $x = $y = 0; $length = strlen($_POST[stego_code]); $code = $_POST[stego_code];

Далее начинается самое интересное. А именно цикл, в котором наше сообщение попадет в изображение. Сначала приведем код, а дальше будем разбирать:

 while ($length--) < $color_pixel = imagecolorat ($img1, $x, $y); $color_pixel_RGB = imagecolorsforindex ($img1, $color_pixel); $color_pixel_RGB[blue] = ord ($code[$length]); $color_new_pixel = imagecolorclosest ($img1, $color_pixel_RGB[red], $color_pixel_RGB[green], $color_pixel_RGB[blue]); imagesetpixel ($img1, $x, $y, $color_new_pixel); $x+=50; if ($x>$w) > 

Цикл будет повторяться пока не дойдем конца сообщения. К тому же будем начинать с последнего символа. Сначала мы узнаем цвет пикселя по координатам x, y ($ color_pixel = imagecolorat ($ img1, $ x, $ y) ;), заносим в массив $ color_pixel_RGB значение соотношения красного, зеленого и синего цветов в пикселях.

Прошу обратить внимания на строчку: $ color_pixel_RGB [blue] = ord ($ code [$ length]) — Именно здесь уровень синего цвета заменяются на номер символа сообщения в ASCII таблице. Это удобно, потому что они не должны преувеличивать число 255 как и значение переменной соответственно RGB. Автор наугад выбрал синий цвет. Можете попробовать с любым другим (зеленым или красным цветом), которые в данной программе остаются нетронутыми, за исключением одного случая, о котором будет дальше.

Далее в цикле происходит нанесение пикселя на новое изображение и увеличение координат. Если они превышают ширину изображения, то происходит увеличение значения координаты по высоте (y), а x приравнивается к нулю.
Вот таким не хитрым способом мы скрыли наше сообщение в изображении.

Но как программа при изъятии стегосообщения узнает, что наступил конец сообщения? Для этого в последнем пикселе сообщение меняем уровень красного цвета на 1.

 $color_new_pixel = imagecolorclosest ($img1, 1, $color_pixel_RGB[green], $color_pixel_RGB[blue]); imagesetpixel ($img1, $x, $y, $color_new_pixel);

И выводим новое изображение на экран:

 imagepng ($img1, "img/img_code2".date(si).".png"); echo "Исходное изображение: ";

Таким образом файл stego.php готов и выглядит так:

stego.php

 $type_img = explode (".", $_POST[url_img]); switch(strtolower($type_img[count($type_img)-1])) < case "png": $img1 = imagecreatefrompng($_POST[url_img]); break; case "jpg": $img1 = imagecreatefromjpeg($_POST[url_img]); break; case "jpeg": $img1 = imagecreatefromjpeg($_POST[url_img]); break; case "gif": $img1 = imagecreatefromgif($_POST[url_img]); break; default: $img1 = imagecreatefromgd ($_POST[url_img]); break; >imagepng ($img1, "img/img_code1".date(si).".png"); echo "Входное изображение: "; $size = getimagesize($_POST[url_img]); $w = $size[0]; $h = $size[1]; $x = $y = 0; $length = strlen($_POST[stego_code]); $code = $_POST[stego_code]; while ($length--) < $color_pixel = imagecolorat ($img1, $x, $y); $color_pixel_RGB = imagecolorsforindex ($img1, $color_pixel); $color_pixel_RGB[blue] = ord ($code[$length]); $color_new_pixel = imagecolorclosest ($img1, $color_pixel_RGB[red],$color_pixel_RGB[green], $color_pixel_RGB[blue]); imagesetpixel ($img1, $x, $y, $color_new_pixel); $x+=50; if ($x>$w) > $color_new_pixel = imagecolorclosest ($img1, 1, $color_pixel_RGB[green], $color_pixel_RGB[blue]); imagesetpixel ($img1, $x, $y, $color_new_pixel); imagepng ($img1, "img/img_code2".date(si).".png"); echo "Исходное изображение: "; ?>

Теперь перейдем ко второй функции, так как, какой смысл в сокрытии информации, если сами потом вытащить не сможем?

И так файл destego.php.

Половина кода аналогично коду stego.php:

destego половина

 if (!$_POST[url_img]) < echo "Введите все данные"; exit(); >$type_img = explode (".", $_POST[url_img]); switch(strtolower($type_img[count($type_img)-1])) < case "png": $img1 = imagecreatefrompng($_POST[url_img]); break; case "jpg": $img1 = imagecreatefromjpeg($_POST[url_img]); break; case "jpeg": $img1 = imagecreatefromjpeg($_POST[url_img]); break; case "gif": $img1 = imagecreatefromgif($_POST[url_img]); break; default: $img1 = imagecreatefromgd ($_POST[url_img]); break; >echo "Входное изображение: "; echo "Код: "; $size = getimagesize($_POST[url_img]); $w = $size[0]; $h = $size[1]; $x = $y = 0;

Здесь уже знакомые нам проверки ввода информации, загрузки изображения и вывод его на экран

Далее идет цикл, который вытягивает нашу информацию с картинки:

 while ($color_pixel_RGB[red]!=1) < $color_pixel = imagecolorat ($img1, $x, $y); $color_pixel_RGB = imagecolorsforindex ($img1, $color_pixel); $text = chr($color_pixel_RGB[blue]).$text; $x+=50; if ($x>$w) > ;

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

 $text[0] = ""; echo $text; 

$ Text [0] = «» — нужно так как первый символ остается пустым и может быть заполнен всяким «мусором».

И так, destego.php выглядит так:

destego.php

 $type_img = explode (".", $_POST[url_img]); switch(strtolower($type_img[count($type_img)-1])) < case "png": $img1 = imagecreatefrompng($_POST[url_img]); break; case "jpg": $img1 = imagecreatefromjpeg($_POST[url_img]); break; case "jpeg": $img1 = imagecreatefromjpeg($_POST[url_img]); break; case "gif": $img1 = imagecreatefromgif($_POST[url_img]); break; default: $img1 = imagecreatefromgd ($_POST[url_img]); break; >echo "Входное изображение: "; echo "Код: "; $size = getimagesize($_POST[url_img]); $w = $size[0]; $h = $size[1]; $x = $y = 0; while ($color_pixel_RGB[red]!=1) < $color_pixel = imagecolorat ($img1, $x, $y); $color_pixel_RGB = imagecolorsforindex ($img1, $color_pixel); $text = chr($color_pixel_RGB[blue]).$text; $x+=50; if ($x>$w) > ; $text[0] = ""; echo $text; ?>

Так, наша программа есть и в интернете. Так она выглядит:

Вводим адрес изображения.
Вводим сообщение автора материала: Осадчий Сергей
Нажимаем «Скрыть» и получаем исходное изображение:

Входное изображение:

image

Исходное изображение:

image

Как видите, изображение идентичны.

Копируем адрес исходного изображения, вставляем в адрес изображения и нажимаем «Изъять». Получаем:

Убедиться можете сами.

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

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

P.S. Не будьте слишком строги к автору. Это моя первая статья на хабре. Спасибо!

  • Информационная безопасность
  • PHP
  • Программирование

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *