Хеширование

Общие сведения о криптографии

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

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

Криптография используется для достижения следующих целей:

· Конфиденциальность: защита данных или личной информации пользователя от несанкционированного просмотра.

· Целостность данных: защита данных от несанкционированного изменения.

· Проверка подлинности: проверка того, что данные исходят действительно от конкретного лица.

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

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

Определение схемы шифрования.

Схема шифрования - это совокупность трёх процессов (алгоритмов):

1) генерации (создания) ключа;

2) зашифрования;

3) расшифрования.

Алгоритм обмена ключами Диффи-Хеллмана.

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

Алгоритм Диффи-Хеллмана работает следующим образом.

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

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

3. P1 выбирает случайное число i и вычисляет I = aⁱ mod b. P1 передает I абоненту P2.

4. P2 выбирает случайное число j и вычисляет J = a^j mod b. P2 передает J абоненту P1.

5. P1 вычисляет k1 = Jⁱ mod b.

6. P2 вычисляет k2 = I^j mod b.

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

Алгоритм RSA.

В 1978 г. Рон Ривест, Ади Шамир и Лен Адельман разработали алгоритм шифрования Rivest-Shamir-Adleman (RSA) с открытым ключом. В отличие от алгоритма Диффи-Хеллмана RSA может использоваться для шифрования и дешифрования.

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

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

Генерация ключей RSA.

Чтобы сгенерировать ключевую пару RSA, выполняются следующие шаги:

1. Выбираются два простых числа p и q и содержатся в секрете.

2. Вычисляется n = p*q.

3. Вычисляется ф(n) = (p - 1)(q - 1).

4. Выбирается такое e, чтобы оно было взаимно простым по отношению к ф(n).

5. Определяется такое d, чтобы (d)(e) = 1 mod ф(n) и d < ф(n).

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

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

Обычно алгоритмы шифрования с закрытым ключом, называемые блочными шифрами, используются для шифрования целого блока данных за один раз. Блочные шифры (такие как RC2, DES, TrippleDES и Rijndael) преобразуют входной блок данных длиной в n байтов в выходной блок зашифрованных данных. Если вы хотите зашифровать или расшифровать последовательность байтов, вам следует делать это блок за блоком. Поскольку n достаточно мало (n = 8 байт для RC2, DES и TripleDES; n = 16 [по умолчанию], n = 24 или n = 32 байта для Rijndael), данные большей длины, чем n, должны шифроваться блоками, один блок за раз.

хеширование функция коллизия шифрование открытый ключ

Алгоритм шифрования с секретным ключом.

М - сообщение;

Н(М) - хэширование сообщения;

Е - электронная цифровая подпись;

К - секретный ключ;

МЕ - не зашифрованное сообщение с ЭЦП;

МЕК - зашифрованное сообщение с ЭЦП;

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

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

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

Предположим, что Алиса и Боб являются двумя сторонами, которые хотят осуществлять связь по незащищенному каналу; они могли бы воспользоваться шифрованием с закрытым ключом, как это описано ниже. Алиса и Боб соглашаются использовать некоторый определенный алгоритм (например, Rijndael) с определенным ключом и вектором инициализации (IV). Алиса пишет сообщение и создает сетевой поток, через который можно отправить это сообщение. Затем она шифрует текст с помощью ключа и вектора инициализации и пересылает зашифрованное сообщение через Интернет. Она не высылает Бобу ключ и вектор инициализации. Боб принимает зашифрованный текст и осуществляет дешифровку, используя ранее согласованные ключ и вектор инициализации. Если происходит перехват передаваемых данных, злоумышленник не может восстановить исходное сообщение, так как ему не известны ключ и вектор инициализации. При использовании такого сценария ключ должен держаться в секрете, но вектор инициализации не обязательно должен быть секретным. В более реалистичном случае либо Алиса, либо Боб создает закрытый ключ и использует шифрование с открытым ключом (асимметричное) для передачи другой стороне закрытого (симметричного) ключа. Дополнительные сведения см. в разделе «Шифрование с открытым ключом».

NET. Framework предоставляет следующие классы, которые реализуют алгоритмы шифрования с закрытым ключом:

· DESCryptoServiceProvider

· RC2CryptoServiceProvider

· RijndaelManaged

· TripleDESCryptoServiceProvider

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

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

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

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

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

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

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

NET. Framework предоставляет следующие классы, которые реализуют алгоритмы шифрования с открытым ключом:

· DSACryptoServiceProvider

· RSACryptoServiceProvider

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

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

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

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

NET Framework предоставляет следующие классы, которые реализуют алгоритмы цифровой подписи:

· DSACryptoServiceProvider

· RSACryptoServiceProvider

Хеш-коды

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

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

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

NET. Framework предоставляет следующие классы, которые реализуют алгоритмы цифровой подписи:

· HMACSHA1

· MACTripleDES

· RC2CryptoServiceProvider

· SHA1Managed

· SHA256Managed

· SHA256Managed

· SHA256Managed

Генерация случайных чисел

