Файл: Методы кодирования данных (Понятие кода и кодирования данных).pdf
Добавлен: 27.04.2023
Просмотров: 221
Скачиваний: 2
Описанный выше вариант кодирования звуковой информации в целом весьма универсален, он позволяет представить абсолютно любой звук и преобразовывать его достаточно разными способами. Однако, бывают случаи, когда удобнее действовать иначе.
Уже достаточно давно используется весьма компактный вариант представления музыки – нотная запись. В ней с помощью специальных символов указывается высота и длительность, а также общий темп исполнения мелодии. В целом, подобную запись можно назвать алгоритмом для исполнителя, записанным на специальном формальном языке. В 1983 г. передовые производители компьютеров и музыкальных синтезаторов разработали стандарт, определивший такую систему кодов. Он получил название MIDI (Musical Instrument Digital Interface). [4] При таком кодировании запись компактна, достаточно легко меняется инструмент музыканта, тональность звука. Одна и та же запись может воспроизводиться как на компьютере, так и на синтезаторе.
Конечно же, указанная система кодирования позволяет нам записать далеко не каждый звук, она применима исключительно для инструментальной музыки. Однако есть у нее и неоспоримые преимущества: чрезвычайно сжатая запись, непринужденность для музыканта (практически любой MIDI-редактор позволяет работать с музыкой в виде стандартных нот), простота замены инструментов, темпа и тональности мелодии.
Есть и другие форматы записи музыки. Среди них – формат MP3, дающий возможность с весьма большим качеством и степенью сжатия кодировать музыку, при этом вместо 18 – 20 музыкальных композиций на стандартном компакт-диске (CDROM) помещается около 200. Одна песня занимает примерно 3,5 Mb, что позволяет пользователям сети Интернет непринужденно обмениваться музыкальными композициями.
Раздел 2 Кодирование текста
Шифр Вижинера
В 1467 году итальянский ученый Леон Альберти впервые задокументировал описание многоалфавитного шифра. Для переключения между алфавитами использовался металлический шифровальный диск. Эта система переключает алфавиты после нескольких зашифрованных слов. Позднее, в 1518 году, Иоганн Трисемус в своем труде «Полиграфия», посвященном криптологии, изобрел tabula recta - центральный компонент шифра Виженера.[6] Представляет собой алфавитную таблицу, каждая строка которой циклически сдвигается.
В 1586 году Блез Виженер представил собственное описание простого, однако, при этом невероятно стойкого к ручному взлому шифра перед комиссией Генриха III во Франции. Немногим позже именно Вижинеру было присвоено изобретение шифра. Давид Кан в своей книге «Взломщики кодов» отозвался об этом критически, написав, что история «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания». [7]
Известный математик Чарльз Доджсон в 1916 году отозвался о шифре Виженера как о не взламываемом в своей статье «Алфавитный шифр», такого же мнения был и Scientific American в 1917 году. Это представление было полностью опровергнуто Фридрихом Касиски в XIX веке, после того, как он сумел полностью взломал шифр. Хотя известны случаи взлома этого шифра некоторыми опытными криптоаналитиками еще в XVI веке. [6]
Шифр Виженера очень прост в использовании, особенно в случае применения шифровальных дисков: к примеру, медный шифровальный диск для шифра Виженера использовался в ходе Гражданской войны в Америке. [8]
Гилберт Вернам улучшал взломанный шифр (он получил название шифр Вернама-Виженера в 1918 году), но, несмотря на его работу, шифр попрежнему продолжал быть уязвимым к криптоанализу. Несмотря на это работа Вернама в финале позволила получить шифр, который по-настоящему сложно взломать.
Шифр Цезаря
В I в до н. э. Гай Юлий Цезарь во время войны с галлами, в переписке со своими сторонниками в Риме, заменял в тексте первую букву латинского алфавита (А) на четвертую (D), вторую (В) - на пятую (Е), наконец, последнюю - на третью.
Сообщение об одержанной им победе выглядело так: YHQL YLGL YLFL «Veni, vidi, vici» - «Пришел, увидел, победил» (лат.).
Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря - является одним из самых простых и является самым известным из методов шифрования.
Шифр Цезаря - это разновидность шифра подстановки, в нем каждый символ в изначальном тексте заменяется символом находящимся на некоторой постоянной позиций праве или левее него в алфавите. К примеру, в шифре со сдвигом 3, А будет заменена на Г, Б превратится в Д, и так далее.
Этот шифр назван в честь римского императора Гая Юлия Цезаря, применившего его для секретной передачи информации своим генералам. Древнеримский историк Светоний не называет примеров вскрытия переписки Цезаря. Сам Цезарь всегда применял один и тот же ключ (сдвиг - 3). Этот способ он применял, в частности, для частной переписки с Цицероном.[Пример данного шифра приведен в приложении 1]
Этот способ шифрования, выполняемый шифром Цезаря, часто используется как составляющие более сложных схем, к примеру как в шифре Виженера, и по сей день имеет приложение в системе ROT13. Как и все моноалфавитные шифры, шифр Цезаря достаточно просто поддается криптоанализу и имеет ничтожно малую область применения на практике.
В 19-ом столетии, раздел рекламных объявлений в газетах иногда применялась, для того чтобы обмениваться сообщениями, шифрованными с использованием легких шифров. Кан (1967) описывает события когда любители принимали участие в секретном общении, шифруя свои сообщения с применением шифра Цезаря в "Таймс". Даже позднее, в 1915, шифр Цезаря применялся: в российской армии использовался как замена для более сложных шифров, которые были сложными в использовании для войск; у немецких и австрийских криптоаналитиков были незначительные сложности при декодировании таких сообщений.
Шифр Цезаря со сдвигом тринадцать применяется в алгоритме ROT13, простом методе запутывания символов, в большой степени применяемого в Usenet, и используется скорее как способ сокрытия спойлеров, чем как полноценный метод шифрования. Шифр Вижинера включает в себя шифр Цезаря с не постоянным сдвигом в каждой позиции в сообщение; величина смещения определяется при помощи повторяющегося ключа. Если ключ имеет такую же длину как и сообщение, в таком случае этот шифр становится невзламываемым до тех пор пока поддерживается тайна ключевого слова.
Ключевые слова, с длинной меньше чем сообщение (например, "Complete Victory", используемое Конфедерацией во время гражданской войны в США), вносят циклический образец, который с помощью улучшенной версии частотного анализа мог быть обнаружен.
Шифр RSA
RSA - криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и цифровая подпись (аутентификация - установление подлинности). Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков Ronald Rivest, Adi Shamir и Leonard Adleman.
RSA относится к асимметричным алгоритмам, у них ключ шифрования различается с ключом дешифровки. Один из ключей находится в открытом доступе (так делается специально) и его называют открытым ключом, второй хранится только у владельца и неизвестен более никому. С помощью каждого из ключей можно произвести операцию только в одну сторону. Сообщение зашифрованное с помощью одного из ключей, можно расшифровать только при помощью другого. Если имеется только один из ключей очень сложно вычислить второй ключ, если разрядность его достаточно высока.
Алгоритм RSA строится по схеме:
1. Взять два достаточно больших простых числа p и q
2. Вычислить n = p * q
3. Вычислить m = (p - 1) * (q - 1)
4. Взять число d взаимно простое с m
5. Взять число e так, чтобы e * d = 1 (mod m)
Числа e и d являются ключами RSA. Шифруемые данные необходимо разбить на блоки - числа от 0 до n - 1. Шифрование и дешифровка данных производятся следующим образом:
· Шифрование: b = ae (mod n)
· Дешифровка: a = bd (mod n)
Интересно также то , что ключи e и d равнозначны, т.е. сообщение можно зашифровать как ключом e, так и ключом d, при этом расшифровка производиться при помощью второго ключа.
Алгоритм RSA намного медленнее чем DES и прочие алгоритмы блокового шифрования. Программная реализация DES работает быстрее по меньшей мере в 100 раз и от 1,000 до 10,000 - в аппаратной реализации (в зависимости от конечного устройства). Благодаря разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блокового шифрования.
Раздел 3 Кодирование изображений
JPEG
Самое большое отличие формата JPEG от других форматов состоит в том, что в JPEG используется алгоритм кодирования с потерями (а не алгоритм без потерь) информации.
Алгоритм кодирования без потерь таким образом сохраняет информацию об изображении, что декодированное изображение точно соответствует оригиналу. При кодировании с потерями часть информации об изображении приносится в жертву, для получения большего коэффициента сжатия.
Декодированное изображение JPEG далеко не всегда соответствует исходному на 100%, но достаточно часто эти различия столь малозаметны, что их едва можно обнаружить.
Процесс кодирования изображения JPEG достаточно сложен и часто для достижения необходимой скорости исполнения требуется специальная аппаратура.
Первым шагом изображение делится на квадраты со стороной размером 8 пикселов. Далее производится кодирование каждого квадрата отдельно за три этапа.
На первом этапе при помощи дискретного косинусоидального преобразования фуры (DCT) преобразуется блок 8х8 с информацией о пикселах в матрицу 8x8 амплитудных величин, представляющую различные частоты (скорости изменения цвета) в изображении.
Во время второго этапа значения матрицы амплитуд делятся на значения матрицы квантования, смещенной так, чтобы амплитуды, незначительно влияющие на общий вид изображения были отфильтрованы.
На третьем и последнем этапе квантованная матрица амплитуд кодируется с применением алгоритма сжатия без потерь.
Алгоритм оперирует областями 8х8, на которых яркость и цвет меняются достаточно плавно.
Вследствие этого процесса, при разложении матрицы такой области в двойной ряд по косинусам значимыми оказываются только первые коэффициенты.
Таким образом, сжатие в JPEG осуществляется за счет малой величины значений амплитуд высоких частот в реальных изображениях.
Вследствии того что в квантованной матрице отсутствует большая доля высокочастотной информации, которая находится в исходной матрице, первая зачастую уменьшается до половины собственного первоначального размера или еще больше.
Реальные фотографические изображения часто совсем невозможно сжать с помощью методов сжатия без потерь, поэтому 50%-ное сжатие следует признать достаточно хорошим.
С другой стороны, применяя методы сжатия без потерь, можно сжимать некоторые изображения на 90%. Такие изображения плохо подходят для сжатия методом JPEG.
При использовании сжатия методом JPEG потери информации обычно происходят на втором этапе процесса.
С ростом значений в матрице квантования, увеличивается часть информации которая отбрасывается из изображения и тем более плотно сжимается изображение.
Компромисс заключается в том, что более большие значения квантования приводят к высокой потере качества изображения.
При создании изображения JPEG пользователь самостоятельно устанавливает уровень качества, величина этого уровня "управляет" значениями матрицы квантования.
Оптимальные показатели качества, которые обеспечивают лучший показатель баланса в отношении коэффициента сжатия и качества изображения, различны для разных изображений и обычно могут быть найдены только эмпирическим методом.
Коэффициент архивации в JPEG может изменяться в пределах от 2 до 200 раз. Как и у любого другого алгоритма сжатия с потерями, у JPEG свои особенности.
Наиболее известны "эффект Гиббса" и дробление изображения на квадраты 8х8.
"Эффект Гиббса" представляет собой проявляется около резких границ предметов, образует своего рода "ореол". Он хорошо виден, если, допустим, поверх фотографии выполнить надпись цветом, резко отличающимся от фона.
Дробление на квадраты происходит, когда задается слишком высокий коэффициент архивации для конкретного изображения.
Не приятным свойством JPEG является также то, что часто горизонтальные и вертикальные полосы на экране абсолютно не видны, и могут появиться только при печати в виде муарового узора.