А.И. Куприянов - Основы защиты информации (1022813), страница 34
Текст из файла (страница 34)
Для этого задается : большое простое число р. Сообщения представляются целыми чис.'::.лами С из интервала (1, р). Оригинальный протокол передачи со;::общения С выглядит следующим образом. Отправитель сообщения А и получатель В знают лишь р. А гене: рирует случайное число Хиз интервала (1, р). В генерирует случай: ное число Уиз того же интервала. А шифрует сообщение, формируя криптограмму В шифрует его своим ключом Ш~ (Ша) хшо«1р (5.80) Ш = Ш(С) = ас(пю«1р) С = 1оя,Ш(С) (пюдр), (5.84 ,/р» 21оя2р, (5.85) 160 161 ««уприяиов Шв — — (Ш„) 'пю«1 р и посылает Ша абоненту А. А снимает свой ключ и возвращает сообщение абоненту В. Получатель В расшифровывает сообщение: С = (ША «) утод Р. (5.81) Криптосистема ЭльГамаля обеспечивает большую степень защиты, чем алгоритм КЯА.
Этот эффект достигается при том же Ю, что позволяет почти на порядок увеличить скорость шифрования и расшифровывания. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа„ т.е. произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предположить, что сложности вскрытия систем КБА и ЭльГамаля будут сходными. С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет.
Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть одна особенность. Если в системе, построенной с помощью алгоритма КБА, криптоаналитику удалось разложить открытый ключ и одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В системе, построенной с помощью алгоритма ЭльГамаля, угрозе раскрытия подвергнутся все абоненты криптографической сети.
Кроме того, появились возможности существенно усовершенствовать методы дискретного логарифмирования для отдельных специальных простых чисел. Преимущества двухключевых систем могли бы привести к полному вытеснению криптосистем с секретными ключами из большинства сетевых приложений, если бы не очень низкая скорость криптопреобразований: они работают на несколько порядков медленнее систем с открытыми ключами. Этот недостаток тем более ес;гвенен, чем длиннее шифруемое сообщение.
Противоречие : решается очень просто, если применять открытое распростра' ние сравнительно коротких секретных ключей, действующих не" должительное время, например в течение одного сеанса связи. оритм формирования секретного сеансового ключа блочного фра основывается на использовании односторонней функции ' кретного возведения в степень и сводится к следующему: (5.82) Если а и р известны, то сообщение С нетрудно зашифровать в ,'. тветствии с этим алгоритмом (нетрудно получить Ш как ре: льтат дискретного возведения в степень (13.17)). Даже при очень : льших р Ш(С) вычисляется в результате применения несколь- операций возведения в квадрат и умножения. Например, а53 а32+ «6+4+1 а.а2.
а2 2. а2 2 2 2. а2 2 2 2 2 5 83 ( ) ((( ) ) ) (((( ) ) ) ) ( ) ебует выполнить пять операций умножения типа а" а и три опе' ции перемножения полученных величин. Всего для вычисления ' потребуется примерно 21оя2р (и не более того) операций умжения. Расшифровка для определения С при известном Ш, но еизвестных а и р потребует вычисления обратной функции ) ; е. дискретного логарифмирования.
Доказано, что если не только ' велико, но и (р — 1) имеет большой простой множитель (на:ример, если 0,5(р — 1) — простое число), вычисление дискретого логарифма потребует примерно ~р операций умножения. азумеется, . функция дискретного возведения в степень при некоторых ус'овиях на а, р и оговорках, сделанных относительно (р — 1), дейительно является односторонней функцией. Эти условия свотся к следующим: число р должно быть простым, а число а ~ 11; р1 ким, что все его степени (по пю«1 р) принимают' значения из ' ножества 11: р — 1]. Иначе говоря, а должно быть примитивным 'лементом поля Галуа ОР(р); такие а всегда существуют. Например, р=7 и а=З: а'=3; а2=2; аз=6; а4=4; а5=5; а6=1 (пю«1р=7).
Работу криптосистемы с открытым ключом можно иллюстриовать на примере обмена шифрованными сообщениями между :вумя абонентами. Условно это абоненты А и Б. Предположим, абоненты желают передать друг другу конфиденциальные со:, щения С„и Св соответственно. Для организации такого обмена (5.87) и используют его для шифровки и дешифровки сообщений по добно обычному секретному ключу, т.е.
абонент А формирует крин тограмму Шл из сообщения Сл по правилу: Шл = (Сл+ КльНтодр), (5.88) а абонент Б, получив Шл, восстанавливает (расшифровывает) от крытый текст с использованием того же вычисленного им ключа Кль, так как С„= (Шл+ Кль)(тод р). (5.89) Совершенно аналогично происходит передача шифрованныт сообщений от Б к А: Шь = (С„+ Кль)(п)одр), (5.90) поскольку Сь = (Шь+ Кль)(п)одр). (5.91) Как видно из (13.22), оба абонента могут образовывать иден тичные ключи для защиты информации при обмене сообщения ми. Причем для каждой пары абонентов сети секретной связи бу дет формироваться свой ключ, неизвестный и недоступный лю бой другой паре (даже если в эту пару войдут порознь либо абонент А, либо Б).
Работа системы секретной связи с открьпъ)м ключом на основе дискретного возведения в степень иллюстриру ется блок-схемой (рис. 5.17). Если некто третий (криптоаналитик, работающий на радио разведку) попытается перехватить сообщение, ему прежде всего придется по шифровке Ш определить ключ Кль. Но для вычисления значения ключа ему необходимо знать либо Хл, либо Хь. Зна ние любой из этих величин позволит вычислить Кль, но Хл = 1о8,Пь(пюд р) и Хь = 1оа,Пл(шодр), (5.92) 162 абонент А выбирает случайное число Хл~11; р — Ц и держит его н секрете, но вычисляет значение дискретной экспоненты: ( д р) (5.86) Число Пл сообщается всем, с кем абонент А собирается уста навливать связь. Можно сказать, что в системе связи Пл — эз такой же.реквизит абонента А, как имя, адрес и номер телефона Точно также поступает и абонент Б, но, разумеется, выбирая другое число Хь и вычисляя другое Пь.
Если А и Б обмениваются конфиденциальными сообщениями. каждый из них вычисляет Кль = ахль = (Пл)хь(п)одр) = (Пь)~„(пюд р) инфорйании + а (птос$ р) Источник сообщения Источник сообщения Шифратор Шифратор Дешифратор Сл Получатель сообщения Получатель сообщения Дешифратор Источник Хл Хая= =П~~ (шоб р) Источник Хь =ПР< л р) Рис. 5.17. Система связи с открьпым ключом ' скольку П„и Пь известны. Невозможность (практическая не' можность, т.е. крайняя затруднительность) перехвата сообщеобусловливается трудностью определения секретного ключа ::при помощи вычисления дискретного логарифма. 5.7. Стойкость к имитирующим и дезинформирующим помехам (обеспечение подлинности сообщений) 163 ::. Помехи системам передачи информации могут навязывать по" ателю ложные сообщения, дезинформировать его.
Противодейие такому информационному нападению входит в круг задач иоэлектронной защиты точно так же, как и противодействие мехам, искажающим сигналы, переносящие эти сообщения. Деформируют только те помехи, которые образуют сообщения, обные истинным, и могут быль приняты как подлинные, со"анные собственным источником информации, т.е. дезинфор' рующие помехи должны имитировать истинные сообщения. оэтому защита от дезинформирующих помех иначе называется ' итозащитой, а способность систем и сообщений противостоять йствию дезинформирующих помех — имитостойкостью.
":: Для обеспечения имитостойкости передаваемых сообщений приняются криптографические методы, в некотором, смысле побные тем, что применяются для обеспечения секретности при редачи информации, Но функции обеспечения секретности (ин' рмационной скрытности) и обеспечения подлинности сообений не тождественны друг другу. ':: Устойчивость к расшифровке еще не достаточна для обеспече: я стойкости сообщений к вредному действию имитирующих '', мех. Из того факта, что сообщение не может быть расшифрова(может быть расшифровано лишь с достаточно малой вероят' стью или по прошествии неприемлемо длительного времени) Р > —.
~с и — у (5.93) еще не следует, что в ходе информационной борьбы противник не может создать ложное, дезинформирующее сообщение. Попытка имитации будет успешной, если система противодействия создаст поддельную шифрограмму Ш„и эта шифрограмма на приемной стороне будет принята за истинную, посланную законным абонентом системы связи. Вероятность такого события Р„. Подобно потенциальной криптостойкости можно определить предельно достижимый уровень имитостойкости информации как способность системы обеспечивать подлинность передаваемых сообщений. Пусть Ф вЂ” число всех возможных криптограмм, т.е.
таких криптограмм, априорная вероятность которых (для системы перехвата) не равна нулю Р(Ш) ~ О. Пусть также Фс и Фк — соответственно числа возможных сообщений и ключей, т. е, Р(С) ~ О и Р(К) ~~ О. Это значит, что для каждой последовательности ключа К существует по крайней мере Фс различных криптограмм и условная вероятность криптограммы для каждого ключа не равна нулю Р(Ш! К) ~ О. Следовательно, если противник, желающий создать ложное сообщение, выберет совершенно случайно криптограмму из полного числа Ф (попытается имитировать шифрованное сообщение), вероятность успеха такой имитации будет Р„= Фс~Ф;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
