Криптология. Методы шифрования информации

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

4. Криптосистемы с открытым ключом

    В 1976 г. У.Диффи и М.Хеллманом был  предложен новый тип криптографической системы - система с открытым ключом [public keycryptosystem]. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая - секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом - упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа.

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

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

    Из-за особенностей алгоритмов, лежащих в  основе систем с открытым ключом, их быстродействие при обработке единичного блока информации обычно в десятки раз меньше, чем быстродействие систем с симметричным ключом на блоке той же длины. Для повышения эффективности систем с открытым ключом часто применяются смешанные методы, реализующие криптографические алгоритмы обоих типов. При шифровании информации выбирается случайный симметричный ключ, вызывается алгоритм с симметричным ключом для шифрования исходного текста. а затем алгоритм с открытым ключом для шифрования симметричного ключа. По коммуникационному каналу передается текст, зашифрованный симметричным ключом, и симметричный ключ, зашифрованный открытым ключом. Для расшифровки действия производятся в обратном порядке: сначала при помощи секретного ключа получателя расшифровывается симметричный ключ, а затем при помощи симметричного ключа - полученный по каналу зашифрованный текст. Для формирования электронной подписи по подписываемому тексту вычисляется его однонаправленная хэш-функция (дайджест) [one-way hash function, digest], представляющая собой один короткий блок информации, характеризующий весь текст в целом; задача восстановления текста по его хэш-функции или подбора другого текста, имеющего ту же хэш-функцию, практически неразрешима. При непосредственном формировании подписи, вместо шифрования секретным ключом каждого блока текста секретный ключ применяется только к хэш-функции; по каналу передается сам текст и сформированная подпись хэш-функции. Для проверки подписи снова вычисляется хэш-функция от полученного по каналу текста, после чего при помощи открытого ключа проверяется, что подпись соответствует именно данному значению хэш-функции. Алгоритмы вычисления однонаправленных хэш-функций, как правило, логически тесно связаны с алгоритмами шифрования с симметричным ключом.

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

1. Система RSA

      Самым распространенным алгоритмом ассиметричного шифрования является алгоритм RSA. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.  Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на  сложности факторизации больших целых чисел.  Современное состояние алгоритмов факторизации (разложения на множители) позволяет решать эту задачу для чисел длиной до 430 бит; исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных на срок до 10 лет, а в 1024 бита – безусловно, надежным. Несмотря на то, что отсутствует математически доказанное сведение задачи раскрытия RSA к задаче разложения на множители, система выдержала испытание практикой и является признанным стандартом de-facto в промышленной криптографии, а также официальным стандартом ряда международных организаций. С другой стороны, свободное распространение программного обеспечения, основанного на RSA, ограничено тем, что алгоритм RSA защищен в США рядом патентов. RSA можно применять как для шифрования/расшифровывания, так и для генерации/проверки электронно-цифровой подписи.

1.   Генерация ключа

    Первым  этапом любого асимметричного алгоритма  является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций:

    Выбираются  два простых (!) числа p и q

    Вычисляется их произведение n(=p*q)

    Выбирается  произвольное число e (e<n), такое, что  НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

    Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод  Евклида как раз и находит  множество пар (d,y), каждая из которых является решением уравнения в целых числах. Два числа (e,n) – публикуются как открытый ключ.

    Число d хранится в строжайшем секрете  – это и есть закрытый ключ, который  позволит читать все послания, зашифрованные  с помощью пары чисел (e,n).

2. Шифрование/расшифровывание

    Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают, взятие целой части от дробного числа.

    Подобный  блок, как Вы знаете, может быть интерпретирован  как число из диапазона (0;2^k-1). Для каждого такого числа (m_i) вычисляется выражение c_i=((m_i)^e)mod n. Блоки c_i и есть зашифрованное сообщение, и их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

    А вот на приемной стороне процесс  дешифрования все же возможен, и  поможет нам в этом хранимое в  секрете число d. Достаточно давно  была доказана теорема Эйлера, частный  случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x^(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой.

      Возведем обе ее части в  степень (-y): (x^{(-y)(p-1)(q-1)})mod n = 1^(-y) = 1.

      Теперь умножим обе ее части  на x: (x^{(-y)(p-1)(q-1)+1})mod n = 1*x = x.

    А теперь вспомним, как создавались открытый и закрытый ключи. С помощью алгоритма Евклида подбиралось такое d, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца можем заменить показатель степени на число (e*d). Получаем (x^e*d)mod n = x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m:

      ((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.

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

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

1. Общие сведения

    В 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P. 
Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P.

2.   Шифрование сообщений

    Протокол  передачи сообщения M выглядит следующим образом.

    абоненты  знают числа A и P;

    абоненты  генерируют независимо друг от друга  случайные числа:

    Ka, Kb

    удовлетворяющих условию:

    1 < K < P

    получатель  вычисляет и передаёт отправителю  число B, определяемое последовательностью:

    В = A ^Kb mod(P)

    отправитель шифрует сообщение M и отправляет полученную последовательность получателю

    C = M * B ^Ka mod(P)

    получатель  расшифровывает полученное сообщение

    D = ( A ^Ka ) ^-Kb mоd(P)

    M = C * D mоd(P)

    В этой системе открытого шифрования та же степень защиты, что для  алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.

3. Подтверждение подлинности отправителя

 

    Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения  подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M:

    абоненты  знают числа A и P;

    отправитель генерирует случайное число и  хранит его в секрете:

    Ka

    удовлетворяющее условию:

    1 < Ka < P

    вычисляет и передаёт получателю число B, определяемое последовательностью:

    В = A ^Ka mod(P)

    Для сообщения M (1 < M < P):

    выбирает  случайное число L (1 < L < P), удовлетворяющее условию

    ( L , P - 1 ) = 1

    вычисляет число

    R = A ^L mod(P)

    решает  относительно S

    M = Ka * R + L * S mod(P)

    передаёт  подписанное сообщение

    [ M, R, S ]

    получатель  проверяет правильность подписи

    A M = ( B ^R ) *  ( R ^S ) mоd(P) 

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