Криптография. Алгоритмы с ассиметричным ключом. Хеш-функции

Проблема распространения ключей была решена т.н. шифрованием открытым, или асимметричным, ключом, концепция которого была представлена Уитфилдом Диффи и Мартином Хеллманом в 1975 году.

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

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

Главный плюс асимметричного шифрования в том, что оно позволяет людям, не имеющим существующей договорённости о безопасности, отправлять зашифрованные сообщения. Необходимость отправителю и реципиенту обмениваться тайными ключами по какому-либо защищённому каналу полностью отпала. Все коммуникации затрагивают только общественные ключи и ни один частный не должен быть передан. Примеры криптосистем с открытым ключом это Elgamal (названная в честь изобретателя, Тахира Эльгамаля), RSA (названная в честь изобретателей: Рона Райвеста, Ади Шамира и Леонарда Адлмана), Diffie-Hellman (названная, правильно, в честь её создателей) и DSA, Digital Signature Algorithm (изобретённый Дэвидом Кравицом).

Хэш функции

У однонаправленной хэш-функинн может быть множество имен: функция сжатия, функция сокращения, contraction function, краткое изложение, характерный признак, криптографическая контрольная сумма, код целостности сообщения (message integrity check, MIC) и код обнаружения манипуляции (manipulation detection code, MDC). Как бы она не называлась эта функция является центральной в современной криптографии. Однонаправленные хэш-функции - это другая часть фундамента многих протоколов.

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

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

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

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

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