Объясните понятие сжатия информации.

Общая схема передачи информации

Информацию можно передавать последовательно, т.е. бит за битом, и параллельно, т.е. группами фиксированного количества бит. Параллельный способ быстрее, но он часто технически сложнее и дороже особенно при передаче данных на большие расстояния. Параллельный способ передачи используют, как правило, только на расстоянии не более 5 метров. Канал связи - это среда передачи информации, которая характеризуется в первую очередь макс. возможной для нее скоростью передач данных(емкостью канала). Шум - это помехи в канале связи при передаче информации. Скорость передачи информации измеряется в количестве переданных за одну секунду бит или в бодах (baud): 1бод = 1бит/сек (bps).

Устройства для преобразования непрерывной информации в дискретную обобщающе называются АЦП (аналого-цифровой преобразователь) или ADC (Analog to Digital Convertor, A/D); для преобразования дискретной информации в аналоговую - ЦАП (цифро-аналоговый преобразователь) или DAC (Digital to Analog Convertor, D/A).

Преобразование информации.

Цель сжатия - уменьшение количества бит, необходимых для хранения или передачи заданной информации(Rar, Zip, Arj, GZ и др.)

Кодирование - процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки (Цифровое,Аналоговое,Таблично-символьное,Числовое) преобразования сообщения в комбинацию символов в соответствии с кодом

Шифрова́ние — способ преобразования открытой информации в закрытую и обратно

Для формального определения предела сжатия рассматриваем любое информационное сообщение длины n как

■ последовательность независимых, одинаково распределенных Д.С.В. X,- или

■ как выборки длины n значений одной Д.С.В. Х.

Пределы сжатия. Теорема 1. Среднее количество бит,

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

Теорема 2. Существует такое кодирование (Шеннона-Фэно), что HX ≥ ML(X) - 1.

Сжатие информации. Метод Шеннона-Фэно

1) Значения д.с.в. располагают в порядке убывания их вероятностей. 2) Затем последовательно делят на две части с приблизительно равными вероятностями. 3) К коду первой части добавляют 0, а к коду второй – 1 ит.д.

недостатки:

· С ростом длины сообщения трудоемкость построения кода становится недопустимо большой.

· Такое кодирование делает невозможным отправку сообщения по частям, что необходимо для непрерывных процессов передачи данных.

· Дополнительный недостаток - необходимость отправки или хранения полученного кода вместе с кодовой таблицей, что снижает эффект от сжатия.\

Полученный код: A—11,

B—1, C —100, D—00,E—011, F — 010

X Р code(X)

А 0,4 0

В 0.2 11

С 0.4 10

ML(X) = ML1(X) = 1.6 бит/сим, НХ = log2 5 - 0.8= 1.523 бит/сим

Сжатие информации. Метод Хаффмена

· Более практичен и никогда по степени сжатия не уступает методу Шеннона-Фэно, более того, он сжимает максимально плотно.

· Код строится при помощи двоичного (бинарного) дерева. Вероятности значений д.с.в. приписываются его листьям; все дерево строится, опираясь на листья.

· Величина, приписан к узлу дерева, наз-ся весом узла.

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

· После постройки корня нужно приписать каждой из ветвей, исходящих из родительских узлов, значения 0 или 1.

· Код каждого значения д.с.в. - это число, получаемое при обходе ветвей от корня к листу, соответствующему данному значению.

Двигаясь по кодовому дереву сверху вниз, можем записать для каждого символа соответствующий ему код

с е h I a k m b

01 00 111 110 100 1011 10101 10100

10. Сжатие информации. Сл. –ор. алгоритмы сжатия

Разработан израильскими математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Lempel).

Одной из причин популярности алгоритмов LZ является их исключительная простота при высокой эффективности сжатия.

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

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

□ Обычно размер окна составляет несколько килобайт, а размер буфера - не более ста байт. Алгоритм пытается найти в словаре фрагмент, совпад-ий с содерж. буфера.

□ Алгоритм LZ выдает коды, сост-ие из 3 эл-ов:

■ смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера;■ длина этой подстроки; ■ первый символ буфера, следующий за подстрокой

46. Объясните процесс шиф-рования информации

Шифр перестановки — шифр, переставляющий символы сообщения между собой для получения шифротекста, так что символы, оставаясь сами собой меняют свою позицию в сообщении. Наиболее интересным является так называемый „шифр нигилистов“, Шифр Цезаря (сдвиг вправо на n символов, одноалфавитный) - – легко взламывается частотным анализом

