Что такое асимметричная криптография? как работает асимметричное шифрование?

Алан-э-Дейл       24.07.2022 г.

Основные принципы построения криптосистем с открытым ключом

  1. Начинаем с трудной задачи P{\displaystyle P}. Она должна решаться сложно в смысле теории: не должно быть алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи P{\displaystyle P} за полиномиальное время относительно размера задачи. Более правильно сказать: не должно быть известного полиномиального алгоритма, решающего данную задачу — так как ни для одной задачи ещё пока не доказано, что для неё подходящего алгоритма нет в принципе.
  2. Можно выделить легкую подзадачу P′{\displaystyle P’} из P{\displaystyle P}. Она должна решаться за полиномиальное время и лучше, если за линейное.
  3. «Перетасовываем и взбалтываем» P′{\displaystyle P’}, чтобы получить задачу P″{\displaystyle P»}, совершенно не похожую на первоначальную. Задача P″{\displaystyle P»} должна по крайней мере выглядеть как оригинальная труднорешаемая задача P{\displaystyle P}.
  4. P″{\displaystyle P»} открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из P″{\displaystyle P»} получить P′{\displaystyle P’}, держится в секрете как секретная лазейка.
  5. Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как второй решает P″{\displaystyle P»}-задачу, первый использует секретную лазейку и решает P′{\displaystyle P’}-задачу.

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

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

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

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

Преимущества асимметричного шифрования

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

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

Шифрование с асимметричным ключом реализовано в алгоритме RSA и алгоритме обмена ключами Диффи-Хеллмана.

Виды алгоритмов симметричного шифрования

В зависимости от принципа работы алгоритмы симметричного шифрования делятся на два типа:

  • блочные;
  • потоковые.

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

К актуальным блочным алгоритмам относятся:

  • AES
  • ГОСТ 28147-89
  • RC5
  • Blowfish
  • Twofish

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

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

  • RC4
  • Salsa20
  • HC-256
  • WAKE

Важные моменты о симметричном и асимметричном шифровании

Самое главное отличие симметричного и асимметричного шифрования заключается в их подходе. Поэтому когда вы слышите или читаете статью про их сравнение вида «этот алгоритм лучше» без упоминания конкретики (определенных условий и задач), то можете смело начинать заниматься другими делами, так как это весьма бесполезное занятие аналогичное спору «Что лучше? Танк или пароход?». Без конкретики, ни то и ни другое. Тем не менее, есть важные моменты, о которых стоит знать:

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

2. Асимметричное шифрование позволяет стартовать безопасное соединение без усилий со стороны пользователя. Симметричный же алгоритм предполагает, что пользователю необходимо «еще узнать каким-то образом пароль». Тем не менее, стоит понимать, что асимметричные алгоритмы так же не обеспечивают 100% безопасности. К примеру, они подвержены атакам «человек по середине». Суть последней заключается в том, что между вами и сервером устанавливается компьютер, который для вас отсылает свой открытый ключ, а для передачи данных от вас использует открытый ключ сервера.

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

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

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

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

7. Наличие шифрования не является гарантом безопасности. Его всегда необходимо рассматривать в купе с другими подходами.

Оценки длин ключей для асимметричных криптосистем, бит

Год

Отдельные

пользователи

Корпорации

Государственные

организации

1995

  768

1280

1536

2000

1024

1280

1536

2005

1280

1536

2048

2010

1280

1536

2048

2015

1536

2048

2048

            Криптосистемы RSA реализуются как аппаратным, так и программным путем.

         Для аппаратной реализации операций зашифрования и расшифрования RSA разработаны специальные процессоры. Эти процессоры, реализованные на сверхбольших интегральных схемах (Сбис), позволяют выполнять операции RSA, связанные с возведением больших чисел в колоссально большую степень по модулю N, за относительно короткое время. И все же аппаратная реализация RSA примерно в 1000 раз медленнее аппаратной реализации симметричного криптоалгоритма DES.

         Одна из самых быстрых аппаратных реализаций RSA с модулем 512 бит на сверхбольшой интегральной схеме имеет быстродействие 64 Кбит/с. Лучшими из серийно выпускаемых СБИС являются процессоры фирмы CYLINK, выполняющие 1024-битовое шифрование RSA.

         Программная реализация RSA примерно в 100 раз медленнее программной реализации DES. С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптосистема RSA никогда не достигнет быстродействия симметричных криптосистем.

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

4.4. Схема шифрования Полига – Хеллмана

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

         Аналогично схеме RSA криптограмма  C и открытый текст  P  определяются из соотношений:

С = Ре mod n,

P = Cd mod n,

где  e*d º1  (по модулю некоторого составного числа).

         В отличие от алгоритма RSA в этой схеме число n  не определяется через два больших простых числа; число n  должно оставаться частью секретного ключа. Если кто-либо узнает значения e и n, он сможет вычислить значение d.

         не зная значений e или d, противник будет вынужден вычислять значение

e = logP C (mod n).

         Известно, что это является трудной задачей.

         Схема шифрования Полига – Хеллмана запатентована в США и Канаде.

4.5. Схема шифрования Эль Гамаля

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

         Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое число Р  и большое целое число G, причем  G < P. Числа  Р и G могут быть распространены среди группы пользователей.

         Затем выбирают случайное целое число X, причем X<P. Число  X  является   секретным   ключом   и  должно   храниться   в секрете.

         Далее вычисляют  Y = GX mod P. Число Y  является открытым ключом.

         Для того чтобы зашифровать сообщение M, выбирают случайное целое число k,  1< k< p –1, такое, что числа  к  и  (P –1) являются взаимно простыми.

         Затем вычисляют числа

a = GK mod P,

b = YK M mod P.

         Пара чисел (a,b)  является шифртекстом. Заметим, что длина  шифртекста  вдвое   больше   длины   исходного   открытого текста М.

         Для того чтобы расшифровать шифртекст  (a,b), вычисляют

                                            M = b/aX mod P.                                        (*)

Поскольку

aX º GKX mod P,

b/aX ºYKM/aX º GKXM/GKX º M (mod P),

то соотношение  (*)  справедливо.

            В реальных схемах шифрования необходимо использовать в качестве модуля P большое целое простое число, имеющее в двоичном представлении длину 512…1024 бит.

         При программной реализации схемы Эль Гамаля   скорость ее работы (на SPARC-II) в режимах шифрования и расшифрования при 160-битовом показателе степени для различных длин модуля P определяется значениями, приведенными в табл.4.2.

Таблица 4.2

Научное обоснование метода

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

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

На основании этого метода далее стали развиваться первые асимметричные системы шифрования. Основой нового алгоритма шифрования была функция Y x (mod P).

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

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

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

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

Алгоритмы асимметричного шифрования

К популярным алгоритмам с использованием ключей относятся: EIGamal, RSA, DSA, ECC и PKCS. Сегодня RSA — это самый применяемый алгоритм. Его можно найти в протоколах SSL/TLS, которые нужны для установления зашифрованного соединения между вами и веб-сайтами. Ключи RSA, как правило, имеют длину 1024, 2048 или 4096 бит. Правительства и крупные организации в настоящее время переходят к минимальной длине ключа в 2048 бит, т.к. считают, что первые два можно взломать намного быстрее.

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

Для чего используется ключи шифрования:

  • Для шифрования вашего интернет-соединения. Асимметричная криптография используется в SSL/TLS, которые помогают сделать ваше HTTPS соединение безопасным.
  • Для шифрования сообщений и почты, использующих протоколы OpenPGP или S/MIME.
  • Для цифровой подписи файлов и документов. С помощью асимметричной криптографии вы можете подтвердить, был ли файл поврежден или отредактирован во время транспортировки.
  • Для завершения криптографических операций. Это гарантирует, что только законные владельцы могут тратить свою крипто-валюту.

Недостатки асимметричного шифрования

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

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

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

ГОСТ 34.10-2018 описывает алгоритмы формирования и проверки электронной цифровой подписи с помощью операций в группе точек эллиптической кривой и функции хеширования. Длины секретного ключа 256 бит и 512 бит.

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

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

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

Суммой точек , эллиптической кривой называется точка , координаты которой определяются, как , , где .

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

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

Алгоритмы формирования и проверки электронной цифровой подписи.

Подпись создается по следующему алгоритму.

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

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

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

— на основе случайно сгенерированного целого числа , это число называют секретным ключом. Затем вычисляется точка на эллиптической кривой . Точка имеет координаты .

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

выходные данные: цифровая подпись которую добавляют к сообщению.

Теперь перейдем к алгоритму проверки подписи.

входные данные: сообщение c цифровой подписью и ключ проверки подписи

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

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

— определяется число , где целое число, которое соответсвует двоичному представлению хеш-кода . Причем если , то принимается за 1. Затем определяется .

— вычисляется точка эллиптической кривой , из которой получается .

— если , то подпись верна

выходные данные: подпись вена/неверна

4.2. Исторический экскурс

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

Широко известным историческим примером криптосистемы является так называемый шифр Цезаря,
который представляет из себя простую замену каждой буквы открытого текста третьей следующей за
ней буквой алфавита (с циклическим переносом, когда это необходимо). Например, «A» заменялась на
«D», «B» на «E», «Z» на «C».

Несмотря на значительные успехи математики за века, прошедшие со времён Цезаря, тайнопись
вплоть до середины 20 века не сделала существенных шагов вперёд. В ней бытовал дилетантский,
умозрительный, ненаучный подход.

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

Кстати, об априорной информации

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

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

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

Тогда же, в период второй мировой войны появились и первые профессиональные службы
дешифровки. Самая извесная из них — «Блечли-парк», подразделение английской службы разведки «МИ-5»

Популярные шифры

Чтобы понять основы шифрования, необходимо обратиться к популярным примерам.

Квадрат Полибия

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

С матрицей 6х6 (36 буквенно-цифровых знаков) мы можем начать замену. Например, буква «А» имеет адрес 1х1 или x=1, y=1. Эту запись можно упростить до 11. Другой пример: адрес буквы «N» будет 2х3 или x=2, y=3 или 23.

  • Сообщение: ENCRYPT ME 2 DAY
  • Шифротекст: 51–23–31–63–15–43–24 13–51 55 41–11–15

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

Шифр Цезаря

Шифр Цезаря считается самым первым. Цезарь использовал его для кодирования сообщений своим генералам, чтобы враги из Римской Империи не смогли прочитать приказы при перехвате. Шифр Цезаря имеет элементарную форму шифрования, и сегодня его легко взломать: алфавит просто сдвигается вправо или влево. Разные значения сдвига приводят к разным результатам шифровки. Число сдвига — это число букв, на которое происходит смещение в одну из сторон, для создания шифротекста.

Пример использования шифра со сдвигом влево на 3:

  • Сообщение: ENCRYPT ME
  • Шифротекст: HQFUBSW PH

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

Прим. пер. Существует более простой способ взлома шифра Цезаря — частотный анализ. Он заключается в подсчёте частоты встреч каждого символа в любом обычном тексте и в шифротексте. Потом символы с похожими частотами заменяются. Например, если в шифротексте чаще всего встречается буква «T», то она заменяется на букву «Е» для английского алфавита. Этот способ действует только для текстов свыше 300 символов.

Квадрат Виженера

Это усовершенствованный шифр Цезаря с разными значениями сдвига. Например, к первой букве сообщения применяется преобразование ROT5, ко второй — ROT16, etc.

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

Гость форума
От: admin

Эта тема закрыта для публикации ответов.