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

Страницы:
1  2 

3. Наступним етапом налаштовану і верифіковану засобами MatLab модель можна авто­матично імплементувати до цільової ПЛІС засобами синтезатора Xilinx AccelDSP та інтегрованої з ним САПР Xilinx ISE. Отож, розроблення апаратних засобів адаптивного еквалайзінга ефективно автоматизується, що прискорює процес і покращує отримані технічні характеристики розробки.

l.Adaptive Equalization System for Data Transmission over Coaxial Cables Jasmine Sai-Ying Cheng A Thesis submitted in conformity with the requirements Department of Electricai and Computer Engineering University of Toronto 1998 Canada National Library Bibliographic Services services bibliographiques, 395 Wellington Street 395. rue Wellington OttawaON KIA ON4. 138 p.2. Haykin, S., Adaptive Filter Theory, Third Ed., Prentice Hall, 1996. 989 p.3. Communications Toolbox User's Guide. The MathWorks, Inc. 2006. 824p.4. AccelDSP Synthesis Tool. User Guide. Release 9.1.01. Xilinx Corp. March, 2007. 228 p. 5. DSP: Designing for Optimal Results High-Performance DSP Using Virtex-4 FPGAs. Xilinx, 2005, 116p.

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

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

ВДОСКОНАЛЕННЯ АЛГОРИТМУ ОБЧИСЛЕННЯ ОБЕРНЕНОГО ЕЛЕМЕНТА gf(2t) В НОРМАЛЬОМУ БАЗИСІ

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

Описано вдосконалення методу Іто-Тічей-Цудзії (Itoh, Teechai, and Tsujii) знаходження оберненого елемента поля Галуа GF(2m) в оптимальному нормальному базисі. Вдосконалення полягає у зменшенні часу виконання послідовності операцій піднесення до квадрата.

The paper describes Itoh, Teechai, and Tsujii method of GF(2m) inverse element calculation improvement in optimal normal base. The improvement minimizes the number of squaring.

Вступ. Сучасні стандарти для роботи з цифровими підписами [1, 2] ґрунтуються на використанні полів Галуа та еліптичних кривих.

/        2      22 2m-i 1

Елементи 9,9 ,9 ,..,6 \ основного поля Галуа GF(2m) утворюють нормальний базис -корені полінома p, що утворює поле). Усі інші елементи основного поля Галуа GF(2m) можуть бути

2 22 2m-i

представлені у нормальному базисі (у вигляді a09 + a19 + a29   +... + am—19    ), де ai - двійкові

розряди (i = 0, 1, ..., m-1).

Для обчислення оберненого елемента в оптимальному нормальному базисі використовується алгоритм Іто-Тічей-Цудзії (Itoh, Teechai, and Tsujii) [3].

Недоліком алгоритму є велика кількість операцій піднесення до квадрата. У нормальному базисі піднесення до квадрата виконується як циклічний зсув елемента на один двійковий розряд праворуч. У роботі пропонується використовувати зсуви на багато розрядів. Також наведений приклад визначення кількості розрядів, на які треба здійснювати багаторозрядні зсуви для поля Галуа GF(2173).

Аналіз публікацій і окреслення проблеми. Для обчислення оберненого елемента в опти­мальному нормальному базисі використовується формула: x 1 = x2 2 = x2(2 1), x^0. Для обчислення x2   2 = x2(2     1) існує ефективний алгоритм Іто-Тічей-Цудзії (Itoh, Teechai, and

Tsujii) [3]:нехай т„ т0 - двійковий розклад цілого числа т-l. Тоді обчислення оберненого елемента виконують так:

(1) bx; k — 1.

(2) Для i від r-1 до 0 обчислюють:

(2.1) cb;

(2.2) для j від 1 до k обчислюють cc2;

(2.3) bbc;

(2.4) k—2k;

(2.5) якщо тг=1, то bb2x та kk+1.

(3) x"=b2.

Цей алгоритм застосовують при реалізації криптографічних пристроїв [4, 5], що виконують перетворення елементів поля Галуа [6] і точок еліптичних кривих [7] під час виконання операцій над цифровими підписами відповідно до стандартів [1, 2].

Недоліком алгоритму є велика кількість операцій cc2 на етапі 2.2, яка зростає із зростанням r. У нормальному базисі піднесення до квадрата виконується як циклічний зсув елемента на один двійковий розряд праворуч. У роботі пропонується використовувати зсуви на багато розрядів. Також наведений приклад визначення кількості розрядів, на які треба здійснювати багаторозрядні зсуви для поля Галуа GF(2173).

Мета роботи. Метою роботи є зменшення часу обчислення оберненого елемента поля Галуа GF(2m) із використанням методу Іто-Тічей-Цудзії. Цей алгоритм зменшує кількість операцій множення, але кількість операцій піднесення до квадрата (на кроці 2.2) залишається великою, час їхнього виконання приблизно дорівнює часу виконання ще одного множення.

У роботі ставиться задача зменшення часу виконання операцій піднесення до квадрата на кроці 2.2.

Модифікація методу Іто-Тічей-Цудзії. Оригінальний алгоритм передбачає використання регістра з двовходовим мультиплексором на вході для виконання занесення початкового значення до регістру і подальшого його циклічного зсуву на один розряд за кожний такт (рис. 2).

Din,

q:

MUX

D

w

RG

 

W

 

Q

Q

Рис. 1. Функціональна схема регістра зсуву на багато розрядів

В основу модернізації алгоритму покладене використання регістрів зсуву з багатовходовим мультиплексором на вході, що дає змогу виконувати зсув з програмованою величиною зсуву за один такт ([8], рис. 2).

Рис. 2. Функціональна схема регістра зсуву на багато розрядів

На рис. 2 позначено:

Din - дані для початкового завантаження регістра зсуву;

Q2 - вихід Q регістра, циклічно зсунутий праворуч наj двійкових розрядів.

Сигнали керування на рис. 1 та рис. 2 не позначені.

Циклічний зсув праворуч за один такт на j двійкових розрядів елемента

а = a1        ат- j-U ат-j , ат-j^^т-^ a0, Я^"^ Ят-j-1)

призводить до піднесення його до степеня 2j:

а     = (ат- j , ат- j+1ат-1, «0-: Ят- j-1 ) .

У табл. 1 показані апаратні витрати на реалізацію багатовходових однорозрядних мультиплексорів на прикладі ПЛІС ф. Xilinx. Як видно, найкраще співвідношення апаратних витрат на один вхід мають мультиплексори з кількістю інформаційних входів 2, 4, 8 (загалом 2").

Таблиця 1

Апаратні витрати на реалізацію мультиплексорів на ПЛІС

Входів

2

3

4

5

6 7

8

LUT (Xilinx, Virtex)

8

16

16

25

32 40

32

LUT/вхід

4

5,3

4

5

5,3 5,6

4

Алгоритм Іто-Тічей-Цудзії передбачає використання двовходового мультиплексора. Модифікація алгоритму полягає в використанні 4- або 8-входових мульитплексорів.

Використання 4-входового мультиплексора дає змогу завантажити початкове значення у регістр зсуву, виконувати зсуви на 1, u та v двійкових розрядів (за один такт). Для різних поліномів значення u та v знаходяться методом перебору.

Нижче наведений приклад для т=17310. Тоді т-1 = 17210 = AC16 = 101011002.

Під час обчислення оберненого елемента зміна значень k (що дорівнює кількості однорозрядних зсувів на етапі 2.2 алгоритму) відбувається згідно з табл. 2. Загальна кількість зсувів дорівнює:

k(6)+ k(5)+...+ k(0)=168.

Таблиця 2 Кількість однорозрядних зсувів

i

7

6

5

4

3

2

1

0

ті

1

0

1

0

1

1

0

0

k(i)

 

1

2

5

10

21

43

86

Очевидно, що значення u та v, які визначають, на скільки розрядів повинен виконуватися багаторозрядний зсув, повинні дорівнювати одному із значень k (різному для u та v). Найкращі результати дає варіант u=43, v=5, що ілюструє табл. 3. Загальна кількість багаторозрядних зсувів (тобто, загальна кількість тактів виконання етапу 2.2 алгоритму) дорівнює Su+Sv+S1=14. Отже, тривалість виконання етапу 2.2 алгоритму зменшується з 168 до 14, тобто, приблизно на порядок.

Для цього прикладу можливе використання 8-входового мультиплексора, який забезпечу­ватиме зсув на 1, 2, 5, 10, 21, 43 та 86 розрядів (при цьому один вхід мультиплексора викорис­товуватимуть для занесення початкового значення). Але, як видно з табл. 1, такий мультиплексор вимагає удвічі більших апаратних витрат порівняно з 4-входовим мультиплексором.

Пункт 2.2. модифікованого алгоритму для 4-входового мультиплексора можна записати у такому вигляді: (2.2)

(2.2.1) Su(i) разів обчислити c <— c2 (тобто, за один i такт виконати циклічний зсув на u двійкових розрядів, переславши інформацію через 3-й вхід мультиплексора MUX);

(2.2.2) Sv(i)  разів обчислити c <— c2   (тобто, за один i такт виконати циклічний зсув на v двійкових розрядів, переславши інформацію через 2-й вхід мультиплексора MUX);

(2.2.3) Sj(i)   разів обчислити c <— c  (тобто, за один i такт виконати циклічний зсув на 1 двійковий розряд, переславши інформацію через 1-й вхід мультиплексора MUX).

Значення Su(i), Sv(i) та St(i) попередньо обчислюються та зберігаються у табл. 3 разом з номерами i відповідних входів мультиплексора.

Структуру додаткового ПЗП, де зберігається табл. 3, визначають за табл. 4.

Таблиця 3

Кількість багаторозрядних зсувів

i

k(i)

Su(i) - кількість зсувів на 43 розряди (через 3-й вхід

Sv(i) - кількість зсувів на 5 розрядів (через 2-й вхід

S1(i) - кількість зсувів на 1 розряд (через 1-й

 

 

MUX)

MUX)

вхід MUX)

6

1

0

0

1

5

2

0

0

2

4

5

0

1

0

3

10

0

2

0

2

21

0

4

1

1

43

1

0

0

0

86

2

0

0

 

Разом зсувів: 14

3

7

4

Пункт 2.2. модифікованого алгоритму для 8-входового мультиплексора можна записати у такому вигляді:

(2.2) обчислити c <— c (тобто, за один i такт виконати циклічний зсув на k(i) двійкових розрядів, переславши інформацію через i вхід мультиплексора MUX).

Значення k(i) попередньо обчислюються та забезпечують поданням відповідних сигналів на входи мультиплексора. Керує мультиплексором безпосередньо номер такту i.

Таблиця 4

Структура ПЗП для збереження табл. 3 у випадку 4-входового мультиплексора

 

Діапазон значень

Розрядність, біт

Примітка

Адреса i

0...6

3

p

Дані Su(i)

0...2

2

 

Дані Sv(i)

0...4

3

 

Дані S,(i)

0..2

2

 

Разом даних

 

7

q

Організація ПЗП

 

8x7=56

2pq

Функціональна схема пристрою, що реалізує етап 2.2 вдосконаленого алгоритму (для випадку використання 8-розрядного мультиплексора) відповідно до табл. 3, наведена на рис. 3.

Результати порівняння оригінального і вдосконаленого алгоритму наведені у табл. 5.

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

D,r

Q2

Q

22

Q

25

Q

210

Q

221

Q

243

Q

286

MUX Sel

7 6 5 4

З 2 1 0

D

RG

*\ Q

Рис. 3. Функціональна схема пристрою

Аналіз часу виконання алгоритму

Цікаво порівняти кількість тактів виконання зсувів (168, 14 або 7 табл. 5) з кількістю тактів виконання операцій множення під час виконання алгоритму Іто-Тічей-Цудзії.

Кількість n операцій множення з використанням немодифікованого алгоритму Іто-Тічей-Цудзії не залежить від елемента, для якого обраховується обернене значення, і дорівнює зменшеній на 1 сумі кількості біт k у записі числа m-1 (k=[Iog(m-1)]) плюс кількість e ненулевих біт (функція w) у цьому записі (e=w(m-l)).

i

Таблиця 5

Порівняння оригінального і вдосконаленого алгоритму

 

2-входовий

4-входовий

8-входовий

 

мультиплексор

мультиплексор

мультиплексор

і - Апаратні витрати (кількість LUT)

8

16

32

s - Кількість тактів зсуву

168

14

7

I s - Комплексний показник, враховує

1344

224

224

апаратні витрати і кількість тактів зсуву

 

 

 

Кількість тактів однорозрядних зсувів з використанням немодифікованого алгоритму Іто-Тічей-Цудзії не залежить від елемента, для якого обраховується обернене значення, і дорівнює різниці m-e-1.

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

Для допустимих основних полів з оптимальним нормальним базисом [1] кількість операцій множення n, кількість тактів множення Nm= n*m і кількість тактів однорозрядних зсувів Ns=m-e-1 та багаторозрядних зсувів k наведена у табл. 6. Також наведена частка Ns/(Ns+Nm) тактів зсуву серед загальної кількості тактів виконання алгоритму (%).

Страницы:
1  2 


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

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

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