Мало кто знает как именно работает асимметричное шифрование. К примеру есть люди которые не считают протокол 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 =)

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

1. tv

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

2. Игорь

   Для чего нужна эта ахинея с открытыми ключами? Симметричные надёжней.
   Добрый день!
   Хороший сайт, понятно изложен материал, огромное спасибо автору. Попал сюда случайно в сентябре, когда искал информацию по практическому шифрованию.
   Пишу потому, что хочу спросить: Есть желающие узнать как найти числа для симметричного шифрования? Могу научить на пальцах как быстро проверить число Р на простоту (без поиска числа g) — но это вряд ли будет интересно. Самое интересное:
   Найти число Р любой длины и число g к нему. Никакие 2 в степени n плюс один (или минус один) при этом не использую. Естественно, это бесплатно. Есть даже сайт, где я выложил свою работу.

Уася Петровичъ

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

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

Евгений

Огромное спасибо за статью!
После прочтения почти все легло на свои полочки, обрело структуру, которую легко наращивать.
Имея такую структуру легко генерировать правильные вопросы (полочка для атак MiTM, отдельное спасибо Михаилу:)).

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

Видео прелестное, особенно учитывая его возраст.

PS: использование метафор для объяснения «сложных» систем честно говоря трудно переоценить. Еще раз спасибо!

dbzix

Из этой статьи я не уловил момент перехода от алгоритма Диффи-Хеллмана, где два абонента для получения секретного ключа обмениваются публичными данными и промежуточными результатами вычислений (в примере получилось целых 6 этапов) к тому этапу, где для шифрования используется некий публичный ключ, который затем дешифруется при помощи приватного (я здесь насчитываю всего 2 этапа передачи данных — отправка публичного ключа и отправка зашифрованного этим ключом сообщения).
Т.е. я понимаю, что где-то между двумя этими объяснениями наверняка кроется много математики, и в итоге объяснение сводится к «это работает именно так, просто поверь». Но было бы наверное проще понять этот внезапный переход, если бы аналогию с красками распространили на объяснение сути шифрования публичным ключом с последующим дешифрованием приватным. А пока получается какое-то «Б работает потому-что А», в то время как между А и Б чёткой связи не прослеживается. По крайней мере для меня.
Уважаемый автор, не будете ли вы так любезны пояснить мне сей мистический прыжок от А к Б? :) Спасибо!

Евгений

Добрый день,

Дано: есть формула Y^x (mod P).
пример в статье основывается на формуле 7^x (mod 11)

я взял для своего примера 4^x (mod 7)
и у меня не получилось прийти к общему ключу.
Вопрос: почему алгоритм в примере работает для 7^x (mod 11) и не работает для 4^x (mod 7)?

Jessi-jane

Андрей

Спасибо, статья отличная!
Только вот чуть не разобрался в алгоритме, в том, как высчитывать через модуль.
Не подскажите, как высчитывать число В, если число А меньше модуля?
Ну например:
3(mod 13) = ?

Я знаю, что если, например, нужно высчитать 625(mod 13), нужно 625/13, а потом наибольший возможный целый делитель (48) умножить на модуль (что здесь будет равняться 624), и наконец 625-624 = 1
Числа 625 и 1 сравнимы по модулю 13, так как 624 делится на 13.
Вот это я понимаю. А вот как быть если модуль больше числа а?

Yellow Horror

1. Атака «человек посередине», это серьёзная проблема. Насколько я могу судить, в рамках одной только криптографии она в принципе не решается: если принять, что Ева способна перехватить и незаметно подменить ВСЕ данные, поступающие к Алисе или исходящие от неё по ЛЮБЫМ каналам связи, никакое шифрование не поможет. Как минимум один сертификат должен быть получен Алисой из абсолютно надёжного источника. Но в случае, если злоумышленник может только прослушивать канал связи, а не менять данные в нём, асимметричное шифрование вполне надёжно.
2. Что касается возможности снимать один «слой шифра» из-под другого, этим свойством обладает банальная функция XOR, широко используемая в криптографии с древнейших времён по сей день. Не думаю, что её можно запатентовать:(

1. Дмитрий Амиров Автор

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

   Что касается функиции XOR — ее сложно назвать шифром, т.к. им она по своей сути не является.

   1. Yellow Horror

      Да ладно? Погуглите про «Шифр Вернама». Это система передачи сообщений с абсолютной криптоустойчивостью. И основана она именно на XOR. Если оставить в стороне некоторые организационные сложности (создание истинно случайных ключей с равномерным распределением, сохранение тайны шифроблокнота в недружелюбном окружении и надёжное уничтожение использованных ключей), ничего проще и надёжнее человечество ещё не придумало.

   2. Yellow Horror

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

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

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

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

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

      4. Алиса вычитает своё секретное число из каждого числа в блоках этого двукратно зашифрованного сообщения и отправляет получившееся сообщение Бобу.

      Алиса сняла свой «слой» шифра и теперь пересылает Бобу своё письмо, зашифрованное только ключом Боба. Который у Евы уже есть! Ева расшифровывает письмо и читает его, а также на всякий случай может восстановить ключ Алисы, пользуясь расшифрованным текстом письма и первой перехваченной ею шифрограммой.

Dmitriy

Здравствуйте. Хорошая статья, но я тоже не понял некоторые моменты, которые описали выше.
Именно переход от алгоритма получения секретного ключа обоими собеседниками (Алиса и Боб) (без их выкладывания в публичный доступ) к асимметричному шифрованию.
У вас написано, что сообщение кодируется на стороне Алисы публичным ключем, полученным от Боба. Но если мы зашифруем публичным ключём, то Ева сможет легко его получить и сама расшифровать, верно?
Ещё для меня осталось непонятным, как можно зашифровать публичным ключём и расшифровать только секретным на стороне Боба. То есть зашифровали словом «Дом» , а расшифровали словом «Мир» . Для меня это какая-то несуразица.
Исходя из этих очевидных пробелов (или у вас, или у меня) , я сделал вывод, что тут схема должна быть посложнее, чем на картинке. Скорее всего под стрелочкой от публичного ключа Боба к Алисе имеется в виду другое, а именно вся последовательность действий по получению «Y» и «P», получению промежуточных результатов и тд. Иными словами, я думаю, что при шифровке исходного сообщения якобы публичным ключем, на самом деле шифруется не публичным, а уже секретным, который вычисляется на каждой стороне по отдельности.

Ещё у меня возник вопрос о расшифровки дважды зашифрованного сообщения. Если взять,допустим, шифр Цезаря, где каждая буква шифруется другой буквой, стоящей, скажем, на 3 позиции дальше. Если Алиса зашифрует букву А в сообщении буквой Б, а потом Боб зашифрует эту букву Б буквой Г, то получить букву А из Г будет просто, причём в любом порядке. Правда это скорее всего будет работать только в тех случаях, если оба знают тип шифрации собеседника и при достаточно простых типах шифрации (моноалфавитные/полиалфавитные). Я тоже новичок в криптографии, так что это моё имхо;)

