Криптология с открытым ключом


Содержание

Криптография для самых маленьких: шифрование с примерами на Python

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

Криптогра́фия (от др.-греч. κρυπτός — скрытый и γράφω — пишу) — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации), аутентификации (проверки подлинности авторства или иных свойств объекта), а также невозможности отказа от авторства.

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

Симметричное шифрование

Предположим, что сторона А хочет передать стороне Б секретную информацию. Стоп. А, Б — это всё некрасиво и неудобно. Именно поэтому в криптографии принято называть стороны обмена информацией именами Алиса (Alice) и Боб (Bob).

Итак, как Алиса может передать сообщение, чтобы никто, кроме Боба, не смог прочесть его? Необходимо как-то изменить эти данные по заранее согласованному с Бобом алгоритму. Простейшим способом реализации такой задачи является подстановочный шифр — алгоритм, при котором каждая буква сообщения заменяется на другую букву. Например, вместо первой буквы алфавита («А») Боб c Алисой будут использовать третью («В»), вместо второй («Б») — четвертую («Г») и так далее.

В этом случае алгоритмом шифрования является сдвиг букв алфавита, а ключом — цифра 2 (сдвиг на две позиции). Любой, кто знает алгоритм и ключ, сможет расшифровать сообщение Алисы. Кстати, попробуйте и вы расшифровать это сообщение — стретвоокуф. Вам поможет простой пример на Python 3:

Такие алгоритмы шифрования, при которых Алиса и Боб должны заранее придумать и согласовать одинаковый секрет, называются симметричными, а рассмотренный пример является самым простым алгоритмом этой группы и называется шифром Цезаря. Он считается небезопасным, и его не рекомендуется использовать. Наиболее популярными и достаточно криптостойкими симметричными алгоритмами являются 3DES и AES.

Асимметричное шифрование

Но что же делать, если Алиса и Боб находятся далеко друг от друга и не могут договориться об использовании одинакового секрета, поскольку есть некая Ева (от англ. eavesdropper — подслушивающий), которая так и хочет узнать тайны Алисы и Боба? В этом случае Боб может отправить Алисе замок, ключ от которого есть только у него. Алиса положит письмо в коробку и запрёт её на этот замок. Теперь ни Алиса, ни Ева не смогут открыть коробку и прочесть письмо.

«КРОК», Москва, Санкт-Петербург, Троицк, Челябинск, Воронеж, Иркутск, Краснодар, Нижний Новгород, Самара, Пермь, от 120 000 до 240 000 ₽

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

Наиболее популярным алгоритмом шифрования с открытым ключом является RSA. Вот как выглядит его реализация на языке Python с использованием библиотеки RSA:

Более подробно с алгоритмом RSA можно ознакомиться в другой нашей статье.

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

Заключение

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

Идея криптосистемы с открытым ключом

Читайте также:

  1. Добыча полезных ископаемых открытым способом
  2. Криптоанализ алгоритмов с открытым ключом
  3. Криптография с несколькими открытыми ключами
  4. Криптография с открытым ключом
  5. Криптография с открытым ключом (несимметричные шифры). Однонаправленная функция и однонаправленная функция с секретом. Проблема существования однонаправленной функции.
  6. Основные принципы построения криптосистем с открытым ключом
  7. Порядок работы с открытыми вопросами и проблемами уровня проекта в целом
  8. Приемы выращивания культурных растений, их научное обоснование. Объясните, почему минеральные удобрения необходимо вносить строго по норме и не хранить под открытым небом.
  9. Сложность вскрытия криптосистемы. Принцип Kerckhoffs. Атака полным перебором. Совершенная и вычислительная секретность. Понятие криптографического протокола.
  10. Сложность вскрытия криптосистемы. Принцип Kerckhoffs. Атака полным перебором. Совершенная и вычислительная секретность. Понятие криптографического протокола.
  11. Только целенаправленное продуктивное действие, по выражению К. С. Станиславского, является ключом к секретам речевого мастерства.

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

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

Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции (ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:

Имя (имя_пароль)
АЛИСА РОМАШКА
БОБ НАРЦИСС

Вход в систему теперь выглядит так:

Имя: АЛИСА
Пароль: ГЛАДИОЛУС

Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

В предыдущем примере используется односторонняя функция без лазейки, поскольку не требуется по зашифрованному сообщению получить исходное. В следующем примере рассматривается схема с возможностью восстановить исходное сообщение с помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:

Сообщение Выбранное имя Криптотекст
К Королёв
О Орехов
Р Рузаева
O Осипов
Б Батурин
К Кирсанова
А Арсеньева

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

Примеры таких криптотекстов:

Криптотекст 1 Криптотекст 2 Криптотекст 3

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

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

Пусть — пространство ключей, а и — ключи шифрования и расшифрования соответственно. — функция шифрования для произвольного ключа , такая что:

Здесь , где — пространство шифротекстов, а , где — пространство сообщений.

— функция расшифрования, с помощью которой можно найти исходное сообщение , зная шифротекст :

> — набор шифрования, а > — соответствующий набор для расшифрования. Каждая пара имеет свойство: зная , невозможно решить уравнение , то есть для данного произвольного шифротекста , невозможно найти сообщение . Это значит, что по данному невозможно определить соответствующий ключ расшифрования . является односторонней функцией, а — лазейкой. [3]

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

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

2. Чтобы послать сообщение Бобу, Алиса применяет функцию шифрования, определённую открытым ключом : , — полученный шифротекст.

3. Боб расшифровывает шифротекст , применяя обратное преобразование , однозначно определённое значением .

Дата добавления: 2015-04-24 ; Просмотров: 378 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Шифрование с открытым ключом: определение, особенности и виды алгоритмов

Идея шифрования с открытым ключом впервые была представлена в Стэнфордском университете в 1976 году М. Хеллманом, Р. Меркле и У. Диффи.

Двумя типами алгоритмов PKC являются: RSA — аббревиатура, получившая название в честь изобретателей: Rivest, Shamir and Adelman и DSA (Digital Signature Algorithm). Шифрование PKC эволюционировало для удовлетворения растущих безопасных коммуникационных потребностей многих секторов и отраслей промышленности, особенно военного направления. В отличие от криптографии с симметричным ключом, шифрование с открытым ключом — это относительно новая концепция.

Этапы возникновения криптосистем

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

Этапы процесса создания:

  • 1977 год. Изобретен RSA группой программистов Р. Ривест, А. Шамир и Л. Адлеман.
  • 1978 год. Создан МакЭлис из-за проблем декодирования для кодов Goppa.
  • 1979 год. Вышел Рабин, основанный на проблеме факторинга и связанный с RSA.
  • 1984 год. Издан Chor-Rivest.
  • 1985 год. Вышел Elgamal на основе дискретного логарифма.

Другие асимметричные криптосистемы:

  1. Эллиптический метод на основе эллиптических кривых, напоминающий Elgamal.
  2. Merkle / Hellman — на основе задачи о рюкзаке LUC, как и RSA, образует последовательность Лукаса.
  3. MNLN — такой же, как RSA.

Принцип шифрования, преимущества и недостатки

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

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

Такие криптосистемы применяются для шифрования данных открытым ключом, аутентификации и целостности. Известными примерами, основанными на асимметричных методах, являются OpenPGP или S/MIME, а также криптографические протоколы, такие как SSH, SSL/TLS и даже https основаны на асимметричных криптосистемах.

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

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

  1. Алгоритмы работают очень медленно: примерно в 10 000 раз медленнее симметричных.
  2. Большая требуемая длина ключа.
  3. Проблемы с несколькими получателями, когда сообщение должно быть дополнительно зашифровано.
  4. Средства защиты гибридных процедур.
  5. Риск безопасности, доступный для каждого открытого ключа, также является недостатком систем шифрования с открытым ключом.

Асимметричная криптография

PKC также известен как шифрование с открытым ключом, асимметричное шифрование, асимметричная криптография, асимметричный шифр, асимметричное шифрование ключей и шифрование Diffie-Hellman. PKC — это криптографический алгоритм и компонент криптосистемы, реализованный различными интернет-стандартами, включая безопасность транспортного уровня (TLS), Pretty Good Privacy (PGP), GNU Privacy Guard (GPG), Secure Socket Layer (SSL) и протокол передачи гипертекста (HTTP).

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

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

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

Метод открытого ключа

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

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

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

Генерация пары RSA

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

  1. Генерировать модуль RSA (n).
  2. Подбирают два простых числа p и q.
  3. Находят производный номер e. Число e должно быть больше 1 и меньше (p — 1) (q — 1). Для e и (p — 1) (q — 1) не должно быть общего фактора, кроме 1.
  4. Выполняют шифрование с помощью открытого ключа.
  5. Пара чисел (n, e) формирует открытый ключ RSA. Хотя n является частью открытого ключа, трудности с факторизацией такого числа обеспечивают, что злоумышленник не может найти за конечное время два простых числа (p & q), используемых для получения n. Это понимание является основой RSA.

Создание секретного ключа состоит в следующем. Частный ключ d вычисляется из p, q и e. Для заданных n и e существует единственное число d. Число d является инверсией e по модулю (p — 1) (q — 1). Это означает, что d — это число меньше (p — 1) (q — 1), но такое, что при умножении на e оно равно 1 по модулю (p — 1) (q — 1). Это соотношение написано математически следующим образом:

ed = 1 mod (p − 1)(q − 1).

Расширенный евклидовый алгоритм принимает p, q и e в качестве входных данных и дает d в качестве вывода. Ниже приведен пример создания пары RSA Key. Для удобства понимания простые числа p & q, взятые здесь, являются небольшими значениями. Практически эти значения должны быть очень значимыми.

  1. Пусть два простых числа равны p = 7 и q = 13. Таким образом, модуль n = pq = 7 x 13 = 91.
  2. Выбирают e = 5, что является допустимым выбором, так как нет числа, которое является общим фактором 5 и (p — 1) (q — 1) = 6 × 12 = 72, за исключением 1. Пара чисел (n, e) = (91, 5) формирует открытый ключ и может быть доступна всем, кому нужно отправить зашифрованные сообщения. Вход p = 7, q = 13 и e = 5. Выход будет равен d = 29.
  3. Убеждаются, что вычисленный d правильный — de = 29 × 5 = 145 = 1 mod 72.
  4. Следовательно, открытый ключ — это (91, 5) и закрытые ключи (91, 29).

Шифрование и дешифрование

Далее процесс шифрования и дешифрования является относительно простым и легко вычисляемым. Интересно, что RSA напрямую не работает со строками битов, как в случае симметричного метода. Он работает с числами по модулю n. Следовательно, необходимо представить открытый текст, как ряд чисел, меньших n.

  1. Предположим, что отправитель хочет отправить текстовое сообщение кому-то, открытый ключ которого (n, e).
  2. Затем отправитель представляет открытый текст как серию чисел меньше n.
  3. Зашифровать первый открытый текст P, который является номером по модулю n. Процесс шифрования — это простой математический шаг, C = Pe mod n.

Другими словами, зашифрованный текст C равен открытому тексту P, умноженному на него e раз, а затем уменьшенному по модулю n. Это означает, что C также меньше n. Возвращаясь к примеру генерации ключей с открытым текстом P = 10, получаем шифрованный текст: C = 105 mod 91.

  1. Процесс дешифрования для RSA также очень прост. Предположим, что получатель пары ключей (n, e) получил текст C.
  2. Получатель поднимает значение C для ключа d. Результат по модулю n будет открытым текстом P: Plaintext = Cd mod n.
  3. Возвращаемся снова к численному примеру, шифрованный текст C = 82 будет дешифрован до числа 10 с использованием закрытого ключа 29: Plaintext = 8229 mod 91 = 10.

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

Функция шифрования — считается однонаправленной функцией преобразования открытого текста в зашифрованный текст и может быть отменена только с помощью секретного ключа d. Трудность определения открытого и закрытого ключа шифрования RSA эквивалентна факторизации модуля n. Таким образом, злоумышленник не может использовать знание открытого ключа RSA для определения секретного ключа RSA, если только он не может определить n. Это также односторонняя функция, переход от значений p & q к модулю n легко, но обратное не представляется возможным.

Если любая из этих двух функций будет не односторонней, то RSA нарушается. Фактически, если технология факторинга эффективно разработана, то RSA больше не будет в безопасности. Сила шифрования RSA резко снижается против атак, если число p и q не являются простыми числами или выбранный открытый ключ e является небольшим числом.

Криптосистема ElGamal

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

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

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

  1. Выбор большого простого числа p. Обычно выбирается простое число от 1024 до 2048 бит.
  2. Выбор генераторного элемента g. Это число должно быть от 1 до p — 1.
  3. Он является генератором мультипликативной группы целых чисел по модулю р. Это означает, что для любого целого m co-prime с p существует целое число k такое, что g k = a mod n. Например, 3 является генератором группы 5 (Z 5 = <1, 2, 3, 4>).

Выбор секретного ключа. Частным ключом x является любое число, большее 1 и меньше, чем (p-1). Вычисление части открытого ключа. Значение y вычисляется по параметрам p, g и закрытому ключу x следующим образом:

Получение открытого ключа. Открытый ключ ElGamal состоит из трех параметров (p, g, y).Предположим, например, что p = 17 и g = 6. Можно утверждать, что 6 является генератором группы Z 17. Закрытый ключ x может быть любым числом больше 1 и меньше 71, поэтому выбирают x = 5. Затем значение y вычисляется следующим образом:

y = 65 mod 17 = 7.

Таким образом, закрытый ключ равен 62, а открытый ключ — (17, 6, 7).

Эллиптическая кривая ECC

Эллиптическая кривая криптографии (ECC) — это термин, используемый для описания набора криптографических инструментов и протоколов, безопасность которых основана на специальных версиях проблемы дискретного логарифма. Он не использует числа modulo p. ECC основан на наборах чисел, связанных с математическими объектами, называемыми эллиптическими кривыми. Существуют правила для добавления и вычисления кратных этих чисел, как и для чисел по модулю p.

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

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

  1. Простота управления ключами.
  2. Эффективное вычисление.

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

Более эффективный для шифрования.

Более эффективный для дешифрования.

Менее эффективный для дешифрования.

Более эффективный для дешифрования.

Для определенного уровня безопасности в RSA требуются длинные ключи.

Для того же уровня безопасности требуются очень короткие ключи.

Метод широко используется.

Новый метод и пока не очень популярный на рынке.

Протокол Secure Sockets Layer (SSL)

Интернет-трафик, который передает информацию через промежуточные компьютеры, может быть перехвачен третьей стороной:

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

Олицетворение может иметь две формы:

  1. Подмена. Человек может притворяться кем-то другим.
  2. Искажение. Человек или организация могут исказить себя. Например, названный сайт может претендовать на роль в онлайн-магазине мебели, когда он действительно получает платежи по кредитным картам, но никогда не отправляет какие-либо товары.

Криптография с открытым ключом обеспечивает защиту от интернет-атак.

Алгоритм шифрования и его преимущества безопасности

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

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

Цифровые сертификаты выдаются организациями, известными как центры сертификации (ЦС). Основными бизнес-приложениями для криптографии с открытым ключом являются:

  1. Цифровые подписи — контент цифровой подписи с закрытым ключом пользователя проверяется открытым ключом пользователя.
  2. Шифрование — содержимое зашифровывается с помощью открытого ключа и может быть расшифровано только с помощью частного ключа пользователя.

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

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

Инфраструктура открытого инструмента

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

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

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

Типичная экосистема PKI включает следующие ключевые компоненты:

  1. Политика сертификации — это спецификация безопасности, которая определяет структуру и иерархию экосистемы PKI, а также политики, связанные с управлением ключами, безопасным хранением, обработкой, аннулированием.
  2. Корневой центр сертификации (CA) отвечает за аутентификацию идентичностей в системе.
  3. Промежуточный ЦС сертифицирован корневым ЦС для конкретных целей, определенных политикой сертификата.
  4. Цифровые сертификаты обычно выдаются и подписываются центрами сертификации.
  5. База данных сертификатов хранит их записи.
  6. Служба аннулирования — это серверы, на которых публикуются обновленные списки отзыва сертификатов (CRL) или Online Certificate Status Protocol (OCSP), которые используют CRL и отвечают на проверки отзыва для устройств, которые сами не могут обрабатывать CRL.

Таким образом, асимметричные криптосистемы используются для шифрования, аутентификации и целостности. Если у злоумышленника отсутствует сертификат открытого ключа шифрования, он никогда не сможет воспользоваться секретными данными. Известными примерами, основанными на асимметричных методах, являются OpenPGP или S/MIME. Но также криптографические протоколы, такие как SSH, SSL/TLS или даже https, основаны на асимметричных криптосистемах.

Криптография для чайников

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

Криптография в повседневной жизни

Слово «криптография» для обывательского уха звучит загадочно и таинственно. Между тем сегодня шифрование на разных уровнях применяется буквально везде — от простого кодового замка на дипломате до многоуровневых систем защиты файлов ранга top secret. Мы сталкиваемся с ней, вставляя карточку в прорезь банкомата, совершая денежные переводы и покупки через интернет, болтая по Skype, отправляя письмо по e-mail и т. д. Если дело связано с информацией, то оно в подавляющем большинстве случаев связано и с криптологией. Однако при всем многообразии сфер применения сегодня существуют только два вида криптографических систем: с открытым ключом (асимметричные) и с секретным ключом (симметричные). В симметричных системах и для шифрования, и для расшифровки информации используется один и тот же ключ. Криптографические системы секретного ключа неуязвимы для дешифровщиков, пока ключ держится в тайне. Главная проблема здесь – в безопасной передаче этого ключа адресату информации, чтобы он мог ее расшифровать. Ведь он может быть перехвачен, если передается по ненадежному каналу. Другая проблема – отношения между пользователями, которые в данном случае строятся исключительно на доверии и не исключают появление третьей стороны, для которой будет интересна засекреченная информация и которая сможет договориться с одним из участников о передачи информации. Естественно, в ущерб другому участнику.

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

Такая схема шифрования сегодня применяется в защищенной электронной переписке на компьютерах, оснащенных модулем TPM (подробнее – в UP Special #12, 2006), однако и эту, внешне непреодолимую преграду интернет-мошенники обходят с помощью фишинга. Нет нужды взламывать защищенное соединение – чтобы получить всю необходимую информацию, достаточно убедить пользователя, что он находится на настоящем сайте банка или интернет-магазина, подставив поддельный. К несчастью, электронные мошенники не только умеют обходить криптозащиту. Хакеры с успехом используют ее в своем промысле.

ВИРУСНАЯ БРОНЯ

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

1. Модель с открытым ключом

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

2. Гибридная модель

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

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

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

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

Первый вирус этого класса появился в 1990 году и назывался он Whale. Он использовал целый ряд технологий, которые сегодня можно найти почти в каждом вирусе: изменение формы (полиморфизм и метаморфизм), технология стелс (когда вирус «прячется» в высшей памяти до уменьшения предела памяти, известной DOS) и бронирование (запутывание кода, его изменение в зависимости от архитектуры системы (8088 или 8086), использование технологии anti-debugger, с помощью которой при обнаружении программы-отладчика вирус блокирует клавиатуру и уничтожает себя).

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

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

КРУГОВАЯ ОБОРОНА

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

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

Существует два способа прозрачного шифрования. В первом основой является так называемый файл-контейнер. Это файл особого формата, в котором хранится вся защищенная информация. С помощью специального драйвера, входящего в состав криптографического продукта, он может подключаться к системе в качестве виртуального съемного диска. На Рабочем столе пользователя файл-контейнер отображается как логический раздел винчестера. Преимущества здесь очевидны: на виртуальном диске можно хранить любую информацию, кроме того, он мобилен – файл-контейнер можно легко перенести на любой другой компьютер.

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

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

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

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

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

ЧЕЛОВЕЧЕСКИЙ ФАКТОР

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

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

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

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

ТРЕТЬЯ СТОРОНА

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

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

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

История криптографии

Примерно в 1900 году до н. э. древние египтяне научились искажать иероглифы, чтобы кодировать послания.

В Древнем Риме активно использовался «шифр Цезаря», когда буквы менялись на другие с заданным сдвигом по алфавиту.

В 600-500 годы до н. э. древними евреями была создана упорядоченная система криптографии «Атбаш». У нас она известна как «тарабарская грамота». Суть метода такова: при письме одна буква алфавита заменяется другой, например вместо буквы «а» ставится буква «я» и т. д.

В 500 году до н. э. китайский ученый Сун Цзы в книге «Искусство войны» сформировал основные принципы разведки и контрразведки, а также методы обработки и защиты информации.

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

В XV веке математик из Италии Леон Батиста Альберти разработал первую математическую модель криптографии. Он же изобрел первое механическое устройство для шифрования секретных документов. На основе этого изобретения действовали все криптографические устройства вплоть до появления компьютеров.

В XVII веке Фрэнсис Бекон создал похожее устройство. В нем каждой букве алфавита соответствовало целых пять вариантов шифровки.

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

В 30-е годы XX века германские ученые создали шифровальную машину «Энигма». Чтобы разгадать принцип ее действия, в Англии была создана целая группа ученых. Им удалось это сделать только через три года после появления «Энигмы». Фактически она стала первым специализированным механическим компьютером.

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

В то же время американцы успешно взламывали японские шифры. У японцев были четыре самые известные шифровальные машины: RED, PURPLE, JADE и CORAL. Все они были взломаны американскими аналитиками.

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

Принципы Керкхоффса

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

  1. Шифр должен быть стойким к взлому. Дело в том, что одиночное зашифрованное сообщение может быть в принципе невзламываемым. Однако часто приходится посылать сотни сообщений, зашифрованных по одной и той же схеме, и в этом случае расшифровывать их с каждым разом будет проще. Степень стойкости зависит также и от того, сколько времени уйдет на взлом. В идеале это должно быть время, за которое взламываемая информация потеряет актуальность для криптоаналитика.
  2. Шифр должен быть простым в использовании. Имеется в виду, что лучше не пользоваться сложными шифросистемами, так как увеличивается время на кодирование-декодирование сообщения, а также возрастает вероятность использования их с ошибками.
  3. Стойкость шифра к взлому полностью зависит от обеспечения секретности ключа, а не алгоритма, поскольку используемым многими людьми алгоритм не может долго находиться в секрете. Ключ же проще сохранить в тайне или в крайнем случае заменить.

Криптография с открытым ключом

Криптография с открытым ключом

Проблема управления ключами была решена криптографией с открытым, или асимметричным, ключом, концепция которой была предложена Уитфилдом Диффи и Мартином Хеллманом в 1975 году[4].

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

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

Главное достижение асимметричного шифрования в том, что оно позволяет людям, не имеющим существующей договорённости о безопасности, обмениваться секретными сообщениями. Необходимость отправителю и получателю согласовывать тайный ключ по специальному защищённому каналу полностью отпала. Все коммуникации затрагивают только открытые ключи, тогда как закрытые хранятся в безопасности. Примерами криптосистем с открытым ключом являются Elgamal (названная в честь автора, Тахира Эльгамаля), RSA (названная в честь изобретателей: Рона Ривеста, Ади Шамира и Леонарда Адлмана), Diffie-Hellman (названная, правильно, в честь её создателей) и DSA, Digital Signature Algorithm (изобретённый Дэвидом Кравицом).

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

IntSystem.org

Случаи из опыта разработки различных WEB проектов. Интересные факты, статьи, впечатления. Программирование и все о нем в сфере WEB.

Асимметричное шифрование. Как это работает?

Мало кто знает как именно работает асимметричное шифрование. К примеру есть люди которые не считают протокол https какой-либо адекватной защитой передаваемых данных. И как правило на попытку убедить в обратном, они отвечают что-то в духе «если мы передаем зашифрованные данные, то мы должны сказать как их расшифровывать, а эту информацию можно перехватить и, следовательно, расшифровать данные». А на аргументы, что это не так и в основу положено асимметричное шифрование, поступает ответ «Ну и что?».

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

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

Кстати почему Алиса и Боб? Об этом есть кратенькая статья на википедии: Алиса, Боб и Ева. Чтобы было понятнее, Алиса и Боб хотят обменяться сообщениями, а Ева пытается эти сообщения перехватить и прочесть.

Немного истории

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

К примеру, Алиса зашифровала некоторое сообщение и хочет отправить его Бобу. Естественно, чтобы Боб его прочитал, ему нужен ключ которым было зашифровано данное сообщение. И тут возникает проблема, как передать ключ чтобы его никто не смог перехватить. Пытливые умы предложат — пусть передают при личной встрече, а потом общаются сколько захотят. Да, не спорю, выход. А теперь представьте на секунду, что ваша интернет почта, перед тем как вы авторизируетесь в ней, потребует вашей поездки до физического местоположения сервера с почтой. Удобно? Пожалуй не очень.

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

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

Немножко реальной жизни

Прежде чем изучать какой либо алгоритм, нужно представить как он работает. И самый простой способ — это сравнить его с работой чего-то в реальности.

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

Естественно на почте прочитать это письмо не могут, но его не может прочитать и сам Боб, так как у него нет ключа которым закрыт замок. Алиса, конечно, может взять еще один железный ящик, положить в него ключ от предыдущего, и отправить его Бобу, но его Боб тоже не сможет открыть…

Единственный путь это все же сделать дубликат ключа и дать его Бобу при личной встрече…

И вот начинает казаться что обмен ключами является неизбежной частью шифрования — или все-таки нет?

Представим другую картину. Распишу пошагово:

  1. Алиса кладет свое письмо в железный ящик и, заперев его на замок, отправляет Бобу.
  2. Боб при получении ящика, (внимание!) берет свой замок и, дополнительно заперев им ящик, отправляет обратно.
  3. Алисе ящик приходит уже с двумя замками (напомню с первым замком Алисы от которого у нее есть ключ, и со вторым — Боба, от которого ключ есть есть только у Боба).
  4. Алиса снимает свой замок, и отправляет ящик обратно Бобу
  5. Бобу приходит ящик с уже одним его замком от которого у него есть ключ
  6. Боб отпирает оставшийся его замок своим ключом, и читает сообщение

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

Вернемся к криптографии

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

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

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

Вернемся к математике

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

Что такое односторонняя функция? К примеру есть функция удвоение, т.е удвоить(4)=8, она двухсторонняя, т.к. из результата 8 легко получить исходное значение 4. Односторонняя функция — та функция после применения которой практически невозможно получить исходное значение. К примеру смешивание желтой и синей краски — пример односторонней функции. Смешать их легко, а вот получить обратно исходные компоненты — невозможно. Одна из таких функций в математике — вычисление по модулю.

За основу алгоритма Хеллман предложил функцию Y x (mod P). Обратное преобразование для такой функции очень сложно, и можно сказать что, по сути, заключается в полном переборе исходных значений.

К примеру вам сказали, что 5 x (mod 7) = 2, попробуйте найдите x, а? Нашли? А теперь представьте что за Y и P взяты числа порядка 10 300 .

Кстати сказать, для повышения стойкости, число P должно являться простым числом, а Y — являться первообразным корнем по модулю P. Но так как мы все же пытаемся понять теорию, то смысла заморачиваться на этом я не вижу.

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

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

Алиса Боб
Этап 1 Оба участника договариваются о значениях Y и P для общей односторонней функции. Эта информация не является секретной. Допустим были выбраны значения 7 и 11. Общая функция будет выглядеть следующим образом: 7 x (mod 11)
Этап 2 Алиса выбирает случайное число, например 3, хранит его в секрете, обозначим его как число A Боб выбирает случайное число, например 6, хранит его в секрете, обозначим его как число B
Этап 3 Алиса подставляет число A в общую функцию и вычисляет результат 7 3 (mod 11) = 343 (mod 11) = 2, обозначает результат этого вычисления как число a Боб подставляет число B в общую функцию и вычисляет результат 7 6 (mod 11) = 117649 (mod 11) = 4, обозначает результат этого вычисления как число b
Этап 4 Алиса передает число a Бобу Боб передает число b Алисе
Этап 5 Алиса получает b от Боба, и вычисляет значение b A (mod 11) = 4 3 (mod 11) = 64 (mod 11) = 9 Боб получает a от Алисы, и вычисляет значение a B (mod 11) = 2 6 (mod 11) = 64 (mod 11) = 9
Этап 6 Оба участника в итоге получили число 9. Это и будет являться ключом.

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

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

  • Значения a и P, и секретное число Боба B
  • или значения b и P, и секретное число Алисы A

Но секретные числа по каналу не передаются! Еве не получится восстановить ключ, не имея чьего-нибудь секретного числа. Почему — я писал выше, данная функция является односторонней. Попробуйте решите уравнение 4 x (mod 11) = 2 y (mod 11) найдя x и y.

Чтобы было понятнее, как работает схема Хеллмана, представьте шифр, в котором в качестве ключа каким-то образом используется цвет:

Допустим вначале, что у всех, включая Алису, Боба и Еву, имеется трехлитровая банка, в которую налит один литр желтой краски. Если Алиса и Боб хотят договориться о секретном ключе, они добавляют в свои банки по одному литру своей собственной секретной краски.

Алиса может добавить краску фиолетового оттенка, а Боб — малинового. После этого каждый из них посылает свою банку с перемешанным содержимым другому.

И наконец, Алиса берет смесь Боба и подливает в нее один литр своей секретной краски, а Боб берет смесь Алисы и добавляет в нее один литр своей секретной краски. Краска в обеих банках теперь станет одного цвета, поскольку в каждой находится по одному литру желтой, фиолетовой и малиновой краски.

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

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

Все равно непонятно? Тогда смотрим видео:

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

Асимметричное шифрование

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

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

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

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

Можно провести и более глубокую аналогию.

Представьте, что Алиса проектирует замок и ключ. Она бдительно охраняет ключ, но при этом изготавливает тысячи дубликатов замков и рассылает их по почтовым отделениям по всему миру. Если Боб хочет послать сообщение, он кладет его в коробку, идет на местный почтамт, просит «замок Алисы» и запирает им коробку. Теперь уже ему не удастся открыть коробку, но когда коробку получит Алиса, она сможет открыть ее своим единственным ключом.

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

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

Заключение

Что же, надеюсь что, поняв как работает асимметричное шифрование изнутри, вы станете больше ему доверять и соответственно чаще пользоваться SSL =)

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

Позволю себе вставить ссылку на один из прошлых моих постов: Коллизии хеш функций? асимметричное шифрование решает! — пример «нестандартного» применения асимметричного шифрования.

Что такое Криптография с Открытым Ключом?

Что такое Криптография с Открытым Ключом?

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

Как Работает Криптография с Открытым Ключом?

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

Поскольку алгоритмы асимметричного шифрования генерируют пары ключей, которые математически связаны, длина этих ключей намного больше, чем те, которые используются в симметричной криптографии. Эти более длинные — обычно от 1024 до 2048 битов — чрезвычайно затрудняют вычисление закрытого ключа из его открытого аналога. Один из наиболее распространенных алгоритмов асимметричного шифрования, используемый сегодня, известен как RSA. В схеме RSA ключи генерируются с использованием модуля, который получается с помощью умножения двух чисел (часто двух больших простых чисел). В основном, модуль генерирует два ключа (один открытый, который может быть общим, и другой закрытый, который должен храниться в секрете). Алгоритм RSA был впервые описан в 1977 году Ривестом, Шамиром и Адлеманом (следовательно, RSA) и остается основной составляющей криптографических систем с открытым ключом.

PKC как Инструмент Шифрования

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

Использование Цифровых Подписей

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

Ограничения

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

Применение Криптографии с Открытым Ключом

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

PKC также занимает видное место в технологиях блокчейн и криптовалют. При создании нового криптовалютного кошелька, генерируется пара ключей (открытый и закрытый ключ). Публичный адрес генерируется с использованием открытого ключа и может безопасно передаваться другим. C другой стороны используется закрытый ключ для создания цифровых подписей и проверки транзакций, и следовательно должен храниться в секрете. Как только транзакция была подтверждена путем валидации хэша, содержащегося в цифровой подписи, эта транзакция может быть добавлена в блокчейн регистр. Данная система проверки цифровой подписи гарантирует, что только лицо, у которого есть закрытый ключ, связанный с соответствующим криптовалютным кошельком, может выводить из него средства. Следует отметить, что асимметричные шифры, используемые в приложениях криптовалюты, отличаются от тех, которые используются в целях компьютерной безопасности. К примеру Bitcoin и Ethereum, используют специальный шифр, известный как Elliptic Curve Digital Signature Algorithm (Алгоритм Цифровой Подписи Эллиптической Кривой, ECDSA) для проверки транзакций.

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

Введение в криптографию и шифрование, часть первая. Лекция в Яндексе

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

Мы впервые публикуем эту лекцию вместе с расшифровкой. Начнём с первой части. Под катом вы найдёте текст и часть слайдов.

Я когда-то читал в МГУ лекции по крипте, и они занимали у меня по полгода. Я попытаюсь вам всё рассказать за два с половиной часа. Никогда этого не делал. Вот и попробуем.

Кто понимает, что такое DES? AES? TLS? Биноминальное отображение?

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

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

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

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

Когда люди говорят про крипту вообще, есть несколько фундаментальных принципов. Один из них — принцип Керкгоффса, который говорит, что open source в криптографии очень важен. Если точнее, он дает общее знание об устройстве протоколов. Смысл очень простой: криптографические алгоритмы, которые используются в той или иной системе, не должны быть секретом, обеспечивающим ее устойчивость. В идеале необходимо строить системы так, чтобы их криптографическая сторона была полностью известна атакующему и единственным секретом являлся криптографический ключ, который в данной системе используется.

Современные и коммерчески доступные системы шифрования — все или почти все или лучшие из них — построены из компонент, устройство и принцип работы которых хорошо известны. Единственная секретная вещь в них — ключ шифрования. Есть только одно известное мне значимое исключение — набор секретных криптографических протоколов для всевозможных государственных организаций. В США это называется NSA suite B, а в России это всякие странные секретные алгоритмы шифрования, которые до определенной степени используются военными и государственными органами.

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

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

Первый криптографический примитив — симметричные шифры.

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

Какие здесь важные нюансы? В большинстве распространенных алгоритмов симметричного шифрования, с которыми можно столкнуться, размер шифротекста всегда равен размеру открытого текста. Современные алгоритмы шифрования оперируют размерами ключей. Размер ключей измеряется в битах. Современный размер — от 128 до 256 бит для алгоритмов симметричного шифрования. Об остальном, в том числе о размере блока, мы поговорим позже.

Исторически, в условном IV веке до нашей эры, существовало два метода дизайна шифров: шифры подстановки и перестановки. Шифры подстановки — алгоритм, где в те времена заменяли одну букву сообщения на другую по какому-то принципу. Простой шифр подстановки — по таблице: берем таблицу, где написано, что А меняем на Я, Б на Ю и т. д. Дальше по этой таблице шифруем, по ней же дешифруем.

Как вы считаете, с точки зрения размера ключа насколько это сложный алгоритм? Сколько вариантов ключей существует? Порядок факториала длины алфавита. Мы берем таблицу. Как мы ее строим? Допустим, есть таблица на 26 символов. Букву А можем заменить на любой из них, букву Б — на любой из оставшихся 25, С — на любой из оставшихся 24… Получаем 26*25*24*… — то есть факториал от 26. Факториал размерности алфавита.

Если взять log226!, это будет очень много. Думаю, вы точно получите в районе 100 бит длины ключа, а то и поболее. Оказалось, что с точки зрения формального представления стойкости указанный алгоритм шифрования — довольно неплохой. 100 бит — приемлемо. При этом все, наверное, в детстве или юности, когда сталкивались с кодировками, видели, что такие алгоритмы дешифруются тривиально. Проблем с расшифровкой нет.

Долго существовали всякие алгоритмы подстановки в разных конструкциях. Одним из них, еще более примитивным, является шифр Цезаря, где таблица формируется не случайной перестановкой символов, а сдвигом на три символа: А меняется на D, B на Е и т. д. Понятно, что шифр Цезаря вместе со всеми его вариантами перебрать очень легко: в отличие от табличной подстановки, в ключе Цезаря всего 25 вариантов при 26 буквах в алфавите — не считая тривиального шифрования самого в себя. И его как раз можно перебрать полным перебором. Здесь есть некоторая сложность.

Почему шифр табличной подстановки такой простой? Откуда возникает проблема, при которой мы можем легко, даже не зная ничего про криптографию, расшифровать табличную подстановку? Дело в частотном анализе. Есть самые распространенные буквы — какая-нибудь И или Е. Их распространенность велика, гласные встречаются намного чаще, чем согласные, и существуют негативные пары, никогда не встречающиеся в естественных языках, — что-то вроде ЬЪ. Я даже давал студентам задание сделать автоматический дешифратор шифра подстановки, и, в принципе, многие справлялись.

В чем проблема? Надо статистику распределения букв исказить, чтобы распространенные буквы не так светились в зашифрованном тексте. Очевидный способ: давайте будем шифровать самые часто встречающиеся буквы не в один символ, а в пять разных, например. Если буква встречается в среднем в пять раз чаще, то давайте по очереди — сначала в первый символ будем зашифровывать, потом во второй, в третий и т. д. Далее у нас получится маппинг букв не 1 к 1, а, условно, 26 к 50. Статистика, таким образом, нарушится. Перед нами первый пример полиалфавитного шифра, который как-то работал. Однако с ним есть довольно много проблем, а главное, очень неудобно работать с таблицей.

Дальше придумали: давайте не будем шифровать такими таблицами, а попробуем брать шифр Цезаря и для каждой следующей буквы изменять сдвиг. Результат — шифр Виженера.

Берем в качестве ключа слово ВАСЯ. Берем сообщение МАША. Задействуем шифр Цезаря, но отсчитывая от этих букв. Например, В — третья буква в алфавите. Мы должны сдвинуть на три буквы соответствующую букву в открытом тексте. М сдвигается в П. А в А. Ш — на 16, перескочим букву А, получим, условно, Д. Я сдвинет А в Я. ПАДЯ.

Что удобно в получившемся шифре? Здесь было две одинаковых буквы, но в результате они зашифровались в разные. Это классно, потому что размывает статистику. Метод хорошо работал, пока где-то в XIX веке, буквально недавно на фоне истории криптографии, не придумали, как его ломать. Если посмотреть на сообщение из нескольких десятков слов, а ключ довольно короткий, то вся конструкция выглядит как несколько шифров Цезаря. Мы говорим: окей, давайте каждую четвертую букву — первую, пятую, девятую — рассматривать как шифр Цезаря. И поищем среди них статистические закономерности. Мы обязательно их найдем. Потом возьмем вторую, шестую, десятую и так далее. Опять найдем. Тем самым мы восстановим ключ. Единственная проблема — понять, какой он длины. Это не очень сложно, ну какой он может быть длины? Ну 4, ну 10 символов. Перебрать 6 вариантов от 4 до 10 не очень сложно. Простая атака — она была доступна и без компьютеров, просто за счет ручки и листа бумаги.

Как из этой штуки сделать невзламываемый шифр? Взять ключ размера текста. Персонаж по имени Клод Шэннон в ХХ веке, в 1946 году, написал классическую первую работу по криптографии как по разделу математики, где сформулировал теорему. Длина ключа равна длине сообщения — он использовал XOR вместо сложения по модулю, равному длине алфавита, но в данной ситуации это не очень принципиально. Ключ сгенерирован случайным образом, является последовательностью случайных бит, и на выходе тоже получится случайная последовательность бит. Теорема: если у нас есть такой ключ, то подобная конструкция является абсолютно стойкой. Доказательство не очень сложное, но сейчас не буду про него говорить.

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

Возьмем два сообщения: МАША, зашифрованная ключом ВАСЯ, и другое слово, у которого ключ тоже был ВАСЯ, — ВЕРА. Получим примерно следующее: ЗЕШЯ. Сложим два полученных сообщения, причем так, чтобы два ключа взаимно удалились. В итоге получим лишь разницу между осмысленным шифротекстом и осмысленным шифротекстом. На XOR это делается удобнее, чем на сложении по длине алфавита, но разницы практически никакой.

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

Помимо шифров подстановки, были еще шифры перестановки. С ними тоже все довольно просто. Берем сообщение ВАСЯИ, записываем его в блок какой-то длины, например в ДИДОМ, и считываем результат так же.

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

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

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

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

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

Из этой истории есть одно занятное исключение — шифроблокноты. Речь идет о настоящей шпионской истории про настоящий шпионаж. Некие люди, которым нужна абсолютно устойчивая коммуникация, генерируют случайные числа — например, буквальным бросанием кубика или буквальным выниманием шаров из барабана, как в лото. Создают два листа, где печатают эти случайные числа. Один лист отдают получателю, а второй оставляют у отправителя. При желании пообщаться они используют этот поток случайных чисел в качестве ключевого потока. Нет, история взята не из совсем далекого прошлого. У меня есть настоящий радиоперехват от 15 октября 2014 года: 7 2 6, 7 2 6, 7 2 6. Это позывной. 4 8 3, 4 8 3, 4 8 3. Это номер шифроблокнота. 5 0, 5 0, 5 0. Это количество слов. 8 4 4 7 9 8 4 4 7 9 2 0 5 1 4 2 0 5 1 4 и т. д. 50 таких числовых групп. Не знаю где, где-то не в России сидел какой-нибудь человек с ручкой и карандашом у обычного радиоприемника и записывал эти цифры. Записав их, он достал похожую штуку, сложил их по модулю 10 и получил свое сообщение. Другими словами, это реально работает, и подобное сообщение нельзя взломать. Если действительно были сгенерированы хорошие случайные числа и он впоследстии сжег бумажку с ключом, то осуществить взлом нельзя никак, совсем.

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

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

Самый исторически распространенный алгоритм подобного рода называется RC4. Он был разработан Роном Ривестом лет 25 назад и активно использовался очень долго, был самым распространенным алгоритмом для TLS, всех его различных вариантов, включая HTTPS. Но в последнее время RC4 начал показывать свой возраст. Для него существует некоторое количество атак. Он активно используется в WEP. Была одна хорошая лекция Антона, история, которая показывает: плохое применение пристойного даже по нынешним меркам алгоритма шифрования приводит к тому, что компрометируется вся система.

RC4 устроен несложно. На слайде целиком описана его работа. Есть внутренний байтовый стейт из 256 байт. На каждом шаге этого стейта есть два числа, два указателя на разные байты в стейте. И на каждом шаге происходит сложение между этими числами — они помещаются в некоторое место стейта. Полученный оттуда байт является следующим байтом в числовой последовательности. Вращая эту ручку таким образом, выполняя подобное действие на каждом шаге, мы получаем каждый следующий байт. Мы можем получать следующий байт числовой последовательности вечно, потоком.

Большое достоинство RC4 — в том, что он целиком внутрибайтовый, а значит, его программная реализация работает довольно быстро — сильно быстрее, в разы, если не в десятки раз быстрее, чем сравнимый и существовавший примерно в одно время с ним шифр DES. Поэтому RC4 и получил такое распространение. Он долго был коммерческим секретом компании RSA, но потом, где-то в районе 90-х годов, некие люди анонимно опубликовали исходники его устройства в списке рассылки cypherpunks. В результате возникло много драмы, были крики, мол, как же так, какие-то неприличные люди украли интеллектуальную собственность компании RSA и опубликовали ее. RSA начала грозить всем патентами, всевозможными юридическими преследованиями. Чтобы их избежать, все реализации алгоритма, которые находятся в опенсорсе, называются не RC4, а ARC4 или ARCFOUR. А — alleged. Речь идет о шифре, который на всех тестовых кейсах совпадает с RC4, но технически вроде как им не является.

Если вы конфигурируете какой-нибудь SSH или OpenSSL, вы в нем не найдете упоминания RC4, а найдете ARC4 или что-то подобное. Несложная конструкция, он уже старенький, на него сейчас есть атаки, и он не очень рекомендуется к использованию.

Было несколько попыток его заменить. Наверное, на мой предвзятый взгляд самым успешным стал шифр Salsa20 и несколько его последователей от широко известного в узких кругах персонажа Дэна Берштайна. Линуксоидам он обычно известен как автор qmail.

Salsa20 устроен сложнее, чем DES. Его блок-схема сложная, но он обладает несколькими интересными и классными свойствами. Для начала, он всегда выполняется за конечное время, каждый его раунд, что немаловажно для защиты от тайминг-атак. Это такие атаки, где атакующий наблюдает поведение системы шифрования, скармливая ей разные шифротексты или разные ключи за этим черным ящиком. И, понимая изменения во времени ответа или в энергопотреблении системы, он может делать выводы о том, какие именно процессы произошли внутри. Если вы думаете, что атака сильно надуманная, это не так. Очень широко распространены атаки подобного рода на смарт-карты — очень удобные, поскольку у атакующего есть полный доступ к коробке. Единственное, что он, как правило, не может в ней сделать, — прочитать сам ключ. Это сложно, а делать все остальное он может — подавать туда разные сообщения и пытаться их расшифровать.

Salsa20 устроен так, чтобы он всегда выполнялся за константное одинаковое время. Внутри он состоит всего из трех примитивов: это сдвиг на константное время, а также сложение по модулю 2 и по модулю 32, 32-битных слов. Скорость Salsa20 еще выше, чем у RC4. Он пока что не получил такого широкого распространения в общепринятой криптографии — у нас нет cipher suite для TLS, использующих Salsa20, — но все равно потихоньку становится мейнстримом. Указанный шифр стал одним из победителей конкурса eSTREAM по выбору лучшего поточного шифра. Их там было четыре, и Salsa — один из них. Он потихоньку начинает появляться во всяких опенсорс-продуктах. Возможно, скоро — может, через пару лет — появятся даже cipher suite в TLS с Salsa20. Мне он очень нравится.

На него имеется некоторое количество криптоанализа, есть даже атаки. Снаружи он выглядит как поточный, генерируя на основе ключа последовательность почти произвольной длины, 2 64 . Зато внутри он работает как блочный. В алгоритме есть место, куда можно подставить номер блока, и он выдаст указанный блок.

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

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

В Salsa указанная проблема решена, поскольку в нем на вход поступает в том числе и номер блока, который надо сгенерировать. Дальше к номеру блока 20 раз применяется алгоритм. 20 раундов — и мы получаем 512 бит выходного потока.

Самая успешная атака — в 8 раундов. Сам он 256-битный, а сложность атаки в 8 раундов — 250 или 251 бит. Считается, что он очень устойчивый, хороший. Публичный криптоанализ на него есть. Несмотря на всю одиозность личности Берштайна в этом аспекте, мне кажется, что штука хорошая и у нее большее будущее.

Исторически поточных шифров было много. Они первые не только в коммерческом шифровании, но и в военном. Там использовалось то, что называлось линейными регистрами сдвига.

Какие тут проблемы? Первая: в классических поточных шифрах, не в Salsa, чтобы расшифровать последнее значение гигабайтного файла, последний байт, вам нужно сначала сгенерировать последовательность на гигабайт. От нее вы задействуете только последний байт. Очень неудобно.

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

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

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

Размер блока в современных шифрах — как правило, 128 бит. Бывают разные вариации, но как правило, речь идет про 128 или 256 бит, не больше и не меньше. Размер ключа — точно такой же, как для поточных алгоритмов: 128 или 256 бит в современных реализациях, от и до.

Из всех широко распространенных блочных шифров сейчас можно назвать два — DES и AES. DES очень старый шифр, ровесник RC4. У DES сейчас размер блока — 64 бита, а размер ключа — 56 бит. Создан он был в компании IBM под именем Люцифер. Когда в IBM его дизайном занимался Хорст Фейстель, они предложили выбрать 128 бит в качестве размера блока. А размер ключа был изменяемый, от 124 до 192 бит.

Когда DES начал проходит стандартизацию, его подали на проверку в том числе и в АНБ. Оттуда он вернулся с уменьшенным до 64 бит размером блока и уменьшенным до 56 бит размером ключа.

20 лет назад вся эта история наделала много шума. Все говорили — наверняка они туда встроили закладку, ужасно, подобрали такой размер блока, чтобы получить возможность атаковать. Однако большое достоинство DES в том, что это первый шифр, который был стандартизован и стал тогда основой коммерческой криптографии.

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

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

У нее есть несколько интересных достоинств. Первое важное достоинство: функция F может быть любой. Она не должна обладать свойствами обратимости, она может и не быть линейной или нелинейной. Все равно шифр остается симметричным.

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

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

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

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

Потом мы его ксорим с раундовым ключом, размер которого — тоже 48 бит, и получаем 48-битное значение.
Затем оно попадает в набор функций, которые называются S-боксы и преобразуют каждый бит входа в четыре бита выхода. Следовательно, на выходе мы из 48 бит снова получаем 32 бита.

И наконец, окончательная перестановка P. Она опять перемешивает 32 бита между собой. Все очень несложно, раундовая функция максимально простая.

Самое интересное ее свойство заключается в указанных S-боксах: задумано очень сложное превращение 6 бит в 4. Если посмотреть на всю конструкцию, видно, что она состоит из XOR и пары перестановок. Если бы S-боксы были простыми, весь DES фактически представлял бы собой некоторый набор линейных преобразований. Его можно было бы представить как матрицу, на которую мы умножаем наш открытый текст, получая шифротекст. И тогда атака на DES была бы тривиальной: требовалось бы просто подобрать матрицу.

Вся нелинейность сосредоточена в S-боксах, подобранных специальным образом. Существуют разные анекдоты о том, как именно они подбирались. В частности, примерно через 10 лет после того, как DES был опубликован и стандартизован, криптографы нашли новый тип атак — дифференциальный криптоанализ. Суть атаки очень простая: мы делаем мелкие изменения в открытом тексте — меняя, к примеру, значение одного бита с 0 на 1 — и смотрим, что происходит с шифротекстом. Выяснилось, что в идеальном шифре изменение одного бита с 0 на 1 должно приводить к изменению ровно половины бит шифротекста. Выяснилось, что DES, хоть он и был сделан перед тем, как открыли дифференциальный криптоанализ, оказался устойчивым к этому типу атак. В итоге в свое время возникла очередная волна паранойи: мол, АНБ еще за 10 лет до открытых криптографов знало про существование дифференциального криптоанализа, и вы представляете себе, что оно может знать сейчас.

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

56 бит сейчас уже можно просто перебрать на кластере машин общего назначения — может, даже на одном. И это плохо. Что можно предпринять?

Просто сдвинуть размер ключа нельзя: вся конструкция завязана на его длину. Triple DES. Очевидный ответ был таким: давайте мы будем шифровать наш блок несколько раз, устроим несколько последовательных шифрований. И здесь всё не слишком тривиально.

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

Окей, 56 бит. Давайте возьмем два — k1 и k2. 56 + 56 = 112 бит. 112 бит даже по нынешним меркам — вполне приемлемая длина ключа. Можно считать нормальным всё, что превышает 100 бит. Так почему нельзя использовать два шифрования, 112 бит?

Одно шифрование DES состоит из 16 раундов. Сеть применяется 16 раз. Изменения слева направо происходят 16 раз. И он — не группа. Есть доказательство того, что не существует такого ключа k3, которым мы могли бы расшифровать текст, последовательно зашифрованный выбранными нами ключами k1 и k2.

Есть атака. Давайте зашифруем все возможные тексты на каком-нибудь ключе, возьмем шифротекст и попытаемся его расшифровать на всех произвольных ключах. И здесь, и здесь получим 2 56 вариантов. И где-то они сойдутся. То есть за два раза по 2 56 вариантов — плюс память для хранения всех расшифровок — мы найдем такую комбинацию k1 и k2, при которых атака окажется осуществимой.

Эффективная стойкость алгоритма — не 112 бит, а 57, если у нас достаточно памяти. Нужно довольно много памяти, но тем не менее. Поэтому решили — так работать нельзя, давайте будем шифровать три раза: k1, k2, k3. Конструкция называется Triple DES. Технически она может быть устроена по-разному. Поскольку в DES шифрование и дешифрование — одно и то же, реальные алгоритмы иногда выглядят так: зашифровать, расшифровать и снова расшифровать — чтобы выполнять операции в аппаратных реализациях было проще.

Наша обратная реализация Triple DES превратится в аппаратную реализацию DES. Это может быть очень удобно в разных ситуациях для задачи обратной совместимости.

Где применялся DES? Вообще везде. Его до сих пор иногда можно пронаблюдать для TLS, существуют cipher suite для TLS, использующие Triple DES и DES. Но там он активно отмирает, поскольку речь идет про софт. Софт легко апдейтится.

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

Однажды DES стал показывать свой возраст, с ним стало тяжело, и люди решили придумать нечто поновее. Американская контора по стандартизации, которая называется NIST, сказала: давайте проведем конкурс и выберем новый классный шифр. Им стал AES.

DES расшифровывается как digital encrypted standard. AES — advanced encrypted standard. Размер блока в AES — 128 бит, а не 64. Это важно с точки зрения криптографии. Размер ключа у AES — 128, 192 или 256 бит. В AES не используется сеть Фейстеля, но он тоже многораундовый, в нем тоже несколько раз повторяются относительно примитивные операции. Для 128 бит используется 10 раундов, для 256 — 14.

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

Как и в DES, в каждом раунде AES есть свои раундовые ключи. Все они генерируются из ключа шифрования для алгоритма. В этом месте AES работает так же, как DES. Берется 128-битный ключ, из него генерируется 10 подключей для 10 раундов. Каждый подключ, как и в DES, применяется на каждом конкретном раунде.

Каждый раунд состоит из четырех довольно простых операций. Первый раунд — подстановка по специальной таблице.

В AES мы строим байтовую матрицу размером 4 на 4. Каждый элемент матрицы — байт. Всего получается 16 байт или 128 бит. Они и составляют блок AES целиком.

Вторая операция — побайтовый сдвиг.

Устроен он несложно, примитивно. Мы берем матрицу 4 на 4. Первый ряд остается без изменений, второй ряд сдвигается на 1 байт влево, третий — на 2 байта, четвертый — на 3, циклично.

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

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

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

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

Мы повторяем 4 описанных шага 10 раз, и на выходе из 128-битного блока снова получаем 128-битный блок.

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

Производители современных процессоров, Intel и AMD, уже разработали ассемблерные инструкции для реализации AES внутри чипа, потому что стандарт довольно несложный. Как итог — AES еще быстрее. Если через DES на современной машинке мы можем зашифровать, например, 1-2 гигабита, то 10-гигабитный AES-шифратор находится рядом и коммерчески доступен обычным компаниям.

Блочный алгоритм шифрует блок в блок. Он берет блок на 128 или 64 бита и превращает его в блок на 128 или 64 бита.

А что мы будем делать, если потребуется больше, чем 16 байт?

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

Да, очевидно, побьем всё на блоки по 16 байт и зашифруем. Такое шифрование называется ECB — electronic code boot, когда каждый из блоков по 16 байт в случае AES или по 8 байт в случае DES шифруется независимо.

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

Примерно так выглядит картинка, зашифрованная в режиме ECB. Даже если мы представим себе, что шифр полностью надежен, кажется, что результат менее чем удовлетворительный. В чем проблема? В том, что это биективное отображение. Для одинакового входа всегда получится одинаковый выход, и наоборот — для одинакового шифротекста всегда получится одинаковый открытый текст.

Надо бы как-нибудь исхитриться и сделать так, чтобы результат на выходе все время получался разным, в зависимости от местонахождения блока — несмотря на то, что на вход подаются одинаковые блоки шифротекста. Первым способом решения стал режим CBC.

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

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

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

Однако у CBC есть несколько проблем.

О размере блока. Представьте: мы начали шифровать и, допустим, у нас DES. Если бы DES был идеальным алгоритмом шифрования, выход DES выглядел бы как равномерно распределенные случайные числа длиной 64 бита. Какова вероятность, что в выборке из равномерно распределенных случайных чисел длиной 64 бита два числа совпадут для одной операции? 1/(2 64 ). А если мы сравниваем три числа? Давайте пока прервемся.

Идея криптосистемы с открытым ключом

Читайте также:

  1. Добыча полезных ископаемых открытым способом
  2. Криптоанализ алгоритмов с открытым ключом
  3. Криптография с несколькими открытыми ключами
  4. Криптография с открытым ключом
  5. Криптография с открытым ключом (несимметричные шифры). Однонаправленная функция и однонаправленная функция с секретом. Проблема существования однонаправленной функции.
  6. Основные принципы построения криптосистем с открытым ключом
  7. Порядок работы с открытыми вопросами и проблемами уровня проекта в целом
  8. Приемы выращивания культурных растений, их научное обоснование. Объясните, почему минеральные удобрения необходимо вносить строго по норме и не хранить под открытым небом.
  9. Сложность вскрытия криптосистемы. Принцип Kerckhoffs. Атака полным перебором. Совершенная и вычислительная секретность. Понятие криптографического протокола.
  10. Сложность вскрытия криптосистемы. Принцип Kerckhoffs. Атака полным перебором. Совершенная и вычислительная секретность. Понятие криптографического протокола.
  11. Только целенаправленное продуктивное действие, по выражению К. С. Станиславского, является ключом к секретам речевого мастерства.

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

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

Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции (ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:

Имя (имя_пароль)
АЛИСА РОМАШКА
БОБ НАРЦИСС

Вход в систему теперь выглядит так:

Имя: АЛИСА
Пароль: ГЛАДИОЛУС

Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

В предыдущем примере используется односторонняя функция без лазейки, поскольку не требуется по зашифрованному сообщению получить исходное. В следующем примере рассматривается схема с возможностью восстановить исходное сообщение с помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:

Сообщение Выбранное имя Криптотекст
К Королёв
О Орехов
Р Рузаева
O Осипов
Б Батурин
К Кирсанова
А Арсеньева

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

Примеры таких криптотекстов:

Криптотекст 1 Криптотекст 2 Криптотекст 3

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

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

Пусть — пространство ключей, а и — ключи шифрования и расшифрования соответственно. — функция шифрования для произвольного ключа , такая что:

Здесь , где — пространство шифротекстов, а , где — пространство сообщений.

— функция расшифрования, с помощью которой можно найти исходное сообщение , зная шифротекст :

> — набор шифрования, а > — соответствующий набор для расшифрования. Каждая пара имеет свойство: зная , невозможно решить уравнение , то есть для данного произвольного шифротекста , невозможно найти сообщение . Это значит, что по данному невозможно определить соответствующий ключ расшифрования . является односторонней функцией, а — лазейкой. [3]

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

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

2. Чтобы послать сообщение Бобу, Алиса применяет функцию шифрования, определённую открытым ключом : , — полученный шифротекст.

3. Боб расшифровывает шифротекст , применяя обратное преобразование , однозначно определённое значением .

Дата добавления: 2015-04-24 ; Просмотров: 379 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

ОСОБЕННОСТИ ПРИМЕНЕНИЯ КРИПТОСИСТЕМ С ОТКРЫТЫМ КЛЮЧОМ

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

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

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

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

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

Применение криптосистем с открытым ключом [34]

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

Для стороны В процесс генерации пары ключей (открытый ключ KUb и личный ключ KRb) не должен порождать вычислительные трудности.

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

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

Для противника должно быть невозможным с точки зрения вычислений восстановление личного ключа KRb из имеющегося открытого ключа KUb.

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

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

Функции шифрования и дешифрования могут применяться в любом порядке:

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

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

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

у=ЛХ) вычисляется легко,

X=/ _1 (Y) практически не поддается вычислению.

В общем случае термин «легко вычислимый» означает, что проблема решается за так называемое полиномиальное время, рассматриваемое как функция длины вводимого значения. Так, если длина вводимого значения равна п битов, то полиномиальное время, требуемое для вычисления функции, пропорционально п а , где а является фиксированной константой. Такие алгоритмы называются алгоритмами, принадлежащими к классу Р (более подробно этот вопрос рассмотрен ранее в гл. 7). Термин «практически невычислимый» обозначает более размытое понятие. В общем случае можно сказать, что функция является практически невычислимой, если усилия по ее вычислению возрастают быстрее, чем полиномиальная функция от длины вводимого значения. Например, если вводимое значение имеет длину «битов, и время, требуемое для вычисления функции, пропорционально 2″, то такая функция считается практически невычислимой. К сожалению, для каждого конкретного алгоритма очень непросто выяснить, отражает ли этот алгоритм указанную степень сложности. К тому же в определении обычного понятия вычислительной сложности алгоритма рассматриваются оценки сложности либо в наихудшем случае, либо в среднем. Для криптографии эти оценки бесполезны, криптография требует практической невычис- лимости обратной функции почти для любого вводимого значения, а не для наихудшего или среднего случая.

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

Y=/(X) вычисляется легко, если известны к и X;

X=fkY) вычисляется легко, если известны к и Y;

X=/a ‘(Y) практически не поддается вычислению, если Y известно, а к— нет.

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

Илон Маск рекомендует:  Что такое код domdocumenttype &#62;internal_subset
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL