Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
В 1976 году Уитфилд Диффи и Мартин Хеллман в [157] заложили основы для преодоления указанной трудности, введя понятия открытого распределения ключей и криптографии с открытым ключом. Сходные понятия было независимо открыты Ральфом Мерклем [265]. Вскоре последовала первая практическая реализация криптосистемы с открытым ключом, предложенная Рональдом Ривестом, Эди Шамиром и Леонардом Эдле-маном [307]. Секретная связь по незащищенным каналам связи между двумя совершенно незнакомыми друг с другом сторонами наконец-то стала возможна.
Основное наблюдение, которое, собственно, и привело к криптографии с открытым ключом, заключалось в том, что тот, кто зашифровывает сообщение, не обязательно должен быть способен его расшифровывать. В таких системах каждый пользователь выбирает свой собственный секретный ключ, на основании которого получает пару соответствующих алгоритмов. При этом он делает один из них доступным каждому из возможных своих респондентов, объявляя этот алгоритм собственным открытым алгоритмом шифрования, в то время как другой, двойственный этому открытому, объявляет своим личным алгоритмом дешифрования, и хранит его в строгом секрете. Это, например, позволяет Бобу, даже совершенно незнакомому с Алисой, применять ее (общедоступный) открытый алгоритм шифрования, чтобы зашифровать предназначенное ей сообщение, но только она сама сможет расшифровать его с помощью своего личного (секретного) алгоритма дешифрования. Само собой разумеется, что такие системы могут быть стойкими лишь тогда, когда из общедоступного алгоритма шифрования никаким образом нельзя получить соответствующий ему секретный алгоритм дешифрования.
24 Определения и классификация
Главу 2
Совсем недавно Шафи Гольдвассер и Сильвио Микэли ввели понятие вероятностного шифрования, которое является очень интересной вариацией на тему криптографии с открытым ключом [197, 198, 56]. В том случае, если произвольное сообщение шифруется при помощи вероятностного шифрования, то при криптоанализе шифртекста, по существу, становится одинаково трудно выяснить о сообщении какую бы то ни было информацию, которая позволила бы восстановить весь открытый текст. Кроме того следует отметить, что существует вероятностная схема шифрования, которая является более быстрой, чем предложенная до этого схема шифрования с открытым ключом RSA — см. § 4.4 и § 4.6. Подобные криптографические системы называются «вероятностным» в связи с тем, что при их использовании шифрование сообщений, которые имеют один и тот же исходный текст и шифруются на одном и том же ключе, в разное время может привести к совершенно различным шифртекстам.
Рассматривались и некоторые другие подходы к проблеме распределения ключей. Например, бесключевая криптография, предложенная Боуэном Альперном и Фредом Шнейдером, может эффективно использоваться в сетях связи, которые скрывают происхождение (но не содержание) сообщений [9, 370, 141]. В идентификационной криптосистеме Эди Шамира отпадает необходимость в распределении ключей, но требуется наличие некоего центра, которому должна быть доверена генерация секретных ключей [318]. Однако здесь мы не будем обсуждать эти новые понятия. В заключение, отметим только, что Чарльз Беннетт и Жиль Брассар, опираясь на работу Стефена Уисне-ра [357], разработали теорию квантовой криптографии, которая предлагает совершенно иную базу для современной криптологии и в своих утверждениях о секретности основывается скорее на
А
квантовой физике, нежели на математике или теории вычислительной сложности [31, 27, 26, 28, 25]. Квантовой криптографии посвящена заключительная седьмая глава этой книги.
Глава 3
Системы с секретным ключом
§ 1. Определения и уровни атак
Криптосистема с открытым ключом состоит из пространства ключей 1C и, для каждого к ? 1C, из пространства открытых текстов сообщений Мк, пространства шифртекстов сообщений Ск и пары функций Ек'.Мк —>Ск и Dk'.Ck —>¦ Мк таких, что Dk{Ek{m)) = т для каждого сообщения открытого текста т&Л4к-При этом необходимо, чтобы, задаваясь любым ключом к, можно было легко получать эффективные алгоритмы для вычисления Ек и Dk- Криптосистема называется эндоморфной, если Ск=Мк для каждого к.
Для обеспечения секретной связи криптосистема используется следующим образом. Если, например, Алиса и Боб предполагают, что в конечном счете могут установить друг с другом конфиденциальную связь, то с самого начала они должны договориться между собой о некотором совместном секретном ключе к?)С. ТоГда, если в дальнейшем Алиса захочет послать некоторое специальное сообщение т?Л4* Бобу, то она, для того чтобы сформировать шифртекст с — Ек{тп), должна использовать алгоритм шифрования Ек', затем ей необходимо будет послать шифр-текст с по незащищенному каналу Бобу; получив этот шифр-текст с, Боб должен использовать алгоритм Dk, чтобы восстановить открытый текст сообщения m=D*(c).
Во многих практически используемых криптографических системах; и Мк, и Ск — конечные множества, часто не зависящие от самого ключа к. Таково, например, множество всех строк,
