Криптография

Криптогра́фия (от крипто... и ...графия), 1) наука о методах преобразования информации для её защиты при передаче по незащищённым каналам связи и о способах практической реализации этих методов.

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

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

Криптографические методы широко используются в различных системах защиты информации. Для решения задач разработки шифров и методов дешифрования в разное время привлекались многие учёные, среди которых были математики, например Ф. Виет, Х. Гольдбах, Н. Винер, А. Тьюринг. Основы современной теоретической криптографии и теории информации были заложены в годы Второй мировой войны К. Шенноном. Он предложил рассматривать шифр как отображение прямого произведения множества ${\displaystyle Z}$ всех потенциально возможных сообщений и множества ${\displaystyle K}$ ключей в множество ${\displaystyle E}$ зашифрованных текстов; при любом фиксированном ключе это отображение ${\displaystyle Z}$ в ${\displaystyle E}$ должно быть обратимым. Шеннон доказал, что шифр может быть совершенным (т. е. принципиально не дешифруемым) только в случае, когда число различных ключей не меньше числа возможных сообщений, и что если это условие выполнено, то можно построить совершенный шифр. Примером совершенного шифра является шифр гаммирования. Если исходное сообщение представлено в виде двоичной последовательности ${\displaystyle m_{1},m_{2},\ldots ,m_{T}}$, состоящей из нулей и единиц, то в качестве ключа нужно случайно и равновероятно выбрать двоичную последовательность ${\displaystyle \gamma _{1},\gamma _{2},...,\gamma _{T}}$ из множества всех ${\displaystyle 2^{T}}$ двоичных последовательностей длины ${\displaystyle T}$; тогда совершенным будет шифр, переводящий ${\displaystyle m_{1},m_{2},\ldots ,m_{T}}$ в ${\displaystyle m_{1}+\gamma _{1},m_{2}+\gamma _{2},\ldots ,m_{T}+\gamma _{T}}$ (все сложения проводятся по модулю 2), и получатель, зная ${\displaystyle \gamma _{1},\gamma _{2},...,\gamma _{T}}$, может восстановить исходное сообщение, вычислив

${\displaystyle (m_{1}+\gamma _{1})+\gamma _{1}=m_{1},(m_{2}+\gamma _{2})+\gamma _{2}=m_{2},\ldots ,(m_{T}+\gamma _{T})+\gamma _{T}=m_{T}}$.

При этом отправитель и получатель должны заранее согласовать значение ключа ${\displaystyle \gamma _{1},\gamma _{2},...,\gamma _{T}}$, пользуясь каналом связи, который заведомо защищён от всех посторонних (например, переслать ключ в запечатанном конверте с надёжным курьером). Если посторонний, у которого нет никакой информации о ${\displaystyle \gamma _{1},\gamma _{2},...,\gamma _{T}}$, попытается восстановить исходное сообщение, перебирая все возможные варианты последовательности ${\displaystyle \gamma _{1},\gamma _{2},...,\gamma _{T}}$, то он получит все возможные двоичные последовательности длины ${\displaystyle T}$, в т. ч. и ${\displaystyle m_{1},m_{2},\ldots ,m_{T}}$, но у него не будет оснований выделить сообщение ${\displaystyle m_{1},m_{2},\ldots ,m_{T}}$ из множества всех остальных комбинаций ${\displaystyle T}$ двоичных знаков. Неудобство указанного шифра связано с необходимостью использования защищённого канала связи для передачи ключей, суммарная длина которых не меньше суммарной длины будущих секретных сообщений. Поэтому на практике используются шифры, в которых объём ключей существенно меньше объёма передаваемых секретных сообщений. Такие шифры не могут быть совершенными; вообще говоря, зашифрованные с их помощью сообщения можно дешифровывать с помощью полного перебора всех возможных ключей. Под стойкостью шифра обычно понимают время работы наилучшего алгоритма вычисления секретного ключа по известным парам исходных и зашифрованных сообщений и известным правилам зашифрования. Однако существующие методы позволяют получать только верхние оценки стойкости шифров (а именно, оценки времени работы конкретных алгоритмов вычисления ключа).

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

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

