Устройство для защиты данных

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РеспуБлик (51)5 G 06 F 7/49

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР, (ГОСПАТЕНТ CCCP) Г ИСАЯИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4817447/24 (22) 23.04,90 (46) 30.08.,93. Бюл. Ь 32 (71) Научно-исследовательский институт средств автоматизации (72) М.H.Áîáîa и C.Ï.Êëîêîöêèé (56) Авторское свидетельство СССР

М 1072050, кл, G 06 F 11/12, 1982.

Авторское свидетельство СССР

Q 1183958, кл, G 06 F 7/49, 1983. (54) УСТРОЙСТВО ДЛЯ ЗАЩИТЫ ДАННЫХ (57) Изобретение относится к области вы, числительной техники и может быть испоЛь„„ Ы„„1837278 А1 зовано для защиты данных, вводимых в

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

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

2 з.п, ф-лы, 6 ил.

1837278

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

Целью изобретения является повышение надежности за счет коррекции ошибок, . На фиг, 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 ИЛИ, первыми входами соединенного с выходом регистра 6 сдвига, вторые входы группы элементов |0 ИЛИ через блок синхронизации 8 подсоединены ко второму выходу регистра

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

И, а пятый выход блока 7 управления подкл»очен ко второму входу блока 8 синхронизации.

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

» Р (г").

Второй регистр 6 (фиг, 3) состоит из элемента И 14 и регистра 15 сдвига, Блок 7 управления (фиг, 4) содержит генератор 16 тактовых импульсов, элементы И

17, 22, 27, 28, счетчик 18 тактов, дешифраторы 19, 24, триггеры 20, 21, 25, 26 и счетчик

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

Блок 9 формирования множимого (фиг.

6) содержит триггер 33, первую группу элементов И 34, вторую группу элементов И 35, третью группу элементов И 36, сумматоры

37 по модулю два и элементы ИЛИ 38, Регистр 1 предназначен для хранения начального и текущего значений преобразуемого элемента данных и представляет собой регистр сдвига, Регистр 2 предназначен для хранения значения ключа и п редставляет собой статический регистр, Блок 3 элементов И предназначен для поэлементного логического умножения величин, находящихся в регистре 1 множимого и в регистре 2 множителя.

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

Регистр 6 обеспечивает прием и хранение элементов данных по сигналам от блока

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

z = а»Кп + а2Кп + „, + а»»»Кв +

2 и»

- К1Кп"И+ + К К - II

40 где а», ..., а » — элементы массива данных;

К»» — ключ произведения;

К1, „., Ve — элементы ключа (К» = а) К;

»T» =) — (— число элементов данных дли45 и ной и в массиве размером» »;

» = ) — (— число элементов ключа К» в

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

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

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

1837278

z = ((...(КеКп + Ке-1} Кп + " +

+Ki) Кл+ а,) Kn - а,->) Кл+ ... + а1) Кл 50 и, изменив порядок следования элеменв

z = ((" (K1Kn + Kz) Kn + " + К К +

+az) Kn + ... + am) Kn.

Следовательно, получение числа z осуествляется операциями умножения и слориггер 20, который разрешает прохождеие информации в регистр 6.

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

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

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

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

17 закрывается.

Блок 8 синхронизации предназначен 30 я поэлементной подачи ключа в блок 9 ормирования множимого . По сигналам от, ока 7 управления посредством счетчика

2 и дешифратора 30 осуществляется послевательное подключение групп разрядов 35 гистра 2 через соответствующие группы

31 элементов И и группу элементов ИЛИ 32 и группу элементов ИЛИ 10 на вход блока 9 ормирования множимого. После выдачи в ех элементов ключа сигналом с дешифра- 40 т ра 30 счетчик 29 устанавливается в исходн е состояние.

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

Формулу для расчета можно представ ть ввиде жения чисел Аь К1 и Кп в поле GF (2 ), Поле

GF (2") определяется многочленом F(x) степени и с коэффициентами из поля GF (2"), который реализуется в блоке 4 произведения. Работа устройства происходит следующим образом. В исходном состоянии регистр 2 заполняется криптографическим ключом, а в блоке 7 управления счетчик 23 слов устанавливается на число элементов массива. По сигналу иэ блока управления первый элемент ключа К1 через первую группу 31 элементов И блока синхронизации 8 и элемент ИЛИ 10 поступает через открытые элементы И 35 и элементы ИЛИ 38 блока 9 формирования множимого записывается в регистр 1. Таким образом в регистре 1 находится элемент ключа К>, а в регистре 2 ключ Кл. Затем из блока 7 управления на регистр 1 и регистр 12 блока 4 умножения поступают тактовые импульсы.

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

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

GF (2"). После И тактов в регистре 12 блока

4 умножения будет записано произведение

К . Kn в виде элемента поля GF (2"), которое поступает на блок 9 формирования множимого и через открытые элементы И 34 подается на первые входы сумматоров 37 по модулю два. На вторые входы сумматоров

37 по модулю два поступает следующий элемент ключа К, в результате чего регистр 1 записываетсЯ сУмма К1 Кл + К . В РегистРа

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

После перебора всех элементов ключа сигналом с дешифратора 24 триггер 25 отключается. и включается триггер 26, который разрешает пода у управляющих импульсов через открытый элемент И 28 на регистр 6. Первый элемент данных а> через элемент ИЛИ 10 поступает на вход блока 9 формирования множимого, откуда, складываясь с предыдущим результатом на сумматорах 37 по модулю два, подается в регистр

1 в виде:((K1 Kn+ Кф4)+ ... + K )Kn+ а . Затем происходит умножение полученной суммы на ключ Кп, запрос нового элемента массива

az и т.д. После m циклов в регистре 12 блока

4 произведения будет находиться сумма

z = ("(К1Кп + К2)Кп + ° .. + Ке)Кп +

+ а ) Kn + ... + а л)К mod F(x), 1837278

10

40

Ф

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

Z = (a1Kn + a2Kn + ° . наКп +

2 tA

+K1K„ " + ... + К Кп ) mod Г(Х) .

Прототип осуществляет формирование п Роне Рочного числа виДа: z = (а1Кп+ а2Кп +

1 2

+ ... + атКп ) + q, где q — случайное число, которое также, кнк и Кп необходимо держать

В СЕКрЕтЕ. ДЛя ТОГО, 1тОбЫ ОПрЕдЕЛИтЬ Кп, а следовательно и получить возможность для преднамеренного изменения данных в прототипе при известном q достаточно решить уравнение степени m относительно одной неизвестной Кп. Из теории вычислений известно, что сложность решения . данного уравнения можно оценить в m операций, з где m — степень уравнения.

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

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

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

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

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

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

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

3. Устройство по п.1,отл и ч а ю щеес я тем, что блок управления содержит два счетчика, генератор тактовых импульсов, два дешифратора, четыре триггера и четыре ,элемента И, при этом вход запуска блока 10 подключен к входу запуска/останова генератора тактовых импульсов, выход которого подключен к первым входам первого и второго элементов И, выходы которых подключены соответственно к первому выходу 15 блока и счетному входу первого счетчика, выход переноса которого подключен к входу, первого дешифратора, первый выход которого подключен к входу установки в "1" первого триггера, выход которого подключен к 20 первому входу третьего элемента И, выход которого подключен к третьему выходу бло(ка, второй выход первого дешифратора подI ключен к входу установки в "0" первого триггера, к первому входу четвертого элемента

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

1837278

1837278 Редактор Н.Коляда

Заказ 2855 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101! 7 ! !

Фиг.b

Составитель M. Áo5ñ ç

Техред М.Моргентал Корректор И.Шулла