Устройство для защиты данных Советский патент 1993 года по МПК G06F7/49 

СО

У

N3 00

Изобретение относится к области вычислительной техники и может быть испоЛьзовано для защиты данных, вводимых в ЭВМ или передаваемых по каналам связи, от целенаправленного их изменения. Целью изобретения является повышение надежности устройства за счет коррекции ошибок. Поставленная цель достигается тем, что устройство для защиты данных содержит первый и второй сдвигающие регистры 1 и 6, регистр 2, первую и вторую группы элементов И 3 и 5, блик умножения на примитивный элемент поля CF (2й), блок 7 управления, блок 8 синхронизации, блок 9 формирования множимого и группу элементов ИЛИ 10. 2 з.п. ф-лы, 6 ил.

Фиг.1

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

Целью изобретения является повышение надежности за счет коррекции ошибок,

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

Устройство (фиг. 1) содержит регистр 1 сдвига, регистр 2, первый блок 3 элементов И, блок 4 умножения, второй блок 5 элементов И, второй регистр 6сдвига, блок 7управления, блок синхронизации 8, блок 9 формирования множимого и группу элементов 10 ИЛИ. Выходы регистра 1 сдвига и регистра 2 соединены со входами соответствующих элементов блока 3 элементов И, выход которого через блок 4 умножения подсоединен ко входам блока 5 элементов И и блока 9 формирования множимого, выход которого соединен со входами регистра 1 сдвига, первый выход блока 7 управления соединен со входом второго регистра сдвига 6, второй выход блока 7 управления соединен со вторыми входами регистра 1 сдвига и блока 4 умножения, третий выход - ко второму входу блока 9 формирования множимого, третий вход которого подключен к выходу группы элементов 10 ИЛИ, первыми входами соединенного с выходом регистра б сдвига, вторые входы группы элементов 10 ИЛИ через блок синхронизации 8 подсоединены ко второму выходу регистра 2, четвертый выход блока 7 управления соединен со вторым входом блока 5 элементов И, а пятый выход блока 7 управления подключен ко второму входу блока 8 синхронизации.

Блок 4 умножения (фиг. 2) содержит сумматоры 11 по модулю два, триггеры 12 и умножители 13. Множители 1.3 представляют собой элементы коммутации, обеспечивающие замыкание обратной связи с выхода последнего триггера 12 в соответствии с а и дом генераторного полинома, используемого для получения элементов поля GF(2H).

Второй регистр 6 (фиг. 3) состоит из элемента И 14 и регистра 15 сдвига.

Блок 7 управления (фиг, 4) содержит генератор 16 тактовых импульсов, элементы И 17, 22, 27, 28, счетчик 18 тактов, дешифраторы 19, 24, триггеры 20, 21, 25, 26 и счетчик слов 23.

Блок 8 синхронизации (фиг. 5) состоит из счетчика 29, дешифратора 30, групп элементов И 31 и групп элементов ИЛИ 32.

Блок 9 формирования множимого (фиг. о) содержит триггер 33, первую группу элементов И 34, вторую группу элементов И 35, третью группу элементов И 36, сумматоры 37 по модулю два и элементы ИЛИ 38,

Регистр 1 предназначен для хранения начального и текущего значений преобразуемого элемента данных и представляет собой регистр сдвига.

Регистр 2 предназначен для хранения значения ключа и представляет собой стати- ческий регистр.

Блок 3 элементов И предназначен для поэлементного логического умножения величин, находящихся в регистре 1 множимо- г о и в регистра 2 множителя.

Блок 4 умножения предназначен для получения произведения сомножителей в поле GF (2м).

Регистр б обеспечивает прием и хране- ние элементов данных по сигналам от блока 7 управления,

Блок 7 управления предназначен для организации циклов умножения и сложения элементов данных и ключа в соответствии с формулой:

z aiKn + 32 Кп2 + ... + атКпт +

40

+ KlKnm+1 + ... + KeKnm+l

5

где ai, ..., ат - элементы массива данных; Кп - ключ произведения; КчКе - элементы ключа (К|- а) К;

т Nr

m J число элементов данных длиной п в массиве размером N;

с

- число элементов ключа Кп о

ключе К длиной S (S п).

0 Умножение ai и к1 производится в поле примитивного многочлена F(x) степени 2, знак + означает сложение по модулю два.

При включении устройства счетчики 18 и 23 устанавливаются в ноль, тактовые им5 пульсы с генератора 16 тактовых импульсов поступают через открытый элемент И 17 на счетчик 13 тактои. После подсчета определенного количества тактов., выбираемого из условия стабильной работы устройства, срабатывает дешифратор 19, который включает

т риггер 20, который разрешает прохождение информации в регистр 6.

По истечении П тактов сигналом с дешифратора 19 триггер 20 выключается и включается триггер 21, который разрешает подачу тактов через элемент И 22 на регистр и на блок 4 умножения.

