Технология шифрования

Размещено на http://allbest.ru

Введение

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

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

Для быстрого выполнения подобного преобразования необходим расшифровывающий ключ.

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

Фундаментальное отличие шифрования с открытым ключом (асимметричное шифрование) заключается в том, что зашифровывающий и расшифровывающий ключи не совпадают.

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

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

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

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

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



1. Теоретическая часть

1.1 Алгоритмы шифрования с открытым ключом. Цифровые подписи

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

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

Некоторые из них, например RSA (Rivest-Shamir-Adelman) и шифрование с помощью эллиптической кривой (Elliptic Curve Criptography, ECC), являются алгоритмами общего употребления в том смысле, что они поддерживают все упомянутые выше операции.

Другие алгоритмы поддерживают только некоторые операции. К ним относятся: алгоритм цифровой подписи (Digital Signature Algorithm, DSA), используемый только для работы с цифровыми подписями, и алгоритм DiJfie-Hetlman (D-H), применяемый только для соглашений о секретных ключах. Алгоритмы шифрования, используемые безопасностью IP (IP Security)

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

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

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

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

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

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

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

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

Сначала рассмотрим алгоритмы, обладающие обеими характеристиками, а затем перейдем к алгоритмам открытого ключа, которые не обладают вторым свойством.

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

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

Закрытый ключ держится в секрете, но называть его будем закрытым ключом, а не секретным, чтобы избежать путаницы с ключом, используемым в симметричном шифровании. Закрытый ключ будем обозначать KR, открытый ключ - KU.

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

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

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

1. Вычислительно легко создавать пару (открытый ключ KU , закрытый ключ KR).

2. Вычислительно легко, имея открытый ключ и незашифрованное сообщение М, создать соответствующий зашифрованное сообщение:

3. Вычислительно легко дешифровать сообщение, используя закрытый ключ:

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

5. Вычислительно невозможно, зная открытый ключ KU и зашифрованное сообщение С, восстановить исходное сообщение М.

Можно добавить шестое требование, хотя оно не выполняется для всех алгоритмов с открытым ключом:

6. Шифрующие и дешифрующие функции могут применяться в любом порядке:

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

Y = f(X) - легко
X = f-1(Y) - трудно

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

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

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

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

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

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

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

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

Y = fk(X) - легко, если k и Х известны
X = fk-1(Y) - легко, если k и Y известны
Х = fk-1(Y) - трудно, если Y известно, но k неизвестно

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

1.2 Описание алгоритма

RSA - криптографическая система с открытым ключом, разработанная Р. Ривестом, А. Шамиром и Л. Адельманом в 1977 году. Все криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

· Если известно , то вычислить относительно просто

· Если известно , то для вычисления нет простого (эффективного) пути.

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

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

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

Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n.

Собственно, сам алгоритм:

1. Выбираются два простых числа p и q

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

3. Вычисляется функция Эйлера m = (p - 1) * (q - 1)

4. Выбирается число e, отвечающее следующим критериям:

a. Оно должно быть простое

b. Оно должно быть меньше значения функции Эйлера

c. Оно должно быть взаимно простым со значением функции Эйлера

5. Вычисляется число d обратное e про модулю функции Эйлера (остаток от деления по модулю m и произведения d и e должен быть равен единице) он же расширенный алгоритм Евклида

В результате таких преобразований мы получаем необходимые нам ключи:

· Открытый ключ - {e, n}

· Закрытый ключ - {d, n}

Шифрование выполняется как возведение блока в степень e по модулю n. Расшифровка выполняется как возведение шифрованного блока в степень d по модулю n.

1.3 Скорость работы алгоритма RSA

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

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

При этом шифрование данных идет быстрее чем расшифровка, а проверка подписи - быстрее чем подписание.

Если k - количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов необходимых для выполнения операции с открытым (public) ключом пропорционально второй степени k, количество шагов для операций секретного (private) ключа - третьей степени k, количество шагов для операции создания ключей - четвертой степени k.

Методы "быстрого умножения" - например, методы основанные на Быстром Преобразовании Фурье Fourier (FFT - Fast Fourier Transform) - выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее.

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

Алгоритм RSA намного медленнее чем DES и другие алгоритмы блокового шифрования.

Программная реализация DES работает быстрее по крайней мере в 100 раз и от 1,000 до 10,000 - в аппаратной реализации (в зависимости от конкретного устройства). Благдаря ведущимся разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блокового шифрования.

1.4 Способы взлома криптосистемы RSA

