В.Н. Васюков - Теория электрической связи (1266498), страница 59

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 59)

Крометого, число различных ключей должно быть также не меньше, чемразличных сообщений. Например, совершенная система получается, если число сообщений равно числу ключей и числу криптограмм, причем все ключи равновероятны [26].В терминах теории информации секретная система содержит дваисточника неопределенности: источник сообщений10 с энтропиейnH  M     P  M i  log P  M i i 110Здесь, очевидно, имеется в виду конечное число сообщений.36313.4. Методы перемешиванияи источник ключей с энтропиейm  H  K     P K j log P K j .j 1Количество информации источника не может быть больше, чемlog n (это количество соответствует равновероятным сообщениям). Эта информация может быть полностью скрыта, только еслинеопределенность ключа не меньше log n .

Таким образом, неопределенность источника ключей устанавливает предел – максимальное количество информации, которое может быть скрыто при помощи ключей данного источника.Если источник порождает последовательности бесконечнойдлины, то никакой конечный ключ не дает совершенной секретности. Пусть длина сообщения равна N , а длина ключа M . Тогдадля совершенной секретности требуетсяN log n  M log m ,где n и m – объемы алфавитов для сообщений и ключей соответственно.Совершенные системы применяются на практике для засекречивания сравнительно коротких сообщений и в тех случаях, когдаполной секретности придается чрезвычайное значение.В качестве теоретической меры секретности Шеннон предложил использовать ненадежность 11 .

Имеются две ненадежности:ненадежность ключаH E  K   H  K | E     P  E, K  log P  K | E E,K(13.2)и ненадежность сообщенияH E M   H M | E     P  E, M  log P M | E  ,E ,M(13.3)где P  E , M  – совместная вероятность криптограммы E и сообщения M , P  E , K  – совместная вероятность криптограммы E иключа K , P  M | E  и P  K | E  – апостериорные вероятности длясообщения и ключа при условии перехвата криптограммы E .11Ненадежностью называется условная энтропия (см. разд.

8.2).36413. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИСуммирование в (13.2) и (13.3) проводится по всем возможнымкриптограммам и ключам (соответственно по всем возможнымкриптограммам и сообщениям) определенной длины, поэтому ненадежности зависят от числа N перехваченных букв криптограммы. Постепенное убывание ненадежностей с ростом N соответствует увеличению сведений о ключе и сообщении, имеющихся ушифровальщика противника.

Если ненадежность становится нулевой, это означает, что единственное сообщение (или единственныйключ) имеет апостериорную вероятность 1, а все остальные – нулевые апостериорные вероятности. Шеннон доказал, что в принципе можно построить систему, в которой ненадежности не стремятся к нулю при N   , и даже «строго идеальную систему», вкоторой H E (K )  H (K ) . Для сообщений на естественных языкаххарактерны неравновероятность и зависимость букв исходноготекста, поэтому для них построение идеальной системы хотя ивозможно, но осуществить его практически очень сложно [26].Статистическая зависимость символов (букв) естественногоязыка позволяет раскрывать многие типы шифров.

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

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

Смысл «распыления»состоит в таком преобразовании текста, при котором статистические связи между его элементами становятся трудно наблюдаемыми, хотя избыточность сообщения при этом и не изменяется. Идея«запутывания» (перемешивания) заключается в том, чтобы сделатьсоотношения между простыми статистиками в пространстве криптограмм и простыми подмножествами в пространстве ключейвесьма сложными и беспорядочными [26]. На этих идеях основано13.4. Методы перемешивания365использование составных шифров, состоящих часто в последовательном применении простых подстановок и перестановок.В шифрах подстановки буквы сообщения заменяются другимибуквами, поэтому статистические свойства текста сохраняются, ноотносятся теперь к буквам другого алфавита. В шифрах перестановки буквы сообщения остаются теми же, но изменяется их расположение в тексте12.

Комбинирование поочередно применяемыхподстановок и перестановок дает возможность создавать весьмастойкие шифры.Один из примеров реализации такого подхода – государственный стандарт шифрования США, известный под названием DES(Data Encryption Standard). Алгоритм шифрования является открытым; секретным при каждом использовании алгоритма являетсятолько ключ. Ключ длиной в 56 бит обеспечивает высокий уровеньстойкости шифра, так как общее количество ключей составляетоколо 7,2·1016. Открытый текст и криптограмма при этом являютсядвоичными 64-значными последовательностями. КриптоалгоритмDES представляет собой суперпозицию из 16 последовательныхшифроциклов, в каждом из которых происходят подстановки и перестановки в четырехбитовых группах, при этом в каждом циклеиспользуются 48 бит ключа, которые выбираются из полного ключа длиной в 56 бит [25].