. Многоалфавитный шифр подстановки состоит из нескольких шифров простой замены.(шифр Виженера, шифр Бофора, одноразовый блокнот. Суть -циклическом применении нескольких моноалфавитных шифров к определённому числу букв шифруемого текста. Самым важным эффект -маскировка частот появления тех или иных букв в тексте). шифры замены - отдельные части сообщения (буквы, слова,...) заменяются на какие-либо другие буквы, числа, символы и т.д. При этом замена осуществляется так, чтобы потом по шифрованному сообщению можно было однозначно восстановить передаваемое сообщение. Гамми́рование (однозначной замены) — метод шифрования, основанный на «наложении» гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле (например, в поле GF(2) такое суммирование принимает вид обычного «исключающего ИЛИ»). При расшифровке операция проводится повторно, в результате получается открытый текст.

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

Симметричные шифры — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ. Ключ должен сохраняться в секрете обеими сторонами. Алгоритм шифрования выбирается сторонами до начала обмена сообщениями. Классическим примером таких алгоритмов являются симметричные криптографические алгоритмы, перечисленные ниже: Простая перестановка, Одиночная перестановка по ключу, Двойная перестановка, Перестановка "Магический квадрат".Асимметричный шифр — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS, SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME. Пото́чный шифр — это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточный шифр реализует другой подход к симметричному шифрованию, нежели блочные шифры. Все методы криптоанализа поточных шифров обычно подразделяют на силовые (атака «грубой силой»), статистические и аналитические. Синхронные поточные шифры (СПШ) — в которых поток ключей генерируется независимо от открытого текста и шифротекста, АПШ – в которых поток ключей создаётся функцией ключа и фиксированного числа знаков шифротекста. Блочный шифр — разновидность симметричного шифра. Особенностью блочного шифра является обработка блока нескольких байт за одну итерацию (как правило 8 или 16).Блочные криптосистемы разбивают текст сообщения на отдельные блоки и затем осуществляют преобразование этих блоков с использованием ключа. К достоинствам блочных шифров относят похожесть процедур шифрования и расшифрования, которые, как правило, отличаются лишь порядком действий. Это упрощает создание устройств шифрования, так как позволяет использовать одни и те же блоки в цепях шифрования и дешифрования.

Абсолютно секретные сис-ы шифр.(одноразовый блокнотов) —с-ма симм. шиф-я, для которой доказана абсолютная криптографическая стойкость. Для шифрования открытый текст объединяется операцией «исключающее ИЛИ» с ключом (одноразовым блокнотом). При этом ключ должен обладать тремя критически важными свойствами: 1. быть истинно случайным; 2. совпадать по размеру с заданным открытым текстом; 3. применяться только один раз.

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

Построение п.п.ч. Недостатки классических генераторов псевдослучайных чисел 1)сравнительно короткий период генерируемой последовательности;2) зависимость между соседними последовательными значениями;3) неравномерность распределения значений

«Псевдослучайные» - из того, что если известно i-е число, то по формуле мы однозначно вычислим (i+1)-й элемент. Из рекуррентной природы формулы следует, что при одном и том же x0 мы получим при повторной генерации ту же самую последовательность. Все арифметические алгоритмы генерации псевдослучайных последовательностей периодичны

Любой генератор ППС должен быть инициализирован случайной величиной, неким внешним источником случайных значений. Методы – Линейный и Квадратичный конгруэнтный метод, Генератор на основе объединения путем конкатенации двух 16-битных генераторов на основе умножения с переносом. Период 2^16. Генераторы на основе умножения с переносом Период 2^160 Современные алгоритмы генерации п.с.ч.-. Вихрь Мерсена - иметь огромный период (2^19937-1) Алгоритм Блюма-Блюма-Шуба алгоритм стойкий к обратным реобразованиям. Алгоритмы «xor-shift» «умножения с переносом» Достаточно быстрый и имеет различные периоды начиная с 2^60. Недостаток - использование умножения. М-последовательности псевдослучайные последовательности, нашедшие широкое применение в широкополосных системах связи (CDMA).

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

Наиболее широко применяемыми на практике симметричными криптосистемами являются системы DES (стандарт США), IDEA (европейский стандарт), ГОСТ (стандарт РФ) и их модификации.

Одной из составляющих стандарта шифрования данных США 1999 г. является алгоритм TDEA («тройной» DEA). В алгоритме TDEA для зашифрования используется три ключа и трижды применяется алгоритм DEA:

Алгоритм ГОСТ с 256-битовым ключом, основанный на концепции алгоритма DEA, но более оптимальный для программной реализации;

В асимметричных криптосистемах (системах с открытым ключом) используется два ключа: открытый ключ – для шифрования и соответствующий ему секретный – для расшифрования. Например RSA.

Основным недостатком всех алгоритмов с окрытым ключом является медленное исполнение как в аппаратной, так и программной реализациях.

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

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

Дата добавления: 2015-11-14