1. Dmitriy

   Забыл ещё спросить.
   В чём разница между симметричным и асимметричным способами?
   

   1. Dmitriy

      Я почитал, более менее как-то всё сгрупировал в уме.
      Отвечу на вопросы мною написаные, возможно, помогая тем самым другим читателям.
      1. По поводу

      У вас написано, что сообщение кодируется на стороне Алисы публичным ключем, полученным от Боба. Но если мы зашифруем публичным ключём, то Ева сможет легко его получить и сама расшифровать, верно?
      Ещё для меня осталось непонятным, как можно зашифровать публичным ключём и расшифровать только секретным на стороне Боба. То есть зашифровали словом «Дом» , а расшифровали словом «Мир» . Для меня это какая-то несуразица.

      В этой статье упомянут алгоритм RSA. Алгоритм симметричного шифрования. В нём действительно используется следующий алгоритм:
      1) Опираясь на некую одностороннюю функцию шифрования (функция, которую легко посчитать в одну сторону, но очень трудно в другую. А) мы создаём на получателе пару {открытый ключ;закрытый ключ}. Эта пара уникальна, то есть каждому открытому ключу соответствует уникальный закрытый ключ под эту одностороннюю функцию.
      
      3)Отправитель шифрует сообщение
      4)Передаёт получателю
      

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

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

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

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

      Симметричный — оба узла знают всю информацию для шифр./дешифр.

      Надеюсь, что кому-то помог;3

      1. Dmitriy

         В этой статье упомянут алгоритм RSA. Алгоритм Асимметричного шифрования Опечатался.

      2. Дмитрий Амиров Автор

         Гм… только сейчас заметил ваши комментарии. Приношу свои извинения.

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

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

         Я все равно не понял утверждение:
         2)Открытый ключ передаётся отправителю.
         3) Отправитель шифрует сообщение
         4)Передаёт получателю
         5)Получатель дешифрует с помощью закрытого ключа. Это сообщение нельзя дешифровать с помощью открытого ключа.

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

Роберт

Спасибо огромное!!!

Роман

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

А в видео, думаю, зря они используют вот это вот 3^(24*54), т.к. вообще не очевидно откуда оно взялось, или пояснили бы, что это условно.

RinswinD

Спасибо за статью. Всё очень доступно разъясняется.

grigory

Ну раздражает ведь всех эта неграмотность правописания — «одностороняя» , «примененны», «длинна», как будто уж в 5-м классе. А так, неплохо для понимания основ.

grigory

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

Allexys

Благодарю за понятную и нескучную статью! Наконец-то я врубился в основы:).

Ярослав

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

Это не совсем так. приведу пример:
— предположим что каждой букве соответствует цифровой код А = 1, Б = 2, В = 3 и т.д.;
— предположим что Алиса отправляет Бобу письмо, состоящее из единственной буквы А (для упрощения примера);

Алиса: накладывает свой шифр А + 2 = В

Боб: накладывает свой шифр В + 3 = Е
Боб: отправляет письмо Алисе
Алиса: снимает свой шифр Е — 2 = Г
Алиса: отправляет письмо Бобу
Боб: снимает свой шифр Г — 3 = А

Здесь число 2 — секретный ключ Алисы, 3 — секретный ключ Боба. Причем он может быть и не односимвольным. В принципе его длина ничем не ограничена.

Дмитрий

Я долго обходил стороной теоретические основы ассиметричного шифрования. Знал поверхностно — есть открытый ключ, которым шифруются данные, и есть закрытый, которым эти данные дешифруются. Но меня всегда напрягала мысль о реализации подобного шифрования.
Ваша статья во многом помогла, за это огромное вам спасибо!
Только к ее концу я опять увидел эту несуразицу — «шифруется открытым ключом». Ведь, строго говоря, шифруется сообщение не открытым ключом, а ключом, полученным на основе закрытого ключа отправителя и открытого ключа получателя (который, в свою очередь, был сгенерирован на основе закрытого ключа получателя). Ведь в таблице про Алису и Боба — они и только они смогли получить один и тот же ключ «9» — он и используется для шифрации и дешифрации сообщения. А вот получить этот ключ можно только на основе пары ключей — секретного (Алисы/Боба) и публичного(Боба/Алисы).
Образно — да, сообщение шифруется всегда секретным ключом отправителя (он, грубо говоря, постоянен) и публичным ключом получателя (он зависит от конкретного получателя), поэтому в описании шифрация «секретным» ключом опускается — и это опущение ломает всю стройность рассуждений.

кларксон

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

если я всем посылаю вопрос «сколько будет 2+2?», рассказываю как зашифровать ответ мне (рассказываю всем публичный ключ), и все мне направят ответ на вопрос, как я узнаю того, от кого именно я жду ответа, тобиш того с кем я хотел установить связь на самом деле?

1. Дмитрий Амиров Автор

   Тут вы немного неправильно ставите вопрос.

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

   UPD: написал статью про , я думаю это будет правильный ответ на ваш вопрос.

   1. кларксон

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

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

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

Beshot

Несколько раз перечитал эту статью и другие по теме, непонятен алгоритм использования ЭЦП в эл. документах. Если так как здесь: https://ru.wikipedia.org/wiki/Электронная_подпись , то возникают расхождения. Так все таки шифруем с помощью закрытого ключа или открытого?

1. Дмитрий Амиров Автор

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

   Если подпись «расшифровалась», то значит публичный ключ соответствует закрытому, а т.к. закрытый ключ априори имеется только у отправителя, то значит подписал документ именно отправитель.

   1. Beshot

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

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

      1. Дмитрий Амиров Автор

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

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

         Давайте рассмотрим на примере. Вы хотите мне прислать сообщение, я хочу убедится что прислали его мне именно вы. Поэтапно:
         1) Вы шифруете сообщение закрытым ключом
         2) Присылаете его мне
         3) Я обращаюсь к вам, и получаю от вас Ваш публичный ключ
         4) Полученное сообщение расшифровываю Вашим публичным ключом
         5) Если сообщение расшифровалось — значит послали его именно вы

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

         1. Beshot

            Ок, но как быть если требуется скрыть от любопытных глаз сообщение?

Аня

Добрый день! Статья понравилась, но остались вопросы (даже нашлась пара похожих в комментариях, но без ответов).
Если во второй части статьи всеже перейти к аналогии с Алисой и Бобом, в частности к числам А, В, а, в, Р и к полученному в примере числу 9, что из них будет закрытым ключом, а что открытым? Заранее спасибо за ответ!

