80. Архивирование. Форматы lz77, lz78. Принцип скользящего окна. Механизм

кодирования совпадений.

LZ77 и LZ78 — алгоритмы сжатия без потерь

Принцип скользящего окна

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

Механизм кодирования совпадений

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

В стандартном алгоритме LZ77 совпадения кодируются парой:

• длина совпадения (match length)

• смещение (offset) или дистанция (distance)

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

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

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

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

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

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

82. Ssh. Клиент, сервер ssh.

SSH (англ. Secure SHell — «безопасная оболочка») — сетевой протоколсеансового уровня, позволяющий производить удалённое управлениеоперационной системой и туннелирование TCP-соединений (например, для передачи файлов). Шифрует весь трафик, включая и передаваемые пароли. SSH допускает выбор различных алгоритмов шифрования. SSH-клиенты и SSH-серверы доступны для большинства сетевых операционных систем.

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

83. SSL. Открытый ключ PKI. SSL (англ. Secure Sockets Layer — уровень защищённых сокетов) — криптографический протокол,  который обеспечивает установление безопасного соединения между клиентом и сервером. SSL изначально разработан компанией Netscape Communications.  Впоследствии на основании протокола SSL 3.0 был разработан и принят стандарт RFC,  получивший имя TLS. Протокол обеспечивает конфиденциальность обмена данными между клиентом и сервером,  использующими TCP/IP, причём для шифрования используется асимметричный алгоритм с открытым ключом. При шифровании с открытым ключом используются два ключа, причем любой из них может использоваться для шифрования сообщения.  Тем самым, если используется один ключ для шифрования, то соответственно для  расшифровки нужно использовать другой ключ. В такой ситуации можно получать  защищённые сообщения, публикуя открытый ключ, и храня в тайне секретный ключ. Инфраструктура открытых ключей (англ. PKI - Public Key Infrastructure) - технология  аутентификации с помощью открытых ключей. Это комплексная система,  которая связывает открытые ключи с личностью пользователя посредством удостоверяющего центра (УЦ). В основе PKI лежит использование криптографической системы с открытым  ключом и несколько основных принципов: закрытый ключ известен только его владельцу; удостоверяющий центр создает сертификат открытого ключа,  таким образом удостоверяя этот ключ; никто не доверяет друг другу, но все доверяют удостоверяющему центру; удостоверяющий центр подтверждает или опровергает принадлежность открытого  ключа заданному лицу, которое владеет соответствующим закрытым ключом. Фактически, PKI представляет собой систему, основным компонентом которой  является удостоверяющий центр и пользователи, взаимодействующие между собой посредством удостоверяющего центра.