Файл: Лабораторная работа 1 Защита документов ms office Цель изучить методы защиты документов ms office, правила создания сложных паролей.pdf

6.
Проверить результат.
Дополнительное задание
Написать программу шифрования текста сообщения рассмотренными методами на любом языке программирования.
Отчет оформить в печатном и электронном видах. Продемонстрировать работу программы на произвольном сообщении
Контрольные вопросы:
1.
Укажите, на какие виды делятся существующие криптосистемы?
2.
Охарактеризуйте криптосистемы с открытым ключом
3.
Поясните, на каких математических принципах основана криптосистема RSA
4.
Расскажите, когда и кем была разработана система RSA, где она используется?
5.
Приведите алгоритм вычисления ключей в системе RSA
6.
Приведите алгоритм шифрования сообщения в системе RSA
7.
Приведите алгоритм дешифрования сообщения в системе RSA
8.
Охарактеризуйте принципы ЭЦП
9.
Поясните, чем различаются алгоритмы RSA и ЭЦП

Лабораторная работа №10 Методы сжатия.
Алгоритм Шеннона - Фано
Цель: ознакомиться с общими принципами сжатия информации с использованием метода Шеннона
- Фано
Эффективное кодирование информации. Общие положения
Напомним, что кодирование – это представление сообщений в форме, удобной для передачи по данному каналу, а декодирование – восстановление информации по принятому сигналу. Одним из важнейших вопросов кодирования является повышение его эффективности, т.е. путем устранения избыточности снижение среднего числа символов, требующихся на букву сообщения. Такое кодирование получило название
эффективное кодирование. Из сказанного выше следует, что
эффективное кодирование решает задачу максимального
сжатия информации.
Эффективное кодирование базируется на
основной теореме Шеннона для канала без
помех, суть которой сводится к следующему:
сообщения, составленные из букв некоторого алфавита, можно закодировать так,
что среднее число двоичных символов на букву сколь угодно близко к энтропии
источника этих сообщений, но не меньше этой величины.
Наличие в сообщениях избыточности позволяет рассматривать вопрос о сжатии данных, т.е. о передаче того же количества информации с помощью последовательностей символов меньшей длины – методы сжатия без потерь (обратимые). Для этого используют специальные алгоритмы сжатия, уменьшающие избыточность.
Эффект сжатия оценивают
коэффициентом
сжатия:
K=n/q где
n – число минимально необходимых символов для передачи сообщения;
q – число символов в сообщении.
Так, при эффективном двоичном кодировании
n равно энтропии источника информации.
Наряду с методами сжатия, не уменьшающими количество информации в сообщении применяют методы сжатия основанные на потере малосущественной информации, - методы сжатия с потерями (необратимые). Следует отметить, что применение методов сжатия с потерями не приемлемо для некоторых видов информации, например, текстовой или числовой.
Обратимое сжатие всегда приводит к снижению объема выходного потока информативности. Из выходного потока при помощи восстанавливающего алгоритма можно получить исходный поток.
Основные методы обратимого сжатия:
✓
Шеннона – Фано;
✓
Хаффмена;
✓
LZW (Lanper – Ziv – Welch);
✓
арифметическое сжатие.
Основные методы необратимого сжатия:
✓
MPEG (Moving Pictues Experts Group);
✓
JPEG (Joint Photographic Expert
Group);
✓
фрактальное сжатие.

