Криптосистема без передачи ключей кратко

Обновлено: 05.07.2024

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

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

Принцип действия асимметричного шифрования

Схема передачи данных между двумя субъектами (А и Б) с использованием открытого ключа выглядит следующим образом:

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

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

Применение асимметричных алгоритмов

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

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

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

Асимметричные алгоритмы

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

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

Теоретически приватный ключ от асимметричного шифра можно вычислить, зная публичный ключ и механизм, лежащий в основе алгоритма шифрования (последнее — открытая информация). Надежными считаются шифры, для которых это нецелесообразно с практической точки зрения. Так, на взлом шифра, выполненного с помощью алгоритма RSA с ключом длиной 768 бит на компьютере с одноядерным процессором AMD Opteron с частотой 2,2 ГГц, бывшем в ходу в середине 2000-х, ушло бы 2000 лет.

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

Криптосистема с открытым ключом

Первую и наиболее известную систему с открытым ключом разработали в 1978 году американцы Р. Ривест (Rivest R.), Э. Шамир (Shamir A.) и Л. Адлеман (Adleman L.). По их именам эта система получила название RSA .

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

Упражнение 50 Пользователь системы RSA выбрал и . Какие из чисел 12, 33, 125, 513 он может выбрать для открытого ключа? Вычислить для них закрытый ключ .

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

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

Чаще всего их цель — деньги. Как они могут их получить?

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

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

И поэтому первое, что нужно сделать — это ответить для себя на несколько вопросов:

В каких файлах хранятся наиболее важные данные?
Какие аккаунты в соц сетях вы не можете потерять?
Что может причинить наибольший вред?
А что может ударить по вашей репутации?

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

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

Что такое шифрование?

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

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

Дешифрование — обратная операция. Преобразование нечитаемых данных в читаемые.

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

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

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

Хм, хорошо. Едем дальше. Слегка повысим напряжение.

Виды шифрования

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

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

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

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

Например, при смещении в 5 символов, символ, который стоит на первой позиции заменить на символ 6 позиции и так далее.

Наиболее стойким на данный момент считается алгоритм AES (Advanced Encryption Standard).
Стоит упомянуть еще один момент — мощность пароля. Мощность пароля измеряется в битах. Одним из наиболее распространенных решений является 128 или 256 бит. Это то количество бит, которое будет выделено для пароля. Так же это число означает количество паролей, которое вы можете получить при данном алгоритме шифрования. Но чем больше длина ключа, тем медленнее протекает процесс шифрования или дешифрования.

Но чаще всего используется асимметричное шифрование

И это приводит нас к новому типу шифрования.

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

Какие алгоритмы позволяют пользоваться этой технологией?

Rivest—Shamir—Adleman (RSA) (наиболее распространенный)
Elliptic curve cryptosystem (ECC)
Diffie—Hellman (DH)
El Gamal

Рассмотрим на примере алгоритма RSA.

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

1) Мы выбираем два простых числа. Желательно, чтобы они были достаточно близкими

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

n = p * s
f = (p — 1) * (s — 1)

3) Теперь наиболее затратная по времени часть — выбор экспоненты и произвольного коэффициента.

e = 5
k = 9
d = (k * f + 1)/e

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

Создать массив соответствий символу и его коду (например, ASCII код)
Применить алгоритм для каждого символа, создавая массив преобразованных значений
Перевести полученный массив обратно в строковый вид
Profit!

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

Среди всех найденных программ, наиболее удобной мне показалась gpg4usb.

Данная программа использует PGP шифрование. Почему я рекомендую использовать именно его?

Все просто. Этот тип шифрования до сих пор еще не удалось взломать. Никому. Так что пользуйтесь.

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

Первое, что необходимо сделать — скачать программу. Вы можете это сделать по ссылке:
ссылка.

Скажу сразу — эта программа кросс—платформенная. То есть вы можете использовать ее как на Windows, так и на Linux.

Второе — это создание пары ключей шифрования.

Это можно сделать, выполнив следующую последовательность действий:

Должно выглядеть примерно так:

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

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

Ну и в завершении статьи хочу поделиться полезной методикой: моделирование угроз и оценка рисков.

Первое, что нужно понять — нельзя обеспечить 100% безопасность, как и свести все риски к нулю. Нельзя получить 100% анонимность. Нельзя получить 100% безопасность (разве что не использовать телефон и ПК).

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

Мы должны использовать риск—ориентированный подход.

Риск = уязвимость * угрозы * последствия

Например, кража ноутбука. Что мы можем сделать? Зашифровать весь диск, добавить дополнительные этапы авторизации.

Рис. 1. Симметричное шифрование.

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

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

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

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

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

Рис. 3. Уилтфилд Диффи и Мартин Хеллман

Метод Диффи—Хеллмана основан на использовании свойств односторонних функций.

Односторонняя функция (one-way function) — это функция у = F(х), которая легко вычисляется для любого входного значения х, но обратная задача — определение х по заданному значению функции у — решается очень трудно.

Примером односторонней функции может служить простейшая функция двух аргументов F(p, q) = pq, представляющая собой произведение двух простых чисел р и q, она вычисляется сравнительно просто, даже если числа р и q очень большие. Но чрезвычайно сложно решить обратную задачу (называемую факторизацией) — по произведению подобрать исходные два простых числа.

Другой пример — функция Y(x) = D x mod Р, которая при некоторых ограничениях на параметры D и Р является односторонней, то есть, зная Y, а также параметры D и Р, нельзя без экстраординарных вычислительных усилий найти аргумент х.

Пусть, например, они договорились, что D = 7 и Р = 13, то есть функция имеет вид
Y(x) = 7 х mod 13.

Таблица 1. Действия Алисы и Боба в соответствии с алгоритмом Диффи—Хеллмана

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

Посмотрим, может ли Ева подобрать разделяемый секретный ключ Алисы и Боба. Пусть на шаге 3, когда Алиса и Боб посылали друг другу свои открытые ключи а(10) и b(9), Ева смогла перехватить эти числа (ведь канал является открытым) и теперь пытается вычислить разделяемый секретный ключ. Зная число a, которое Алиса послала Бобу, Ева хочет повторить действия Боба и вычислить разделяемый секретный ключ по формуле 10 B mod 13. Для этого ей требуется закрытый ключ Боба В, который он, однако, хранит секретно от всех. Зато Ева знает, что Боб использовал свой закрытый ключ В, когда вычислял значение своего открытого ключа — b.

То есть задача будет решена, если Ева сможет подобрать такое значение B, чтобы значение 7 В mod13 равнялось 9. Но именно это практически неразрешимо, поскольку функция 7 В mod13 является односторонней. Таким образом, Алиса и Боб действительно получили секретный ключ.

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

все параметры D, Р, A, В должны быть целыми положительными числами;
A и B должны быть большими числами порядка 10 100 ;
Р должно быть большим простым числом порядка 10 300 , причем желательно, чтобы (Р — 1)/2 также было простым числом;
число D не обязательно должно быть большим, обычно оно выбирается меньше десяти, D

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

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

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

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

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

Рис. 4. Модель асимметричной криптосистемы.

1. Алиса передает Бобу свой открытый ключ Е по незащищенному каналу в незашифрованном виде.

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

Функции, которые удовлетворяют данным требованиям, назвали односторонними функциями с потайным входом (trapdoor function). Некоторое время ученым не удавалось найти функции, удовлетворяющие этим критериям, поэтому идея асимметричного шифрования не находила практического применения. Наконец, в 1978 году трое американских ученых, Ривест, Шамир и Адлеман, предложили долгожданный алгоритм асимметричного шифрования RSA, названный так по первым буквам их фамилий — Rivest, Shamir, Adleman. В табл. 2 описываются основные шаги алгоритма RSA.

Таблица 2. Последовательность действий участников обмена данными в соответствии с алгоритмом RSA.

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

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

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

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

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

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

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

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

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

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

Что такое односторонняя функция? К примеру есть функция удвоение, т.е удвоить(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. Это и будет являться ключом.

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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