Васюков В.Н. Теория электрической связи

Подождите немного. Документ загружается.

13.4. Методы перемешивания

363

и источник ключей с энтропией

 

   

log

H K P K P K







Количество информации источника не может быть больше, чем

log n

(это количество соответствует равновероятным сообщени-

ям). Эта информация может быть полностью скрыта, только если

неопределенность ключа не меньше

log n

. Таким образом, неопре-

деленность источника ключей устанавливает предел – максималь-

ное количество информации, которое может быть скрыто при по-

мощи ключей данного источника.

Если источник порождает последовательности бесконечной

длины, то никакой конечный ключ не дает совершенной секретно-

сти. Пусть длина сообщения равна

, а длина ключа

. Тогда

для совершенной секретности требуется

log logN n M m

где

– объемы алфавитов для сообщений и ключей соответ-

ственно.

Совершенные системы применяются на практике для засекре-

чивания сравнительно коротких сообщений и в тех случаях, когда

полной секретности придается чрезвычайное значение.

В качестве теоретической меры секретности Шеннон предло-

жил использовать ненадежность

. Имеются две ненадежности:

ненадежность ключа

       

| , log |

H K H K E P E K P K E  



(13.2)

и ненадежность сообщения

       

| , log |

H M H M E P E M P M E  



, (13.3)

где

 

,P E M

– совместная вероятность криптограммы

и сооб-

щения

 

,P E K

– совместная вероятность криптограммы

ключа

 

|P M E

 

|P K E

– апостериорные вероятности для

сообщения и ключа при условии перехвата криптограммы

Ненадежностью называется условная энтропия (см. разд. 8.2).

13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

364

Суммирование в (13.2) и (13.3) проводится по всем возможным

криптограммам и ключам (соответственно по всем возможным

криптограммам и сообщениям) определенной длины, поэтому не-

надежности зависят от числа

перехваченных букв криптограм-

мы. Постепенное убывание ненадежностей с ростом

соответст-

вует увеличению сведений о ключе и сообщении, имеющихся у

шифровальщика противника. Если ненадежность становится нуле-

вой, это означает, что единственное сообщение (или единственный

ключ) имеет апостериорную вероятность 1, а все остальные – ну-

левые апостериорные вероятности. Шеннон доказал, что в принци-

пе можно построить систему, в которой ненадежности не стремят-

ся к нулю при

N 

, и даже «строго идеальную систему», в

которой

( ) ( )

H K H K

. Для сообщений на естественных языках

характерны неравновероятность и зависимость букв исходного

текста, поэтому для них построение идеальной системы хотя и

возможно, но осуществить его практически очень сложно [26].

Статистическая зависимость символов (букв) естественного

языка позволяет раскрывать многие типы шифров. Например,

шифр Цезаря (и вообще шифры на основе подстановок) раскрыва-

ется на основе простого подсчета частот встречаемости различных

букв в криптограмме и сравнения их с известными для данного

языка частотами. Для некоторых шифров могут потребоваться бо-

лее тонкие методы статистического анализа. В любом случае ста-

тистический анализ криптограмм строится на основе некоторых

статистик. Под статистикой понимается функция наблюдаемой

криптограммы, значение которой позволяет сделать какие-либо

более или менее правдоподобные выводы относительно использо-

ванного ключа. Удачный выбор подходящих статистик определяет

успех криптоаналитика при взломе шифра, многократно сужая

возможный круг ключей до того предела, когда уже можно устано-

вить правильный ключ путем перебора.

Для того чтобы затруднить раскрытие шифров статистически-

ми методами, Шеннон предложил использовать две идеи, которые

он назвал «распылением» и «запутыванием». Смысл «распыления»

состоит в таком преобразовании текста, при котором статистиче-

ские связи между его элементами становятся трудно наблюдаемы-

ми, хотя избыточность сообщения при этом и не изменяется. Идея

«запутывания» (перемешивания) заключается в том, чтобы сделать

соотношения между простыми статистиками в пространстве крип-

тограмм и простыми подмножествами в пространстве ключей

весьма сложными и беспорядочными [26]. На этих идеях основано

13.4. Методы перемешивания

365

