ГЛАВА 5. КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ
Основная проблема, возникающая при использовании крип- тосистем с секретным ключом, рассмотренных в гл. 2, –
проблема распределения ключей. Учитывая, что процедуры за- шифрования и расшифрования выполняются с помощью одного и того же ключа, в системе с n абонентами потребуется
2 1
-
n
n
ключей, которые не только должны быть сгенерированы, но и надежным образом распределены среди всех участников инфор- мационного обмена. Необходимость наличия недоступных для противника секретных каналов для обмена ключами делает та- кой подход к построению системы секретной связи чрезвычайно дорогостоящим мероприятием, практически не применимым в коммерческих сетях связи, в региональных и глобальных ин- формационных системах и, естественно, абсолютно недоступен частным лицам. Другой принципиальный недостаток криптоси- стем с секретным ключом – невозможность разрешения кон- фликтов. При их возникновении арбитр оказывается в безвыход- ной ситуации, так как секретную ключевую информацию
AB
k
знают как минимум двое участников информационного обмена.
А это означает, что в рамках системы, показанной на рис. 2.1, невозможно обеспечить юридическую значимость пересылаемых электронных документов.
Еще в сороковых годах прошлого столетия К. Шеннон пред- ложил строить шифр таким образом, чтобы задача его вскрытия была эквивалентна решению некоей математической задачи, требующего объема вычислений, недоступного для современных компьютеров. Реализация этой идеи стала возможной, когда в
1976 г. Диффи и Хеллман предложили принципиально новый способ организации секретной связи без предварительного об- мена ключами, так называемое шифрование с открытым ключом.
При этом для зашифрования и расшифрования используются разные ключи и знание одного из них не дает практической воз- можности определить второй. В результате ключ зашифрования может быть сделан открытым без потери стойкости шифра, и лишь ключ расшифрования держится получателем в секрете.
154
5.1. Односторонние функции
Базовым в новом направлении криптографии является поня- тие односторонней функции [4]. По заданному аргументу x лег- ко вычислить значение этой функции F(x), в то же время опре- деление x из F(x) трудновычислимо, иначе говоря, нет алгорит- ма для решения этой задачи с полиномиальным временем рабо- ты. Теоретически x по известному значению F(x) можно найти всегда, используя метод полного перебора, т.е. проверяя по очереди все возможные значения x до тех пор, пока соответст- вующее значение F(x) не совпадет с заданным. Однако практи- чески при значительной размерности множества X такой под- ход неосуществим.
Итак, односторонней функцией называется функция
Y
X
F :
, обладающая двумя свойствами:
1)
существует полиномиальный алгоритм вычисления зна- чений F(x), иначе говоря, задача нахождения значений
y = F(x) при известных значениях x вычислительно раз- решима;
2)
не существует полиномиального алгоритма инвертиро- вания функции F, т.е. задача нахождения значений x по известным значениям y = F(x) вычислительно неразре- шима.
До сих пор ни для одной функции кандидата на звание одно- сторонней не доказано, что она действительно является одно- сторонней.
Пример кандидата на звание односторонней функции –
модульное возведение в степень, т.е. функция
p
x
F
x
mod , где p – большое простое число, – примитивный элемент поля
p
GF
. То, что эта функция может быть эффективно вычислена даже при разрядности параметров в несколько сотен знаков, можно показать на примере:
25
можно вычислить с помощью всего лишь шести операций умножения (умножением считается и возведение в квадрат), так как
155 2
2 2
2 25
При вычислении
pxmod взятие модуля во избежания получе- ния очень больших чисел следует делать после каждого умноже- ния. Пусть
l – разрядность экспоненты
x, тогда при вычислении
pxmod по приведенному в [3] рекурсивному алгоритму потре- буется выполнить от
l до 2
l модульных операций умножения:
function expmod ( ,
x,
p)
if x = 0
then return 1
if x = 0 mod2
then return ppxmod
,
2
,
expmod
2
else return ( expmod ( ,
x – 1,
p) mod
p Задача вычисления функции, обратной модульному возведе- нию в степень, называется
задачей дискретного логарифмирова-ния. На сегодняшний день неизвестно ни одного эффективного алгоритма вычисления дискретных логарифмов больших чисел.
Односторонняя функция в качестве функции зашифрования неприменима, так как, хотя
F(
x) – надежно зашифрованное со- общение
x, никто, в том
числе и законный получатель, не сможет восстановить
x. Обойти эту проблему можно с помощью
одно-сторонней функции с секретом (one-way trapdoor function). Та- кова, например, функция
YXEk:
, имеющая обратную
XYDk:
, однако узнать обратную функцию только по
kE без знания секрета
k невозможно.
Таким образом, односторонней функцией с секретом
k назы- вается функция
YXEk:
, зависящая от параметра
k и обла- дающая тремя свойствами:
1)
при любом
k существует полиномиальный алгоритм вы- числения значений
xEk;
2)
при неизвестном
k не существует полиномиального алго- ритма инвертирования
kE ;
156 3)
при известном k существует полиномиальный алгоритма инвертирования
k
E .
Функцию
k
E можно использовать для зашифрования инфор- мации, а обратную ей функцию
k
D – для расшифрования, так как при всех
X
x
справедливо
x
x
E
D
k
k
При этом подразумевается, что тот, кто знает, как зашифро- вывать информацию, вовсе не обязательно должен знать, как расшифровывать. Так же, как и в случае с односторонней функ- цией, вопрос о существовании односторонних функций с секре- том открыт. Для практической криптографии найдено несколько функций, кандидатов на звание односторонней функции с секре- том. Для них второе свойство не доказано, однако известно, что задача инвертирования эквивалентна некоторой хорошо изучен- ной и давно известной трудной математической задаче. Это оз- начает, что второе требование к односторонней функции с сек- ретом заменяется более слабым условием: при неизвестном k
вероятно не существует полиномиального алгоритма инверти- рования
k
E .
Применение рассмотренных функций для шифрования ин- формации позволяет [3, 4, 29]: избавится от необходимости надежных (а точнее, аутентич- ных) каналов связи для предварительного обмена ключами; свести проблему взлома шифра к решению трудной матема- тической задачи, т.е., в конечном счете, принципиально по- другому подойти к обоснованию стойкости криптосистемы; решать средствами криптографии задачи, отличные от шиф- рования, например задачу обеспечения юридической значи- мости электронных документов.
5.2. Модель криптосистемы с открытым ключом
Криптосистема с открытым ключом (public key cryptosystem)
(рис. 5.1), основанную на применении односторонних функций с секретом, можно реализовать следующим образом. Пользова- тель B, который хочет получать конфиденциальные сообщения,
157 должен выбрать одностороннюю функцию
BE с секретом
(ключом)
Bk . Он сообщает всем заинтересованным описание своей функции зашифрования
BE , например, публикует его в справочнике открытых ключей. При этом ключ
Bk , а, следова- тельно, и алгоритм расшифрования
BD держатся в секрете. Ес- ли теперь пользователь
A хочет послать
B секретное сообщение
m, то он находит в справочнике функцию
BE , а затем вычисля- ет
mEcB и посылает шифротекст
c по открытому каналу пользователю
B. Последний, зная секрет
Bk , т.е. умея инверти- ровать
BE , определяет
m по полученному
c, вычисляя
cDmB. Противник, не зная ключа
Bk , в силу второго свой- ства односторонней функции с секретом не сможет прочитать секретную информацию. В отличие от криптосистемы с секрет- ным ключом, если абонент
A, зашифровав некоторое сообще- ние
m для абонента
B, сохранит шифротекст
c, но потеряет
m или забудет его содержание, он не будет иметь никаких пре- имуществ перед противником в раскрытии исходного текста
m по известному
c.
Атаки на криптосистему с открытым ключом аналогичны атакам на криптосистемы с секретным ключом,
однако следует помнить, что в первом случае противник всегда знает открытый ключ, а значит, всегда возможна атака на основе выбранного открытого текста. Кроме того, возможна так называемая атака с проверкой текста (verifiable text attack): если число возможных открытых текстов невелико, противник, зная открытый ключ, может заранее заготовить соответствующие им шифротексты, а затем, сравнивая с ними перехваченные шифровки, получать соответствующие последним открытые тексты. Исключить та- кой вид атак на криптосистему позволяет
вероятностное шиф-рование.
Шифрование с открытым ключом может использоваться в тех из рассмотренных в гл. 2 режимах, которые для зашифро- вания и расшифрования используют разные функции соответ-
158 ственно
k
E и
k
D (например, ECB и CBC, при этом, очевидно, что второй вариант предпочтительней).
Зашифрование
E
B
(m)
Расшифрование
D
B
(c)
m
c
c
m
Абонент
А
(отправитель)
Абонент
В
(получатель)
Противник
W
Открытый канал связи
Справочник открытых ключей
Генератор ключевой пары
Секретный ключ получателя k
В
(ключ расшифрования)
k
B
Открытый ключ получателя k
B
(ключ зашифрования)
(secret)
(public)
(public)
Рис. 5.1.Модель криптосистемы с открытым ключом
Наиболее известные системы с открытым ключом: рюкзачная криптосистема (Knapsack Cryptosystem); криптосистемаRSA; криптосистема Эль-Гамаля (ElGamal Cryptosystem); криптосистема, основанная на свойствах эллиптических кривых.(Elliptic Curve Cryptosystem (ECCS)).
Криптосистема Т. Эль-Гамаля, основанная на сложности решения задачи дискретного логарифмирования, послужила основой для создания старых российского и американского стандартов электронной подписи. Остальные криптосистемы будут рассмотрены ниже.
5.3. Открытое распределение ключей
Помимо принципа построения асимметричных криптосистем
Диффи и Хеллман предложили протокол выработки общего
секретного ключа, т.е. процедуру взаимодействия по открыто-
159 му каналу связи удаленных абонентов A и B, обладающую сле- дующими свойствами: в конце процедуры у A и B появляется общая секретная информация (общий секретный ключ
AB
k
), которой до на- чала действия протокола не было; противник, способный перехватывать все сообщения и знающий цель протокола, не может восстановить сформи- рованный секретный ключ.
Этот протокол, на первый взгляд невозможный, основывает- ся на задаче дискретного логарифмирования, рассмотренной выше. Противник, который хочет узнать формируемый секрет- ный ключ, вынужден решать именно эту трудную математиче- скую задачу. Пусть p – большое простое число,
– примитив- ный элемент поля
p
GF
(основы теории конечных полей даны в гл. 8). Числа p и считаются общедоступными. Тогда про- цедура получения общей секретной информации имеет сле- дующий вид.
Протокол выработки общего секретного
ключа Диффи–Хеллмана
1.
Абоненты A и B независимо друг от друга вырабатыва- ют два случайных числа соответственно
A
x и
B
x , кото- рые держат в секрете.
2.
Абоненты A и B вычисляют значения
p
y
A
x
A
mod и
p
y
B
x
B
mod .
3.
Абоненты A и B обмениваются сообщениями
A
y и
B
y .
4.
A, получив сообщение
B
y , вычисляет значение
p
p
y
A
B
A
x
x
x
B
mod mod
;
5.
B, получив сообщение
A
y , вычисляет значение
p
p
y
B
A
B
x
x
x
A
mod mod
6.
Элемент
p
GF
, равный
p
B
A
x
x
mod , объявляется об- щим секретным ключом.
160
5.4. Электронная цифровая подпись Диффи и Хеллман предложили использовать односторон- нюю функцию с секретом для
цифровой подписи сообщений, которая позволила бы, например, устанавливать истину при возникновении споров относительно авторства пересылаемых важных документов. Традиционная криптосистема с секретным ключом (см. рис. 2.1) не может быть использована для разре- шения противоречий, возникающих между не доверяющими друг другу абонентами, так как секретная информация (ключ), используемая для зашифрования сообщений, известна как ми- нимум двум лицам. Поэтому пересылка по линиям связи пла- тежных документов или информации, требующей нотариально- го заверения, в этом случае чревата большими неприятностями.
Если
kE – односторонняя функция с секретом, то подписан- ное сообщение можно представить в виде пары
,
,
mDmkгде
m – подписываемый документ, а
kD – функция, обратная
kE . Из определения односторонней функции с секретом следу- ет, что для такой подписи характерны следующие особенности: подписать сообщение
m может только обладатель секрета
k, т.е. подделать подпись практически невозможно; проверить подпись может любой абонент, знающий функ- цию
kE , так как проверка подписи заключается в проверке равенства
mDEmkk; при возникновении споров относительно авторства сооб- щений отказаться от
подписи нельзя из-за невозможности ее подделки; подпись позволяет контролировать
целостность подпи- санных документов, а значит, их можно безо всякого ущерба пересылать по открытым каналам связи.
Если необходимо обеспечить секретность, можно применить следующий
протокол цифровой подписи. Пусть у каждого из двух абонентов
A и
B имеется пара взаимно-обратных функций –
161 открытая функция зашифрования E и секретная функция рас- шифрования D. Если абонент А хочет послать подписанное со- общение абоненту В, то он, используя сначала свой секретный ключ, а затем открытый ключ получателя, вычисляет
m
D
E
c
A
B
и передает шифротекст c абоненту B. Получатель сообщения, используя сначала свой секретный ключ, а затем открытый ключ абонента А, восстанавливает исходный текст, вычисляя
c
E
D
m
A
B
Теперь при возникновении спорной ситуации, когда А отка- зывается от посланного сообщения, он обязан предъявить ар- битру свой секретный ключ. Арбитру необходимо лишь прове- рить равенство
c
D
m
D
B
A
В случае его выполнения он убеждается, что никто, кроме А, отправить сообщение не мог, и принимает решение в пользу В.
Приведенный протокол заставляет быть честным и абонента В.
Для того чтобы исказить принятое сообщение m на
,
m'
ему не- обходимо изменить и подпись
m
D
s
A
на
m'
D
s'
A
. Но для этой операции необходим секретный ключ абонента А, которо- го у В нет.
Приведенная последовательность применения функций
A
D и
B
E единственна возможна. Если абонент А попытается по- слать В «подписанное» сообщение вида
,
m
E
D
c
B
A
противник W, перехватив это сообщение, используя открытый ключ абонента А, сможет вычислить
,
m
E
c
E
B
A
а затем, ис- пользуя свой закрытый ключ, послать якобы подписанное им сообщение
m
E
D
c
B
W
Тогда В, вычислив
,
m
c
E
D
W
B
162 был бы убежден, что m подписано именно W. Таким образом, в рассматриваемой ситуации противник всегда может подписы- вать сообщения, содержимое которых он сам прочитать не в состоянии.
Общий недостаток всех криптосистем с открытым ключом – низкое быстродействие, поэтому на практике применяются мо- дифицированные схемы цифровой подписи, в значительной степени решающие данную проблему. Эти схемы будут рас- смотрены далее.
5.5. Криптосистема, основанная на задаче
об укладке рюкзака
Создание данной системы шифрования и ее модификаций чаще всего связывают с именами Р. Меркля и М. Хеллмана.
Прототипом трудной математической задачи, лежащей в ее ос- нове, является следующая ситуация.
Имеются рюкзак и множество предметов, которые хотелось бы захватить с собой, отправляясь в поход. Требуется найти подмножество предметов, которые заполнят рюкзак до отказа.
Рассмотрим пример простой числовой задачи такого типа.
Простая задача об укладке рюкзака
Представить число 55 в виде суммы некоторых из чисел
{3, 8, 12, 2, 32, 59}.
Ответ: 55 = 3 + 8 + 12 + 32.
Итак, число 55 равно сумме первого, второго, третьего и пя- того чисел из представленного списка. Данный факт можно за- писать следующим образом:
111010 55
. При этом можно решить обратную задачу: если известна последовательность
(111010), можно восстановить число 55, суммируя первое, вто- рое, третье и пятое числа из заданного списка. Таким образом, на основе списка чисел можно построить примитивную систему шифрования, как показано на рис. 5.2.
163
Абонент
А(отправитель)
Абонент
В(получатель)
111010 55
EkDk111010
Рис. 5.2. Примитивная система шифрования, в которой отправителю и получателю известен список чисел {3, 8, 12, 2, 32, 59}
Еще более простая задача об укладке рюкзака получается в том случае, если каждое число в списке больше суммы всех предыдущих, стоящих справа, например, являются степенями двойки.
Очень простая задача об укладке рюкзака Представить число 26
в виде суммы различных чисел из списка {32, 16, 8, 4, 2, 1}.
Ответ: 26 = 16 + 8 + 2 или
011010 26
По сути, решение задачи сводится к переводу заданного де- сятичного числа в двоичную систему счисления, обратная же задача суть перевод заданного двоичного числа в десятичную систему счисления.
Теперь можно сформулировать основные принципы получе- ния односторонней функции с секретом и построения на ее ос- нове криптосистемы с открытым ключом на основе задачи об укладке рюкзака:
1)
составляется трудная задача T, не решаемая за поли-номиальное время;
2)
из T выделяется легкая подзадача easyT, имеющая поли-номиальный или даже более простой алгоритм реше-ния;
3)
путем «взбивания» легкая задача easyT превращается в труднорешаемую задачу shuffleT, не имеющую никакого сходства с easyT;
164 4)
на основе
shuffle
T
определяется открытая функция за-
шифрования; процедура получения
easy
T
из
shuffle
T
дер-
жится в секрете;
5)
криптосистема конструируется таким образом, чтобы
для противника процедура дешифрования заключалась в
решении
shuffle
T
, имеющей вид трудной задачи T, а закон-
ный получатель, знающий секрет, решал бы легкую за-
дачу
easy
T
Предположим, что список
1 2
1
-
,
,
,
a
a
a
n
состоит из ста
40-значных чисел, т.е. t = 100, и c – 42-значное число.
Трудная задача T об укладке рюкзака
Дан список чисел
0 1
1
-
,
,
,
,
,
a
a
a
a
i
n
.
Представить число c в виде суммы некоторых чисел
i
a из
списка.
Если числа в списке выбраны случайным образом, для отве- та на вопрос, какие из них в сумме дают c, необходимо пере- брать
100 2
различных вариантов. Если использовать этот список в системе шифрования, аналогичной показанной на рис. 5.2, она была бы надежной, но законный получатель не смог бы восстановить переданное ему сообщение.
Необходима задача об упаковке рюкзака с секретом, кото- рую мог бы легко решить законный получатель информации, а для противника она бы выглядела по-прежнему трудноразре- шимой. Сначала составим легкую задачу
easy
T
об укладке рюк- зака, для чего выбираем числа
,
,
,
,
,
,
0 1
1
-
a
a
a
a
i
n
содержащие в десятичной записи степени двойки.
Схема соответствующей системы шифрования на основе списка
165 031608
,
120802
,
260405
,
220209
,
020105 4
3 2
1 0
a
a
a
a
a
показана на рис. 5.3. Второй и третий разряды каждого числа
i
a из списка содержит степень двойки
i
2 , первые разряды всех чи- сел в данном примере содержат нули. В общем случае нулевые разряды должны стоять не только правее, но и левее степеней двойки, чтобы после сложения любого количества чисел из спи- ска в результате переносов не исказилась сумма этих степеней.
«Взбивание» задачи
easy
T
и получение
shuffle
T
можно выпол- нить с помощью операции модульного умножения. Выберем два больших взаимно простых числа r и s и найдем такое число t, чтобы выполнялось условие
r
st
mod
1
. Уничтожим список
0 1
1
-
,
,
,
,
,
a
a
a
a
i
n
и число s, предварительно получив новый список
,
,
,
,
,
,
0 1
1
-
b
b
b
b
i
n
каждый элемент которого суть результат умножения соответст- вующего число из первоначального списка на s по модулю r:
r
sa
b
i
i
mod
,
1
,
0 n
i
Числа из нового списка будут казаться случайными числами из интервала
1
;
0 r
, и все, кто не знает принцип их получе- ния, примут соответствующую задачу
shuffle
T
за трудную задачу об укладке рюкзака. Именно она будет применяться при зашиф- ровании информации, поэтому список
,
,
,
,
,
,
0 1
1
-
b
b
b
b
i
n
сообщается всем заинтересованным лицам. Числа t и r держатся в секрете. Таким образом, получим следующую систему шифро- вания.
166
Абонент А
(отправитель)
Абонент В
(получатель)
11001 172515
E
k
D
k
11001 020105 120802 031608 172515
_______
+
172515 25
(11001)
Рис. 5.3. Примитивная система шифрования на основе легкой задачи об укладке рюкзака
Криптосистема на основе задачи об укладке рюкзака
Открытый ключ зашифрования: список
0 1
1
-
,
,
,
,
,
b
b
b
b
i
n
Закрытый ключ расшифрования: пара чисел
r
t ;
Алгоритм зашифрования двоичного сообщения
0 1
1
-
,
,
,
,
,
m
m
m
m
m
i
t
:
1 0
n
i
i
i
k
c
m
b
m
E
Алгоритм расшифрования закрытого сообщения c:
1)
составляем произведение
r
m
a
r
m
tb
tc
n
i
i
i
n
i
i
i
mod mod
1 0
1 0
;
2)
решая легкую задачу об укладке рюкзака, находим
0 1
1
-
,
,
,
,
,
m
m
m
m
m
i
n
Пример шифрования по приведенной схеме показан на рис. 5.4.
167
a
5
= 101
a
4
= 002
a
3
= 104
a
2
= 008
a
1
= 016 1
0 1
0 1
b
5
= 089
b
4
= 028
b
3
= 131
b
2
= 112
b
1
= 224 14 mod 265
Легкая задача об укладке рюкзака
Трудная задача об укладке рюкзака
Исходное сообщение
089 131 224 444
+
____
E
k
444
D
k
444 19 =
= 221 mod 265 21
(10101)
1 0
1 0
1
Расшифрованное сообщение
Зашифрованное сообщение
Рис. 5.4. Пример рюкзачной криптосистемы
К сожалению, некоторые варианты этой оригинальной и красивой криптосистемы были раскрыты вскоре после своего создания.
5.6. Криптосистема RSA
Система RSA, название которой происходит от первых букв фамилий авторов – Р. Ривеста, А. Шамира и Л. Адлемана
(R. Rivest, A. Shamir, L. Adleman), является наиболее распро- страненной и изученной криптосистемой с открытым ключом.
Она основана на использовании того факта, что легко пере- множить два больших простых числа, в то же время крайне трудно разложить на множители их произведение. В результате произведение может быть использовано в качестве элемента открытого ключа зашифрования. Исходные простые числа не- обходимы для расшифрования, при этом задача их восстанов- ления до сих пор сопротивляется всем атакам криптоаналити- ков. Таким образом, имеются хорошие предпосылки для по- строения односторонней функции с секретом.
Рассмотрим некоторые математические факты, на которых основан алгоритм. Согласно малой теореме Ферма, если p – простое число, то для любого x, взаимно простого с p, справед- ливо
;
mod
1 1
p
x
p
для любого x, справедливо
168 mod p
x
x
p
Функция
n натурального аргумента n, равная количеству положительных целых чисел, меньших n и взаимно простых с n, называется функцией Эйлера. Для нее справедливы сле- дующие соотношения:
,
;
1
;
1 1
1
b
a
ab
p
p
p
r
r
где p – простое, r, a и b – натуральные,
1
, b
a
. Эти свойства позволяют легко вычислять
n , когда известно разложение n на простые множители. Если натуральное число e удовлетворя- ет условию
1
,
n
e
, то существует единственное натураль- ное число
n
d
, для которого справедливо
n
de
mod
1
Пусть
pq
n
, где p и q – два больших различных простых числа, и
1
,
n
x
. Тогда согласно теореме Эйлера для лю- бого натурального x выполняется сравнение
n
x
x
ed
mod и, следовательно,
x
n
x
ed
mod при условии
n
x
Итак, выберем два больших различных простых числа p и q и число e, взаимно-простое с числом
1 1 q
p
. Вычислим
pq
n
и найдем такое d, что
1 1
mod
1
q
p
de
Тогда рассматриваемая криптосистема выглядит следующим образом.
169
Криптосистема RSA
Открытый ключ зашифрования: числа n и e.
Закрытый ключ расшифрования: числа p, q и d.
Алгоритм зашифрования сообщения m:
c
n
m
m
E
e
k
mod
Алгоритм расшифрования закрытого сообщения с:
m
n
c
c
D
d
k
mod
Примечание. Необходимым условием является уничтожение чисел p и q после вычисления ключей e и d.
Единственный способ найти алгоритм расшифрования
k
D при известных e и n состоит в том, чтобы разложить на про- стые множители число n, найти p и q, а следовательно, и d.
Правильный выбор разрядности чисел p и q (первоначально авторы RSAпредлагали в качестве p и q использовать не ме- нее чем 40-разрядные десятичные числа) делает задачу факто- ризации n практически неосуществимой.
Пример шифрования по приведенной схеме показан на рис. 5.5.
Абонент А
(отправитель)
Абонент В
(получатель)
0101 14
E
k
D
k
0101 5
7
mod 33 =
= 78125 mod 33 =
= 14 14 3
mod 33 =
= 2744 mod 33 = 5
Рис. 5.5. Пример шифрования по схеме RSA
Авторы RSA при описании принципов функционирования своей системы выбрали в качестве исходного текста фразу
«ITS ALL GREEC TO ME»
(«Для меня все это совершенно непонятно»).
Для того чтобы преобразовать этот текст в одно большое число, закодировали пробел между словами 0, букву А – 1, бук-
170 ву В – 2, букву С – 3, ... , букву Z – 26. На представление каж- дого символа выделили пять двоичных разрядов. В результате приведенной фразе стало соответствовать число
m
= 09201900011212000718050511002015001305.
Для шифрования авторы выбрали e = 9007 и n =
11438162575788886766923577997614661201021829672124236 25626518429357069352457338978305971235639587050589890 75147599290026879543541.
После зашифрования получили число
n
m
c
e
mod
19993513149780510045231712274026064742320401705839146 31037037174062597160894892750439920962672582675012893 554461353823769748026.
Число n было произведением 64-значного и 65-значного простых чисел p и q, выбранных случайным образом.
Если исходный текст слишком велик, чтобы с ним можно бы- ло обращаться как с одним числом, то его следует разбить на блоки и каждый блок рассматривать как отдельное число, при этом необходимо использовать шифрование со сцеплением бло- ков (режим CBC).
При разработке криптосистемы сначала выбираются два раз- личных простых числа p и q. Для этого произвольно выбирается нечетное число r подходящего размера (например, сторазрядное) и проверяется на простоту. В случае, если тест дает отрицатель- ный результат, проверяется число r + 2 и т.д. Существует при- близительно
99 99 100 100 10
ln
10 10
ln
10 100-разрядных простых чисел.
Учитывая, что всего существует
2 10 10 99 100 100-разрядных нечетных чисел, вероятность успеха одного конкретного теста равна приблизительно 0,00868. После того как p и q выбраны, кандидаты на e проверяются с помощью алгоритма Евклида. Ко- гда e удовлетворяет условию
1
,
n
e
, цепочка равенств, по- лучаемых в результате применения алгоритма Евклида, дает нам и значение d. Процедура шифрования суть модульное возведе- ние в степень, данную операцию следует осуществлять методом
171 последовательного возведения в квадрат, т.е. после каждого воз- ведения в квадрат результат берется по модулю r. При этом ни- когда не возникают числа большие
2
n [3].
5.7. Криптосистема Эль-Гамаля
Криптосистема Эль-Гамаля – асимметричная криптографиче- ская схема шифрования, предложенная Тахиром Эль-Гамалем в
1984 г. (Taher ElGamal, «A Public-Key Cryptosystem and a Signature
Scheme Based on Discrete Logarithms», IEEE Transactions on Infor- mation Theory, v. IT-31, n. 4, 1985, pp. 469–472).
Криптосистема может быть определена над любой цикличе- ской группой G. Защищенность схемы основана на сложности решения задачи дискретного логарифмирования.
Алгоритм генерации ключей:
1)
породить мультипликативную циклическую группу G степени q с образующей g: выбрать простое число q – степень криптосистемы; сформировать случайное g, g < q;
2)
выбрать случайное x, x < q;
3)
вычислить h = g
x
mod q.
Открытый ключ = (h, g, q).
Закрытый ключ = x.
Алгоритм зашифрования:
1)
подготовить шифруемое сообщение m, m < q;
2)
выбрать случайное y, y < q;
3)
вычислить с
1
= g
x
mod q, c
2
= m h
y
mod q.
Криптограмма – (с
1
, с
2
).
Алгоритм расшифрования:
1)
вычислить
q
c
c
m
x
mod
1 2
Расшифрование будет верным, поскольку
m
g
mg
g
mh
c
c
m
xy
xy
xy
y
x
1 2
172
Криптостойкость системы Эль-Гамаля зависит от свойств груп- пы G и особенностей конкретной реализации. Схема уязвима к ата- кам с подобранным шифротекстом. К примеру, имея криптограмму
(с
1
, с
2
) некоторого (возможно, неизвестного) сообщения m, легко создать криптограмму (с
1
, 2с
2
) сообщения 2m.
Шифрование по схеме Эль-Гамаля является вероятностным, другими словами, каждому исходному сообщению может соот- ветствовать множество достоверных шифротекстов за счет про- извольности выбора y.
5.8. Гибридные криптосистемы
Несмотря на все преимущества криптосистем с открытым ключом, ни одна из известных на сегодняшний день их реализа- ций не может конкурировать по быстродействию с криптосисте- мами с секретным ключом. Так, например, быстродействие сис- темы RSA в тысячи раз ниже быстродействия DES. В результате при шифровании длинных информационных последовательностей может случиться так, что применение асимметричного алгоритма недопустимо снижает скорость информационного обмена, а при- менение симметричного невозможно из-за отсутствия общего секретного ключа у участников этого обмена или по каким-то другим причинам. Выходом из этой ситуации является использо- вание гибридной криптосистемы (рис. 5.6, 5.7).
В схеме, показанной на рис. 5.6, на начальном этапе участни- ки информационного обмена (абоненты А и В), используя прото- кол выработки общего секретного ключа, формируют общую секретную информацию (сеансовый ключ
AB
k
). На следующем этапе для обмена зашифрованными сообщения используется криптосистема с секретным ключом.
Схема, показанная на рис. 5.7, предполагает наличие у каждо- го участника информационного обмена двух ключей: открытого
public
k
и закрытого
secret
k
. Рассмотрим процесс пересылки не- коего документа m. Отправитель (абонент А) вырабатывает сек- ретный ключ – случайное число, используемое только один раз, и поэтому называемое одноразовым или сеансовым ключом. Се-
173 ансовый ключ используется для зашифрования документа m при помощи симметричного криптоалгоритма, после этого он за- шифровывается на открытом ключе получателя (абонент В) и присоединяется к ранее зашифрованному документу. Сформиро- ванное таким образом сообщение отсылается получателю. По- следний, получив сообщение, повторяет те же процедуры, но в обратном порядке. С помощью своего секретного ключа получа- тель восстанавливает сеансовый ключ, а затем с его помощью расшифровывает и сам документ.
Генератор ПСЧ абонента А
Генератор ПСЧ абонента В
x
A
x
B
ω
x
mod n
y
A
ω
x
mod n
y
B
y
B
x
mod n
k
AB
Абонент А
(отправитель)
Сообщение m
Зашифрование
E
AB
(m)
Зашифрованное сообщение c
Расшифрование
D
AB
(c)
m
Абонент B
(получатель)
A
A
B
y
A
x
mod n
B
k
AB
Рис. 5.6. Первый вариант схемы гибридного шифрования
174
Абонент А
(отправитель)
Документ m
Зашифрование документа
Сеансовый ключ
k
AB
Генератор ПСЧ абонента А
(генератор ключей)
Открытый ключ абонента В
k
B
Зашифрованное сообщение
Зашифрование сенсового ключа
E
AB
(m)
E
B
(k
AB
)
E
AB
(m)
E
B
(k
AB
)
Документ m
Сеансовый ключ
k
AB
(secret)
(public)
Закрытый ключ получателя
k
B
Расшифрование сеансового ключа
Расшифрование документа
Абонент В
(получатель)
Рис. 5.7. Второй вариант схемы гибридного шифрования
175
5.9. Генераторы ПСЧ на основе односторонних функций
с секретом
Криптографически стойкие генераторы ПСЧ могут быть по- строены на основе односторонних функций с секретом.
М. Блюм и С. Микали для обозначения основного требования к криптостойкому генератору ПСЧ ввели понятие непредсказуе-
мость (unpredictable) или непредикативность влево – криптоа- налитик, знающий логику работы такого генератора, имеющий возможность анализировать его выходную последовательность, но не знающий используемого инициализирующего вектора
(синхропосылки), для определения первого выработанного бита не может предложить лучшего способа, чем подбрасывание жребия.
Справедливы следующие утверждения [3, 4]:
непредикативный влево генератор является криптогра-
фически сильным;
криптографически сильные генераторы существуют то-
гда и только тогда, когда существуют односторонние
функции.
Рассмотрим, например, так называемый ВВS-генератор, по- лучивший свое название в честь авторов Э. Блюм, М. Блюма и
М. Шуба, основанный на криптосистеме Блюма.
Пусть p и q – два больших простых числа примерно одина- кового размера, причем
4
mod
,
4
mod
q
p
Тогда число n = pq называется целым числом Блюма. Пусть
*
n
Z
– множество целых положительных чисел, меньших n, которые не делятся ни на p, ни на q. Пусть
n
QR – подмножество
,
*
n
Z
со- стоящее из квадратичных вычетов по модулю n. Число элемен- тов множества
*
n
Z равно (p – 1)(q – 1), причем в точности чет- вертую их часть составляют элементы подмножества
n
QR Каж- дый элемент
n
QR имеет ровно четыре различных квадратных корня в
,
*
n
Z
из них лишь один, называемый примитивным, принадлежит
n
QR
176
Пример 5.1. Если
p = 19,
q = 23; имеем
n = 437. Тогда
;
139
,
135
,
7 19 133
*
437
*
437
*
437
ZZZкроме того, учитывая, что не существует такого целого числа
a, что
,
437
mod
35 2
aа
,
437
mod
39 24 2
можно записать
139
,
135 437 437
QRQRКвадратными корнями из 139 по модулю 437 являются числа
24, 185, 252 и 413, при этом 24 – примитивный квадратный ко- рень, так как
437
mod
24 47 2
Задача определения примитивных квадратных корней по модулю числа n вычислительно эквивалентна задаче разложе-ния этого числа на множители. Таким образом, получаем кан-
дидата на одностороннюю функцию с секретом, поскольку функция
nxxfmod
2
эффективно вычисляется, а произвести обратное преобразова- ние может лишь тот, кто знает секрет – разложение
n на мно- жители.
Пусть
n – целое число Блюма.
Генератор Э. Блюм–
М. Блюма–
Шуба 1.
Выберем в качестве инициализирующего вектора слу- чайное число
0
nQRx Для этого возьмем такое случай- ное число
x, что
,
1
,
nx и вычислим mod
2 0
nxx2.
Искомой последовательностью бит длиной
m будет по- следовательность
,
1
,
0
,
1 2
1 0
0
,
mibbbbbxBBSmimnгде
ib – младший бит числа
,
ix
177 mod
2 1
n
x
x
i
i
Важным достоинством этого генератора является то, что при знании разложения n на множители он допускает прямое опре-
деление отдельных бит, которые в нем вырабатываются. Имеем mod
2 0
n
x
x
i
i
По теореме Эйлера
,
mod
1 1
1
n
x
q
p
а значит,
,
mod
1 1
mod
2 0
n
x
x
q
p
i
i
т.е. с помощью двух операций модульного возведения в сте- пень, которые эффективно вычисляются, любое число
i
x мо- жет быть найдено исходя лишь из начального вектора
0
x и индекса i.
Аналогичным образом можно построить генератор ПСЧ на основе другой односторонней функции с секретом, например лежащей в основе криптосистемы RSA, т.е. на основе функции mod n
x
x
f
e
Генератор RSA
1.
Выберем в качестве инициализирующего вектора слу- чайное число
*
0
n
Z
x
2.
Искомой последовательностью бит длиной m будет яв- ляться последовательность
,
1
,
0
,
1 2
1 0
0
,
m
i
b
b
b
b
b
x
RSA
m
i
m
n
где
i
b –младший бит числа
,
i
x
mod
1
n
x
x
e
i
i
Ш. Гольдвассер и С. Микали предложили схему шифрова- ния, основанную на использовании BBS-генератора в качестве источника ключевой последовательности. Данная схема не
обеспечивает секретности по отношению к атаке на основе
выбранного шифротекста.
178
Пусть исходное сообшение M суть m-разрядная битовая по- следовательность,
0
x – случайный квадратичный вычет по мо- дулю n. Функция зашифрования по схеме Гольдвассер–Микали имеет вид
,
,
0
,
x
BBS
M
x
c
m
n
m
при этом
m
x включается в шифротекст для того, чтобы закон- ный получатель мог его расшифровать. Простейший алгоритм расшифрования в данном случае может заключаться в восста- новлении ПСП в обратном направлении в соответствии с ре- куррентным уравнением
,
mod
1
n
x
x
i
i
а затем получении исходного текста по формуле
0
,
x
BBS
c
M
m
n
Знание множителей p и q позволяет законному получателю сразу из
m
x получить
,
0
x а затем формировать ПСП точно так же, как это делал отправитель.
Алгоритм вычисления x
0
из x
m
1.
С помощью обобщенного алгоритма Евклида вычисляем такие целые числа a и b, что
1
bq
ap
2.
Вычисляем
;
1
mod
4 1
p
p
m
;
1
mod
4 1
q
q
m
;
mod mod
p
p
x
u
m
;
mod mod
q
q
x
v
m
mod
0
n
bqu
apv
x
Таким образом, эффективность рассмотренной схемы выше эффективности схемы RSA. Более того, тщательный анализ
BBS-генератора показал, что после каждой операции модуль-
179 ного возведения в квадрат можно использовать приблизительно
L
2
log младших битов числа
i
x , где L – разрядность модуля n [3].
Контрольные вопросы
1.
Кто инициатор создания двухключевой криптосистемы: отправитель или получатель?
2.
Назовите два принципиальных недостатка двухключе- вых криптосистем.
3.
Что такое односторонняя функция? Приведите пример.
4.
Что такое односторонняя функция с секретом? Приве- дите пример.
5.
На чем основана стойкость криптосистемы RSA?
6.
Приведите пример создания криптосистемы RSA.
7.
На чем основана стойкость ранцевой криптосистемы?
8.
На чем основана стойкость криптосистемы Эль-Гамаля?
9.
Приведите пример создания криптосистемы Эль-Гамаля.
Скачать 3.04 Mb.