Кроме того, сигнал с триггера 21 посту- г ает также на блок 9 формирования множимого, разрешая подачу множимого ai на сумматор 37, и на счетчик 23 слов, который г одсчитывает количество at.

После п тактов дешифратор 19 сбрасы- сает триггер 21 и включает триггер 20, и г роцесс, описанный выше, повторяется.

Через элемент И 27 на блок 8 синхронизации при переключении триггеров 20 и 21 г оступает сигнал выбора соответствующего элемента ключа, подаваемого в блок 9 формирования множимого. После того, как все элементы ключа будут выданы сигналом с ;ешифратора 24 триггер 25 отключается, и включается триггер 26, разрешая выдачу сигнала с триггера 20 для управления регистром 6. После того, как счетчик 23 слов достигает установленного значения, сигналом с дешифратора 24 триггер 26 устанавливается в исходное состояние, а элемент И закрывается.

Блок 8 синхронизации предназначен поэлементной подачи ключа в блок 9 формирования множимого. По сигналам от блока 7 управления посредством счетчика 2 Э и дешифратора 30 осуществляется последовательное подключение групп разрядов егистра 2 через соответствующие группы 31 элементов И и группу элементов ИЛИ 32 группу элементов ИЛИ 10 на вход блока 9 (формирования множимого. После выдачи ;ех элементов ключа сигналом с дешифра- т )ра 30 счетчик 29 устанавливается в исход- нре состояние.

Блок 9 формирования множимого пред- н азначен для суммирования произведений а в соответствии с формулой для расчета z.

Формулу для расчета можно пре цста- 1ть в виде

2 ((...(КеКп + Ке-1)Кл + ... +

+Ki) Кп + ат) Кп - am-i) Кп + ... +.ai) Кп

и(1и, изменив порядок следования элемен- в

z ((...(KiKn+K2)Kn + ... + Ке)Кп +

+32) Кп + ... + Зт) Кп.

Следовательно, получение числа z осуществляется операциями умножения и сложения чисел Ai, KJ и Кп в поле GF (2м). Поле GF (2Н) определяется многочленом F(x) степени п с коэффициентами из поля GF (2м), который реализуется в блоке 4 произведе- 5 ния. Работа устройства происходит следующим образом. В исходном состоянии регистр 2 заполняется криптографическим ключом, а в блоке 7 управления счетчик 23 слов устанавливается на число элементов

0 массива. По сигналу из блока управления первый элемент ключа Ki через первую группу 31 элементов И блока синхронизации 8 и элемент ИЛИ 10 поступает через открытые элементы И 35 и элементы ИЛИ 38

5 блока 9 формирования множимого записывается в регистр 1. Таким образом в регистре 1 находится элемент ключа Ki, а в регистре 2 ключ Кп. Затем из блока 7 управления на регистр 1 и регистр 12 блока 4

0 умножения поступают тактовые импульсы. На первом такте первый разряд элемента Ki из регистра 1 поступает на первые входы блока 3 элементов И, на вторые входы которого поступают значения разрядов ключа

5 Кп с выходов регистра 2. В блоке 3 элементов И первый разряд элемента Ki умножается на ключ Кп, и результат подается в блок 4 умножения, где осуществляется формирование произведения в виде элемента поля

0 GF (2П). После И тактов в регистре 12 блока 4 умножения будет записано произведение Ki . Кп в виде элемента поля GF (2П), которое поступает на блок 9 формирования множимого и через открытые элементы И 34 пода5 ется на первые входы сумматоров 37 по модулю два. На вторые входы сумматоров 37 по модулю два поступает следующий элемент ключа К2, в результате чего регистр 1 записывается сумма КгКп + К2. В регистра

0 2 находится ключ Кп, и процесс умножения, описанный выше, повторяется.

После перебора всех элементов ключа сигналом с дешифратора 24 триггер 25 отключается, и включается триггер 26, кото5 рый разрешает подачу управляющих импульсов через открытый элемент И 28 на регистр 6. Первый элемент данных ai через элемент ИЛИ 10 поступает на вход блока 9 формирования множимого, откуда, склады0 ваясь с предыдущим результатом на сумматорах 37 по модулю два, подается в регистр 1 в виде: ((Ki -Кп + K2jKn)+... + Ке)Кп + ai. Затем происходит умножение полученной суммы на ключ Кп, запрос нового элемента массива

5 аа и т.д. После m циклов в регистре 12 блока 4 произведения будет находиться сумма

Z (...(KlKn + K2)Kn + ... + Ке)Кп +

+ ai) Кп + ... + am)Kn mod F(x),

которая по сигналу из блока 7 управления через группу элементов И 5 выдается на выход устройства.

Таким образом, устройство позволяет формировать проверочное число по формуле

(aiKn + a2Kn2 + ... amKnm- -.

+KiKnmVl +

+ KeKnm+e) mod F(x).

Прототип осуществляет формирование проверочного числа вида: z (aiKn + 32Kn + + ... -t- amKnm) + q, где q - случайное число, которое также, как и Кп необходимо держать D секрете. Для того, чтобы определить Кп, а следовательно и получить возможность для преднамеренного изменения данных в прототипе при известном q достаточно решить уравнение степени m относительно одной неизвестной Кп. Из теории вычислений известно, что сложность решения данного уравнения можно оценить в m операций, где m - степень уравнения.

В предложенном устройстве в результата введения групп элементов 1/1 5, ИЛИ 10 и блока синхронизации 8, осуществляется формирование дополнительных членов уравнения, коэффициенты которых при неизвестной Кп также неизвестны. Следовательно, так как криптографический ключ выбирается из массива случайных чисел, то полученные дополнительныечлены могут быть выражены в виде случайного числа S Р(к), которое эквивалентно случайному числу q в прототипе. Однако, в силу того, что в предложенном устройстве число S является функцией криптографического ключа, оно нигде не хранится и по каналу связи не передается. В силу этого компрометации S Г(к) без компрометации ключа произойти не может, Таким образом, в предложенном устройстве, чтобы определить Кп, необходимо решить 2КП уравнений относительно неизвестной Кп, а в прототипе только одно уравнение, что подтверждает существенное повышение стойкости предложенного устройства к компрометации ключа по сравнению с прототипом.

Формула изобретения 1. Устройство для защиты данных, содержащее первый и второй сдвигающие регистры, регистр, блок умножения на примитивный элемент поля GF(2), блок формирования множимого, блок управления, первую группу элементов И, при этом выход первого сдвигающего регистра подключен к первым входам элементов И первой группы, выходы которых подключены к информационным входам блока умножения на примитивный элемент поля GF(2H), выходы которого подключены соответственно к

информационным входам первой группы блока формирования множимого, выходы которого подключены к информационным входам первого сдвигающего регистра, выходы первой группы регистра подключены соответственно к вторым входам элементов И первой группы, первый выход блока управления подключен к входу сдвига первого сдвигающего регистра и к входу синхрони0 зации блока умножения на примитивный элемент поля GF(2), второй и третий выходы блока управления подключены соответственно к входу синхронизации блока формирования множимого и к входу сдвига

5 второго сдвигающего регистра, отличающееся тем, что, с целью повышения надежности за счет коррекции ошибок, оно содержит блок синхронизации, вторую группу элементов И и группу элементов

0 ИЛИ, при этом выходы блока умножения на примитивный элемент поля GF(2H) подключены соответственно к первым входам элементов И второй группы, выходы которых подключены соответственно к выходам уст5 р ойства, вход запуска и входы криптографического ключа которого подключены соответственно к входу запуска блока управления и к информационным входам регистра, выходы групп с второй по (Н+1)-ную

0 которого подключены соответственно к входам групп с первой по Н-ную режима блока синхронизации, выходы которого подключены соответственно к первым входам элементов ИЛИ группы, выходы которых

5 подключены соответственно к информационным входам второй группы блока формирования множимого, информационный вход устройства подключен к информационному входу второго сдвигающего регистра, выхо0 ды которого подключены соответственно к вторым входам элементов ИЛИ группы, четвертый и пятый выходы блока управления подключены соответственно к входу режима блока синхронизации и к вторым входам

5 элементов И второй группы, выходы которых подключены соответственно к выходам устройства.

0 счетчик, дешифратор, Н групп элементов И и группу элементов ИЛИ, при этом вход режима блока синхронизации подключен к счетному входу счетчика, информационные выходы которого подключены к входам де5 шифратора, а-й выход (где а 1Н) которого подключен к первым входам элементов И а-й группы, (Н+1)-й выход дешифратора подключен к входу установки в О счетчика, входы режима а-й группы блока синхронизации подключены соответственно к ото рым входам элементов И а-й группы, выходы которых подключены соответственна к a-м входам элементов ИЛИ группы, выходы которых подключены соответственно к выходам блока синхронизации.

первого элемента И, третий выход первого дешифратора подключен к входу установки в О второго триггера, второму входу блока и счетному входу второго счетчика, информационный вход которого подключен к входу второго дешифратора, первый выход которого подключен к входу установки в Т третьего триггера, выход которого подключен к второму входу четвертого элемента И, выход которого подключен к пятому выходу

блока, второй выход второго дешифратора подключен к входу установки в О третьего триггера и входу установки в 1 четвертого триггера, выход которого подключен к второму входу третьего элемента И, третий выход второго дешифратора подключен к входу установки в О четвертого триггера, к второму входу второго элемента И и четвертому выходу блока.

фиг,

Pi/eJ

На 5л они /t/4 На 5л ок 8 У Но длок 6 Фиг.4

Dm 5л ока 2.

От 5т

На 5л ок 10