Пристрій для множення елементів скінченних полів gf(2n)

Пристрій для множення елементів скінченних полів GF(2n), який містить блок формування часткових добутків, що складається з n груп по n елементів І у кожній, (n-1) блоків матричного перетворення та блок додавання, виходи якого з'єднані з виходом результату пристрою, вхід 1-го розряду першого (I=1, ..., n) співмножника якого з'єднаний з згрупованими першими входами елементів І і-ої групи блока формування часткових добутків, входи поточної суми j-го блока матричного перетворення (j=2, ..., n-1) з'єднані з виходами поточної суми (j-l)-го блока матричного перетворення, який відрізняє ться тим, що в нього введений дешифратор, а кожний блок матричного перетворення містить першу і другу групи із n та (n-1) суматорів по модулю два, першу і другу гр упи з (n-2) та n елементів І та елемент АБО, причому входи дешифратора з'єднані з відповідними входами коефіцієнтів утворюючого полінома пристрою і входами коефіцієнтів утворюючого полінома кожного з (n-1) блоків матричного перетворення, а виходи зі входами коефіцієнтів розширення k-го блока матричного перетворення (k=1, ..., n-2), ви ходи поточної суми (n-1)-го блока матричного перетво U 2 25491 1 3 25491 другого регістрів є входами коефіцієнтів першого і другого співмножників, виходи першого регістру з'єднані з об'єднаними першими входами n елементів И в одноіменних з номерами виходів першого регістру групах елементів И відповідно, а виходи другого регістр у під’єднані до одноіменних входів першого блоку матричного перетворення та до други х входів одноіменних елементів И першої групи елементів И, при цьому, виходи попередніх блоків матричного перетворення під’єднані до одноіменних входів слідуючих блоків матричного перетворення та до других входів одноіменних елементів И слідуючих гр уп, ви ходи одноіменних елементів И кожної групи з'єднані з входами, одноіменними з елементами И багатовходових суматорів по модулю два, ви ходи яких є ви ходами пристрою. Недоліком даного пристрою є обмеженість функціональних можливостей. Задачею корисної моделі є удосконалення пристрою для множення елементів скінченних полів шля хом введення дешифратора. Це дозволяє забезпечити безпосередньо виконувати множення елементів різноманітних скінчених полів GF(2n), тобто має широкі функціональні можливості. Поставлена задача вирішується тим, що в пристрої для множення елементів скінченних полів GF(2n), який містить блок формування часткових добутків, який складається з n груп по n елементів И кожній, (n-1) блоків матричного перетворення та блок додавання, виходи якого з'єднані з виходом результату пристрою, вхід 1-го розряду першого (І=1,..., n) співмножника якого з'єднаний з згрупованими першими входами елементів И і-ої групи блоку формування часткових добутків, входи поточної суми j-гo блоку матричного перетворення (j=2, ...,n-1) з'єднані з виходами поточної суми (j-1)гo блоку матричного перетворення, а також, згідно з корисною моделлю, введено дешифратор, а кожний блок матричного перетворення містить першу і др угу гр упи із n та (n-1) суматорів по модулю два, першу і др угу гр упи з (n-2) та n елементів И та елемент АБО, причому входи дешифратора з'єднані з відповідними входами коефіцієнтів утворюючого поліному пристрою і входами коефіцієнтів утворюючого поліному кожного з (n-1) блоків матричного перетворення, а виходи зі входами коефіцієнтів розширення k-го блоку матричного перетворення (к=1, ..., n-2), виходи поточної суми (n-1)го блоку матричного перетворення з'єднані з першими входами блоку додавання, другі входи якого з'єднані з виходами відповідних елементів И з першої по (n-1) блока формування часткових добутків груп у якого з'єднані відповідно з входами часткових добутків з першого по (n-1) блок матричного перетворення, вхід і-го розряду другого співмножника пристрою з'єднаний з групованими другими входами і-их елементів И в кожній групі блоку формування часткових добутків, при цьому в кожному блоці матричного перетворення перші входи суматорів по модулю два першої групи з'єднані з входами поточної суми блоку, входи часткових добутків якого з'єднані з другими входами суматорів по модулю два першої групи, виходи яких, 4 починаючи з другого, з'єднані відповідно з першими входами суматорів по модулю два другої групи, другі входи яких з'єднані з виходами з першого по (n-1)-ий елемент И другої гр упи, ви ходи суматорів по модулю два та ви хід (n-2)-го елементу И другої групи з'єднані з відповідними виходами поточної суми блоку, виходи суматорів по модулю два з першого по (n-2)-ий першої групи з'єднані відповідно з першими входами елементів И першої групи, другі входи яких з'єднані з відповідними входами коефіцієнтів розширення блоку, а виходи з входами елемента АБО, ви хід якого з'єднаний з групованими першими входами елемента И другої групи, другі входи яких з'єднані з відповідними входами коефіцієнтів утворюючого поліному блоку. Множення елементів скінчених полів GF(2n) виконується як множення многочленів та зводиться до обчислення суми часткових добутків з приведенням її по модулю утворюючого поліному, що забезпечує множення елементів скінчених полів GF(2n) (2 £ m £ n), створених різними утворюючими поліномами. В результаті це дозволяє забезпечити безпосередньо виконувати множення елементів різноманітних скінчених полів GF(2n), і як наслідок, розширюються функціональні можливості. На Фіг.1 зображена структурна схема пристрою для множення елементів скінчених полів GF(2n). На Фіг.2 - структурна схема блоку матричного перетворення. На Фіг.3 - структурна схема дешифратора. На Фіг.4 - комбінаційна схема множення скінченого поля GF(2n). На Фіг.5 - Схема одного (n-1)-го розряду пристрою обчислення операційних коефіцієнтів рі(j) . На Фіг.6 - 1-й рівень комбінаційної схеми множення елементів скінчених полів. На Фіг.7 - універсальна комбінаційна схема множення елементів скінченних полів GF(2n). Пристрій для множення елементів скінчених полів містить входи 1 коефіцієнтів утворюючого поліному, входи 2 першого співмножника, входи 3 другого співмножника, блок 4 формування часткових добутків, (n-1) блоків 5 матричного перетворення, блок 6 додавання, дешифратор 7 та ви ходи 8 результату. Блок 5 матричного перетворення містить входи 9 поточної суми, входи 10 часткових добутків, входи 11 поточного коефіцієнту розширення, входи 12 коефіцієнтів утворюючого поліному, першу груп у з п суматорів 13 по модулю два, першу групу з (n-2) елементів И 14, (n-2) - вхідних елементів АБО 15, др угу груп у з п елементів И 16, другу групу з (n-1) суматорів 17 по модулю два та ви ходи поточної суми. Дешифратор 7 містить входи 19 коефіцієнтів утворюючого поліному, гр упу з (n-3) інверторів 20, груп у з (n-3) елементів И 21 та виходи 22 поточного коефіцієнту розширення. Пристрій для множення елементів скінчених полів GF(2n) працює в такий спосіб. Перед початком множення на входи 1 утворюючого поліному пристрою поступають значення коефіцієнтів утворюючого поліному gm(x), що призводить до формування на відповідному виході дешифратора 7 коефіцієнта розширення m. При 5 25491 поданні на входи 2 та 3 пристрою відповідно першого a(x ) та другого b( x ) співмножників на виходах блоку 4 формування часткових добутків утворюються часткові добутки a(x ) *bi, які подаються на входи 10 часткових добутків відповідних і-тих блоків 5 матричного перетворення, входи 9 поточної суми кожного з яких з'єднані з одноіменними входами 18 попереднього (і-1)-го блоку 5 матричного перетворення. На виходах 18 кожного і-го блоку 5 матричного перетворення формується і-а поточна сума як приведена по модулю утворюючого поліному сума і-го часткового добутку та (і-1)-ої поточної суми, a(x ) *bi Å ; Rn-1( x) mod gm ( x) . Таким чином, на виходах 19 (n-1)-го блоку 5 матричного перетворення формується поточна сума Rn-1 (x ) , як сума a(x ) *b1 Å ; Rn-2 (x ) modgm (x ) . Остаточний результат множення елементів скінчених полів формується на виходах 8 блоку 6 підсумовування. Блок 4 формування часткових добутків, який вміщує в себе n груп по n елементів И в кожній, слугує для отримання послідовності часткових добутків виду a(x ) *bk, аi - множина коефіцієнтів першого співмножника, bк - коефіцієнт другого співножника. На виходах елементів И перші групи формують часткові добутки а (n-1) * b(n-1), а(n-2) * b(n1) , а (n-3) * b (n-1) , ..., а 1 * b (n-1) , а 0 * b (n-1) , на ви ходах другої гр упи елементів И - а(n-1) * b (n-2), а(n-2) * b(n-2), а(n-3) * b(n-2), ..., а 1 * b(n-2), а0 * b(n-2), на ви ходах n-ої групи елементів И - а(n-1) * b 0, а(n-2) * b 0, а(n-3) * b 0, ..., а1 * b0, а0 * b0. Дешифратор 7 призначений для визначення коефіцієнта розширення поля. Так, як ступінь розширення поля визначається старшим коефіцієнтом перетворюючого поліному gm(x), то поява сигналу "1" в старшому коефіцієнті утворюючого поліному трактується на виходах де шифратора як поточний коефіцієнт розширення. При цьому на всі інші входи надходить сигнал "0", та вони блокуються. Блоки 5 матричного перетворення обчислюють поточну сум у часткових добутків та приведення її по модулю утворюючого поліному gm(x). Обчислення поточної суми a(x ) *b1 Å Rn-1 (x ) , де 6 a(x ) коефіцієнти першого співмножника, bi - і-тий коефіцієнт другого співмножника, який відповідає номеру і-го поточного блоку 5 матричного перетворення, Rn-1 (x ) - коефіцієнти поточної суми (і1)-го попереднього блоку 5 матричного перетворення, ф сумма по модулю два, яка виконується першою групою суматорів 13 по модулю два. Приведення по модулю два утворюючого поліному gm(x) виконується за умови якщо, сума по модулю два ak*b1 Å Р(I-1)=1/ак та P(i-1) відповідно к-ті коефіцієнти першого співмножника та поточної суми попереднього блоку 5 матричного перетворення співпадає зі значенням коефіцієнта розширення поля ("1"), то з суми a(x ) *bi Å Rn-1 (x ) вираховується значення коефіцієнтів gm(x) утворюючого поліному, що являється результуючою поточною сумою цього блоку. Якщо немає співпадання ак *b1 Å Р(i-1)k зі значенням коефіцієнта розширення ("0"), то віднімання не виконується, та сума a(x ) *bi Å Rn-1 (x ) передається на вихід блоку. Перша група елементів И 14 застосовується для порівняння коефіцієнта розширення зі знаком ак *b1 Å Р(i-1)k, а др уга 16 - для управління відніманням, а (n-3) - входовий елемент АБО 15 призначений для мултиплексування коефіцієнтів розширення. Блок 6 сумування, який складається з (n1) суматорів по модулю два, призначений для формування коефіцієнтів результуючого добутку, які визначаються як сума a(x ) *bi Å Rn-1 (x ) . Множення елементів скінченних полів GF(2n) виконується як множення многочленів та призводить до обчислення суми часткових добутків с приведенням їх по модулю утворюючого поліному. Таким чином, ефективність запропонованого пристрою визначається його багатофункціональними можливостями (діапазон степені розширення полю), регулярністю структури та можливістю реалізації у вигляді ВІС або ПЛІС. Джерела інформації 1. Патент Російської Федерації №2058040, кл. G06F7/49, 1996. 2. Патент України № 4046, кл. G06F7/49, 1994. 7 25491 8 9 Комп’ютерна в ерстка В. Мацело 25491 Підписне 10 Тираж 26 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601