СПОСОБ ШИФРОВАНИЯ ИНФОРМАЦИИ, ПРЕДСТАВЛЕННОЙ ДВОИЧНЫМ КОДОМ Российский патент 1998 года по МПК H04L9/20 

Описание патента на изобретение RU2103829C1

Изобретение относится к электросвязи и вычислительной техники, а конкретнее к криптографическим способам и устройствам для шифрования сообщений (информации). В совокупности признаков предлагаемого способа используются следующие термины:
пароль представляет из себя комбинацию битов, известную только законному пользователю;
шифрключ (ключ шифрования) представляет из себя комбинацию битов, используемую при шифровании информационных сигналов данных; шифрключ является сменным элементом шифра и используется для преобразования данного сообщения или данной совокупности сообщений; шифрключ является известным только законному пользователю или может быть выработан по детерминированным процедурам по паролю, известному только законному пользователю;
шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием шифрключа; шифр может быть реализован в виде программы для ЭВМ или в виде отдельного устройства;
шифрование есть процесс, реализующий некоторый способ преобразования данных с использованием шифрключа, переводящий данные в криптограмму, представляющую собой псевдослучайную последовательность знаков, из которой получение информации без знания ключа практически невыполнимо;
дешифрование есть процесс, обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании шифрключа;
криптостойкость является мерой надежности защиты информации и представляет собой трудоемкость, измеренную в количестве элементарных операций, которые необходимо выполнить для восстановления информации по криптограмме при знании алгоритма преобразования, но без знания шифрключа;
двоичный код информации есть последовательность единичных и нулевых битов, имеющая смысл или отражающая характеристики явлений (процессов) и предметов (объектов) при интерпретации по заданному правилу, например, данные, представленные русским текстом, могут быть преобразованы в двоичный код информации, если каждому знаку текста поставить в соответствие блок битов с уникальной структурой;
двоичный вектор - это некоторая последовательность нулевых и единичных битов, например, соответствующая фоновому шуму или сигналам помех в линии связи; двоичным вектором понимается совокупность упорядоченных битов, которая не интерпретируется получателем (приемником) данных как полезный сигнал или как информация;
псевдослучайный закон формирования двоичных векторов есть заданное детерминированное правило генерирования длинной последовательности битов по некоторому начальному параметру и разбиение этой последовательности на участки необходимого размера; в качестве начального параметра может использоваться секретный ключ; без знания значения начального параметра выходная последовательность практически неотличима от случайно генерируемых сигналов.

Известны способы блочного шифрования данных (например, стандарт США DES Диффи У., Хеллмэн М.Э. Защищенность и имитостойкость: Введение в криптографию. - ТИИЭР, 1979, т. 67. N. 3, с. 87-89), способ шифрования (патент США N 5222139, 22.06.1993, шифр FEAL-1 и криптоалгоритм B-Crypt. Мафтик С. Механизмы защиты в сетях ЭВМ. - М.: Мир, 1993, с. 49-52). В известных способах шифрование блоков данных выполняют путем формирования ключа шифрования в виде совокупности подключей, разбиения преобразуемого блока данных на подблоки и поочередного изменения последних с помощью операций подстановки, перестановки и арифметических операций, выполняемых над текущим подблоком и текущим подключом.

