Файл: Методы кодирования данных (позволяющие выполнять шифрование).pdf

До появления Интернета шифрование во многих отношениях считалось проблемой только для государственных учреждений. Алгоритм RSA был введен в то время, когда потенциальная популярность Интернета впервые стала очевидной. С этой популярностью пришел высокий спрос на безопасную и надежную возможность передачи информации. Алгоритм RSA, воспринимаемый как почти неразрушимая криптосистема с открытым ключом, быстро стал ключевым методом выбора для приложений криптографии в Интернете, включая, например, шифрование электронной почты. Сегодня RSA также продолжает использоваться внутри протокола Secure Socket Layer (SSL), используемого в большинстве случаев обмена данными в интернете [1.]. Это позволяет сделать вывод о том, что алгоритм RSA является очень надежной криптосистемой, которая используется в течение последних тридцати лет для обеспечения безопасности в миллионах приложений в Интернете.

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

Методы сжатия данных

Основы сжатия данных

Объемы регулярно производимых цифровых данных растут день ото дня. По данным всемирной консалтинговой организации International Data Corporation, общий объем новых данных будет увеличиваться с ежегодным приростом 57%, что опережает ожидаемый рост емкости носителей информации. Поскольку необходимо сохранять большую часть этих данных, всегда существует экономически целесообразная потребность в эффективных цифровых архивах. Наиболее популярные их них используют принцип сжатия данных. Сжатие представляет собой процесс преобразования входного потока данных (исходного потока, или исходных необработанных данных) в другой поток данных (выходной поток, поток битов, или сжатый поток), который имеет меньший размер [14.]. Поток – это файл или буфер в памяти.

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

Предметную область сжатия данных часто называют кодированием для сжатия. Легко представить себе, что входные символы (такие как биты, коды ASCII, байты, аудиосэмплы или значения пикселей) генерируются определенным источником информации и должны быть закодированы перед их отправкой по назначению. Источник может быть без внутренней памяти, но может также иметь память. В первом случае каждый символ не зависит от предшествующих ему, во втором – зависит от некоторых ему предшествующих и, возможно, также от следующих за ним символов, поэтому они взаимосвязаны. Источник данных без памяти также называется «независимым и одинаково распределенным». Сжатие данных достигло своего пика за последние 20 лет. Количество и качество литературы в этой области являются достаточным доказательством.

Существует много известных способов сжатия данных [14.]. Они основаны на разных идеях, подходят для разных типов данных и дают разные результаты, но в основе каждого из них лежит один и тот же принцип – они сжимают данные, удаляя избыточность из исходных данных в исходном файле. Любые неслучайные данные имеют некоторую структуру, и эта структура может быть использована для достижения меньшего представления данных, представления, где структура не различима. Термины «избыточность» и «структура» используются в профессиональной литературе, равно как и «гладкость», «согласованность» и «корреляция»; все они относятся к одному и тому же понятию. Таким образом, избыточность является ключевым понятием в любой дискуссии о сжатии данных.

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

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

Принцип сжатия путем удаления избыточности [15.] также отвечает на следующий вопрос: «Почему уже сжатый файл не может быть сжат в дальнейшем?» Ответ, конечно же, заключается в том, что такой файл имеет небольшую избыточность или не имеет ее вообще, поэтому из него уже ничего нельзя удалить. Примером такого файла является случайный текст. В случайном тексте каждая буква встречается с равной вероятностью, поэтому присвоение символам кодов фиксированного размера не добавляет избыточности. Когда такой файл сжимается, избыточность для удаления отсутствует. Другой ответ на вопрос заключается в том, что если бы можно было сжимать уже сжатый файл, то последовательные сжатия уменьшали бы размер файла до тех пор, пока он не станет занимать всего лишь один байт или даже один бит в памяти компьютера. Это, конечно, невозможно, поскольку один байт не может содержать информацию, представленную в сколь угодно большом файле.

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

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

Кроме того, современные методы сжатия без потерь [11.] являются адаптивными, поскольку они не просматривают весь входной файл и не создают словарь ссылок, который должен быть заменен. Вместо этого они анализируют файл, когда начинают его читать, и воссоздают словарь, основываясь на том, какие данные в действительности повторяются. Словарь становится более информативным и объемным по мере продолжения процесса.

Архивы и форматы архивных файлов

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

Некоторые архивы могут быть оформлены в виде программ [17.]. Они являются самораспаковывающимися – для распаковки содержимого такого архива не требуется иметь совместимую с ним программу-архиватор.

Использование архивов имеет ряд преимуществ:

• удобство ориентации в файловом пространстве;
• экономия места;
• надежность хранения информации.

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

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

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

Программистам UNIX-подобных систем хорошо известна стандартная утилита ar, так как она широко используется даже сегодня для создания статических библиотек, которые являются не чем иным, как архивами скомпилированных файлов. Утилита ar может использоваться для создания архивов всех видов. Как правило, файлы пакетов .deb в системах Debian – это не что иное, как ar-архивы. А пакеты mpkg в MacOS X – это сжатые gzip-архивы cpio. Формат tar более популярен среди пользователей, чем thanar и cpio, поскольку команда tar была действительно хорошей и простой в использовании [11.].

RAR – это хорошо известный формат архивных файлов, который используется для сжатия данных, восстановления после ошибок и охвата файлов [11.]. Структурно файл RAR состоит из блоков переменной длины обязательных и необязательных данных. Точность создания блоков со временем развивалась от версии к версии. Первоначально файл RAR состоял из маркера или вводного блока, архивного блока, который состоял из заголовка архива и заголовка файла, и закрывающего блока, который состоял из дополнительных комментариев или другой информации, необходимой для правильной обработки файла. Порядок этих блоков мог варьироваться, но первый блок должен быть вводным блоком, за которым следует блок заголовка архива. Блок архива очень сложен, потому что он содержит заголовки своих архивов, а также заголовки файлов [18.].

Формат файла ZIP был введен в конце 1980-х годов для утилиты PKZIP. Он обновлялся из года в год, и теперь включает в себя различные алгоритмы сжатия. Не всегда случается так, что ZIP-алгоритмы являются наиболее эффективными или действенными – у них есть много других конкурентов, которые могут работать лучше во многих ситуациях, но общая производительность этих алгоритмов хорошая. Формат файла ZIP используется во многих продуктах, таких как файлы JAR Java, файлы проекта SAS Enterprise Guide и т.д. Формат ZIP поддерживается Windows, поэтому он специально используется в кроссплатформенных средах [14.].