2 Программирование на языке высокого уровня



страница16/29
Дата29.11.2016
Размер3.73 Mb.
Просмотров7173
Скачиваний0
1   ...   12   13   14   15   16   17   18   19   ...   29

Требования


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

  • Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m должно быть вычислительно невозможно найти блок данных x, для которого {h(x)=m}.

  • Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого h(n)=h(m).

  • Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений ~(m, m\'), имеющих одинаковый хеш.

Данные требования не являются независимыми:

  • Обратимая функция нестойка к коллизиям первого и второго рода.

  • Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Атака «дней рождения» позволяет находить коллизии для хеш-функции с длиной значений n битов в среднем за примерно 2^{n/2}вычислений хеш-функции. Поэтому n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2^{n/2}.

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

Итеративная последовательная схема


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

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

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

Сжимающая функция на основе симметричного блочного алгоритма


В качестве сжимающей функции можно использовать симметричный блочный алгоритм шифрования. Для обеспечения большей безопасности можно использовать в качестве ключа блок данных предназначенный к хешированию на данной итерации, а результат предыдущей сжимающей функции в качестве входа. Тогда результатом последней итерации будет выход алгоритма. В таком случае безопасность хеш-функции базируется на безопасности используемого алгоритма. Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них — MD5, SHA-1, SHA-2и ГОСТ Р 34.11-94).

149. Поточные шифры и генераторы псевдослучайных чисел.


Поточные шифры


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

 принцип работы поточного шифра

Генератор ключей выдает поток битов ki, которые будут использоваться в качестве гаммы. Источник сообщений генерирует биты открытого текста хi, которые складываются по модулю 2 с гаммой, в результате чего получаются биты зашифрованного сообщения уi:



y_i = x_i \oplus k_i, i=1,2,…,n

Чтобы из шифротекста y1, y2,..., yn восстановить сообщение x1, x2,..., xn, необходимо сгенерировать точно такую же ключевую последовательность k1, yk,..., kn, что и при шифровании, и использовать для расшифрования формулу



x_i = y_i \oplus k_i,\ i=1,2,…,n

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


Линейный конгруэнтный генератор псевдослучайных чисел


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

ki=(a*ki-1+b)mod c,

где а, b, с — некоторые константы, a ki-1 — предыдущее псевдослучайное число. Для получения k1 задается начальное значение k0.

Метод Фибоначчи с запаздываниями (Lagged Fibonacci Generator) — один из методов генерации псевдослучайных чисел. Он позволяет получить более высокое "качество" псевдослучайных чисел.

Известны разные схемы использования метода Фибоначчи с запаздыванием. Один из широко распространённых фибоначчиевых датчиков основан на следующей рекуррентной формуле:



http://www.intuit.ru/department/security/bcript/7/7_3.jpg

где ki — вещественные числа из диапазона [0,1], a, b — целые положительные числа, параметры генератора. Для работы фибоначчиеву датчику требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел необходим некоторый объем памяти, зависящих от параметров a и b.


Генератор псевдослучайных чисел на основе алгоритма BBS


Широкое распространение получил алгоритм генерации псевдослучайных чисел, называемый алгоритмом BBS (от фамилий авторов — L. Blum, M. Blum, M. Shub) или генератором с квадратичным остатком. Для целей криптографии этот метод предложен в 1986 году.

Он заключается в следующем. Вначале выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4, то есть при делении p и q на 4 должен получаться одинаковый остаток 3. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое (то есть не имеющее общих делителей, кроме единицы) с М. Вычисляем х0= х2mod M. х0 называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется хn+1= хn2 mod M. Результатом n-го шага является один (обычно младший) бит числа хn+1. Иногда в качестве результата принимают бит чётности, то есть количество единиц в двоичном представлении элемента. Если количество единиц в записи числа четное – бит четности принимается равным 0, нечетное – бит четности принимается равным 1.

Генераторы псевдослучайных чисел на основе сдвиговых регистров с обратной связью


Сдвиговые регистры с обратной связью могут применяться для получения потока псевдослучайных бит. Сдвиговый регистр с обратной связью состоит из двух частей: собственно n-битного сдвигового регистра и устройства обратной связи

 сдвиговый регистр с обратной связью

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

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


Использование режимов OFB и CTR блочных шифров для получения псевдослучайных чисел


Можно использовать любой блочный алгоритм, например AES или ГОСТ 28147-89, для поточного шифрования информации, используя режимы OFB и CTR блочных шифров.

Название режима OFB (Output FeedBack) переводится как "обратная связь по выходу".

Пусть минимальный блок данных, используемый для передачи, состоит из j бит; обычным значением является j=8 (то есть минимальной порцией передаваемых данных является 1 байт). В режиме OFB блочный шифр f на основе секретного ключа К и некоторого инициализирующего значения Y0 формирует псевдослучайную последовательность j-битовых чисел z1,z2,...,zk, которая затем может использоваться в качестве гаммы для шифрования сообщения. Результат зашифрования является входом процедуры шифрования следующего блока исходного сообщения. На каждом этапе шифрования из зашифрованного блока Yi выбирается j младших битов.

Таким образом, для получения псевдослучайной последовательности используется схема:

Yi=f(Yi-1,K),

zi=j младших бит Yi, 1<=i<=k

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

Генераторы настоящих случайных чисел в криптографии


Генераторы ПСЧ находят широкое применение в криптографии, например, при потоковом шифровании. Однако иногда бывает необходимо генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (random number generator) или сокращённо ГСЧ (RNG). Генератор настоящих случайных чисел в зависимости от некоторого инициализирующего значения выдает последовательность, которая не может быть впоследствии повторена.

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



  • количество импульсов счетчика Гейгера за единицу времени, например, за одну секунду;

  • числа, оказывающиеся на верхней грани игрального кубика при произвольном броске;

  • количество самолетов, пролетающих над определенным районом в единицу времени, например, месяц.

150. Криптографические алгоритмы с открытым ключом и их использование (асимметричная криптография): RSA, алгоритм Диффи-Хеллмана, алгоритм Эль-Гамаля.

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


Основные способы использования алгоритмов с открытым ключом


Основными способами использования алгоритмов с открытым ключом являются шифрование/дешифрование, создание и проверка подписи и обмен ключа.

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

шифрование с открытым ключом


Рис. 7.1.  Шифрование с открытым ключом

  1. Пользователь В создает пару ключей KUb и KRb, используемых для шифрования и дешифрования передаваемых сообщений.

  2. Пользователь В делает доступным некоторым надежным способом свой ключ шифрования, т.е. открытый ключ KUb. Составляющий пару закрытый ключ KRb держится в секрете.

  3. Если А хочет послать сообщение В, он шифрует сообщение, используя открытый ключ В KUb.

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

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

Создание и проверка подписи состоит из следующих шагов:



создание и проверка подписи


Рис. 7.2.  Создание и проверка подписи

  1. Пользователь А создает пару ключей KRA и KUA, используемых для создания и проверки подписи передаваемых сообщений.

  2. Пользователь А делает доступным некоторым надежным способом свой ключ проверки, т.е. открытый ключ KUA. Составляющий пару закрытый ключ KRA держится в секрете.

  3. Если А хочет послать подписанное сообщение В, он создает подпись EKRa[M] для этого сообщения, используя свойзакрытый ключ KRA.

  4. Когда В получает подписанное сообщение, он проверяет подпись DKUa[M], используя открытый ключ А KUA. Никто другой не может подписать сообщение, так как этот закрытый ключ знает только А.

До тех пор, пока пользователь или прикладная система надежно хранит свой закрытый ключ, их подписи достоверны.

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


Алгоритм RSA


Алгоритм RSA является, наверно, наиболее популярным и широко применяемым асимметричным алгоритмом в криптографических системах.

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



  1. задача проверки числа на простоту является сравнительно легкой;

  2. задача разложения чисел вида n = pq ( р и q — простые числа); на множители является очень трудной, если мы знаем только n, а р и q — большие числа (это так называемая задача факторизации, подробнее о ней см. "Основные положения теории чисел, используемые в криптографии с открытым ключом").

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные должны быть представлены в виде целых чисел между 0 и n -1 для некоторого n.

Алгоритм Диффи-Хеллмана


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

Y = AX mod P.

Причем, имея Х, вычислить Y легко. Обратная задача вычисления X из Y является достаточно сложной. Экспонента X как раз и называется дискретным логарифмом Y. Таким образом, зная о сложности вычисления дискретного логарифма, число Y можно открыто передавать по любому каналу связи, так как при большом модуле P исходное значение Х подобрать будет практически невозможно. На этом математическом факте основан алгоритм Диффи-Хеллмана для формирования ключа.

Алгоритм Эль-Гамаля


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

Затем каждый абонент группы выбирает свое секретное число Хi, 1 < Х i < Р-1, и вычисляет соответствующее ему открытое число y_i : y_i = a^{x_i}\: mod \: p. Таким образом, каждый пользователь может сгенерировать закрытый ключ Хi и открытый ключ Yi.

Информация о необходимых параметрах системы сведена в следующую таблицу.




Общие параметры

Открытый ключ

Закрытый ключ

Пользователь 1

Р, А

Y1

Х1







Пользователь i

Yi

Хi

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

Электронная подпись на основе алгоритма RSA


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

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






Открытый ключ

Закрытый ключ

Пользователь А

NA, dA

eA

Пользователь Б

NБ, dБ

eБ

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

Основная часть протокола состоит из следующих шагов.



  1. Сначала пользователь А вычисляет числа http://www.intuit.ru/img/tex/7554b71e162c06430d87a6b86575caf8.png, то есть шифрует сообщение своим закрытым ключом. В результате этих действий пользователь А подписывает сообщение.

  2. Затем пользователь А вычисляет числа http://www.intuit.ru/img/tex/c5770f6adb56b3a74b9a8d1a70aec5ca.png, то есть шифрует то, что получилось на шаге 1 открытым ключом пользователя Б. На этом этапе сообщение шифруется, чтобы никто посторонний не мог его прочитать.

  3. Последовательность чисел gi передается к пользователю Б.

  4. Пользователь Б получает gi и вначале вычисляет последовательно числа http://www.intuit.ru/img/tex/dc12dce7d95a0d0a919696ea44a2dbd2.png, используя свой закрытый ключ. При этом сообщение расшифровывается.

  5. Затем Б определяет числа http://www.intuit.ru/img/tex/db81323c9623341fd411980d417065f0.png, используя открытый ключ пользователя А. За счет выполнения этого этапа производится проверка подписи пользователя А.

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

  • пользователь А не может отказаться от своего сообщения, если он признает, что секретный ключ известен только ему;

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

Цифровая подпись на основе алгоритма Эль-Гамаля

Принцип создания и проверки подписи


Алгоритм Эль-Гамаля также можно использовать для формирования цифровой подписи. Группа пользователей выбирает общие параметры Р и А. Затем каждый абонент группы выбирает свое секретное число Хi, 1 < Хi< Р-1, и вычисляет соответствующее ему открытое число http://www.intuit.ru/img/tex/683a38086827bc1dc5f2ad98f13a5c99.png. Таким образом, каждый пользователь получает пару (закрытый ключ; открытый ключ) = (Хi, Yi). Открытые ключи пользователей могут храниться в общей базе системы распределения ключей и при необходимости предоставляться всем абонентам системы.

Сообщение, предназначенное для подписи, должно быть представлено в виде числа, меньшего модуля Р. При большом размере сообщение разбивается на блоки необходимого размера. В некоторых случаях подписывается не само сообщение, а значение хеш-функции от него. В любом варианте цифровая подпись вычисляется в зависимости от некоторого числа m (m < P).

Пусть пользователь 1 хочет подписать свое сообщение цифровой подписью и передать его пользователю 2. В этом случае алгоритм действий следующий.


  1. Первый пользователь выбирает случайное секретное число k, взаимно простое с Р-1, и вычисляет число http://www.intuit.ru/img/tex/2afac081493c5b85dd8d5d4b35bc5c7f.png

  2. Затем с помощью расширенного алгоритма Евклида необходимо найти значение b в следующем уравнении:

m = (X1 * a +k * b) mod (P-1)

Пара чисел (a, b) будет цифровой подписью сообщения m.



  1. Сообщение m вместе с подписью (a, b) отправляется пользователю 2.

  2. Пользователь 2 получает сообщение m и с использованием открытого ключа первого абонента Y1 вычисляет два числа по следующим формулам: http://www.intuit.ru/img/tex/fe1a00f6d3ccff20ecf2a4d94626846a.png Если с1 = с2, то цифровая подпись первого пользователя верная. Для подписывания каждого нового сообщения должно каждый раз выбираться новое значение k.

Подписи, созданные с использованием алгоритма Эль-Гамаля, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи(a,b), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.

Стандарты на алгоритмы цифровой подписи

Стандарт цифровой подписи DSS


Во многих странах сегодня существуют стандарты на электронную (цифровую) подпись. Стандарт цифровой подписи DSS (Digital Signature Standard – DSS) был принят в США в 1991 году и пересмотрен в 1994 году. В основе стандарта лежит алгоритм, называемый DSA (Digital Signature Algorithm) и являющийся вариацией подписи Эль-Гамаля. В алгоритме используется однонаправленная хеш-функцияH(m). В качестве хэш-алгоритма стандарт DSS предусматривает использование алгоритма SHA-1.

Стандарт цифровой подписи ГОСТ Р34.10-94


В России принят стандарт ГОСТ Р34.10-94 "Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма". В этом стандарте используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS.

Пример создания и проверки подписи по стандарту ГОСТ Р34.10-94


Пусть p = 23, q = 11, a =6 (проверяем: 611 mod 23 = 1 )

Создание подписи.

Предположим, пользователь А выбрал в качестве закрытого ключа число х=8. После этого он вычисляет открытый ключ по формуле y = аx mod p. То есть y = 68 mod 23 = 18.

Для создания подписи пользователь А выбирает случайное число k = 5.

Пусть результат вычисления хеш-функции для сообщения H(m) = 9.

Подпись сообщения состоит из двух чисел (r, s):

r = (аkmod p) mod q = (65 mod 23) mod 11 = 2,

s = (k* H(m) + x * r) mod q = (5 * 9 + 8 * 2) mod 11 = 6,

Таким образом, подпись сообщения состоит из пары чисел (2, 6).

Новый отечественный стандарт ЭЦП


В 2001 г. был принят новый отечественный стандарт на алгоритм формирования и проверки ЭЦП. Его полное название следующее: "ГОСТ Р34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи".

Данный алгоритм был разработан главным управлением безопасности связи Федерального агентства правительственной связи и информации при Президенте Российской Федерации при участии Всероссийского научно-исследовательского института стандартизации. Новый стандарт разрабатывался с целью обеспечения большей стойкости алгоритма генерации ЭЦП.

В основе ГОСТ Р34.10-2001 лежат алгоритмы с использованием операций на эллиптических кривых. Стойкость ГОСТ Р34.10-2001 основывается на сложности взятия дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции по ГОСТ Р34.11-94. Размер формируемой цифровой подписи – 512 бит.

152. Шифрование, помехоустойчивое кодирование и сжатие информации

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

В связи с появлением сетей передачи данных высокой пропускной способности и развитием мультимедиа-технологий возникает проблема шифрования больших объемов информации

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

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

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

Помехоустойчивое кодирование


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

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

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

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

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

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


Принципы сжатия данных


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

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

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

153. Анализ рисков как основа управления информационной безопасностью предприятия. Методики управления и анализа рисков.





Поделитесь с Вашими друзьями:
1   ...   12   13   14   15   16   17   18   19   ...   29


База данных защищена авторским правом ©nethash.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал