Учебное пособие Москва 200 8 удк 004. 738 Ббк 32. 973. 202
1 чел. помогло. вернуться в начало
| скачать ^ Функцией хэширования или, как еще иногда говорят, хэш-функцией, называется некоторое преобразование исходного текста в последовательность фиксированной длины. Такое преобразование должно обладать следующими свойствами:
Основные области применения функций хэширования:
В Российской Федерации принят и действует отечественный стандарт на функцию хэширования ГОСТ Р 34.11-94. Термин «открытые ключи» появился в криптографии после того, как два американских ученых Мартин Хеллман (Martin Hellman) и Уитфилд Диффи (Whitfield Diffie) опубликовали свою знаменитую статью «Новые направления в криптографии» в 1976 году (Diffie, Hellman, 1976). Диффи и Хеллман сформулировали оосновные принципы построения криптографических систем с открытыми ключами:
В основе алгоритмов с открытыми ключами лежит понятие односторонних функций с потайным ходом. У таких функций очень легко вычислить их значение по известному аргументу, но совершенно невозможно определить аргумент, если известно только значение функции. Определить аргумент можно, если известна некоторая секретная дополнительная информация, называемая потайным ходом. Таким образом, любой может вычислить значение односторонней функции, то есть выполнить процедуру шифрования. Обратную процедуру расшифрования и определения исходного аргумента функции может выполнить только тот, кто знает секретную информацию, то есть ключ расшифрования. За годы развития криптографии с открытыми ключами предлагались различные варианты односторонних функций, на основе которых можно было бы разрабатывать криптоалгоритмы. Однако с течением времени выделились следующие три основные задачи:
В 1978 г. была предложена и опубликована наиболее известная и распространенная на сегодняшний день криптосистема с открытыми ключами RSA. Название системы образовано по первым буквам ее разработчиков Ривеста, Шамира и Адлемана (Rivest, Shamir, Adleman). Алгоритм RSA может использоваться для шифрования данных и для электронной цифровой подписи. Рассмотрим схему шифрования RSA: ^ p, q – большие простые числа n=p*q – модуль шифрования j(n)=(p-1)(q-1) – функция Эйлера Открытый ключ e выбирается из интервала 1 Секретный ключ d вычисляется по расширенному алгоритму Евклида: ed=1 (mod j (n)) ^ c = me (mod n) Операция расшифрования: m=cd (mod n) Секретные значения: p, q, d Открытый ключ: e Рассмотрим конкретный пример шифрования по RSA: ^ Пусть p=5 и q=11 n=p*q=5*11=55 j (n)=(p-1)(q-1) = (5-1)(11-1)=4*10=40 Пусть открытый ключ e = 7 Тогда секретный ключ d=23 Операция шифрования исходного сообщения m=2: c = 27 (mod 55) = 18 ^ m=1823 (mod 55) = 2 Секретные значения: p=5, q=11, d=23 Открытый ключ: e=7 Считается, что надежность системы состоит в вычислительной сложности решения задачи факторизации больших чисел. Действительно, если разложить на множители значение модуля шифрования n, то можно определить числа p и q. Зная числа p и q можно вычислить секретный ключ. В таком случае возможно нелегальное прослушивание сетевого трафика, извлечение и расшифрование передающихся криптограмм. Однако на существующем уровне развития вычислительной техники нет способа на практике эффективно раскладывать большие числа на множители. Под словом эффективно тут понимается полиномиальная зависимость времени работы от размера числа. Следует отметить, что с 1994 г. теоретически для квантового компьютера были предложены полиномиальные алгоритмы факторизации, а также решения некоторых других сложных проблем, включая задачу дискретного логарифмирования (Манин, 1999). Однако существующий уровень технологий все еще не позволяет полноценно использовать эти алгоритмы. Для обеспечения действительной и достаточно долгосрочной секретности сегодня на практике рекомендуется использовать числа размером от 1024 бит. Ниже приведена в таблица зависимости требуемой производительности для осуществления успешной атаки на RSA в зависимости от размера модуля шифрования (Чмора, 2001). ^
1 M/Y – год работы компьютера, который выполняет один миллион операций в секунду. Эквивалентной мощностью обладает, например, DEC VAX 11/780. Предполагается, что к 2004 г. вычислительный потенциал атаки со стороны некоторой крупной организации может достигнуть уровня до 108 M/Y, а к 2014 г. – до 1011 M/Y. Возможные атаки с привлечением вычислительных ресурсов компьютеров, подключенных к глобальной открытой сети, например к Интернет, достигнут еще большего уровня и составят в 2004 г. до 2*109 M/Y, а в 2014 г. – до 1013 M/Y. В 2003 году известный ученый Ади Шамир, один из разработчиков RSA, вместе со своим коллегой Ираном Тромером, опубликовал работу (Shamir, Tromer, 2003), в которой была предложена схема нового аппаратного устройства, получившего название TWIRL (The Weizmann Institute Relation Locator). Это устройство предназначено для разложения чисел на множители и, по сути, является специализированной интегральной схемой, выполненной по 0.13-микронной технологии. На данный момент разработана принципиальная схема устройства и оценена ориентировочная стоимость его создания. Ожидается, что стоимость реализации TWIRL для взлома шифра RSA с длиной ключа в 512 бит менее чем за 10 минут составит $10 000, а для 1024 бит за 1 год – $1 000 000. На практике схема TWIRL еще не реализована.
|
плохо
2отлично
1 