СПОСОБ ЗАЩИТЫ ИНФОРМАЦИИ
INFORMATION PROTECTION METHOD

Изобретение относится к способам защиты информации, а более конкретно - к алгоритмам шифрования с публичным ключом, которые применяются для повышения уровня безопасности алгоритмов генерации секретных ключей и шифрования в системах защиты информации на основе идентификационных данных.
Из уровня техники известны способы защиты информации на основе идентификационных данных (СЗИОИД), отличительной чертой которых является возможность использования в качестве публичного ключа уникального идентификатора пользователя (строки произвольной длинны, например, электронного адреса типа someone@somehost.com) [1]. Главным достоинством такой системы является то, что отправителю перед шифрованием не требуется получать публичный ключ получателя и проверять его подлинность. Однако, в системе, реализующей этот способ, необходимо наличие сервера, известного как Генератор Секретных Ключей (ГСК), который генерирует секретные ключи и после аутентификации выдает их пользователям в соответствии с их идентификаторами.
СЗИОИД включает в себя следующий набор этапов:
Этап 1. Начальная инициализация (σ). Алгоритм, который берет на вход параметр безопасности системы σ. На выходе алгоритм выдает (PK, SMK), где РК - публичный ключ системы, SMK - секретный мастер-ключ системы.
ID
Этап 2. Генерация секретного ключа (РК, SMK, ID). Алгоритм, который берет на вход РК, SMK и идентификатор пользователя ID. На выходе алгоритм выдает секретный ключ пользователя SK.
Этап 3. Шифрование (РК, ID, M). Алгоритм, который берет на вход РК, ID и сообщение M. На выходе алгоритм выдает шифротекст С.
ID
ID
Этап 4. Дешифрование (РК, ID, SK, С). Алгоритм, который берет на вход РК, ID, SK и С. На выходе алгоритм выдает М.
Известны несколько реализации СЗИОИД, которые используют разный математический аппарат (см. публикации [2, 3, 4, 5], в которых используют эллиптические кривые; и публикации [6, 7], в которых используют вычеты). Безопасность таких способов и систем базируется на допущении о сложности задачи дискретного логарифмирования или задачи определения квадратичного вычета. Системы защиты информации, основанные на кодах, контролирующих ошибки, базируются на доказано сложной задаче синдромного декодирования случайного линейного кода. Следовательно, применение кодового подхода приводит к обеспечению большей безопасности полученной в результате схемы. Кроме того, кодовые криптосистемы имеют меньшую сложность процедур шифрования и дешифрования по сравнению с криптосистемами на эллиптических кривых, так как требуют только сложения набора двоичных векторов. Однако, криптосистемы, реализованные при помощи эллиптических кривых, имеют высокую вычислительную сложность процедур шифрования и дешифрования, а схемы, базирующиеся на квадратичных вычетах, имеют в основе безопасности допущение о сложности задачи факторизации, что делает их ненадежными в рамках постквантум криптографии.
Наиболее близким к заявляемому способу является техническое решение, предложенное в публикации [8] и описывающее алгоритм цифровой подписи на основе кодов. Ниже приводится краткое описание алгоритма цифровой подписи согласно [8], известного также как «способ Сандрие»:
PK
*
При начальной инициализации выбирают код Гоппы (n, k), исправляющий t ошибок, и генерируют его проверочную матрицу H размера ((n-k)×n). Секретным мастер-ключом системы является порождающий многочлен Гоппы. Случайным образом выбирают невырожденную матрицу В размера (n-k)×(n-k) и матрицу перестановки Р размера n×n. Вычисляют публичный ключ системы H=BHP. Для генерации подписи некоторого сообщения M∈{0,1} выполняется следующий итерационный алгоритм:
1. Инициализация счетчика рехеширования: counter=0
2. Хеширование исходного сообщения: s=hash(M|counter), через hash() обозначим хэш-функцию, отображающую строку произвольной длины в строку длины (n-k).
<mrow><mi>S</mi><mi>i</mi><mi>g</mi><mi>n</mi><mrow><mo>(</mo><mi>M</mi><mo>)</mo></mrow><mo>=</mo><mrow><mo>{</mo><mrow><mi>e</mi><mo>:</mo><mi>e</mi><msubsup><mi>H</mi><mrow><mi>P</mi><mi>K</mi></mrow><mi>T</mi></msubsup><mo>=</mo><mi>s</mi><mo>,</mo><mtext> </mtext><mi>w</mi><mi>t</mi><mrow><mo>(</mo><mi>e</mi><mo>)</mo></mrow><mo>≤</mo><mi>t</mi><mo>;</mo><mtext> </mtext><mtext> </mtext><mi>c</mi><mi>o</mi><mi>u</mi><mi>n</mi><mi>t</mi><mi>e</mi><mi>r</mi></mrow><mo>}</mo></mrow></mrow>
3. При помощи известного подписывающему узлу секретного ключа (многочлена Гоппы) выполняют алгоритма декодирования кода Гоппы. В случае успеха возвращают подпись сообщения в виде
, в случае отказа от декодирования counter=counter+1 возвращаются к шагу 2. Основным недостатком такого алгоритма является то, что он предназначен для проверки аутентичности сообщения и изначально не пригоден для использования его в СЗИОИД.
Задача, на решение которой направлено заявляемое изобретение, состоит в создании способа защиты информации на основе идентификационных данных (СЗИОИД) с использованием кодов, контролирующих ошибки, и безопасность которого базируется на доказано сложной задаче. При этом такой способ должен иметь меньшую сложность процедур шифрования и дешифрования, чем существующие аналоги, базирующиеся на эллиптических кривых.
Поставленная задача решается за счет модификации алгоритма цифровой подписи, описанного в прототипе [8] и основанного на кодах.
Основным отличительным признаком заявляемого способа от способа-прототипа является то, что в описанную выше схему цифровой подписи внесены следующие изменения:
- при начальной инициализации
- в зависимости от параметра безопасности σ выбирают двоичный код, имеющий полиномиальный алгоритм декодирования с параметрами (l, k') и корректирующей способностью t' и порождающей матрицей G, а также вероятность р;
- при вычислении секретного ключа пользователя
- применяют процедуру постановки подписи по способу Сандрие;
- при шифровании
- осуществляют предварительное кодирование исходного сообщения в коде, заданном на этапе начальной инициализации (Этап 1), для дальнейшего снятия ошибок на этапе дешифрования (Этап 4);
i
i
i
i
i
i
<mrow><msub><mi>A</mi><mi>i</mi></msub><mo>=</mo><mrow><mo>(</mo><mrow><mtable><mtr><mtd><mrow><msub><mi>a</mi><mn>1</mn></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>a</mi><mn>2</mn></msub></mrow></mtd></mtr><mtr><mtd><mo>⋮</mo></mtd></mtr><mtr><mtd><mrow><msub><mi>a</mi><mn>1</mn></msub></mrow></mtd></mtr></mtable></mrow><mo>)</mo></mrow><mo>:</mo><msub><mi>s</mi><mi>i</mi></msub><msubsup><mi>a</mi><mi>j</mi><mi>T</mi></msubsup><mo>=</mo><msub><mrow><mrow><mo>(</mo><mrow><msub><mi>M</mi><mi>c</mi></msub></mrow><mo>)</mo></mrow></mrow><mi>j</mi></msub></mrow>
- закодированное слово шифруют в виде C=sA+X, где матрица A находится по формуле
, а матрица X является случайной двоичной матрицей, с вероятностью появления единицы р;
- при дешифровании
<mrow><msub><mrow><mover><mi>M</mi><mo>∧</mo></mover></mrow><mi>c</mi></msub><mo>=</mo><mi>S</mi><msub><mi>K</mi><mrow><mi>I</mi><mi>D</mi></mrow></msub><msub><mi>C</mi><mrow><mi>c</mi><mi>o</mi><mi>u</mi><mi>n</mi><mi>t</mi><mi>e</mi><mi>r</mi></mrow></msub><mo>=</mo><msub><mi>M</mi><mi>c</mi></msub><mo>+</mo><mi>S</mi><msub><mi>K</mi><mrow><mi>I</mi><mi>D</mi></mrow></msub><mi>X</mi></mrow>
- дешифрование осуществляют при помощи секретного ключа по формуле
;
ID
- в расшифрованном сообщении производят снятие вектора ошибки SKX при помощи декодирования кода, заданного на этапе начальной инициализации (Этап 1) матрицей G, с известной процедурой декодирования.
Далее существо заявляемого изобретения, а именно, СЗИОИД на базе кодов, исправляющих ошибки, поясняется в деталях с привлечением графических материалов, где
Фиг.1. Схема пошагового выполнения этапа начальной инициализации системы.
Фиг.2. Схема пошагового выполнения этапа генерации секретного ключа.
Фиг.3. Схема пошагового выполнения этапа шифрования.
Фиг.4. Схема пошагового выполнения этапа дешифрования.
Фиг.5. Схема взаимодействия алгоритмов, реализующих все этапы схемы.
Рассмотрим основные этапы работы СЗИОИД.
Этап 1. Начальная инициализация. Схема данного этапа показана на
Фиг.1. ГСК генерирует публичные параметры системы и секретный мастер-ключ.
Шаг 1 (101). Вычисление секретного мастер-ключа SMK. ГСК выбирает код Гоппы с параметрами (n, k), исправляющий t ошибок и генерирует его проверочную матрицу H размера ((n-k)×n). Секретным мастер-ключом системы является порождающий многочлен Гоппы.
PK
Шаг 2 (102). Вычисление публичного ключа. Случайным образом выбирают невырожденную матрицу B размера (n-k)×(n-k) и матрицу перестановки P размера n×n. Вычисляют H=BHP.
RK
В зависимости от параметра безопасности σ выбирают код, имеющий полиномиальный алгоритм декодирования с параметрами (l, k') и корректирующей способностью t' и порождающей матрицей G, а также вероятность р. Итак публичный ключ системы состоит из двух матриц и двух значений: PK=(H, G, t, p). Этот ключ публикуют для общего доступа.
Этап 2. Генерация секретного ключа. Схема данного этапа показана на Фиг.2. Эта операция выполняется ГСК в ответ на запрос пользователя о выдаче ключа. Через hash() обозначим хэш-функцию, отображающую строку произвольной длины в строку длины (n-k).
Запрос содержит идентификатор ID пользователя.
Шаг 1 (201). Инициализация счетчика рехеширования: counter=0.
Шаг 2 (202). Хеширование идентификатора: s=hash(ID|counter).
<mrow><mi>S</mi><msub><mi>K</mi><mrow><mi>I</mi><mi>D</mi></mrow></msub><mo>=</mo><mrow><mo>{</mo><mrow><mi>e</mi><mo>:</mo><mi>e</mi><msubsup><mi>H</mi><mrow><mi>P</mi><mi>K</mi></mrow><mi>T</mi></msubsup><mo>=</mo><mi>s</mi><mo>,</mo><mtext> </mtext><mi>w</mi><mi>t</mi><mrow><mo>(</mo><mi>e</mi><mo>)</mo></mrow><mo>≤</mo><mi>t</mi><mo>;</mo><mtext> </mtext><mtext> </mtext><mi>c</mi><mi>o</mi><mi>u</mi><mi>n</mi><mi>t</mi><mi>e</mi><mi>r</mi></mrow><mo>}</mo></mrow></mrow>
Шаг 3 (202). Попытка декодирования. При помощи известного ГСК мастер-ключа SMK выполняют алгоритма декодирования кода Гоппы. В случае успеха возвращают
, в случае отказа от декодирования counter=counter+1 возвращаются к Шагу 2 (202).
Этап 3. Шифрование. Схема данного этапа показана на Фиг.3.
Шаг 1 (301). Кодирование исходного сообщения, k' бит исходного сообщения кодируют при помощи публичной матрицы G
c
M=MG.
i
Шаг 2 (302). Генерация набора публичных ключей. При помощи процедуры рехеширования генерируется набор s, i=0, …, f
i
s=hash(ID/i)
i
Шаг 3 (303). Генерация набора шифротекстов. Для каждого s, i=0, …, f генерируют матрицу
<mrow><msub><mi>A</mi><mi>i</mi></msub><mo>=</mo><mrow><mo>(</mo><mrow><mtable><mtr><mtd><mrow><msub><mi>a</mi><mn>1</mn></msub></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>a</mi><mn>2</mn></msub></mrow></mtd></mtr><mtr><mtd><mo>⋮</mo></mtd></mtr><mtr><mtd><mrow><msub><mi>a</mi><mn>1</mn></msub></mrow></mtd></mtr></mtable></mrow><mo>)</mo></mrow><mo>:</mo><msub><mi>s</mi><mi>i</mi></msub><msubsup><mi>a</mi><mi>j</mi><mi>T</mi></msubsup><mo>=</mo><msub><mrow><mrow><mo>(</mo><mrow><msub><mi>M</mi><mi>c</mi></msub></mrow><mo>)</mo></mrow></mrow><mi>j</mi></msub></mrow>
.
<mrow><msub><mi>X</mi><mi>i</mi></msub><mo>:</mo><mi>Pr</mi><mrow><mo>{</mo><mrow><msub><mi>x</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><msub><mi>j</mi><mn>2</mn></msub></mrow></msub><mo>=</mo><mn>1</mn></mrow><mo>}</mo></mrow><mo>=</mo><mi>p</mi></mrow>
i
i
i
i
Случайным образом порождают двоичную матрицу
. Вычисляют набор шифротекстов по формуле C=sA+X.
Этап 4. Дешифрование. Схема данного этапа показана на Фиг.4.
i
<mrow><msub><mrow><mover><mi>M</mi><mo>∧</mo></mover></mrow><mi>c</mi></msub><mo>=</mo><mi>S</mi><msub><mi>K</mi><mrow><mi>I</mi><mi>D</mi></mrow></msub><msub><mi>C</mi><mi>i</mi></msub></mrow>
Шаг 1 (401). Дешифрование шифротекст. Получатель сообщения выбирает шифротекст, соответствующий своему секретному ключу C:i=counter и вычисляет
.
<mrow><msub><mrow><mover><mi>M</mi><mo>∧</mo></mover></mrow><mi>c</mi></msub></mrow>
Шаг 2 (402). Декодирование. При помощи известного полиномиального алгоритма декодирования для кода с публичной матрицей G получатель сообщения вычисляет M по
.
Взаимодействия алгоритмов, реализующих этапы 1, 2, 3 и 4 описано на Фиг.5. На этапе 1 на шаге 1 (101) генерируют секретный мастер-ключ, который высылают алгоритму этапа 2. На шаге 2 (102) генерируют публичный ключ. который публикуют в общедоступном месте. На этапе 2, получив от алгоритма этапа 4 запрос на выдачу секретного ключа, на шаге 1 (201) инициализирую г счетчик рехеширования. На шаге 2 (202) хешируют пару значений идентификатора и счетчика. На шаге 3 (203) декодируют полученное на шаге 2 (202) значение как синдром и, в случае успеха, отправляют полученный вектор ошибки и значение счетчика алгоритму этапа 4, в случае отказа от декодирования увеличивают счетчик на единицу и возвращаются к шагу 2 (202). На этапе 3, на шаге 1 (301) сначала кодируют информационное сообщение. Затем на шаге 2 (302) генерируют набор публичных ключей. На шаге 3 (303) для каждого публичного ключа генерируют соответствующую шифрограмму и посылают набор шифрограмм алгоритму этапа 4. На этапе 4 на шаге 1 (401) запрашивают секретный ключ у алгоритма этапа 2, потом на шаге 2 (402) дешифруют одну из полученных от алгоритма этапа 3 шифрограмм при помощи секретного ключа, полученного от алгоритма этапа 2. На шаге 3 (403) декодируют полученное на предыдущем шаге сообщение.
Заявляемое изобретение может найти практическое применение в тех случаях, когда требуется обеспечить повышение уровня безопасности алгоритмов генерации секретных ключей и шифрования в системах защиты информации на основе идентификационных данных, например, для поддержки безопасных соединений.
Ссылки:
[1] A. Shamir, Identity-based cryptosystems and signature schemes, Proc. Of Crypto 84, LNCS 196, pp.47-53, 1984
[2] D. Boneh, M. Franklin, Identity Based Encryption from the Weil Pairing, Proc. Crypto 01, LNCS 2139, pp.213-229, 2001
[3] D. Boneh, X. Boyen, Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles, Proc. Eurocrypt 04, LNCS 3027, pp.223-238, 2004
[4] «Systems and methods for identity-based encryption and related cryptographic techniques", US patent application 20030081785, Boneh, Dan (Palo Alto, CA, US), Franklin, Matthew (Davis, CA, US), 2003, May
[5] "Identity-based-encryption system", US patent 7590236, Boneh, Dan (Palo Alto, CA, US). Boyen, Xavier (Palo Alto, CA, US), 2009, September,
[6] С. Cocks, An Identity Based Encryption Scheme based on Quadratic Residues, LNCS 2260, pp.360-363, 2001
[7] D. Boneh, С.Gentry, M. Hamburg, Space-Efficient Identity Based Encryption Without Pairings, Proc. FOCS 07, pp.647-657, 2007
[8] N. Courtois, M. Finiasz, N. Sendrier, How to achieve a MacEliece-based digital signature scheme. Springer-Verlag, 2001