Кодирование и шифрование. 4

Содержание 

1. Введение……………………………………………………………………....…3
2. Основные понятия кодирования и шифрования……………….…………......4
3. Способы кодирования информации..……………………………………….…5
1. Кодирование двоичным кодом……………………………….………….....6
2. Кодирование символьной информации………………….………………...7
3. Кодирование числовой информации………………………………….…...8
4. Кодирование текстовой информации……………………………………...9
5. Универсальное кодирование текстовой информации…………………...14
6. Кодирование графической информации………………………………….15
7. Кодирование звуковой информации………………………….………..…17
4. Шифрование……………………………………………………….……….….19
1. Виды шифров………………………………………………………………20
2. Надежность в шифровании……………………………………………..…21
3. Криптографические системы…………………………………………...…22
5. Заключение……………………………………………………………….…....24
6. Список литературы………………………………………………………...….25

Введение

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

     Одна  из наиболее важных задач (всего общества) – задача кодирования сообщений  и шифрования информации.

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

Основные понятия кодирования и шифрования

     Код – правило соответствия набора знаков одного множества Х знакам другого множества Y. Если каждому символу Х при кодировании соответствует отдельный знак Y, то это кодирование. Если для каждого символа из Y однозначно отыщется по некоторому правилу его прообраз в X, то это правило называется декодированием.

     Знак - это элемент конечного множества отличных друг от друга элементов.

     Кодирование – процесс преобразования букв (слов) алфавита Х в буквы (слова) алфавита Y.

     Сообщение, которое мы хотим передать адресату, назовем открытым сообщением. Оно, естественно, определено над некоторым алфавитом. Зашифрованное сообщение может быть построено над другим алфавитом. Назовем его закрытым сообщением. 

     Шифрование  - процесс преобразования открытого сообщения в закрытое сообщение.

     Шифр - какая-либо система преобразования текста (код) для обеспечения секретности передаваемой информации. 
 
 
 
 
 
 

Способы кодирования информации

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

     Кодирование двоичным кодом

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

     Своя  системы существует и в вычислительной технике – она называется двоичным кодированием и основана на представлении  данных последовательностью всего  двух знаков: 0 и 1. Эти знаки называют двоичными цифрами, по-английски – binary digit или сокращённо bit (бит). Одним битом могут быть выражены два понятия: 0 или 1 (да или нет, чёрное или белое, истина или ложь и т.п.). Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия. Тремя битами можно закодировать восемь различных значений.  
 
 
 
 
 
 
 

Кодирование символьной (текстовой) информации

     Основная  операция, производимая над отдельными символами текста - сравнение символов.

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

     Для кодирования текстов используются различные таблицы перекодировки. Важно, чтобы при кодировании  и декодировании одного и того же текста использовалась одна и та же таблица.

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

     Наиболее  популярные таблицы перекодировки: ДКОИ-8, ASCII, CP1251, Unicode.

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

     Различных комбинаций из 0 и 1 при длине кода 8 бит может быть 28 = 256, поэтому  с помощью одной таблицы перекодировки  можно закодировать не более 256 символов. При длине кода в 2 байта (16 бит) можно  закодировать 65536 символов. 
 
 
 
 

Кодирование числовой информации

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

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

Кодирование текстовой информации

     В настоящее время, большая часть  пользователей, при помощи компьютера обрабатывает текстовую информацию, которая состоит из символов: букв, цифр, знаков препинания и др. Подсчитаем, сколько всего символов и какое количество бит нам нужно: 10 цифр, 12 знаков препинания, 15 знаков арифметических действий, буквы русского и латинского алфавита, ВСЕГО: 155 символов, что соответствует 8 бит информации.

Единицы измерения информации:

1 байт = 8 бит

1 Кбайт  = 1024 байтам

1 Мбайт  = 1024 Кбайтам

1 Гбайт  = 1024 Мбайтам

1 Тбайт  = 1024 Гбайтам

     Суть  кодирования заключается в том, что каждому символу ставят в  соответствие двоичный код от 00000000 до 11111111 или соответствующий ему  десятичный код от 0 до 255.

     Основным  отображением кодирования символов является код ASCII – (American Standard Code for Information Interchange)- американский стандартный код обмена информацией, который представляет из себя таблицу 16 на 16, где символы закодированы в шестнадцатеричной системе счисления.

     В системе ASCII закреплены две таблицы кодирования: базовая и расширенная. Базовая таблица закрепляет значения кодов от 0 до 127, а расширенная относится к символам с номерами от 128 до 255.

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

     Кодировка символов русского языка, известная  как кодировка Windows-1251, была введена «извне» - компанией Microsoft, но, учитывая широкое распространение операционных систем и других продуктов этой компании в России, она глубоко закрепилась и нашла широкое распространение.

     Другая  распространённая кодировка носит  название КОИ-8 (код обмена информацией, восьмизначный) – её происхождение относится к временам Действия Совета Экономической Взаимопомощи государств Восточной Европы. Сегодня кодировка КОИ-8 имеет широкое распространение в компьютерных сетях на территории России и в российском секторе Интернета.

     Международный стандарт, в котором предусмотрена  кодировка символов русского языка, носит названия ISO (International Standard Organization – Международный институт стандартизации). На практике данная кодировка используется редко.  
 
 
 
 
 
 
 
 
 
 
 

     Ниже  приведены таблицы кодировки  ASCII и Windows-1251. 

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

     Существуют  несколько способов преобразования текста.

1. Переход от естественных обозначений к более компактным. Этот способ применяется для сжатия записи дат, номеров изделий, уличных адресов и т.д. Идея способа показана на примере сжатия записи даты. Обычно мы записываем дату в виде 10. 05. 01. , что требует 6 байтов памяти ЭВМ. Однако ясно, что для представления дня достаточно 5 битов, месяца- 4, года- не более 7, т.е. вся дата может быть записана в 16 битах или в 2-х байтах.
2. Подавление повторяющихся символов. В различных информационных текстах часто встречаются цепочки повторяющихся символов, например пробелы или нули в числовых полях. Если имеется группа повторяющихся символов длиной более 3, то ее длину можно сократить до трех символов. Сжатая таким образом группа повторяющихся символов представляет собой триграф S P N , в котором S – символ повторения; P – признак повторения; N- количество символов повторения, закодированных в триграфе. В других схемах подавления повторяющихся символов используют особенность кодов ДКОИ, КОИ-7, КОИ-8, заключающуюся в том , что большинство допустимых в них битовых комбинаций не используется для представления символьных данных.
3. Кодирование часто используемых элементов данных. Этот способ уплотнения данных также основан на употреблении неиспользуемых комбинаций кода ДКОИ. Для кодирования, например, имен людей можно использовать комбинации из двух байтов диграф PN, где P – признак кодирования имени, N – номер имени. Таким образом может быть закодировано 256 имен людей, чего обычно бывает достаточно в информационных системах. Другой способ основан на отыскании в текстах наиболее часто встречающихся сочетании букв и даже слов и замене их на неиспользуемые байты кода ДКОИ.
4. Посимвольное кодирование. Семибитовые и восьмибитовые коды не обеспечивают достаточно компактного кодирования символьной информации. Более пригодными для этой цели являются 5 - битовые коды, например международный телеграфный код МГК-2. Перевод информации в код МГК-2 возможен с помощью программного перекодирования или с использованием специальных элементов на основе больших интегральных схем (БИС). Пропускная способность каналов связи при передаче алфавитно-цифровой информации в коде МГК-2 повышается по сравнению с использованием восьмибитовых кодов почти на 40%.
5. Коды переменной длины. Коды с переменным числом битов на символ позволяют добиться еще более плотной упаковки данных. Метод заключается в том, что часто используемые символы кодируются короткими кодами, а символы с низкой частотой использования - длинными кодами. Идея такого кодирования была впервые высказана Хаффманом, и соответствующий код называется кодом Хаффмана. Использование кодов Хаффмана позволяет достичь сокращения исходного текста почти на 80%.

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

Универсальная система кодирования  текстовых данных

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

     Несмотря  на тривиальную очевидность такого подхода, простой механический переход  на данную систему долгое время сдерживался  из-за недостатков ресурсов средств  вычислительной техники (в системе  кодирования UNICODE все текстовые документы становятся автоматически вдвое длиннее). Во второй половине 90-х годов технические средства достигли необходимого уровня обеспечения ресурсами, и сегодня мы наблюдаем постепенный перевод документов и программных средств на универсальную систему кодирования. 
 
 
 
 

Кодирование графической информации

     Важным  этапом кодирования графического изображения  является разбиение его на дискретные элементы (дискретизация).

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

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

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

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

     Pixel (picture element - элемент рисунка) - минимальная единица изображения, цвет и яркость которой можно задать независимо от остального изображения.

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

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

     Для черно-белого изображения код цвета  каждого пикселя задается одним  битом.

     Если  рисунок цветной, то для каждой точки  задается двоичный код ее цвета.

     Поскольку и цвета кодируются в двоичном коде, то если, например, вы хотите использовать 16-цветный рисунок, то для кодирования  каждого пикселя вам потребуется 4 бита (16=24), а если есть возможность  использовать 16 бит (2 байта) для кодирования  цвета одного пикселя, то вы можете передать тогда 216 = 65536 различных цветов. Использование трех байтов (24 битов) для кодирования цвета одной точки позволяет отразить 16777216 (или около 17 миллионов) различных оттенков цвета - так называемый режим “истинного цвета” (True Color). Заметим, что это используемые в настоящее время, но далеко не предельные возможности современных компьютеров.

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

     При кодировании информации о цвете  с помощью восьми бит данных можно  передать только 256 оттенков. Такой  метод кодирования цвета называется индексным.  
 
 
 
 
 

Кодирование звуковой информации

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

1. Метод FM (Frequency Modulation) основан та том, что теоретически любой сложный звук можно разложить на последовательность простейших гармонических сигналов разных частот, каждый из которых представляет собой правильную синусоиду, а, следовательно, может быть описан числовыми параметрами, т.е. кодом. В природе звуковые сигналы имеют непрерывный спектр, т.е. являются аналоговыми. Их разложение в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальный устройства – аналогово-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях неизбежны потери информации, связанные с методом кодирования, поэтому качество звукозаписи обычно получается не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов с окрасом характерным для электронной музыки. В то же время данный метод копирования обеспечивает весьма компактный код, поэтому он нашёл применение ещё в те годы, когда ресурсы средств вычислительной техники были явно недостаточны.
2. Метод таблично волнового cинтеза (Wave-Table) лучше соответствует современному уровню развития техники. В заранее подготовленных таблицах хранятся образцы звуков для множества различных музыкальных инструментах. В технике такие образцы называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, некоторые параметры среды, в которой происходит звучание, а также прочие параметры, характеризующие особенности звучания. Поскольку в качестве образцов исполняются реальные звуки, то его качество получается очень высоким и приближается к качеству звучания реальных музыкальных инструментов.

    Шифрование

    Шифрование  - процесс преобразования открытого сообщения в закрытое сообщение.

    Если А – открытое сообщение, В – закрытое сообщение (шифр) , f – правило шифрования, то f(A) = B.

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

    При кодировании нет такого секретного ключа, так как кодирование ставит целью лишь более сжатое, компактное представление сообщения.

    Если  k – ключ, то можно записать f(k(A)) = B. Для каждого ключа k, преобразование f(k) должно быть обратимым, то есть f(k(B)) = A. Совокупность преобразования f(k) и соответствия множества k называется шифром .  
 
 
 
 
 
 

Виды  шифров

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

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

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

     По  этому признаку различают:

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

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

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

Надежность  в шифровании

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

     Пример: Один из лучших примеров алгоритма шифрования – принятый в 1977 году Национальным бюро стандартов США алгоритм стандарта шифрования данных DES (Data Encrypted Standard). Исследования алгоритма специалистами показали, что пока нет уязвимых мест, на основе которых можно было бы предложить метод криптоанализа, существенно лучший, чем полный перебор ключей. В июле 1991 года введен в действие аналогичный отечественный криптоалгоритм (стандарта ГОСТ 28147-89), который превосходит DES по надежности. 
 
 
 
 
 
 
 
 
 

     Криптографическая система

     Криптогpафическая система – семейство Х пpеобpазований откpытых текстов. Члены этого семейства индексиpуются, обозначаются символом k; паpаметp k является ключом. Множество ключей K – это набоp возможных значений ключа k. Обычно ключ пpедставляет собой последовательный pяд букв алфавита.

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

       Кpиптосистемы pазделяются на симметpичные, с откpытым ключом, и системы электронной подписи.

• В симметpичных кpиптосистемах, как для шифpования, так и для дешифpования, используется один и тот же ключ.
• В системах с откpытым ключом используются два ключа – откpытый и закpытый, котоpые математически (алгоритмически) связаны дpуг с дpугом. Инфоpмация шифpуется с помощью откpытого ключа, котоpый доступен всем желающим, а pасшифpовывается лишь с помощью закpытого ключа, который известен только получателю сообщения.
• Электpонной (цифpовой) подписью (ЭЦП) называется пpисоединяемое к тексту его кpиптогpафическое пpеобpазование, котоpое позволяет пpи получении текста дpугим пользователем пpовеpить автоpство и подлинность сообщения.

     К ЭЦП предъявляются два основных требования: легкость проверки подлинности подписи и высокая сложность подделки подписи.

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

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