1. Аня

   Не понятно, отправился мой комментарий или нет:(

2. Дмитрий Амиров Автор

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

Григорий

Симметричные криптосистемы

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

Основные сведения

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

Классическим примером таких алгоритмов являются симметричные криптографические алгоритмы , перечисленные ниже:

• Простая перестановка
• Одиночная перестановка по ключу
• Двойная перестановка
• Перестановка "Магический квадрат"

Простая перестановка

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

Одиночная перестановка по ключу

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

Двойная перестановка

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

Перестановка «Магический квадрат»

Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Подобные квадраты широко применялись для вписывания шифруемого текста по приведенной в них нумерации. Если потом выписать содержимое таблицы по строкам, то получалась шифровка перестановкой букв. На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3 х 3, если не принимать во внимание его повороты. Магических квадратов 4 х 4 насчитывается уже 880, а число магических квадратов размером 5 х 5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим.

В квадрат размером 4 на 4 вписывались числа от 1 до 16. Его магия состояла в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же числу - 34. Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила».

После этого шифрованный текст записывается в строку (считывание производится слева направо, построчно):
.ирдзегюСжаоеянП

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

История

Требования

Полная утрата всех статистических закономерностей исходного сообщения является важным требованием к симметричному шифру. Для этого шифр должен иметь «эффект лавины » - должно происходить сильное изменение шифроблока при 1битном изменении входных данных (в идеале должны меняться значения 1/2 бит шифроблока).

Также важным требованием является отсутствие линейности (то есть условия f(a) xor f(b) == f(a xor b)), в противном случае облегчается применение дифференциального криптоанализа к шифру.

Общая схема

В настоящее время симметричные шифры - это:

• блочные шифры . Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами . Результатом повторения раундов является лавинный эффект - нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.

• поточные шифры , в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования . Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-89 в режиме гаммирования), запущенного в специальном режиме.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

Типичным способом построения алгоритмов симметричного шифрования является сеть Фейстеля . Алгоритм строит схему шифрования на основе функции F(D, K), где D - порция данных, размером вдвое меньше блока шифрования, а K - «ключ прохода» для данного прохода. От функции не требуется обратимость - обратная ей функция может быть неизвестна. Достоинства сети Фейстеля - почти полное совпадение дешифровки с шифрованием (единственное отличие - обратный порядок «ключей прохода» в расписании), что сильно облегчает аппаратную реализацию.

Операция перестановки перемешивает биты сообщения по некоему закону. В аппаратных реализациях она тривиально реализуется как перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна - f(a) xor f(b) == f(a xor b)

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

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

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

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

• длина ключа
• число раундов
• длина обрабатываемого блока
• сложность аппаратной/программной реализации
• сложность преобразования

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

• AES (англ. Advanced Encryption Standard ) - американский стандарт шифрования
• ГОСТ 28147-89 - отечественный стандарт шифрования данных
• DES (англ. Data Encryption Standard ) - стандарт шифрования данных в США

Сравнение с асимметричными криптосистемами

Достоинства

• скорость (по данным Applied Cryptography - на 3 порядка выше)
• простота реализации (за счёт более простых операций)
• меньшая требуемая длина ключа для сопоставимой стойкости
• изученность (за счёт большего возраста)

Недостатки

• сложность управления ключами в большой сети. Означает квадратичное возрастание числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 - 499500 и т. д.
• сложность обмена ключами. Для применения необходимо решить проблему надёжной передачи ключей каждому абоненту, так как нужен секретный канал для передачи каждого ключа обеим сторонам.

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

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

Литература

• Гатчин Ю.А., Коробейников А.Г. Основы криптографических алгоритмов. Учебное пособие. - СПб.: СПбГИТМО(ТУ), 2002.
• Кон П. Универсальная алгебра. - М.: Мир. - 1968.
• Коробейников А. Г. Математические основы криптографии. Учебное пособие. СПб: СПб ГИТМО (ТУ), 2002.

Ссылки

• справочник, рассматривающий в том числе симметричное шифрование

Симметричные криптосистемы
Поточный шифр
Сеть Фейстеля

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

¦ Электронная цифровая подпись

¦ Современные технологии аутентификации. Смарт-карты

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

Шифрование как процесс своей историей уходит глубоко в века. Так, подстановочные шифры существуют уже около 2500 лет. Яркий тому пример – шифр Атбаш, который возник примерно в 600 году до нашей эры. Суть его работы заключалась в использовании еврейского алфавита в обратном порядке. Юлий Цезарь также использовал подстановочный шифр, который и был назван в его честь – шифр Цезаря. Суть шифра Цезаря заключалась в том, чтобы заменить каждую из букв другой, стоящей в алфавите, на три места дальше от исходной. Так, буква A превращалась в Д, Б преобразовывалась в E, Я преобразовывалась в Г и т. д.

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

Согласно классическим канонам ИБ с помощью шифрования обеспечиваются три основополагающих состояния безопасности информации.

¦ Конфиденциальность. Шифрование используется для сокрытия информации от неавторизованных пользователей при передаче или хранении.

¦ Целостность. Шифрование используется для предотвращения изменения информации при передаче или хранении. Яркий пример – контрольная сумма, полученная с использованием хэш-функции (то, что можно увидеть на FTP-серверах рядом с файлом (примерно так – dpofgj 0 93utm34tdfgb45ygf), который собираемся скачать).

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

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

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

¦ атака "грубой силой", или Brute Force (атаки "грубой силой" подразумевают подбор всех возможных вариантов ключей);

¦ поиск уязвимых мест в алгоритме.

Учитывая тот факт, что применяемые в настоящее время алгоритмы шифрования уже проверены "огнем и временем", совершенно очевидно, что взломщик будет использовать Brute Force. Взлом конфиденциальной информации, зашифрованной стойким алгоритмом и достаточно длинным ключом (к примеру, 512 бит), потребует со стороны взломщика использования "армии" суперкомпьютеров или распределительной сети из нескольких сотен тысяч машин плюс уйму времени и денег. Но если деньги есть, то почему бы и нет! Так, в 1997 году организация Electronic Frontier Foundation (EFF) анонсировала компьютерную систему, которая сможет найти ключ DES за четыре дня. Создание такой системы обошлось компании в $250 000. С помощью современного оборудования можно определить ключ DES посредством атаки "грубой силы" за 35 минут.

2.1. Алгоритмы и стандарты шифрования

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

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

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

Известны также и другие виды шифрования, такие, например, как тайнопись. Алгоритмы тайнописи по известным причинам не являются публичными: посторонним лицам неизвестен сам алгоритм шифрования; закон преобразования знают только отправитель и получатель сообщения. Одним из ярких примеров таких систем можно считать одноразовые блокноты. Именно одноразовые блокноты (One-time Pad, или OTP) можно назвать единственной теоретически невзламываемой системой шифрования. Одноразовый блокнот представляет собой список чисел в случайном порядке, используемый для кодирования сообщения. Как это и следует из названия, OTP может быть использован только один раз. Одноразовые блокноты широко применяются в информационных средах с очень высоким уровнем безопасности (но только для коротких сообщений). Так, в Советском Союзе OTP использовался для связи разведчиков с Москвой.

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

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

Популярными алгоритмами симметричного шифрования являются:

¦ DES (значительно устарел) и TripleDES (3DES);

¦ AES (Rijndael);

¦ ГОСТ 28147-89;

Основными параметрами алгоритмов симметричного шифрования можно считать:

¦ стойкость;

¦ длину ключа;

¦ количество раундов;

¦ длину обрабатываемого блока;

¦ сложность аппаратной/программной реализации.

Итак, начнем.

Data Encryption Standard (DES). Алгоритм Data Encryption Standard (DES) был разработан компанией IBM в начале 1970-х гг. Национальный институт стандартов и технологий США (NIST) принял на вооружение алгоритм (публикация FIPS 46) для DES в 1977 году. Дальнейшей модификации алгоритм подвергался в 1983, 1988, 1993 и 1999 годах.

До недавнего времени DES был "стандартом США", поскольку правительство этой страны рекомендовало применять его для реализации различных систем шифрования данных. Однако несмотря на то что изначально DES планировалось использовать не более 10-15 лет, попытки его замены начались только в 1997 году.

DES использует ключ длиной 56 бит. По сегодняшним меркам, такая длина ключа неприемлема. DES является блочным алгоритмом шифрования, обрабатывающим единовременно один 64-битный блок открытого текста. В алгоритме DES выполняются 16 циклов шифрования с различным подключом в каждом из циклов. Ключ подвергается действию своего собственного алгоритма для образования 16 подключей (рис. 2.1).

Рис. 2.1. Схема работы DES

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

Вводится функция F, которая работает с 32-разрядными словами исходного текста ® и использует в качестве параметра 48-разрядный ключ (J). Схема работы функции F показана на рис. 2.1. Сначала 32 входных разряда расширяются до 48, при этом некоторые разряды повторяются.

Для полученного 48-разрядного кода и ключа выполняется операция сложения по модулю 2. Результирующий 48-разрядный код преобразуется в 32-разрядный с помощью S-матриц.

Исходный 48-разрядный код делится на восемь групп по шесть разрядов. Первый и последний разряды в группе используются в качестве адреса строки, а средние четыре разряда – в качестве адреса столбца. В результате каждые шесть бит кода преобразуются в четыре бита, а весь 48-разрядный код – в 32-разрядный (для этого нужно восемь S-матриц). Существуют разработки, позволяющие выполнять шифрование в рамках стандарта DES аппаратным образом, что обеспечивает довольно высокое быстродействие.

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

В 1973 году Хорст Фейштель (Horst Feistel) в журнале Scientific American опубликовал статью "Cryptography and Computer Privacy", в которой раскрыл некоторые важные аспекты шифрования, а также ввел конструкцию, названную впоследствии сетью Фейштеля. Эта схема была использована в проекте Lucifer фирмы IBM, над которым работали Фейштель и Дон Копперсмит (Don Coppersmith). Данный проект был скорее экспериментальным, но стал базисом для Data Encryption Standard (DES). Итеративная структура алгоритма позволяла упростить его реализацию в аппаратных средах.

Уместно заметить, что следующие блочные шифры как раз таки используют классическую или модифицированную сеть Фейштеля в своей основе: Blowfish, Camellia, CAST, DES, FEAL, ГОСТ 28147-89, KASUMI, LOKI97, Lucifer, MacGuffin, MARS, MAGENTA, MISTY1, RC2, RC5, RC6, Skipjack, TEA, Triple DES, Twofish, XTEA.

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

Advanced Encrypt Standard (AES). Вскоре после выхода DES обнаружилась очевидная слабость алгоритма. Необходимость в принятии нового стандарта была более чем явной: небольшая длина ключа DES (56 бит) позволяла применить метод грубой силы против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала необходимого быстродействия. Модификация TDES обладала достаточной длиной ключа, но при этом была еще медленнее. TDES не просуществовал столь долго, чтобы можно было говорить о том, что алгоритм стоек и надежен. Ему на смену, как и следовало ожидать, пришел более стойкий и надежный алгоритм – AES, который, между прочим, был выбран в результате конкурса и принят в качестве американского стандарта шифрования правительством США. Немного о самом конкурсе.

2 января 1997 года NIST (Национальный Институт Стандартов и Технологий) объявляет о намерении найти замену DES, являвшемуся американским стандартом с 1977 года. NIST принял достаточное количество предложений от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Активный отклик со стороны открытого криптографического сообщества привел к объявлению конкурса 12 сентября 1997 года. Алгоритм могла предложить практически любая организация или группа исследователей. Минимальные требования к новому стандарту были следующими:

¦ это должен быть блочный шифр;

¦ длина блока должна составлять 128 бит;

¦ алгоритм должен работать с ключами длиной 128, 192 и 256 бит;

¦ использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах);

¦ ориентироваться на 32-разрядные процессоры;

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

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

20 августа 1998 года на первой конференции AES был объявлен список из 15 кандидатов, а именно: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent и Twofish.

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

В марте 1999 года прошла вторая конференция AES, а в августе 1999 года были объявлены пять финалистов, среди которых оказались: MARS, RC6, Rijndael, Serpent и Twofish. Все они были разработаны авторитетными криптографами, имеющими мировое признание. На 3-й конференции AES в апреле 2000 года все авторы представили свои алгоритмы.

В Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа, прошла третья конференция AES. Двухдневная конференция была разделена на восемь сессий по четыре в день. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FGPA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось количество раундов в алгоритмах-кандидатах. На второй день был проанализирован Rijndael с сокращенным количеством раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, еще раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael как о лидере рассказал Винсент Риджмен (Vincent Rijmen), заявивший о надежности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.

Строго говоря, AES и Rijndael не одно и то же, так как Rijndael поддерживает широкий диапазон длин ключей и блоков.

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

В отличие от ГОСТ 28147, который будет рассмотрен ниже, алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4 х 4, 4 х 6 или 4 х 8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.

Алгоритм Rijndael предусматривает выполнение четырех последовательных преобразований.

1. BS (ByteSub) – табличная замена каждого байта массива (рис. 2.2).

Рис. 2.2. Табличная замена каждого байта массива

2. SR (ShiftRow) – сдвиг строк массива. При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное количество байт, зависящее от размера массива. Например, для массива размером 4 х 4 строки 2, 3 и 4 сдвигаются на 1, 2 и 3 байта соответственно (рис. 2.3).

3. Следующим идет MC (MixColumn) – операция над независимыми столбцами массива, когда каждый столбец по определенному правилу умножается на фиксированную матрицу C(X) (рис. 2.4).

4. Заключительный этап – AK (AddRoundKey) – добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 2.5).

Рис. 2.3. Сдвиг строк массива

Рис. 2.4. Операция MixColumn

Рис. 2.5. Операция добавления ключа

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

Рис. 2.6. Последовательность раундов Rijndael

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

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

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

26 мая 2006 года на конференции Quo Vadis IV Николя Тадеуш Куртуа (польский криптограф, проживающий во Франции) представил практическое доказательство существования алгебраических атак, оптимизированных против шифра AES-Rijndael. За полтора часа на своем ноутбуке он осуществил демо-взлом всего лишь по нескольким шифртекстам близкого аналога Rijndael. Хотя это был только модельный шифр, он являлся таким же стойким, в него не было добавлено существенных слабостей, он имел такие же хорошие диффузионные характеристики и устойчивость ко всем известным до этого видам криптоанализа. Единственным отличием были лишь измененные в рамках модели алгебраических атак параметры S-блоков и уменьшенное для наглядности количество раундов. Однако этого было достаточно, чтобы убедить скептиков в реальности алгебраических атак и несовершенстве даже такого, казалось бы, совершенного метода шифрования.

ГОСТ 28147. Следующим алгоритмом симметричного шифрования, который мы рассмотрим, станет ГОСТ 28147-89. Это советский и российский стандарт симметричного шифрования, введенный 1 июля 1990 года. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптографическую защиту данных, хранимых и передаваемых в сетях ЭВМ, в отдельных вычислительных комплексах или ЭВМ.

Алгоритм был разработан в бывшем Главном Управлении КГБ СССР или в одном из секретных НИИ в его системе. Первоначально имел гриф (ОВ или СС – точно неизвестно), затем гриф последовательно снижался и к моменту официального проведения алгоритма через Госстандарт СССР в 1989 году был снят. Алгоритм остался ДСП (как известно, ДСП не считается грифом). В 1989 году стал официальным стандартом СССР, а позже, после распада СССР, федеральным стандартом Российской Федерации.

С момента опубликования ГОСТа на нем стоял ограничительный гриф "Для служебного пользования", и формально шифр был объявлен "полностью открытым" только в мае 1994 года. По известным причинам, история создания шифра и критерии его проектирования до сих пор неизвестны.

ГОСТ 28147-89 представляет собой блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма – уже известная нам сеть Фейштеля. Основным режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирования и гаммирования с обратной связью). Рассмотрим механизм работы алгоритма подробнее.

При работе ГОСТ 28147-89 информация шифруется блоками по 64 бита (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бита (N1 и N2). После завершения обработки субблока N1 его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, то есть применяется логическая операция XOR – исключающее ИЛИ), а затем субблоки меняются местами. Данное преобразование выполняется определенное количество раз (раундов): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции (рис. 2.7).

Рис. 2.7. Преобразование выполняется определенное количество раз

Первая операция подразумевает наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-битной частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-битных подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей, в зависимости от номера раунда и режима работы алгоритма.

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

Алгоритм, определяемый ГОСТ 28147-89, может работать в четырех режимах:

¦ простой замены;

¦ гаммирования;

¦ гаммирования с обратной связью;

¦ генерации имитоприставок.

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

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

В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бита. Гамма шифра – это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2 .

1. В регистры N1 и N2 записывается их начальное заполнение – 64-битная величина, называемая синхропосылкой.

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

3. Содержимое регистра N1 складывается по модулю (2 32 – 1) с константой C1, равной 2 24 + 2 16 + 2 8 + 2 4 , а результат сложения записывается в регистр N1.

4. Содержимое регистра N2 складывается по модулю 2 32 с константой C2, равной 2 24 + 2 16 + 2 8 + 1, а результат сложения записывается в регистр N2.

5. Содержимое регистров N1 и N2 подается на выход в качестве 64-битного блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).

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

Для расшифровки гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR.

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

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

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

Рассматривая режим генерации имитоприставок, следует определить понятие предмета генерации. Имитоприставка – это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-битный блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.

Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-битное содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2^.Чаще всего используется 32-битная имитоприставка, то есть половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы – в первую очередь электронная цифровая подпись.

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

Алгоритм ГОСТ 28147-89 считается достаточно сильным – в настоящее время для его раскрытия не существует более эффективных методов, чем упомянутый выше Brute Force. Высокая стойкость алгоритма достигается в первую очередь за счет большой длины ключа, равной 256 бит. К тому же при использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость ГОСТ 28147-89 уже при 32 раундах можно считать более чем достаточной, и это притом, что полный эффект рассеивания входных данных достигается уже после восьми раундов.

На сегодняшний день алгоритм ГОСТ 28147-89 полностью удовлетворяет всем требованиям криптографии и обладает теми же достоинствами, что и другие алгоритмы, но лишен их недостатков. К очевидным достоинствам этого алгоритма можно отнести:

¦ эффективность реализации и, соответственно, высокое быстродействие на современных компьютерах;

¦ бесперспективность силовой атаки (XSL-атаки в учет не берутся, так как их эффективность на данный момент полностью не доказана).

Однако же, как оно всегда и бывает, алгоритм не лишен недостатков: тривиально доказывается, что у ГОСТа существуют "слабые" ключи и S-блоки, но в стандарте не описываются критерии выбора и отсева "слабых". Кроме того, стандарт не специфицирует алгоритм генерации S-блоков (таблицы замен). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой – поднимает ряд проблем: нельзя определить криптостойкость алгоритма, не зная заранее таблицы замен; реализации алгоритма от различных производителей могут использовать разные таблицы замен и могут быть несовместимы между собой.

Кратко рассмотрим некоторые другие алгоритмы симметричного шифрования.

Blowfish. Blowfish представляет собой 64-битный блочный шифр, разработанный Шнайером (Schneier) в 1993 году. Этот шифр, как и многие другие, основан на алгоритме сети Фейштеля. Отдельный раунд шифрования данного алгоритма состоит из зависимой от ключа перестановки и зависимой от ключа с данными замены. Все операции основаны на операциях XOR и прибавлениях к 32-битным словам (XORs and additions on 32-bit words). Ключ имеет переменную длину (максимальная длина 448 бит) и используется для генерации нескольких подключевых массивов (subkey arrays). Шифр был создан специально для 32-битных машин и существенно быстрее ранее рассмотренного нами алгоритма DES.

IDEA (International Data Encryption Algorithm) был разработан К. Лейем (Lai) и Д. Месси (Massey) в конце 1980-х годов. Это шифр, состоящий из 64-битных повторяющихся блоков со 128-битным ключом и восемью раундами. Следует отметить, что, в отличие от ранее нами рассмотренных алгоритмов шифрования, IDEA не основан на сети Фейштеля, хотя процесс дешифрования аналогичен процессу шифрования. IDEA был сконструирован с учетом его легкого воплощения как программно, так и аппаратно. Ко всему прочему безопасность IDEA основывается на использовании трех несовместимых типов арифметических операций над 16-битными словами.

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

RC5 представляет собой довольно быстрый блочный шифр, разработанный Ривестом (Ronald Linn Rivest) специально для «RSA Data Security». Этот алгоритм параметричен, то есть его блок, длинна ключа и количество проходов (раундов) переменны.

Размер блока может равняться 32, 64 или 128 бит. Количество проходов может варьироваться от 0 до 2048 бит. Параметричность подобного рода делает RC5 необычайно гибким и эффективным алгоритмом в своем классе.

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

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

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

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

Открытый ключ вычисляется из секретного: kl = f(k2). Асимметричные алгоритмы шифрования основаны на применении однонаправленных функций. Согласно определению функция y = f(x) является однонаправленной, если ее можно легко вычислить для всех возможных вариантов x, а для большинства возможных значений y достаточно сложно вычислить такое значение x, при котором y = f(x) .