использование составных шифров, состоящих часто в последова-

тельном применении простых подстановок и перестановок.

В шифрах подстановки буквы сообщения заменяются другими

буквами, поэтому статистические свойства текста сохраняются, но

относятся теперь к буквам другого алфавита. В шифрах переста-

новки буквы сообщения остаются теми же, но изменяется их рас-

положение в тексте

. Комбинирование поочередно применяемых

подстановок и перестановок дает возможность создавать весьма

стойкие шифры.

Один из примеров реализации такого подхода – государствен-

ный стандарт шифрования США, известный под названием DES

(Data Encryption Standard). Алгоритм шифрования является откры-

тым; секретным при каждом использовании алгоритма является

только ключ. Ключ длиной в 56 бит обеспечивает высокий уровень

стойкости шифра, так как общее количество ключей составляет

около 7,2·10

. Открытый текст и криптограмма при этом являются

двоичными 64-значными последовательностями. Криптоалгоритм

DES представляет собой суперпозицию из 16 последовательных

шифроциклов, в каждом из которых происходят подстановки и пе-

рестановки в четырехбитовых группах, при этом в каждом цикле

используются 48 бит ключа, которые выбираются из полного клю-

ча длиной в 56 бит [25]. По утверждению Национального бюро

стандартов США, метод DES имеет высокую криптостойкость, ко-

торая делает его раскрытие дороже получаемой при этом прибыли,

экономичен в реализации и эффективен в смысле быстродействия.

Наиболее существенным недостатком считается слишком корот-

кий ключ: для дешифрования требуется перебрать 2

(или 7,2·10

)

ключей, что достаточно много для современной аппаратуры, но

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

метод допускает простую модификацию в виде последовательного

применения к сообщению нескольких циклов шифрования с раз-

личными ключами: например, уже при трех ключах для дешифро-

вания требуется выполнение около 2

168

(т.е. 3,7·10

) операций.

Отечественный стандарт шифрования данных, предусмотрен-

ный ГОСТ 28147-89, предназначен для шифрования данных аппа-

Простой пример шифра перестановки может быть реализован, напри-

мер, путем записи сообщения в разграфленный прямоугольник по

строкам и последующего считывания по столбцам. Один из методов

шифрования основан на записи сообщения на ячейках граней кубика

Рубика и считывании после заданного числа заданных трансформа-

ций [25].

13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

366

ратным или программным путем [25]. Стандарт предусматривает

различные режимы шифрования, но в любом случае используется

256-разрядный двоичный ключ. Двоичные данные, подлежащие

зашифрованию, разбиваются на блоки по 64 разряда, над которыми

выполняются преобразования, включающие суммирования по мо-

дулям 2, 2

и 2

–1, подстановки и циклические сдвиги. Стандарт

обладает всеми достоинствами алгоритма DES и в то же время

свободен от его недостатков, однако имеет собственный сущест-

венный недостаток – очень низкое быстродействие при програм-

мной реализации [25].

13.5. КРИПТОСИСТЕМЫ

С ОТКРЫТЫМ КЛЮЧОМ

Системы с открытым ключом названы так потому, что ключ,

используемый при зашифровании данных, не является секретным и

может быть, например, опубликован в средствах массовой инфор-

мации. Также несекретным является алгоритм зашифрования. За-

щита данных обеспечивается тем, что для расшифрования необхо-

дим другой (секретный) ключ, причем он не может быть определен

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

открытым ключом называют поэтому несимметричными алгорит-

мами [29]. Наиболее известен метод шифрования с открытым клю-

чом RSA

Согласно методу RSA, для генерирования ключей необходимо

выполнить следующие действия [25].

1. Выбрать два больших простых числа

2. Определить их произведение

.n pq

3. Выбрать число

взаимно простое с числом

( 1)( 1)pq

4. Определить число

для которого выполняется условие

mod[( 1)( 1)] 1ed p q  

5. Назвать открытым ключом числа

, а секретным клю-

чом числа

Метод назван по первым буквам фамилий авторов – Rivest, Shamir, Ad-

leman.

13.5. Криптосистемы с открытым ключом

367

Для применения полученных ключей открытое сообщение не-

обходимо закодировать числами от 0 до

1n 

. Каждое такое число

()Mi

зашифровывается при помощи открытого ключа по формуле

 

( ) ( ) mod( )

C i M i n

. (13.4)

Для расшифрования используется формула с секретным ключом

 

( ) ( ) mod( )

M i C i n

. (13.5)

Пример 13.1. Рассмотрим в качестве простого примера алгоритм

RSA, основанный на очень малых числах

. Предположим, что

шифрованию подлежит сообщение на русском языке [25]. Буквы

сообщения можно представить числами от 0 до 32 (см. разд. 13.2).

Тогда за

можно принять число 33, а за простые числа

со-

ответственно 3 и 11. Итак, согласно описанному алгоритму:

1) выберем два простых числа

3p 

11q 

;

2) найдем

3 11 33n   

;

3) за число

взаимно простое с числом

( 1)( 1) 20pq  

примем число 3;

4) соотношению

3mod(20) 1e

удовлетворяют числа 7, 27,

47,…; выберем

7e 

Итак, открытым ключом для зашифрования является пара чи-

сел

7e 

33n 

, а закрытым (секретным) ключом для расшиф-

рования – пара чисел

3d 

33n 

Зашифруем слово ДОМ. Буквам Д, О и М соответствуют числа

5, 15 и 13. Используя открытый ключ, получим на основании (13.4)

криптограмму, состоящую из чисел:

5 mod(33) 78125mod(33) 14C   

;

15 mod(33) 170859375mod(33) 27C   

;

13 mod(33) 62748517mod(33) 7C   

Для расшифрования криптограммы

{14, 27, 7}

воспользуемся

формулой (13.5) и секретным ключом:

14 mod(33) 2744mod(33) 5M   

;

27 mod(33) 19683mod(33) 15M   

;

7 mod(33) 343mod(33) 13M   

. ◄

13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

368

Легко видеть, что в результате расшифрования получилось ис-

ходное открытое сообщение ДОМ. Следует отметить, что на прак-

тике применяются настолько большие числа

, что, зная

(открытый ключ), невозможно найти

за приемлемое время,

так как в настоящее время не только не известен достаточно эф-

фективный (полиномиальный) алгоритм разложения большого

числа на простые множители, но и сам вопрос о существовании

таких алгоритмов (а следовательно, о возможности взлома систем с

открытым ключом в будущем) остается открытым [25, 27]. Тем не

менее нельзя исключить открытие в будущем эффективных алго-

ритмов определения делителей целых чисел (факторизации),

вследствие чего метод шифрования с открытым ключом станет аб-

солютно бесполезным. Пока этого не произошло, метод RSA имеет

важные преимущества перед другими криптосистемами, такие как

очень высокая криптостойкость и простота аппаратной и про-

граммной реализации

13.6. ЦИФРОВАЯ ПОДПИСЬ

Одной из важных задач, связанных с передачей документов

по каналам связи или с пересылкой их на машинных носителях в

электронной форме, является задача аутентификации (подтвержде-

ния подлинности). Для документа в обычной (бумажной) форме

эта проблема решается за счет жесткой связи информации с носи-

телем (бумагой). Документ в электронной форме такой связи не

имеет и иметь не может.

При передаче секретных документов (военного или диплома-

тического содержания) весьма вероятным является перехват доку-

мента противником, который может либо создать и переслать вме-

сто него подложный документ, либо изменить содержимое

документа законного источника. Чтобы обнаружить подмену, в

зашифрованное сообщение встраивается так называемая имито-

вставка, которая представляет собой последовательность, получен-

ную по определенному алгоритму на основе всего текста открыто-

го сообщения. Получатель после расшифрования криптограммы

подвергает полученный открытый текст повторной обработке тем

же алгоритмом и сравнивает полученную имитовставку с приня-

той. Если совпадения нет, принятое сообщение считается ложным.

Кроме метода RSA, к криптосистемам с открытым ключом относятся

системы Эль-Гамаля и Мак-Элиса [25].

13.6. Цифровая подпись

369

Совершенно другая ситуация может иметь место при обмене

информацией коммерческого характера. Здесь возможна ситуация,

когда партнеры по информационному обмену не доверяют друг

другу и являются в каком-то смысле противниками. Один из парт-

неров может изготовить документ, зашифровать его и заявить, что

получил его от партнера.

Для такого случая необходимо применять схему шифрования

следующего вида. Передающий абонент зашифровывает подпись с

помощью своего секретного ключа, а получатель расшифровывает

ее своим несекретным ключом. Несекретный ключ может пред-

ставлять собой набор проверочных соотношений, позволяющих

установить подлинность подписи, но не восстановить секретный

ключ. Таким образом, никто, кроме законного автора документа,

не в состоянии сгенерировать правильную подпись.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. В чем заключается проблема защиты информации?

2. Что такое совершенная секретная система?

3. В чем отличие криптографии и стеганографии?

4. Чем отличаются шифры от кодов?

5. В чем состоят задачи криптографии и криптоанализа?

6. Что такое система с открытым ключом? На чем основана ее

криптостойкость?

7. Что такое цифровая подпись?

УПРАЖНЕНИЯ

1. Попросите партнера зашифровать сообщение длиной

80…100 букв шифром простой подстановки. Расшифруйте крипто-

грамму, воспользовавшись оценками вероятностей букв русского

текста (для оценивания можно использовать любой неспециальный

текст, например газетную статью).

2. Зашифруйте короткое (10…20 букв) сообщение при помощи

гаммы. В качестве гаммы используйте некоторый текст (например,

фразу, строку из стихотворения, пословицу и т.п.). Предложите

партнеру расшифровать текст, передав ему гамму.

3. Зашифруйте короткое слово (3…5 букв) при помощи алго-

ритма RSA, воспользовавшись данными примера 13.1. Расшифруй-

те полученный шифртекст.

14. ЭФФЕКТИВНОСТЬ И ОПТИМИЗАЦИЯ СИСТЕМ СВЯЗИ

370

14. ЭФФЕКТИВНОСТЬ

И ОПТИМИЗАЦИЯ

СИСТЕМ СВЯЗИ

овременные системы связи (системы пере-

дачи информации, телекоммуникационные

системы) представляют собой высокотехнологичную инфраструк-

туру, во многом определяющую облик цивилизации. Создание

средств связи, их эксплуатация, разработка новых принципов и

технологических решений в условиях жесткой конкурентной борь-

бы предъявляют высокие требования к качеству принимаемых ре-

шений. Специалисту совершенно необходимо знать, по каким па-

раметрам следует сравнивать между собой различные устройства и

системы связи, как обеспечить выполнение предъявляемых требо-

ваний по их эффективности, помехоустойчивости, скрытности,

электромагнитной совместимости, информационной защищенно-

сти и т.д. Подробное изучение этих вопросов является предметом

специальных дисциплин. В настоящем разделе дается лишь крат-

кое изложение основных понятий, связанных с эффективностью

систем связи и их оптимизацией.

14.1. ОСНОВНЫЕ ПОКАЗАТЕЛИ

ЭФФЕКТИВНОСТИ

Назначение любой системы связи заключается в передаче

информации; чем быстрее и точнее передается информация, тем

лучше система. Поэтому основными показателями качества (эф-

фективности) систем связи являются скорость передачи и верность

(достоверность), под которой понимается степень соответствия

принятого сообщения переданному. Конкретная количественная

мера верности выбирается в зависимости от характера сообщения

[22]. В дискретных системах связи мерой верности может служить,

например, средняя вероятность ошибочного решения при приеме, в

14.1. Основные показатели эффективности

371

аналоговых системах – среднеквадратическое отклонение принято-

го сообщения от переданного.

Скорость передачи информации



измеряется в битах в секун-

ду; ее не следует путать с технической скоростью, измеряемой в бо-

дах (см. разд. 1). Предельная скорость передачи информации по

данному каналу называется его пропускной способностью

. Одна-

ко этот предел лишь показывает потенциальные возможности, для

приближения к которым могут потребоваться непомерные затраты

(например, очень сложные и дорогие кодеры и декодеры, очень

большое время кодирования-декодирования и т.п.). Степень исполь-

зования пропускной способности канала характеризуют относитель-

