Лекция 6. Анализ и синтез информационных систем. 11 страница

Полезност ь

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

Ценност ь

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

Кумулят ивпост ь

Свойство кумулятивности характеризует накопление и хранение информации.

Динамические свойства информации

Динамические свойства информации, как следует из самого названия, характеризуют динамику развития информации во времени.

Рост информации

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

Ст арение

Среди динамических свойств необходимо также отметить свойство старения информации.

Сообщение - это символы для информации, смысл которых нужно выучить. Понятия информации и сообщение являются основными понятиями при изучении теории информации. Сообщения в теории информации представляют собой носитель информации. Одну и туже информацию можно передать с помощью различных сообщений, например, на различных языках народов мира. Одно и тоже сообщение несет различную информацию. Например, «Весь июль будет жарким, осадков не ожидается». Для отдыхающих на море это сообщение несет информацию одного содержания, а для тружеников сельского хозяйства и жителей высокогорного района друтое содержание. Читая одни и те же стихи, каждый из читающих почерпнет информацию для себя. Редактор увидит в стихах мастерство поэта, а читателя больше заинтересует содержание произведения. Итак, из сказанного следует, что одно и тоже сообщение, несет различную информацию, в зависимости от того с каких позиций она рассматривается или по каким правилам интерпретируется. Ярким примером, поясняющим правила интерпретации, является криптография. В данном случае из сообщения извлекает информацию только тот, кто располагает ключом для дешифрации. Варианты возможных связей между сообщениями приведены в нижеперечисленных примерах.

1. 1. «Доброе утро», «Си!еп Могдеп»

2. 2. «А&В», «Микротекст»

3. 3. «Заболел дядя, тетя кашляет».

4. 4. «Кика гиги тое1»

5. 5. «Веселая Елена Снегина наш аптекарь»

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

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

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

Таблица 1

- - АКИНХЕТ

- - ОБСЙДЖЫ

- - ЯЙЗМФВС

Укажите для каждого случая способ расшифровки. Зашифруйте этими способами свою фамилию, имя, отчество

2. 2. С помощью частотного анализа применительно к русскому алфавиту докажите возможность расшифровки нижеследующей фразы кодом ЦЕЗАРЯ

ЕРТБЩЗЗ УФТЗОНЗПКЗЖЗНВЗФ СХФЭ МРТРФКО

3. 3. Шифровку, закодированную кодом ЦЕЗАРЯ, легче расшифровать с помощью вертикальных полосок, на которых расположен все буквы русского алфавита, двигая их механически при любом итоге можно подобрать осмысленный текст.

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

4. 4. 33 буквы русского алфавита дополнив тремя знаками - (.) точка, (,) запятая и () пробел представьте в виде матрицы 6*6, в которой каждому символу алфавита соответствует двоичное число. Зашифруйте этим кодом свою фамилию, имя, отчество.

5. 5. Расшифруйте текст, используя все известные способы (частотный анализ, код ЦЕЗАРЯ). Затем этим способом зашифруйте свою фамилию, имя, отчество ЫЧБТОЗМОАЛААБРАТТАЫ ВОЬДНАОМГНОЬУТЧИСЯ

СОДЕРЖАНИЕ ОТЧЕТА

1.Наименование, тема, цель работы.

2. 2. Представьте шифровки по п.1, 2, 3, 4, 5.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дайте определение понятию «информация».

2. Свойства информации.

3. Что такое «сообщение»?

4. Дайте определение понятию «язык».

5. Перечислите эффрекгоры и рецепторы человека и высших животных.

Лабораторная работа №> 7

Блочное кодирование.

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

Теоретические сведения.

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

Блоковый код называется равномерным, если и остается постоянным для всех букв сообщения.

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

Способность кода обнаруживать и исправлять обусловлена наличием избыточных символов. На вход кодирующего устройства поступает последовательность из 1с информационных двоичных символов. На выходе ей соответствует последовательность из и двоичных символов, причем п>к. Всего может быть 2**к различных входных последовательностей и 2**п различных выходных последовательностей. Из общего числа 2**п входных последовательностей только 2**к последовательностей соответствует входным, будем называть их разрешенными кодовыми комбинациями. Остальные (2**п)- (2**к) - есть запрещенные кодовые комбинации.

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

Рассмотрим механизм искажения кодовой комбинации.

Обозначим через Вй множество запрещенных комбинаций, Вй= (Ы, Ь2...}, а через А1 множество разрешенных комбинаций, Ай={а1, а2...} I - количество единиц в ошибочной комбинации, через Е1 множество всевозможных ошибочных комбинаций.

ВН равно сложению по модулю два А1 и Е1: Вй = AI + Е1 А1 + 2**к Вй+ (2**п)-<2**к)

Число всевозможных переходов разрешенных комбинаций в любые друтие комбинации равна (2**п) * (2**к), числу возможных переходов разрешенных в запрещенные комбинации равна 2**1с((2**п)-(2**к)).

Тогда относительное число обнаруживаемых ошибочных комбинаций Мош=2**к((2**п)-(2**1с)/(2**п)*{2**1с)=1-1/2**{п-1с)

Любой метод декодирования может рассматриваться как правило разбиения всего множества запрещенных кодовых комбинаций на 2**к непересекающихся подмножеств М, каждое из которых ставится в соответствие одной из разрешенных комбинаций. При получении запрещенной комбинации, принадлежащей подмножеству Ml принимается решение, что передавалась разрешенная комбинация А1.

Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из А1 то есть в 2**п-2**к случаях.

При наличии избыточности любой код способен исправлять ошибки.

Отношение числам исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно

N и сир - ((2**пХ2**к))/((2**к)((2**п)-(2**1с)))

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

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

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

Р = Сн*Рг*(1-Р)**(и-г)

Если учесть что Р«1, то в этом случае наиболее вероятны ошибки низшей кратности. Пример

Обнаружить и исправить ошибки при передаче следующих комбинаций: А1= 0001 А2=0101 А3=1110 А4=1110 Т - количество единиц в ошибочных комбинациях

передаче разрешенных кодовых комбинаций. В ней содержится все 2**п комбинация. Таким образом,* любая принятая комбинация идентифицирована.

Допустим, на приемной стороне получена кодовая комбинация 1100. Она относится к подмножеству МЗ, а так как МЗ относится к разрешенной комбинации A3, то на приемной стороне принимается решение, что была передана комбинация A3 и исправляется комбинация 1100 на 1110.

Содержание отчета

1. Постановка задачи.

2. Краткие теоретические сведения.

3. Текст программы.

4. Результаты работы программы.

Задание

Вывести на экран таблицу всех возможных комбинаций, таблицу неповторяющихся комбинаций, определить по введенному коду, какая кодовая комбинация была передана.

Контрольные вопросы.

1.Какие коды называют помехоустойчивыми?

2. За счет чего помехоустойчивый код получает способность обнаруживать и исправлять ошибки?

3. Охарактеризуйте блоковые и непрерывные, разделимые и неразделимые помехоустойчивые коды?

4. Что понимают под кратностью ошибки?

Лабораторная работа №8 ОСНОВЫ КРИПТОГРАФИИ Дан обзор алгоритмов, реализующих классическую технику криптографического кодирования. Рассмотрены основные понятия криптографии. Приведены задания к практическим работам.

Введение

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

Основные понятия

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

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

Алгоритмы с использованием ключа делятся на два класса: симметричные (или алгоритмы секретным ключом) и ассиметричные (или алгоритмы с открытым ключом). Разница в том, что симметричные алгоритмы используют один и тот же ключ для шифрования и для дешифрования (или же ключ для дешифровки просто вычисляется по ключу шифровки). В то время как асимметричные алгоритмы используют разные ключи, и ключ для дешифровки не может быть вычислен по ключу шифровки.

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

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

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

Вообще говоря, симметричные алгоритмы работают быстрее, чем ассиметричные. На практике оба типа алгоритмов часто используются вместе: алгоритм с открытым ключом используется для того, чтобы передать случайным образом сгенерированный секретный ключ, который затем используется для дешифровки сообщения.

Многие качественные криптографические алгоритмы доступны широко - в книжном магазине, библиотеке, патентном бюро или в Интернет. К широко известным симметричным алгоритмам относятся DES и IDEA, Наверное самым лучшим асимметричным алгоритмом является RSA.

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

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

Цифровые подписи также можно использовать для удостоверения (сертификации — to certify) того, что документ принадлежит определенному лицу. Это делается так: открытый ключ и информация о том, кому он принадлежит подписываются стороной, которой доверяем. При этом доверять подписывающей стороне мы можем на основании того, что ее ключ был подписан третьей стороной. Таким образом возникает иерархия доверия. Очевидно, что некоторый ключ должен быть корнем иерархии (то есть ему мы доверяем не потому, что он кем-то подписан, а потому, что мы верим a-priori, что ему можно доверять). В централизованной инфраструктуре ключей имеется очень небольшое количество корневых ключей сети (например, облеченные полномочиями государственные агенства; их также называют сертификационными агенствами — certification authorities). В распределенной инфраструктуре нет необходимости иметь универсальные для всех корневые ключи, и каждая из сторон может доверять своему набору корневых ключей (скажем своему собственному ключу и ключам, ею подписанным). Эта концепция носит название сети доверия (web of trust) и реализована, например, в PGP.

Классическая техника шифрования

Рассмотрим примеры использования классической техники шифрования. Это проиллюстрирует основные подходы, применяемые в традиционном шифровании и по сей день, а также поможет понять возможные контрмеры — соответствующие методы криптоанализа.

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

Применение подстановок

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

Шифр Цезаря

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

Открытый текст: meet me after the toga party

Шифрованный текст: PHHW РН DIWHU WKH WRJD SDUMB

Обратите внимание на то, что алфавит считается "циклическим", поэтому после Z идет А. Определить преобразование можно, перечислив все варианты, как показано ниже.

Открытый текст: abcdefghijklmnopqrstuvwxyz Шифрованный текст: DEFGHTJKLMNOPQRSTUYWXYZABC

Если каждой букве назначить числовой эквивалент (а=1, b = 2 и т.д.), то алгоритм можно выразить следующими формулами. Каждая буква открытого текста р заменяется буквой шифрованного текста С:

С = Е (р) = (р + 3) mod(26).

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

С = Е (р) = (р + k)mod(26), где к принимает значения в диапазоне от 1 до 25. Алгоритм дешифрования также прост:

р • D(С) = (С - k)mod(26).

Если известно, что определенный текст был шифрован с помощью шифра Цезаря, то с помощью простого перебора всех вариантов раскрыть шифр очень просто - для этого достаточно проверить 25 возможных вариантов ключей. На рис.1 показаны результаты применения этой стратегии к указанному выше сообщению. В данном случае открытый текст распознается в третьей строке.) • х^г/ Р(х) = (x⁶ + x⁵ + xV (х³ + х+1)= х³+х² + х+1+ 1/(х³ + х+1) I 1111 + 001/1011

При делении необходимо учитывать, что вычитание производится по модулю 2. Остаток суммируем с h(x) • х^г. В результате получим закодированное сообщение:

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

1. Известны алгоритмы шифрования и дешифрования.

2. Необходимо перебрать всего 25 вариантов.

3. Язык открытого текста известен и легко узнаваем.

В большинстве случаев, когда речь идет о защите сетей, можно предполагать, что алгоритм известен. Единственное, что делает криптоанализ на основе метода последовательного перебора практически бесполезным — это применение алгоритма, для которого требуется перебрать слишком много ключей. Например, алгоритм DES(Data Encryption Standard), использующий 56 - битовые ключи, требует при последовательном переборе рассмотреть пространство из 2, или более чем 7 х 10¹⁶ ключей.

Третья характеристика также важна. Если язык, на котором написан открытый текст, неизвестен, то расшифрованный текст можно не распознать. Более того, исходный текст может состоять из сокращений или быть каким-либо образом сжат - это также затрудняет распознавание. Например, на рис.2 показан фрагмент текстового файла, сжатого с помощью широко известного алгоритма ZIP. Если теперь этот файл зашифровать с помощью простого подстановочного шифра (необходимо лишь расширить шифр, чтобы он включал все символы, а не только 26 букв), то при использовании метода последовательного перебора вариантов расшифрованный текст распознать будет очень сложно.

~+ИГ- П-0)<4 {ооф, e~Q%rau-"I 0~Z-

й*20#АаеЭ ce«q7.Qn-®3NOti CEz 'Y-/⁰⁰l [±C eQ,<NO-d«^vxa Аа£ёйЗА x}o§k^sA

yl' ~AE1.и J/'iTe&i 'с<иП- "AD(GWAC~y ioAW POi«tUtg"|,n. ^vI^AuNrc~ = ~L"90gllCr&CE< -i<06§":

~(E!SGqevo~ u\,3>1к-*60Ф%х^п' fi'6#=~myfe>^v>nP<,/i Aj AO<i,"Zu- Q"0~6CEy{% „£>Ё6 Д 71-Ai°u02gSy'0-

2A11Si /{5)^л,,ПК^Р(Е71,йё^л,31^б^,,бгТ^,,У^ЛШоеУ> Q+ео/ ' <KӘr*+~ "<u~ В ZOK-QJyu/. lOfltzsS/] >EQ u

Puc. 2. Пример еж ат ого т екст а

Моноалфавитные шифры

При наличии всего 25 возможных вариантов ключей шифр Цезаря далек от того, чтобы считаться надежно защищенным. Существенного расширения пространства ключей можно добиться, разрешив использование произвольных подстановок. Давайте еще раз вспомним шифр Цезаря.

Открытый текст: abcdefghij klmnopqrstuvwxyz Шифрованный текст: DEFGHIJKLMNOPQRSTUVWXYZABC

Если в строке "Шифрованный текст" допустить использование любой из перестановок 26 символов алфавита, то мы получим 26!, или более чем 4 х 10^[1] возможных ключей. Это на 10 порядков больше, чем размер пространства ключей DES, и это кажется достаточным для того, чтобы сделать невозможным успешное применение криптоанализа на основе метода последовательного перебора.

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

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

На первом этапе можно определить относительную частоту появления в тексте различных букв и сравнить их со среднестатистическими данными для букв английского языка, показанными на рис.З.

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

Сравнивая эти результаты с данными, показанными на рис.З, можно заключить, что, скорее всего, буквы Р и Z шифрованного текста являются эквивалентами букв е и t открытого текста, хотя трудно сказать, какой именно букве — Р или Z — соответствует е, а какой — t. Буквы S, U, О, М и Н, обладающие относительно высокой частотой появления в тексте, скорее всего, соответствуют буквам из множества (г, n, i, о, a, s}. Буквы с низкой частотой появления (а именно А, В, G, Y, I, J), по-видимому, соответствуют буквам множества {w,v,b,k, x,q, j, z}.

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

Один из очень эффективных методов заключается в подсчете частоты использования комбинаций, состоящих из двух букв. Такие комбинации называют биграммами. Для значений относительной частоты появления в тексте биграмм тоже можно построить гистограмму, подобную показанной на рис.З. Известно, что в английском языке самой распространенной является биграмма th. В нашем шифрованном тексте чаще всего (три раза) встречается комбинация ZW. Поэтому можно предположить, что Z соответствует t, a W — h. Тогда из ранее сформулированной гипотезы вытекает, что Р соответствует е. Заметим, что в шифрованном тексте буквосочетание ZWP имеется, и теперь мы можем представить его как the. В английском языке the является самой распространенной триграммой (т.е. комбинацией из трех букв), поэтому можно надеяться, что мы движемся в правильном направлении.

Не нашли, что искали? Воспользуйтесь поиском: