В С Глухов - Система команд криптографічного процесора - страница 1

Страницы:
1  2 

витрати ресурсів) на засобах, наближених до реальних. За допомогою створеного додаткового програмного забезпечення отримано можливість проводити опрацювання реальних алгоритмів.

1. Э. Опенгайм. Применение цифровой обработки сигналов. - М.: Мир, 1980. - С. 192-267. 2. Фурман Я.А., Юрьев А.Н., Яшин В.В. Цифровые методы обработки и распознавания бинарных изображений. - Красноярск: Изд-во Краснояр. ун-та, 1992. - C. 12-19. 3. William K. Pratt. Digital Image Processing: PIKS Inside, John Wiley & Sons, 2001, Third Edition. - С. 150-159. 4. Motorola DSP Simulator reference manual, http://www.motorola-dsp.com. 5. Motorola DSP assembler reference manual, http: // www.motorola-dsp.com. 6. Motorola DSP linker/librarian reference manual, http://www.motorola-dsp.com. 7. Motorola DSP56303 User's Manual, http://www.motorola-dsp.com.

 

 

 

УДК 681.3 В.С. Глухов

Національний університет "Львівська політехніка", кафедра електронних обчислювальних машин

 

СИСТЕМА КОМАНД КРИПТОГРАФІЧНОГО ПРОЦЕСОРА

© Глухов В.С., 2004

Описаний підхід до синтезу системи команд спеціалізованого процесора для створення і аналізу цифрового підпису.

The approach to synthesis of digital signature specialized processor instruction set is described.

Вступ. Наш світ стає все більше електронним в тому сенсі, що багато сфер людської діяль­ності вже значною мірою пов'язані з цифровим світом. Технології змінюють сталу термінологію -вже звичними стали словосполучення: електронний документообіг, електронна комерція, електрон­ний уряд. А з 1 січня 2004 року в Україні офіційно дозволено користуватися електронним цифровим підписом замість звичайного [1].

Сьогодні в Україні діють два стандарти на цифровий підпис: міждержавний стандарт ГОСТ 34.310-95 [2] та національний стандарт України ДСТУ 4145-2002 [3]. Поряд з великою кількістю літератури про основи і принципи захисту інформації [4-7, 16] останнім часом у фахових виданнях розглядаються конкретні питання впровадження систем захисту інформації, в тому числі і систем цифрового підпису, в нетрадиційних галузях [8], проектування структури цих засобів [9-11], питання стійкості закладених в них алгоритмів [12]. Разом з ними актуальними є також і розглянуті у цій статті питання організації роботи криптографічних процесорів. До цих питань зокрема належить розподіл функцій між центральним і спеціалізованим процесором та вибір системи команд останнього.

Окреслення проблеми. Нині загальновизнаними є декілька способів побудови криптогра­фічних систем. Одним з них є використання стандартних універсальних програмованих процесорів і процесорів обробки сигналів. Цей підхід характеризується невисокою швидкодією.

Перспективнішим є використання сукупності програмованого (центрального) процесора і спеціалізованого криптографічного процесора (або кількох спеціалізованих процесорів), при цьому спеціалізовані процесори можуть бути виконані у вигляді ядер НВІС [4, 9, 11]. При цьому актуаль­ною стає задача організації ефективної взаємодії центрального і спеціалізованого процесорів, а також задача вибору системи команд останнього.

Тут описаний підхід до реалізації взаємодії програмованого (центрального) процесора з ядром спеціалізованого криптографічного процесора, який виконує дії, необхідні для отримання цифрового підпису.

 

 

42Огляд методів взаємодії програмованого (центрального) процесора і спеціалізованого процесора. Відомі декілька методів взаємодії центрального процесора і спеціалізованого:

1)  спеціалізований процесор (сопроцесор) аналізує потік команд, які в ході виконання своєї програми зчитує з пам'яті команд центральний процесор, сопроцесор знаходить серед них ті, які входять до його власної системи команд, і виконує їх. За таким методом взаємодіють центральний процесор і математичний сопроцесор у мікропроцесорах ф. Intel;

2)  центральний процесор пересилає до регістрів спеціалізованого процесора (сопроцесора) дані для обробки та інструкцію, яка вказує, що треба робити з цими даними. За таким методом взаємодіють центральний процесор і математичний сопроцесор у мікропроцесорах ф. Motorola;

3)  центральний і спеціалізований процесори мають незалежні лічильники команд, системи команд, можуть виконувати свої програми паралельно. Центральний процесор може запускати спеціалізований процесор на виконання тієї чи іншої програми і потім приймати результати виконання цих програм. Спеціалізований процесор у цьому випадку можна назвати спецобчис-лювачем. Аналогом такого методу взаємодії є взаємодія центрального процесора і каналу вводу-виводу, тому спеціалізований процесор можна також назвати "математичним каналом" [13, 14].

Перший метод вимагає глибокого знання особливостей архітектури центрального процесора, його системи команд, використання її кодів для запуску сопроцесора. Як правило, такі сопроцесори можуть використовуватися тільки з одним типом центральних процесорів, що обмежує їхнє використання у вигляді ядер.

Другий і третій методи вільні від цих недоліків.

При глибшому розгляді можна побачити, що спецобчислювач (метод 3) містить (в тому чи іншому вигляді) центральний процесор нижнього рівня і сопроцесор (метод 2). Така багаторівнева структура і аналогія з каналом вводу-виводу дає змогу застосувати при проектуванні спецобчислювача еталонну модель взаємодії відкритих систем для розподілу функцій між елементами системи. При такому підході можна вважати, що сопроцесор і спецобчислювач виконують функції двох нижніх рівнів моделі: сопроцесор виконує функції "фізичного" рівня (виконує "пересилання" даних через свій арифметико-логічний пристрій з тими чи іншими властивостями), а спецобчислювач - функції канального рівня. На центральний процесор нижнього рівня покладається задача взаємодії з центральним процесором верхнього рівня і управління роботою сопроцесора (рис. 1).Центральний процесор верхнього рівня


И--- Н

 

 

 

и-


Поштова скринька

 

Двопортова пам' ять


Спецобчислювач

Сопроцесор

Центральний процесор нижнього рівняОперандиКоманда


Двопортова пам' ятьРис. 1. Криптографічна система

 

Детальну структуру криптографічного спецобчислювача показано на рис. 2.

За необхідності (і не тільки для криптографічних систем, а для спеціалізованих систем взагалі) кількість рівнів може бути збільшена "вгору" (згідно з еталонною моделлю - до семи), при цьому вони будуть мати вкладену структуру. На кожному рівні її можна подати як сукупність рівневого центрального процесора і підпорядкованого йому спеціалізованого процесора, куди "вкладена" структура нижнього рівня. Незалежно від рівня центральний процесор взаємодіє із

 

 

43спеціалізованим процесором через двопортову буферну пам'ять, системи на сучасних ПЛІС, для яких характерною є наявність у генерованих ядер вузлів двопортової пам'яті.


Такий підхід сприяє реалізації складі бібліотечних елементів і

Сопроцесор

Регістр-акумулятор Ra

 

Регістр R

 

 

Регістр Rj

 

 

Регістр R2

 

 

Регістр R3

 

 

Регістр R4

 

Для синхронізації роботи центрального та спеціалізованого процесорів використовується "поштова скринька" ("семафор").

Незалежно від рівня центральний процесор при взаємодії із спеціалізованим виконує такі операції:

1)    аналізує стан поштової скриньки і в разі відсутності там ознаки роботи спеціалізованого процесора переходить до виконання наступних операцій;

2)    читає з двопортової пам'яті результат попередньої роботи спеціалізованого процесора;

3)    заносить до двопортової пам' яті операнди;

4)    записує до двопортової пам' яті команду;

5)    встановлює у поштовій скриньці ознаку роботи спеціалізованого процесора (запускає його);

6)  повертається на виконання першого кроку у даній послідовності операцій.
У свою чергу спеціалізований процесор виконує такі дії:

1)    аналізує стан поштової скриньки і в разі наявності там ознаки роботи спеціалізованого процесора переходить до виконання наступних операцій;

2)    читає з двопортової пам' яті операнди;

3)    читає з двопортової пам' яті команду;

4)    декодує і виконує команду;

5)    записує до двопортової пам' яті результат;

6)    скидає у поштовій скриньці ознаку роботи спеціалізованого процесора;

7)    повертається на виконання першого кроку у даній послідовності операцій.

Особливості формування цифрового підпису. Аналіз алгоритмів формування і перевірки цифрового підпису показує, що їхньою особливістю є обробка багаторозрядних цілочисельних

 

 

44даних. У табл. 1 наведено розрядності вхідних та вихідних даних і проміжних результатів, які потрібні для формування цифрового підпису згідно з ГОСТ 34.310-95 [2]. Послідовність виконання операцій над цими числами показана на блок-схемі алгоритму вироблення цифрового підпису, яка наведена на рис. 3.

45



 

Розрядність зміннихЗ аналізу алгоритму випливає необхідність реалізації довгих операцій: піднесення до степеня за модулем і знаходження модуля (друга з них є окремим випадком першої).

Модуль (залишок від ділення) знаходиться при виконанні операції ділення одним з відомих способів, наприклад, методом без відновлення залишків.

Для знаходження степеня за модулем ak(mod p), відомий алгоритм [16]:

якщо       k = ko2r + ... + kr-121 + kr2°, k = {0;1}, ko=1,

тоді        a = a1.12*akl (mod p), a° = a.

Іншими словами

a1 = a1-12*a (mod p), якщо k1 = 1.

a1 = a1-12 (mod p), якщо k1 = 0. (1) Таким чином ця операція зводиться до ітераційного аналізу розрядів показника степеня k, виконання операцій множення і знаходження модуля.

Синтез системи команд криптографічного сопроцесора. З проведеного аналізу видно, що розрядність операндів і результатів кратна 256 біт. Тому для центрального процесора сопроцесор, який власне проводить обчислення, представляється як сукупність 256 розрядних регістрів, куди можна записати вхідні величини і звідки можна прочитати остаточні та проміжні результати. Для отримання цифрового підпису достатньо мати обмежену кількість таких регістрів, умовно позначених далі як регістри R1 (Rj) і один 512 розрядний регістр-акумулятор, далі позначений як регістр Ra.

На основі зроблених зауважень можна представити реалізацію алгоритму формування цифрового підпису як послідовність "канальних" команд спецобчислювача - його програму. Ця послідовність формується центральним процесором верхнього рівня. Кожна канальна команда відповідає одному оператору на блок-схемі алгоритму і розкладається у послідовність програм центрального процесора нижнього рівня, який за необхідності ініціює виконання сопроцесором окремих команд з системи команд останнього.

До основних програм центрального процесора нижнього рівня входять програми, наведені у табл. 2.

Таблиця 2

Основні програми

 

з/п

Позначення програми

Дія

Опис програми

1

Операнд -> Ra

завантаження

регістра-

акумулятора

операнд з центрального процесора (ЦП) записується в регістр-акумулятор сопроцесора

2

Операнд -> R1

завантаження регістра

операнд з центрального процесора (ЦП) записується в один з регістрів сопроцесора;

3

R -> Ra

пересилання

пересилання вмісту одного з регістрів до регістра-акуму-лятора

4

Ra (rest) -> R

пересилання

пересилання залишку (модуля) до одного з регістрів сопро­цесора

5

вивід R1

вивід

вивід результату з регістра

6

Ra mod R1->Ra (rest),z

знаходження залишку

ділення вмісту регістра-акумулятора сопроцесора ділиться на вміст одного з регістрів сопроцесора, залишок від ділення записується у молодші розряди регістра-акумулятра (rest), формується ознака рівності залишку 0 (z)

7

Ra+ R * Rj ->Ra

множення з накопиченням

добуток вмісту двох довільних регістрів сопроцесора до­дається до вмісту регістра-акумулятора

 

Блок-схему реалізації алгоритму формування цифрового підпису з використанням основних програм (табл. 2) наведено на рис. 4. В операторах блок-схеми підкреслені дії, які повинні виконуватися згідно з ГОСТ 34.310-95, а нижче показано, якими програмами ці дії реалізуються.

 

 

46m=h(M);

m->Ra

 

Початокm(mod q);

q->Ri;

Ra mod R->Ra (rest); Ra (rest)-> Ri;

 

m(mod q):=02551

02551-> Rir=a (mod p);

a-> Ri;

a-> Ri;

0->Ra; P-> Ri;

аналіз k; Ra+ Ri Rj->Ra; Ra mod Ri->Ra (rest);

Ra (rest)-> Ri;

Програми сопроцесора

Операнд-^;, Операнд-> Ri Ra mod R2->Ra (rest),z

Ra (rest)-> Ri

Ri ->Ra

Ra+ Ri * Rj ->Ra

 

i, j = 0, 4
47Основними програмами центрального процесора нижнього рівня є:

короткі програми (програми 1...5 табл. 2, кожній з цих програм відповідає одна команда сопроцесора);

програма множення з накопиченням (програма 7 табл. 2); програма знаходження залишку (програма 6 табл. 2).

При знаходженні залишку треба виконувати значну кількість таких додаткових специфічних операцій, як:

визначення положення старших розрядів операндів та результатів. Для цього необхідно організувати зчитування окремих регістрів (де зберігається ділене і дільник) без видачі їхнього вмісту назовні сопроцесора;

визначення кількості циклів ділення;

вирівнювання положення старших бітів операндів;

визначення типу операції - додавання чи віднімання, яка повинна виконуватися в наступному циклі ділення (формування і аналіз знака проміжного результату).

Крім того, доцільно саму операцію ділення розглядати як послідовність коротких команд віднімання, додавання і зсуву (якщо ділення виконується методом без відновлення залишків). Тому доцільним є розбиття в першу чергу саме програми знаходження залишку на послідовність команд сопроцесора, які утворять основу його системи команд.

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

Треба зауважити, що центральний процесор не тільки управляє роботою сопроцесора, але і сам може виконувати деякі прості операції. Наприклад, при піднесенні до степеня треба аналізу­вати розряди показника степеня. Оскільки показник степеня не модифікується під час знаходження залишку, доцільно аналіз його розрядів покласти на центральний процесор. При цьому сопроцесор виконує послідовність команд множення і додавання, а центральний процесор за результатами аналізу розрядів показника степеня визначає порядок цих операцій і кількість операцій множення в кожному циклі (1).

Також слід врахувати, що регістри сопроцесора і його регістр-акумулятор (де формується результат цілочисельного множення і знаходиться ділене при цілочисельному діленні) мають різну розрядність (відповідно, 256 і 512 біт). Тому для пересилання інформації між ними необхідно мати у складі команд сопроцесора команди пересилання 256 старших і 256 молодших бітів.

Страницы:
1  2 


Похожие статьи

В С Глухов - Вдосконалення алгоритму обчислення оберненого елемента gf(2t) в нормальому базисі

В С Глухов - Система команд криптографічного процесора