Наибольшее распространение среди методов сжатия информации без потерь нашли
статистические алгоритмы сжатия, учитывающие вероятность появления отдельных символов в информационном потоке. В первую очередь это алгоритмы Шеннона – Фано и
Хаффмена.
Алгоритм Шеннона – Фано. Эффективное кодирование базируется на основной теореме Шеннона для канала без помех.
✓
Буквы алфавита сообщений вписываются в таблицу в порядке убывания вероятностей;
✓
Буквы алфавита разделяются на две группы так, чтобы суммы вероятностей в каждой группе были по возможности одинаковы (максимально близки); в группе может быть любое число символов, в том числе – один;
✓
Всем буквам верхней половины в качестве первого символа приписывается единица (1), а всем нижним – нули;
✓
Каждая из полученных групп в свою очередь разбивается на две подгруппы с одинаковыми суммарными вероятностями и т.д. процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Процедура кодирования по методу Шеннона - Фано иллюстрируется таблицей.
Буква
Вероятность появления буквы в сообщении Р(λ
i
)
I
II
III
IV
V
Kод
n
i
⋅ P
i
А
0,6 1
1 0,6
Б
0,2 0
1 1
011 0,6
В
0,1 0
010 0,3
Г
0,04 0
1 001 0,12
Д
0,025 0
1 0001 0,1
Е
0,015 0
00001 0,075
Ж
0,01 1
000001 0,06
З
0,01 0
000000 0,06
Для полученного таким образом кода среднее число двоичных символов, приходящихся на одну букву, равно
7
n =
∑
n
i
P
i
≈
1.9,
i=
0
Основные информационные характеристики источника сообщения:
✓
энтропия источника - источник может быть охарактеризован средним количеством
информации, приходящимся на одно элементарное сообщение, носящим название
“энтропия источника” и определяемым следующим образом:
K

H(
λ
) = −
∑
i=
1
P(
λ
i
)⋅ log P(
λ
i
), i = 1, K.;
H
(
λ
)
= 1,781.
H
(
λ
)
✓
избыточность источника
ρ
Џ
= 1− log K
; где H(λ) - энтропия реального источника, log K - максимально достижимая энтропия для источника с объемом алфавита в К символов
✓
среднее число символов на букву в коде
7
n =
∑
n
i
P
i
≈
1.9;
i=
0
✓
избыточность кода
ρ
k
=
1−
≈
0.06,.
Выполнить практическое задание:
Задача 1. Построить код по алгоритму Шеннона – Фано для списка сообщений с заданным распределением вероятностей. Определить среднее число двоичных символов, приходящихся на одну букву
S
T
U
V
W
X
Y
Z
1
0,08 0,1 0,15 0,15 0,3 0,05 0,12 0,05
2
0,15 0,1 0,15 0,15 0,1 0,1 0,15 0,1
3
0,15 0,02 0,25 0,15 0,08 0,15 0,2
-
4
0,02 0,25 0,04 0,01 0,4 0,1 0,03 0,15
5
0,15 0,2 0,08 0,12 0,15 0,1 0,1
-
6
0,07 0,04 0,3 0,1 0,07 0,12 0,3
-
Рассмотрим пример использования алгоритма Шеннона – Фано для кодирования произвольного
текстового сообщения (рис. 1, 2)
Построить код по алгоритму Шеннона – Фано для сообщения
А КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ
Определить среднее число двоичных символов, приходящихся на одну букву.
Решение:
1.
Вычислить общее количество символов в сообщении (диапазон B4:C31)
2.
Выбрать символы без повторений (диапазон D2:K3)
3.
Вычислить, сколько раз каждая буква и пробел используется в сообщении (диапазон
D4:K31)

Рис. 1. Вычисление количества букв и вероятностей
4.
Вычисления в диапазоне D33:K33 – в ячейке D33 использовать формулу
=СУММ(D4:D32), скопировать формулу на диапазон;
5.
Вычисления в диапазоне D34:K34 – в ячейке D34 использовать формулу =D33/28, скопировать формулу на диапазон;
6.
Вычисления в диапазоне D34:K34 – в ячейке D34 использовать формулу =D33/28, скопировать формулу на диапазон;
7.
Вычисления в ячейке L33 - использовать формулу =СУММ(D33:K33);
8.
Вычисления в ячейке L34 - использовать формулу
=СУММ(D34:K34);
9.
Вычисления в ячейке О16 - использовать формулу
=СУММ(О8:О15);
10.
Вычисления в ячейке U16 - использовать формулу
=СУММ(U8:U15).
11.
Самостоятельно
Рис.
2.
Алгоритм
Шеннона
–
Фано
записат
ь итоговые коды.
Выполнить практическое задание:
Задача 2. Построить код по алгоритму Шеннона – Фано для сообщения

ВОТ ВИДИТЕ, ЧТО НИЧЕГО НЕ ВИДИТЕ, А ПОЧЕМУ - СКОРО
УВИДИТЕ
Определить среднее число двоичных символов, приходящихся на одну букву.
Задача 3. Построить код по алгоритму Шеннона – Фано для произвольного сообщения
(не менее 25-30 символов). Определить среднее число двоичных символов, приходящихся на одну букву.
Контрольные вопросы:
1.
Охарактеризуйте понятие «эффективное кодирование»
2.
Поясните суть основной теоремы Шеннона для канала без помех
3.
Поясните, каким образом вычисляется коэффициент сжатия
4.
Перечислите основные методы обратимого сжатия
5.
Перечислите основные методы необратимого сжатия
6.
Опишите порядок кодирования сообщений с помощью алгоритма Шеннона – Фано
7.
Перечислите основные информационные характеристики источника сообщения
8.
Поясните понятие энтропия источника
9.
Поясните, каким образом вычисляется среднее число символов на букву в коде по алгоритму Шеннона - Фано
10.
Поясните алгоритм построения кода для произвольного сообщения по алгоритму
Шеннона - Фано
11.
Поясните, как вычислить вероятность появления каждой буквы в произвольном сообщении
Справочный материал к практической работе
№10
Количественная характеристика информации В большинстве работ по теории информации основное внимание уделяется той ее характеристике, которая получила название
объем
информации.Работ, в которых анализируются другие стороны, характеристики и свойства информации, совсем немного.
Основными
методами
определения
объема
информации
являются: ✓ комбинаторный,
✓ статистический,
✓ алгоритмическ ий,
✓ метрически й.
Все эти методы исходят из принципа разнообразия состояний информационной системы.
При комбинаторном методе используют разнообразие множества характеристик объекта Х по признакам его элементов х,
при статистическом методе — по вероятности наступления некоторого состояния х∈X, и
при метрическом — используют возможные значения х некоторой измеримой величины X. Единство подходов позволяет сравнительно легко переходить от одной меры информации к другой.
В соответствии с определением
Р.
Хартли считается, что объем информации I, получаемый об объекте или системе, тем больше, чем выше разнообразие их возможных состояний:

I=K
lnN, где К — коэффициент пропорциональности, обусловленный избранной мерой объема информации (при К = 1 информация измеряется в натуральных единицах, при К = (ln2)
-1
=
1,443 — в битах, при К= (ln10)
-1
= 0,4343 — в десятичных единицах); N — число возможных различных (дискретных) состояний или возможных сообщений о системе или объекте.
Формула Хартли более известна в виде I=log
2
N
Комбинаторная логарифмическая мера объема информации по
Р.Хартли очень проста для вычисления и удобна при аналитических расчетах из-за свойства аддитивности логарифмической функции. Но она же инвариантна относительно любых свойств информации, безразмерна и потому не чувствительна к содержанию информации, не учитывает различий между разными сообщениями или состояниями системы (почти невероятному сообщению придается такое же количественное значение информации, как и весьма правдоподобному).
Эти свойства делают комбинаторную меру объема информации по Р.Хартли практически бесполезной в задачах исследования проблем, для которых существенны не только количественные характеристики неравновероятных сообщений, но и смысловое содержание этих сообщений. В частности, такая мера не адекватна исходным условиям большинства задач анализа ИБ сложных систем.
В статистическом методе используют энтропийный подход. При этом объем информации оценивается мерой уменьшения у получателя неопределенности (энтропии) выбора или ожидания событий после получения информации. Объем информации тем больше, чем ниже вероятность события.
Энтропийный подход широко используют при определении объема информации, передаваемого по каналам связи. Выбор при приеме информации осуществляется между символами алфавита в принятом сообщении. Пусть сообщение, принятое по каналу связи, состоит из N символов (без учета связи между символами в сообщении). Тогда объем информации

