Моно- и многоалфавитные подстановки

Подстановки - наиболее пpостой вид пpеобpазований, заключающийся в замене символов исходного текста на дpугие (того же алфавита) по более или менее сложному пpавилу.

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

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

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

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

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

Замена символов открытого текста может происходить на специальные символы, например на "пляшущих человечков", как в рассказе К.Дойла.

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

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

Ниже приведен фрагмент многоалфавитного ключа замены.

С помощью многоалфавитного шифра сообщение "ГДЕ АББА" можно зашифровать несколькими способами:

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

Рассмотрим еще один многоалфавитный шифр замены, который был описан в 1585 французским дипломатом Блезом де Виженером. Шифрование производится с помощью, так называемой таблицы Виженера (Рис. 30). Здесь, как и прежде, показана лишь часть таблицы для того, чтобы изложить лишь идею метода.

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

Предположим, что нужно зашифровать сообщение "ГДЕ АББА". В качестве ключа выберем слово "ДЕВА". В результате получим:

В результате преобразований получится шифровка:

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

Для пояснения идеи возьмем квадрат (матрицу) 8х8, будем записывать текст последовательно по строкам сверху вниз, а считывать по столбцам последовательно слева направо.

Предположим, что требуется зашифровать сообщение:

"НА ПЕРВОМ КУРСЕ ТЯЖЕЛО УЧИТЬСЯ ТОЛЬКО ПЕРВЫЕ ЧЕТЫРЕ ГОДА ДЕКАНАТ".

В результате преобразований получится шифровка: "НМТЧОРЫ_А_ЯИЛВРД_КЖТЬЫЕЕПУЕЬКЕ_КЕРЛСО_ ГАР СОЯ_ЧОНВЕ__ПЕДАО_УТЕТАТ" (читаем таблицу по столбцам).

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

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

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

В компьютерах преобразование открытого текста происходит естественным путем, так как каждый символ кодируется двоичным числом. Вид этого преобразования зависит от используемой операционной системы. Для определенности будем считать, что открытое сообщение кодируется с помощью кодовой таблицы CP1251 (операционная система Windows). Кроме того, будем считать, что секретная гамма добавляется к открытому тексту по правилу сложения по модулю два без переносов в старшие разряды (логическая операция Исключающее ИЛИ). Результаты всех преобразований поместим в таблицу.

Для наглядности результат шифрования переведен с помощью таблицы CP-1251 в буквы.

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

С какими целями используется цифровая подпись? Для предотвращения следующих ситуаций при электронном документообороте:

1) отказ: абонент А заявляет, что не посылал документа абоненту В, хотя на самом деле он его послал;

2) модификация: абонент В изменяет документ и утверждает, что именно таким получил его от абонента А;

3) подмена: абонент В сам формирует документ и заявляет, что получил его от абонента А;

4) активный перехват: нарушитель (подключившийся к сети) перехватывает документы (файлы) и изменяет их;

5) "маскарад": абонент С посылает документ от имени абонента А;

6) повтор: абонент С повторяет посылку документа, который абонент А ранее послал абоненту В.

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

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

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

3) задача нахождения Е по известному D должна быть трудной.

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

Перечислим наиболее известные математические схемы ЭЦП: RSA (названа по первым буквам фамилий авторов: R. L. Rivest, A. Shamir, L. Adleman), OSS (H. Ong, C. P. Schnorr, A. Shamir), Эль-Гамаля (T. ElGamal), Рабина (M. Rabin), Окамото Сираиси (T. Okamoto, A. Shiraishi), Мацумото Имаи (T. Matsumoto, H. Imai), схемы с использованием эллиптических кривых и др.

В схемах RSA, Рабина, Эль-Гамаля и Шнорра (C. P. Schnorr) трудность задач подделки подписи обусловлена вычислительной сложностью задач факторизации или дискретного логарифмирования.

В принятых не стандартах США и России на цифровую подпись (DSS - Digital Signature Standard, ГОСТ Р 34.10-94 "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма" и ГОСТ Р 34.11-94 "Функция хеширования") используются специально созданные алгоритмы. В основу этих алгоритмов положены схемы Эль-Гамаля и Шнорра.

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

Чтобы поставить ЭЦП под конкретным документом, необходимо проделать довольно большой объем вычислительной работы. Эти вычисления разбиваются на два этапа.

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

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

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

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

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

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

Если рассматриваемое соотношение оказывается выполненным, то подпись признается правильной, а сам документ подлинным, в противном случае документ считается измененным, а подпись под ним недействительной.

Алгоритмы сжатия данных появились с тех пор, как появились сами массивы данных, которые следовало как-то хранить и передавать. Таким образом, проблема “данные/степень их сжатия” актуальна уже достаточно давно. В наши дни она стоит особенно остро, поскольку с ростом технологий растут и массивы данных. Несмотря на расширение каналов передачи данных, скорость этой самой передачи является узким местом.

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

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

Давайте возьмем простой пример. Допустим, необходимо составить таблицу, в которую будут заноситься результаты эксперимента с подбрасыванием монеты. Даже это простое действие мы можем сделать несколькими способами, например, так (1 -орел, 0 – решка):

Это далеко не все способы, но налицо явная избыточность информации в первых двух таблицах и устранение избыточности данных в последней таблице. Итак, сжатие – это избавление от избыточных данных, осуществляемое по алгоритму эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее. Это сжатие без потери кода. А что же такое потеря кода в алгоритмах сжатия? Это безвозвратное устранение некоторой избыточности кода без ощутимой потери качества информации. Это легко понять на следующем примере: возьмем обычный текстовый файл и удалим из абзацев все символы переноса строки, заменим в файле все цепочки пробелов в начале абзацев на символ табуляции, а также удалим все незначащие пустые строки и сохраним наш файл. Что мы получили? Мы получили точно такой же читаемый файл с неизмененной информацией, но меньшего размера. Иными словами, качество информации не потеряно. Но вместе с тем мы уже не сможем восстановить устраненную избыточную информацию. Именно на этом принципе и работают алгоритмы сжатия мультимедийных данных. Например, уменьшение размеров изображения – тоже своего рода сжатие с потерями.

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

Принцип работы алгоритма легко понять на следующем примере. Имеем текст:

аааааааааааабббббббббвапезааааааааааааааааазепккккккккккккккккккккккккк

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

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

LZ – Lempel-Ziv. Это метод словарей, несколько улучшенный алгоритм сжатия изображений, впервые опубликованный в 1977 г. На сегодняшний день LZ-алгоритм и его модификации получили наиболее широкое распространение по сравнению с другими методами сжатия. Принцип в общем похож на RLE. Из повторяющихся участков кода формируется индексированный словарь. А поскольку индекс занимает гораздо меньше места, чем участок кода, получается достаточно эффективный метод сжатия. Основной плюс – сжимаются повторы комбинаций. Основной недостаток – словарь требуется хранить в том же файле. Существует большое число модификаций этого метода LZ – LZW, LZ77, LZSS и т. д.

Вероятностные методы сжатия. В основе вероятностных методов сжатия (алгоритмов Шеннона-Фано (Shannon Fano) и Хаффмана (Huffman) лежит идея построения “дерева”, в котором положение символа на “ветвях” определяется частотой его появления. Каждому символу присваивается код, длина которого тем меньше, чем выше частота появления этого символа. Существуют две разновидности вероятностных методов, различающихся способом определения вероятности появления каждого символа:

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

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

Статические методы характеризуются хорошим быстродействием и не требуют значительных ресурсов оперативной памяти. Они нашли широкое применение в многочисленных программах-архиваторах, например, ARC, ZIP, RAR и т. д.

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: