Способ аутентифицированного шифрования
AUTHENTICATED CODING METHOD

Область техники, к которой относится изобретение
Предлагаемое изобретение относится к криптографии и средствам защиты информации и может быть использовано для реализации как аутентифицированного шифрования, так и просто аутентификации сообщения.
Уровень техники
Способы аутентифицированного шифрования работают с сообщениями, которые состоят из несекретной и секретной части. Они позволяют одновременно зашифровать секретную часть сообщения и получить для всего сообщения имитовставку.
Известны способы аутентифицированного шифрования сообщений, представленных в цифровом виде, а именно в виде двоичных данных, выполняемые с использованием блочного шифрования с секретным ключом и уникального вектора инициализации, например, способ аутентифицированного шифрования GCM (Galois/Counter Mode; NIST Special Publication 800-38D, November 2007, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC).
Для дальнейшего рассмотрения введем обозначения:
- операция конкатенации двух векторов А и В, результатом является вектор, в котором левая часть совпадает с вектором А, а правая часть совпадает с вектором В;
[b]
0двоичная строка из b нулевых битов, где b - целое положительное число;
⊕ - операция покомпонентного сложения по модулю 2 двух двоичных строк одинаковой длины;
n
⊗ - операция умножения в конечном поле Галуа GF(2) с порождающим многочленом этого поля;
Е(K, М) - алгоритм блочного зашифрования сообщения М с секретным ключом K;
n - длина блока;
K - ключ шифрования длины k бит;
F - ключ финализации длины k бит;
S - уникальный вектор инициализации длины S бит, т.е. для всех сообщений, зашифрованных на одном ключе шифрования K, значение S должно быть различным;
- ассоциированные данные (несекретная часть сообщения), состоящие из r блоков;
- открытый текст (секретная часть сообщения), состоящий из m блоков;
М - сообщение (двоичный вектор), которое состоит из ассоциированных данных А и открытого текста Р;
Т - имитовставка сообщения М длины t бит;
16
с - запись константы с в 16-ричной системе счисления;
len(M) - длина сообщения М(в байтах);
{ } - двоичная строка, длина которой равна нулю;
|М| - длина сообщения М (в битах);
d
L(u) - слово из первых d символов слова u, d≤|u|;
U mod N -для целого U и натурального N остаток от деления U на N;
32
incr(Y) - прибавление единицы к правым 32 битам слова Y и взятие результата по модулю 2.
64
64
39
71
Способ GCM включает два этапа использования: аутентифицированное шифрование и расшифрование с проверкой имитовставки. Для реализации способа необходимы алгоритм блочного шифрования Е с длиной блока 128 бит и с секретным ключом K длины k бит и синхропосылка S длины 5 бит, 1≤s≤2. Способ применяют к сообщению М, которое состоит из ассоциированных данных А и открытого текста Р, длина ассоциированных данных не должна превышать 2 бита, а длина открытого текста не должна превышать (2-256) бита, при этом суммарная длина ассоциированных данных и открытого текста, защищенных на одном ключе не должна превышать 2 бита.
Перед началом реализации способа ассоциированные данные и открытый текст записывают в виде:
r+m+1
i
Для осуществления способа необходима вспомогательная функция GHASH: GHASH(Н, A, С) = Х, где переменные X, i=0, …, r+m+1 определяют следующим образом:
В результате этапа выполнения аутентифицированного шифрования получают шифртекст с, длина которого совпадает с длиной открытого текста, и имитовставку Т длины t бит, 64≤t≤128, для сообщения М. Аутентифицированное шифрование происходит следующим образом:
K
[128]
H=E(0),
i
i-1
Y=incr(Y), i=1, …, m,
i=1, …, m-1,
Этап расшифрования и проверки имитовставки для ассоциированных данных А, шифртекста С и имитовставки Т осуществляют следующим образом:
K
[128]
Н=Е(0),
i
i-1
Y=incr (Y), i=1, …, m,
i=1, …, m,
Если значения T и T' совпали, то в результате этого этапа получают открытый текст Р, иначе получают специальный признак ОШИБКА.
Недостатком способа GCM является снижение стойкости, возникающее из-за уязвимости к атакам на имитовставку, использующим свойства линейности (Ferguson N. Authentication weaknesses in GCM. Comments submitted to NIST Modes of Operation Process, 2005, статья по адресу: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf) и свойства цикличности многочленов (Markku-Juhani Olavi Saarinen. Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes. In Anne Canteaut, editor, Fast Software Encryption, volume 7549 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2012), кроме того, для алгоритма известен ряд атак с усеченной длиной имитовставки (рассмотрены в указанной выше статье Ferguson N.) и с повторяющимися векторами инициализации (Joux A. Authentication Failures in NIST version of GCM. Comments submitted to NIST Modes of Operation Process, 2006, статья по адресу: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/800-38_Series-Drafts/GCM/Joux_comments.pdf).
64
Известен и другой способ аутентифицированного шифрования, согласно стандарту СТБ 34.101.31-2011 (Государственный стандарт Республики Беларусь СТБ 34.101.31-2011. Информационные технологии и безопасность. Защита информации. Криптографические алгоритмы шифрования и контроля целостности). Способ состоит из этапа установки защиты и этапа снятия защиты, для его реализации на обоих этапах необходимы одни и те же алгоритм блочного шифрования Е с длиной блока 128 бит и с секретным ключом K длины 256 бит и синхропосылка S длины 128 бит. Защиту устанавливают для сообщения М, которое состоит из ассоциированных данных А и открытого текста Р, длина открытого текста и ассоциированных данных не должна в сумме превышать 2 бита. В результате установки защиты получают шифртекст С, длина которого совпадает с длиной открытого текста, и имитовставку Т длиной 64 бита для сообщения М. Перед началом выполнения способа ассоциированные данные и открытый текст записывают в виде:
i
i
i
i
При шифровании блокам Р ставятся в соответствие блоки С, |С|=|P|, из которых потом составляется шифртекст С.
На этапе установки защиты выполняют следующие действия:
0
1. Вычисляют Y=E(K, S)
2. Для i=1, 2, …, m выполняют:
i
i-1
128
1) Y=Y+l(mod2),
2)
3. Устанавливают
0
16
Н=Е(K, Е(K,S)), q=B194BAC80A08F53B366D008E584A5DE4
4. Для i=1, …, r вычисляют:
5. Для i=1, 2, …, m вычисляют:
6. Вычисляют
7. Вычисляют
64
r+m+2
8. Вычисляют Т=L(q)
9. Возвращают (С, Т)
Защиту снимают для ассоциированных данных А, шифртекста С и имитовставки Т. В результате этапа снятия защиты получают либо признак ОШИБКА, либо расшифрованный открытый текст Р, причем получение признака ОШИБКА означает нарушение целостности данных.
На этапе снятия защиты выполняют следующие действия:
1. Устанавливают
0
16
H=Е(K, Е(K, S)), q=В194ВАC80А08F53B366D008Е584А5DE4
2. Для i=1, …, r вычисляют:
3. Для i=1, 2, …, m вычисляют:
4. Вычисляют
5. Вычисляют
64
r+m+2
6. Если Т≠L(q), то возвращают ОШИБКА.
0
7. Устанавливают Y=Е (K, S)
8. Для i=1, 2, …, m выполняют:
i
i-1
128
1) Y=Y+1(mod2),
2)
9. Возвращают Р
Для разных криптографических приложений зачастую требуется различная длина имитовставки, поэтому одним из недостатков способа СТБ является фиксированная длина имитовставки равная 64 битам.
Другим недостатком известного способа является недостаточная скорость выполнения в некоторых вариантах реализации. Кроме того, использование умножения длины сообщения на ключ имитозащиты, потенциально может привести к снижению стойкости способа к криптографическим атакам.
Способ аутентифицированного шифрования СТБ 34.101.31-2011 выбран в качестве прототипа.
Раскрытие изобретения
Технический результат заключается в повышении криптографической стойкости способа аутентифицированного шифрования и повышении скорости выполнения способа.
Для этого предлагается способ, ранее описанный (Бабуева А.А., Науменко А.П. О подходах к анализу схем аутентифицированного шифрования, построенных с использованием умножения в конечных полях. Конференция РусКрипто'2018, материал по адресу: https://www.ruscrypto.ru/resource/archive/rc2018/files/02_Babueva_Naumenko.pdf).
Для реализации способа необходимы способ блочного шифрования Е(K, М) с длиной блока n бит, n кратно 32, n≥64, ключ шифрования K длиной k бит, k≥128, ключ финализации F длиной k бит и вектор инициализации S длиной s бит,  Ключи K и F должны быть выработаны случайно (псевдослучайно), равновероятно и независимо друг от друга. Для вектора инициализации должно быть выполнено требование уникальности, т.е. он должен быть различен для всех сообщений, зашифрованных на одном и том же ключе.
Сообщение М включает в себя:
i
• ассоциированные данные А, разделенные на г блоков A, 0<i≤r, имеющие в составе хотя бы один ненулевой блок, причем r - целое положительное число
причем длина ассоциированных данных должна быть кратна 8 битам;
i
• и, возможно, открытый текст Р, разделенный на m блоков Р, 0<i≤m, причем m - целое число,
1
m-1
m
|P|=…=|P|=n, |P|≤n,
длина открытого текста должна быть кратна 8 битам;
причем выполняется соотношение
Суммарное количество блоков ассоциированных данных и открытого текста, обработанных на одном ключе не должно превышать
Способ состоит из 4-х этапов: шифрования, выработки имитовставки, расшифрования и проверки имитовставки. В результате шифрования и выработки имитовставки способ выдает неизмененные ассоциированные данные, зашифрованный текст, длина которого совпадает с длиной открытого текста, и имитовставку Т длины t бит, 1≤t≤n, значение t выбирают перед использованием способа и не меняют в процессе его использования;
Шифрование происходит следующим образом:
получают последовательность значений счетчиков:
i
i-1
Y =incr(Y), 2≤i≤m
получают шифртекст , длина которого совпадает с длиной открытого текста, выполняя следующие действия:
i=1, …, m-1,
0
Заметим, что начальное значение счетчика получается как , т.е. не нужно выполнять зашифрования вектора инициализации как в способе-прототипе, где Y=E(K, S), что позволяет начать этап шифрования, как только получено сообщение.
Выработка имитовставки для сообщения М происходит следующим образом:
если длина последнего блока ассоциированных данных меньше n, то дополняют этот блок:
если длина последнего блока шифртекста меньше n, то дополняют этот блок:
вычисляют значение имитозащитной группы Z:
вычисляют ключ имитозащиты Н:
[n]
Н=Е(K, 0);
1
вычисляют значение вектора q:
вычисляют значения векторов
j=2, …, r-1,
при r>1,
i=1, …, m-1,
m>0,
вычисляют
причем для размещения len(Р) выделяют  двоичных разрядов, а для размещения Len(A) выделяют  двоичных разрядов;
вычисляют значение имитозащитной группы Z:
используют t младших бит имитозащитной группы Z в качестве имитовставки Т.
В результате этапа шифрования и выработки имитовставки формируют пакет данных, включающий в себя
• ассоциированные данные , r≥1;
• шифртекст  m≥0,
• имитовставку Т.
j
[n]
Заметим, что в способе-прототипе ключ имитозащиты Н вырабатывается как Е(K, Е(K, S)), т.е. используется два блочных зашифрования, кроме того, вычисление ключа имитозащиты возможно только при получении вектора инициализации. Это не позволяет сразу при получении сообщения начать вычислять значения q, j=1, …, r+m. В предложенном способе ключ имитозащиты Н вырабатывается как Е(K, 0), это значит, что он может быть вычислен заранее без знания вектора инициализации, более того, используется только одно зашифрование, что также позволяет увеличить скорость выработки Н.
r+m
2
i
Скорость вычисления последовательности, подающейся на вход финального шифрования, в новом способе выше, чем в способе-прототипе, поскольку отсутствует начальное умножение ключа имитозащиты на константу, кроме того, в новом способе вычисление q и E(F, S) могут быть выполнены параллельно, тогда как в способе-прототипе умножение длины сообщения на ключ имитозащиты происходит после вычисления всех значений q, 1≤i≤r+m.
i
i
Два последних шифрования происходят с помощью ключа финализации. Это означает, что если значение  совпадет с одним из счетчиков Y, 1≤i≤m, то использовать знание Е(K, Y) для того, чтобы восстановить имитозащитную группу Z, нецелесообразно, поскольку  зашифровано на другом ключе. Невозможность реализации такой атаки позволяет говорить об увеличении криптографической стойкости предложенного способа по сравнению со способом-прототипом.
Для осуществления расшифрования и проверки имитовставки данных, полученных из пакета, необходимы ключ шифрования K, ключа финализации F и вектор инициализации S, которые использовались на этапе шифрования и выработки имитовставки.
Этап расшифрования шифртекста, полученного из пакета, можно выполнять независимо от этапа проверки имитовставки, при этом расшифрованный открытый текст и ассоциированные данные могут использоваться далее только в случае успешного результата проверки имитовставки. Этап расшифрования состоит в следующем:
i
i-1
Y=incr(Y), 2≤i≤m,
, i=1, …, m-1;
Проверка имитовставки происходит следующим образом:
[n]
Е(K, 0),
j=2, …, r-1,
при r>1,
i=1, …, m-1,
m>0,
t
T'=L(Z)
Если значения имитовставок Т и T' не совпали, то полученный пакет удаляют, и результатом этапов расшифрования и проверки имитовставки считают отрицательный результат проверки имитовставки. Если значения имитовставок совпали, то значения ассоциированных данных и шифртекста признают истинными и результатом этапов расшифрования и проверки имитовставки считают полученный открытый текст  и ассоциированные данные А.
Таким образом, повышение стойкости достигается за счет использования блочного зашифрования длины сообщения, а также использования двух разных ключей для шифрования и аутентификации.
Зашифрование длины сообщения позволяет избавиться от возникновения доступных для анализа зависимостей последовательности, поступающей на финальное шифрование, от битов длины сообщения, поскольку операция шифрования является более стойкой операцией, чем операция умножения в поле Галуа.
Использование двух различных ключей для шифрования и аутентификации позволяет избавиться от потенциальной угрозы совпадения результата зашифрования одного из счетчиков с имитовставкой, полученной для сообщения.
Повышение скорости выполнения способа достигается за счет того, что не нужно производить дополнительных шифрований вектора инициализации, а ключ имитозащиты Н может быть вычислен заранее. Выработка имитовставки реализуется быстрее, чем в способе-прототипе, поскольку отсутствуют начальная обработка константы и умножение длины сообщения на ключ имитозащиты, при этом шифрование длины сообщения может производиться параллельно с другими вычислениями.
Кроме того, предлагаемый способ может быть использован с блочными шифрами, имеющими различные длины блоков, длины ключей и векторов инициализации. Длина имитовставки также может быть выбрана различной, в зависимости от предпочтительного баланса между уровнем стойкости и необходимостью передавать или хранить дополнительные байты имитовставки.
Осуществление изобретения
2
7
128
128
Рассмотрим осуществление предложенного способа с использованием алгоритма блочного шифрования "Кузнечик" (Национальный стандарт РФ. ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры) в качестве Е(K, М) с длиной блока n=128, длиной ключа k=256, а также с длиной вектора инициализации s=72 и с порождающим многочленом ƒ=1+α+α+α+α в поле GF(2).
Для осуществления способа необходимы ключ шифрования K длиной 256 бит, ключ финализации F длиной 256 бит и вектор инициализации S длиной 72 бит. Ключи K и F должны быть выработаны случайно (псевдослучайно), равновероятно и независимо друг от друга. Для вектора инициализации должно быть выполнено требование уникальности, т.е. он должен быть различен для всех сообщений, зашифрованных на одном и том же ключе.
Сообщение М включает в себя:
i
• ассоциированные данные А, разделенные на r блоков A, 0<i≤r, имеющие в составе хотя бы один ненулевой блок, причем r - целое положительное число,
1
r-1
r
|A|=…=|A|=128, |А|≤128
причем длина ассоциированных данных должна быть кратна 8 битам;
i
• и, возможно, открытый текст Р, разделенный на m блоков P, 0<i≤m, причем m - целое число,
1
m-1
m
|P|=…=|P|=128, |Р|≤128
длина открытого текста должна быть кратна 8 битам;
причем выполняется соотношение
32
r+m≤2-1
Способ состоит из 4-х этапов: шифрования, выработки имитовставки, расшифрования и проверки имитовставки. Шифрование происходит следующим образом:
получают последовательность значений счетчиков:
i
i-1
Y=incr(Y), 2≤i≤m;
получают шифртекст  длина которого совпадает с длиной открытого текста, выполняя следующие действия:
i=1, …, m-1;
Выработка имитовставки для сообщения М происходит следующим образом:
• если длина последнего блока ассоциированных данных меньше 128, то дополняют этот блок:
• если длина последнего блока шифртекста меньше 128, то дополняют этот блок:
• вычисляют значение имитозащитной группы Z:
• вычисляют ключ имитозащиты Н:
[128]
Н=Е(K, 0);
1
• вычисляют значение вектора q:
• вычисляют значения векторов
j=2, …, r-1,
при r>1,
i=1, …, m-1,
, m>0;
• вычисляют
причем для размещения len(Р) выделяют 40 двоичных разрядов, а для размещения len(А) выделяют 16 двоичных разрядов;
• вычисляют значение имитозащитной группы Z:
• используют t младших бит имитозащитной группы Z в качестве имитовставки Т.
В результате этапа шифрования и выработки имитовставки формируют пакет данных, включающий в себя
• ассоциированные данные , r≥1;
32
• шифртекст  m≥0, r+m≤2-1;
• имитовставку Т.
Для осуществления расшифрования и проверки имитовставки данных, полученных из пакета, необходимы ключ шифрования K, ключа финализации F и вектор инициализации S, которые использовались на этапе шифрования и выработки имитовставки.
Этап расшифрования шифртекста, полученного из пакета, можно выполнять независимо от этапа проверки имитовставки, при этом расшифрованный открытый текст и ассоциированные данные могут использоваться далее только в случае успешного результата проверки имитовставки. Этап расшифрования состоит в следующем:
i
i-1
Y=incr(Y), 2≤i≤m,
i=1, …, m-1,
Проверка имитовставки происходит следующим образом:
[128]
Н=Е(K, 0),
j=2, …, r-1,
при r>1,
i=1, …, m-1,
m>0,
t
T'=L(Z)
Если значения имитовставок Т и T' не совпали, то полученный пакет удаляют, и результатом этапов расшифрования и проверки имитовставки считают отрицательный результат проверки имитовставки. Если значения имитовставок совпали, то значения ассоциированных данных и шифртекста признают истинными и результатом этапов расшифрования и проверки имитовставки считают полученный открытый текст  и ассоциированные данные А.
Отметим, что осуществление изобретения с другими значениями параметров способа, вообще говоря, требует дополнительных исследований криптографической стойкости.