По утверждению Национального бюростандартов США, метод DES имеет высокую криптостойкость, которая делает его раскрытие дороже получаемой при этом прибыли,экономичен в реализации и эффективен в смысле быстродействия.Наиболее существенным недостатком считается слишком короткий ключ: для дешифрования требуется перебрать 256 (или 7,2·1016)ключей, что достаточно много для современной аппаратуры, номожет оказаться преодолимым в ближайшем будущем. Впрочем,метод допускает простую модификацию в виде последовательногоприменения к сообщению нескольких циклов шифрования с различными ключами: например, уже при трех ключах для дешифрования требуется выполнение около 2168 (т.е. 3,7·1050) операций.Отечественный стандарт шифрования данных, предусмотренный ГОСТ 28147-89, предназначен для шифрования данных аппа12Простой пример шифра перестановки может быть реализован, например, путем записи сообщения в разграфленный прямоугольник построкам и последующего считывания по столбцам.

Один из методовшифрования основан на записи сообщения на ячейках граней кубикаРубика и считывании после заданного числа заданных трансформаций [25].36613. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИратным или программным путем [25]. Стандарт предусматриваетразличные режимы шифрования, но в любом случае используется256-разрядный двоичный ключ. Двоичные данные, подлежащиезашифрованию, разбиваются на блоки по 64 разряда, над которымивыполняются преобразования, включающие суммирования по модулям 2, 232 и 232–1, подстановки и циклические сдвиги. Стандартобладает всеми достоинствами алгоритма DES и в то же времясвободен от его недостатков, однако имеет собственный существенный недостаток – очень низкое быстродействие при программной реализации [25].13.5.

КРИПТОСИСТЕМЫС ОТКРЫТЫМ КЛЮЧОМСистемы с открытым ключом названы так потому, что ключ,используемый при зашифровании данных, не является секретным иможет быть, например, опубликован в средствах массовой информации. Также несекретным является алгоритм зашифрования. Защита данных обеспечивается тем, что для расшифрования необходим другой (секретный) ключ, причем он не может быть определенпо открытому ключу зашифрования. Алгоритмы шифрования соткрытым ключом называют поэтому несимметричными алгоритмами [29]. Наиболее известен метод шифрования с открытым ключом RSA13.Согласно методу RSA, для генерирования ключей необходимовыполнить следующие действия [25].1.

Выбрать два больших простых числа p и q.2. Определить их произведение n  pq.3. Выбрать число d , взаимно простое с числом ( p  1)(q  1) .4. Определить число e, для которого выполняется условиеed mod[( p  1)(q  1)]  1 .5. Назвать открытым ключом числа e и n , а секретным ключом числа d и n .13Метод назван по первым буквам фамилий авторов – Rivest, Shamir, Adleman.36713.5. Криптосистемы с открытым ключомДля применения полученных ключей открытое сообщение необходимо закодировать числами от 0 до n  1 . Каждое такое числоM (i ) зашифровывается при помощи открытого ключа по формулеC (i)   M (i) mod(n) .e(13.4)Для расшифрования используется формула с секретным ключомM (i)  C(i) mod(n) .d(13.5)Пример 13.1.

Рассмотрим в качестве простого примера алгоритмRSA, основанный на очень малых числах p и q . Предположим, чтошифрованию подлежит сообщение на русском языке [25]. Буквысообщения можно представить числами от 0 до 32 (см. разд. 13.2).Тогда за n можно принять число 33, а за простые числа p и q соответственно 3 и 11. Итак, согласно описанному алгоритму:1) выберем два простых числа p  3 и q  11 ;2) найдем n  3  11  33 ;3) за число d , взаимно простое с числом ( p  1)(q  1)  20 ,примем число 3;4) соотношению e  3mod(20)  1 удовлетворяют числа 7, 27,47,…; выберем e  7 .Итак, открытым ключом для зашифрования является пара чисел e  7 и n  33 , а закрытым (секретным) ключом для расшифрования – пара чисел d  3 и n  33 .Зашифруем слово ДОМ.

Характеристики

Список файлов книги