Однако известные способы-аналоги не обладают достаточной стойкостью к атакам на основе подобранного исходного текста, например к дифференциальному криптоанализу (Berson T.A. Differential Cryptanalysis Mod 232 with application to MD5// EUROCRYPT'92. Hungary, May 24-28, 1992. Proceedings, р. 67-68).

Наиболее близким по своей технической сущности к предлагаемому способу блочного шифрования является способ, описанный в Российском стандарте криптографической защиты данных (Стандарт СССР ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования). Способ-прототип включает в себя формирование ключа шифрования в виде последовательности из 8 подключений длиной 32 бита, разбиении входной информации, представленной в виде двоичного кода, на участки длиной по 64 бит, формировании на их основе 64-битовых блоков данных и преобразовании блоков под управлением ключа шифрования. Перед преобразованием каждый блок данных разбивается на два 32-битовых подблока В1 и В2, которые поочередно преобразуются. Один шаг преобразования подблока, например подблок B2, заключается в наложении на него текущего подключа Qi, являющегося фиксированным для данного шага, с помощью операции сложения по модулю 232 (+) в соответствии с формулой B2 : = B2 + Qi, где 1≤i≤8, после чего над полученным новым значением подблока B2 выполняют операцию подстановки, затем операцию циклического сдвига влево на одиннадцать бит, т.е. на одиннадцать двоичных разрядов в сторону старших разрядов, а затем на полученное значение B2 накладывают подблок B1 с помощью операции поразрядного суммирования по модулю два (⊕) в соответствии с формулой B2 := B2 ⊕ B1. Операция подстановки выполняется следующим образом.

Подблок разбивается на 8 двоичных вектора длиной по 4 бит. Каждый двоичный вектор заменяется двоичным вектором из таблицы подстановок. Выбранные из таблицы подстановок 8 4-битовых вектора объединяются в 32-битовый двоичный вектор, который и является выходным состоянием подблока после выполнения операции подстановки. Всего выполняется 32 аналогичных шага изменения подблоков, причем для всех преобразуемых входных блоков данных на фиксированном шаге преобразования подблоков используется подключ с фиксированным номером.

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

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

Поставленная цель достигается тем, что в известном способе блочного шифрования, заключающимся в формировании ключа шифрования, формировании К≥1 блоков данных, содержащих P≥1 участков двоичного кода информации длиной b≥1 бит и преобразования блоков данных под управлением ключа шифрования, дополнительно генерируют D≥1 двоичных векторов длиной v≥1 бит, а блоки данных формируют путем присоединения двоичных векторов с участками двоичного кода информации.

Генерирование двоичных векторов может выполняться, например, по случайному закону путем измерения вероятностного физического процесса или измерения сигнала датчика шума, в качестве которого во многих приложениях используются специально сконструированные электронные устройства. В другом варианте способа может быть использован генератор псевдослучайных чисел, на вход которого подается случайно выбираемое двоичное число, получая на выходе псевдослучайную последовательность необходимого размера. Известен ряд способов построения генераторов псевдослучайных чисел ( например, Брикелл Э.Ф., Одлижко Э.Ф. Криптоанализ: Обзор новейших результатов.- ТИИЭР. 1988, т. 76. N. 5, с. 87-89).

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

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

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

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

Предлагаемый способ ориентирован на шифрование входных блоков с использованием предварительного присоединения к входным блокам случайно генерируемых двоичных векторов. Законный пользователь знает ключ шифрования, поэтому, используя алгоритм дешифрования, может восстановить структуру двоичного вектора и структуру входного блока. Отделяя и отбрасывая двоичный вектор, который не содержит какой-либо части передаваемой информации, законный получатель полностью и однозначно восстанавливает предназначавшуюся для него информацию. Для выполнения шифрующих преобразований подблоков может быть использован, например, способ шифрования блоков данных [заявки "Способ блочного шифрования данных". Молдовян А.А., Молдовян Н.А. (вх. N. 001918, N. гос. регистр. 97101622 от 10 февраля 1997) и "Способ шифрования блоков данных". Молдовян А. А. , Молдовян Н.А. (вх. N. 001918, N. гос. регистр. 97103756].

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

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

Пример 1. Пример поясняет способ шифрования информации, представленной двоичным кодом, разбитым на участки размером 32 бит. В этом примере шифрключ формируется в виде пронумерованной последовательности 32-битовых подключей { Q(j)}, где j - номер подключа, j = 0,1,2,...,255.

Алгоритм 1: 32-битовый блочный шифр.

1. Взять очередной 32-битовый участок двоичного кода информации Y, выработать 32-битовый случайный вектор X, сформировать блок данных обозначает конкатенацию (объединение) путем присоединения двоичного вектора X и участка двоичного кода информации Y.

2. Установить счетчик числа раундов шифрования = 1 и параметр, задающий необходимое число раундов R = 3.

3. Сформировать текущий номер подключа l со структурой 8 младших битов подблока Y : l = Y mod 256.

4. Преобразовать подблок X := (X + Q(l) mod 232), где Q(l) - текущий подключ, имеющий номер l, знак := обозначает операцию присваивания.

5. Сформировать номер l со структурой 8 младших битов подблока X : l = X mod 28.

6. Преобразовать подблок Y := Y ⊕ Q(l), где знак ⊕ обозначает операцию поразрядного сложения по модулю 2.

7. Сформировать номер l со структурой битов с 9-го по 16-й подблока Y: l = (Y>8>) mod 28, где выражение вида W>u> обозначает операцию циклического сдвига слова W на u бит.

8. Преобразовать подблок X := X ⊕ Q(l).

9. Сформировать номер l со структурой битов с 9-го по 16-й подблока X: x = (X>8>) mod 28.

10. Преобразовать подблок Y := Y - Q(l) mod 232.

11. Сформировать номер l со структурой битов с 17-го по 24-й подблока Y : y = (Y>16>) mod 28.

12. Преобразовать подблок X := X - Q(l) mod 232.

13. Сформировать номер l со структурой битов с 17-го по 24-й подблока X : l = (X>16>) mod 28.

14. Преобразовать подблок Y := Y ⊕ Q(l).

15. Сформировать номер l со структурой битов с 25-го по 32-й подблока Y :l (Y>24> mod 28.

16. Преобразовать подблок X := X ⊕ Q(l).

17. Сформировать номер l со структурой битов с 25-го по 32-й подблока X : l = (Y>24> mod 28.

18. Преобразовать подблок Y := (Y + Q(l) mod 232)>x> и присвоить новое значение счетчику r := r + 1.

19. Сравнить значение r со значением R.

20. Если r > R, то выдать конкатенацию подблоков $ как блок шифротекста, в противном случае перейти к шагу 2 и продолжить преобразование подблоков.

Данный пример обеспечивает скорость шифрования около 11 Мбит/с для микропроцессора Intel 486/100. В процедуре дешифрования последовательность выполнения элементарных шагов преобразования меняется на обратную, а все бинарные операции заменяются на обратные на соответствующих шагах шифрования. Скорость дешифрования равна скорости шифрования. После дешифрования старшие 32 бита отбрасываются, а младшие 32 бита представляют собой восстановленную информацию.

Пример 2. Пример поясняет способ шифрования информации, представленной двоичным кодом, разбитым на участки размером по 12 бит. В этом примере используется известный способ шифрования 64-битовых блоков B (где B = X, Y), например способ-прототип. Функция шифрования обозначена как E(B), т.е. при шифровании блока B он преобразуется по правилу B := E(B).

Алгоритм 2: 48-битовый блочный шифр.

1. Сформировать ключ шифрования.

2. Взять очередные четыре 12-битовых участка двоичного кода информации t1, t2, t3 и t4, выработать по случайному закону четыре 20-битовых двоичных вектора v1, v2, v3 и v4, сформировать блок данных .

3. Разбить блок данных T на два подблока: где
4. Преобразовать подблок X: X := E(X).

5. Наложить подблок X на подблок Y: Y := Y ⊕ X.

6. Преобразовать подблок Y: Y := E(Y).

7. Наложить подблок Y на подблок X: X := X ⊕ Y.

8. Преобразовать подблок X: X := E(X).

9. Наложить подблок X на подблок Y: Y := Y ⊕ X.

10. Преобразовать подблок Y: Y := E(Y).

11. Наложить подблок Y на подблок X: X := X ⊕ Y.

12. Выдать блок как выходной блок шифртекста.

Пример 2 поясняется фиг. 1-3.

На фиг. 1 блок 1 представляет двоичный код информации, разбитый на 12-битовые участки, блок 2 - последовательность генерируемых 20-битовых векторов; на фиг. 2 показана структура формируемых блоков данных; на фиг. 3 - схема преобразований 3, где блок E обозначает процедуры шифрования в соответствии со способом-прототипом.

Похожие патенты RU2103829C1

название год авторы номер документа
СПОСОБ ШИФРОВАНИЯ БЛОКОВ ДАННЫХ 1997
  • Молдовян Александр Андреевич[Ru]
  • Молдовян Николай Андреевич[Ru]
  • Молдовяну Петр Андреевич[Md]
RU2111620C1
СПОСОБ ШИФРОВАНИЯ ИНФОРМАЦИИ, ПРЕДСТАВЛЕННОЙ В ДВОИЧНОМ ВИДЕ 1998
  • Молдовян А.А.
  • Молдовян Н.А.
  • Зима В.М.
RU2141728C1
СПОСОБ ШИФРОВАНИЯ БЛОКОВ ДАННЫХ 1997
  • Молдовян А.А.
  • Молдовян Н.А.
RU2106752C1
СПОСОБ КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ БЛОКОВ ДАННЫХ 1997
  • Молдовян А.А.
  • Молдовян Н.А.
RU2106753C1
СПОСОБ КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ БЛОКОВ ЦИФРОВЫХ ДАННЫХ 1997
  • Молдовян А.А.
  • Молдовян Н.А.
RU2140709C1
СПОСОБ ШИФРОВАНИЯ БЛОКОВ ЦИФРОВЫХ ДАННЫХ 1997
  • Молдовян А.А.
  • Молдовян Н.А.
  • Молдовяну П.А.
RU2124814C1
СПОСОБ КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ БЛОКОВ ДВОИЧНЫХ ДАННЫХ 1998
  • Молдовян А.А.
  • Молдовян Н.А.
RU2141729C1
ИТЕРАТИВНЫЙ СПОСОБ БЛОЧНОГО ШИФРОВАНИЯ 1999
  • Гуц Н.Д.
  • Изотов Б.В.
  • Молдовян А.А.
  • Молдовян Н.А.
RU2172075C1
СПОСОБ ИТЕРАТИВНОГО БЛОЧНОГО ШИФРОВАНИЯ ДВОИЧНЫХ ДАННЫХ 2001
  • Молдовян А.А.
  • Молдовян Н.А.
RU2206961C2
СПОСОБ БЛОЧНОГО ШИФРОВАНИЯ ДИСКРЕТНОЙ ИНФОРМАЦИИ 1998
  • Масловский В.М.
  • Молдовян А.А.
  • Молдовян Н.А.
RU2140711C1

Иллюстрации к изобретению RU 2 103 829 C1

Реферат патента 1998 года СПОСОБ ШИФРОВАНИЯ ИНФОРМАЦИИ, ПРЕДСТАВЛЕННОЙ ДВОИЧНЫМ КОДОМ

Изобретение относится к электросвязи и вычислительной техники, а конкретнее к криптографическим способам и устройствам для шифрования данных. Цель: повышение стойкости блочного шифра к атакам на основе известных и подобранных исходных текстов. Способ включает формирование ключа шифрования, формирование K≥1 блоков данных, содержащих P≥1 участков двоичного кода информации и преобразования блоков данных под управлением ключа шифрования. Отличается от известных способов тем, что дополнительно генерируют D≥1 двоичных векторов, а блоки данных формируют путем присоединения двоичных векторов к участкам двоичного кода информации. Двоичные вектора генерируют по случайному или псевдослучайному закону. Двоичные вектора присоединяют к участкам двоичного кода информации в зависимости от ключа шифрования или фиксированному правилу. 3 з.п. ф-лы, 3 ил.

Формула изобретения RU 2 103 829 C1

1. Способ шифрования информации, представленной двоичным кодом, заключающийся в формировании ключа шифрования, формировании К ≥ 1 блоков данных, содержащих Р ≥ 1 участков двоичного кода информации, и преобразовании блоков данных под управлением ключа шифрования, отличающийся тем, что дополнительно генерируют D ≥ 1 двоичных векторов, а формируют блоки данных путем присоединения двоичных векторов к участкам двоичного кода информации. 2. Способ по п.1, отличающийся тем, что двоичные векторы генерируют по случайному закону. 3. Способ по п.1, отличающийся тем, что двоичные векторы генерируют по псевдослучайному закону. 4. Способ по п.1, отличающийся тем, что двоичные векторы присоединяют к участкам двоичного кода информации в зависимости от ключа шифрования.

Документы, цитированные в отчете о поиске Патент 1998 года RU2103829C1

US, патент, 5222139, кл
Очаг для массовой варки пищи, выпечки хлеба и кипячения воды 1921
  • Богач Б.И.
SU4A1
Пресс для формовки проток и стаканов из шамотной массы 1931
  • Морозов М.А.
SU28147A1
Системы обработки информации
Защита криптографическая
Алгоритм криптографического преобразования.

RU 2 103 829 C1

Авторы

Молдовян Александр Андреевич[Ru]

Молдовян Николай Андреевич[Ru]

Молдовяну Петр Андреевич[Md]

Даты

1998-01-27Публикация

1997-04-02Подача