Существует несколько способов взлома RSA. Наиболее эффективная атака: найти секретный (private) ключ, соответствующий необходимому открытому (public) ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым (public) ключом и подделывать подписи.

Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n - p и q.

На основании p, q и e (общий показатель), нападающий может легко вычислить частный показатель d. Основная сложность - поиск главных сомножителей (факторинг) n; безопасность RSA зависит от разложения на сомножители (факторинга), что является трудонразрешимой задачей, не имеющей эффективных способов решения.

Фактически, задача восстановления секретного (private) ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = M^e*(mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный (private) ключ.

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

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

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

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

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

Другая атака единственного сообщения применяется в том случае если кто-то посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападаюший может перехватить эти сообщения и расшифровать сообщение M.

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

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

Разумеется, существуют и атаки нацеленные не на криптосистему непосредственно, а на уязвимые места всей системы коммуникаций в целом; такие атаки не могут рассматриваться как взлом RSA, так как говорят не о слабости алгоритма RSA, а скорее об уязвимости его конкретной реализации.

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

2. Практическая часть

Моя реализация криптосистемы RSA состоит из 4 основных классов:

BigNumberGenerator - генератор больших чисел, как простых так и обычных.

Для проверки большого числа на простоту был реализован вероятностный тест Миллера-Рабина.

Тест Миллера - Рабина - вероятностный полиномиальный тест простоты. Он позволяет эффективно определять, является ли заданное ему число составным.

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

Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа m, то вероятность того что m составное не превосходит .

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

RSAGenerator - генератор ключей RSA, работающий по выше изложенному алгоритму генерации ключей.

Core - ядро программы, в нем заложены все остальные основные необходимые методы.

Converter - класс работающий с пользователем, т.е. тот самый класс, который преобразует ваш текст в шифр-текст и наоборот.



2.1 Время генерации ключей

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

10 тестов на ключ на машине Intel Pentium CPU B970 2.30 GHz с 6 Гб ОЗУ
64 bit - 0 секунд
128 bit - от 0 до 2 секунд
256 bit - от 0 секунд до 12 секунд
512 bit - от 0 секунд до 3 минут 13 секунд
1024 bit - от 58 секунд до 139 минут 35 секунд
2048 bit - за 3 часа не завершился даже первый тест

10 тестов на ключ на машине Intel Core i7 CPU 860 2.8GHz с 4 Гб ОЗУ
64 bit - 0 секунд
128 bit - от 0 до 2 секунд
256 bit - от 0 до 6 минут 13 секунд
512 bit - от 3 секунд до 3 минут 42 секунд
1024 bit - от 34 секунд до 112 минут 35 секунд
2048 bit - за 3 часа не завершился даже первый тест

Файлы отчеты прилагаются, в каждом отчете 2 параметра на строку - верность ключа и время его генерации. Верность ключа определяется шифрованием строки test и ее дешифрованием.

2.2 Скорость преобразования

График зависимости скорости преобразования от длинны ключа на машине Intel Pentium CPU B970 2.30 GHz с 6 Гб ОЗУ представлен ниже, длинна текста - 916289 символов



Как видно на графике, скорость шифрования немного выше скорости дешифрования.

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

Поэтому расшифрование данных идёт медленнее чем шифрование

Следовательно, так и должно быть. Ускорить операцию расшифрования можно:

· разбив ключ n на те самые простые p и q,

· выполнить обычное преобразование

· с помощью китайской теоремы об остатках восстановить m через m1 и m2

Это будет действительно быстрее, так как p и q числа порядка , где length - длинна ключа n, но я не стал этого реализовывать по той простой причине, что не хватило времени.



Вывод

В целом криптосистема RSA получилась рабочая, стабильная, но быстрой генерации ключей длинны 1024 bit и более так и не получилось реализовать, хотя встроенный в .Net Framework класс System.Security.Cryptography.RSA это может.

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

Все дело в преобразовании выходной после шифрования строки в кодировке Base64, она и придает шифр-тексту такой непонятный вид.

шифрование криптографический электронный цифровой



Список используемой литературы

1. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ: Триумф, 2002

2. RSA шифрование на пальцах - http://www.michurin.net/computer-science/rsa.html

3. НОУ ИНТУИТ - http://www.intuit.ru/studies/courses/552/408/lecture/9368?page=5

4. Поиск элемента обратного по модулю - http://e-maxx.ru/algo/reverse_element

5. RSA Википедия - https://ru.wikipedia.org/wiki/RSA

Размещено на Allbest.ru