ным показателем – информационной эффективностью

/IC



Ресурсы, которыми располагает разработчик, всегда ограничены.

Например, могут быть ограничены стоимость устройств, эксплуата-

ционные расходы, максимальное время задержки получения сооб-

щений, полоса частот, занимаемая системой радиосвязи, допусти-

мый уровень электромагнитных излучений вне этой полосы,

уровень скрытности связи, степень защищенности (время, необхо-

димое для «взлома» криптограммы), массогабаритные характери-

стики и др. Таким образом, поиск решения при проектировании сис-

темы связи имеет характер задачи оптимизации с ограничениями.

Обозначая различные количественные показатели эффективно-

сти (качества) через

, ,...,

k k k

, получаем вектор

, который ха-

рактеризует качество системы. Множество векторов пространства

размерности выше 1 не является естественно упорядоченным, как

одномерное пространство (например, числовая прямая); сравнение

двух систем между собой по векторному показателю не позволяет,

как правило, выбрать безусловно лучшее решение. Формулирова-

ние задачи выбора оптимального решения всегда предполагает за-

дание скалярного показателя, такого, что искомому оптимальному

решению соответствует его максимум (или минимум); этот ска-

лярный показатель называется целевой функцией. Иногда за ска-

лярный показатель качества можно принять линейную комбина-

цию компонент вектора

, но тогда встает вопрос о назначении

весовых коэффициентов. В большинстве случаев более оправдан-

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

вектора (например, скорость передачи информации) при ограниче-

ниях в форме неравенств, накладываемых на остальные компонен-

ты (например, средняя вероятность ошибки при приеме двоичного

символа не более 0,001; задержка не более 0,1 с; потребляемая

мощность не более 0,5 Вт и т.п.).

14. ЭФФЕКТИВНОСТЬ И ОПТИМИЗАЦИЯ СИСТЕМ СВЯЗИ

372

Аргументами целевой функции служат, вообще говоря, все ве-

личины, так или иначе влияющие на значение целевой функции.

Поскольку таких факторов слишком много и учесть их влияние

точно не представляется возможным, неизбежно упрощение моде-

ли и сведéние всего множества влияющих величин к нескольким

наиболее существенным. Тем не менее, необходимо рассматривать

систему связи в виде целостного объекта, учитывая ее состав,

взаимодействие ее частей друг с другом, влияние на нее окружаю-

щей среды, взаимодействие системы и пользователей, историю и

перспективы развития систем данного класса и близких классов и

т.д. Такой подход называется системным [12].

14.2. ОПТИМИЗАЦИЯ СИСТЕМ СВЯЗИ

Действие системы связи можно описать операторным урав-

нением, выражающим различные этапы формирования, передачи и

приема сигналов. Рассматривая упрощенную систему связи (см.

рис. 1.2), можно описать преобразование сообщения

в модули-

рованный сигнал

()ut

операторным выражением

( ) { , ( )}u t M a s t

где

()st

– колебание-переносчик. Преобразование модулированно-

го сигнала на выходе передатчика в наблюдаемое колебание на

входе приемника можно представить выражением

( ) { ( ), ( )}z t T u t t

, где

()t

– помеха в канале. Аналогично, преоб-

разование наблюдаемого колебания в оценку



сообщения можно

описать выражением

{ ( )}a D z t



. Объединяя эти выражения, по-

лучим операторное уравнение системы связи

{ { { , ( )}, ( )}}a D T M a s t t



. (14.1)

Задача оптимального проектирования системы связи заключа-

ется в том, чтобы обеспечить наилучшее качество в смысле вы-

бранного критерия. Критерий должен соответствовать назначению

системы, быть достаточно простым и зависеть от величин, кото-

рыми можно управлять в процессе проектирования.

Полная задача оптимизации проектирования системы согласно

(14.1) может быть разложена на подзадачи, связанные с оптимиза-

цией на уровне отдельных операторов, входящих в (14.1). В неко-

торых случаях, когда задана линия связи [12], оператор

( ) { ( ), ( )}z t T u t t

, описывающий взаимодействие сигнала с поме-

хой, считается неуправляемым, тогда оптимизация осуществляется