Примером однонаправленной функции может служить умножение двух больших чисел: N = S х G. Само по себе, с точки зрения математики, такое умножение представляет собой простую операцию. Однако обратная операция (разложение N на два больших множителя), называемая также факторизацией, по современным временным оценкам представляет собой достаточно сложную математическую задачу.

Ну что ж, рассмотрим некоторые из алгоритмов асимметричного шифрования.

Алгоритм Диффи-Хеллмана. В 1976 году Уитфилд Диффи (Whitfield Diffie) и Мартин Хеллман (Martin Hellman) разработали свою систему шифрования с открытым ключом. Система Диффи-Хеллмана разрабатывалась для решения проблемы распространения ключей при использовании систем шифрования с секретными ключами. Идея заключалась в том, чтобы применять безопасный метод согласования секретного ключа без передачи ключа каким-либо другим способом. Следовательно, необходимо было найти безопасный способ получения секретного ключа с помощью того же метода связи, для которого разрабатывалась защита. Суть алгоритма Диффи-Хеллмана заключается в следующем. Предположим, что двум точкам (S1 и S2) требуется установить между собой безопасное соединение, для которого необходимо согласовать ключ шифрования.

¦ S1 и S2 принимают к использованию два больших целых числа a и b, причем 1 < a < b.

¦ S1 выбирает случайное число i и вычисляет I = ai ? mod b. S1 передает I абоненту S2.

¦ S2 выбирает случайное число j и вычисляет J = aj ? mod b. S2 передает J абоненту S1 .

¦ S1 вычисляет k1 = Ji ? mod b.

¦ S2 вычисляет k2 = Ij ? mod b.

Имеем k1 = k2 = ai ? j х mod b, следовательно, k1 и k2 являются секретными ключами, предназначенными для использования при передаче других данных.

Даже если допустить, что злоумышленнику каким-то образом удастся прослушать передаваемый трафик, то ему будут известны a, b, I и J. Тем не менее остаются в секрете i и j. Уровень безопасности системы зависит от сложности нахождения i при известном I = ai ? mod b. Эта задача называется задачей дискретного логарифмирования и считается очень сложной (то есть с помощью современного вычислительного оборудования ее решить практически невозможно), если числа очень велики. Следовательно, a и b необходимо выбирать очень тщательно. Например, оба числа b и (b – 1)/2 должны быть простыми и иметь длину не менее 512 бит. Рекомендуемая длина чисел составляет 1024 бита.

Алгоритм RSA был разработан в 1978 году тремя соавторами и получил свое название по первым буквам фамилий разработчиков (Rivest, Shamir, Adleman). В основе стойкости алгоритма стоит сложность факторизации больших чисел и вычисления дискретных логарифмов. Основной параметр алгоритма RSA – модуль системы N, по которому проводятся все вычисления в системе, а N = R х S (R и S – секретные случайные простые большие числа, обычно одинаковой размерности).

Секретный ключ k2 выбирается случайным образом и должен соответствовать следующим условиям: 1 < k2 < F(N) и НОД (k2, F(N))= 1, где НОД – наибольший общий делитель. Иными словами, k1 должен быть взаимно простым со значением функции Эйлера F(N) , причем последнее равно количеству положительных целых чисел в диапазоне от 1 до N, взаимно простых с N, и вычисляется как F(N) = (R – 1) ? (S – 1) .

Открытый ключ kl вычисляется из соотношения (k2 х kl) = 1 ? mod F(N). Для этого используется обобщенный алгоритм Евклида (алгоритм вычисления наибольшего общего делителя). Зашифровка блока данных M по алгоритму RSA выполняется следующим образом: C = Mkl ? mod N. Поскольку в реальной криптосистеме с использованием RSA число k1 весьма велико (в настоящее время его размерность может доходить до 2048 бит), прямое вычисление Mk1 нереально. Для его получения применяется комбинация многократного возведения M в квадрат с перемножением результатов. Обращение данной функции при больших размерностях неосуществимо; иными словами, невозможно найти M по известным C, N и kl. Однако, имея секретный ключ k2, при помощи несложных преобразований можно вычислить M = Ck2 ? mod N. Очевидно, что, помимо собственно секретного ключа, необходимо обеспечивать секретность параметров R и S. Если злоумышленник добудет их значения, то сможет вычислить и секретный ключ k2.

В настоящее время криптосистема RSA применяется в самых различных продуктах, на различных платформах и во многих отраслях. Достаточно вспомнить ее использование в операционных системах Microsoft, Apple, Sun и Novell, чтобы представить всю "грандиозность" RSA. В аппаратной составляющей алгоритм RSA широко используется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, в криптографическом оборудовании Zaxus (Racal). Ко всему прочему, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Интернет, в том числе S/MIME, SSL и S/WAN, а также используется во многих правительственных учреждениях, государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.

Алгоритм Эль-Гамаля. Эль-Гамаль (Taher Elgamal) разработал вариант системы Диффи-Хеллмана. Он усовершенствовал этот алгоритм и получил один алгоритм для шифрования и один для обеспечения аутентификации. Алгоритм Эль-Гамаля не был запатентован (в отличие от RSA) и таким образом стал более дешевой альтернативой, так как не требовалась уплата лицензионных взносов. Поскольку этот алгоритм базируется на системе Диффи-Хеллмана, то его стойкость обеспечивается сложностью решения все той же задачи дискретного логарифмирования.

Алгоритм цифровой подписи (Digital Signature Algorithm). Алгоритм DSA был разработан правительством США как стандартный алгоритм для цифровых подписей (см. разд. 2.3). Данный алгоритм базируется на системе Эль-Гамаля, но позволяет осуществлять только аутентификацию. Конфиденциальность этим алгоритмом не обеспечивается.

Шифрование с использованием эллиптических кривых. Эллиптические кривые были предложены для использования в системах шифрования в 1985 году. Системы шифрования с использованием эллиптических кривых (ECC) основываются на отличной от факторизации или дискретного логарифмирования математической задаче. Данная задача заключается в следующем: имея две точки A и B на эллиптической кривой, такие что A = kB, очень трудно определить целое число k. Несмотря на некоторую «экзотичность», использование ECC перед алгоритмом RSA или Диффи-Хеллмана в ряде случаев дает существенное преимущество. Самым большим из таких преимуществ является то, что ключи могут иметь существенно меньшую длину (по причине сложности задачи). И это без потери стойкости! Как результат, вычисления производятся быстрее с сохранением того же уровня безопасности. Так, безопасность, обеспечиваемая 160-битным ключом ECC, может быть приравнена к 1024-битному ключу RSA.

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

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

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

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

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

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

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

2.2. Электронная цифровая подпись

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

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

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

Основные термины, применяемые при работе с ЭЦП

Закрытый ключ – это некоторая информация длиной 256 бит, которая хранится в недоступном другим лицам месте на дискете, смарт-карте, touch memory. Работает закрытый ключ только в паре с открытым ключом.

Открытый (public) ключ используется для проверки ЭЦП получаемых документов-файлов; технически это некоторая информация длиной 1024 бита. Открытый ключ работает только в паре с закрытым ключом.

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

Средства электронно-цифровой подписи – аппаратные и/или программные средства, обеспечивающие:

¦ создание электронной цифровой подписи в электронном документе с использованием закрытого ключа электронной цифровой подписи;

¦ подтверждение с использованием открытого ключа электронной цифровой подписи подлинности ЭЦП в электронном документе;

¦ создание закрытых и открытых ключей электронных цифровых подписей.

ЭЦП – это просто

Начнем с того, что ЭЦП – это вовсе не «зверь», и никаких специальных знаний, навыков и умений для ее использования не потребуется.

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

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

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

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

¦ имя файла открытого ключа подписи;

¦ информация о лице, сформировавшем подпись;

¦ дата формирования подписи.

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

Управление ключами

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

Задача защиты ключей от подмены решается с помощью сертификатов. Сертификат позволяет удостоверить заключенные в нем данные о владельце и его открытый ключ подписью какого-либо доверенного лица. В централизованных системах сертификатов (например, PKI – Public Key Infrastructure) используются центры сертификации, поддерживаемые доверенными организациями. В децентрализованных системах (например, PGP – Pretty Good Privacy) путем перекрестного подписания сертификатов знакомых и доверенных людей каждым пользователем строится сеть доверия.

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

ЭЦП под микроскопом

Рассмотрим принцип работы ЭЦП подробнее. Схема электронной подписи обычно включает в себя следующие составляющие:

¦ алгоритм генерации ключевых пар пользователя;

¦ функцию вычисления подписи;

¦ функцию проверки подписи.

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

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

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

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

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

Продолжим. Алгоритмы ЭЦП делятся на два больших класса:

¦ обычные цифровые подписи;

¦ цифровые подписи с восстановлением документа.

Обычные цифровые подписи необходимо пристыковывать к подписываемому документу. К этому классу относятся, например, алгоритмы, основанные на эллиптических кривых (ECDSA, ГОСТ Р34.10-2001, ДСТУ 4145-2002). Цифровые подписи с восстановлением документа содержат в себе подписываемый документ: в процессе проверки подписи автоматически вычисляется и тело документа. К этому классу относится один из самых популярных алгоритмов – RSA, который мы рассмотрим в конце раздела.

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

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

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

¦ Защита от изменений документа. При любом случайном или преднамеренном изменении документа (или подписи) изменится хэш, и, следовательно, подпись станет недействительной.

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

¦ подделать подпись для выбранного им документа;

¦ подобрать документ к данной подписи, чтобы подпись к нему подходила;

¦ подделать подпись для хоть какого-нибудь документа;

¦ подменить открытый ключ (см. подразд. "Управление ключами" разд. 2.2) на свой собственный, выдавая себя за владельца;

¦ обманом заставить владельца подписать какой-либо документ, например, используя протокол слепой подписи;

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

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

RSA как фундамент ЭЦП

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

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

Распространение системы RSA дошло до такой степени, что ее учитывают при создании новых стандартов. Первым при разработке стандартов цифровых подписей в 1997 году был разработан стандарт ANSI X9.30, поддерживающий Digital Signature Standard (стандарт цифровой подписи). Годом позже был введен ANSI X9.31, в котором сделан акцент на цифровые подписи RSA, что отвечает фактически сложившейся ситуации, в частности для финансовых учреждений.

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

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

Алгоритм RSA предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им. Как было уже сказано выше, в этом алгоритме используется два ключа – открытый и секретный. Данный алгоритм привлекателен также в случае, когда большое количество субъектов (N) должно общаться по схеме "все-со-всеми". В случае симметричной схемы шифрования каждый из субъектов каким-то образом должен доставить свои ключи всем остальным участникам обмена, при этом суммарное количество используемых ключей будет достаточно велико при большом значении N. Применение асимметричного алгоритма требует лишь рассылки открытых ключей всеми участниками, суммарное количество ключей равно N.

Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M) , и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n = pq и число d, c (d, p – 1) = (d, q – 1) = 1 (один из возможных способов выполнить это условие – выбрать d больше, чем p/2 и q/2). Шифрование производится по формуле: f(M) = Md х mod n, где M и f(M) оба < n – 1 . Оно может быть вычислено за разумное время, даже если M, d и n содержат весьма большое количество знаков. Адресат вычисляет M на основе M d , используя свое знание p и q. Если dc ? (p _ 1) 1, тогда (M d) e ? p 1.

Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M)) e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.

Аналогично (M d) e ? q M, если dc ? (q _ 1) 1. е удовлетворяет этим двум условиям, если cd ? (p _ 1)(q _ 1) 1. Мы можем позволить е = x, когда x является решением уравнения dx + (p – 1)(q – 1)y = 1.

Так как (M d) e – M делимо на p и q, оно делимо и на pq. Следовательно, мы можем определить M, зная Md, вычислив его значение в степени е и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, нельзя было вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором приблизительно 1050 комбинаций. Данная проблема изучается уже около 100 лет.

Теоретически можно предположить, что возможно выполнение операции f-l без вычисления p и q. Но в любом случае задача эта непроста, и разработчики считают ее трудно факторизуемой.

Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M и хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно – надо знать все возможные значения Mi.

Проясним использование алгоритма RSA на конкретном примере. Выберем два простых числа p = 7; q = l7 (на практике эти числа во много раз длиннее). В этом случае n = pq будет равно ll9. Теперь необходимо выбрать е. Выберем е = 5. Следующий шаг связан с формированием числа d, так чтобы de = 1 х mod [(p – 1)(q – 1)]. d = 77 (использован расширенный алгоритм Евклида). d – секретный ключ, а е и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать, представляется M = 19. С = Me х mod n. Получаем зашифрованный текст C = 66. Этот "текст" может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М = Cd х mod n и C = 66. В результате получается M = 19.

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

Возможно ли взломать ЭЦП?

Взлом ЭЦП фактически сводится к взлому алгоритма шифрования. В данном случае возможные варианты взлома мы рассмотрим на примере алгоритма RSA.

Существует несколько способов взлома RSA. Наиболее эффективная атака – найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом, и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель) нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n. Безопасность RSA зависит от разложения на сомножители (факторинга), что является трудной задачей, не имеющей эффективных способов решения.

Фактически, задача восстановления секретного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот: можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = Me х mod n, то корнем степени e из mod n является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделать подписи, даже не зная секретный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

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

Самое простое нападение на отдельное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст (например, "Штирлиц – Плей-шнеру"). Затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака на единственное сообщение применяется в том случае, если отправитель посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение M.

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

2.3. Современные технологии аутентификации. Смарт-карты

