От искусства до науки: 10 фактов из истории криптографии

4.5. Шифры с открытым ключом

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

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

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

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

Алгоритм RSA

RSA (назван по имени авторов — Rivest, Shamir и Alderman) — это алгоритм с открытым ключом (public key), предназначенный как для шифрования, так и для аутентификации (цифровой подписи). Разработан в 1977 году. Он основан на трудности разложения очень больших целых чисел на простые сомножители (факторизации).

RSA — очень медленный алгоритм. Для сравнения, на программном уровне DES по меньше мере в 100 раз быстрее RSA; на аппаратном — в 1 000-10 000 раз, в зависимости от выполнения.

Алгоритм RSA заключается в следующем.

1. Берутся два очень больших простых числа p и q, и находятся их произведение n=pq и функция Эйлера от n:.
2. Выбирается случайное целое число D, взаимно простое с M, и вычисляется E, такое, что: .
3. Потом публикуется D и n как открытый ключ, E сохраняется в тайне (оно вместе с n составляет секретный ключ).
4. Пусть S — сообщение, длина которого должна быть в интервале (1..n); если длина его больше, то оно разбивается на части. Шифровка производится возведением в степень D по модулю n: .
5. Для расшифровки производится аналогичная операция — возведение в степень E по модулю n: .
   В последнем равенстве нетрудно убедиться, используя малую теорему Ферма.

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

Задача получения из открытого ключа {D, n} секретного ключа {E, n} сводится к задаче факторизации (разложения на простые сомножители) большого числа n. Такая задача для чисел длиной 100-150 десятичных разрядов пока не решена, и перспектив её решения в ближайшем будущем не видно. Однако, с другой стороны, пока не доказана и невозможность факторизации таких чисел (иначе, чем прямым перебором).

Алгоритм RSA запатентован в США. Его использование другими лицами не разрешено (при длине ключа свыше 56 бит). Правда, справедливость такого установления можно поставить под вопрос: как можно патентовать обычное возведение в степень? Но, тем не менее, RSA защищён законами об авторских правах.

Шифровка с открытым ключом

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

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

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

Предъявляемые требования

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

Главные требования:

• Образование. Криптографом может стать человек, окончивший один из профильных вузов (факультеты, где обучают криптографии и защите информации). Если специалист собирается работать в Вооружённых силах РФ, то ему предстоит получить дополнительные знания в армейской учебке.
• Знания. Шифровальщик должен хорошо знать математику, английский и основные языки программирования. Кроме этого, ему понадобятся знания в области кодирования информации.
• Навыки. Специалист должен обладать навыками грамотного общения и работы с секретными документами.
• Соблюдение режима секретности. Криптограф должен не только зашифровать данные, но и хранить в секрете всю полученную информацию. В большинстве случаев со специалистов берут подписку о неразглашении данных.

Квантовая криптография

Это уже не совсем основы криптографии, а более продвинутый уровень.

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

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

Адаптированный перевод «Understanding Cryptography From Math to Physics»

Варвара Николаева

Криптограф — профессия на все времена

05 мая 2019

5 мая люди очень редкой профессии отмечают свой профессиональный праздник.

Это шифровальщики.

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

С появлением радио и телеграфа в 20-м веке криптографическое дело стало очень популярным.

В связи с этим были изобретены новые методы шифрования.

Один из важнейших векторов развития шифрования связан с военным делом.

Во время Второй мировой войны советские инженеры совершили прорыв в области шифрования.

С 1941 по 1947 год было передано более 1,6 миллиона зашифрованных телеграмм и кодограмм.

Нагрузка на каналы связи иногда доходила до 1,5 тыс. телеграмм в сутки.

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

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

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

Жизнь была вторична.

Первично — материал, прошедший шифрование или дешифрование.

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

В годы войны советские шифровщики проделали огромную работу.

К весне 1942 года было расшифровано около 50 тысяч немецких телеграмм и радиограмм.

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

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

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

За образцовое выполнение правительственных заданий 54 специалиста были награждены орденами и медалями уже в начале войны.

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

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

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

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

Это действительно внимательные, усердные и трудолюбивые люди.

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

Имена некоторых криптографов и разработчиков программ безопасности широко известны.

Среди них — Евгений Касперский, окончивший 4-й (технический) факультет Высшей школы КГБ (сейчас Институт криптографии, связи и информатики Академии ФСБ России).

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

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

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

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

Все они — наше национальное достояние, наша гордость, память, боль и победа.

_____

Хеш-функции

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

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

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

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

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

Примеры хеш-алгоритмов

• Adler-32
• CRC
• SHA-1
• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• HAVAL
• MD2
• MD4
• MD5

• N-Hash

• RIPEMD-256
• RIPEMD-320
• Skein
• Snefru
• Tiger (TTH)
• Whirlpool
• ГОСТ Р34.11-94 (ГОСТ 34.311-95)
• IP Internet Checksum (RFC 1071)

Атака и требования

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

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

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

Начнём с основ: чуть-чуть о криптографии

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

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

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

Интересная многоходовочка… Ну а как она реализуется, спросит пытливый %username%? Все дело в так называемых односторонних функциях. Пусть есть функция . По известному аргументу вычислить значение функции проще, чем захватить Вестерос с тремя драконами и армией безупречных. Однако вычисление аргумента по известному значению функции является довольно-таки трудоемкой задачей.

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

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

Криптография и блокчейн

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

Хеш функции

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

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

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

Цифровые подписи

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

Среди множества схем криптографии на основе открытого ключа наиболее распространенной является схема на основе эллиптических кривых и схема, основанная на разложении множителей. В биткоине задействована первая схема – эллиптических кривых. Закрытый ключ в нем имеет размер в 32 байта, открытый – 33 байта, а подпись занимает около 70 байт.

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

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

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

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

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

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

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

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

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

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

5. Для обеспечения анонимности. Конечно, анонимность в интернете это весьма специфическое понятие, однако криптография может быть использована для этого. К примеру, те же прокси-сервера или браузер Tor.

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

Трудоустройство, зарплата, карьера

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

Места работы:

• IT-компания;
• частная или государственная фирма (отдели информационной безопасности);
• структуры Министерства обороны РФ;
• шифрорган ФСБ России.

Заработная плата у криптографа довольно высокая. Её минимальная планка находится на уровне 35 тыс. рублей, а максимальная — 220 тыс. рублей. Размер оклада зависит от места работы, квалификации специалиста, опыта и степени доверия.

4.6. Хэш-функции

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

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

Такая функция зовётся хэш-функцией. К её выбору следует отнестись тщательно. Неудачная хэш-функция позволит противнику подделать подписанное сообщение. Хэш-функция, так же, как и криптоалгоритмы, подлежит стандартизации и сертификации. В нашей стране она регламентируется ГОСТ Р-3411.

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

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

X=Rnd();
X₁=Hash(X);
X₂=Hash(X₁);
X₃=Hash(X₂);
...

Эта последовательность X…X_N хранится в памяти клиента во время сеанса связи.
При первом соединении и аутентификации на сервере клиент пересылает серверу
последнее число последовательности X_N. При следующем контакте в
качестве подтверждения, что запрос исходит от уже прошедшего проверку
клиента, пересылается предыдущее число — X_N-1. Поскольку
хэш-функция односторонняя, легко проверить, что X_N=Hash(X_N-1).
При следующем обращении к серверу пересылается X_N-2 и так далее.
Но для злоумышленника, даже если он перехватит соединение, станет
непосильной задачей из X_N-1 вычислить X_N, то есть,
взять обратную функцию от Hash().

Основные понятия

Протоколцикловroundпроходовpassшаговstep, action

• генерация нового (случайного) значения;
• вычисление значений функции;
• проверка сертификатов, ключей, подписей, и др.;
• приём и отправка сообщений.

сеансомролей

1. Участник с ролью «Отправитель» должен отправить участнику с ролью «Получатель» сообщение.
2. Участник с ролью «Получатель» должен принять от участника с ролью «Отправитель» сообщение.

1. 1-го апреля в 13:00 Алиса отправила Бобу сообщение.
2. 1-го апреля в 13:05 Боб принял от Алисы сообщение.

Защищённым протоколомпротоколом обеспечения безопасности

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

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

От: admin

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