Конспект лекций для студентов, магистров и аспирантов всех специальностей
| Вид материала | Конспект |
- Конспект лекций бурлачков в. К., д э. н., проф. Москва, 1213.67kb.
- Конспект лекций для студентов всех специальностей дневной и заочной формы обучения, 1439.07kb.
- Курс лекций (для магистров всех специальностей Академии) харьков − 2006, 1136.42kb.
- Конспект лекций по курсу основы алгоритмизации и программирования для студентов всех, 3059.86kb.
- Конспект лекций по курсу Начертательная геометрия (для студентов заочной формы обучения, 1032.28kb.
- Конспект лекций для студентов по специальности i-25 01 08 «Бухгалтерский учет, анализ, 2183.7kb.
- Конспект лекций по курсу "Начертательная геометрия и инженерная графика" Кемерово 2002, 786.75kb.
- Конспект лекций по дисциплине «Маркетинг», 487.79kb.
- Конспект лекций для студентов специальности 080110 «Экономика и бухгалтерский учет, 1420.65kb.
- Конспект лекций по культурологии Для студентов всех специальностей, 4611.53kb.
Защита информации от случайных помех. Код Р. Хэмминга.
Рассмотрим некоторый алфавит, в котором n=2 m букв. Если буквы появляются в текстах равновероятно, то минимальное количество двоичных символов на одну букву совпадает с H бит на символ и равно m (максимально плотная кодировка). При сбое декодировать такой текст невозможно. Чтобы контролировать ошибки, вводим x дополнительных двоичных позиций под каждую букву. События – ошибок в коде буквы нет, ошибка в первой позиции, ошибка во второй позиции, и так далее, ошибка в позиции m+x – считаем равновероятными. Тогда минимальное количество символов под кодирование одной буквы с контрольными символами x должно определиться количеством информации
H=log2 (1+m+x).
Но чтобы получить информацию об ошибках после кодирования буквы (или после передачи по каналу связи) нужно иметь информацию в x бит, которая была бы не менее количества информации H:
x log 2 (1+m+x).
Из этого неравенства вытекает, что должно быть
2x – x –1 m.
Например, если x=3, то m можно выбрать равным четырём. Итого имеем семь двоичных позиций под букву, из них четыре позиции – информационные, а три – контрольные. Обозначим эти позиции
b1 b2 b3 b4 b5 b6 b7
По Р. Хэммингу позиции
b1 b2 b4
нужно выбрать контрольными (мнемоническое правило: номера контрольных позиций это целые степени двойки 0, 1, 2), а позиции b3 b5 b6 b7 - информационными. Содержимое контрольных позиций должно определяться содержимым информационных позиций. По Р. Хэммингу контрольные позиции заполняются по правилу:
b 1 = b 3+b 5+b 7 mod 2
b 2 = b 3 +b 6 +b 7 mod 2 (Х1)
b 4 = b 5 +b 6 +b 7 mod 2
Тогда (s1 s2 s3) будет двоичным кодом той ячейки, где содержится ошибка, и этот код должен вычисляться по правилу:
s1 = b 4 + b 5 +b 6 +b 7 mod 2
s2 = b 2 + b 3 +b 6 +b 7 mod 2 (Х2)
s 3 = b 1 + b 3+b 5+b 7 mod 2
Если ошибки нет, то (s1 s2 s3)= (0 0 0) .
Если в уравнениях (Х2) заменить символы
b1 b2 b3 b4 b5 b6 b7
номерами их позиций в двоичной кодировке:
1 (001) 2(010) 3(011) 4(100) 5(101) 6(110) 7(111) ,
то получим, что (s1 s2 s3)= (0 0 0) . В этом случае из уравнений (Х2) вытекают уравнения (Х1) на правило заполнения контрольных позиций.
Пример:
Пусть некоторая буква алфавита имеет код:
b3 b5 b6 b7 = 1 0 0 1
Находим контрольные символы по формулам (Х1):
b 1 b 2 b 4 = 0 0 1
Тогда расширенная кодировка буквы имеет вид:
b1 b2 b3 b4 b5 b6 b7 = 0 0 1 1 0 0 1 (X3)
Подсчитываем s1 , s2 , s3 по формулам (Х2) . Получаем, что (s1 s2 s3)= ( 0 0 0 ).
Допустим, что в третьей позиции кода Х(3) возникла по какой-то причине ошибка, и код стал таким:
b1 b2 b3 b4 b5 b6 b7 = 0 0 0 1 0 0 1 (Х4)
Вычисляем s1 ,s2, , s3 для кода (Х4) по формулам ( Х2). В результате имеем:
s1 = ( b 4 + b 5 +b 6 +b 7 mod 2 ) = 0
s2 = ( b 2 + b 3 +b 6 +b 7 mod 2 ) = 1
s 3 = ( b 1 + b 3+b 5+b 7 mod 2 ) = 1
Получили, что (s1 s2 s3)= (011) – это двоичный адрес третьей ячейки, где возникла ошибка. Таким образом, код Р. Хэмминга позволяет прогнозировать и исправить одиночную ошибку. Код Р. Хэмминга обобщается на произвольные алфавиты и позволяет исправлять не только одиночные ошибки кодов отдельных букв, но и кратные ошибки. Кроме того, дополнительные биты в схеме Р. Хэмминга
используют и для шифрования информации. Это отдельное направление защиты информации, которое мы не рассматриваем.
^ Из истории криптографии.
История криптографии связана с большим количеством дипломатических и военных тайн и поэтому окутана туманом легенд.
Свой след в истории криптографии оставили многие хорошо известные исторические личности. Приведём наиболее яркие примеры. Первые сведения об использовании шифров в военном деле связаны с именем спартанского полководца Лисандра (шифр “Сцитала”). Цезарь использовал в переписке шифр, который вошёл в историю как шифр “Цезаря”. В более поздние времена шифров было изобретено очень много и мы на них не останавливаемся.
Шифр “Сцитала” известен со времён войны Спарты против Афин в V веке до н. э. Для его реализации использовалась сцитала – жезл, имеющий форму цилиндра. На сциталу виток к витку наматывалась узкая папирусная лента (без просветов и нахлёстов), а затем на этой ленте вдоль оси сциталы записывался открытый текст. Лента разматывалась и получалось (для непосвящённых), что поперёк ленты в беспорядке написаны какие-то буквы. Затем лента отправлялась адресату. Адресат брал такую же сциталу, таким же образом наматывал на неё полученную ленту и читал сообщение вдоль оси сциталы. Отметим, что в этом шифре преобразование открытого текста в зашифрованный заключается в определённой перестановке букв открытого текста. Поэтому класс шифров, к которым относится и шифр «Сцитала», называется шифрами перестановки.
Шифр Цезаря реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после неё буквой в алфавите, который считается написанным по кругу, т. е. после буквы «z» следует буква «а». Отметим, что Цезарь заменял букву третьей после неё буквой, но можно заменять и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига. Класс шифров, к которым относится и шифр Цезаря, называется шифрами замены.
^ Математические основы шифрования.
Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией.
Принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона «Математическая теория связи». В своей работе «Теория связи в секретных системах» Клод Шеннон обобщил накопленный до него опыт разработки шифров.
^ Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания.
Шифр замены.
Легко дать математическое описание шифра замены.
Пусть X и Y – два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также g: X Y – взаимно однозначное отображение X в Y. Тогда шифр замены действует так: открытый текст
x 1 x 2...x n
преобразуется в шифрованный текст
g ( x )g (x 2)...g(x n ).
^ Шифр перестановки.
Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр «Сцитала». Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна n и - взаимнооднозначное отображение множества {1, 2, …,n} в себя. Тогда шифр перестановки действует так: отрезок открытого текста
x 1 x 2 ... x n преобразуется в отрезок шифрованного текста
x , x , …, x .
σ(1) σ(2) σ(n)
Важнейшим для криптографии был результат К. Шеннона о существововании и единственности абсолютно стойкого шифра..