Программная реализация методы шифрования Цезаря и Вижинера

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

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

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

 

2.4.1. Система RSA

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

 

2.4.1.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.4.1.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.4.2. Алгоритм Эль-Гамаль

 

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

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

Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P.

 

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

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

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

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

Ka, Kb

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

1 < K < P

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

В = A ^Kb mоd(P)

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

C = M * B ^Ka mоd(P)

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

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

M = C * D mоd(P)

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

 

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

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

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

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

Ka

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

1 < Ka < P

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

В = A ^Ka mоd(P)

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

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

( L , P - 1 ) = 1

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

R = A ^L mоd(P)

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

M = Ka * R + L * S mоd(P)

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

[ M, R, S ]

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

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

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

Практическое применение криптологии.

 

3. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ КРИПТОЛОГИИ

 

3.1. Цифровая  подпись

 

3.1.1. Общие положения

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

• Гарантирование истинности письма путем сличения подписи с имеющимся образцом;
• Гарантирование авторства документа ( с юридической точки зрения)

Выполнение данных  требований основывается на следующих  свойствах подписи:

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

перенести ее на другой документ невозможно.

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

  Существует несколько  методов построения ЭЦП, а именно:

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

Кроме перечисленных, существуют и другие методы построения схем ЭЦП

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

3.1.2. Алгоритм DSA

В 1991 г. в США был  опубликован проект федерального стандарта  цифровой подписи - DSS (Digital Signature Standard, [DSS91]), описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта  была его патентная чистота.

Предлагаемый алгоритм DSA, имеет, как  и RSA, теоретико-числовой характер, и  основан на криптографической системе Эль-Гамаля в варианте Шнорра. Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит.