Криптография - статьи

         

Литература


1.

Шеннон К., Теория связи в секретных системах, в кн.: Шеннон К. Э., Работы по теории информации и кибернетике, М.: ИЛ, 1963.

2.

Защита информации. ТИИЭР, Т.78,

 5, 1988.

3.

Menezes A. J., van Oorshot P. S., Vanstone, Handbook of applied cryptography. CRC Press. 1997.

4.

Чмора А., Современная прикладная криптография, Гелиос АРБ, 2001.

5.

Koblitz N., Algebraic Aspects of Cryptography, Springer, 1997.

6.

Beker H., Piper F., Cipher System, Northwood Books, 1982.

7.

Cryptology and computational number theory, Proc. of Symp. in Appl. Math., v. 42, 1990.

8.

Luby M., Pseudorandmness and cryptographic applications, N.Y., Princeton Univ. Press, 1996.

9.

Сидельников В. М., Открытое шифрование на основе двоичных кодов Рида -- Маллера, Дискретная математика, 1994, т. 6, № 2, 3-20.

10.

Сидельников В. М., Шестаков С. О., О безопасности системы шифрования, построенной на основе обобщенных кодов Рида -- Соломона, Дискретная математика, 1994, т. 4, № 3.

11.

Сидельников В. М., Черепнев М. А., Ященко В. В., Системы открытого распределения ключей на основе некоммутативных полугрупп, Доклады РАН, 1993, т. 332, № 5.



О современной криптографии


В. М. Сидельников, д. ф.-м. н., профессор, академик Академии криптографии РФ,

зав. лабораторией МГУ по математическим проблемам криптографии

Опубликовано на сайте

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

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

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

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

Мы далее рассматриваем только математические преобразования информации, представленной в дискретном виде, т. е. в виде последовательности w элементов конечного алфавита A.

Известны два вида шифрования -- традиционное (оно же симметрическое) и "открытое шифрование" (асимметрическое). При традиционном шифровании законный пользователь X с помощью некоторого конечного автомата AK


(шифратора) преобразует последовательность

w=(w1,...wn), называемую открытой информацией, в шифрованную информацию
. Шифратор AK (ключа), известного пользователю  X. Законные пользователи, которым предназначена информации w, осуществляют расшифрование информации также с помощью некоторого конечного автомата, зависящего от параметра K`, связанного с K. Обычно K`=K. В рассматриваемом случае каждый законный пользователь изначально обладает как преобразованием
, так и преобразованием

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

В традиционном варианте шифрования законные пользователи X

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

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

Второй вид шифрования (возникший в 70-х годах XX столетия), для которого нет необходимости в дополнительном секретном канале распределения ключей, носит название "открытого шифрования". При открытом шифровании каждый абонент X сети связи строит (или доверяет кому-либо построить) "одностороннюю" функцию
, которая, так же как и в первом случае, определяется некоторым секретным параметром K, известным только абоненту X. Функция
строится таким образом, чтобы ее значения

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



при известном секретном параметре K также вычислялась достаточно "просто", т. е. абонент X

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

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

Абонент Y, желающий передать открытую информацию w

абоненту X, вычисляет шифрованную информацию

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

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

осуществляет "открытое шифрование", а саму функцию называют односторонней или однонаправленной (one-way function), хотя строгое определение "односторонней функции", известное в абстрактной теории сложности вычислений, отличается от приведенного. Примеры функций FX, используемых на практике, см. ниже.

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



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

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

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

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

в тех или иных условиях. Обычно усилия направляются на вычисление ключа K. Вместе с тем в некоторых случаях можно определить w без определения ключа (бесключевое чтение). Далее под взламыванием будем понимать только задачу определения ключа.

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



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

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

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

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

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

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

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

Блочный шифратор
представляет собой автомат, входами и выходами которого являются последовательности w и
длины n. Входная последовательность разбивается на блоки длины n и каждый блок шифруется независимо один от другого на одном ключе K. Блочный шифратор реализует перестановку элементов пространства An, где A -- используемый алфавит. Самым известными блочными шифраторами являются американский шифратор DES (data encryption standard) и отечественный стандарт ГОСТ 28147-89  , у которых длина блока n

равна 64 и 256 соответственно. Имеются и другие типы шифраторов, существенно отличные от рассмотренных.

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



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

Ввиду того, что задача определения ключа может быть представлена как задача решения некоторой системы нелинейных уравнений в конечном поле, для криптографии представляют значительный интерес методы решения систем того или иного вида и оценки их сложности. С примерами криптографических исследований можно познакомиться по многочисленным работам, связанным с изучением свойств преобразования DES, которые опубликованы в последние 20 лет в Procedings of Crypto, Procedings of Eurocrypt, Journal of Cryptology.

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

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

За последние годы получил значительное развитие раздел теоретической криптографии, занимающийся изучением вопросов существования тех или иных криптографических объектов с доказуемыми (при некоторых дополнительных предположениях) оценками стойкости. В круг интересов этого раздела криптографии входят вопросы построения и обоснования свойств таких криптографических понятий как "односторонняя функция", псевдослучайный генератор, криптографический протокол (cryptographic protocol), в частности, протокол доказательства с нулевым разглашением (zero-knowledge proof protocol) и т. п. Эти понятия изучаются с точки зрения абстрактных позиций сложности вычислений.



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

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

Пусть необходимо передать элемент
из конечного множества A. В качестве
часто выступает значение хэш-функции. Будем предполагать, что на обоих концах канала связи имеется секретный элемент b (ключ) из множества B. Пусть функция
инъективна при каждом фиксированном y и обладает тем свойством, что для каждых
и c множество
решений уравнения

имеет достаточно много элементов.

В рассматриваемой системе имитозащиты по общедоступному каналу связи вместо элемента
из A передается элемент

. Законный пользователь знает ключ b, поэтому он, получив элемент c, решает уравнение
и определяет элемент 
.

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

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




вида
, где Fq -- конечное поле с q

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

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

Наиболее известной на настоящий момент, используемой на практике и достаточно стойкой (2001 г.) является система RSA (сокращение от фамилий авторов - Rivest, Shamir, Adleman). В этой системе законный пользователь X для построения однонаправленной функции F=FX выбирает число n=nX, являющееся произведением двух достаточно больших простых чисел p и q, и целое число z=zX такое, что

, где (r,m) -- наибольший общий делитель чисел r и m,
-- функция Эйлера (количество натуральных чисел, не превосходящих n и взаимно простых с n, или порядок мультипликативной группы
вычетов по modn взаимно простых с n). Открытая информация, представленная целым числом w,
, шифруется с помощью общеизвестной функции

, действующей на
. Числа n="nX" и zX всех абонентов сети засекреченной связи обычно помещают в общедоступный справочник. Таким образом, любой абонент может послать секретное сообщение абоненту X.



Секретная информация (ключ) законного пользователя X

состоит из чисел p и q, на которые разлагается число n. Знание p и q позволяет вычислить значение функции Эйлера

, а затем с помощью алгоритма Евклида -- число z`, для которого
. Очевидно, обратное преобразование
имеет вид



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



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

. В общем случае сложность решения задачи разложения является достаточно большой. В течение нескольких последних десятилетий математиками было найдены несколько нетривиальных алгоритмов разложения целых чисел на множители. В частности, удалось разложить 155-разрядное девятое число Ферма
на три простых множителя. Множители имеют примерно одинаковое число разрядов. Считается, что система RSA имеет достаточную стойкость, если n имеет более 512 двоичных разрядов.



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

-- линейный код над
с параметрами (n,k,b), который имеет простое декодирование, и M -- его порождающая
-матрица. Пусть H -- невырожденная
-матрица и
-- перестановочная
-матрица.



Открытой информацией является k-мерный вектор

, шифрованной -- n-мерный вектор

(функция
), где
-- случайный вектор веса

. Секретный ключ образуют матрицы H и
, а общедоступным ключом является матрица
. Случайный элемент
генерирует отправитель. Матрицы H и
"маскируют" матрицу M.

Получив
, абонент X вычисляет следующие элементы:

, декодирует
, т. е. представляет его в виде
,

,
, где

, и, наконец, с помощью последнего соотношения находит w.



Проделать последнюю цепочку вычислений злоумышленнику трудно из-за того, что он не знает

. Поэтому ему трудно декодировать код
с порождающей матрицей M`, который для него является кодом "общего положения". Известно, что сложность N декодирования таких кодов имеет вид
, т. е. при относительно небольших k и n-k является неприемлемо большой.



Если в качестве

взять код Боуза -- Чоудхури -- Хоквингема или код Рида -- Маллера, то при подходящем k и n мы получим стойкую систему открытого шифрования. Если же в качестве
взять код Рида -- Соломона, то получим слабую систему. Кодовые системы имеют алгоритм зашифрования информации существенно более быстрый, чем системы RSA.





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



Для примера рассмотрим один популярный метод построения открытого ключа в сети абонентов Xj,

, предложенный Диффи и Хеллманом. Пусть
-- конечное поле с достаточно большим числом элементов q и
-- первообразный элемент мультипликативной группы G этого поля. Каждый из абонентов Xj и Xi один независимо от другого выбирают по секретному числу xj,xi,
,


поля, например, помещают их в общедоступный справочник. Для образования секретной связи между Xj и Xi первый абонент вычисляет элемент
, а второй --
. Таким образом, у каждого из абонентов образуется один и тот же элемент
поля
, который и является "открытым ключом".



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

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



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

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





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





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

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



На основе идей "открытого шифрования" в криптографии появились методы преобразования информации, открывающие новые возможности для ее использования в деловом мире. К таким методам следует отнести алгоритмы по созданию цифровой подписи, системы идентификации, пароли, системы распределения ключей и многие другие (см., например, и статьи в Proceding of Crypto, Proceding of Eurocrypt, Journal of Cryptolodgy и др.).



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

сообщения w

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

при известном w элемент g может быть относительно просто вычислен X, но не может быть вычислен злоумышленником без привлечения очень значительных и потому недоступных ему вычислительных ресурсов (подпись не может быть подделана),



существует простой алгоритм проверки соответствия

(от подписи не может отказаться абонент X).



В общем случае в качестве цифровой подписи сообщения w можно использовать элемент

, где
- односторонняя функция.



В качестве примера иного способа построения функции

, который нашел достаточно широкое практическое применение, рассмотрим цифровую подпись Эль Гамаля. Используем обозначения, введенные при описании примера построения открытого ключа. Поле
считаем простым, т. е. p -- простое число.



Пользователь X вырабатывает секретное число x,

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

пользователь X выбирает случайно из интервала (1,p-1). Число m определяется числами r и w с помощью соотношения
.





Отметим, что, во-первых, пользователь X может достаточно просто вычислить m при известных числах

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

>


Дополнительная информация


1.Разработка CSP для Windows
2.Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms
3.Много интересной информации об архитектуре CSP можно найти тут



Функции конвертирования ключей


Архитектура круговорота открытых ключей для "нестандартных" алгоритмов в Windows представлена на .

Функция A_ConvertPublicKeyInfo - на входе принимает ключ в формате ASN.1 DER и должна преобразовать его в формат, который "понимает" функция CSP CPImportKey

Функция A_EncodePublicKeyInfoAndParameters на входе принимает ключ в том формате,

в котором ключ экспортирует CPExportKey. На выходе A_EncodePublicKeyInfoAndParameters должна сформировать ASN.1 DER структуру с ключом - ту же самую, которая в случае импорта передается в A_ConvertPublicKeyInfo - на вход. Надеюсь, вы не запутались во всех этих входах и выходах.

Вот сигнатуры и краткие описания параметров этих функций:

BOOL WINAPI A_ConvertPublicKeyInfo( DWORD dwCertEncodingType, // IN - VOID *EncodedKeyInfo, // IN - буфер с ключом - указатель // на структуру CERT_PUBLIC_KEY_INFO

DWORD dwAlg, // IN - AlgId ключа

DWORD dwFlags, // IN - обычно 0

BYTE **ppStructInfo, // OUT - двойной указатель на структуру // в заголовке структуры идет сначала PUBLICKEYSTRUC, затем DSSPUBKEY, // а затем сам ключ с параметрами DWORD *StructLen // OUT - длина структуры

);

BOOL WINAPI A_EncodePublicKeyAndParameters( DWORD dwCertEncodingType, // IN

LPCSTR lpszStructType, // IN - OID алгоритма

const void* pvStructInfo, // IN - такая же структура как // на выходе ConvertPublicKeyInfo

DWORD nStructLen, // IN - длина входной структуры

DWORD dwFlags, // IN - обычно 0

DWORD Unk, // ? - неизвестно

BYTE **pbPubKey, // OUT - открытый ключ в ASN.1 DER

DWORD* pcPubKeyLen, // OUT - длина открытого ключа BYTE **pbParams, // OUT - параметры открытого ключа

DWORD* pcParamsLen // OUT - длина параметров

);

Форматы ключей зависят от криптопровайдера и используемых алгоритмов.



Функция I_CryptGetDefaultCryptProvider из crypt32.dll


По непонятной для меня причине Windows часто не пытается искать нужный криптопровайдер по идентификатору алгоритма, с которым требуется работать. В таких случаях она просто вызывает недокументированную функцию I_CryptGetDefaultCryptProvider, и если тот провайдер, который вернула эта функция, не умеет работать с данным алгоритмом, то процесс завершается с ошибкой. Так происходит, например, при разборе в Internet Explorer PKCS#7 ответа в сценарии с запросом сертификата на тестовом УЦ.

HCRYPTPROV WINAPI I_CryptGetDefaultCryptProv(ALG_ID algid);

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

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



Интеграция провайдера в Windows


Помимо наличия библиотеки самого провайдера, дополнительно требуется:

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

Только после выполнения этих действий провайдер нормально интегрируется в систему и вы сможете, например, генерировать сертификаты при помощи вашего провайдера на основе стандартного компонента ОС Windows Server - Сertification services или на тестовом УЦ КриптоПро.

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

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



Привязка закрытого ключа к сертификату


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

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

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

PCCERT_CONTEXT pCert; CRYPT_KEY_PROV_INFO prov_info; … prov_info.cProvParam = 0; prov_info.rgProvParam = 0; prov_info.dwFlags = 0; prov_info.dwKeySpec = AT_SIGNATURE; prov_info.dwProvType = 0; prov_info.pwszContainerName = L"key-kont-name"; prov_info.pwszProvName = L"A-CSP";

CertSetCertificateContextProperty( pCert, CERT_KEY_PROV_INFO_PROP_ID, 0, &prov_info );

Успехов в разработке криптопровайдера!



Регистрация криптопровайдера и алгоритмов в системе


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

Процесс регистрации самого CSP подробно описан в MDSN, и повторять эту информацию здесь смысла нет. Все это подробно описано в []. Также здесь мы не будем останавливаться на проблеме подписи нового CSP в Microsoft и путях ее обхода. Эта проблема уже многократно обсуждалась на различных форумах, например смотрите []. Гораздо интереснее рассмотреть регистрацию криптографических алгоритмов. Каждый алгоритм имеет свой уникальный ASN.1 идентификатор Оbject Identifier - OID. Например, алгоритм подписи ГОСТ-34.10-2001 имеет такой OID (представленный в виде строки) - "1.2.643.2.2.3". Идентификатор каждого поддерживаемого вашим CSP алгоритма следует занести в реестр. Помимо OID у каждого криптоалгоритма в Windows существует еще идентификатор в виде четырехбайтового числа - AlgID, по которому алгоритмы идентифицируются в провайдере. Этот идентификатор заносится в CSP и его можно узнать, перечислив алгоритмы посредством вызова CPGetProvParam. В КриптоПро, например, для алгоритма хеширования ГОСТ-34.11-94 AlgID используется значение 0x801e.

Пусть нам необходимо зарегистрировать алгоритм подписи ГОСТ-34.10-2001. Тогда в реестре необходимо прописать следующие идентификаторы:

"1.2.643.2.2. 9!1" - Хэш ГОСТ-34.11-94 "1.2.643.2.2.19!3" - Ключ подписи ГОСТ-34.10-2001 "1.2.643.2.2.3!4" - Подпись ГОСТ-34.10-2001 - Алгоритм Хэша + Алгоритм Ключа

Далее приведен пример кода регистрации OID алгоритма ГОСТ-34.11-94 // Регистрация GOST-3411-94 HASH OID //

CRYPT_OID_INFO oidInfo; int rc = 0;

memset(&oidInfo, 0, sizeof(CRYPT_OID_INFO)); oidInfo.cbSize = sizeof(CRYPT_OID_INFO);

oidInfo.pszOID="1.2.643.2.2.9"; oidInfo.pwszName= L"GOST-3411-94 HASH"; oidInfo.dwGroupId = CRYPT_HASH_ALG_OID_GROUP_ID; oidInfo.Algid = 0x801e; oidInfo.ExtraInfo.cbData=0; oidInfo.ExtraInfo.pbData=0;


rc = CryptRegisterOIDInfo( &oidInfo, 0 ); if(rc) printf("\nHash algorithm registered"); else printf("\nError registering hash algorithm");

Аналогично регистрируются и остальные алгоритмы. Подробную информацию о структуре CRYPT_OID_INFO можно найти в MSDN.

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

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

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

#define YOUR_PROV_NAME "MY_PROV"

#define YOUR_PROV_TYPE 75

rc = CryptSetProvider( YOUR_PROV_NAME, YOUR_PROV_TYPE );


Сценарии применения нашего CSP


Рассмотрим здесь два сценария применения CSP.

Первый сценарий - проверка подписи сертификата. Для проверки подписи система загружает открытый ключ из сертификата, которым подписан проверяемый. Затем по OID алгоритма подписи проверяемого сертификата, так как описано в предыдущем разделе статьи, определяется требуемый провайдер. Чтобы проверить подпись, нужно импортировать открытый ключ в CSP и можно было бы подумать, что Windows сразу вызывает функцию нашего провайдера CPImportKey. Но не тут-то было!

Второй сценарий - генерация ключевой пары и отправка запроса на сертификат на Удостоверяющий Центр. Windows загружает наш CSP, генерирует ключевую пару и экспортирует к себе наверх открытый ключ, вызывая функцию CPExportKey. Все хорошо. Вроде бы надо взять и поместить полученный буфер с ключом в PKCS#10 запрос, который затем будет отправлен на УЦ. И тут все опять не совсем так.

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



Эта статья для тех, кто


Эта статья для тех, кто по тем или иным причинам решил написать собственный криптопровайдер для OC семейства Windows. Если Вы хотите реализовать в вашем провайдере нестандартные алгоритмы, то вам предстоит столкнуться с определенными трудностями. Трудности могут возникнуть, например, при попытках использования вашего криптопровайдера для проверки сертификатов в MS Internet Explorer.
Под нестандартными алгоритмами здесь понимаются не всемирные DES, RSA, DSA и т.д., а, например, алгоритмы семейства ГОСТ. Дело в том, что для RSA и подобных алгоритмов все необходимые идентификаторы уже зашиты в систему, а для ГОСТ-ов (или многих других алгоритмов) надо отдельно позаботиться о том, чтобы система их "увидела".
Для примеров кода используется Си. Все примеры кода служат только для иллюстрации принципов, изложенных в статье и не являются полноценными рабочими программами.
Также подразумевается, что у читателя есть базовые знания в области прикладной криптографии и термины "открытый ключ", "ASN.1" и подобные для него не являются загадкой.

Криптография - статьи





Криптография - статьи


Александр Лозовюк

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

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

Основные функции GnuPG таковы:

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

Конечно, используются только открытые и свободные системы шифрования, например, алгоритм IDEA не поддерживается ввиду того, что срок действия патента на него еще не истек (он действителен до 2007 года, но реализации алгоритма доступны уже сейчас, например: ftp://ftp.gnupg.dk/pub/contrib-dk/.

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

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

Основной особенностью является система ключей. В GnuPG вы создаете себе несколько ключей, причем каждый служит для отдельного действия (и использует разные алгоритмы). Один из ключей, создаваемые первым, является главным ключом, остальные подчиненными, подключами. Например, главный ключ используется только для подписи самых важных документов, имеет длину 1024 бит, алгоритм DSA, срок действия ключа не ограничен. Для шифрования документов вы создаете еще один или несколько подключей (например, для деловой и личной переписки), которые могут использоваться только для шифрования (алгоритмы ElGamal или RSA). Для этих ключей можно назначить срок использования, например, год или два.

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

Описанная иерархия ключей изображена на рис.


К этой схеме надо дать пояснение. Изначально, при генерации набора ключей, создается пара из двух ключей: главного (алгоритм DSA, 1024 бит) который используется для подписи, и подключа для шифрования документа (ElGamal). Для ключей ElGamal длина может быть до 4096 бит, для остальных – по умолчанию 1024, а максимум 2048 бит.

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

Сперва надо выбрать типы ключей (DSA или RSA), потом задать их длину и срок действия. Если выбирается генерация ключа с установками по умолчанию, то главный ключ DSA будет иметь длину 1024 бит, а для подчиненного ключа ElGamal длину можно выбрать произвольно. Далее в диалоговом режиме укажите свое имя и адрес email, а также пароль для защиты вашего закрытого ключа. В результате в списке ключей (программа ведет свою собственную базу ключей, куда заносятся открытые ключи ваших респондентов) появится новый ключ. GnuPG также поддерживает связь с открытыми серверами, на которых размещаются базы данных открытых ключей, ваш ключ можно туда экспортировать командой --send-keys.

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

И так, вернемся назад к возможностям программы. Для работы с документами доступны несколько команд:

подписать документ; зашифровать документ; подписать и зашифровать документ;

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

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

Кроме прозрачной подписи, GnuPG может создавать еще и отделённые подписи командой --detach-sign. Такая подпись сохраняется в отдельном файле с расширением *.asc и должна распространятся вместе с подписываемым документом. При проверке такой подписи необходимо указать полный путь к файлу подписи. При этом сам документ может быть как зашифрованным, так и полностью открытым.

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

Кратко опишем основные команды GnuPG, которые могут понадобиться для повседневной работы. Весь список команд есть в справке и доступен при помощи команды gpg --help:




--gen-key – создание новой пары ключей. Команда –edit-key позволяет в последствии изменить параметры ключа. --sign – создает подпись для указанных файлов, используя ключ (если не введен его идентификатор, использует ключ по-умолчанию). --detach-sign создаст подпись в отдельном файле, иначе создается совмещенная подпись. --encrypt – указывает на то, что данные надо зашифровать. Если применяется совместно с –-sign то данные одновременно подписываются. --symmetric – можно применять когда просто надо зашифровать файл (используется симметричный алгоритм, но можно выбрать алгоритм командой --cipher-algo). --decrypt – расшифровывает указанные файлы и сохраняет результат в файл (если указан) или выводит в консоль. Если файлы содержат подпись, она также проверяется. --verify – проверяет подписи для указанных файлов, не выводя содержимого файла. --list-keys – выводит список всех открытых ключей. Команда --list-secret-keys показывает ваши секретные ключи. --delete-key – удаляет открытый ключ из списка. --delete-secret-key удаляет секретный ключ (например, он скомпрометирован или окончился срок действия) --export (--import) – экспорт/импорт ваших ключей, например, для резервирования или переноса на другой компьютер. По умолчанию ключи в бинарном виде, для получения их в ASCI-виде укажите параметр –armor.

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



Литература


1. D.Kahn. The Codebreakers, The Story of Secret Writing.-- New York: Screbner, 1996.

2. K.Э. Шеннон. Теория связи в секретных системах (В кн.: Шеннон К.Э. Работы по теории информации и кибернетике).- М.: ИЛ, 1963.- С. 333–402.

3. G.S.Vernam. Cipher printing telegraph systems for secret wire and radio telegraphic communications //J.Amer. Inst. Elec. Eng.-1926.- v. 55.- Р.109–115.

4. W.Diffie and M.E.Hellman. New directions in cryptography //IEEE Trans. Informat. Theory.- 1976.- Nov., v. IT-22.- P. 644–654.

5. A.G. Konheim. Cryptography: A Primer //John Willy & Sons.- New York, 1981.

6. E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standart.- New York: Springer-Verlag, 1993.

7. M. Matsui. Linear Criptanalysis Method for DES Cipher. Proseedings, EUROCRYPT’93; published by Springer-Verlag.

8.** W. Stallings. Cryptography and Network security. Principles and Practice. Second Edition. Upper Saddle River, NJ: Prentice Hall, 1999.

9. P. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems. - Lect. Notes Comput. Sci.- v. 1109.- Р. 104–113.

10. О.В. Вербіцький. Вступ до криптології.-Львів: Видавництво науково-технічної літератури, 1998.

11. A. Salomaa. Public - Key Cryptography.- New York: Springer-Verlag, 1996.

12.** J. Jaworski and P. Perrone. Java Security Handbook.- SAMS Publishing, 2000.

13. K. Nyberg. Differentially uniform mappings for cryptography. - Lect. Notes Comput. Sci.- v. 765.- Р. 55–64.

** Готовится перевод на русский язык в Издательском доме “Вильямс”. (www.williamspublishing.com)

document.write('');

Новости мира IT:

02.08 - 02.08 - 02.08 - 02.08 - 02.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 31.07 - 31.07 - 31.07 - 31.07 - 31.07 -

Архив новостей

Последние комментарии:

 (66)

2 Август, 17:53

 (19)

2 Август, 17:51

 (34)

2 Август, 15:40

 (42)

2 Август, 15:35

 (1)

2 Август, 14:54

 (3)



Математика криптологии


В. Масол, д.ф-м.н,

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

– Джентельмены не читают чужих писем,- заявил госсекретарь США Стимсон в 1929 г., узнав о том, что “черный кабинет” госдепартамента США занимался раскрытием шифрованных дипломатических телеграмм многих стран. Он немедленно упразднил упомянутый кабинет. Однако, являясь в 1940 г. военным министром, Стимсон заметно смягчился и простил раскрытие японских шифров (подробнее об этом и других исторических фактах см. В работе [1]).

Период до 1949 г. называют эпохой донаучной криптологии, поскольку достижения тех времен основаны в большей мере на интуиции и “вере”, не подкрепленных доказательствами. Последние впервые появились в публикации 1949 г. К. Шеннона [2]. Он доказал в ней, в частности, невозможность раскрытия случайного шифра Г. Вернама, введенного в работе [3], без знания секретного ключа.

В свою очередь, идеология криптографии с открытыми (несекретными) ключами впервые была изложена в 1976 г. У. Диффи и М. Хеллманом в работе [4]. В ней авторы показали, что секретная связь возможна без передачи секретного ключа между отправителем и получателем.

Благодаря ставшими уже классическими статьям [2 и 4], криптология состоялась как математическая наука.

К. Шеннон выделил в своей работе два общих принципа, используемых в практических шифрах: рассеивание и перемешивание. Достижение рассеивания и перемешивания осуществляется посредством реализации перестановок символов открытого текста, а также подстановок, заменяющих символы открытого текста на другие символы, из того же алфавита. Конкретный вид как перестановок, так и подстановок определяют секретные ключи. Один из примеров криптоалгоритма, разработанного в соответствии с указанными принципами К.Шеннона, является стандарт шифрования данных (DES), принятый в США в июле 1977 г. в качестве Федерального стандарта. В этом стандарте открытый текст Х, криптограмма Y и ключ Z -- двоичные последовательности длиной М = 64, N = 64 и K = 56 соответственно. Так как M = N, то DES является подстановкой в алфавите, содержащем 264 символов. Полное описание криптоалгоритма DES можно найти практически в любом учебнике по криптографии (например [5]), опубликованном после 1977 г.

С момента принятия Федерального стандарта DES и по сей день, он остается в центре внимания криптоаналитиков. Используемые при этом математические методы частично изложены в упоминавшейся ранее книге [5]. К ним А. Конхайм (автор книги [5]) относит методы теории вероятностей и математической статистики, линейной алгебры, теории групп и теории сложности. Более десяти лет стандарт DES оправдывал надежды его защитников. По состоянию на январь 1988 г. наиболее быстрый из известных вариантов криптоанализа этого стандарта предполагал выполнение 2K-1 процедур шифрования, т. е. практически предполагалось осуществление перебора всех вариантов. Первые сообщения о том, что теоретически возможно вскрыть стандарт DES за число операций, меньшее, чем 2K-1, появились в 1990 г., а соответствующие публикации в 1993 г. Так в работе [6] показано, что методом разностного криптоанализа перебор вариантов можно снизить до 247. Данный подход, как выяснилось со временем, был известен разработчикам стандарта DES. Однако противодействия этому методу, заложенные ими в криптосистему DES, при некоторых обстоятельствах, указанных авторами работы [6], удается обойти. Линейный криптографический анализ, предложенный в работе [7], основан на вероятностной оценке числа линейных соотношений между открытым текстом, шифртекстом и битами ключа, которые содержат информацию о ключе. Для успешной атаки на стандарт DES метод линейного криптоанализа требует 243 зашифрованных текстов (см. [7]).

Теоретические работы [6 и 7] послужили толчком к совершенствованию известных и созданию новых криптографических схем. Этот период в развитии криптографии нашел свое отображение в монографии [8], перевод которой на русский язык в настоящее время готовится в Издательском доме “Вильямс” (). В частности, в этой работе помещено детальное описание криптоалгоритма RC5, являющегося, по мнению специалистов, весьма удачным и таким, который после незначительных модификаций мог бы сменить стандарт DES.

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

В связи со сказанным более острым становится вопрос о том, что понимать под надежностью криптографического алгоритма. От чего в точности он защищает? Ответ на поставленный вопрос ищется, в частности, в рамках различных математических теорий. Принимая во внимание тот факт, что в большинстве случаев криптосистемы являются булевыми функциями, т. е. функциями, отображающими наборы из n битов в наборы из m битов, создатели указанных систем стремятся к тому, чтобы эти функции имели равномерно распределенный выход и тем самым “уничтожали” статистические закономерности открытого текста, обеспечивая, таким образом, криптосистеме надежность в теоретико-информационном смысле. В свою очередь, стандарт DES и возможные его приемники, к которым специалисты относят криптоалгоритмы RC6 (незначительная модификация упоминавшегося ранее RC5), MARS, Twofish, Serpent и Rijndael, считаются надежными в вычислительном смысле.

Различные толкования понятия надежности можно объяснить, обратившись к правилу для криптографов, сформулированному еще в XIX веке Керкхоффом (Kerckhoffs) в его книге “La Cryptographic militare”: криптоаналитику противника известен весь механизм шифрования, кроме значения секретного ключа. Для криптографа, придерживающегося этого правила, понятие надежности алгоритма становится, таким образом, динамически изменяющимся, зависящим от криптоаналитических возможностей противника в различные моменты времени.

Формирование понятия надежности, изобретение линейного криптоанализа в ответ на принятие стандарта DES -- все это может служить примерами проявления взаимосвязи двух составных частей криптологии. В свою очередь криптография с открытым ключом послужила толчком к раскрытию многих криптосистем. Чтобы объяснить это явление, обратимся снова к работе К. Шеннона [2]. В ней автор рекомендует конструировать такие шифры, чтобы раскрытие любого из них было эквивалентно решению задачи, о которой известно, что для ее решения требуется большой объем работы. Эта рекомендация помогла авторам работы [4] предложить криптографию, не использующую передачи секретного ключа. Их метод построен на применении односторонней функции и односторонней функции с потайным ходом. Определения и примеры этих функций, а также собственно алгоритм шифрования можно найти практически в каждом учебнике по криптографии, вышедшем после 1977 г., в частности [5, 8, 10, 11 и др. ]. Доказательство стойкости криптосистемы с открытым ключом могло бы состоять в обосновании того факта, что любой алгоритм раскрытия этой системы требует неприемлемо большого объема вычислений. Ни одна из систем с открытым ключом не удовлетворяет этому критерию стойкости. Хотя существуют такие криптосистемы, в отношении которых доказано, что их стойкость эквивалентна сложности решения задачи разложения целого числа n на простые множители. По мнению многих специалистов, указанная задача является крайне сложной для больших значений числа n. Вполне естественно, что поиски труднорешаемых математических задач могут привести к доказательству того, что задача, считавшаяся трудной и на этом основании использовавшаяся в криптоалгоритме, в действительности не является таковой и, следовательно, криптосистема, построенная на ней, вполне раскрываемая.

Ранее мы коснулись содержания учебников по криптографии, опубликованных после 1977 г. Для читателя, заинтересовавшегося данной тематикой, добавим к сказанному, что как учебники, так и справочные пособия по криптографии последних лет содержат, как правило, сведения о классическом шифровании с секретными ключами, о шифровании с открытыми ключами и о применениях криптографии. Различие между монографиями обусловлено различными научно-педагогическими интересами их авторов. Так, в работе [5] значительное место уделено математическим методам криптоанализа, в [11] - криптографии с открытыми ключами, в [8] - применениям криптографии (в частности, к безопасному общению в сети интернет), в [12] - программной реализации на языке Java алгоритмов криптографии с открытыми ключами и иллюстрациям их применения в задачах аутентификации информации, цифровой подписи и т. д.

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



Основы работы с OpenSSL


Автор: Vsevolod A. Stakhov/CEBKA
E-mail: VStakhov tehnopark org
Сайт:

OpenSSL — это система защиты и сертификации данных, название SSL переводится, как система безопасных сокетов (secure socket layer). OpenSSL используется практически всеми сетевыми серверами для защиты передаваемой информацией. Существует программное API SSL (SSLEAY), позволяющее создавать безопасные сокеты с шифрацией передаваемых данных в собственных разработках. Но в данной статье я бы хотел рассказать о самой системе OpenSSL, вызываемой через командную строку.

Т.к. OpenSSL поддерживает очень много различных стандартов сертификации, шифрования, хеширования, то использование данной команды достаточно сложно. Внутри OpenSSL существуют отдельные компоненты, отвечающие за то или иное действие, для получения списка доступных компонентов можно вызвать openssl с параметрами list-standart-commands. Можно также получить список доступных алгоритмов хеширования (list-message-digest-commands) и алгоритмов шифрования (list-cipher-commands).

OpenSSL может использоваться во множестве случаев и умеет выполнять следующие задачи:

Создавать и управлять ключами RSA и DSA — команды rsa, dsa, dsaparam. Создавать сертификаты формата x509, запросы на сертификацию, восстановление — команды x509, req, verify, ca, crl, pks12, pks7. Зашифровывать данные с помощью симметрического или асимметрического шифрования — команды enc, rsautl. Высчитывать хеши различных типов — команда dgst. Работа с S/MIME — команда s/mime. Проверка работы серверов и клиентов ssl — команды s_client, s_server.

Cуществует также несколько вспомогательных утилит ssl:

    — openssl speed [список_алгоритмов_хеширования_или шифрования]:

тестирование скорости различных алгоритмов, если запускать без параметров, то тестируются все алгоритмы; алгоритмы внутри списка разделяются пробелом, например: openssl speed md5 rsa idea blowfish des 3des sha1. В конце работы выводится общая скорость работы различных алгоритмов (в 1000-х байт в секунду), для обработки различной длины блоков. Вот результат работы тестов скорости на моем домашнем компьютере (Celeron 366), на других машинах значения будут другими:

Проверка алгоритмов асимметрического шифрования:

    — openssl rand [-out file] [-rand file] num:

генерация num рандомных байт, можно использовать для проверки рандомизационной последовательности rand:

# openssl rand -rand .rnd 5
Wеб~
#


    — openssl ciphers [-ssl2] [-ssl3] [-tls1] NAME: вывод доступных алгоритмов для обеспечения уровня безопасности NAME, где NAME — это символическое название группы алгоритмов. Обычно используются значения:

      LOW — алгоритмы низкого уровня безопасности (<128 бит);

      MEDIUM — алгоритмы среднего уровня стойкости (128 бит);

      HIGH — алгоритмы высокой стойкости (>128 бит);

      ALL — все алгоритмы;

      NULL — алгоритмы без шифрования.

Обычно в настоящее время используются алгоритмы групп MEDIUM и HIGH, которые еще долго не смогут быть взломаны прямым перебором. Можно также вывести список алгоритмов из нескольких групп, разделив их «:» (например, MEDIUM:HIGH).

Теперь я бы хотел рассказать об основных утилитах openssl. Для начала о методах генерации ключей, затем о командах шифрования, и, наконец, о сертификатах, s/mime. Итак, пару слов о генерации ключей. Для создания rsa-ключей используется команда genrsa: openssl genrsa [-out file] [-des | -des3 | -idea] [-rand file] [bits]

Команда genrsa создает секретный ключ длиной bits в формате PEM, шифрует его одним из алгоритмов: des (56 бит), des3 (3-й des 168 бит) или idea (128 бит). При выборе алгоритма шифрования будет запрошен пароль для шифрации создаваемого секретного ключа (если алгоритм не указан, то секретный ключ не шифруется, чего делать ни в коем случае нельзя для личных ключей, т.к. некоторые серверы требуют отсутствие шифрации для сектетного ключа сервера). Опция -out говорит программе, что вывод нужно осуществлять не в stdout, а в файл file (опция -out присутствует во множестве других компонентов openssl и используется аналогичным образом для указания выходного файла). Опция -rand указывает на файл[ы] (разделенные «:»), из которых будут считываться данные для установки seed (зерна) генератора случайных чисел. В качестве таких файлов сразу же приходит на ум использовать что-то вроде /dev/random или /dev/urandom, но у меня с этим возникли проблемы: все вешалось наглухо, поэтому я рекомендую в этом случае использовать какие-нибудь сложно угадываемые файлы, вроде /var/log/messages или /boot/vmlinuz, думаю, что угадать содержимое этих файлов не намного проще, чем содержимое /dev/random, но работает этот фокус в любом *nix (опция -rand также присутствует во всех компонентах генерации и управления ключами и сертификатами). Использовать /dev/random и /dev/urandom, конечно, можно, но я для этого скопировал из /dev/random 32768 байт в файл .rnd таким образом: dd if=/dev/[u]random of=.rnd count=64



Кроме этого, можно указывать в качестве -rand-файла EGD-сокет, который обеспечивает генерацию определенного количества случайных байт, EGD доступен на узле http://www.lothar.com/tech/crypto/. Установка генератора случайных чисел производится на основании хеша -rand файла, поэтому можно указывать файлы различной длины, т.к. хеш все равно имеет фиксированное число бит. Пример генерации 4096 битового секретного ключа RSA: # openssl genrsa -out /etc/openssl/key.pem -des3
-rand /var/log/messages 4096 Generating RSA private key .....++*...++++++++* Enter PEM passphrase: Verify PEM passphrase:

После этого секретный ключ зашифровывается и записывается в файл (в текстовом виде). В начале ключа указывается алгоритм шифрования. Для создания публичного ключа rsa на основе секретного используется команда openssl rsa. Даная команда имеет следующий формат:

openssl rsa -in filename [-out file] [-des | -des3 |-idea] [-check] [-pubout]

Утилита openssl rsa способна изменять пароль и алгоритм шифрования секретного ключа, будучи вызвана с параметром -in и -out. Если применить параметр -pubout, то в указанный файл -out будет записан публичный ключ, вычисленный на основе -in секретного. Например, создание публичного ключа на основании секретного: openssl rsa -in /etc/openssl/key.pem
-out /etc/openssl/pubkey.pem -pubout

Изменение пароля и алгоритма шифрования секретного ключа с des3 на idea: openssl rsa -in /etc/openssl/key.pem -out /etc/openssl/key1.pem -idea

Для создания ключей DSA используется утилита openssl gendsa, аналогичная genrsa, но есть два отличия: во-первых, для ключей DSA нельзя прямо указывать длину в битах и, во-вторых, ключи DSA могут генерироваться согласно некоторым параметрам, записанным в файл paramfile утилитой openssl dsaparam. dsaparam имеет следующий формат:

openssl dsaparam [-rand file{s}] [-C] [-genkey] [-out file] numbits

где numbits — длина желаемого ключа, -С заставляет dsaparam вывести на stdout код на СИ для программной генерации DSA на основе необходимых параметров, а опция -genkey говорит, что в выходной файл, наряду с параметрами, дополнительно записывается созданный секретный ключ DSA, но нельзя его сразу же зашифровать, поэтому удобнее воспользоваться утилитой openssl gendsa, которая имеет схожий синтаксис с командой genrsa, но вместо числа бит указывается файл параметров, созданный dsaparam:

# openssl gendsa -out /etc/openssl/dsakey.pem -rand /boot/vmlinuz -idea paramfile



  Enter PEM passphrase:

  Verify PEM passphrase:

Для управления ключами dsa используется программа openssl dsa, которая абсолютно аналогична (в параметрах) утилите openssl rsa. Поэтому я просто приведу пример генерации публичного ключа DSA: # openssl dsa -in /etc/openssl/dsakey.pem
-out /etc/openssl/pubdsakey.pem -pubout

Теперь настало время рассказать о компонентах openssl, выполняющих шифрование и хеширование данных. Для выполнения симметрического шифрования используется утилита openssl enc -cipher или ее сокращенная запись openssl cipher, где cipher — это одно из символических имен симметрических шифров. Наиболее популярными являются следующие: base-64 (преобразование в текстовый вид), bf (blowfish — 128 бит), des (56 бит), des3 (168 бит), rc4 (128 бит), rc5 (128 бит), rc2 и idea (128 бит). Для указания входного и выходного файлов используется опции -in и -out соответственно. Пароль для шифрования вводится с клавиатуры (можно указать в командной строке параметром -k, но это очень плохо по соображениям безопасности, т.к. большинство шеллов умеют сохранять историю командной строки, IMHO намного лучше ввести пароль непосредственно перед шифрованием, хотя эта опция полезна для скриптов, так что забывать о ней нельзя :). Учтите, что пароль не спрашивается при обработке файла base64, т.к. шифрования не происходит. Для расшифровки зашифрованных данных примените openssl cipher с опцией -d (алгоритм шифрования и дешифрования должен совпадать!), а для одновременной обработки данных base64 можно воспользоваться опцией -a. Шифрование по умолчанию происходит с подмешиванием, т.е. для выбора алгоритма подмешивания используется случайная соль (salt), в этом случае, если вы шифруете один и тот же файл в разное время одним и тем же алгоритмом и паролем, то результаты скорее всего будут разными (это затрудняет атаку по словарю). Также по умолчанию используется cbc-режим алгоритмов, когда ключ меняется в течение всего сеанса работы согласно передаваемым данным, этот прием очень сильно затрудняет брутфорс, т.к. атакующему сложно поймать нужный момент времени. Приведу несколько примеров:

* зашифруем файл, используя алгоритм des3
# openssl des3 -in file -out file.des3
* расшифруем полученный файл
# openssl des3 -d -in file.des3 -out file
* зашифруем файл, используя алгоритм blowfish(bf), и



* закодируем base64
# openssl bf -a -in file -out file.bf64
* теперь расшифруем его и обработаем сразу же base64
# openssl bf -a -d -in file.bf64 -out file

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

openssl hashalg [-c] file[s]

Вычисляется хеш-сообщения фиксированной длины в виде одной строки или, если указана опция -c, строки, разделенной на пары HEX-чисел двоеточием. Из алгоритмов хеширования могут применяться следующие: md2 (128 бит), md4(128 бит), md5 (128 бит), mdc2 (128 бит), sha (160 бит), sha1 (160 бит), ripemd160 (160 бит). Опять же приведу пару примеров:

* вычислим md5-хеш файла:
# openssl md5 -c file
MD5(file)= 81:fd:20:ff:db:06:d5:2d:c3:55:b5:7d:3f:37:ac:94
* а теперь SHA1-хеш этого же файла:
# openssl sha1 file
SHA1(file)= 13f2b3abd8a7add2f3025d89593a0327a8eb83af

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

openssl dgst -sign private_key -out signature -hashalg file[s]

Подписывание file с помощью секретного ключа "private_key", используя алгоритм хеширования "hasalg" (обычно применяются sha1 или md5). openssl dgst -signature signature -verify public_key file[s]

Проверка подписи в "file", используя публичный ключ "public_key" и ЭЦП "signature". Данная программа выводит «Verification OK» при правильной подписи или «Verification Failure» в любом другом случае. Учтите, что ЭЦП в таком случае хранится отдельно от файла, который ею подписан (причем в каком-то кривом формате).

Для шифрации и дешифрации RSA алгоритмом используется программа rsautl. Данная утилита имеет также возможность подписывать и проверять подпись сообщений (однако работать все равно приходится с хешем сообщения, т.к. подписывать можно только небольшой объем данных, по этой причине лучше применять openssl dgst). Для шифрации/дешифрации используется следующий синтаксис:

openssl rsautl -in file -out file.cr -keyin pubkey.pem -pubin -encrypt



(Шифрация "file" с использованием публичного ключа "pubkey.pem")

openssl rsautl -in file.cr -out file -keyin secretkey.pem -decrypt

(Дешифрация "file.cr" с использованием секретного ключа "secretkey.pem")

Теперь настало время рассказать об одном из главных применений openssl — управление сертификатами. Openssl имеет возможность генерировать сертификаты, управлять ЭЦП и шифрацией с помощью сертификатов. Однако применение утилит управления сертификатами — достаточно сложная задача. Поэтому для начала я дам общие представления о сертификатах. Сертификат содержит публичный ключ, подписанный одним из корневых доверенных центров сертификации (или комплементарным секретным ключом), данные об организации, выдавшей сертификат и в некоторых случаях зашифрованный секретный ключ, а также отпечаток (хеш) публичного ключа. Сертификаты имеют время действия, по окончанию которого они автоматически считаются недействительными, иерархия сертификатов обычно строится на основании сети доверия (бывают довольно длинные цепочки сертификатов, ведущие к доверенному ключу из root CA). Таким образом, сертификат — это полный комплекс системы асимметрического шифрования, предоставляющий гораздо больше возможностей, чем сами по себе ключи (а также являющийся более защищенной системой). Основным привлекательным моментом сертификата является возможность записи в него информации об организации, этот ключ выдавшей. Таким образом явно напрашивается применение собственной системы сертификации в данной организации. Можно, например, выдавать сотрудникам их персональные сертификаты, подписанные сертификатом организации (его можно сгенерировать самому или получить от сторонней компании). Причем эти сертификаты впоследствии можно использовать для удостоверения личности сотрудника, например, при почтовой переписке или аутентификации на http-сервере (apache+ssl). Единственное условие, которое должно выполняться, — это наличие на машине клиента сертификата организации в списке корневых доверенных ключей. Общее содержание сертификатов определено стандартом x509, в то время как форматы записей сертификатов могут внести некоторую путаницу. Openssl по умолчанию использует формат PKCS#10, Microsoft использует по умолчанию формат PKCS#12 (в руководстве по openssl этот формат охарактеризован, как один большой баг :), формат PKCS#7 используется для запросов на сертификацию к CA (центр сертификации) и не может содержать секретного ключа, также для этой цели может использоваться DER-закодированный сертификат (DER-кодирование подобно кодированию base64, но имеет специальное назначение для использования в криптографических системах) также без секретного ключа. Учтите, что при использовании DER-формата убираются маркеры начала и конца сертификата, а его содержимое кодируется base64, поэтому в файле DER можно хранить только один сертификат, с другой стороны DER сертификаты поддерживаются M$ (стандартное расширение .cer), поэтому иногда бывает нужно преобразовать сертификаты из одного формата в другой (я здесь имею ввиду PEM или DER): PEM-->DER openssl x509 -inform PEM -in cert.pem
-outform DER -out cert.cer DER-->PEM openssl x509 -inform DER -in cert.cer
-outform PEM -out cert.pem



Таким же образом можно конвертировать и ключи асимметрического шифрования (используя утилиты rsa или dsa).

Думаю, что не сильно запутал вас всеми этими стандартами. Если объяснять на пальцах, то все выглядит следующим образом: клиент создает сертификат и отправляет свой публичный сертификат (PKCS#7) в центр сертификации. В центре сертификации обрабатывается запрос клиента (запрос на сертификацию), и сертификат клиента подписывается секретным ключом центра сертификации. Клиент, имея публичный ключ центра сертификации, проверяет подлинность подписи и может далее использовать свой сертификат. Для организации можно предложить следующее решение: на сервере создается сертификат организации; генерируется запрос на сертификацию и отправляется к некоему доверенному центру сертификации (который будет известен всем клиентам и персоналу данной организации); получается сертификат организации, который можно использовать при создании сертификатов клиентов. Последние создаются так: клиент посылает запрос на выдачу сертификата; сервер создает сертификат клиента и подписывает его сертификатом организации; клиент получает сертификат клиента и сертификат организации; после проверки достоверности ключа организации (предполагается, что клиент доверяет CA, которым был подписан сертификат организации) проверяется достоверность сертификата клиента. После такой операции клиент будет точно уверен, что получил сертификат от данной организации, и может его использовать для работы с ней. По такой схеме построены все центры выдачи сертификатов(правда зачастую сертификат организации бывает подписан самим собой, что требует от клиента добавить сертификат организации к доверенным, а в первой схеме сертификат организации принадлежит к группе промежуточных центров сертификации, и этот случай предпочтительнее с точки зрения безопасности и удобства клиента, но требует больше работы от администратора). Да, хорошенькое объяснение на пальцах! Но что тут поделать: сертификаты — это довольно запутанная вещь. Сейчас я объясню, как создавать сертификаты с помощью openssl, и приведу пример только что описанного безобразия…

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

[ req ]
# Секция основных опций
default_bits = 2048
# Число бит
default_keyfile = keyfile.pem
# Имя ключа, используемого для сертификата
distinguished_name = req_distinguished_name
# DN организации, выдавшей сертификат
prompt = no
# Брать параметры из конфига неинтерактивный режим
[ req_distinguished_name ]
# DN организации
CN=RU
# Страна
ST=Ivanovskaya
# Область
L=Gadukino
# Город
O=Krutie parni
# Название организации
OU=Sysopka
# Название отделения
CN=Your personal certificate
# Имя для сертификата (персоны, получающей сертификат)
emailAddress=certificate@gaduk.ru
# Мыло организации



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

имя = подсказка
имя_default = значение_по_умолчанию
имя_max = максимум
имя_min = минимум

Пример интерактивного файла конфигурации:

[ req ]
default_bits = 1024
default_keyfile = privkey.pem
distinguished_name = req_distinguished_name

[ req_distinguished_name ]

countryName = Country Name (2 letter code)

countryName_default = RU

countryName_min = 2

countryName_max = 2

localityName = Locality Name (eg, city)

organizationName = Organization Name(eg, org)

organizationalUnitName = Organizational Unit Name (eg, section)

commonName = Common Name (eg, YOUR name)

commonName_max = 64

emailAddress = Email Address

emailAddress_max = 40

Спешу обрадовать некоторых ленивых товарищей: если вы намереваетесь создавать просто сертификат сервера (например, для LDAP-сервера), то указывать конфиг необязательно, будет использоваться конфиг по умолчанию /usr/lib/ssl/openssl.cnf, который содержит все необходимое. Ну а теперь традиционно приведу примеры использования openssl req(я не собираюсь подробно описывать данную команду, т.к. думаю, что для большинства случаев хватит примеров, а для особых случаев можно почитать man req).

openssl req -new -newkey rsa:2048 -keyout rsa_key.pem -config cfg -out certreq.pem

Создание запроса на сертификацию (-new) на основе создаваемого секретного ключа rsa (-newkey rsa:2048), который записывается в файл -keyout(и шифруется тройным DES). Запрос на сертификацию создается на основе конфигурационного файла — config. openssl req -x509 -new -key private_key.pem -config cfg -out selfcert.pem -days 365

Создание (-new) self-signed сертификата (-x509) для использования в качестве сертификата сервера или сертификата CA. Сертификат создается с использованием секретного ключа -key и конфигурационного файла -config. Создаваемый сертификат будет действителен в течение 365 дней (-days), опция -days не применима к запросам на сертификацию.

Для управления сертификатами x509 используется утилита openssl x509. С ее помощью можно подписать сертификат или запрос на сертификацию сертификатом CA. Также можно просмотреть содержимое сертификата в читаемой форме (DN, публичный ключ, время действия, отпечаток и.т.д.). Приведу примеры вышеописанных действий:

openssl x509 -in cert.pem -noout -text



Просмотреть информацию о сертификате в «нормальной» форме. Вот что примерно будет выведено, также можно использовать дополнительные опции: -fingerprint (необходимо сочетать с одной из опций -sha1, -md5 или -mdc2), -modulus (вывод публичного ключа), -serial, -subject, -issuer (организация, выдавшая сертификат), -email, -startdate, -enddate:

Certificate:
Data:
Version: 3 (0x2)
Serial Number: 0 (0x0)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=RU, ST=region, L=city, O=organization, OU=Sysopka,CN=CEBKA/Email=CEBKA@smtp.ru
Validity
Not Before: Nov 9 08:51:03 2002 GMT
Not After : Nov 9 08:51:03 2003 GMT
Subject: C=RU, ST=region, L=city, O=organization, OU=Sysopka,CN=CEBKA/Email=CEBKA@smtp.ru
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit):
00:c6:6b:3b:8e:f8:33:05:a0:dc:e1:38:8f:6a:68:
42:1c:21:33:aa:90:b6:8c:93:14:11:9b:69:94:8a:
3a:0e:42:29:b0:45:14:1b:f0:37:2c:f3:05:db:13:
06:a9:cd:eb:99:31:51:25:86:c8:69:e0:5e:8d:28:
04:8d:1f:08:37:d7:72:39:fe:05:57:61:68:95:bf:
5c:ae:13:f2:05:a1:29:c3:bf:3b:32:ca:1a:ff:22:
53:f9:32:92:78:fe:44:c3:e1:ca:42:5c:5f:d1:49:
da:1c:9f:34:06:04:ee:46:74:8d:11:68:ef:37:e2:
74:1e:d9:46:04:b8:7e:d5:c5
Exponent: 65537 (0x10001)
Signature Algorithm: md5WithRSAEncryption
3b:42:85:45:08:95:f3:f1:fc:8a:23:88:58:0e:be:e5:9b:56:
1e:c1:ff:39:28:4f:84:19:f8:3e:38:ef:98:34:d6:ee:e0:0a:
de:36:3a:5c:15:88:d7:2a:a4:0a:d5:dc:3e:b2:72:4c:82:57:
b8:fe:52:f6:e2:06:01:38:eb:00:0b:f2:a9:87:be:65:83:19:
13:50:ae:6c:f2:0a:07:14:e6:8c:60:cd:c5:a3:d1:e1:ea:da:
24:c2:6a:06:d5:dc:1c:71:c9:64:fa:9e:c9:ca:97:e2:06:84:
de:4c:69:b8:9a:af:66:14:8d:46:9a:00:53:13:c9:ab:10:b8:
09:c2

openssl x509 -req -in clientreq.pem -extfile /usr/lib/ssl/openssl.cnf \ -extensions /usr/lib/ssl/openssl.cnf -CA CAcert.pem
-CAkey serverkey.pem \ -CAcreateserial -out clientcert.pem

Подписать запрос на сертификацию (-req) файла -in, используя доверенный CA сертификат -CA и его секретный ключ -CAkey. В конечный сертификат клиента (-out), записываются дополнительные параметры сертификата 3-й версии из файла /usr/lib/ssl/openssl.cnf (конфигурационный файл по умолчанию). Но об этом я расскажу после на конкретном примере. Такое поведение x509 позволяет организовать свой центр сертификации, подписывающий запросы клиентов на сертификацию. openssl x509 -in CAcert.pem -addtrust sslclient -alias "myorganization CA" \ -out CAtrust.pem



Преобразование сертификата -in в доверенный сертификат для использования в SSL-клиентах (sslserver — использование в качестве сертификата сервера, emailProtection — использование в качестве сертификата S/MIME).

Я еще раз хотел бы вернуться к проблеме построения CA. Для использования внутри организации можно использовать self-signed сертификат, но для использования CA вне организации приходится использовать сертификаты, выданные или подписанные сторонней организацией. Во втором случае возникает проблема выбора такой сторонней организации (она легко разрешается для дочерних компаний), которая требует юридического анализа (в разных странах существуют свои законы криптографии и поэтому дать какой-либо конкретный совет я не могу). Если вам довелось работать в российской правительственной компании, то считайте, что вам не повезло — использовать openssl для работы с правительственными организациями нельзя. Наши уважаемые гос. деятели добавили геморроя админам, разрешив использовать только алгоритмы ГОСТ (симметрические, асимметрические, хеширования — меня просто выворачивает от самого этого слова ГОСТ ;), поэтому использовать вам придется только специальные программы, реализующие эти алгоритмы. Я же приведу здесь пример построение собственного CA с self-signed сертификатом:

1) Генерируем секретный ключ:

openssl genrsa -out CAkey.pem -rand randfile -des3 4096

2) Создаем self-signed сертификат:

openssl req -new -x509 -key CAkey.pem -out CAcert.pem -days 365 -config cfg

Содержимое конфигурационного файла зависит от организации, можно даже воспользоваться утилитой /usr/lib/ssl/misc/CA.pl -newcert, которая создаст ключ и сертификат в одном файле в интерактивном режиме (хотя мне этот вариант не очень понравился, лучше один раз написать нормальный конфиг) — о дополнительных требованиях к конфигурации CA сертификата см. ниже.

3) Приведу пример скрипта, генерирующего клиентские сертификаты:

#!/bin/bash

dd if=/dev/random of=/tmp/.rnd count=64

RAND="/var/log/messages:/boot/vmlinuz:/tmp/.rnd"



REQ="openssl req"

X509="openssl x509"

RSA="openssl rsa"

GENRSA="openssl genrsa"

O="company"

C="RU"

ST="region"

L="city"

PURPOSES="digitalSignature, keyEncipherment"

CERTTYPE="client, email, objsign"

CA="/etc/openssl/CAcert.pem"

CAkey="/etc/openssl/CAkey.pem"

OUTDIR="/etc/openssl/clientcert/"

CN="client"
BITS=2048
DAYS=365

# Создаем секретный ключ во временной папке БЕЗ шифрования

TMP="/tmp/ssl-$$"
mkdir $TMP

if [ ! -d $OUTDIR ];then
mkdir $OUTDIR
fi


pushd $TMP > /dev/null
$GENRSA -rand $RAND -out tmp.key $BITS

# Создаем конфиг для клиента

cat > cfg <

[ req ]
default_bits = $BITS
distinguished_name = req_DN
extensions = v3_req
[ req_DN ]
countryName = "1. Country Name (2 letter code)"
countryName_default = "$C"
countryName_min = 2
countryName_max = 2
stateOrProvinceName = "2. State or Province Name (full name) "
stateOrProvinceName_default = "$ST"
localityName = "3. Locality Name (eg, city) "
localityName_default = "$L"
0.organizationName = "4. Organization Name (eg, company) "
0.organizationName_default = "$O"
organizationalUnitName = "5. Organizational Unit Name (eg, section) "
organizationalUnitName_default = "$OU"
commonName = "6. Common Name (eg, CA name) "
commonName_max = 64
commonName_default = "$CN"
emailAddress = "7. Email Address (eg, name@FQDN)"
emailAddress_max = 40
emailAddress_default = ""
[ v3_req ]
basicConstraints = CA:FALSE
keyUsage = $PURPOSES
nsCertType = $CERTTYPE
EOT
# Создаем запрос на сертификацию
$REQ -new -key tmp.key -config cfg -rand $RAND -out $CN.pem

# Этот файл лучше удалить побыстрее: мало ли чего...
rm -fr /tmp/.rnd

if [ $? -ne 0 ]; then
echo "Failed to make a certificate due to error: $?"
popd > /dev/null
rm -fr $TMP
exit $?
fi
# Подписываем сертификат сертификатом сервера

$X509 -req -in $CN.pem -CA $CA -CAkey $CAkey -CAsetserial \
-extensions -config cfg -days $DAYS -out $OUTDIR$CN.pem

chmod 0400 $OUTDIR$CN.pem
chown root:root $OUTDIR$CN.pem
# Шифруем секретный ключ
$RSA -in tmp.key -des3 -out $OUTDIR$CN-key.pem

chmod 0400 $OUTDIR$CN-key.pem
chown root:root $OUTDIR$CN-key.pem
# Выполняем заключительные действия
popd > /dev/null

rm -fr $TMP

echo -e "Generation complete, go to $OUTDIR and give to client $CN his certificate and \
\n private key (for windows users you should use openssl pkcs12 utility)"



Дополнительные свойства, описанные в скрипте (v3_req), означают, что клиент может использовать сертификат для подписывания и шифрации, но его сертификат не является CA сертификатом. Для CA-сертификата значение basicConstraits должно быть равно CA:TRUE (об этом забывать нельзя!). Поле nsCertType определяет дополнительные назначения данного ключа (для использования в качестве клиента, подписывания, использования в почтовых сообщениях). Для CA-сертификатов обычно применяют следующие значения nsCertType: sslCA, emailCA. Для ssl-ключей серверов (например, Apache) используется значение nsCertType = server. Полученный таким образом сертификат клиента будет содержать информацию о поставщике сертификата (то есть о вашем сертификате организации). Клиенту необходимо будет передать его сертификат, его секретный ключ (зашифрованный!) и ваш сертификат организации. Для клиентов Micro$oft необходимо еще и перевести сертификаты в формат PKCS#12. Для этого воспользуемся командой openssl pkcs12: openssl pkcs12 -export -in client.pem
-inkey client-key.pem -out client.p12 \ -name "Client certificate from our organization"

Для обратного преобразования используется синтаксис:

openssl pkcs12 -in client.p12 -out client.pem

В выходной файл записываются сертификат клиента, ca сертификат, секретный ключ клиента (его можно зашифровать опцией -des3, -idea и.т.д.). Такое поведение позволяет использовать для вывода только формат pem (маркеры здесь обязательны!). Для экспорта сертификата организации можно воспользоваться командой pkcs12 (конечно же, без параметра inkey ;), можно также обработать сертификат организации base64 и сохранить в файле .cer (openssl x509 -in CA.pem -outform DER -out CA.cer).

В openssl существует компонент управления s/mime-сообщениями, называющийся openssl smime. Данная утилита позволяет зашифровывать, расшифровывать, управлять ЭЦП и MIME-заголовками писем. Приведу опять же несколько примеров ее использования:

openssl smime -sign -in mail.txt -text -from CEBKA@smtp.ru -to \



user@mail.ru -subject "Signed message" -signer mycert.pem -inkey \
private_key.pem | sendmail user@mail.ru

Подписывает сообщение -in (в текстовом виде) и подписывает (-sign) его с помощью сертификата (-signer) и секретного ключа (-inkey). Вывод идет непосредственно к sendmail, для этого определены MIME-заголовки from, to и subject.

openssl smime -verify -in mail.msg -signer user.pem -out signedtext.txt

Проверяет подпись в файле -in, записывает сообщение в файл -out, а полученный сертификат — в файл -signer (для проверки s/mime-сообщения не требуется ничего, кроме него самого, т.к. ЭЦП s/mime содержит публичный ключ!). openssl smime -encrypt -in mail.txt -from CEBKA@smtp.ru
-to user@mail.ru \ -subject "Encrypted message" -des3 user.pem | sendmail \ user@mail.ru

Шифрация файла -in с помощью сертификата получателя "user.pem", используя алгоритм "des3". Вывод программы посылается непосредственно в sendmail. openssl smime -decrypt -in mail.msg -recip mycert.pem -inkey private_key.pem \ -out mail.txt

Расшифровка файла -in с помощью секретного ключа -inkey и сертификата -recip (ваш собственный сертификат).

Есть альтернатива не указывать smime-заголовки from, to и subject. Можно просто указать необходимый файл -out и добавить заголовки с помощью программы sendmail вручную. Кроме этого, есть еще одна деталь использования smime: некоторые почтовые клиенты используют в качестве подписи вложение в формате PKCS#7 (чаще всего закодированное base64). В таком случае необходимо применять smime следующим образом: openssl smime -verify -inform [PEM | DER]
-in signature.pem[der] -content \ mail.txt

PEM используется для стандартного формата PKCS#7, а DER заставляет произвести дополнительную обработку base64. Учтите, что в данном случае файл -in представляет собой только подпись (аттачмент), а -content — непосредственно текст письма. Можно также заставить smime подписывать сообщения подобным образом, если указать опцию -pk7out (PEM формат). Для преобразования PKCS#7 структуры из формата PEM в формат DER можно воспользоваться утилитой openssl base64 (обратное преобразование достигается за счет использования опции -d).

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


Доступ через сеть


Обе технологии рассчитаны на работу в незащищенных сетях, работающих по протоколу IP. Однако различие в возможностях этой работы очень существенны. Благодаря наличию системы сертификатов PKI может реализовать взаимодействие в сетях по протоколам HTTPS и (в том числе к почтовому серверу Microsoft Exchange Server, веб-сервисам на базе MicrosoftIIS), в то время как область применения PGP - это фактически только электронная почта.

Программы шифрования данных особенно полезны именно при работе в незащищенных сетях. Даже в случае использования незащищенного HTTP с помощью программ шифрования можно организовать обмен зашифрованными документами через онлайновые хранилища данных. Пользователь может зашифровать документы любым доступным встроенным криптопровайдером, поместить зашифрованный файл в хранилище и дать ссылку на скачивание своему корреспонденту. В системе PGP в этом варианте обмена не возникает вообще никаких проблем, в системе PKI необходимо, чтобы пользователи пользовались одинаковыми криптопровайдерами. Для официального документооборота необходимо в этом случае еще и использование сертифицированных российских СКЗИ. Ведущими средствами криптографической защиты информации на российском рынке программных средств сегодня являются от компании "Крипто-Про", - "Сигнал-КОМ", - "МО ПНИЭИ".



PKI или PGP?


,

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

Наличие ЦС и ЦР обусловило то, что в системе PKI доминирующим направлением подтверждения подлинности является вертикальная (иерархическая) составляющая, когда сертификат подтверждается кем-то, имеющим более высокий статус. В системе PGP основной является горизонтальная составляющая или, другими словами, схема "прямого доверия". Хотя и в той, и в другой системе возможно как вертикальное, так и горизонтальное подтверждение подлинности. Образно можно представить, что в PKI доверие распространяется в виде дерева, а в PGP - в виде сети.



Различия в стандартах


В основу PGP положен стандарт , который содержит:

сведения о владельце сертификата; открытый ключ владельца сертификата; ЭЦП владельца сертификата; период действия сертификата; предпочтительный алгоритм шифрования.

В основу PKI положен стандарт Х.509, который содержит:

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

Несмотря на наличие множества версий формата Х.509, существует ряд фундаментальных различий между форматами сертификатов Х.509 и PGP:

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



Так что же лучше?


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

При этом необходимо помнить, что приобретение одних только программ шифрования на основе стандарта Х.509 не создает в полной мере саму инфраструктуру PKI. Необходимо использовать сертифицированные для РФ криптопровайдеры, а также обеспечить взаимодействие с официальными российскими ЦС.

Ссылки по теме:

document.write('');

Новости мира IT:

02.08 - 02.08 - 02.08 - 02.08 - 02.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 31.07 - 31.07 - 31.07 - 31.07 - 31.07 -

Архив новостей

Последние комментарии:

 (66)

2 Август, 17:53

 (19)

2 Август, 17:51

 (34)

2 Август, 15:40

 (42)

2 Август, 15:35

 (1)

2 Август, 14:54

 (3)

2 Август, 14:34

 (3)

2 Август, 14:15

 (2)

2 Август, 13:34

 (7)

2 Август, 13:04

 (3)

2 Август, 12:28

BrainBoard.ru

Море работы для программистов, сисадминов, вебмастеров.

Иди и выбирай!

Loading

google.load('search', '1', {language : 'ru'}); google.setOnLoadCallback(function() { var customSearchControl = new google.search.CustomSearchControl('018117224161927867877:xbac02ystjy'); customSearchControl.setResultSetSize(google.search.Search.FILTERED_CSE_RESULTSET); customSearchControl.draw('cse'); }, true);

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
<

VPN


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



Who is who?


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

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

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

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



Задачи, решаемые PGP и PKI


Обе эти технологии используются для следующих целей:

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

Рассмотрим работу систем PGP и PKI.



Защита файлов и документов


Задача криптографической защиты электронных почтовых сообщений, файлов и документов сводится к шифрованию данных. И PGP, и российские программные продукты, реализующие логику PKI, позволяют шифровать информацию. Для частной переписки этих мер безопасности может быть вполне достаточно, но для работы государственных и коммерческих организаций этих возможностей недостаточно. Прежде всего потому, что PGP не работает с российскими стандартами, а значит, не отвечает ни необходимому уровню безопасности, ни существующим . Работу с сертифицированными криптографическими алгоритмами поддерживают такие отечественные программы, как (компания "Информзащита"), (компания Digt), (ООО "Газинформсервис"), и ("Сигнал-КОМ").

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

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



Алгоритм декодирования ресурсов из PWL-файла с правильным паролем


После нахождения правильного пароля прогоняем функцию XorT с индексами не 1...33, а 33...63. Таким образом мы декодируем 15 адресов блоков с ресурсами. Должны получиться значения типа 0x292, 0x294 и т.д. Как мы помним, адрес 1-го блока всегда равен 0x290. Таким образом, у нас будет массив Res[17] типа WORD, в первое значение - 0x290, далее 15 декодированных адресов, а последний WORD - это размер файла (в примере выше это будет значение 0x2DC).

Далее следует цикл на 16 (проверка блоков с ресурсами), в начале его вычисляем разницу между соседними адресами N - если разница между ними равна 2, то переход на следующий адрес.

Если N > 2, то данный i-й блок содержит ресурсы.

Формируем новый массив X (размером 64 байта) следующим образом:

0xFFFFFFFF (DWORD)

Логин в верхнем регистре

0x0 (1 байт)

CryptoSeed[i] (DWORD) - это значение берем из массива по адресу 0x20C, причем i - это номер блока ресурсов.

0x80 (1 байт)

0x0 (по адрес 0x37 включительно)

По адресу 0x38 записываем (0x48 + (длина логина << 3)) (DWORD)

0x0 (до конца массива)

Выполняем MD5 (массив X), получаем массив Cnt (16 байт), т.е. производим свертку логина с нужным CryptoSeed.

Формируем массив Z (размером 64 байта) следующим образом:

Пароль

0x0 (1 байт)

Cnt (16 байт)

0x80 (1 байт)

0x0 (по адрес 0x37 включительно)

По адресу 0x38 записываем (0x88 + (длина пароля << 3)) (DWORD)

0x0 (до конца массива)

Выполняем MD5 (массив Z), получаем массив Key (16 байт), т.е. производим свертку пароля.

Выполняем RC4, используя в качестве ключа Key.

И теперь полученным массивом M начинаем декодировать весь блок с ресурсами длиной N процедурой, аналогичной XorT. Причем начинаем использовать массив M также с 1-го значения (не с нулевого(!)) до 255, если ресурс больше 255 символов, то i "переваливает" байтовую границу и уже массив M начинает использоваться с нуля, а не с единицы.

Посмотрим на приведенном выше примере структуру первого из наших декодированных ресурсов:

0290: .. .. .. .. .. .. 1A 00 0A 00 08 00 01 03 43 52 |..............CR


02A0: 49 53 54 49 41 4E 5C 44 68 65 6C 6C 67 61 74 65 |ISTIAN\Dhellgate

Ее формат такой:

? длина ресурса (WORD), в нашем примере - 26(0x1A) байт.

? длина логина (WORD), в нашем примере - 10 символов.

? длина пароля (WORD), в нашем примере - 8 символов.

? BYTE, назначение которого пока точно не известно.

? тип хранимого ресурса (BYTE):



1 = NT Domain

2 = NT Server

3 = Shared

4 = MAPI

6 = Dial-Up

18 = NetWare

19 = WWW

Далее располагаются логин, а после него - пароль.

В нашем примере - тип ресурса "Shared", логин "CRISTIAN\D", пароль "hellgate".
(Примечание: для Shared-ресурсов запись CRISTIAN\D будет означать следующее: CRISTIAN - имя компьютера, а D - ресурс, предоставленный для общего пользования.)

Далее анализируем текущий блок с ресурсами, пока не перевалили за N, "поглядывая" в таблицу по адресу 0x109, т.к. в PWL-файлах между блоками ресурсов очень часто бывает "мусор" (неисповедимы пути Microsoft), а в этой таблице будет точное указание - в каком блоке сколько ресурсов.


Формат PWL-файлов Windows'OSR2/98/ME


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

Подробно рассмотрим в качестве примера следующий PWL-файл:

0000: E3 82 85 96 03 00 00 00 02 00 01 00 00 00 00 00

0010: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0030: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0040: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0050: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0060: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0070: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0090: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00A0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00B0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00C0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00D0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00E0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00F0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0100: 00 00 00 00 00 00 00 00 00 0D 03 FF FF FF FF FF

0110: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0120: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0130: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0140: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0150: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0160: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0170: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0180: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0190: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

01A0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

01B0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

01C0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

01D0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF


01E0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

01F0: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

0200: FF FF FF FF FF FF FF FF 52 02 00 00 00 00 00 00

0210: 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00

0220: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0230: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

0240: 01 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00

0250: 00 00 88 51 47 58 2C 74 13 7C 6F D7 9E 9D 58 59

0260: 0B 3A A5 22 85 22 94 80 58 F9 61 00 B6 51 72 28

0270: D5 D7 3A 58 23 03 DD BC A7 4B E7 E2 71 65 66 CE

0280: 3F 58 FC 59 76 02 F0 12 8E 5F 79 94 39 E0 36 29

0290: 13 B9 8E 3B A1 F3 74 D4 78 38 01 E0 B5 FE DE A3

02A0: 80 CC 4E B7 67 1D 7C 36 7B C5 AA 76 4C D0 8E EE

02B0: 28 78 8A BB 7A 5A 81 2C AB 29 79 97 33 89 60 79

02C0: F7 6C 1C 72 1B 33 0A 09 F2 7E E4 3A A6 BE F4 C6

02D0: AE 06 DE 31 67 BB EA 7B D5 CA AE 01

Теперь внимательно посмотрим, из каких полей состоит файл:

Сразу оговорю следующие ограничения PWL-файлов: в файле может находится максимум 16 блоков ресурсов. Максимальное количество ресурсов в файле - 255. Это ограничения самой Windows. В каждом блоке может располагаться любое количество ресурсов, но их суммарное количество не может быть больше 255. И еще одно ограничение PWL-файла - то, что он не может быть больше 64кБ.

Итак, первое, что мы видим - это сигнатура (т.е. первые 4 байта файла), которая равна 0x968582E3, сразу же замечу, что у PWL-файлов от Windows'3.11/95 сигнатура другая - 0x4E464DB0.

По смещению 0x4 следует DWORD с неизвестным содержимым.

По смещению 0x8 следует WORD. Он определяет общее кол-во ресурсов в файле. В нашем примере - 2 ресурса.

Начиная с адреса 0x00A до адреса 0x109 располагается странная таблица размером 255 байт. Какую она содержит информацию, известно лишь Microsoft. Есть предположение, что там хранятся номера ресурсов, хотя эта таблица для декодирования данных из файла в принципе не нужна.

Начиная с адреса 0x109 до адреса 0x208 находится другая таблица (тоже размером 255 байт), в которой хранится такая информация: любой байт из этой таблицы равный i (кроме 0xFF) означает, что i-й блок содержит ресурсы. Количество одинаковых байт равных i в данной таблице отражает количество ресурсов в i-м блоке. В нашем примере - 1-й байт в таблице показывает, что у нас имеются ресурсы в 13-м (0x0D) блоке, а 2-й байт в таблице показывает, что у нас имеются ресурсы в 3-м блоке ресурсов.



По адресу 0x208 находится DWORD (у нас он равен 0x00000252), который определяет смещение CryptoSign. Кстати, я в этом поле других значений не видел ни в одной PWL-ке!

С адреса 0x20C по 0x24C располагается массив CryptoSeed[16], он необходим для декодирования всех 16 блоков ресурсов.

По адресу 0x24C располагается CheckSeed (DWORD), с которого и начинается декодирование PWL-файла.

Далее идут два нулевых байта. Какую они несут функцию - неизвестно.

По адресу 0x252 располагается массив CryptoSign (16 байт).

По адресу 0x262 располагается массив CheckSign (16 байт) - этот массив вместе с CryptoSign является "контрольным значением" для определения правильности пароля. Их применение рассмотрим ниже.

По адресу 0x272 располагается массив из 15 WORD'ов - это адреса 15 блоков ресурсов, начиная со второго. Адрес же первого ресурса всегда один и тот же и составляет 0x290. Эти адреса уже являются зашифрованными. Посмотрим, что это будут за байты после декодирования правильным паролем:

0270: .. .. 92 02 94 02 96 02 B2 02 B4 02 B6 02 B8 02

0280: BA 02 BC 02 BE 02 C0 02 C2 02 C4 02 D8 02 DA 02

Как мы видим - действительно там находятся адреса! Эти адреса никогда не могут быть одинаковымии получается, что если блок ресурсов пустой, то он все равно занимает 2 байта  - это мы видим на начальных адресах: 0x292, 0x294 - эти значения ссылаются на "мусор", ресурсы же в этом файле находятся по адресам 0x296 ... 0x2B2 и 0x2C4 ... 0x2D8 - это видно по тому, что разница между этими соседними адресами больше двух байт и т.к. мы уже отмечали, у нас 3-й и 13-й блок имеют ресурсы (см. пункт 6).

А с адреса 0x290 начинаются непосредственно ресурсы. Эти данные также зашифрованы. После дешифрования мы увидим, что с адресов 0x296 и 0x2C4 действительно есть что-то, похожее на ресурсы :)

0290: 4C 9C 50 94 C9 82 1A 00 0A 00 08 00 01 03 43 52 |L.P...........CR

02A0: 49 53 54 49 41 4E 5C 44 68 65 6C 6C 67 61 74 65 |ISTIAN\Dhellgate

02B0: E3 A8 CF DD 80 8A 8D 9A 1B 97 6B B9 BD F0 AE 9A |....?.....k.....

02C0: 5C D4 20 88 12 00 05 00 05 00 00 04 4D 41 50 49 |\. .........MAPI

02D0: 00 4D 41 50 49 00 28 F3 1D B2 90 80             |.MAPI.(....?

Как правильно декодировать ресурсы и их формат будет рассмотрен ниже.


это не что иное, как


MD5 - это не что иное, как операция свертки 64 байт в 16.

Посмотрим как эта функция описана в официальном документе - RFC1321 с небольшими упрощениями и нашими комментариями:

...

#define S11 7

#define S12 12

#define S13 17

#define S14 22

#define S21 5

#define S22 9

#define S23 14

#define S24 20

#define S31 4

#define S32 11

#define S33 16

#define S34 23

#define S41 6

#define S42 10

#define S43 15

#define S44 21

/* F, G, H and I are basic MD5 functions */

/* Основные макросы преобразования */

#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))

#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))

#define H(x, y, z) ((x) ^ (y) ^ (z))

#define I(x, y, z) ((y) ^ ((x) | (~z)))

/* ROTATE_LEFT rotates x left n bits */

/* Этот макрос - это всего лишь элементарная команда циклического сдвига ROL на Асме! Оригинальный вариант ротации на С работает быстрее на процессорах с архитектурой RISC. Для x86 процессоров лучше использовать команду ROL */

#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4. Rotation is separate from addition to prevent recomputation */

/* Основные макросы трансформации значений a, b, c и d */

#define FF(a, b, c, d, x, s, ac) { \

(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \

(a) = ROTATE_LEFT ((a), (s)); \

(a) += (b); \

}

#define GG(a, b, c, d, x, s, ac) { \

(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \

(a) = ROTATE_LEFT ((a), (s)); \

(a) += (b); \

}

#define HH(a, b, c, d, x, s, ac) { \

(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \

(a) = ROTATE_LEFT ((a), (s)); \

(a) += (b); \

}

#define II(a, b, c, d, x, s, ac) { \

(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \

(a) = ROTATE_LEFT ((a), (s)); \

(a) += (b); \

}

/* MD5 basic transformation. Transforms state based on block */

/* Непосредственно сам алгоритм MD5 */

static void MD5Transform (state, block)

{

UINT4 a,b,c,d,state[4], x[16];

a = state[0] = 0x67452301;



b = state[1] = 0xefcdab89;

c = state[2] = 0x98badcfe;

d = state[3] = 0x10325476;

/* Round 1 */

FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */

FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */

FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */

FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */

FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */

FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */

FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */

FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */

FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */

FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */

FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */

FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */

FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */

FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */

FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */

FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */

/* Round 2 */

GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */

GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */

GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */

GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */

GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */

GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */

GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */

GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */

GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */

GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */

GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */

GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */

GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */

GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */

GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */

GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */

/* Round 3 */

HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */

HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */

HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */

HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */

HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */



HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */

HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */

HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */

HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */

HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */

HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */

HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */

HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */

HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */

HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */

HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */

/* Round 4 */

II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */

II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */

II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */

II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */

II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */

II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */

II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */

II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */

II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */

II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */

II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */

II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */

II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */

II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */

II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */

II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */

state[0] += a;

state[1] += b;

state[2] += c;

state[3] += d;

}

В итоге получаем из входного массива x (16 DWORD'ов) массив state (всего 4 DWORD'a).


Описание алгоритмов, используемых для шифрования PWL-файлов


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



Оптимизация алгоритмов восстановления паролей


Вот и начинается самое интересное. ;)

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



Краткое описание: на входе имеем


Краткое описание: на входе имеем ключ размером 16 байт, на выходе получаем массив из 256 байт, в котором равномерно и псевдослучайно распределены байты от 0 до 255, причем их распределение зависит от входного ключа:

byte t; //Временная ячейка

byte A = 0; //Здесь будем получать новый псевдослучайный индекс

byte M[256]; //Наш формируемый массив

byte Key[16]; //Исходный ключ, с помощью него будем формировать массив M

for (int i = 0; i < 256; i++)

M[i] = i; //Последовательно заполняем массив значениями от 0 до 255

for (int i = 0; i < 256; i++)

{

   A += (M[i] + Key[i % 16]); //Вычисляем новый индекс для обмена байтами

   t = M[i]; 

   M[i] = M[A]; //Меняем местами i-й байт и байт по вычисленному индексу A

   M[A] = t; 

}

Далее по этому алгоритму байтами из массива M с помощью завершающей процедуры RC4 с применением операции XOR расшифровываются любые необходимые данные.


RC4 (1-я часть)


1. Сразу же бросается в глаза инициализация массива значениями от 0 до 255, которое происходит при каждом новом значении ключа (т.е. фактически при каждом новом пароле). Как же можно сделать ее более эффективной?

Выход есть - инициализировать массив не побайтно (256 команд), а, например, используя 32-битные регистры процессора, по 4 байта за 64 команды - и действительно, выигрыш по времени будет в 4 раза (конечно же, если массив M выровнен минимум по границе DWORD'a). А есть ли еще более "широкие" регистры, чтобы за одну команду "махом" записывать бОльшее кол-во байт? Регистры FPU отпадают, т.к. операции с ними выполняются очень долго, остаются, конечно же, MMX-регистры:

.DATA

qwInit DQ 0706050403020100h

qwAdd DQ 0808080808080808h

...

.CODE

mov edi,offset M+128

movq mm0,qword ptr [qwInit]

movq mm1,qword ptr [qwAdd]

movq [qword ptr edi-128],mm0

paddb mm0,mm1

movq [qword ptr edi-120],mm0

paddb mm0,mm1

movq [qword ptr edi-112],mm0

...

paddb mm0,mm1

movq [qword ptr edi+112],mm0

paddb mm0,mm1

movq [qword ptr edi+120],mm0

Чтобы не писать 31 одинаковый фрагмент кода, гораздо проще использовать зарезервированный макрос Ассемблера IRP, тогда последние строки кода можно заменить на следующую конструкцию:

IRP i,<-15,-14, ... ,14,15>

paddb mm0,mm1

   movq [qword ptr edi+(i*8)],mm0

ENDM

Итого получаем - на инициализацию массива из 256 байт затрачиваем 66 команд процессора, которые выполняются за ~35-40 тактов, т.к. команды PADDB и MOVQ выполняются синхронно.

Нетрудно догадаться, ЧТО наворотил бы на месте этого цикла любой компилятор С, если этот код писать не на Асме. ;)

У читателя, наверное, возник вопрос - почему мы инициализируем EDI не на начало массива M, а на его середину?

Просто дело в том, что при таком варианте программы дополнительное смещение к EDI будет приводить к увеличению длины команды MOVQ всего на один байт (знаковый диапазон -128...+127) и команда получает длину в 4 байта. А если, к примеру, прибавить к EDI +256, то смещение будет расширено до DWORD'a и длина команды увеличится до 7 байт. Использование же более коротких команд является предпочтительным, т.к. идет более "плотное" заполнение буфера предвыборки команд и более оптимальное их декодирование процессорами.

И еще - вдумчивый читатель скажет, что есть ведь еще более "широкие" XMM-регистры - те, которые используются в наборах команд SSE (которые, кстати, поддерживают и Athlon'ы) и SSE2 от Intel. Используя их, можно оперировать с памятью блоками по 16 байт за такт!

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



RC4 (2-я часть)


Теперь рассмотрим "перетасовку" байт в массиве M, используя входной ключ.

Здесь получается такая картина - на обработку одного байта массива M необходимо минимум 7 команд, покажем это на примере одной итерации:

xor eax,eax ;в AL будем хранить индекс A

mov ebp,offset Key

mov edi,offset M

...

add al,byte ptr[ebp+i] ;A += Key[i % 16]

mov dl,byte ptr [edi+i] ;Считываем M[i]

add al,dl ;A += M[i]

movzx esi,al

mov bl,byte ptr [edi+esi] ;Считываем M[A]

mov byte ptr [edi+esi],dl

mov byte ptr [edi+i],bl

...


Причем такая конструкция имеет ряд особенностей:

Использование команды MOVZX ESI,AL устраняет следующий конфликт на процессорах Intel: обращение к 32-битному регистру сразу после модификации его младшей (16- или 8-битной) части. В этом случае ко времени выполнения команды добавляется несколько тактов штрафа. Кстати, на процессорах от AMD таких штрафов нет. :)

Конфликты по чтению/записи в одну кэш-линейку процессора.

Известно, что при обращении к ячейке памяти процессор считывает из памяти (или кэша 2-го уровня) не одну эту ячейку, а целую строку (например, 32 байта), которую и размещает в кэше 1-го уровня. При этом ВСЯ эта строка помечается как доступная либо только для чтения, либо для записи. Поэтому, если прочитать байт по адресу X, а потом записать байт по адресу (X + 1), то несмотря на то, что байт по адресу (X + 1) уже в кэше(!), процессор после выполнения первой команды должен сначала "освободить" всю строку, а лишь потом снова ее загрузить, но уже для записи в нее, что, естественно, приводит к штрафам. Но, т.к. алгоритм формирует равномерное распределение байт, то такие конфликты возникают нечасто.

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

В итоге такая конструкция выполняется в среднем за 5 тактов, т.к. все эти команды простые и на процессорах P-II/III от Intel могут декодироваться всеми 3-мя декодерами. Таким образом, декодирование может происходить по 3 команды за такт, что частично компенсирует вышеописанные штрафы.



Стандартный алгоритм восстановления паролей к PWL-файлам


Считываем из исходного PWL-файла по смещению 0x24C - CheckSeed (DWORD).

-//- по смещению 0x252 - CryptoSign (16 байт).

-//- по смещению 0x262 - CheckSign (16 байт).

Формируем массив X (размером 64 байта) следующим образом:

0xFFFFFFFF (DWORD)

Логин в верхнем регистре

0x0 (1 байт)

CheckSeed (DWORD)

0x80 (1 байт)

0x0 (по адрес 0x37 включительно)

По адресу 0x38 записываем (0x48 + (длина логина << 3)) (DWORD)

0x0 (до конца массива)

Выполняем MD5 (массив X), получаем массив Cnt (16 байт), т.е. производим свертку логина.

Формируем массив Y (размером 64 байта) следующим образом:

Логин в верхнем регистре

0x0 (0x11 байт)

0x80 (1 байт)

0x0 (по адрес 0x37 включительно)

По адресу 0x38 записываем (0x88 + (длина логина << 3)) (DWORD)

0x0 (до конца массива)

Формируем массив Z (размером 64 байта) следующим образом:

Пароль

0x0 (1 байт)

Cnt (16 байт)

0x80 (1 байт)

0x0 (по адрес 0x37 включительно)

По адресу 0x38 записываем (0x88 + (длина пароля << 3)) (DWORD)

0x0 (до конца массива)

Выполняем MD5 (массив Z), получаем массив Key (16 байт), т.е. производим свертку пароля.

Выполняем RC4, используя в качестве ключа Key.

Копируем во временный буфер Temp (32 байта):

CryptoSign (16 байт)

CheckSign (16 байт)

Выполняем процедуру XorT (массив M, массив Temp), получаем модифицированный массив Temp.

Копируем первые 16 байт из массива Temp в буфер Y с адреса (длина логина + 1)

Выполняем MD5 (массив Y), получаем массив TempKey (16 байт).

Сравниваем 16 байт массива TempKey и вторые 16 байт из массива Temp и если они не равны, то инкремент пароля и возврат на пункт 7, иначе - пароль верный!


Внимание! А на "десерт" - самое вкусненькое ;) - то, что позволило в свое время программе PWLInside существенно увеличить скорость перебора и по этому параметру здорово "оторваться" от своих конкурентов.

Оказывается, для быстрой оценки - тот пароль или нет, можно пункты 10...14 не выполнять, а значит и не вызывать второй раз MD5, который (как уже было сказано) выполняется около 300 тактов, что дает прирост скорости еще на 20-25%!

Дело вот в чем.

Если внимательно присмотреться к процедуре декодирования ресурсов, то мы увидим, что с помощью массива M после пункта 9 стандартного алгоритма при проходе с правильным паролем мы декодируем:

начальный буфер Temp - это не что иное, как 32 байта исходного PWL-файла с адреса 0x252,

смещения (адреса) блоков ресурсов с адреса 0x272,

и, наконец, сами ресурсы.

Поэтому можно не выполнять операции над CryptoSign и CheckSign (для проверки правильности пароля), а просто проверить после XOR'a адрес первого блока ресурсов, который находится по адресу 0x272.

Если он лежит в диапазоне 0x292...(длина PWL-файла), то есть вероятность, что этот пароль верный! Для окончательной же проверки правильности пароля нужно выполнить пункты 10...14, т.к. только в этом случае (когда совпадут все 16 байт массива Temp), можно быть уверенным, что это именно верный пароль.

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

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

Поэтому код предварительной оценки пароля в упрощенном виде будет выглядеть так:

...

//Массив M перерабатывается с помощью RC4

...

byte t; //Временная ячейка

byte A = 0; //Здесь будем получать новый псевдослучайный индекс




WORD Offset = (WORD *)&lpFile[0x272]; //Зашифров. адрес 1-го блока ресурсов

WORD Len = XXX; //Длина исходного PWL-файла

//

for (int i = 1; i < 35; i++)

{

A += M[i]; // Вычисляем новый индекс для обмена байтами

   t = M[i]; 

   M[i] = M[A]; //Меняем местами i-й байт и байт по вычисленному индексу A

   M[A] = t;

   //

   t = M[i] + M[A]; //Вычисляем еще один индекс

   if (i == 33)

      ((byte *)&Offset)[0] ^= M[t]; //Декодируем 1-й байт адреса

   if (i == 34)

       ((byte *)&Offset)[1] ^= M[t]; //Декодируем 2-й байт адреса

}

//

if ((Offset > 0x291) && (Offset < Len))

{

   //Есть вероятность, что пароль верный,

   //делаем полную перепроверку по пунктам 10...14

}

else

{

   //Однозначно пароль неверный, переходим на новый пароль

}

Как видим, переработка массива M все равно остается, но(!) - первые 32 итерации мы НИЧЕГО не XOR'им, а декодируем ТОЛЬКО на 33 и 34 итерациях адрес блока ресурсов.

Таким образом, зачем нам делать пункты 10...14 и проверять 16 байт, когда можно выполнить "упрощенный" вариант процедуры XorT и проверить всего 2 байта! ;)

При всем моем уважении к Microsoft, однако, это еще одна их "дыра" в реализации качественных методов хранения паролей пользователей!

Итак, что мы получили в среднем:

~40 тактов на инициализацию массива M.

~300 тактов на первый проход MD5.

~1000 тактов на проход RC4.

~150 тактов на все остальное (формирование массива Z, инкремент пароля, "упрощенная" функция XorT, проверки и пр.)

В итоге мы получаем суммарное время обработки одного пароля около 1500 тактов

на всех типах процессоров, что приведены в начале статьи, кроме процессора Pentium 4. :(

Дело в том, что микроархитектура P4 по сравнению с P-II/III была существенно переработана - увеличено время выполнения команды (до 20 стадий), изменились размеры строк кэша данных и кода и еще ряд "усовершенствований", поэтому этот код (в особенности, реализация алгоритма RC4) для P4 не является оптимальным и в следующей версии PWLInside будет модифицирован. При этом на процессорах AMD, даже последних, таких проблем не возникает - на Athlon'e XP 1700+ (1466МГц) с ядром ThoroughBred программа исправно выдает около миллиона паролей в секунду. Вот так AMD делает аналоги процессоров Intel в чем-то лучше, чем сама Intel. :)


Восстановление паролей к PWL-файлам


Автор: (c), 2003

WWW: www.InsidePro.com

Версия документа: 1.0



или так называемые парольные кэши


PWL-файлы ( или так называемые парольные кэши Windows) - это файлы с именами пользователей компьютера и с расширениями *.PWL (к примеру, Master.PWL, Sales.PWL и пр.), которые находятся в директории Windows.
Это файлы, в которых хранятся различные аккаунты (т.е. сочетание логин/пароль) данного пользователя, т.е. пароли ко всем ресурсам, при первом подключении к которым в окне ввода пароля был включен флажок "Запомнить пароль". Таким образом, в нем хранятся пароли к "расшаренным" ресурсам сети, пароли на подключение к NetWare/NT-серверам, пароли на Dial-Up-соединения и пр.
Функция запоминания паролей в Windows реализована давно и была введена с "благой" целью - облегчение работы пользователей. И действительно - зачем вводить каждый раз при подключении к провайдеру пароль "q6Rf8UI24dq" :) , когда можно один раз ввести его с бумажки, а потом забыть про этот пароль вообще. Таким образом, Windows собирает все пароли пользователя, шифрует их с помощью логина (имени пользователя) и текущего пароля пользователя (т.е. того пароля, который вводится при загрузке Windows) и хранит в этом PWL-файле.
Естественно, все эти данные зашифрованы определенными алгоритмами, и для их дешифрования необходимо знать пароль пользователя - а это фактически пароль на вход в Windows. А так как людям свойственно забывать свои пароли, то подбор пароля, во-первых, позволяет его "вспомнить", а во-вторых, позволяет просмотреть список аккаунтов этого пользователя, которые Windows сохраняет в этом PWL-файле, например, там может быть и забытый пароль на подключение к провайдеру. ;)
В данной статье будут описаны те методы оптимизации при подборе паролей к PWL-файлам, которые были использованы при создании программы PWLInside и которые позволили занять программе лидирующее место по скорости работы среди аналогичных программ.
И сразу оговорюсь, что речь пойдет только о PWL-файлах операционных систем Windows'OSR2/98/ME, т.к. в PWL-файлах ОС Windows'3.11/95 методы шифрования гораздо проще и подбор пароля любой сложности - дело одного часа работы любой программы по восстановлению к ним паролей, в том числе и PWLInside.
Вся информация в тексте о времени выполнения фрагментов кода в тактах дана для следующих типов процессоров:
Intel Pentium MMX/II/III и все Celeron'ы из этих семейств.
AMD K6-II/III, все Duron'ы и Athlon'ы.
Такая информация дается как усредненное время выполнения на всех этих типах процессоров.
Примеры кода, приведенные ниже, даны в синтаксисе Microsoft Visual С++ v6.0 и MASM v7.0.

к концу наше описание. Надеюсь,


Вот и подошло к концу наше описание. Надеюсь, теперь по работе с PWL-файлами от Windows'OSR2/98/ME ни у кого не осталось "темных пятен". Видно, что данные алгоритмы можно было бы прооптимизировать еще больше с применением команд современных процессоров, но - операционные системы этих поколений уже уходят "в прошлое" - процент этих ОС и так уже невысокий, со временем снижается все больше и больше, и восстановление паролей к PWL-файлам уже не столь актуально, как несколько лет назад.
Хотя, возможно, стоит еще поработать в этой области. ;)
Сейчас основной процент ОС семейства Windows - это Windows'2000, Windows'XP, а теперь уже и Windows'2003. Так как у всех этих систем ядро другое (на базе NT), то и методы хранения, шифрования, а также восстановления ;) паролей пользователей тоже другие.
В них информация о паролях пользователей хранится в SAM-файлах, которые представляют собой ветку "HKEY_LOCAL_MACHINE\SAM" реестра Windows, и пароли зашифрованы другими алгоритмами, нежели в PWL-файлах.
Но(!) - несмотря на все попытки Microsoft создать максимально надежный механизм авторизации, все их методы почему-то имеют явные огрехи - это наглядно демонстрируют как методики, описанные выше, так и методы хранения и шифрования паролей в SAM-файлах.
В операционных системах Windows'NT, начиная с 6-го сервис-пака, Windows'2000, Windows'XP (а по всей видимости и в Windows'2003) применяется дополнительное шифрование хешэй пользователей (которые и так получены путем шифрования паролей определенными алгоритмами) с использованием утилиты Syskey.
Данный механизм успешно просуществовал несколько лет. Его многократно пытались взломать, но все попытки были безуспешны, пока этой проблемой не заинтересовались мы с Ocean'ом. ;)
И механизм был "взломан"! Это наглядно демонстрирует программа SAMInside.
Но про SAM-файлы и методы восстановления к ним паролей расскажу как-нибудь в другой раз. :)
Особую благодарность выражаю 'у, т.к. только наша с ним совместная деятельность в этой области привела к появлению на свет таких программ как PWLInside, SAMInside
и ряда других.
Удачи всем!

Здесь будем получать новый псевдослучайный


Эта часть RC4 (не описанная выше), которая декодирует необходимые данные с помощью массива M:

...

//Массив M перерабатывается с помощью RC4

...

byte t; //Временная ячейка

byte A = 0; // Здесь будем получать новый псевдослучайный индекс

for (byte i = 1; i < 33; i++)

{

A += M[i]; //Вычисляем новый индекс для обмена байтами

    t = M[i]; 

    M[i] = M[A]; //Меняем местами i-й байт и байт по вычисленному индексу A

    M[A] = t;

    //

    t = M[i] + M[A]; //Вычисляем еще один индекс

    Data[i - 1] ^= M[t]; //Декодируем 32 байта массива Data

}


Квантовая криптография, почти реальность


07.08.2003

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

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

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

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






Фотография Женевского озера, сделанная со спутника
Для распространения квантовой криптографии есть не только теоретические предпосылки, но и вполне реальная практическая потребность. Защищенность передачи данных зависит от возможности сохранить ключ в секрете от противника. Если говорить о синхронной схеме, то ее уязвимость в существенной мере зависит, например, от успешности деятельности разведки. Яркий пример тому — использование криптомашины Enigma немецкими военными во время Второй мировой войны. Как только английские спецслужбы добывали ключи, то, какой бы ухищренной ни была схема шифрования, она раскрывалась в считанные дни и при том весьма незамысловатыми по сегодняшним меркам средствами. Сохранность криптосистемы с публичными ключами, являющейся основой передачи данных в Internet, возможна только до тех пор, пока нет достаточной вычислительной мощности для ее раскрытия. Безопасность схемы, предложенной RSA, гарантируется факторизацией больших целых чисел. В предвидении неизбежного конца этой схемы информационному обществу требуется альтернативное решение. Пока ничего иного помимо квантовой криптографии не предложено. Ведущий специалист RSA Laboratories Бурт Калиски сказал по этому поводу: «Квантовое распределение ключей является основным сдвигом парадигмы в развитии криптографии. Способность обнаруживать прослушивание линии связи с абсолютной уверенностью в обнаружении вызывает восхищение. Сочетание квантовой и классической криптографии способно обеспечить реальную защищенность коммуникаций» [3]. Подобное признание дорогого стоит.

Квантовая криптография еще не вышла на уровень практического использования, но приблизилась к нему. В мире существует несколько организаций, где ведутся активные исследования в области квантовой криптографии. Среди них IBM, GAP-Optique, Mitsubishi, Toshiba, Национальная лаборатория в Лос-Аламосе, Калифорнийский технологический институт (Caltech), а также молодая компания MagiQ и холдинг QinetiQ, поддерживаемый британским министерством обороны. Диапазон участников — от крупнейших мировых вендоров до небольших начинающих компаний — свидетельствует о начальном периоде в формировании рыночного сегмента, когда в нем на равных могут участвовать и те, и другие.



В IBM продолжаются фундаментальные исследования в области квантовых вычислений [6], начатые группой во главе с Чарльзом Беннеттом, который в 1984 году вместе с Жилем Броссардом предложил простую схему защищенного квантового распределения ключей. Схема получила известность под названием «протокол BB84». О практических достижениях IBM в квантовой криптографии в последние годы известно немногое; эти работы ведутся без излишней рекламы.

Особое место занимает созданная на основе Женевского университета компания GAP (Group of Applied Phisics) Optique. Компания с европейскими академическими корнями сохраняет традиции научных публикаций; для тех, кто серьезно заинтересуется квантовой криптографией, несомненно, будут интересны две статьи авторов из GAP [4, 5]. О том, что квантовая криптография выходит из лабораторного состояния можно судить хотя бы потому, что в 2003 году о ней пишет и бизнес-пресса (в частности, New York Times), и популярные издания (в том числе, National Geographic). Под руководством Николаса Гисина GAP-Optique совмещает теоретические исследования с практической деятельностью. Компании впервые удалось передать ключ на расстояние 67 километров из Женевы в Лозанну, воспользовавшись почти промышленным образцом аппаратуры [7].

Этот рекорд был побит компанией Mitsubishi Electric, которой удалось передать квантовый ключ на расстояние 87 километров; скорости еще очень невелики, всего 7,2 бит в секунду.

Исследования в области квантовой криптографии ведутся и в европейском исследовательском центре Toshiba Research Europe, расположенном в Кембридже. Отчасти они спонсируются английским правительством; в них участвуют сотрудники Кембриджского университета и Империал-колледжа в Лондоне. Сейчас им удается передавать фотоны на расстояние до 100 километров; есть надежда, что через три года будут выпущены коммерческие продукты.

Компания MagiQ Technologies была основана в 1999 году на средства пула крупных финансовых институтов. Помимо собственных сотрудников с ней сотрудничают научные работники из целого ряда университетов США, Канады, Великобритании и Германии. До последнего времени вела скрытное существование и заявила о себе после того, как сочла себя готовой к объявлению готовящегося коммерческого продукта, но и после него ясного представления о нем пока нет. В качестве кодового имени для средства для распределения ключей (quantum key distribution, QKD) избрано имя племени индейцев навахо. Известно, что во время Второй мировой войны язык навахо использовался для передачи особо секретных сообщений: лиц, знавших его за пределами Соединенных Штатов попросту не было. Navajo способен в реальном времени генерировать и распространять ключи средствами квантовых технологий, он должен обеспечивать защиту от внутренних и внешних злоумышленников. По сообщениям, Navajo находится в состоянии бета-тестирования и станет коммерчески доступным в конце года. Вице-президентом MagiQ является Алексей Трифонов, наш соотечественник, защитивший докторскую диссертацию Санкт-Петербургском университете в 2000 году.



QinetiQ — своего рода исследовательская корпорация, поддерживаемая министерством обороны Великобритании. Она появилась на свет в результате деления британского агентства DERA (Defence Evaluation and Research Agency) в 2001 году, вобрав в себя все неядерные оборонные исследования. В силу этой специфики в QinetiQ не особенно расположены делиться своими достижениями.

Литература

А. Корольков, Квантовая криптография, или как свет формирует ключи шифрования. Компьютер в школе, № 7, 1999. В. Красавин, Квантовая криптография, www.submarine.ru. MagiQ Technologies offers different kind of Grid Security. Grid Today, vol. 1, no. 23, November 2002. I. Marcikic, H. de Riedmatten, W. Tittel, H. Zbinden, N. Gisin, Long-distance teleportation of qubits at telecommunication wavelengths. http://www.gap-optique.unige.ch/I&Hnature.pdf

Nicolas Gisin, Gregoire Ribordy, Wolfgang Tittel, Hugo Zbinden, Quantum cryptography. http://www.gap-optique.unige.ch/Publications/Pdf/QC.pdf

Brad Huntting, David Mertz, Introduction to Quantum Computing. A guide to solving intractable problems simply. http://www-106.ibm.com/developerworks/linux/library/l-quant.html

D Stucki, N Gisin, O Guinnard, G Ribordy, H Zbinden, Quantum key distribution over 67 km with a plug&play system. http://www.gapoptic.unige.ch/Publications/Pdf/njp-2002.pdf


Квантовая телепортация


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

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



Экспериментальная реализация


Не так давно метод квантового распространения ключа воспринимался как научная фантастика. Но в 1989 г. в Уотсоновском исследовательском центре IBM Чарльзом Беннетом, Джилом Брасардом и их студентами была построена первая система, реализующая протокол ВВ84. Она позволяла «Алисе» и «Бобу» обмениваться секретным ключом со скоростью 10 бит/с на расстоянии 30 см. Это был небольшой шаг для Алисы и Боба, но большой шаг в развитии квантовой криптографии!

Позже эту идею реализовала Национальная лаборатория в Лос-Аламосе в эксперименте по распространению ключа в оптоволоконном кабеле на расстояние 48 км. В качестве среды передачи сигнала использовался и открытый воздух, расстояние передачи, в котором составляло около 1 км. Разработан план эксперимента по передаче квантового сигнала на спутник. Если этот эксперимент увенчается успехом, можно надеяться, что технология вскоре станет широко доступной.

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


Сведения об авторах:

Виноградова Лилия Степановна, ассистент Украинского государственного химико-технологического университета

Виноградов Константин Георгиевич, ст. преподаватель

document.write('');

Новости мира IT:

02.08 - 02.08 - 02.08 - 02.08 - 02.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 01.08 - 31.07 - 31.07 - 31.07 - 31.07 - 31.07 -

Архив новостей

Последние комментарии:

 (66)

2 Август, 17:53

 (19)

2 Август, 17:51

 (34)

2 Август, 15:40

 (42)

2 Август, 15:35

 (1)

2 Август, 14:54

 (3)

2 Август, 14:34

 (3)

2 Август, 14:15



Квантовое распространение ключа


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

Идея использовать квантовые объекты для защиты информации от подделки и несанкционированного доступа впервые была высказана Стефаном Вейснером (Stephen Weisner) в 1970 г. Спустя 10 лет Беннет и Брассард, которые были знакомы с работой Вейснера, предложили использовать квантовые объекты для передачи секретного ключа. В 1984 г. они опубликовали статью, в которой описывался протокол квантового распространения ключа ВВ84.

Носителями информации в протоколе ВВ84 являются фотоны, поляризованные под углами 0, 45, 90, 135 градусов. В соответствии с законами квантовой физики, с помощью измерения можно различить лишь два ортогональных состояния: если известно, что фотон поляризован либо вертикально, либо горизонтально, то путем измерения, можно установить — как именно; то же самое можно утверждать относительно поляризации под углами 45 и 135 градусв. Однако с достоверностью отличить вертикально поляризованный фотон от фотона, поляризованного под углом 45?, невозможно.

Эти особенности поведения квантовых объектов легли в основу протокола квантового распространения ключа. Чтобы обменяться ключом, Алиса и Боб предпринимают следующие действия:

Алиса посылает Бобу фотон в одном из поляризованных состояний (0, 45, 90, 135 градусов) и записывает угол поляризации. Отсчет углов ведется от направления "вертикально вверх" по часовой стрелке. В реальных же системах перед процессом передачи ключа оборудование специально юстируется для обеспечения одинакового режима отсчета на приемнике и передатчике (причем эту юстировку приходится проводить периодически в процессе передачи), а "пространственное расположение" начала отсчета угла -- несущественно.

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

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

Алиса по общедоступному каналу связи сообщает Бобу, какие анализаторы он выбрал правильно. Те фотоны, для которых Боб неверно выбрал анализатор, отбрасываются.

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



Значения разрядов ключа получаются следующим


Последовательность фотонов Алисы |    /    /    —   \    |     |   —  —
Последовательность анализаторов Боба
 +  x  +  +   x  x  x   +   x Результаты измерений Боба  0  0  1  1   1  0  1   1   0 Анализаторы выбраны верно  +  +    +   +       +   Ключ  0  0    1   1       1 Рис. 1. Принцип действия протокола ВВ84.

Условные обозначения:

Поляризация фотонов: | - вертикальная, — - горизонтальная, / - под угром 45, \ - под углом 135.

Анализаторы: + - прямоугольный, х - диагональный

Значения разрядов ключа получаются следующим образом: в случае вертикально-горизонтальной ("прямоугольной") поляризации вертикально-поляризованный фотон означает 0, горизонтально-поляризованный — 1; в случае диагональной поляризации фотон, поляризованный под углом 45 градусов -- 0, 135 градусов -- 1.

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

При изучении рисунка, на первый взгляд странно выглядят результаты измерения Боба (например, в 3-м столбце). Но, если анализатор выбран Бобом неверно, то результаты являются случайными (50/50), поэтому там вполне мог бы быть и 0 — этот результат все равно будет отброшен при формировании ключа.

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

1-й столбец — Алиса послала вертикально-поляризованный фотон, Боб выбрал "прямоугольный" анализатор и, следовательно, смог получить правильный результат — 0. Этот результат вошел в ключ.

2-й столбец — Алиса посылает фотон, поляризованный под углом 45 градусов, Боб выбирает диагональный анализатор и может получить верный результат — 0. Этот результат также входит в ключ.

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

4-й столбец — Алиса посылает горизонтально-поляризованный фотон, Боб выбирает верный анализатор и получает результат 1, который войдет в ключ.

5-й столбец — Алиса посылает фотон, поляризованный под углом 135 градусов, Боб выбирает правильный, диагональный анализатор и получает результат 1, который войдет в ключ.

6-й и 7-й столбцы — Алиса дважды подряд (это случайно!) посылает вертикально-поляризованный фотон, но Боб оба раза (это тоже случайно) выбирает неверный, диагональный анализатор, в результате чего результаты его измерений — случайны, что и представлено на рисунке: в 6-м столбце Боб получил 0, а в 7-м — 1. Оба эти результата при формировании ключа будут отброшены из-за того, что был выбран неверный анализатор.

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

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

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

Если Алиса и Боб не собираются использовать полученный ими ключ сразу, то перед ними возникает новая проблема, — как сохранить ключ в секрете? В 1991 г. Артур Экерт (Artur Ekert) предложил протокол, позволяющий решить обе эти проблемы — распространения и хранения ключа. Протокол Экерта основан на эффекте сцепления квантовых частиц. Сцепленные частицы ведут себя необычном образом: если произвести измерение одной из них, то другая (на каком бы расстоянии она ни находилась) обязательно «перейдет» в состояние, противоположное состоянию первой частицы. Парадокс заключается в том, что информация о состоянии частицы передается со скоростью, превышающей скорость света. Тем не менее, это явление демонстрируется физиками экспериментально и может быть использовано для шифрования информации.

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


Введение в криптографию


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

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

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

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

Если используется постоянный закрытый ключ, то расшифровка сообщения зависит от вычислительной мощности системы и времени. В США, например, для шифрования используется стандарт DES (Data Encryption Standard), разработанный в 1977 году. Он основан на 56-битном ключе, при помощи которого можно закодировать 64 бит информации. На этом стандарте основывается защита банковских транзакций, паролей Unix-систем и других секретных данных. Поскольку длина ключа меньше, чем длина кодируемого сообщения, то механизм защиты не является абсолютно надежным. Если попытаться угадать ключ методом проб и ошибок, нужно перебрать 256 всевозможных значений. И хотя этот объем вычислений очень велик, в настоящее время уже имеются данные о возможности взлома подобных систем. Рекордное время составляет 22 часа 15 минут при распределенной обработке информации в компьютерной сети ().

Теория шифрования с использованием открытого ключа была создана Уэтфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в 1976 г. В этой системе Боб имеет общедоступный код для шифрования и закрытый код для расшифровки сообщений. Криптосистемы с открытым ключом основываются на так называемых односторонних функциях:
по некоторому x легко вычислить функцию f(x), но зная f(x) трудно вычислить х.

Первый алгоритм, основанный на теории Диффи-Хеллмана, был предложен Роном Райвестом (Ron Rivest), Эди Шамиром (Adi Shamir) и Леонардом Эдлманом (Leonard Adleman) в 1977 г (RSA-алгоритм). Он основан на разложении простого числа на множители. Известно, что вычислить произведение двух простых чисел легко. В то же время, обратная задача – разложение числа на простые множители, достаточно трудоемка, поскольку время вычислений экспоненциально возрастает при увеличении количества битов в исходном числе. Хотя в настоящее время не опубликованы быстрые алгоритмы решения задачи разложения числа на простые множители, нельзя утверждать, что они не существуют вовсе. Кроме того, вычислительная мощность компьютерных систем постоянно возрастает, поэтому сложность задачи не означает ее неразрешимость. Так, компания RSA, основанная вышеперечисленными авторами алгоритма, предлагает всем желающим разложить на простые множители представленные ею числа. Один из последних отчетов компании посвящен разложению числа, состоящего из 155 цифр. Эта задача требует 35,7 процессорных года, что примерно эквивалентно 8000 MIPS-лет3; в реальном времени потребовалось 3,7 месяца благодаря распределенной обработке информации в компьютерной сети.

Таким образом, на настоящий момент единственно надежным методом шифрования является метод «одноразового блокнота», поскольку доказана его безусловная секретность, то есть секретность по отношению к шпиону, который обладает неограниченными временем и вычислительной мощностью. На пути к достижению такого уровня секретности, стоит проблема распространения ключа: Алиса и Боб должны обменяться ключом, сохранив его в полном секрете. Одним из ее решений является разработанный Чарльзом Беннетом (Charles Bennett) и Джилом Брассардом (Gilles Brassard) протокол квантового распространения ключа (quantum key distribution).