Криптография, введение в предмет

    Криптографическим преобразованием T для алфавита Z_m называется последовательность автоморфизмов: T={T⁽ⁿ⁾:1£n<¥}

    T⁽ⁿ⁾: Z_m,n®Z_m,n, 1£n<¥

    Каждое T⁽ⁿ⁾ является, таким образом, перестановкой n-грамм из Z_m,n.

    Поскольку T⁽ⁱ⁾ и T^(j) могут быть определены независимо  при i¹j, число криптографических преобразований исходного текста размерности n равно (mⁿ)!¹. Оно возрастает непропорционально при увеличении m и n: так, при m=33 и n=2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.

    Практическая  реализация криптографических систем требует, чтобы преобразования {T_k: kÎK} были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).

    1.2. Системы подстановок

    Определение Подстановкой p на алфавите Z_m называется автоморфизм Z_m, при котором буквы исходного текста t замещены буквами шифрованного текста p(t):

    Z_m à Z_m; p: t à p(t).

    Набор всех подстановок называется симметрической группой Z_m è будет в дальнейшем обозначаться как SYM(Z_m).

    Утверждение SYM(Z_m) c операцией произведения является группой, т.е. операцией, обладающей следующими свойствами:

    Замкнутость: произведение подстановок p₁p₂ является подстановкой:

    p: tàp₁(p₂(t)).

    Ассоциативность: результат произведения p₁p₂p₃ не зависит от порядка расстановки скобок:

    (p₁p₂)p₃=p₁(p₂p₃)

    Существование нейтрального элемента: постановка i, определяемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Z_m) по операции умножения: ip=pi для "pÎSYM(Z_m).

    Существование обратного: для любой подстановки p существует единственная обратная подстановка p^-1, удовлетворяющая условию

    pp^-1=p^-1p=i.

      Число возможных подстановок  в симметрической группе Z_m называется порядком SYM(Z_m) и равно m! .

    Определение. Ключом подстановки k для Z_m называется последовательность элементов симметрической группы Z_m:

    k=(p₀,p₁,...,p_n-1,...), p_nÎSYM(Z_m), 0£n<¥

    Подстановка, определяемая ключом k, является криптографическим преобразованием T_k, при помощи которого осуществляется преобразование n-граммы исходного текста (x₀ ,x₁ ,..,x_n-1) в n-грамму шифрованного текста (y₀ ,y₁ ,...,y_n-1):

    y_i=p(x_i),   0£i<n

    где n – произвольное (n=1,2,..). T_k называется моноалфавитной подстановкой, если p неизменно при любом i, i=0,1,..., в противном случае T_k называется многоалфавитной подстановкой.

    Примечание. К наиболее существенным особенностям подстановки T_k относятся следующие:

    1. Исходный текст  шифруется посимвольно. Шифрования n-граммы (x₀ ,x₁ ,..,x_n-1) и ее префикса (x₀ ,x₁ ,..,x_s-1) связаны соотношениями

    T_k(x₀ ,x₁ ,..,x_n-1)=(y₀ ,y₁ ,...,y_n-1)

    T_k(x₀ ,x₁ ,..,x_s-1)=(y₀ ,y₁ ,...,y_s-1)

    2. Буква шифрованного текста y_i является функцией только i-й компоненты ключа p_i  и i-й буквы исходного текста x_i.

    1.3. Подстановка Цезаря

    Подстановка Цезаря является самым простым вариантом  подстановки. Она относится к  группе моноалфавитных подстановок.

    Определение. Подмножество C_m={C_k: 0£k<m} симметрической группы SYM(Z_m), содержащее m подстановок

    C_k: j®(j+k) (mod m), 0£k < m,

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

    Умножение коммутативно, C_kC_j=C_jC_k=C_j+k, C₀ – идентичная подстановка, а обратной к C_к является C_k^-1=C_m-k, где 0<k<m. Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки C₃.

    Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный  текст”. Для C₃ подстановки приведены в Табл. 1. Стрелка (à) означает, что буква исходного текста (слева) шифруется при помощи C₃ в букву шифрованного текста (справа).

    Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x₀, x₁ ,..,x_n-1) в n-грамму шифрованного текста (y₀ ,y₁ ,...,y_n-1) в соответствии с правилом

    y_i=C_k(x_i), 0£i<n.

    Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством  подстановки C₃ преобразуется в еюыолхиврсеюивцнгкгрлб.

Аàг	Йàм	Тàх	Ыàю
Бàд	Кàн	Уàц	Ьàя
Вàе	Лàо	Фàч	Эà_
Гàж	Мàп	Хàш	Юàа
Дàз	Нàр	Цàщ	Яàб
Еàи	Оàс	Чàъ	_àв
Жàй	Пàт	Шàы
Зàк	Рàу	Щàь
Иàл	Сàф	Ъàэ

 

    Таблица 1.1: Применение подстановки Цезвря.

    При своей несложности система легко  уязвима. Если злоумышленник имеет 

    1) шифрованный и соответствующий исходный текст или

    2) шифрованный текст выбранного злоумышленником исходного текста,

    то  определение ключа и дешифрование исходного текста тривиальны.

    Более эффективны обобщения подстановки  Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм² (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

    1.4.Многоалфавитные  системы. Системы  одноразового использования

    Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных.

    Многоалфавитная подстановка определяется ключом p=(p₁,  
p₂, ...), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением. Пусть {K_i: 0£i<n} – независимые случайные переменные с одинаковым распределением вероятностей,

    принимающие значения на множестве Z_m

    Pкл{(K₀, K₁, ..., K_n-1)=(k₀, k₁, ..., k_n-1)}=(1/m)ⁿ

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

    X=(X₀, x₁, ..., x_n-1)

    в шифрованный текст

    Y=(Y₀, y₁, ..., y_n-1)

    при помощи подстановки Цезаря

    Y_i=C_Ki(x_i)=(K_i+X_i) (mod m)   i=0...n-1                            (1)

    Для такой системы подстановки используют также термин “одноразовая лента” и “одноразовый блокнот”. Пространство ключей К системы одноразовой подстановки является вектором рангов (K₀, K₁, ..., K_n-1) и содержит mⁿ точек.

    Рассмотрим  небольшой пример шифрования с бесконечным  ключом. В качестве ключа примем текст

      “БЕСКОНЕЧНЫЙ_КЛЮЧ....”.

    Зашифруем с его помощью текст “ШИФР_НЕРАСКРЫВАЕМ”. Шифрование оформим в таблицу: 

ШИФРУЕМЫЙ_ТЕКСТ	24	8	20	16	19	5	12	27	9	32	18	5	10	17	18
БЕСКОНЕЧНЫЙ_КЛЮЧ	1	5	17	10	14	13	5	23	13	27	9	32	10	11	30
ЩРДЪАТТССЦЪЫДФЬП	25	13	4	26	0	18	17	17	22	26	27	4	20	28	15

 

    Исходный  текст невозможно восстановить без  ключа.

    Наложение белого шума в виде бесконечного ключа  на исходный текст меняет статистические характеристики языка источника. Системы  одноразового использования теоретически не расшифруемы³, так как не содержат достаточной информации для восстановления текста.

    Почему  же эти системы неприменимы для  обеспечения секретности при  обработке информации? Ответ простой - они непрактичны, так как требуют  независимого выбора значения ключа  для каждой буквы исходного текста. Хотя такое требование может быть и не слишком трудным при передаче по прямому кабелю Москва - Нью-Йорк, но для информационных оно непосильно, поскольку там придется шифровать многие миллионы знаков.