Смарт-карты, подобно Memory-картам, представляют собой пластиковые карты со встроенной микросхемой (ICC, integrated circuit card – карта с интегрированными электронными схемами). Однако смарт-карты представляют собой более сложное устройство, содержащее микропроцессор и операционную систему, контролирующую устройство и доступ к объектам в его памяти. Кроме того, смарт-карты, как правило, обладают возможностью проводить криптографические вычисления.

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

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

Смарт-карты находят все более широкое применение в различных областях – от систем накопительных скидок до кредитных и дебетовых карт, студенческих билетов и телефонов стандарта GSM.

В зависимости от встроенной микросхемы все смарт-карты делятся на несколько основных типов, кардинально различающихся по выполняемым функциям:

¦ карты памяти;

¦ микропроцессорные карты;

¦ карты с криптографической логикой.

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

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

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

Считыватели для смарт-карт

Несмотря на название – устройство для чтения смарт-карт, – большинство оконечных устройств, или устройств сопряжения (IFD, InterFace Device), способны как считывать, так и записывать, если позволяют возможности смарт-карты и права доступа. Устройства для чтения смарт-карт могут подключаться к компьютеру посредством последовательного порта, слота PCMCIA, последовательной шины USB. По методу считывания информации карты делятся на следующие:

¦ контактные;

¦ бесконтактные;

¦ со сдвоенным интерфейсом.

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

¦ контактная область:

Шесть или восемь контактов квадратной или овальной формы;

Позиции контактов выполнены в соответствии со стандартом ISO-7816;

¦ чип (микропроцессор карты);

¦ пластиковая основа.

Устройства чтения смарт-карт могут быть интегрированы в клавиатуру.

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

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

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

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

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

Генерирование ключа с помощью устройства

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

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

¦ Стандарт ISO-7816 "Идентификационные карты – карты с микросхемой с контактами". Состоит из шести частей, регламентирующих физические характеристики, размер и расположение контактов, сигналы и протоколы, структуру файлов, адресацию и команды обмена.

¦ Стандарт EMV (Europay, MasterCard & Visa). Первая и вторая части базируются на ISO-7816, в последующих частях добавлены определения обработки транзакций, спецификации терминалов и т. д.

«Страшная анатомия» смарт – возможен ли взлом?

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

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

А можно ли взломать смарт-карту, и если да, то как это сделать?

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

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

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

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

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

Технологии индуцированных сбоев подразумевают создание внештатных условий работы чипа, чтобы открыть потенциальные каналы доступа к защищенной информации. Например, в конце сентября 1996 года научный коллектив из Bellcore (научно-исследовательский центр американской компании Bell) сообщил о том, что обнаружена серьезная потенциальная слабость общего характера в защищенных криптографических устройствах, в частности в смарт-картах для электронных платежей (D. Boneh, R.A. DeMillo, R.J. Lipton «On the Importance of Checking Cryptographic Protocols for Faults»; www.demiLLo.com/PDF/smart.pdf). Авторы назвали свой метод вскрытия «криптоанализом при сбоях оборудования» (Cryptanalysis in the Presence of Hardware Faults). Суть же метода заключается в том, что искусственно вызванная с помощью ионизации или микроволнового облучения ошибка в работе электронной схемы позволяет сравнить сбойные значения на выходе устройства с заведомо правильными значениями, тем самым восстанавливая криптографическую информацию, хранящуюся в смарт-карте.

Простые оптические приборы.

Лупа

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

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

где h - размер предмета. При рассматривании этого же предмета невооруженным глазом его следует расположить на расстоянии наилучшего зрения нормального глаза. Предмет будет виден под углом

Отсюда следует, что угловое увеличение лупы равно

Линза с фокусным расстоянием 10 см дает увеличение в 2,5 раза.

Рис 3. 1 Действие лупы: а - предмет рассматривается невооруженным глазом с расстояния наилучшего зрения ; б - предмет рассматривается через лупу с фокусным расстоянием F.

Угловое увеличение

Глаз находится очень близко к линзе, поэтому за угол зрения можно принять угол 2β, образованный лучами, идущими от краев предмета через оптический центр линзы. Если бы лупы не было, нам пришлось бы поставить предмет на расстоянии наилучшего зрения (25 см) от глаза и угол зрения был бы равен 2γ. Рассматривая прямоугольные треугольники с катетами 25 см и F см и обозначая половину предмета Z, можем написать:

(3.4)

2β - угол зрения, при наблюдении через лупу;

2γ - угол зрения, при наблюдении невооруженным глазом;

F - расстояние от предмета до лупы;

Z - половина длины рассматриваемого предмета.

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

Следовательно, увеличение лупы пропорционально , то есть её оптической силе.

3.2 Микроскоп.

Микроскоп применяют для получения больших увеличений при наблюдении мелких предметов. Увеличенное изображение предмета в микроскопе получается с помощью оптической системы, состоящей из двух короткофокусных линз - объектива O1 и окуляра O2 (рис. 3.2). Объектив даст действительное перевернутое увеличенное изображение предмета. Это промежуточное изображение рассматривается глазом через окуляр, действие которого аналогично действию лупы. Окуляр располагают так, чтобы промежуточное изображение находилось в его фокальной плоскости; в этом случае лучи от каждой точки предмета распространяются после окуляра параллельным пучком.

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

Как следует из рис. 3.2, угол зрения φ предмета, рассматриваемого через окуляр в приближении малых углов

Приближенно можно положить d ≈ F1 и f ≈ l, где l - расстояние между объективом и окуляром микроскопа («длина тубуса»). При рассматривании того же предмета невооруженным глазом

В результате формула для углового увеличения γ микроскопа приобретает вид

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

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

Телескоп

Телескопы (зрительные трубы) предназначены для наблюдения удаленных объектов. Они состоят из двух линз - обращенной к предмету собирающей линзы с большим фокусным расстоянием (объектив) и линзы с малым фокусным расстоянием (окуляр), обращенной к наблюдателю. Зрительные трубы бывают двух типов:

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

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

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

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

Угловому увеличению γ, как и линейному увеличению Γ, можно приписать знаки плюс или минус в зависимости от того, является изображение прямым или перевернутым. Угловое увеличение астрономической трубы Кеплера отрицательно, а земной трубы Галилея положительно.

Угловое увеличение зрительных труб выражается через фокусные расстояния:

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

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

Разберем схему и принцип работы некоторых широко распространенных оптических приборов.

Фотоаппарат

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

Рис 3. 4

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

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

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

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

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

Глаз

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

Зрение двумя глазами позволяет видеть предмет с разных сторон, т. е. осуществлять объемное зрение. Экспериментально доказано, сто при видении одним глазом картина с 10 м кажется плоской (при базе - расстояние между крайними точками зрачка, - равной диаметру зрачка). Глядя двумя глазами, мы видим плоской картину с 500 м (база - расстояние между оптическими центрами хрусталиков), т. е. можем на глаз определить размеры предметов, какой и на сколько ближе или дальше.

Для увеличения этой способности надо увеличить базу, это осуществляется в призматическом бинокле и в разного рода дальномерах (рис. 3.5).

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

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