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

Шифрование: Ci = EK(Pi)
Дешифрование: Pi = DK(Ci)

Pi = DK (Ci) = Pi = DK (EK (Pi))

ECB_Encryption (K,Plaintext bloks)
{
  for(i = 1 to N)
  { 
    Ci <- EK (Pi), 
  }
  return Cliphertext blocks
}

X = EK(PN-1) ->  CN =  headm(X)
Y = PN|tailn-m(X) -> CN-1 = EK(Y)

Режим сцепления блоков шифрованного текста (CBC)

Следующая эволюция в работе режимов — режим сцепления блоков шифрованного текста (CBC — Cipher Block Chaining). В режиме CBC каждый блок исходного текста, прежде чем быть зашифрованным, обрабатывается с помощью проведения операции ИСКЛЮЧАЮЩЕЕ ИЛИ с предыдущим блоком шифра. Когда блок зашифрован, блок передают, но копия сохраняется в памяти, которая используется в шифровании следующего блока. Читатель может задать вопрос о начальном блоке, поскольку перед первым блоком нет блока зашифрованного текста. В этом случае используется фальшивый блок, называемый вектор инициализации (IV). Передатчик и приемник согласуют заданный заранее IV. Другими словами, IV используется вместо несуществующего C0. Рисунок 11.3 показывает режим CBC. На передающей стороне операция ИСКЛЮЧАЮЩЕЕ ИЛИ проводится перед шифрованием; а на стороне приемника дешифрование проводится перед операцией ИСКЛЮЧАЮЩЕЕ ИЛИ.

(рис 11.3) Режим цепочки блоков шифротекста

Соотношение между исходным текстом и зашифрованным текстом показано ниже:

$$Шифрование: \\ C_{0} = IV \\ C_{i} = E_{K}(P_{i} \oplus C_{i-1}) \\ Дешифрование: \\ C_{0} = IV \\ P_{i} = D_{K}(C_{i}) \oplus C_{i-1}$$

Пример 11.4

Можно доказать, что каждый блок исходного текста на стороне Алисы может быть точно восстановлен на стороне Боба — потому что шифрование и дешифрование инверсны друг другу.

$$P_{i} = D_{K}(C_{i}) \oplus C_{i-1} = D_{K} (E_{K}(P_{i} \oplus C_{i-1})) \oplus C_{i-1} = P_{i} \oplus C_{i-1} \oplus C_{i-1} = P_{i}$$

Вектор инициализации (IV)

Вектор инициализации (IV) должен быть известен передатчику и приемнику. Хотя сохранение этого вектора в тайне не требуется, целостность вектора играет важную роль в безопасности режима CBC ; IV помогает сохранить безопасность изменения информации. Если Ева может изменить значения бит IV, это может изменить значения бит первого блока.

Для того чтобы использовать IV, рекомендовано несколько методов. Передатчик может выбрать псевдослучайное число и передать его через безопасный канал (например, использующий режим ECB ). Фиксированное значение может быть согласовано Алисой и Бобом как IV, когда ключ засекречивания установлен. Это может быть часть ключа засекречивания, и так далее.

Проблемы безопасности

В режиме CBC имеются следующие две проблемы безопасности.

Одинаковые блоки исходного текста, принадлежащие тому же самому сообщению, зашифровываются в различные блоки зашифрованного текста. Другими словами, отдельные образцы в блоке не сохраняются. Однако когда два сообщения равны, их шифрованный текст одинаковый, если они используют те же самые IV. Фактически, если первые M блоков в двух различных сообщениях равны и IV совпадает, они будут зашифрованы в одинаковые блоки. По этой причине некоторые специалисты рекомендуют использование для IV метки времени.

Ева может добавить некоторые блоки зашифрованного текста в конце потока зашифрованного текста.

Распространение ошибки

В режиме CBC единственный бит ошибки в блоке Cj зашифрованного текста в процессе передачи — в процессе дешифрования может создать ошибку в большинстве битов блока Pj исходного текста. Однако эта одиночная ошибка изменяет только один бит в исходном тексте блока Pj+1 (бит в том же самом местоположении). Доказательство этого факта оставляем как упражнение. Исходный текст блоков от Pj+2 до PN не затрагивается этим единственным битом ошибки. Единственный бит ошибки в зашифрованном тексте — самовосстанавливаемый.

Алгоритм

Алгоритм 11.2 дает псевдокод для шифрования — процедура encrypt. Она зашифровывает единственный блок (например, DES или AES). Алгоритм дешифрования оставляем как упражнение.

CBC_ Encryption (IV,K, Plaintext bloks)
{
  C0 <- IV
  for (i=1 to N)
  {
    Temp <- Pi ⊕ Ci-1
    Ci <- EK (Temp)
  }
return Ciphertext blocks
}

Захват зашифрованного текста

Методика захвата зашифрованного текста, рассмотренная для режима ECB, может также быть применена к режиму CBC, как это показано ниже.

$$U = P_{N-1} \oplus C_{N-2} \to X = E_{K}(U) \to C_{N} = head_{m}(X) \\ V = P_{N}|pad_{n-m}(0) \to Y = X \oplus V \to C_{N-1} = E_{K}(Y)$$

Функция head — та же самая, что описана в режиме ECB; функция pad вставляет нули.

Приложения

Режим работы CBC может использоваться, чтобы зашифровать сообщения. Однако из-за механизма формирования цепочки параллельная обработка невозможна. Режим CBC не используется при шифровании и дешифровании массивов файлов с произвольным доступом, потому что шифрование и дешифрование требуют доступа к предыдущим массивам. Режим СВС применяется для установления подлинности сообщения.

Режим кодированной обратной связи (CFB)

ECB и режимы CBC предназначены для шифрования и дешифрования блоков сообщений. Размер блока, n, определяется принятым шифром. Например, n = 64 для DES и n = 128 для AES. В некоторых ситуациях мы должны использовать DES или AES как секретные шифры, но исходный текст или размеры блока зашифрованного текста должны быть меньшими. Например, чтобы зашифровать и расшифровывать символы 8 -битового ASCII, вы не захотели бы использовать один из традиционных шифров, обсужденных в лекции 4, потому что они ненадежны. Решение состоит в том, чтобы применить DES или AES в режиме кодированной обратной связи (CFB). В этом режиме размер блока, используемого в DES или AES, — n, но размер исходного текста или блока зашифрованного текста — r, где r <n.

Идея состоит в том, что DES или AES используются не для того, чтобы зашифровать исходный текст или расшифровывать зашифрованный текст, а для того, чтобы зашифровать или расшифровывать содержание регистра сдвига, S, размером n. Шифрование сделано с применением операции ИСКЛЮЧАЮЩЕЕ ИЛИ к r -битовому блоку исходного текста с r -битовым регистром сдвига. Дешифрование сделано с применением операции ИСКЛЮЧАЮЩЕЕ ИЛИ к r -битовому блоку зашифрованного текста с r -битовым регистром сдвига. Для каждого блока регистр сдвига Si выполняет сдвиг регистра Si-1 (предыдущий регистр сдвига) на r бит влево, заполняя самые правые r битов с Ci-1. Тогда Si зашифрован в Ti. Только самые правые r битов Ti обрабатываются с помощью ИСКЛЮЧАЮЩЕГО ИЛИ с исходным текстом, из блока Pi получая Ci. Обратите внимание, что Si, для первого блока — это IV — не сдвигается.

Рисунок 11.4 показывает режим CFB для шифрования; дешифрование то же самое, но роли блоков исходного текста ( Pi ) и блоков зашифрованного текста ( Ci ) меняются местами. Обратите внимание, что шифрование и дешифрование используют функцию шифрования основного блочного шифра (например, DES или AES).

(рис 11.4) Шифрование в режиме кодированной обратной связи В режиме CFB шифрование и дешифрование используют функцию шифрования основного блочного шифра.

Соотношение между исходным текстом и блоками зашифрованного текста показано ниже:

$$Шифрование: C_{i} = P_{i} \oplus SelectLeft_{r} \{ E_{K} [ShiftLeft_{r} (S_{i-1}) | C_{i-1})]\} \\ Дешифрование: P_{i} = C_{i} \oplus SelectLeft_{r} \{ E_{K} [ShiftLeft_{r} (S_{i-i}) | C_{i-i})]\}$$

где ShiftLeft — процедура, которая сдвигает содержание ее параметра на r бит влево (крайние левые r -биты отбрасываются). Оператор | показывает конкатенацию (последовательное соединение). SelectLeft -процедура выбирает только крайние левые r -битов параметра. Возможно доказать, что каждый блок исходного текста на стороне Алисы может быть точно восстановлен на стороне Боба. Это доказательство оставляем как упражнение.

Интересно, что в этом режиме не требуется дополнение блоков, потому что размер блоков, r, обычно выбирается так, чтобы удовлетворить размеру блока данных, который нужно зашифровать (например, символ). Интересное также другое — что система не должна ждать получения большого блока данных ( 64 бита или 128 битов) для того, чтобы начать шифрование. Процесс шифрования выполняется для маленького блока данных (таких как символ), Эти два преимущества приводят к двум недостаткам. CFB менее эффективен, чем CBC или ECB, потому что он применяет шифрование основным блочным шифром маленького блока размером r.

CFB как шифр потока

Хотя CFB — режим, предназначенный для того, чтобы использовать блочные шифры, такие как DES или AES, — он может быть шифром потока. Фактически, это несинхронный шифр потока, в котором ключевой поток зависит от зашифрованного текста. Рисунок 11.5 показывает процесс дешифрования и шифрования и генератор ключей.

(рис 11.5) Шифрование в режиме кодированной обратной связи как шифр потока

Рисунок 11.5 показывает, что основной шифр (DES или AES), ключ шифра ( K ) и предыдущий блок шифра ( Ci ) используются только для того, чтобы создать ключевые потоки ( ki1 k2..., kN ).

Алгоритм

Алгоритм 11.3 дает процедуру для шифрования. Он вызывает несколько других процедур, детали которых оставляем как упражнения. Обратите внимание, что мы написали алгоритм так, чтобы показать характер режима потока (обработка в реальном масштабе времени). Алгоритм выполняется, пока блоки исходного текста не будут зашифрованы.

CFB_Encryption (IV, K, r)
{
  i <- 1
  while (more blocks to encrypt)
  {
  input (Pi) 
  (if i=l)
    S <- IV
  else
    {
    Temp <- shiftLeft(S)
    S <- concatenate (Temp, Ci-1)
    }
  T <- EK(S)
  k <- selectLeftr(T) 
  Ci <- Pi ⊕ ki
  output (Ci)
  i <- i + 1
  }
}

Проблемы безопасности

В режиме CFB есть три первичных проблемы безопасности.

Точно так же как CBC, образцы на уровне блока не сохраняются. Одинаковые блоки исходного текста, принадлежащие одному и тому же самому сообщению, зашифровываются в различные блоки.

Одним и тем же ключом может быть зашифровано больше чем одно сообщение, но тогда значение IV должно быть изменено для каждого сообщения. Это означает, что Алиса должна использовать различные IV каждый раз, когда она передает сообщение.

Ева может добавить некоторый блок зашифрованного текста к концу потока зашифрованного текста.

Распространение ошибки

В CFB ошибка в единственном бите в зашифрованном тексте блока Cj в процессе передачи создает единственный бит ошибки (в той же самой позиции) в исходном тексте блока Pj. Однако большинство битов в следующих блоках исходного текста будут с ошибкой (с 50 -процентной вероятностью), пока биты Cj все еще находятся в регистре сдвига. Вычисление числа затронутых блоков оставляем как упражнение. После того как регистр сдвига полностью регенерирован, система избавляется от ошибки.

Приложение

Режим работы CFB может использоваться, чтобы зашифровать блоки небольшого размера, такие как один символ или бит. Нет необходимости в дополнении, потому что размер блока исходного текста обычно устанавливается ( 8 для символа или 1 для бита).

Специальный случай

Если блоки в тексте и в основном шифре — одного и того же размера ( n = r ), шифрование/дешифрование становится более простым, но построение диаграммы и алгоритм оставляем как упражнение.

Режим внешней обратной связи (OFB)

Режим внешней обратной связи (OFB — OUTPUT FEEDBACK) очень похож на режим CFB, с одной особенностью: каждый бит в зашифрованном тексте независим от предыдущего бита или битов. Это позволяет избежать распространения ошибок. Если при передаче возникает ошибка, она не затрагивает следующие биты. Подобно CFB, и передатчик и приемник используют алгоритм шифрования. Рисунок 11.6 показывает режим OFB.

(рис 11.6) Шифрование в режиме внешней обратной связи

OFB как шифр потока

OFB, так же как и CFB, может создать поточный шифр на базе основного шифра. Однако ключ потока не зависит от исходного текста или зашифрованного текста; значит, шифр потока — синхронный, как это обсуждалось в лекции 7. Рисунок 11.7 показывает шифрование и дешифрование, а также генератор ключей.

(рис 11.7) Шифрование в режиме внешней обратной связи как шифрование потока

Алгоритм

Алгоритм 11.4 дает процедуру шифрования. Этот алгоритм последовательно вызывает другие процедуры, детали которых мы оставляем как упражнение. Заметим, что алгоритм написан так, чтобы показать режим потока (ситуация реального времени). Алгоритм работает, пока все блоки исходного текста не будут зашифрованы.

OFB_Encryption (IV, K, r)
{
  i <- 1
  while (more blocks to encrypt)
  {
  input (Pi)
  if (i=l)
    S <- IV
  else
    {
    Temp <- shiftLeftr(S)
    S <- concatenate (Temp, ki-1)
    }
  T <- Ek(s)
  k, <- selectLeftr (T)
  Ci <- Pi ⊕ ki
  output (Ci)
  i <- i + 1
  }
}

Проблемы безопасности

В режиме OFB имеются следующие две проблемы безопасности.

Точно так же как в режиме CFB, образцы на уровне блока не сохраняются. Одинаковые блоки исходного текста, принадлежащие тому же самому сообщению, зашифровываются в различные блоки.

Любое изменение в зашифрованном тексте затрагивает исходный текст, зашифрованный в приемнике.

Распространение ошибки

Единственная ошибка в зашифрованном тексте затрагивает только соответствующий бит в исходном тексте.

Специальный случай

Если блоки в тексте и основном шифре имеют один тот же размер ( n = r ), шифрование/дешифрование становится более простым, но мы оставляем диаграммы и алгоритм как упражнение.

Режим счетчика (CTR)

В режиме счетчика (CTR — Counter) нет информации обратной связи. Псевдослучайный ключевой поток достигается с помощью счетчика. Счетчик на n бит инициализируется в заранее определенное значение ( IV ) и увеличивается по основному и заранее определенному правилу ( mod 2n ). Чтобы обеспечивать случайность, величина приращения может зависеть от номера блока. Исходный текст и блок зашифрованного текста имеют один и тот же размер блока, как и основной шифр (например, DES или AES). Блоки размера n исходного текста зашифрованы так, чтобы создать зашифрованный текст с блоком размера n. Рисунок 11.8 показывает шифрование в режиме счетчика.

(рис 11.8) Шифрование в режиме счетчика

Отношение между исходным текстом и блоками зашифрованного текста показано ниже.

$$Шифрование: C_{i}=P_{i} \oplus E_{ki} (Счетчик) \\ Дешифрование: P_{i}=C_{i} \oplus E_{ki} (Счетчик)$$

CTR использует функцию шифрования основного блочного шифра ( EK ) и для шифрования, и для дешифрования. Достаточно легко доказать, что блок Pi исходного текста может быть восстановлен из зашифрованного текста Ci. Это мы оставляем как упражнение.

Мы можем сравнить режим CTR с режимами OFB и ECB. Подобно OFB, CTR создает ключевой поток, который независим от предыдущего блока зашифрованного текста, но CTR не использует информацию обратной связи. Так же как ECB, CTR создает n -битовый зашифрованный текст, блоки которого независимы друг от друга — они зависят только от значений счетчика. Отрицательной стороной этого свойства является то, что режим CTR, подобно режиму ECB, не может использоваться для обработки в реальном масштабе времени. Алгоритм шифрования ждет перед шифрованием законченный n -разрядный блок данных. Положительная сторона этого свойства та, что режим, подобно режиму ECB, может использоваться, чтобы зашифровать и расшифровывать файлы произвольного доступа, и значение счетчика может быть связано номером записи в файле.

CTR как шифр потока

CFB, OFB и CTR — фактически шифры потока. Рисунок 11.9 показывает шифрование и дешифрование i-того блока данных.

(рис 11.9) Шифрование в режиме счетчика как шифр потока

Алгоритм

Алгоритм 11.5 содержит процедуру в псевдокоде для шифрования; алгоритм для дешифрования оставляем как упражнение. Здесь значение приращения зависит от номера блока. Другими словами, значения счетчика — IV, IV + 1, IV + 3, IV + 6, и так далее. Предполагается, что все N -блоки исходного текста готовы до начала шифрования, но алгоритм может быть переписан, чтобы избежать этого предположения.

Безопасность

Проблемы безопасности для режима CTR те же самые, что и для режима OFB.

Распространение ошибки

Единственная ошибка в зашифрованном тексте затрагивает только соответствующий бит в исходном тексте.

CTR_Encryption (IV, K, Plaintext blocks)
{
  Counter <-  IV 
  for(i= 1 to N)
  {
    Counter <- (Counter + i - 1)mod 2N 
    ki <- EK (Counter)
    Ci <- Pi ⊕ ki
   } 
  return Ciphertext blocks
 }

Сравнение различных режимов

Таблица 11.1 сравнивает пять различных режимов работы, рассмотренных в этой лекции.

Итоги режимов работы

Режим работы	Описание	Тип результата	Размер блока
ECB	Каждый n-битовый блок шифруется независимо тем же самым ключом	Блочный шифр	n
CBC	То же самое, что и в ECB, но каждый блок сначала складывается (ИСКЛЮЧАЮЩЕЕ ИЛИ) с предыдущим зашифрованным текстом	Блочный шифр	n
CFB	Каждый r-битовый блок складывается (ИСКЛЮЧАЮЩЕЕ ИЛИ) с r-битовым ключом, который является частью предыдущего текста шифра	Шифр потока	r $$\le$$ n
OFB	То же самое, что и в CFB, но регистр сдвига модифицирован с помощью предыдущего r-битового ключа	Шифр потока	r $$\le$$ n
CTR	То же самое, как в OFB, но счетчик используется вместо регистра сдвига	Шифр потока	n

11.2. Использование шифров потока

Хотя эти пять режимов работы допускают использование блочных шифров для шифрования сообщений или файлов в больших модулях (ECB, CBC и CTR) и маленьких модулях (OFB и OFB), иногда необходимо передать поток для того, чтобы зашифровать маленькие единицы информации — символы или биты. Шифры потока более эффективны для обработки в реальном масштабе времени. Некоторые шифры потока использовались в различных протоколах в течение прошлых нескольких десятилетий. Мы рассмотрим только два: RC4 и A5/1.

RC4

RC4 — потоковый шифр, который был разработан в 1984 г. Рональдом Ривестом. RC4 используется во многих системах передачи данных и протоколах организации сети, например, SSL/TLS и IEEE 802.11 (беспроводный стандарт LAN).

RC4 — байт-ориентированный шифр потока, в котором байт ( 8 битов) исходного текста складывается (ИСКЛЮЧАЮЩЕЕ ИЛИ) с байтом ключа, чтобы получить байт зашифрованного текста. Ключ засекречивания, из которого сгенерированы однобайтовые ключи в потоке ключей, может содержать от 1 до 256 байтов.

Матрица состояний

RC4 базируется на понятии матрицы состояний. В каждый момент матрица состояний 256 байтов активизируется, из нее случайным образом выбирается один байт, чтобы служить ключом для шифрования Идея может быть показана в виде массива байтов:

S [0] S [l] S [2] ••• S [255]

Заметим, что индексы диапазона элементов — между 0 и 255. Содержание каждого элемента — байт ( 8 битов), который может интерпретироваться как целое число от 0 до 255.

Идея

Рисунок 11.10 показывает идею RC4. Первые два блока выполняются только один раз (инициализация); перестановки для того, чтобы создавать ключ потока, повторяются, пока есть байты исходного текста, предназначенные для шифрования.

(рис 11.10) Идея шифра потока RC4

Инициализация. Инициализация делается в два шага.

1. На первом шаге матрица состояний инициализируется для значений 0, 1..., 255. Создается также массив ключей K [0], K [1] ..., K [255]. Если ключ засекречивания имеет точно 256 байтов, байты копируются в массив K ; иначе — байты повторяются, пока не заполнится массив K.

for (i = 0 to 255)                                                                
{
  S[i] <- i
  K[i] <- Key [i mod Key Length] 
}

2. На втором шаге инициализированная матрица проходит перестановку (скрэмблирование элементов), основанную на значении байтов в K[i]. Ключевой байт используется только на этом шаге, чтобы определить, какие элементы должны быть заменены. После этого шага байты матрицы полностью перетасованы.

j <- 0
for (i = 0 to 255)
{
  j <- (1 + S[i] + K[i]) mod 256
  swap (S[i] , S[j])
}

Генерация ключевого потока. Ключи k в ключевом потоке генерируются один другим. Сначала элементы матрицы состояний переставляются на основе значений своих элементов и значений двух индивидуальных переменных i и j. Затем значения двух элементов матрицы состояний в позициях i и j используются, чтобы определить индекс элемента матрицы состояний, который служит как ключ k. Следующий код повторяется для каждого байта исходного текста, чтобы создать новый ключевой элемент в ключевом потоке. Переменные i и j инициализируются в 0 прежде, чем будет проведена первая итерация, но значение копируется от одной итерации к следующей.

i <- (i +1) mod 256
j <- (j +S[i]mod256
swap (S [i] , S[j])
k <- S [(S[i] + S[j]) mod 256]

Шифрование или дешифрование. После того как k были создан, байт исходного текста зашифровывается с помощью k, чтобы создать байт зашифрованного текста. Дешифрование представляет собой обратный процесс.

Алгоритм

Алгоритм 11.6 показывает процедуру, написанную на псевдокоде, для RC4.

RC4_Encryption (K)
{
  // Создание начальной матрицы состояний и ключевых байтов
  for (i = 0 to 255)
  {
    S[i] <- i
    K[i] <- Key [i mod Key Length]
  }
 // Перестановка байтов матрицы состояний на основе значений байта ключа
  j <- 0 
  for (i = 0 to 255)
  {
    j <- (j+ S[i] + K[i] mod 256
    замена (S[i] , S[j]) 
    //Непрерывная перестановка байтов, генерация ключей и шифрование 
    i <- 0 
    j <- 0
    while (пока есть байты для шифрования)
    i <- (i + 1) mod 256
    j <- (j +S[i]) mod 256
    swap(S[i],S[j])
    k <- S[(S[i]+S[j])mod256]
   //Ключ готов, шифрование
   input P
   C <- P ⊕ k 
   output C
   }
}

Пример 11.5

Чтобы показать случайность ключа потока, мы используем ключ засекречивания со всеми нулевыми байтами. Ключевой поток для 20 значений A: (222, 24, 137, 65, 163, 55, 93, 58, 138, 6, 30, 103, 87, 110, 146, 109, 199, 26, 127, 163).

Пример 11.6

Повторим пример 11.5, но пусть ключ засекречивания будет пять байтов (15, 202, 33, 6, 8). Ключевой поток — (248, 184, 102, 54, 212, 237, 186, 133, 51, 238, 108, 106, 103, 214, 39, 242, 30, 34, 144, 49). Снова случайность в ключевом потоке очевидна.

Проблемы безопасности

Известно, что шифр безопасен, если размер ключа — по крайней мере, 128 битов ( 16 байтов). Это подтверждается сообщениями о некоторых атаках для малых размеров ключей (меньше, чем 5 байтов). Протоколы, которые сегодня использует RC4, устанавливают размеры ключей, которые делают RC4 безопасным. Однако, как и для многих других шифров, рекомендуется, чтобы для различных сеансов использовались различные ключи. Это препятствует Еве использовать дифференциальный криптоанализ шифра.

A5/1

В этом разделе мы вводим шифр потока, который использует линейный регистр сдвига (см. лекции 9-10, LFSR Linear Feed Back Shift Register), чтобы создать битовый поток: A5/1. A5/1 (член семейства шифров A5) используется в Глобальной Системе Мобильной связи (GSM). Телефонная связь в GSM осуществляется как последовательность кадров на 228 битов, при этом каждый кадр длится 4,6 миллисекунды. A5/1 создает поток бит, исходя из ключа на 64 бита. Разрядные потоки собраны в буфере по 228 битов, чтобы складывать их по модулю два с кадром на 228 битов, как показано на рис. 11.11.

(рис 11.11) Общий вид A5/1

Генератор ключей

A5/1 используются три LFSR на 19,22,23 бита. LFSR , содержащие биты символов и синхронизации показаны на рис 11.12.

(рис 11.12) Три линейных регистра сдвига для AS/5

Однобитовый выход обеспечивает тактовыми импульсами буфер на 228 битов, который используется для шифрования (или дешифрования).

Инициализация. Инициализация выполняется для каждого кадра шифрования (или дешифрования). Она использует ключ засекречивания на 64 бита и 22 бита соответствующего номера кадра. Следующие шаги:

1. Сначала все биты в трех линейных регистрах сдвига устанавливаются в 0.

2. Второй: ключ на 64 бита смешивается со значением регистра согласно следующему коду. Каждый линейный регистр смещается на один шаг ( синхронизация ).

For (i = 0 to 63)
{
  Сложение по модулю 2 K[i] с крайними левыми битами всех трех регистров.
  Синхронизация всех трех линейных регистров сдвига
}

3. Повторить предыдущий процесс, но использовать 22 -битовый кадр.

for (i = 0 to 22)
{
  Сложение по модулю 2 номера кадра [i] с крайними левыми битами всех трех регистров.
  Синхронизация всех трех линейных регистров сдвига
}

4. В течение 100 циклов синхронизируется весь генератор. При этом используется мажоритарная функция (см. следующий абзац), для того чтобы определить, какой линейный регистр сдвига должен быть синхронизирован. Обратите внимание, что иногда синхронизация здесь означает, что два, а то и все три линейных регистра сдвига проходят процесс смещения.

for (i = 0 to 99)
{
  Синхронизация всего генератора, на основе мажоритарной функции
}

Мажоритарная функция. Значение мажоритарной функции ( majority ) с параметрами ( b1 b 2, b3 ) равно 1, если значение большинства битов — 1 ; если это — 0, то ее значение — 0. Например, majority (1, 0, 1) = 1, но majority (0, 0, 1) = 0. Значение мажоритарной функции определяется перед поступлением тактового импульса; три входных бита названы синхронизирующими битами: если самый правый бит равен нулю, это — биты линейных регистров LFSR1 [10], LFSR2 [11] и LFSR3 [11]. Обратите внимание, что в литературе эти биты 8, 10 и 10 отсчитывают слева (как это показано на рис. 11.12). Мы будем рассматривать 10, 11 и 11, считая справа. Это соглашение соответствует месту бита в характеристическом полиноме.

Ключевые биты потока. Генератор ключей создает ключевой поток в один бит при каждом тактовом импульсе. Прежде чем ключ создан, вычисляется мажоритарная функция. Затем каждый линейный регистр сдвига синхронизируется, если его бит синхронизации соответствует результату мажоритарной функции; иначе — он не синхронизируется.

Пример 11.7

В некоторый момент времени биты синхронизации — 1, 0 и 1. Какой должен быть LFSR?

Решение

Результат Majority (1, 0, 1) = 1. LFSR1 и LAFS3 сдвигаются, а LFSR2 — нет.

Шифрование/дешифрование

Разрядные потоки, созданные генератором ключей, записываются в буфер, чтобы потом сформировать ключ на 228 битов, который затем складывает по модулю два с кадром исходного текста, чтобы создать кадр зашифрованного текста. В один момент времени делается шифрование/дешифрование одного кадра.

Проблемы безопасности

Хотя GSM продолжает использовать A5/1, уже были зарегистрированы несколько атак на GSM. Две из них были упомянуты. В 2000 году Алекс Бирюков, Дэвид Вагнер и Эди Шамир показали, что атака в реальном масштабе времени находит ключ за несколько минут на основе известных малых исходных текстов, но это требует этапа предварительной обработки с 248 шагами. В 2003 Экдахи и Джонсон (Ekdahi и Johannson) опубликовали атаку, которая вскрывала A5/1 за несколько минут, используя анализ исходного текста в течение 2-5 минут. Имея в виду некоторые новые атаки GSM, возможно, в будущем нужно будет сменить или укрепить A5/1.

11.3. Другие проблемы

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

Управление ключами

Алиса и Боб должны совместно использовать секретный ключ, чтобы иметь надежную связь с использованием шифра с симметричным ключом. Если есть n объектов в сообществе, каждый из которых хочет связаться с n – 1 другим объектом, то тогда необходимы n (n – 1) ключей засекречивания. Однако при шифровании симметричными ключами один ключ может использоваться в обоих направлениях: от Алисы к Бобу и от Боба к Алисе. Это означает, что нужно только n (n – 1)/2 ключей. Если n — приблизительно миллион, то должны быть выданы почти пятьсот миллионов ключей. Поскольку это нереально, то были найдены несколько других решений. Первое: каждый раз, когда Алиса и Боб хотят связаться, они могут создать между собой сеансовый (временный) ключ. Второе: могут быть установлены один или более центров распределения ключей, чтобы распределять сеансовые ключи для объектов. Все эти проблемы — часть теории управления ключами.

Управление ключами будет обсуждаться в лекции 15.

Генерирование ключей

Другая проблема в шифровании симметричными ключами — безопасная генерация ключа. Различные шифры с симметричным ключом нуждаются в ключах различных размеров. Выбор ключа должен базироваться на гарантии безопасности систематического метода для избежания утечки. Если Алиса и Боб генерируют сеансовые ключи между собой, они должны выбрать ключ случайным образом, так, чтобы Ева не могла предвидеть, каков будет следующий ключ. Если ключи должен распределять ключевой центр, они должны иметь случайный характер, чтобы Ева не могла получить ключ, назначенный Алисе и Бобу, из ключа, назначенного Джону и Еве. Это подразумевает, что нужен генератор случайных (или псевдослучайных) чисел. Поскольку обсуждение генератора случайных чисел включает некоторые темы, которые еще не были рассмотрены, изучение генераторов случайных чисел представлено в приложении K.

Генераторы случайных чисел будут обсуждаться в приложении K.

11.4. Рекомендованная литература

Нижеследующие книги и сайты дают более детальную информацию о предметах, рассмотренных в этой лекции. Пункты, приведенные в квадратных скобках, содержатся в списке в конце книги.

Книги

[Sch99], [Sta06], [PHS03], [Sti06], [MOV97] и [KPS02] рассматривают режимы работы. [Vau06] и [Sta06] дают полные сведения о шифрах потока.

Сайты

Нижеследующие сайты содержат больше информации о темах, обсужденных в этой лекции.

http: // en.wikipedia.org/wiki/Block_cipher_modes_of_operation

http://www.itl.nist.gov/fipspubs/fip81.htm

en.wikipedia.org/wiki/A5/1

en.wikipedia.org/wiki/RC4

11.5. Итоги

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

Самый простой режим работы называется режимом электронной кодовой книги (ECB — ELECTRONIC CODEBOOK). Исходный текст разделен на N блоков. Размер блока — n бит. Каждый блок использует для шифрования и дешифрования один и тот же ключ.

В режиме сцепления блоков шифротекста (CBC — Cipher Block Chaining) каждый блок исходного текста прежде чем зашифровывать, складывают по модулю два с предыдущим блоком зашифрованного текста. Когда блок зашифрован, его передают, но его копия сохраняется в памяти, чтобы ее можно было использовать для шифрования следующего блока. Передатчик и приемник согласуют заранее заданный вектор инициализации ( IV ), чтобы складывать его по модулю два с первым блоком зашифрованного текста.

Чтобы шифровать маленькие модули данных в реальном масштабе времени, применяется режим кодированной обратной связи (CFB — CIPHER FEEDBACK), CFB применяет стандартные блочные шифры, такие как DES или AES, регистр сдвига, но использует операцию сложения по модулю два, чтобы зашифровать или расшифровывать модули данных. Режим CFB использует блочные шифры, но в результате — это шифр потока, потому что каждый модуль данных зашифровывается своим ключом.

Режим внешней обратной связи (OFB) очень похож на режим CFB, с одной разницей — каждый бит в зашифрованном тексте независим от предыдущего бита или битов. Это позволяет избежать распространения ошибки. Вместо того чтобы использовать предыдущий блок зашифрованного текста, OFB берет предыдущий ключ как информацию обратной связи.

В режиме счетчика (CTR) нет информации обратной связи. Псевдослучайность в потоке достигается с помощью счетчика. Счетчик на n битов инициализируется установкой заранее заданного значения ( IV ) и увеличивается по заранее заданному правилу.

Чтобы зашифровать маленькие единицы данных, такие как символы или биты, были разработаны для испытаний несколько шифров потока. Эти шифры потока более эффективны для обработки в реальном масштабе времени. В этой лекции рассматривались только два шифра потока — RC4 и A5/l.

RC4 — шифр потока, ориентированный на байт, в котором байт ( 8 битов) исходного текста надо сложить по модулю два с байтом ключа, чтобы создать байт зашифрованного текста. Секретный ключ, из которого генерируются однобайтовые ключи в ключевом потоке, может содержать от 1 до 256 байтов. Ключевой генератор потока базируется на перестановке 256 байтов.

A5/1 — шифр потока, используемый для мобильной телефонной связи. A5/1 создает поток бит из ключа на 64 бита, используя три линейных регистра сдвига.

11.7. Набор для практики

Обзорные вопросы

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

Перечислите пять режимов работы, рассмотренных в этой лекции.

Определите ECB ( ELECTRONIC CODEBOOK) и перечислите его преимущества и недостатки.

Определите CBC (CIPHER BLOCK CHAINING) и перечислите ее преимущества и недостатки.

Определите CFB (CIPHER FEEDBACK) и перечислите его преимущества и недостатки

Определите OFB (OUTPUT FEEDBACK) и перечислите его преимущества и недостатки.

Определите CTR и перечислите его преимущества и недостатки.

Разделите пять режимов работы на две группы: те, которые используют функции шифрования и дешифрования, — основные шифры (например, DES или AES), и те, которые используют только функцию шифрования.

Разделите пять режимов работы на две группы: те, которые требуют дополнение текста, и те, которые не требуют этого.

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

Объясните основные различия между RC4 и A5/1. Какой из них использует линейный регистр сдвига?

Каков размер модуля данных в RC4? Каков размер модуля данных в A5/1?

Перечислите режимы работы, которые могут быть ускорены параллельной обработкой.

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

Упражнения

Покажите, почему режим CFB создает несинхронный шифр потока, а режим OFB создает синхронный.

Сколько блоков затрагивает единственный бит ошибки в передаче в режиме CFB?

В режиме ECB бит 17 в зашифрованном тексте блока 8 разрушен в течение передачи. Найдите возможные разрушенные биты в исходном тексте.

В режиме CBC биты 17 и 18 в зашифрованном тексте блока 9 в процессе передачи были разрушены. Найдите возможные разрушенные биты в исходном тексте.

В режиме CFB биты 3-6 в зашифрованном тексте блока 11 разрушены ( r = 8 ). Найдите возможные разрушенные биты в исходном тексте.

В режиме CTR блоки 3 и 4 полностью разрушены. Найдите возможные разрушенные биты в исходном тексте.

В режиме OFB полный зашифрованный текст блока 11 разрушен ( r = 8 ). Найдите возможные разрушенные биты в исходном тексте.

Докажите, что исходный текст, используемый Алисой, может быть восстановлен Бобом в режиме CFB.

Докажите, что исходный текст, используемый Алисой, может быть восстановлен Бобом в режиме OFB.

Докажите, что исходный текст, используемый Алисой, может быть восстановлен Бобом в режиме CTR.

Покажите диаграмму для шифрования и дешифрования в режиме CFB, когда r = n.

Покажите диаграмму для шифрования и дешифрования в режиме OFB, когда r = n.

Покажите процесс, используемый для алгоритма дешифрования в режиме ECB, если применяется захват зашифрованного текста (CTS).

Покажите диаграммы шифрования и дешифрования для режима ECB (только последние два блока), когда используется захват зашифрованного текста (CTS).

Покажите процесс, используемый для алгоритма дешифрования в режиме CBC, если применяется захват зашифрованного текста (CTS).

Покажите шифрование и диаграмму дешифрования для режима CBC (только последние два блока), когда используется захват зашифрованного текста (CTS).

Объясните, почему нет потребности в захвате зашифрованного текста в режимах CFB, OFB и CTR (CIPHER FEEDBACK, OUTPUT FEEDBACK).

Покажите эффект распространения ошибки, когда ECB (ELECTRONIC CODEBOOK) использует методику CTS.

Покажите эффект распространения ошибки, когда CBC использует методику CTS.

Режим Формирование цепочки блоков является вариантом, в котором все предыдущие блоки зашифрованного текста перед шифрованием складываются по модулю два с текущим исходным текстом. Выведите рисунок-диаграмму, которая показывает шифрование и дешифрование.

Режим размножения Цепочка блоков шифротекста (PCBC) является вариантом CBC, в котором перед шифрованием предыдущий блок исходного текста и предыдущий блок зашифрованного текста складывается по модулю два с текущим блоком исходного текста. Нарисуйте диаграмму, которая показывает шифрование и дешифрование.

Режим Цепочка блоков шифротекста с контрольной суммой (CBCC) является вариантом CBC, в котором все предыдущие блоки исходного текста перед шифрованием складываются по модулю два с текущим блоком исходного текста. Нарисуйте диаграмму, чтобы показать шифрование и дешифрование и проиллюстрировать процедуру.

В RC4 покажите первые 20 элементов ключевого потока, если ключ засекречивания — 7 байтов со значениями 1, 2, 3, 4, 5, 6 и 7. Вы можете при желании написать маленькую программу.

В RC4 найдите значение для ключа засекречивания, который не изменяет матрицу состояний после первого и второго шагов инициализации.

Алиса обменивается сообщениями с Бобом, используя в RC4 для засекречивания 16 -байтовый ключ засекречивания. Ключ засекречивания изменяется каждый раз, используя рекурсивное определение K = (Ki-1+Ki-1 )mod 2128. Покажите, сколькими сообщениями они могут обменяться перед тем, как текст начнет повторяться.

В A5/1 найдите максимальный период каждого линейного регистра сдвига.

В A5/1 найдите значение следующих функций. В каждом случае показать, сколько синхронизируется линейных регистров сдвига.

Majority (1, 0, 0)

Majority (0, 1, 1)

Majority (0, 0, 0)

Majority (1, 1, 1)

В A5/1 найдите выражение для мажоритарной функции.

Напишите алгоритм дешифрования в псевдокоде для режима ECB.

Напишите алгоритм дешифрования в псевдокоде для режима CBC.

Напишите псевдокод алгоритма дешифрования для режима CFB.

Напишите алгоритм дешифрования в псевдокоде для режима OFB.

Напишите алгоритм дешифрования в псевдокоде для режима CTR.

Напишите алгоритм для shiftleft -процедуры, используемой в алгоритме 11.4.

Напишите алгоритм для selectleft -процедуры, используемой в алгоритме 11.4.

Напишите алгоритм для процедуры конкатенации, используемой в алгоритме 11.4.