<< Предыдущая

стр. 23
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

этом ожидаемая длина периода потока ключей Р и с . 5 . 1 1 . Расшифро­
вание в режиме СВС
получается большей, нежели при других значе­
ниях.
Глава 5. Симметричные шифры

Как и ранее, мы разбиваем открытый текст на серию блоков:
mi,

Но на этот раз, в отличие от пре­
дыдущих случаев, блоки состоят из
\У1-\
j битов. Процесс шифрования проис­
r-i ходит по следующей схеме (рис. 5.12).

ч Прежде всего, переменной xi присва­
ивается начальное значение IV, За­
выбор левыху битов
тем, при г = 1, 2, . . . , q', делаются
i
i Q (7 битов шифротекста) преобразования:
t У1 = Ek{xi),
I m, (j битов открытого текста) |
бг = j крайних слева битов блока Уг^
Р и с . 5.12. Шифрование в режи­ Ui =• TTii 0 е^.
ме OFB

Расшифрование происходит ана­
логично (см. рис. 5.13).

5.4.4. Р е ж и м CFB
Последний режим, который мы рас­
и смотрим, носит название «обратной
связи по шифротексту» или СРВ (Ci­
-i pher FeedBack). Он похож на режим
[f^
УА
0 F 5 , но блочный шифр в нем транс­
Ч
^
формируется в поточный. Напомним,
1 выбор левыху битов]
что в предыдущем режиме начало по-
i
1^ rrij и битов шифротекста) тока ключей получается из значения
IV ^ а остальной поток формируется
t пошагово, в результате шифрования
I с, (J битов открытого текста) |
значения шифруюш;ей функции, вы­
Рис. 5.13. Расшифрование в ре­ численного на предыдуш;ей стадии. В
жиме OFB
случае СРВ поток ключей возникает
в результате еще одного шифрования
блоков криптограммы (рис. 5.14):
Уо = IV, Zi = Ekivi-i)
вг = j крайних слева битов блока Zi, Vi = rrii ® ei.
Мы не будем разбирать процедуру расшифрования, оставив ее в
качестве упражнения.
5.5. Подлинность сообщений 149

5.5. Подлинность сообщений
Блочные шифры могут не толь­
ГГГ I.
ко обеспечивать конфиденциальность
сообш;ений, но и контролировать це­ i
лостность данных. Предположим, что
^k
стороны, обмениваюш;иеся секретной
1'
^
информацией, хотят быть уверенны­
выбор левыху битов]
ми в том, что информация при пере­
i
даче не была искажена. Они могут ис­ •
ff^ 1
Q (y битов шифротекста)
пользовать обш;ий (shared) секретный
Т
к л ю ч и а л г о р и т м с к л ю ч о м (напри- |т,- (/ битовоткрытоготекста)!
мер, блочный шифр) для генерирова­
ния контрольного значения, посыла­ Р и с . 5.14. Шифрование в режи­
емого вместе с данными. Такие зна­ ме СРВ
чения называют кодами аутентифи­
кации сообщений, или MAC (Message
Authentication Codes):
MAC = Fk{M),
где F — контрольная функция (check function), к — секретный
ключ, а М — сообщение. При этом мы не предполагаем секрет­
ность сообщения^, поскольку пытаемся на этом этапе сохранить це­
лостность данных, а не их конфиденциальность. Если нам нужно
засекретить сообщение, то его следует зашифровать после вставки
MAC. В результате такой комбинации пользователь передает
Ek{m\\MAC{m)).
Существует несколько различных типов MAC, но наиболее из­
вестная и широко используемая — это СВС-МАС. Этот код обоб­
щает режим СВС блочного шифра. Коды СВС-МАС упоминаются
в различных международных стандартах, изданных в начале 80-ых
годов прошлого столетия. Точности ради стоит отметить, что в
стандартах говорится об использовании алгоритма DES в режиме
СВС для создания системы аутентификации сообщений, хотя, оче­
видно, вместо DES можно брать любой блочный шифр.
Опишем процедуру, в результате которой из п-битового блочно­
го шифра получается т-битовый ( т < п) MAC.
- Сначала данные дополняются так, чтобы их можно было раз­
бить на серию п-битовых блоков.
^Поэтому оно и обозначено заглавной буквой. — Прим. перев.
Глава 5, Симметричные шифры

- Полученные блоки шифруются блочным шифром в режиме СВС,
- Последний из полученных блоков после необязательной заключи­
тельной обработки и отбрасывания лишних битов (при т < п)
является требуемым кодом аутентификации MAC.
Таким образом, если Mi, . . . , Mq — n-битовые блоки данных, то эта­
пы вычисления MAC можно описать так:
oi = Ek{Mi), li = Mi® Oi-i для г = 2, . . . , q, Oi = Ek(li).
Последнее значение Oq подается на вход необязательной заключи­
тельной процедуры, результат которой обрезается до нужного раз­
мера и считается искомым MAC (рис. 5.15).
При пользовании схемой вычисления СВС-
^^ 12
^ щ MAC необходимо осторожно обращаться с
^ ^ начальными дополнениями данных. Между-
ТII народные стандарты предлагают три спосо-
' г˜п ба дополнения:
[^ [^ Ы 1. Все дополняющие символы — нули.
[необязательная!
Этот метод имеет множество недостат-
процедура
4' ков, связанных с тем, что при нем не-
возможно обнаружить добавление, сти-
Рис. 5.15. Схема рабо- рание или перемещение нулей, если не
ты СВС-МАС известна длина оригинального сообще­
ния.
2. В конце всех добавляемых по необходимости нулей вставля­
ется одна единица, сигнализирующая о конце сообщения, если
оно оканчивается строкой нулей.
3. Опять все дополняющие символы — нули. Но на этот раз к со­
общению добавляется специальный блок, содержащий инфор­
мацию о длине исходного текста.
Стандарты предписывают два возможных необязательных за­
ключительных шага, разработанных для усложнения атакующим
поиска ключа методом полного перебора:
1) выбрать ключ ki и вычислить Oq = Ek{Dki{oq));
2) выбрать ключ к2 и вычислить Oq = Ek^ioq),
Другой способ аутентификации основан на криптографических хэш-
функциях (см. §10.3). При этом секретный ключ присоединяется к
сообщению, и вся связка подается на вход хэш-функции. Выход хэш-
функции и есть код MAC.
5.6. Современные поточные шифры 151

5.6. Современные поточные шифры

При шифровании большого объема данных (таких, например, как
речь, или «живое» видео) в реальном времени, требуется что-то бо­
лее быстрое, нежели один из блочных шифров, рассмотренных ра­
нее. Для этих целей подходят поточные шифры. Они, как правило,
похожи на одноразовый шифр-блокнот, с которым мы уже встреча­
лись. Их суть заключается в сложении по модулю 2 битов потока
ключей с битами сообщения. Однако вместо фиксированного пото­
ка ключей, который в ранних поточных шифрах и являлся секрет­
ным ключом, в современных системах поток ключей генерируется
из короткого основного ключа с помощью однозначно определенных
детерминированных алгоритмов.

5.6.1. РСЛОС
Стандартный способ генерирования потока битов основан на ис­
пользовании регистра сдвига с обратной связью. Это микросхема с
ячейками памяти, в каждой из которых записан один бит информа­
ции. Множество таких ячеек и образует регистр. На каждом шаге
содержимое нескольких заранее определенных ячеек, которые на­
зываются отводами^ пропускается через функцию обратной связи.
А ее значение записывается в самую левую ячейку регистра, сдвигая
все остальные его биты на одну позицию вправо. Самый крайний
справа, «вытолкнутый» из регистра, бит — выход регистра сдвига
на данном шаге (рис. 5.16).
По причинам, о которых мы будем го­
ворить позже, в качестве функций обрат- гН-^/-1И/-2Н-з1 ••• H2Hil'^ol-»
ной связи желательно брать нелинейные L| ^фЦия обратной tвяtи ^
функции. Однако это сложно осуществить
на практике, и поэтому пользуются реги- Рис. 5.16. Регистр сдвига с
стром сдвига с линейной обратной сея- ^^Р^'Тнои связью
зъю или, сокращенно, РСЛОС^ функция
обратной связи в котором линейна. Этот регистр устроен так же,
как и общий, описанный выше. Но в качестве функции обратной
связи берется логическая операция XOR исключающего ИЛИ.
На языке математики работу регистра длины / можно описать
следующим образом. Задается последовательность битов [ci, . . . , с/],
в которой на отводах стоят единицы, а в остальных ячейках — ну­
ли. Допустим, что в начальном положении в регистре записана по­
следовательность [5/_1, . . . , 51, 5о]. На выходе регистра получается
Глава 5. Симметричные шифры

последовательность 5о, 5i, 52, . . . , 5/_i, 5/, 5/_|_i,..., где при j ^ I
Sj = Ci • 5j_i 0 C2 • Sj_2 ©•••©€/••• 5j_/.
Заметим, что если в начальном состоянии регистра во всех его ячей­
ках стояли нули, то и на выходе мы будем получать сплошные нули.
Если же стартовал последовательность была нетривиальной, то ге­
нерируемая последовательность, в конечном счете, окажется пери­
одической. Действительно, число возможных последовательностей
длины I конечно, и меняя их на каждом шагу, мы волей-неволей по­
лучим одну из уже встречавшихся. После этого, ввиду детермини­
рованности процесса, мы получим периодичность. Напомним, что
периодом последовательности называется наименьшее натуральное
число АГ, при котором для всех достаточно больших значений пара­
метра i выполняется равенство


Нетрудно подсчитать, что суш;ествует 2^ — 1 разных ненулевых на­
чальных состояний регистра. Поэтому максимум, на что можно рас­
считывать, это на то, что регистр сдвига с линейной обратной свя­
зью при любом ненулевом начальном положении будет генерировать
последовательность битов периода 2^ — 1.
Свойства выдаваемой РСЛОС последовательности тесно связа­
ны со свойствами двоичного многочлена
С{Х) = 1 + ciX + С2Х^ + • • • + ciX^ е F2[X],
ассоциированного с этим регистром. Его ненуле­
вые коэффициенты называются отводами, как и
"* 1 "^3 1 "^2 1 "^l г
соответствуюш;ие ячейки регистра, поставляюш;ие
i значения аргументов функции обратной связи. На
1 е—
—- ' рис. 5.17 изображен РСЛОС^ ассоциированный с
^^' • • ^' многочленом X^-i-X+1. а на рис. 5.18 — с многочле-
ГИСТр сдвига с оо ^Q ^ ТТ П^ТГХ^^
линейной обрат- ^^^ ^ + А " -f-1. На практике применяют РСЛОС
^
ной связью, ас- С примитивным ассоциированным многочленом,
социированный
с многочленом Определение 5Л. Двоичный многочлен С(X) сте-
X 4-Х-hi пени I называется примитивным^ если он неприво­
дим, а его корень в является образующей мульти­
пликативной группы поля F2Z. Иначе говоря, при­
митивный многочлен степени / удовлетворяет двум условиям:
-?2[Х]/{С{Х))=?2{в)=?21,
- F;, = (в).
5.6. Современные поточные шифры

Свойства последовательности битов, г»|^2feiкзо I • • • I -з I "2 Hi !-•
^^
т
генерируемой РСЛОС^ зависят от ассоци-
в<
ированного многочлена:
- Если с т а р ш и й к о э ф ф и ц и е н т ассоци- ^«^-^5.18. Регистр сдвига с
^ линейной обратной связью,
ированного многочлена с/ = О, то не- ассоциированный с много-
риодичность генерируемой последо- членом Х^^ + Х^ + 1
вательности может проявляться не
сразу.
- Если Q = 1, то соответствуюш;ая последовательность называ­
ется неособой. Она будет периодичной с самого начала, т.е.
равенство s^j^i = Si выполнено для всех г, а не только для
достаточно больших. Наиболее интересны неособые последо­
вательности, соответствующие многочленам со следующими
дополнительными свойствами:
• Когда С{Х) неприводим, при любом ненулевом начальном
состоянии регистра период генерируемой последовательно­
сти равен наименьшему числу iV, при котором многочлен
С{Х) делит 1 -I- Х ^ . Как следствие, период последователь­
ности будет делить число 2^ — 1.
• Если С{Х) примитивен, то любое ненулевое начальное со­
стояние регистра дает последовательность с максимально
возможным периодом 2^ — 1.
Опустим доказательство этих утверждений. Его можно найти в
любом хорошем учебнике, посвященном приложениям конечных по­
лей к теории шифрования, криптографии или системам передачи
данных. В качестве примера рассмотрим РСЛОС с ассоциирован­
ным многочленом I + X + Х^, Генерируемая последовательность в
этом случае имеет вид

<< Предыдущая

стр. 23
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>