отображение f: Х'
→
Х*, такое что f(х) совпадает с результатом применения алгоритма к объекту х. Тогда f называется
вычислимой функцией,которая задается алгоритмом.
Пусть теперь рассматривается некоторое исходное множество объектов, причем устанавливается взаимно однозначное соответствие между этим множеством и множеством двоичных слов конечной длины, т.е. слов вида х = x
1
х
2
…х
n
, где х
i
есть 0 или 1, i
∈
1,
..., п. Установленное соответствие между множествами позволяет в дальнейшем в качестве объектов без существенного ограничения общности рассматривать только двоичные слова.
Модуль |х| обозначает длину слова х. Конечное двоичное слово можно записать так, что его возможно будет восстановить по его описанию. Например, слово 110001100011000 соответствует тексту: две единицы, три нуля, повторенные трижды. Разные слова имеют различные описания, но одно слово может иметь множество описаний. Сравним между собой описания двоичного слова для того, чтобы выбрать из них самое простое. Описание двоичного слова х задается не в произвольной словесной форме, а в виде двоичного слова — аргумента некоторой (пока фиксированной) вычислимой функции f. Пока на f не накладывается никаких ограничений: она может быть определена не на всех двоичных аргументах. Не для каждого двоичного слова х имеется двоичный прообраз (такое слово р, что f(p) = х).
Для некоторого двоичного слова x
существует множество Р
f
(х) всех двоичных слов, таких что f(p) = x
(
ЭТО множество для данной функции f может оказаться и пустым). Пусть
K
f
(x)
можно назвать сложностью слова х по функции f.
Таким образом, сложность слова х по f — это длина самого короткого двоичного слова, в котором содержится полное описание слова х при фиксированном способе восстановления слов по их описаниям (т. е. при фиксированной функции f). Если для данного способа восстановления такого описания не существует, то сложность слова х по f считается бесконечно большой.
Возможны и другие определения информации, употребляемые в частных приложениях и еще менее полезные для описания информационных процессов в сложных организационных и организационно-технических системах (информационная мера сложности структурно- функциональной модели описания объекта по А.В. Шилейко и В.Ф.Кочневу, информационная мера неопределенности принятия решения по Н.Н.Моисееву).
Другая разновидность определения объема информации —
тезаурусный
подход. Согласно этому подходу, предложенному Ю.А. Шрейдером, объем информации, извлекаемый человеком из сообщения, можно оценить степенью изменения его знаний.
Структурированные знания, представленные в виде понятий и отношений между ними, называются
тезаурусом. Структура тезауруса иерархическая. Понятия и отношения, группируясь, образуют другие, более сложные понятия и отношения.
Количество информации, энтропия источника сообщений
Для сравнения между собой различных источников сообщений необходимо ввести некоторую количественную меру, которая дала бы возможность объективно оценить информацию, содержащуюся в сообщении. Такая мера впервые была введена K.
Шенноном в 1948 г., а затем более строго определена А.Я. Хинчиным. Рассмотрим основы информационного подхода Шеннона.
Всякая информация получается потребителем после приема сообщения, то есть в результате опыта. Сообщение, получаемое на приемной стороне, несет полезную информацию лишь в том случае, если имеется неопределенность относительно состояния источника. Если опыт может закончиться только одним исходом и наблюдатель заранее знает исход опыта, то по его результату он не получает никакой информации. Например, если сообщат, что солнце всходит на востоке, то никакой информации это сообщение не принесет, поскольку все знают, что это верно. В таком событии, как ежедневный восход солнца на востоке, нет ничего неопределенного, вероятность этого события равна единице и количество информации,