Патент на изобретение №2266622

(54) СПОСОБ БЛОЧНОГО ШИФРОВАНИЯ ИНФОРМАЦИИ

(57) Реферат:

Изобретение относится к криптографии и средствам защиты информации. Техническим результатом является обеспечение высокой скорости обработки информации и обеспечение после шифрования квазислучайной последовательности сигналов, независимо от статистики отдельных букв в исходном тексте. Технический результат достигается тем что, способ шифрования и дешифрования информации включает использование блочных взаимообратных однозначных двухпараметрических шифрующего и дешифрующего преобразований на основе таблиц со случайным заполнением размером N строк каждая с участием последовательности гаммы от независимого от информации датчика случайных чисел, причем для блока шифрования длиной байт вырабатывают последовательность гаммы длиной байт, изменяющейся для каждого блока, при этом каждый байт преобразуют с помощью двухпараметрического преобразования байт v_i=F(u_i,_i) с участием квазислучайных значений последовательность гаммы _i длиной 1 байт, затем выполняется в два этапа операция формирования блока шифрования путем объединения байт, причем шифрующее преобразование объединения байт первой ступени с номерами i, имеющими значения от 1 до , выполняют суммированием определенных исходных u_i и преобразованных значений v_i байт: a_i=v_i+v_i+1+u_i для i=1,…, (-1), a=v+u₁+u₂+…+u, шифрующее преобразование объединения байт второй ступени a_i с номерами i, имеющими значения от 1 до , выполняют в виде рекуррентных операций F следующим образом: _i=F(a_i, a_i+1) для i=1,…, (-1), =a, дешифрующие преобразование байт выполняют в обратной последовательности, сначала выполняют дешифрующее преобразование второй ступени для значений каждого принятого байта ‘_i с номером i, имеющим значения от 1 до , в виде рекуррентных операций F^-1 следующим образом: а’=‘; a’_I=F^-1(‘_i,a’_i+1) для i=-1, -2,…, 1, затем выполняют дешифрующее преобразование первой ступени для значений каждого байта a_i с номером i, имеющим значения от 1 до в виде рекуррентных операций F^-1 следующим образом: , для i=1,…, . 3 з.п. ф-лы.

Изобретение относится к криптографии и средствам защиты информации от несанкционированного ознакомления, изменения содержания (модификации) при хранении и передаче информации и может применяться при построении программных, аппаратных и программно-аппаратных средств криптографической защиты информации от ознакомления и контроля и восстановления целостности информации.

Известны способы шифрования информации, основанные на использовании криптографического преобразования информации с помощью случайных таблиц замены. Первый из известных способов такого шифрования, называемый полибианский квадрат, предполагает использование таблицы, в которой случайным образом записаны значения букв используемого алфавита. Значение шифруемой буквы используется как адрес, по которому считывается из таблицы записанная там буква, которая является результатом криптографического преобразования. С позиций современной криптографии, такое преобразование не изменяет вероятности появления отдельных букв в шифруемом тексте, а лишь меняет соотношение вероятностей отдельных букв в криптограмме. Если буква «а», в соответствии с таблицей замены, переходит а букву «т», то вероятность появления в исходном тексте буквы «а» будет равна вероятности появления в криптограмме буквы «т». Известно, что анализ статистики отдельных букв в тексте криптограммы дает возможность для дешифрования теста противником. Подобные таблицы замены, как одно параметрическая операция криптографического преобразования используется в различных криптографических алгоритмах, в том числе в отечественном стандарте шифрования ГОСТ 28147-89, в качестве одной из операций усложнения преобразования.

Известен способ криптографического блочного преобразования, реализованный в стандарте США AES (Advanced Encryption Standart), предназначенный для защиты информации от ознакомления, контроля целостности и подлинности.

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

В соответствии с изобретением в способе шифрующего преобразования предполагается строить шифрование как двухпараметрическую операцию, где результат шифрующего преобразования зависит как от значения исходного шифруемой комбинации u_i длиной L бит (в простейшем случае это буква или байт, в более общем – это q-ичный символ или блок, содержащий несколько байт) и квазислучайного параметра преобразования _i длиной не менее L бит – F(u_i,_i). Знак i указывает на принадлежнось этих операндов, участвующих в преобразовании, к определенному интервалу времени. Для каждого очередного значения шифруемой комбинации u_i вырабатывается новое значение _i.

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

Для реализации преобразования байт и одной из операций объединения байт способа строятся кодовые таблицы Т_к (i), каждая объемом 2^l, где l – длина шифруемой за один такт последовательности (блока), а величина 2^l=N – определяет размер алфавита обрабатываемых знаков. При длине блока байт используется до 2-1 таблица Т_к, из которых таблиц используется для преобразования байт и -1 таблица – для второй операции объединения байт при шифровании.

В каждую таблицу Т_к(i) до начала шифрования записывают без повторения случайным образом все возможные значения обрабатываемых в процессе шифрования знаков длиной l бит. Процесс заполнения может осуществляться одним из двух способов. В соответствии с первым в таблицу заносятся последовательно в порядке возрастания числа с 0 до 2^l-1. Затем производится случайная перестановка записанных в таблицу значений без введения новых или исключения имеющихся значений букв. Число таких возможных перестановок равно (2^l)!. Например, при l=8 число перестановок (2⁸)! превышает 10³⁰⁰. Такая математическая интерпретация формирования таблицы Т_к дает представление о числе вариантов заполнения таблицы, но не дает конкретного варианта реализации заполнения. Практически заполнения осуществляют с помощью следующих операций. Предварительное заполнение таблицы Т_к выполняют с помощью датчика случайных чисел (ДСЧ) в следующем порядке, первое значение полученного от ДСЧ знака записывают в первую строку таблицы Т_к с номером 0, полученное от ДСЧ второе значение знака сравнивают с ранее записанным первым знаком, при их несовпадении второе значение записывают во вторую ячейку таблицы с номером 1, в противном случае значение второго знака, полученного от ДСЧ, отбрасывается, вырабатывается третье значение знака, сравниваемое затем с записанным в таблице значением, для заполнения очередной строки таблицы Т_к с номером i (i имеет значение от 1 до 2^l-1) получают очередное значение знака от ДСЧ, сравнивают полученное значение с каждым из i-1 значением записанных в таблицу знаков, в случае несовпадения ни с одним из знаков этот знак записывается в строку с номером i, при совпадении с одним из ранее записанным в таблицу знаков полученное от ДСЧ значение отбрасывается и процесс заполнения таблицы повторяется до полного ее заполнения.

В шифровании очередного знака исходного текста u_i, производимого с помощью двухпараметрической операции F(u_i,_i), участвует значение комбинации гаммы _i, полученное от независимого от шифруемого сообщения источника гаммы, выполняющего роль датчика случайных чисел (ДСЧ). Полученное с помощью операции F(u_i,_i) значение зашифрованного знака v_i в соответствии с изобретением получают следующим образом: находят таблице Т_к значение исходного знака u_i, причем в этой таблице любое возможное значение исходного знака присутствует обязательно в единственной строке таблицы, в результате этой операции получают адрес исходной комбинации в кодовой таблице А(u_i). Затем отступают по строкам таблицы Т_к на _i строк “вниз”, считая комбинацию _i двоичным числом. Из строки таблицы Т_к, отстоящей от строки с номером А(u_i) на _i строк “вниз”, считывается результат преобразования v_i. Операцию смещения «вниз» по таблице можно выразить через операцию с адресами, то есть адрес результата преобразования равен

A(v_i)=A(u_i)+_i mod N, где N – размер таблицы.

Дешифрование выполняется с помощью обратной относительно шифрования операцией. Эта операция состоит в поиске в кодовой таблице Т_к подлежащей дешифрованию комбинации v_i смещению по таблице «вверх» на число строк, определяемое комбинацией гаммы дешифрования _i. To есть дешифрование выполняется с помощью вычисления адреса результата:

A(u_i)=A(v_i)-_i mod N, где N – размер таблицы.

Для упрощения поиска строки в таблице Т_к адреса исходной комбинации строится дополнительная таблица адресов Т_а на основании заполненной кодовой таблицы. Если в первой строке таблицы Т_к с номером 0 записана комбинация g, то в строке таблицы Т_а с адресом g записано значение 0, если во второй строке таблицы Т_к с адресом 1 хранится комбинация t, то в строке t таблицы Т_а хранится значение 1 и т.д. Тогда поиск исходной комбинации u_i при шифровании и v_i при дешифровании сводится к считыванию из таблицы Т_а значений комбинаций соответственно из строк с номерами u_i и v_i таблицы Т_а.

Зашифрованные с помощью операции v_i=F(u_i,_i) каждого i-го из байт с использованием для каждого байта собственной таблицы Т_к(i), число которых , подвергаются операции шифрующего преобразования объединения байт первой ступени с номерами i, имеющими значения от 1 до . Для этого выполняют суммирование определенных исходных u_i и преобразованных значений v_i:

a_i=v_i+v_i+1+u_i для i=1,…, (-1),

а=v+u₁+u₂+…+u

Для полученных после операции объединения байт первой ступени а_i выполняют шифрующее преобразование объединения байт второй ступени. Для этого для значений а_i с номером i, имеющим значения от 1 до , выполняют рекуррентные операции

_i=F(a_i,a_i+1) для i=1,…, (-1),

=a.

Каждое их (-1) преобразований _i=Р(а_i,a_i+1) выполняется с использованием собственной таблицы Т_к(i).

Дешифрование принятого по каналу связи (или считанного из памяти компьютера) блока, состоящего из символов (байт) ‘_i, где i=1,…, , выполняются в обратном порядке операции над байтами.

Дешифрующее преобразование второй ступени выполняют для значений каждого байта ‘_i, с номером i, имеющем значения от 1 до , в виде рекуррентных операций

a’=‘;

a’_i=F^-1(‘_i,a’_i+1) для i=-1, a-2,…, 1

Дешифрующее преобразование первой ступени выполняют для значений каждого байта а_i с номером i, имеющим значения от 1 до в виде рекуррентных операций

, для i=1,…,

Для =4 (преобразование 4 байт) это дешифрующее преобразование, с учетом обозначения операции обратного преобразования байт F^-1(_i,_i) как операции деления, имеет вид:

Предложенный и описанный выше способ шифрования может рассматриваться как блочный шифр с длиной блока L=l, имеющий пространство ключей размером V_k=V+V_t, где V – размер ключа, используемого при преобразовании знаков (байт), равный длине блока L=l, a V_t – длина ключа, применяемого при заполнении случайных таблиц замены, равная в битах величине V_t=l(2-1)2^l.

Способ может применяться как блочный шифр, то есть при постоянных значениях ключа для каждого из последовательности шифруемых боков исходной информации, а также как блочно-поточный шифр, когда для очередного (i+1)-го блока изменяется значение ключа, используемого при шифровании знаков (байт), то есть последовательность значений _i длиной L=l от независимого от шифруемой информации ДСЧ.

Способ может применяться для решения следующих задач:

– шифрования для обеспечения криптографической защиты от ознакомления и НСД;

– для контроля и восстановления целостности информации с помощью помехоустойчивого стохастического кодирования с обнаружением и исправлением естественных и преднамеренных искажений информации, когда операции шифрования выполняют роль стохастического преобразования q-ичных символов (n,k,q)-кода; в этом режиме способ может применяться только как блочно-поточный шифр со сменой ключа для каждого очередного q-ичного символа;

– для выполнения операции хэширования при формировании и проверки электронно-цифровой подписи (ЭЦП).

Описанный способ обладает следующими преимуществами:

– высокая скорость обработки информации;

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

– сложное нелинейное преобразование, не имеющее никакого другого формального описания, кроме описания заполнения кодовой таблицы Т_к;

– возможность рассматривать начальное заполнение таблиц как ключ шифрования, кроме начального заполнения ДСЧ, вырабатывающего поток гаммы.

Источники информации

1. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. – М.: ГК СССР по стандартам, 1989.

2. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. – М.: Радио и связь, 1999.

3. Зенин О.С., Иванов М.А. Стандарт криптографической защиты – AES. Конечные поля. – М.: КУДИЦ-ОБРАЗ, 2002.

4. Зима В.М., Молдовян А.А., Молдовян Н.А. Безопасность глобальных сетевых технологий. – СПб.; БХВ-Петербург, 2001.

5. Московский университет и развитие криптографии в России. Материалы конференции в МГУ 17-18 2002 г. – М.: МЦНМО, 2003. – 287 с.

Формула изобретения

1. Способ шифрования и дешифрования информации, характеризуемый использованием блочных взаимообратных однозначных двухпараметрических шифрующего и дешифрующего преобразований на основе таблиц со случайным заполнением размером N строк каждая с участием последовательности гаммы от независимого от информации датчика случайных чисел, причем для блока шифрования длиной байт вырабатывают последовательность гаммы длиной байт, изменяющейся для каждого блока, при этом каждый байт преобразуют с помощью двухпараметрического преобразования байт v_i=F(u_i,_i) с участием квазислучайных значений последовательность гаммы _i длиной 1 байт, затем выполняется в два этапа операция формирования блока шифрования путем объединения байт, причем шифрующее преобразование объединения байт первой ступени с номерами i, имеющими значения от 1 до , выполняют суммированием определенных исходных u_i и преобразованных значений v_i байт:

a_i=v_i+v_i+1+u_i для i=1,…, (-1);

a=v+u₁+u₂+…+u,

шифрующее преобразование объединения байт второй ступени a_i с номерами i, имеющими значения от 1 до , выполняют в виде рекуррентных операций F следующим образом:

_i=F(a_i,a_i+1) для i=1,…, (-1);

=а,

дешифрующее преобразование байт выполняют в обратной последовательности, причем сначала выполняют дешифрующее преобразование второй ступени для значений каждого принятого байта ‘_i с номером i, имеющим значения от 1 до , в виде рекуррентных операций F^-1 следующим образом:

a’=‘;

a’_I=F^-1 (‘_i, a’_i+1) для i=-1, -2,…, 1,

затем выполняют дешифрующее преобразование первой ступени для значений каждого байта a_i с номером i, имеющим значения от 1 до , в виде рекуррентных операций F¹ следующим образом:

для i=1,…, .

2. Способ по п.1, отличающийся тем, что шифрующее преобразование v_i=F(u_i,_i) каждого из байт производят с помощью своей таблицы со случайным однозначным заполнением, при числе таблиц , путем поиска в таблице исходного значения u_i и считывания результата преобразования v_i, отстоящего на _i строк “вниз” по модулю размера таблицы N.

3. Способ по п.1, отличающийся тем, что дешифрующее преобразование u_i=F^-1(v_i,_i) каждого из байт производят с помощью своей таблицы со случайным однозначным заполнением, при числе таблиц , путем поиска в таблице исходного значения v_i и считывания результата преобразования u_i, отстоящего на _i строк “вверх” по модулю размера таблицы N.

4. Способ по п.1, отличающийся тем, что для повышения стойкости шифрования операции шифрования и дешифрования блока может повторяться М раундов.