Процесс генерации случайных чисел является составной частью многих криптографических операций. Например, криптографические ключи должны выбираться настолько случайно, насколько это возможно, чтобы было фактически невозможно воспроизвести их значения. Криптографические генераторы случайных чисел должны выдавать данные, которые невозможно численно предугадать с вероятностью выше p < 0,5; это означает, что любой метод предсказания очередного выходного бита должен действовать не лучше, чем простое случайное угадывание. Классы NET. Framework используют генераторы случайных чисел для создания криптографических ключей.

RNGCryptoServiceProvider реализует алгоритм генератора случайных чисел.

Использование генератора псевдослучайных чисел

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

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

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

Криптография и защита информации

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

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

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

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

Базовая терминология

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

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

Криптография - это наука о том, как обеспечить секретность сообщения.

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

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

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

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

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

Классификация криптоалгоритмов

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

Основной схемой классификации всех криптоалгоритмов является следующая:

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

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

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

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

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

В зависимости от характера воздействий, производимых над данными, алгоритмы подразделяются на:

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

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

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

В зависимости от размера блока информации криптоалгоритмы делятся на:

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

2. Блочные шифры. Единицей кодирования является блок из нескольких байтов (в настоящее время 4-32). Результат кодирования зависит от всех исходных байтов этого блока. Схема применяется при пакетной передаче информации и кодировании файлов.

Рассмотрим общую схему симметричной, или традиционной, криптографии.

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

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

Незашифрованное сообщение будем обозначать P или M, от слов plaintext и message. Зашифрованное сообщение будем обозначать С, от слова ciphertext.

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

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

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

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

Стойкость алгоритмов шифрования

Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования.

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

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

Если Х - это исходное сообщение и K - криптографический ключ, то зашифрованный передаваемый текст можно записать в виде Y = EK[X].

Получатель, используя тот же ключ, расшифровывает сообщение X = DK[Y].

Противник, не имея доступа к K и Х , должен попытаться узнать Х, K или и то, и другое.

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

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

* Табличная подстановка, при которой группа битов отображается в другую группу битов. Это так называемые S-box ;

* Перемещение, с помощью которого биты сообщения переупорядочиваются;

* Операция сложения по модулю 2, обозначаемая XOR или;

* Операция сложения по модулю 232 или по модулю 216;

* Циклический сдвиг на некоторое число битов.

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

Области применения криптоалгоритмов

Стандартный алгоритм шифрования должен быть применим во многих приложениях:

* Шифрование данных. Алгоритм должен быть эффективен при шифровании файлов данных или большого потока данных.

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

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

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

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

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

* Процессоры среднего размера. Алгоритм должен работать на микроконтроллерах и других процессорах среднего размера;

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

* Алгоритм должен быть простым для написания кода, чтобы минимизировать вероятность программных ошибок;

* Алгоритм должен иметь плоское пространство ключей и допускать любую случайную строку битов нужной длины в качестве возможного ключа. Наличие слабых ключей нежелательно;

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

* Все операции с данными должны осуществляться над блоками, кратными байту или 32-битному слову.

Заключение

Хеширование, которое зародилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных. Появились новые методы хеширования, новые модификации алгоритмов, написанных ранее. По мнению Дональда Кнута ([3], стр. 586), наиболее важным открытием в области хеширования со времен 70 годов, вероятно, является линейное хеширование Витольда Литвина [18]. Линейное хеширование, которое не имеет ничего общего с классической технологией линейной адресации, что позволяет многим хеш-адресам расти и выступать в поле вставляемых и удаляемых элементов. Линейное хеширование может также использоваться для огромных баз данных, распределенных между разными узлами в сети.

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

Список литературы:

1. Hellerman H., Digital Computer System Principles. McGraw-Hill, 1967.

2. Ершов А.П., Избранные труды., Новосибирск: «Наука», 1994.

3. Кнут Д., Искусство программирования, т.3. М.: Вильямс, 2000.

4. Peterson W.W., Addressing for Random-Access Storage // IBM Journal of Research and Development, 1957. V.1, N2. Р.130--146.

5. Morris R., Scatter Storage Techniques // Communications of the ACM,

1968. V.11, N1. Р.38--44.

6. Buchholz W., IBM Systems J., 2 (1963), 86-111

7. http://www.optim.ru/cs/2000/4/bintree_htm/hash.asp

8. Fundamenta Math. 46 (1958), 187-189

9. http://www.cs.sfu.ca/CC/354/zaiane/material/notes/Chapter11/node20.html

10. http://www.ecst.csuchico.edu/~melody/courses/csci151_live/Dynamic_hash_no tes.htm

11. http://planetmath.org/encyclopedia/Hashing.html

12. http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html

13. R. Cichelli, Minimal Perfect Hashing Made Simple, Comm. ACM Vol. 23 No. 1, Jan. 1980.

14. http://www2.ics.hawaii.edu/~richardy/project/hash/applet.html

15. http://www.cs.uic.edu/~i201/HashingAns.pdf

16. T. Gunji, E. Goto, J. Information Proc., 3 (1980), 1-12

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

18. Litwin W., Proc. 6th International Conf. on Very Large Databases (1980), 212-223

19. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 2001

20. Вирт Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.

21. Керниган Б., Пайк Р., Практика программирования, СПб.: Невский диалект, 2001.

22. Шень А., Программирование: теоремы и задачи. М.: МЦНМО, 1995.

Размещено на Allbest.ru

...