- Главная
- Без категории
- Шифрование
Содержание
- 2. Обзор Симметричные алгоритмы шифрования Алгоритм DES Несимметричные алгоритмы шифрования Алгоритм RSA Односторонние функции шифрования
- 3. Шифрование — это средство обеспечения конфиденциальности данных, хранящихся в памяти компьютера или передаваемых по проводной или
- 4. Симметричные алгоритмы шифрования Существует два класса криптосистем — симметричные и асимметричные. В симметричных схемах шифрования (классическая
- 5. Алгоритм DES Наиболее популярным стандартным симметричным алгоритмом шифрования данных является DES (Data Encryption Standard). Алгоритм разработан
- 6. Алгоритм DES Вот уже более трех десятков лет алгоритм DES испытывается на стойкость. И хотя существуют
- 7. Алгоритм DES В симметричных алгоритмах главную проблему представляют ключи. Во-первых, криптостойкость многих симметричных алгоритмов зависит от
- 8. Несимметричные алгоритмы шифрования В середине 70-х двое ученых — Винфилд Диффи и Мартин Хеллман — описали
- 9. Несимметричные алгоритмы шифрования В модели криптосхемы с открытым ключом также три участника: отправитель, получатель и злоумышленник
- 10. Несимметричные алгоритмы шифрования – пример-аналогия Пусть руководитель предприятия (на рис. 4 это пользователь 1) решает вести
- 11. Несимметричные алгоритмы шифрования – пример-аналогия Могут ли пользователи 2, 3 и 4 прочитать чужие сообщения S2,
- 12. Несимметричные алгоритмы шифрования – пример-аналогия На рис. 5 показана другая схема использования открытого и закрытого ключей,
- 13. Несимметричные алгоритмы шифрования Для того чтобы в сети все n абонентов имели возможность не только принимать
- 14. Алгоритм RSA В настоящее время одним из наиболее популярных криптоалгоритмов с открытым ключом является криптоалгоритм RSA.
- 15. Алгоритм RSA В некоторых публикациях приводятся следующие оценки: для того чтобы найти разложение 200-значного числа, понадобится
- 16. Односторонние функции шифрования Во многих базовых технологиях безопасности используется еще один прием шифрования — шифрование с
- 17. Односторонние функции шифрования Прежде чем отправить сообщение, отправитель вычисляет для него дайджест и отправляет его вместе
- 18. Односторонние функции шифрования Это средство не распознает модификацию данных злоумышленником, который, подменив сообщение, может просто добавить
- 19. Односторонние функции шифрования Помимо обеспечения целостности сообщений, дайджест может быть использован в качестве электронной подписи для
- 20. Дополнительные материалы для изучения История криптографии Проблема сокрытия содержания послания при его транспортировке волновала людей с
- 21. Чаще всего шифруются тексты документов, но в последнее время шифрованию подвергаются и изображения, голосовые данные и
- 22. Дополнительные материалы для изучения Общие требования к криптосистемам Знание использованного алгоритма не должно снижать надежность шифрования.
- 23. Дополнительные материалы для изучения Общие требования к криптосистемам Многоалфавитные подстановки несравненно более надежны. К числу простых
- 24. Дополнительные материалы для изучения Общие требования к криптосистемам В таблице 1 приведен пример использования такого вида
- 25. Дополнительные материалы для изучения Общие требования к криптосистемам Примером шифрования с использованием секретного ключа является метод
- 26. Дополнительные материалы для изучения Система DES Наибольшее распространение в последнее время получило блочное шифрование, где последовательность
- 27. Дополнительные материалы для изучения Система DES Отправитель и получатель должны знать ключи до начала обмена (эти
- 28. Дополнительные материалы для изучения Базовые определения и теоремы Конгруентность. a конгруентно b по модулю n (a
- 29. Дополнительные материалы для изучения Базовые определения и теоремы Должно быть ясно, что уравнение не будет иметь
- 30. Дополнительные материалы для изучения Базовые определения и теоремы Фокус заключается в том, что берется число и
- 31. Дополнительные материалы для изучения Базовые определения и теоремы Согласно теореме 2, если p простое число, существует
- 32. Дополнительные материалы для изучения Базовые определения и теоремы Другие сходные алгоритмы используют целочисленные логарифмы, элиптические кривые
- 33. Дополнительные материалы для изучения Базовые определения и теоремы Если хакер умудрится вставить свою ЭВМ в разрыв
- 34. Дополнительные материалы для изучения Базовые определения и теоремы Решить эту проблему подмены ключей можно путем пересылки
- 35. Дополнительные материалы для изучения Базовые определения и теоремы Базовые характеристики блочных алгоритмов шифрования представлены в таблице
- 36. Дополнительные материалы для изучения Базовые определения и теоремы Стандарт на хэш функции задает документ ISO/IEC 10118.
- 37. Дополнительные материалы для изучения Базовые определения и теоремы В настоящее время имеется три семейства криптосистем с
- 38. Дополнительные материалы для изучения Базовые определения и теоремы Развитие методов программирования и повышение быстродействия ЭВМ приводит
- 39. Полезную информацию по системам шифрования можно получить на следующих серверах: www.cs.hut.fi/crypto/ www.subject.com/crypto/crypto.html www.rsa.com/ www.netscape.com/newsref/ref/rsa.html www.microsoft.com/workshop/prog/security/pkcb/crypt.htm www.semper.org/sirene/people/gerrit/secprod.html
- 40. Дополнительные материалы для изучения Алгоритм DES Стандарт шифрования DES (Data Encryption Standard) был разработан в 1975
- 41. Дополнительные материалы для изучения Алгоритм DES Вводится функция f, которая работает с 32-разрядными словами исходного текста
- 42. Дополнительные материалы для изучения Алгоритм DES Преобразование начинается с перестановки бит (IP - Initial Permutation) в
- 43. Дополнительные материалы для изучения Алгоритм DES Структурная схема реализации алгоритма DEA показана на рис. 10. Рис.
- 44. Дополнительные материалы для изучения Алгоритм DES Исходный 48-разрядный код делится на 8 групп по 6 разрядов.
- 45. Дополнительные материалы для изучения Алгоритм DES Таблица 1 Таблица 2
- 46. Дополнительные материалы для изучения Алгоритм шифрования RSA Алгоритм RSA (Rivest, Shamir и Adleman, 1978 год) предполагает,
- 47. Дополнительные материалы для изучения Алгоритм шифрования RSA Аналогично (Md)e ≡ qM, если dc ≡ (q-1)1. e
- 48. Дополнительные материалы для изучения Алгоритм шифрования RSA Проясним использование алгоритма RSA на конкретном примере. Выбираем два
- 49. Дополнительные материалы для изучения Алгоритм шифрования AES Стандарт AES (Advanced Encryption Standard) является стандартом шифрования США,
- 50. Дополнительные материалы для изучения Алгоритм шифрования AES При реализации алгоритма AES используются операции сложения байт (по
- 51. Дополнительные материалы для изучения Алгоритм шифрования AES Как было сказано выше длины ключей Nk (длина, измеренная
- 52. Дополнительные материалы для изучения Алгоритм шифрования AES Преобразование SubByte() Преобразование SubByte() является нелинейной подстановкой байтов, которое
- 53. Дополнительные материалы для изучения Алгоритм шифрования AES Преобразование MixColumns() Преобразование MixColumns() обрабатывает State колонка за колонкой,
- 54. Дополнительные материалы для изучения Алгоритм шифрования AES Рис. 13. Псевдокод реализации процедуры преобразования ключа
- 55. Расшифровка Все процедуры, описанные в предыдущем разделе, являются обратимыми. Целью дешифровки является обработка зашифрованного массива данных
- 56. Дополнительные материалы для изучения Алгоритм шифрования AES Преобразование InvShiftRows() Процедура InvShiftRows() является обратной по отношению ShiftRows().
- 58. Скачать презентацию
Обзор
Симметричные алгоритмы шифрования
Алгоритм DES
Несимметричные алгоритмы шифрования
Алгоритм RSA
Односторонние функции шифрования
Обзор
Симметричные алгоритмы шифрования
Алгоритм DES
Несимметричные алгоритмы шифрования
Алгоритм RSA
Односторонние функции шифрования
Шифрование — это средство обеспечения конфиденциальности данных, хранящихся в памяти компьютера или передаваемых
Шифрование — это средство обеспечения конфиденциальности данных, хранящихся в памяти компьютера или передаваемых
Шифрование является краеугольным камнем всех служб информационной безопасности, будь то система аутентификации или авторизации, защищенный канал или средства безопасного хранения данных.
Любая процедура шифрования, превращающая информацию из обычного «понятного» вида в «нечитабельный» зашифрованный, естественно должна быть дополнена процедурой дешифрирования, которая, будучи примененной к зашифрованному тексту, снова приводит его в понятный вид.
Пара процедур - шифрование и дешифрирование - называется криптосистемой. Обычно криптосистема предусматривает наличие специального параметра — секретного ключа. Криптосистема считается раскрытой, если найдена процедура, позволяющая подобрать ключ за реальное время. Сложность алгоритма раскрытия является одной из важных характеристик криптосистемы и называется криптостойкостью.
В криптографии принято правило Керкхоффа, заключающееся в том, что стойкость шифра должна определяться только секретностью ключа. Так, все стандартные алгоритмы шифрования (например, AES, DES, PGP) широко известны, их детальное описание содержится в легкодоступных документах, но от этого их эффективность не снижается. Система остается защищенной, если злоумышленнику известно все об алгоритме шифрования, но он не знает секретный ключ.
Симметричные алгоритмы шифрования
Симметричные алгоритмы шифрования
Существует два класса криптосистем — симметричные и асимметричные. В симметричных
Симметричные алгоритмы шифрования
Существует два класса криптосистем — симметричные и асимметричные. В симметричных
На рис. 1 приведена классическая модель симметричной криптосистемы, теоретические основы которой впервые были изложены в 1949 году в работе Клода Шеннона.
Рис. 1. Модель симметричного шифрования
В данной модели три участника: отправитель, получатель и злоумышленник. Задача отправителя заключается в том, чтобы по открытому каналу передать некоторое сообщение в защищенном виде. Для этого он зашифровывает открытый текст X ключом k и передает шифрованный текст Y. Задача получателя заключается в том, чтобы расшифровать У и прочитать сообщение X. Предполагается, что отправитель имеет свой источник ключа. Сгенерированный ключ заранее по надежному каналу передается получателю. Задача злоумышленника заключается в перехвате и чтении передаваемых сообщений, а также в имитации ложных сообщений.
Алгоритм DES
Наиболее популярным стандартным симметричным алгоритмом шифрования данных является DES (Data Encryption Standard).
Алгоритм DES
Наиболее популярным стандартным симметричным алгоритмом шифрования данных является DES (Data Encryption Standard).
Данные шифруются поблочно. Перед шифрованием любая форма представления данных преобразуется в числовую. Числа получают путем применения любой открытой процедуры преобразования блока текста в число. Например, ими могли бы быть значения двоичных чисел, полученных слиянием кодов ASCII последовательных символов соответствующего блока текста. На вход шифрующей функции поступает блок данных размером 64 бита, он делится пополам на левую (I) и правую (К) части. На первом этапе на место левой части результирующего блока помещается правая часть исходного блока. Правая часть результирующего блока вычисляется как сумма по модулю 2 (операция XOR) левой и правой частей исходного блока. Затем на основе случайной двоичной последовательности по определенной схеме в полученном результате выполняются побитные замены и перестановки.
Рис. 2. Схема шифрования по алгоритму DES
Используемая двоичная последовательность, представляющая собой ключ данного алгоритма, имеет длину 64 бита, из которых 56 действительно случайны, а 8 предназначены для контроля ключа.
Алгоритм DES
Вот уже более трех десятков лет алгоритм DES испытывается на стойкость. И
Алгоритм DES
Вот уже более трех десятков лет алгоритм DES испытывается на стойкость. И
В 2001 году Национальное бюро стандартов США приняло новый стандарт симметричного шифрования, который получил название AES (Advanced Encryption Standard). Стандарт AES был разработан в результате проведения конкурса на разработку симметричного алгоритма шифрования, обладающего лучшим, чем у DES, сочетанием показателей безопасности и скорости работы. Победителем был признан алгоритм Rijndael, который и был положен в основу AES. В результате AES обеспечивает лучшую защиту, так как использует 128-битные ключи (а также может работать со 192- и 256-битными ключами) и имеет более высокую скорость работы, кодируя за один цикл 128-битный блок в отличие от 64-битного блока DES. В настоящее время AES является наиболее распространенным симметричным алгоритмом шифрования.
Алгоритм DES
В симметричных алгоритмах главную проблему представляют ключи. Во-первых, криптостойкость многих симметричных алгоритмов
Алгоритм DES
В симметричных алгоритмах главную проблему представляют ключи. Во-первых, криптостойкость многих симметричных алгоритмов
Несимметричные алгоритмы шифрования
В середине 70-х двое ученых — Винфилд Диффи и Мартин
Несимметричные алгоритмы шифрования
В середине 70-х двое ученых — Винфилд Диффи и Мартин
Особенность шифрования с открытым ключом состоит в том, что одновременно генерируется уникальная пара ключей, таких что текст, зашифрованный одним ключом, может быть расшифрован только с использованием второго ключа, и наоборот.
Рис. 3. Модель криптосистемы с открытым ключом
Несимметричные алгоритмы шифрования
В модели криптосхемы с открытым ключом также три участника: отправитель,
Несимметричные алгоритмы шифрования
В модели криптосхемы с открытым ключом также три участника: отправитель,
Задача отправителя заключается в том, чтобы по открытому каналу связи передать некоторое сообщение в защищенном виде. Получатель генерирует на своей стороне два ключа: открытый Е и закрытый D. Закрытый ключ D (часто называемый также личным ключом) абонент должен сохранять в защищенном месте, а открытый ключ Е он может передать всем, с кем хочет поддерживать защищенные отношения. Для шифрования текста служит открытый ключ, но расшифровать этот текст можно только с помощью закрытого ключа. Поэтому открытый ключ передается отправителю в незащищенном виде.
Отправитель, используя открытый ключ получателя, шифрует сообщение X и передает его получателю. Получатель расшифровывает сообщение своим закрытым ключом D. Очевидно, что числа, одно из которых служит для шифрования текста, а другое — для дешифрирования, не могут быть независимыми друг от друга, а значит, есть теоретическая возможность вычисления закрытого ключа по открытому. Однако это связано с огромным объемом вычислений, которые требуют соответственно огромного времени. Поясним принципиальную связь между закрытым и открытым ключами следующей аналогией.
Несимметричные алгоритмы шифрования – пример-аналогия
Пусть руководитель предприятия (на рис. 4 это пользователь 1)
Несимметричные алгоритмы шифрования – пример-аналогия
Пусть руководитель предприятия (на рис. 4 это пользователь 1)
Рис. 4. Пример криптосистемы с открытым ключом
Когда у сотрудников возникает необходимость написать секретное сообщение руководителю, они, пользуясь словарем, пишут сообщения на санскрите. Руководитель переводит сообщения на русский язык, пользуясь доступным только ему санскритско-русским словарем. Очевидно, что здесь роль открытого ключа Е и закрытого ключа D руководителя играют русско-санскритский и санскритско-русский словари соответственно.
Несимметричные алгоритмы шифрования – пример-аналогия
Могут ли пользователи 2, 3 и 4 прочитать
Несимметричные алгоритмы шифрования – пример-аналогия
Могут ли пользователи 2, 3 и 4 прочитать
Заметим, что у сотрудников имеется теоретическая возможность для разгадывания сообщений друг друга, так как, затратив массу времени, можно прямым перебором составить санскритско-русский словарь по русско-санскритскому. Такая очень трудоемкая процедура, требующая больших затрат времени, отдаленно напоминает восстановление закрытого ключа по открытому.
Несимметричные алгоритмы шифрования – пример-аналогия
На рис. 5 показана другая схема использования открытого и
Несимметричные алгоритмы шифрования – пример-аналогия
На рис. 5 показана другая схема использования открытого и
Итак, руководитель пишет письма своим сотрудникам на санскрите (то есть шифрует их закрытым ключом D). Сотрудник, получивший послание, пытается перевести зашифрованную часть письма, пользуясь санскритско-русским словарем (открытым ключом Е). Если ему это удается, то это доказывает, что текст был зашифрован закрытым ключом, парным открытому ключу Е руководителя. А владельцем этого парного ключа может быть только руководитель, значит, именно он является автором этого сообщения.
Рис. 5. Использование шифрования закрытым ключом для подтверждения авторства
Сообщения первого пользователя S12, S13, S14, адресованные пользователям 2, 3 и 4, не являются секретными, так как все адресаты обладают одним и тем же открытым ключом, с помощью которого они могут расшифровывать все сообщения, поступающие от пользователя 1.
Несимметричные алгоритмы шифрования
Для того чтобы в сети все n абонентов имели возможность
Несимметричные алгоритмы шифрования
Для того чтобы в сети все n абонентов имели возможность
Хотя информация об открытом ключе не является секретной, ее нужно защищать от подлогов, чтобы злоумышленник под именем легального пользователя не навязал свой открытый ключ, после чего с помощью своего закрытого ключа он сможет расшифровывать все сообщения, посылаемые легальному пользователю, и отправлять свои сообщения от его имени. Проще всего было бы распространять списки, связывающие имена пользователей с их открытыми ключами, широковещательно путем публикаций в средствах массовой информации (бюллетени, специализированные журналы и т. п.). Однако при таком подходе мы снова, как и в случае с паролями, сталкиваемся с плохой масштабируемостью. Решением проблемы является технология цифровых сертификатов — электронных документов, которые связывают конкретных пользователей с конкретными открытыми ключами.
Алгоритм RSA
В настоящее время одним из наиболее популярных криптоалгоритмов с открытым ключом является
Алгоритм RSA
В настоящее время одним из наиболее популярных криптоалгоритмов с открытым ключом является
В 1978 году трое ученых (Ривест, Шамир и Адлеман) разработали систему шифрования с открытыми ключами RSA (Rivest, Shamir, Adleman), полностью отвечающую всем принципам Диффи—Хеллмана. Этот метод состоит в следующем.
Случайно выбираются два очень больших простых числа p и q.
Вычисляются два произведения n = р х q и m = (р - 1) х (q - 1).
Выбирается случайное целое число Е, не имеющее общих сомножителей c m.
Находится D такое, что DE = 1 по модулю m.
Исходный текст X разбивается на блоки таким образом, чтобы 0 < Х< п.
Для шифрования сообщения необходимо вычислить по модулю п.
Для дешифрирования вычисляется X = С D по модулю п.
Таким образом, чтобы зашифровать сообщение, необходимо знать пару чисел (E, n), а чтобы расшифровать — пару чисел (D, п). Первая пара — это открытый ключ, а вторая — закрытый.
Зная открытый ключ (E, n), можно вычислить значение закрытого ключа D. Необходимым промежуточным действием в этом преобразовании является нахождение чисел р и q, для чего нужно разложить на простые множители очень большое число я, а на это требуется очень много времени. Именно с огромной вычислительной сложностью разложения большого числа на простые множители связана высокая криптостойкость алгоритма RSA.
Алгоритм RSA
В некоторых публикациях приводятся следующие оценки: для того чтобы найти разложение
Алгоритм RSA
В некоторых публикациях приводятся следующие оценки: для того чтобы найти разложение
Программная реализация криптоалгоритмов типа RSA значительно сложнее и менее производительна, чем реализации классических криптоалгоритмов тина DES. Вследствие сложности реализации операций модульной арифметики криптоалгоритм RSA обычно используют только для шифрования небольших объемов информации, например для рассылки классических секретных ключей или в алгоритмах цифровой подписи, а основную часть пересылаемой информации шифруют с помощью симметричных алгоритмов.
Таблица 1. Сравнительные характеристики алгоритмов шифрования
Односторонние функции шифрования
Во многих базовых технологиях безопасности используется еще один прием шифрования —
Односторонние функции шифрования
Во многих базовых технологиях безопасности используется еще один прием шифрования —
Эта функция, примененная к шифруемым данным, дает в результате значение, называемое дайджестом, которое состоит из фиксированного сравнительно небольшого и не зависящего от длины шифруемого текста числа байтов.
Подчеркнем, знание дайджеста не позволяет и даже не предполагает восстановления исходных данных. Для чего же нужны односторонние функции шифрования (ОФШ)?
Для ответа на этот вопрос рассмотрим несколько примеров. Пусть требуется обеспечить целостность сообщения, передаваемого по сети. Отправитель и получатель договорились, какую ОФШ и с каким значением параметра — секретного ключа — они будут использовать для решения этой задачи.
Односторонние функции шифрования
Прежде чем отправить сообщение, отправитель вычисляет для него дайджест и
Односторонние функции шифрования
Прежде чем отправить сообщение, отправитель вычисляет для него дайджест и
Рис. 6. Использование односторонних функций шифрования для контроля целостности
Таким образом, хотя знание дайджеста не дает возможности восстановить исходное сообщение, оно позволяет проверить целостность данных.
На первый взгляд кажется, что дайджест является своего рода контрольной суммой для исходного сообщения. Однако имеется и существенное отличие. Контрольные суммы применяются тогда, когда нужно обнаружить ошибки, вызванные техническими неполадками, например помехами в линии связи.
Односторонние функции шифрования
Это средство не распознает модификацию данных злоумышленником, который, подменив сообщение, может
Односторонние функции шифрования
Это средство не распознает модификацию данных злоумышленником, который, подменив сообщение, может
В отличие от контрольной суммы дайджест вычисляется с использованием параметра — секретного ключа. Поскольку значение секретного ключа для ОФШ известно только отправителю и получателю. Любая модификация исходного сообщения будет немедленно обнаружена.
На рис. 1, б показан другой вариант использования односторонней функции шифрования для обеспечения целостности данных. Здесь односторонняя функция не имеет параметра-ключа, но зато применяется не просто к сообщению, а к сообщению, дополненному секретным ключом. Получатель извлекает из полученных по сети данных исходное сообщение, потом дополняет его тем же известным ему секретным ключом и применяет к полученным данным одностороннюю функцию. Результат вычислений сравнивается с полученным по сети дайджестом.
Односторонние функции шифрования
Помимо обеспечения целостности сообщений, дайджест может быть использован в качестве электронной
Односторонние функции шифрования
Помимо обеспечения целостности сообщений, дайджест может быть использован в качестве электронной
Построение односторонних функций является трудной задачей. Такого рода функции должны удовлетворять двум условиям:
по дайджесту, вычисленному с помощью данной функции, должно быть невозможно каким-либо образом вычислить исходное сообщение;
должна отсутствовать возможность вычисления двух разных сообщений, для которых с помощью данной функции могли быть вычислены одинаковые дайджесты.
Наиболее популярной в системах безопасности в настоящее время является серия хэш-функций MD2, MD4, MD5. Все они генерируют дайджесты фиксированной длины 16 байт. Адаптированным вариантом MD4 является американский стандарт SHA, длина дайджеста в котором составляет 20 байт. Компания IBM поддерживает односторонние функции MDC2 и MDC4, основанные на алгоритме шифрования DES.
Дополнительные материалы для изучения
История криптографии
Проблема сокрытия содержания послания при его транспортировке волновала людей
Дополнительные материалы для изучения
История криптографии
Проблема сокрытия содержания послания при его транспортировке волновала людей
Известно, что еще Цезарь (100-44 годы до нашей эры) при переписке использовал шифр, получивший его имя. В 1518 году Джоанес Тритемиус написал первую книгу по криптографии, где впервые были описаны многоалфавитные подстановочные шифры. Лишь в 1918 году во время первой мировой войны в Германии была применена шифровальная система ADFGVX. Позднее в 1933-45 годах в Германии была разработана и применена первая шифровальная машина Enigma (на этом принципе работает система crypt в UNIX). Мощное развитие криптография получила в период второй мировой войны. С этой шифровальной машиной связан и первый успех в области вскрытия сложных шифров. В 19-ом веке голандец Август Керкхоф сформулировал фундаментальное требование, предъявляемое к криптосистемам и сегодня (принцип Керкхофа): Секретность шифра должна базироваться не на секретности алгоритма, а на секретном ключе.
Если в алгоритм заложена возможность относительно быстрого дешифрования (мечта всех спецслужб мира), то рано или поздно это станет известно, и такой возможностью воспользуются злоумышленники, что может привести к утечке критическо важной информации. Основы современной криптографии были заложены в работе Клода Шеннона “Теория связи в секретных системах” (1949).
Чаще всего шифруются тексты документов, но в последнее время шифрованию подвергаются и изображения,
Чаще всего шифруются тексты документов, но в последнее время шифрованию подвергаются и изображения,
Во время второй мировой войны в Великобритании в Government Code and Cypher School работало более 10000 человек (из них две трети женщин). Код немецкой шифровальной машины Энигма взломал английский математик Алан Тьюринг, но в той или иной степени в этом участвовали и остальные 10000 сотрудников. Ключи настройки машины Энигма изменялись каждые сутки в полночь. В результате были дешифрованы два с половиной миллиона нацистских секретных сообщений. Следует иметь в виду, что тогда не было ЭВМ в современном понимании этого слова и вся работа выполнялась с помощью электромеханических устройств (Colossus - British Tabulating Machine Company). Англичане считают эту машину первым программируемым электронным компьютером. Если бы эти сообщения дешифровались в ручную, то надо было бы перебрать 158x1018 вариантов. Colossus эмулировал работу 36 машин Энигма. Многие сообщения начинались с метеорологических данных, что позволяло проверить настройки дешифровальной машины. Сотрудники, обслуживающие Colossus, работали парами, чтобы исключить случайные ошибочные действия. Работа была посменная, круглосуточная. Работа проходила в условиях глубокой секретности. Более поздняя версия Mark II Colossus была способна дешифровать до 25000 символов в секунду. Машина Colossus поддерживается в рабочем состоянии и сегодня, но уже в качестве музейного экспоната.
Шифрование предполагает преобразование исходного текста Т с использованием ключа К в зашифрованный текст t. Симметричные криптосистемы для шифрования и дешифрования используется один и тот же ключ К. Появившиеся в последние годы системы с открытым ключом, осуществляют шифрование с помощью общедоступного ключа, для дешифрования в этом случае необходим секретный ключ, который порождается совместно с открытым.
Дополнительные материалы для изучения
История криптографии
Дополнительные материалы для изучения
Общие требования к криптосистемам
Знание использованного алгоритма не должно снижать надежность
Дополнительные материалы для изучения
Общие требования к криптосистемам
Знание использованного алгоритма не должно снижать надежность
Длина зашифрованного текста должна быть равна длине исходного открытого текста (это требование относится к числу желательных и выполняется не всегда).
Зашифрованный текст не может быть прочтен без знания ключа.
Каждый ключ из многообразия ключей должен обеспечивать достаточную надежность.
Изменение длины ключа не должно приводить к изменению алгоритма шифрования.
Если известен зашифрованный и открытый текст сообщения, то число операций, необходимых для определения ключа, не должно быть меньше полного числа возможных ключей.
Дешифрование путем перебора всех возможных ключей должно выходить далеко за пределы возможностей современных ЭВМ.
Если при шифровании в текст вводятся дополнительные биты, то алгоритм их внесения должен быть надежно скрыт.
Не должно быть легко устанавливаемой зависимости между последовательно используемыми ключами.
Алгоритм может быть реализован аппаратно.
В симметричных криптосистемах могут использоваться одно- или многоалфавитные подстановки (например, одно-алфавитная подстановка Цезаря), при этом производится замена символов исходного текста на другие с использованием достаточно сложных алгоритмов.
Дополнительные материалы для изучения
Общие требования к криптосистемам
Многоалфавитные подстановки несравненно более надежны. К
Дополнительные материалы для изучения
Общие требования к криптосистемам
Многоалфавитные подстановки несравненно более надежны. К
Ключ может быть одноразового и многоразового использования. Одноразовый ключ достаточно большой длины (или бесконечный) может обеспечить сколь угодно высокую надежность, но его использование создает неудобства, связанные с его транспортировкой (ключ должен быть как-то доставлен получателю зашифрованного послания).
Дополнительные материалы для изучения
Общие требования к криптосистемам
В таблице 1 приведен пример использования такого
Дополнительные материалы для изучения
Общие требования к криптосистемам
В таблице 1 приведен пример использования такого
Зашифрованный текст получается здесь из исходного добавлением значения очередного кода ключа (сложение может быть заменено вычитанием или операцией исключающее ИЛИ). Исходный текст в данном случае невозможно восстановить без знания ключа.
Таблица 1.
Дополнительные материалы для изучения
Общие требования к криптосистемам
Примером шифрования с использованием секретного ключа является
Дополнительные материалы для изучения
Общие требования к криптосистемам
Примером шифрования с использованием секретного ключа является
abcdefghijklmnopqrstuvwxyz ghijklmnopqrstuvwxyzabcdef
opqrstuvwxyzabcdefghijklmn
Lmnopqrstuvwxyzabcdefghijk
fghijklmnopqrstuvwxyzabcde
Ключ = golf (смотри левую вертикальную колонку символов).
Исходный текст разбивается на группы по m символов (в рассмотренном случае по 4). Для каждой группы первый символ заменяется соответствующей буквой первого алфавита, вторая - из второго и т.д. Например, фраза "get me out of here please" будет преобразована следующим образом:
getm eout ofhe repl ease mser kcfy utsj xsaq kohj
Дополнительные материалы для изучения
Система DES
Наибольшее распространение в последнее время получило блочное шифрование, где
Дополнительные материалы для изучения
Система DES
Наибольшее распространение в последнее время получило блочное шифрование, где
ECB electronic code book;
CBC cipher block chaining;
CFB cipher feedback;
OFB output feedback.
Из-за того, что алгоритм DES в настоящее время представляется устаревшим и не обеспечивает достаточной надежности, довольно часто исходный текст последовательно шифруется трижды с помощью различных ключей.
Шифрование и дешифрование базируются на использовании ключей. Математически это можно выразить следующим образом (cм. lglwww.epfl.ch/~jkienzle/digital_money/node11.html;
www.ee.mtu.edu/courses/ ee465/groupa/overview.html):
EK(M) = C DK(c) = M, где K – секретный ключ, M - исходный текст; C - зашифрованный текст; Е – алгоритм шифрования; D – алгоритм дешифрования.
Эффективность системы шифрования определяется числом кодовых комбинаций или ключей, которое необходимо перебрать, чтобы прочесть зашифрованный текст. Существует две системы ключей шифрования/дешифрования. Для симметричных алгоритмов предполагается, что ключ дешифрования может быть вычислен по известному ключу шифрования. Оба ключа при этом должны быть секретными (например, система DES).
Дополнительные материалы для изучения
Система DES
Отправитель и получатель должны знать ключи до начала обмена
Дополнительные материалы для изучения
Система DES
Отправитель и получатель должны знать ключи до начала обмена
Шифры бывают поточными и блочными. В первом случае обработка исходного текста производится побитно или побайтно. Во втором - текст перед обработкой разбивается на блоки.
Асимметричные схемы шифрования/дешифрования предполагают существования независимых ключей для шифрования и дешифрования. Причем один не может быть получен из другого и наоборот. В идеале ключ дешифровки не может быть получен из шифрующего ключа за любое разумное время. В этом случае ключ шифрования может быть сделан общедоступным (например, алгоритм RSA). Партнеры до начала коммуникаций должны послать друг другу ключи шифрования КШО и КШП (ключи шифрования отправителя и получателя). Возможность перехвата таких ключей опасности не представляет. Дешифрование выполняется с помощью ключей КДО и КДП, которые образуют пары с КШО и КШП соответственно и формируются совместно. Ключи КШО и КШП обычно пересылаются на фазе инициализации сессии информационного обмена.
Шифрование может осуществляться по определенным правилам с помощью таблиц шифрования или ключей. При этом могут использоваться самые разные алгоритмы, в том числе, например, перемещение символов текста определенным образом. За свою историю люди придумали достаточно большое число способов шифрования. Новейшие из них базируются на методиках, заимствованных из теории чисел. По этой причине, прежде чем переходить к следующему разделу, введем некоторые определения.
Дополнительные материалы для изучения
Базовые определения и теоремы
Конгруентность. a конгруентно b по модулю n
Дополнительные материалы для изучения
Базовые определения и теоремы
Конгруентность. a конгруентно b по модулю n
a +c ≡ n(b + d) и ac ≡ nbd
Аналогичная процедура для деления не всегда справедлива: 6 ≡ 1218 но 3 ≠ 9. Приведенные здесь и далее математические определения и обоснования взяты из: http://lglwww.epfl.ch/~jkienzle/digital/node20.html.
Необходимо также вспомнить о знакомом всем со школьной скамьи понятии наибольшего общего делителя. Для a и b число (a,b) является наибольшим общим делителем, который делит a и b без остатка: (56,98)=14; (76,190)=38.
Теорема 1. Для любых a,b существуют целые числа x,y, для которых ax+by=(a,b). В данной статье не приводится доказательств представленных утверждений, их следует искать в книгах по дискретной математике.
В этом можно убедиться, решая уравнение 30x+69y=3 путем последовательных упрощающих подстановок (ищется целочисленное решение: 30x+69y=3)
30x'+9y=3 [x'=x+2y]
3x'+9y'=3 [y'=y+3x']
3x"+0y'=3 [x"=x'+3y'].
Легко видеть, что x"=1, y'=0 является решением окончательного уравнения. Мы можем получить решение исходного уравнения путем обратной подстановки
x'=x"-3y'=1; y=y'-3x'=-3; x=x'-1y=7.
Мы можем решить уравнение вида 30x+69y=15 путем умножения нашего решения: y=-15, x=35.
Дополнительные материалы для изучения
Базовые определения и теоремы
Должно быть ясно, что уравнение не будет
Дополнительные материалы для изучения
Базовые определения и теоремы
Должно быть ясно, что уравнение не будет
Все другие целочисленные решения 30x+69y=15 могут быть получены, варьируя первое решение:
y=-15+(30/3)t x=35 -(69/3)t для целого t.
Если мы проделаем то же для произвольного равенства ax+by=(a,b), мы возможно получим один из коэффициентов равным нулю, а другой - (a,b). В действительности эта процедура представляет собой алгоритм Евклида для нахождения наибольшего общего делителя.
Важно то, что этот процесс реализуем на ЭВМ даже в случае, когда a и b имеют несколько сотен значащих цифр. Легко показать, что 600-значное число не потребует более чем 4000 уравнений. Теорема 1 справедлива и для простых чисел.
Следствие 1. Если p является простым числом, ar ≡ pas и a ≠ 0, тогда r ≡ s.
Следствие 2. Если p простое число и a ≠ 0 mod p, тогда для любого b существует y, для которого ay ≡ pb.
Следствие 3. ("Теорема о китайском остатке"). Если (p,q)=1, тогда для любого a,b существует n, для которого n ≡ pa и n≡ qb.
Во многих криптографических приложениях используется:
a a2 a3 … mod p, где a и p целые числа.
Оказывается, можно выполнить такие вычисления даже для случая, когда в указанную процедуру вовлечены достаточно большие числа, например:
432678 mod 987.
Дополнительные материалы для изучения
Базовые определения и теоремы
Фокус заключается в том, что берется число
Дополнительные материалы для изучения
Базовые определения и теоремы
Фокус заключается в том, что берется число
4322 = 186624; 186624 mod 987 = 81; 4324 mod 987 = 812 mod 987 = 639 4328 -> 6392 mod 987 -> 690 …. 432512 -> 858 так как 678= 512+128+32+4+2, то: 432678->(81)(639)….(858) -> 204
Вычисления с использованием показателя включают в себя ограниченное число умножений. Если числа содержат несколько сотен цифр, необходимы специальные подпрограммы для выполнения таких вычислений. Рассмотрим последовательность степеней 2n mod 11:
2 4 8 5 10 9 7 3 6 1
Здесь числа от 1 до 10 появляются в виде псевдослучайной последовательности.
Теорема 2
Пусть p является простым числом. Существует такое a, что для каждого 1≤ b ≤ p-1, существует такое 1≤ x ≤ p-1, что ax ≡ pb, a не обязательно равно 2.
Степени 2 mod 7 равны 2, 4, 1. Далее числа повторяются, а числа 3, 5, или 6 не могут быть получены никогда. Рассмотрим некоторые следствия этой теоремы.
Следствие 4. Пусть a соответствует требованиям теоремы 2, тогда ap-1 ≡ p1.
Следствие 5. Для любого b ≠ 0, bp-1 ≡ p1.
Следствие 6. Если x ≡ (p-1)y, тогда bx ≡ pby
Лемма
Пусть b ≠ 0, d наименьшее положительное число, такое что bd ≡ p1. Тогда для любого с>0 c bc ≡ p1 d делит c без остатка. В частности для следствия 5, d делит p-1 без остатка.
.
Дополнительные материалы для изучения
Базовые определения и теоремы
Согласно теореме 2, если p простое число,
Дополнительные материалы для изучения
Базовые определения и теоремы
Согласно теореме 2, если p простое число,
Легко показать, что если a примитивный корень, ax примитивный корень в том и только том случае, если (x,p-1)=1. В этом примере это означает, что число примитивных корней равно
1222*(1/2)*(12/13)*(46/47)=552.
Таким образом, если мы выберем а произвольно, вероятность того, что это будет примитивный корень равна ~.45. Выбирая а наугад и тестируя, можно сравнительно быстро найти примитивный корень.
Наиболее современные системы шифрования используют асимметричные алгоритмы с открытым и секретным ключами, где нет проблемы безопасной транспортировки ключа. К числу таких систем относится алгоритм rsa (rivest-shamir-adleman - разработчики этой системы - Рональд Ривест, Ади Шамир и Леонард Адлеман, 1977 год), базирующийся на разложение больших чисел на множители.
Дополнительные материалы для изучения
Базовые определения и теоремы
Другие сходные алгоритмы используют целочисленные логарифмы, элиптические
Дополнительные материалы для изучения
Базовые определения и теоремы
Другие сходные алгоритмы используют целочисленные логарифмы, элиптические
шифрованный текст трудно (практически невозможно) расшифровать с использованием открытого ключа.
установление закрытого ключа на основе известного открытого должно быть нереализуемой задачей на современных ЭВМ. При этом должна существовать объективная оценка нижнего предела числа операций, необходимых для решения такой задачи.
К сожалению, эти алгоритмы достаточно медленно работают. По этой причине они могут использоваться для транспортировки секретных ключей при одном из традиционных методов шифрования-дешифрования.
Но следует помнить, что не существует абсолютных мер защиты. На рис. 7. показан способ нарушения конфиденциальности в системах с двухключевой схемой шифрования.
Рис. 7.
Дополнительные материалы для изучения
Базовые определения и теоремы
Если хакер умудрится вставить свою ЭВМ в
Дополнительные материалы для изучения
Базовые определения и теоремы
Если хакер умудрится вставить свою ЭВМ в
Дополнительные материалы для изучения
Базовые определения и теоремы
Решить эту проблему подмены ключей можно путем
Дополнительные материалы для изучения
Базовые определения и теоремы
Решить эту проблему подмены ключей можно путем
Начиная с 1997 года NIST (National Institute for Standards and Technology) совместно с промышленностью и криптографическим сообществом разрабатывал приемника для алгоритма DES (длина ключа 56 бит). В результате был создан алгоритм AES (Advanced Encryption Standard), который был опубликован в 2001 году (FIPS 197). AES представляет собой блочный, симметричный алгоритм шифрования с длиной блока 128 бит. Длина ключа может принимать значения 128, 192 или 256 бит (AES-128, AES-192 и AES-256, соответственно).
Кроме AES ISO/IEC 18033 (см. http://www.ni.dm.de, http://csrc.nist.gov и www.x9.org) специфицирует еще шесть различных блочных шифров (см. таблицу).
Если предположить, что ключ DES можно подобрать за секунду, то для подбора ключа AES-128 потребуется около 149 триллионов лет (кстати, возраст нашей вселенной всего 20 миллиардов лет).
Дополнительные материалы для изучения
Базовые определения и теоремы
Базовые характеристики блочных алгоритмов шифрования представлены в
Дополнительные материалы для изучения
Базовые определения и теоремы
Базовые характеристики блочных алгоритмов шифрования представлены в
Относительные уровни безопасности разных алгоритмов представлены ниже.
Дополнительные материалы для изучения
Базовые определения и теоремы
Стандарт на хэш функции задает документ
Дополнительные материалы для изучения
Базовые определения и теоремы
Стандарт на хэш функции задает документ
Дополнительные материалы для изучения
Базовые определения и теоремы
В настоящее время имеется три семейства криптосистем
Дополнительные материалы для изучения
Базовые определения и теоремы
В настоящее время имеется три семейства криптосистем
Системы IF (Integer Factorization - целочисленная факторизация), такие как система цифровой подписи, базирующаяся на RSA, использует сложность факторизации при работе с большими целыми числами.
Системы DL (Discrete Logarithm - целочисленный логарифм), такие как алгоритм цифровой подписи NIST (DSA, FIPS 186), базируются на вычислительной сложности оперирования с целочисленными логарифмами.
Системы EC (Elliptic Curve эллиптические кривые) являются сходными с DL примитивами. Они основываются на вычислительной сложности проблемы расчета целочисленных логарифмов через эллиптические кривые. Преимуществом этой системы является относительная ее сила по отношению к длине параметра. Другими словами эллиптические кривые предоставляют большую секретность на бит. Примером эллиптической кривой является уравнение типа Y2=X3 +aX+b.
Прочность всех этих алгоритмов основывается на трудностях, например, разложения больших чисел на сомножители или работы с целочисленными логарифмами. До сих пор не доказано, что не существует алгоритмов быстрого решения указанных проблем. Если такие алгоритмы будут найдены, придется придумывать другие системы шифрования. Следует также помнить, что в случае взлома машины, криптографические методы окажутся бесполезными, так как, например spyware, сможет иметь доступ к исходному тексту файлов или вводимых паролей.
Согласно закону Мура число компонентов на чип удваивается каждые 18 месяцев. Это можно интерпретировать как удвоение вычислительной мощности ЭВМ каждые 18 месяцев.
Дополнительные материалы для изучения
Базовые определения и теоремы
Развитие методов программирования и повышение быстродействия ЭВМ
Дополнительные материалы для изучения
Базовые определения и теоремы
Развитие методов программирования и повышение быстродействия ЭВМ
Современные системы подбора пароля способны проверять до нескольких миллионов вариантов паролей в секунду. Но нужно помнить, что украсть пароль с помощью spyware много проще и дешевле.
Для взлома паролей и подбора крипто-ключей могут использоваться botnet (сети, состоящие из взломанных машин). Ведь размеры таких сетей достигает нескольких миллионов, в 2009 году поставлен рекорд в 10.000.000. За год взламывается более 100.000.000 машин.
Рис. 8. Временная зависимость деградации безопасности шифров
Полезную информацию по системам шифрования можно получить на следующих серверах:
www.cs.hut.fi/crypto/
www.subject.com/crypto/crypto.html
www.rsa.com/
www.netscape.com/newsref/ref/rsa.html
www.microsoft.com/workshop/prog/security/pkcb/crypt.htm
www.semper.org/sirene/people/gerrit/secprod.html
www.fri.com/~rcv/deschall.htm
www.cl.cam.ac.uk/brute/
Дополнительные материалы для изучения
Базовые
Полезную информацию по системам шифрования можно получить на следующих серверах:
www.cs.hut.fi/crypto/
www.subject.com/crypto/crypto.html
www.rsa.com/
www.netscape.com/newsref/ref/rsa.html
www.microsoft.com/workshop/prog/security/pkcb/crypt.htm
www.semper.org/sirene/people/gerrit/secprod.html
www.fri.com/~rcv/deschall.htm
www.cl.cam.ac.uk/brute/
Дополнительные материалы для изучения
Базовые
Дополнительные материалы для изучения
Алгоритм DES
Стандарт шифрования DES (Data Encryption Standard) был разработан
Дополнительные материалы для изучения
Алгоритм DES
Стандарт шифрования DES (Data Encryption Standard) был разработан
DEA (ANSI x3.92-1981; www.cryptosoft.com/html/fips46-2.htm) оперирует с блоками данных размером 64 бита и использует ключ длиной 56 бит. Такая длина ключа соответствует 1017 комбинаций, что обеспечивало до недавнего времени достаточный уровень безопасности. В дальнейшем можно ожидать расширения ключа до 64 бит (например, LOKI) или вообще замены DES другим стандартом.
Входной блок данных, состоящий из 64 бит, преобразуется в выходной блок идентичной длины. Ключ шифрования должен быть известен, как отправляющей так и принимающей сторонам. В алгоритме широко используются перестановки битов текста.
Дополнительные материалы для изучения
Алгоритм DES
Вводится функция f, которая работает с 32-разрядными словами
Дополнительные материалы для изучения
Алгоритм DES
Вводится функция f, которая работает с 32-разрядными словами
32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1
Рис. 9. Алгоритм работы функции f
Для полученного 48-разрядного кода и ключа выполняется операция исключающее ИЛИ (XOR). Результирующий 48-разрядный код преобразуется в 32-разрядный с помощью S-матриц. На выходе S-матриц осуществляется перестановка согласно схеме показанной справа (числа представляют собой порядковые номера бит).
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Схема перестановки
Дополнительные материалы для изучения
Алгоритм DES
Преобразование начинается с перестановки бит (IP - Initial
Дополнительные материалы для изучения
Алгоритм DES
Преобразование начинается с перестановки бит (IP - Initial
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Полученный блок делится на две 32-разрядные части L0 и R0. Далее 16 раз повторяются следующие 4 процедуры:
Преобразование ключа с учетом номера итерации i (перестановки разрядов с удалением 8 бит, в результате получается 48-разрядный ключ).
Пусть A=Li, а J - преобразованный ключ. С помощью функции f(A,J) генерируется 32-разрядный выходной код.
Выполняется операция XOR для Ri f(A,J), результат обозначается Ri+1.
Выполняется операция присвоения Li+1=Ri.
Дополнительные материалы для изучения
Алгоритм DES
Структурная схема реализации алгоритма DEA показана на рис.
Дополнительные материалы для изучения
Алгоритм DES
Структурная схема реализации алгоритма DEA показана на рис.
Рис. 10. Структурная схема реализации
алгоритма DEA
Инверсная перестановка разрядов предполагает следующее размещение 64 бит зашифрованных данных (первым битом становится 40-ой, вторым 8-ой и т.д.).
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
S-матрицы представляют собой таблицы содержащие 4-ряда и 16 столбцов. Матрица S(1) представлена ниже (эта матрица, также как и те, что приведены в ссылке 2, являются рекомендуемыми).
No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
Дополнительные материалы для изучения
Алгоритм DES
Исходный 48-разрядный код делится на 8 групп по 6
Дополнительные материалы для изучения
Алгоритм DES
Исходный 48-разрядный код делится на 8 групп по 6
Преобразования ключей Kn (n=1,…,16; Kn = KS(n,key), где n - номер итерации) осуществляются согласно алгоритму, показанному на рис. 11.
Рис. 11. Алгоритм вычисления
последовательности ключей Kn
Для описания алгоритма вычисления ключей Kn (функция KS) достаточно определить структуру “Выбора 1” и “Выбора 2”, а также задать схему сдвигов влево (табл. 2). “Выбора 1” и “Выбора 2” представляют собой перестановки битов ключа (PC-1 и PC-2; табл. 1). При необходимости биты 8, 16,…, 64 могут использоваться для контроля четности.
Для вычисления очередного значения ключа таблица делится на две части С0 и D0. В С0 войдут биты 57, 49, 41,…, 44 и 36, а в D0 - 63, 55, 47,…, 12 и 4. Так как схема сдвигов задана (табл. 2) C1,D1; Cn, Dn и так далее могут быть легко получены из C0 и D0. Так, например, C3 и D3 получаются из C2 и D2 циклическим сдвигом влево на 2 разряда.
Дополнительные материалы для изучения
Алгоритм DES
Таблица 1
Таблица 2
Дополнительные материалы для изучения
Алгоритм DES
Таблица 1
Таблица 2
Дополнительные материалы для изучения
Алгоритм шифрования RSA
Алгоритм RSA (Rivest, Shamir и Adleman, 1978 год)
Дополнительные материалы для изучения
Алгоритм шифрования RSA
Алгоритм RSA (Rivest, Shamir и Adleman, 1978 год)
Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M), и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n=pq и число d, c (d,p-1)=(d,q-1)=1 (один из возможных способов выполнить это условие, выбрать d больше чем p/2 и q/2). Шифрование производится по формуле:
f(M) ≡ Md mod n,
где M и f(M) оба ≤ n-1.
Как ранее было показано, это может быть вычислено за разумное время, даже если M, d и n содержит весьма большое число знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. В соответствие со следствием 6, если
dc ≡ (p-1)1, тогда (Md)e ≡ p1.
Исходный текст числа M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.
Дополнительные материалы для изучения
Алгоритм шифрования RSA
Аналогично (Md)e ≡ qM, если dc ≡ (q-1)1.
Дополнительные материалы для изучения
Алгоритм шифрования RSA
Аналогично (Md)e ≡ qM, если dc ≡ (q-1)1.
Так как (Md)e - M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован (20 сентября 1983, действовал до 2000 года).
Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.
Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно - надо знать все возможные значения Mi.
Дополнительные материалы для изучения
Алгоритм шифрования RSA
Проясним использование алгоритма RSA на конкретном примере. Выбираем
Дополнительные материалы для изучения
Алгоритм шифрования RSA
Проясним использование алгоритма RSA на конкретном примере. Выбираем
На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1 Мбайт/сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма.
Дополнительные материалы для изучения
Алгоритм шифрования AES
Стандарт AES (Advanced Encryption Standard) является стандартом шифрования
Дополнительные материалы для изучения
Алгоритм шифрования AES
Стандарт AES (Advanced Encryption Standard) является стандартом шифрования
Он специфицирует алгоритм Rijndael http://www.nist.gov/CryptoToolkit
(смотри также http://csrc.nist.gov/ publications/fips/fips197/fips-197.pdf).
Этот алгоритм представляет собой симметричный блочный шифр, который работает с блоками данных длиной 128 бит и использует ключи длиной 128, 192 и 256 бит (версии AES-28; AES-192 и AES-256). Сам алгоритм может работать и с другими длинами блоков данных и ключей, но эта возможность в стандарт не вошла. При использовании 128-битного ключа для взлома шифрования по заявлению правительства США потребуется 149 триллионов лет.
Биты данных нумеруются с нуля, начиная со старших. В AES основным является полиномиальное представлением кодов. Так байт {01100011} следует представлять как:
x6 +x5 + x + 1.
Алгоритм AES производит операции над двумерными массивами байт, называемыми структурами (state). Структура состоит из 4 рядов по Nb байт. Nb равно длине блока, деленной на 32 (в данном стандарте Nb=4). Это позволяет обозначать структуру как sr,c или s[r,c], где 0≤r<4 и 0≤с<4.
Входной код (in), который является последовательностью 16 байт можно представить как:
s[r,c] =in[r +4c].
Дополнительные материалы для изучения
Алгоритм шифрования AES
При реализации алгоритма AES используются операции сложения
Дополнительные материалы для изучения
Алгоритм шифрования AES
При реализации алгоритма AES используются операции сложения
m(x) = x8 + x4 + x3 + x + 1 [1]
Вычисление произведения М байтов {b1} на {b2} здесь выполняется согласно следующему алгоритму:
M=[{b1}●{b2}] mod m(x). [2]
В этом случае обратная величина байта равна:
{b}-1 ={b} mod m(x) [3]
для умножения полубайтов (коды длиной 4 бита) используется неприводимый полином:
m2(x) = x4 + 1
Вычисление произведения М полубайтов {a} на {b} здесь выполняется следующим образом:
M=[{a}●{b}] mod m2(x). [2a]
M представляет собой полубайт d. Операцию умножения полубайтов {a} на {b} можно записать в матричном виде:
[4].
Дополнительные материалы для изучения
Алгоритм шифрования AES
Как было сказано выше длины ключей Nk (длина,
Дополнительные материалы для изучения
Алгоритм шифрования AES
Как было сказано выше длины ключей Nk (длина,
При запуске алгоритма шифрования входной блок данных копируется в массив state. После первоначального добавления к state ключа массив state преобразуется с помощью функции циклической обработки Nr раз (последний цикл несколько отличается от предыдущих, см. рис. 19.3). Результат преобразования заносится в выходной массив.
Шифрование
Рис. 12. Псевдокод, реализующий
процедуру шифрования
Описание алгоритма в С-подобном представлении отображено на рис. 12. Преобразования SubByte(), ShiftRows(), MixColumns() и AddRoundKey() осуществляют обработку массива state. Массив w[i] описан ниже.
Дополнительные материалы для изучения
Алгоритм шифрования AES
Преобразование SubByte()
Преобразование SubByte() является нелинейной подстановкой байтов, которое
Дополнительные материалы для изучения
Алгоритм шифрования AES
Преобразование SubByte()
Преобразование SubByte() является нелинейной подстановкой байтов, которое
Каждый байт заменяется на обратный мультипликативный (см. формулу 3). Байт {00} преобразуется сам в себя.
Для каждого байта осуществляется аффинное преобразование в поле GF(2), задаваемое формулой
[1.1]
Преобразование ShiftRows()
В преобразованиях ShiftRows() байты в последних трех рядах State циклически сдвигаются на разное число байт. Первый ряд (r=0) не сдвигается. Преобразование ShiftRows() осуществляется следующим образом:
для 0
Дополнительные материалы для изучения
Алгоритм шифрования AES
Преобразование MixColumns()
Преобразование MixColumns() обрабатывает State колонка за колонкой,
Дополнительные материалы для изучения
Алгоритм шифрования AES
Преобразование MixColumns()
Преобразование MixColumns() обрабатывает State колонка за колонкой,
Преобразование AddRoundKey()
В преобразовании AddRoundKey() к State добавляется ключ итерации (Round Key; побитовая операция XOR). Операция производится для каждого байта State.
Процедура расширения ключа
Ключи итерации вычисляются на основе ключа шифрования с помощью процедуры преобразования ключа (Key expansion). Эта процедура формирует Nb(Nr+1) слов. Алгоритм требует Nb слов и каждая из Nr итераций требует Nb слов. В результате получается линейный массив 4-байтовых слов, который обозначается [wi], где i лежит в пределах 0?i (см. рис. 13).
Функция SubWord() работает с входными байтами, преобразуя их с помощью S-таблиц. Операция выполняется для каждого из 4 входных байт.
Функция RotWord() использует в качестве входного слова [a0,a1,a2,a3] и возвращает слово [a1,a2,a3,a0].
Дополнительные материалы для изучения
Алгоритм шифрования AES
Рис. 13. Псевдокод реализации процедуры преобразования ключа
Дополнительные материалы для изучения
Алгоритм шифрования AES
Рис. 13. Псевдокод реализации процедуры преобразования ключа
Расшифровка
Все процедуры, описанные в предыдущем разделе, являются обратимыми. Целью дешифровки является обработка зашифрованного
Расшифровка
Все процедуры, описанные в предыдущем разделе, являются обратимыми. Целью дешифровки является обработка зашифрованного
Дополнительные материалы для изучения
Алгоритм шифрования AES
Рис. 14. Псевдокод процедуры дешифровки
Дополнительные материалы для изучения
Алгоритм шифрования AES
Преобразование InvShiftRows()
Процедура InvShiftRows() является обратной по отношению ShiftRows().
Дополнительные материалы для изучения
Алгоритм шифрования AES
Преобразование InvShiftRows()
Процедура InvShiftRows() является обратной по отношению ShiftRows().
Преобразование InvSubBytes()
Преобразование InvSubBytes() является обратной подстановкой байт, в которой S-таблица последовательно применяется для каждого из байтов State. Это достигается за счет обратного аффинного преобразования.
Преобразование InvMixColumns()
Процедура InvMixColumns() является обратной по отношению MixColumns() (см. раздел 1.3). Колонки рассматриваются как полиномы над полем GF(28).
Обратное преобразование AddRoundKey()
Преобразование AddRoundKey(), описанное в разделе 1.4 является обратимым, так как содержит только операции XOR.