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

(54) СПОСОБ ШИФРУЮЩЕГО ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ

(57) Реферат:

Способ шифрующего преобразования информации, характеризуемый тем, что до начала шифрования все возможные неповторяющиеся значения комбинаций алфавита u_i случайным образом с помощью датчика случайных чисел (ДСЧ) записывают в кодовую таблицу с N строками, а в каждую строку u_i адресной таблицы Т_а записывают номер строки i кодовой таблицы Т_к, в которой записано значение комбинации алфавита u_i, где N – размер алфавита, совпадающий с числом строк кодовой и адресной таблиц Т_к и Т_а, u_i – исходная комбинация, подлежащая шифрованию, причем для заполнения очередной i-й строки кодовой таблицы Т_к, где i – значение от 1 до N, получают очередное значение комбинации алфавита от ДСЧ, которое сравнивают с каждым из i-1 значением записанных комбинаций алфавита в кодовую таблицу Т_к и в случае несовпадения ни с одной из записанных комбинаций алфавита очередное значение комбинации алфавита u_i записывают в i-ю строку кодовой таблицы Т_к, при шифровании из строки u_i адресной таблицы Т_а считывают адрес A(u_i) исходной комбинации u_i в кодовой таблицы Т_к, значение шифрованной комбинации v_i исходной комбинации алфавита u_i при значении параметра преобразования _i равно значению комбинации алфавита, хранящейся в строке A(v_i) кодовой таблице Т_к, адрес которой определяют как A(v_i)=A(u_i)+_i по модулю числа N, считывают значение шифрованной комбинации v_i из строки кодовой таблицы Т_к с адресом A (v_i), при дешифровании зашифрованной комбинации v_i при значении параметра преобразования _i определяют значение комбинации, хранящейся в строке адрес А(u_i) кодовой таблицы Т_к, адрес которой определяют как A(u_i)=A(v_i)-_i по модулю числа N и считывают значение комбинации u_i из строки кодовой таблицы Т_к с адресом А(u_i). Технический результат, достигаемый при осуществлении заявленного способа, состоит в повышении скорости обработки информации.

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

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

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

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

Для реализации способа строится кодовая таблица Т_к объемом 2^l, где l – длина шифруемой последовательности (блока), а величина 2^l=N определяет размер алфавита обрабатываемых знаков. В таблицу Т_к до начала шифрования записывают без повторения случайным образом все возможные значения обрабатываемых в процессе шифрования знаков длиной l бит. Процесс заполнения может осуществляться одним из двух способов. В соответствии с первым в таблицу заносятся последовательно в порядке возрастания числа с 0 до 2^l-1. Затем производится случайная перестановка записанных в таблицу значений без введения новых или исключения имеющихся значений букв. Число таких возможных перестановок равно (2^l)!. Например, при l=8 число перестановок (2⁸)! превышает 10³⁰⁰. Такая математическая интерпретация формирования таблицы Т_к дает представление о числе вариантов заполнения таблицы, но не дает конкретного варианта реализации заполнения. В соответствии с п.5 формулы изобретения практически заполнения осуществляют с помощью следующих операций. Предварительное заполнение таблицы Т_к выполняют с помощью датчика случайных чисел (ДСЧ) в следующем порядке, первое значение полученного от ДСЧ знака записывают в первую строку таблицы Т_к с номером 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, причем в этой таблице любое возможное значение исходного знака присутствует обязательно в единственной строке таблицы, в результате этой операции получают адрес исходной комбинации в кодовой таблице A(u_i). Затем отступают по строкам таблицы Т_к на _i строк “вниз”, считая комбинацию _i двоичным числом. Из строки таблицы Т_к, отстоящей от строки с номером А(u_i) на _i строк “вниз”, считывается результат преобразования v_i. Операцию смещения «вниз» по таблице можно выразить через операцию с адресами, то есть адрес результата преобразования равен

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

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

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 таблицы Т_а.

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

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

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

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

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

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

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

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

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

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

MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 14.01.2006

Извещение опубликовано: 20.06.2007 БИ: 17/2007

NF4A Восстановление действия патента СССР или патента Российской Федерации на изобретение

Дата, с которой действие патента восстановлено: 27.07.2007

Извещение опубликовано: 27.07.2007 БИ: 21/2007