Схема для пошуку мультиплікативно оберненого елемента за довільним модулем

Реферат: Схема пошуку мультиплікативно оберненого елемента за довільним модулем містить nрозрядну шину першого операнду, n-розрядну шину другого операнду, n-розрядну шину результату та суматор. Додатково містить блок ділення, з входами якого з'єднано виходи регістрів, таким чином за один такт роботи блока ділення отримується частка і остача відділення операндів, додано мультиплексори, блок множення, блок віднімання, елементи, що виконують арифметичне порівняння двох операндів "більше ніж", блок керування. UA 111351 U (12) UA 111351 U UA 111351 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель належить до галузі автоматики та обчислювальної техніки і може бути використана при реалізації операції пошуку мультиплікативно оберненого елемента у полі GF(p) та за довільним модулем, якщо аргумент є взаємно простим з модулем числом. Виконання даної операції є необхідною в багатьох криптографічних протоколах та алгоритмах завадостійкого кодування даних, зокрема системах цифрового підпису, при шифруваннідешифруванні даних з використанням еліптичних кривих та при кодуванні-декодуванні даних кодом Ріда-Соломона. Відомий метод та його апаратна реалізація пошуку мультиплікативно оберненого елемента у полі GF(p) [1], що містить шину першого операнду, шину другого операнду, регістри для зберігання значень змінних з можливістю зсуву, суматор, елемент, що виконує арифметичне порівняння двох операндів "більше ніж", а також шину результату. Дана схема дозволяє виконувати пошук мультиплікативно оберненого елемента у полі GF(p). Його недоліком є великі апаратні витрати та обмежені функціональні можливості, оскільки ця схема дає можливість виконувати операцію пошуку мультиплікативно оберненого елемента лише у полі GF(p), в той же час якщо аргумент є взаємнопростим з модулем числом, то часто виникає необхідність пошуку мультиплікативно оберненого елемента у кільці лишків за довільним модулем. Відомий метод та його апаратна реалізація пошуку мультиплікативно оберненого елемента у полі GF(p) [2], що містить шину першого операнду, шину другого операнду, регістри для зберігання значень змінних, блок піднесення до степеня за модулем, а також шину результату. Дана схема дозволяє виконувати пошук мультиплікативно оберненого елемента у полі GF(p). Її недоліком є те, що для пошуку мультиплікативно оберненого елемента використовується метод, заснований на теоремі Ейлера. Доведено, що даний метод пошуку мультиплікативно оберненого елемента є найбільш обчислювально витратним. Окрім цього до недоліків даної апаратної реалізації потрібно віднести обмежені функціональні можливості, оскільки ця схема дає можливість виконувати операцію пошуку мультиплікативно оберненого елемента лише у полі GF(p), в той же час, якщо аргумент є взаємнопростим з модулем числом, то часто виникає необхідність пошуку мультиплікативно оберненого елемента у кільці лишків за довільним модулем. Найбільш близьким за технічною суттю (прототипом) і результатом, що досягається, є схема для обчислення мультиплікативно оберненого елемента за модулем [3], що містить шину першого операнду, шину другого операнду, регістри для зберігання значень змінних, мультиплексори, суматор, дешифратор, лічильник, а також шину результату. Недоліком даної апаратної реалізації є відсутність повного опису та функціональної схеми саме для пошуку мультиплікативно оберненого елемента. Наведена схема реалізує лише операцію піднесення до степеня за модулем та може бути використана для обчислення мультиплікативно оберненого елемента за теоремою Ейлера. Але відомим фактом є те, що даний спосіб пошуку мультиплікативно оберненого елемента є найбільш обчислювально витратним. В основу корисної моделі поставлена задача розширення функціональних можливостей та зменшення обчислювальних витрат при пошуку мультиплікативно оберненого елемента до числа взаємно простого з модулем у кільці лишків за довільним модулем. Поставлена задача вирішується тим, що у схемі для обчислення мультиплікативно оберненого елемента за модулем, що містить n-розрядну шину першого операнду 901, nрозрядну шину другого операнду 902, n-розрядну шину результату 903, та суматор 601, згідно з корисною моделлю, використано блок ділення 301, з входами якого з'єднано виходи регістрів 102 і 101, таким чином за один такт роботи блока ділення 301 отримується частка і остача від ділення операндів, додано мультиплексори 201, 202, 204, 205 та 206, блок множення 401, блок віднімання 501, елементи, що виконують арифметичне порівняння двох операндів "більше ніж" 701 та 702, блок керування 1000, при цьому n-розрядна шина першого операнду 901 з'єднана з другим інформаційним входом мультиплексора 201, n-розрядна шина другого операнду 902 з'єднана з другим інформаційним входом мультиплексора 202 і входом регістра 103 для зберігання значення другого операнду, перший вихід 910 (частка) блока ділення 301 з'єднано з першим входом блока множення 401, вихід блока множення 401 з'єднано з другим входом блока віднімання 501, вихід блока віднімання 501 з'єднано з другим інформаційним входом мультиплексора 204, вихід регістра 101 з'єднано з другим входом блока ділення 301 і першим входом елемента, що виконує арифметичне порівняння двох операндів "більше ніж" 701, на другий вхід 931 елемента 701 подається константа '1', вихід елемента, що виконує арифметичне порівняння двох операндів "більше ніж" 701 з'єднано з входом 904 блока керування 1000, вихід 905 блока керування є керуючим сигналом мультиплексора 202, вихід 906 блока керування є керуючим сигналом мультиплексора 201, вихід 907 блока керування є 1 UA 111351 U 5 10 15 20 25 30 35 40 45 50 55 60 керуючим сигналом мультиплексора 204, вихід 908 блока керування є керуючим сигналом мультиплексора 205. Введення вказаних ознак дозволяє розширити функціональні можливості схеми обчислення мультиплікативно оберненого елемента за довільним модулем та зменшити обчислювальні витрати. Суть корисної моделі пояснюється кресленням. На кресленні наведена структурна схема для пошуку мультиплікативно оберненого елемента за довільним модулем, де 101, 102, 103, 104, 105-n-розрядні синхронні регістри, 201, 202, 204, 205-n-розрядні мультиплексори з двома інформаційними входами, 301 - синхронний блок ділення; 401 - блок множення; 501 - блок віднімання; 601 - суматор; 701, 702 - елементи, що виконують арифметичне порівняння двох операндів "більше ніж", на виході яких формується сигнал '1', якщо перший операнд більший за другий; 801 - дільник частот; 1000 - блок керування; 901-n-розрядна шина першого операнду, число, для якого виконується пошук мультиплікативно оберненого елемента; 902-n-розрядна шина другого операнду, модуль, за яким виконується пошук мультиплікативно оберненого елемента; 903-n-розрядна шина, яка є виходом схеми пошуку мультиплікативно оберненого елемента за довільним модулем; 910 - перший вихід (частка) блока ділення 301; 909 - другий вихід (остача) блока ділення 301; 931 - другий вхід елемента 701; 932 - другий вхід елемента 702; 933 - перший інформаційний вхід мультиплексора 204; 934 - перший інформаційний вхід мультиплексора 205; 936 - перший інформаційний вхід мультиплексора 206. Шина першого операнду 901 з'єднана з другим інформаційним входом мультиплексора 201, шина другого операнду 902 з'єднана з другим інформаційним входом мультиплексора 202 і входом регістра 103 для зберігання значення другого операнду, на вхід синхросигналу якого подається синхросигнал 920, вихід мультиплексора 201 з'єднано з входом регістра 101 для зберігання значення першого операнду, на вхід синхросигналу якого подається синхросигнал 920, керуючим сигналом мультиплексора 201 є сигнал, що формується на виході 906 блока керування 1000, вихід мультиплексора 202 з'єднано з входом регістра 102 для зберігання значення другого операнду, на вхід синхросигналу якого подається синхросигнал 920, керуючим сигналом мультиплексора 202 є сигнал, що формується на виході 905 блока керування 1000, вихід регістра 101 з'єднано з другим входом блока ділення 301 і першим входом елемента, що виконує арифметичне порівняння двох операндів "більше ніж" 701, на другий вхід 931 елемента 701 подається константа '1', вихід елемента, що виконує арифметичне порівняння двох операндів "більше ніж" 701 з'єднано з входом 904 блока керування 1000, вихід регістра 102 з'єднано з першим входом (частка) блока ділення 301 і першим інформаційним входом мультиплексора 201, вихід регістра 103 з'єднано з другим інформаційним входом мультиплексора 206, другий вихід 909 (остача) блока ділення 301 з'єднано з першим інформаційним входом мультиплексора 202, на вхід синхросигналу блока ділення 301 подається синхросигнал 921 (частота сигналу 921 дорівнює одній восьмій частоти сигналу 920), що згенерований дільником частот 801, на вхід якого подається синхросигнал 920, перший вихід 910 (частка) блока ділення 301 з'єднано з першим входом блока множення 401, вихід блока множення 401 з'єднано з другим входом блока віднімання 501, вихід блока віднімання 501 з'єднано з другим інформаційним входом мультиплексора 204, на перший інформаційний вхід 933 мультиплексора 204 подається константа '0', вихід мультиплексора 204 з'єднано з входом регістра 104, на вхід синхросигналу якого подається синхросигнал 920, керуючим сигналом мультиплексора 204 є сигнал, що формується на виході 907 блока керування 1000, вихід регістра 104 з'єднано з другим входом блока множення 401 і другим інформаційним входом мультиплексора 205, на перший інформаційний вхід 934 мультиплексора 205 подається константа '0', вихід мультиплексора 205 з'єднано з входом регістра 105, на вхід синхросигналу якого подається синхросигнал 920, керуючим сигналом мультиплексора 205 є сигнал, що формується на виході 908 керуючого блока керування 1000, вихід регістра 105 з'єднано з першим входом блока віднімання 501 і першим входом елемента, що виконує арифметичне порівняння двох операндів "більше ніж" 702, і другим входом суматора 601, на другий вхід 932 елемента 702 подається константа '0', вихід елемента, 702 є керуючим сигналом мультиплексора 206, на перший інформаційний вхід 935 мультиплексора 206 подається константа '0', вихід мультиплексора 206 з'єднано з першим входом суматора 601, виходом суматора 601 є n-розрядна шина 903, яка і є виходом схеми пошуку мультиплікативно оберненого елемента за довільним модулем. В основі роботи схеми пошуку мультиплікативно оберненого елемента за довільним модулем лежить удосконалена модифікація Бредлі розширеного алгоритму Евкліда. Розглянемо дану модифікацію розширеного алгоритму Евкліда докладніше. 2 UA 111351 U 5 Мультиплікативно оберненим елементом до числа z у медулярній арифметиці є таке число у, що виконується рівність: . z у = l(mod m). Умовою існування мультиплікативно оберненого елемента є НСД(z;m) = 1. Якщо ця умова не виконується, то мультиплікативно обернений елемент до z не існує. Розширений алгоритм Евкліда дозволяє знайти НСД двох чисел m та b і коефіцієнти х та у рівності х · m + у · b = d, 10 15 (1) де d - найбільший спільний дільник m та b. Якщо рівність (1) привести за модулем m, то отримаємо: у · b = d(mod m) Для випадку d = 1 маємо, що елемент у є мультиплікативно оберненим елементом до b за модулем m. В той же час рівність одиниці НСД(m; b) є необхідною умовою існування мультиплікативно оберненого елемента. Таким чином можна зробити висновок, що при існуванні мультиплікативно оберненого елемента його завжди можна знайти за допомогою розширеного алгоритму Евкліда. При побудові розширеного алгоритму Евкліда для пошуку НСД необхідно підтримувати виконання двох рівностей: 20 u=А·m+В·b ν=C·m+D·b 25 30 35 40 45 50 55 (2) (3) Значення u та v в процесі роботи алгоритму змінюється так само як і при роботі звичайного алгоритму Евкліда пошуку НСД. Значення А, В, С та D змінюється таким чином, щоб підтримувати виконання рівностей (2) та (3). Для того, щоб забезпечити виконання рівностей (2) та (3) на початку роботи алгоритму встановлюється А = 1,В = 0, С = 1,D = 1. -1 Очевидно, що з метою пошуку b (mod m) немає необхідності шукати обидва коефіцієнти рівності (2), а достатньо лише знайти коефіцієнт при b. Враховуючи цей факт та використовуючи ідею Бредлі, побудовано модифікований розширений алгоритм Евкліда, який знаходить лише коефіцієнт В, тобто в процесі роботи алгоритм підтримує тільки рівності виду В · b = u та D · b = ν. Окрім цього, зупинка ітераційного процесу виконується за значенням  = 1, а не  = 0, як у базовому алгоритмі. Назвемо такий алгоритм удосконаленою модифікацією Бредлі розширеного алгоритму Евкліда. Розглянемо як працює схема для пошуку мультиплікативно оберненого елемента за довільним модулем. Якщо пристрій знаходиться в режимі очікування, блок керування генерує керуючі сигнали 905, 906, що дорівнюють значенню '1' для мультиплексорів 202, 201 відповідно, 907 і 908 - що дорівнюють значенню '0' для мультиплексорів 204 і 205 відповідно, таким чином досягається надходження до регістрів 101 і 102 значень операндів і початкових значень 0 і 1, відповідно до регістрів 104 і 105. Коли на шини операндів 901 і 902 надходять операнди, схема для пошуку мультиплікативно оберненого елемента за довільним модулем переходить в режим роботи. Після завантаження значення першого операнду в регістр 101 і другого операнду в регістри 102 і 103, блок керування генерує керуючі сигнали 905, 906, що дорівнюють значенню '0' для мультиплексорів 202, 201 відповідно, 907 і 908 - що дорівнюють значенню '1' для мультиплексорів 204 і 205 відповідно, таким чином досягається надходження до регістра 102 значення з виходу 909 блока ділення 301, далі значення з виходу регістра 102 надходить на вхід регістра 101, значення з виходу регістра 104 надходить на вхід регістра 105, значення з виходу блока віднімання 501 надходить на вхід регістра 104, та виконуються дії над операндами, згідно з удосконаленою модифікацією Бредлі розширеного алгоритму Евкліда, а саме: елемент, що виконує арифметичне порівняння двох операндів "більше ніж" 701 виконує перевірку чи перевищує значення, що зберігається в регістрі 101, одиницю та формує сигнал, що подається на вхід 904 блока керування 1000. В залежності від отриманого сигналу виконуються наступні дії: Доки значення, що зберігається в регістрі 101, перевищує 1, пристрій залишається в режимі роботи. Блок ділення 301 формує частку від ділення значення, що зберігається в регістрі 101, на значення, що зберігається в регістрі 102, на виході 910 і остачу від ділення на виході 909. 3 UA 111351 U 5 10 15 20 25 30 Частка від ділення надходить на перший вхід блока множення 401, на другий вхід якого надходить значення, що зберігається в регістрі 104. Результат множення надходить на другий вхід блока віднімання 501, на перший вхід якого надходить значення, що зберігається в регістрі 105. Значення з виходу регістра 104 надходить до регістра 105 через мультиплексор 205. Результат віднімання надходить до регістра 104 через мультиплексор 204. Значення з виходу регістра 102 надходить до регістра 101 через мультиплексор 201. Остача від ділення з виходу 909 блока ділення 301 надходить до регістра 102 через мультиплексор 202. Якщо значення в регістрі 101 не перевищує 1, то пристрій переходить в режим видачі результату на шину результату 903. Елемент, що виконує арифметичне порівняння двох операндів "більше ніж" 702 виконує перевірку, чи менше значення, що зберігається в регістрі 105 за нуль, сигнал сформований на виході елемента 702 є керуючим сигналом мультиплексора 206. В залежності від отриманого сигналу виконуються наступні дії: Якщо значення, що зберігається в регістрі 105, менше за нуль, то на вихід мультиплексора 206 надходить значення, що зберігається в регістрі 103. Якщо значення, що зберігається в регістрі 105, не менше за нуль, то на вихід мультиплексора 206 надходить значення 0. Суматор 601 подає на шину результату 903, що є виходом схеми для пошуку мультиплікативно оберненого елемента за довільним модулем, результат додавання значення, що зберігається в регістрі 105 і значення на виході мультиплексора 206. Джерела інформації: 1. United States Patent № US 7574469 B2, МПК G06F 7/72. Method for Generating the Multiplicative Inverse in a Finite Field GF(p) I Robert Lorencz (CZ); заявник Ceske Vysoke Uceni Technicke, Fakulta Elektrotechnika, Prague (CZ). - № 10/535808; Dec. 15, 2003; Aug. 11, 2009 2. United States Patent № US 7191333 B1, МПК Н03К 19/00, G06F 7/04, G06F 7/556. Method and Apparatus for Calculating a Multiplicative Inverse of an Element of a Prime Field / Mahesh S. Maddury СA (US), Kenneth J. Tomei CA (US); заявник Cisco Technology, Inc., San Jose, CA (CZ). № 10/040050; Oct. 25, 2001; Mar. 13, 2007 3. United States Patent № US 6978016 B2, МПК G06F 7/52, H04L 9/30. Circuits for Calculating Modular Multiplicative Inverse / Chin-Long Chen (US), Vincenzo Condorelli (US), Camil Fayad (US); заявник International Business Machines Corporation (US). - № 09/740245; Dec. 19, 2000; Dec. 20, 2005. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 35 40 45 50 55 Схема пошуку мультиплікативно оберненого елемента за довільним модулем, що містить nрозрядну шину першого операнду (901), n-розрядну шину другого операнду (902), n-розрядну шину результату (903) та суматор (601), яка відрізняється тим, що додатково містить блок ділення (301), з входами якого з'єднано виходи регістрів (102) і (101), таким чином за один такт роботи блока ділення (301) отримується частка і остача від ділення операндів, додано мультиплексори (201), (202), (204), (205) та (206), блок множення (401), блок віднімання (501), елементи, що виконують арифметичне порівняння двох операндів "більше ніж" (701) та (702), блок керування (1000), при цьому n-розрядна шина першого операнду (901) з'єднана з другим інформаційним входом мультиплексора (201), n-розрядна шина другого операнду (902) з'єднана з другим інформаційним входом мультиплексора (202) і входом регістра (103) для зберігання значення другого операнду, перший вихід (910) блока ділення (301) з'єднано з першим входом блока множення (401), вихід блока множення (401) з'єднано з другим входом блока віднімання (501), вихід блока віднімання (501) з'єднано з другим інформаційним входом мультиплексора (204), вихід регістра (101) з'єднано з другим входом блока ділення (301) і першим входом елемента, що виконує арифметичне порівняння двох операндів "більше ніж" (701), на другий вхід (931) елемента (701) подається константа '1', вихід елемента, що виконує арифметичне порівняння двох операндів "більше ніж" (701) з'єднано з входом (904) блока керування (1000), вихід (905) блока керування є керуючим сигналом мультиплексора (202), вихід (906) блока керування є керуючим сигналом мультиплексора (201), вихід (907) блока керування є керуючим сигналом мультиплексора (204), вихід (908) блока керування є керуючим сигналом мультиплексора (205). 4 UA 111351 U Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5