Современные шифраторы делятся на два класса: поточные и блочные. Поточные шифраторы представляют собой электронные устройства с ячейками памяти и специализированными процессорами; они вырабатывают последовательности некоторых знаков и используют их вместо случайной равновероятной последовательности в шифре гаммирования. Последовательность, вырабатываемая потоковым шифратором, однозначно определяется ключевыми параметрами, задающими начальные состояния ячеек памяти конечного автомата и выбор тех или иных вариантов работы процессоров. Это позволяет отправителю и получателю, согласовавшим заранее значения ключевых параметров, вырабатывать одну и ту же последовательность ${\displaystyle \gamma _{1},\gamma _{2},...,\gamma _{T}}$. Блочные шифраторы разбивают исходное сообщение, представленное в виде двоичной последовательности, на блоки одинакового размера (например, по 64, 128 или более битов), вычисляют образы этих блоков при взаимно однозначном отображении, конкретный вид которого зависит от секретного ключа, и объединяют образы блоков в зашифрованное сообщение. Получатель, используя тот же секретный ключ, что и отправитель, разбивает полученное сообщение на блоки и, применяя к ним обратное отображение, восстанавливает исходное сообщение.

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

В схеме шифрования с открытым ключом, предложенной в 1976 г. американскими учёными У. Диффи и М. Хеллманом, используются семейства ${\displaystyle \left\{E_{e},e\in M\right\}}$ и ${\displaystyle \left\{D_{d},d\in M\right\}}$ отображений зашифрования и расшифрования соответственно, действующие на конечном множестве ${\displaystyle K}$ (например, на множестве ключей шифратора) и обладающие следующими свойствами:

а) для каждого ${\displaystyle e\in M}$ существует такое ${\displaystyle d\in M}$, что ${\displaystyle E_{e}}$ и ${\displaystyle D_{d}}$ – взаимно обратные отображения;

б) задача нахождения значения ${\displaystyle k}$ из множества ${\displaystyle K}$ по отображению ${\displaystyle E_{e}}$ и значению ${\displaystyle z=E_{e}(k)}$ вычислительно неразрешима за заданное время;

в) существуют не очень сложные способы вычисления значений отображений ${\displaystyle E_{e}}$ и ${\displaystyle D_{d}}$ и построения пар взаимно обратных отображений ${\displaystyle (E_{e},D_{d})}$.

Если такие семейства выбраны, то любой абонент ${\displaystyle A}$ может выработать пару взаимно обратных отображений ${\displaystyle (E_{e},D_{d})}$, сообщить всем желающим правило вычисления отображения ${\displaystyle E_{e}}$ (открытый ключ), а правило вычисления ${\displaystyle D_{d}}$ (секретный ключ) держать в секрете. Любой абонент ${\displaystyle B}$, чтобы передать абоненту ${\displaystyle A}$ значение ${\displaystyle k}$ в виде, защищённом от посторонних, может передать абоненту ${\displaystyle A}$ по общедоступному каналу связи значение ${\displaystyle z=E_{e}(k)}$. Тогда абонент ${\displaystyle A}$, знающий отображение ${\displaystyle D_{d}}$, сможет восстановить ${\displaystyle k}$ по ${\displaystyle z}$, а посторонние, не знающие ${\displaystyle D_{d}}$ и не имеющие возможности построить ${\displaystyle D_{d}}$ по ${\displaystyle E_{e}}$, не смогут этого сделать. Т. к. математически строго обоснованные примеры отображений, удовлетворяющих условию б), ещё не найдены, У. Диффи и М. Хеллман предложили использовать для построения систем шифрования с открытым ключом алгоритмические задачи, считающиеся вычислительно сложными. Ныне предложен ряд систем шифрования с открытым ключом, основанных на сложности решения задач типа разложения натуральных чисел на простые множители, вычисления квадратного корня в мультипликативной группе вычетов по составному модулю, дискретного логарифмирования [т. е. решения сравнения вида ${\displaystyle ax\equiv b\,(\operatorname {mod} n)}$, где ${\displaystyle n}$ – достаточно большое натуральное число], аналогичных задач для групп эллиптических кривых над конечными полями и некоторых других.

Потребности коммерческих и финансовых организаций, а также особенности электронных средств связи, задачи защиты электронных баз данных и т. п. стимулировали разработку ряда новых направлений использования криптографических методов: защиты информации в компьютерных сетях, т. н. электронной подписи, идентификации пользователя (как при деловой переписке, так и при использовании электронных кредитных карт), методов разделения секрета (таких способов разделения секретной информации между ${\displaystyle n}$ лицами, которые не позволяют получить никакой информации о секрете, если одновременно не соберётся хотя бы ${\displaystyle k}$ лиц из этой группы) и т. п.

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

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

2) Тайнопись, система изменения письма с целью сделать текст непонятным для непосвящённых.

3) Раздел палеографии, изучающий графику систем тайнописи.