Пристрій для додавання і віднімання чисел за модулем m модулярної системи числення

Пристрій для додавання і віднімання чисел за модулем m модулярної системи числення, що містить перший і другий вхідні регістри, вихідний регістр, дешифратор, кільцевий регістр зсуву (КРЗ), інвертор за модулем m (m - модуль, за яким працює пристрій), першу, другу та третю групи елементів І, групу елементів АБО, приймальний регістр, схему порівняння (СП), лічильник імпульсів (ЛІ), причому перший і другий інформативні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід першого вхідного регістра підключено до входу дешифратора, виходи якого підключені до входів відповідних розрядів КРЗ, вихід вихідного регістра є виходом пристрою, U 2 (19) 1 3 порівняння, вихід якої підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу множник частоти, а виходи розрядів КРЗ підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістру. Недолік аналогу - значний час реалізації модульних арифметичних операцій. Недолік обумовлено тим, що вміст розрядів КРС представлено у двійковому коді. Найбільш близьким за технічною суттю до запропонованої корисної моделі є пристрій «Устройство для сложения и вычитания чисел по модулю Р» (а.с. СССР №1259255, Бюл. №35, 1986г., G06F7/72), де реалізується операція модульного додавання та віднімання (A±B) modm. Пристрій містить перший і другий вхідні регістри, вихідний регістр, дешифратор, групу ключових елементів, групу елементів І, елемент АБО, генератор імпульсів, множник частоти, лічильник, кільцевий регістр зсуву, схему порівняння, чотири елементи І, причому, перший інформаційний вхід пристрою є входом першого вхідного регістра, вихід якого є входом дешифратора, виходи якого є першими входами відповідних ключових елементів, виходи яких підключено до перших входів відповідних елементів І групи, виходи яких через елемент АБО підключено до входу вихідного регістра, вихід якого є виходом пристрою, першу керуючу шину пристрою підключено до входу генератора імпульсів, вихід якого підключено до перших входів першого і другого елементів І, вихід першого елемента І підключено до входу лічильника, вихід якого підключено до других входів ключових елементів групи та до других входів елементів І групи, а також до других входів першого і другого елементів І, вихід другого елемента І підключено до входу множника частоти, а виходи розрядів кільцевого регістра зсуву підключено до третіх входів відповідних елементів І групи, а другий інформаційний вхід пристрою підключено до входу другого вхідного регістра, вихід другого вхідного регістра підключено до другого входу схеми порівняння, а вихід множника частоти є першими входами третього і четвертого елементів І, виходи яких підключено до відповідно першого і другого входів кільцевого регістру зсуву, а до других входів третього і четвертого елементів І підключено відповідно друга і третя керуючі шини пристрою. Недолік прототипу - значний час реалізації модульних арифметичних операцій додавання та віднімання (A±B)mod m. Недолік обумовлено тим, що вміст розрядів КРС представлено у двійковому коді. В основу запропонованої корисної моделі поставлено технічну задачу зменшення часу реалізації арифметичних операцій додавання та віднімання (А±В)mod m у МСЧ. Задача вирішується тим, що у пристрій для додавання і віднімання чисел за модулем m модулярної системи числення, що містить перший і другий вхідні регістри, вихідний регістр, дешифра 49712 4 тор, кільцевий регістр зсуву (КРЗ), інвертор за модулем m (m - модуль, за яким працює пристрій), першу, другу та третю групи елементів І, групу елементів АБО, прийомний регістр, схему порівняння (СП), лічильник імпульсів (ЛІ), причому, перший і другий інформативні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід першого вхідного регістру підключено до входу дешифратора, виходи якого підключені до входів відповідних розрядів КРЗ, вихід вихідного регістру є виходом пристрою, вихід другого вхідного регістру підключено до першого входу інвертору за модулем m і до перших входів елементів І першої групи, до другого входу інвертора за модулем m підключена шина подачі значення m, а до других входів елементів І першої групи підключена шина подачі сигналу ознаки "додавання", вихід інвертора за модулем m підключено до перших входів елементів І другої групи, до других входів яких підключена шина подачі сигналу ознаки "віднімання", виходи елементів І першої та другої груп, через групу елементів АБО, підключено до входу прийомного регістру, вихід якого підключено до перших входів СП, до других входів якої відключено виходи ЛІ, згідно винаходу, в пристрій введено шифратор і елемент заборони, при цьому, виходи розрядів КРЗ через перші входи відповідних елементів І третьої групи підключено до входів шифратора, вихід якого підключено до входу вихідного регістру а управляючий вхід пристрою підключено до входу елемента заборони, вихід якого підключено до входу ЛІ і до керуючого входу КРЗ, а вихід СП підключено до других входів елементів І третьої групи, а також до другого (заборонного) входу елемента заборони. На Фіг.1 представлена блок-схема запропонованої корисної моделі. В таблиці 1 представлений алгоритм кодування вмісту шифратора 20. В таблиці 2 представлений алгоритм функціонування КРЗ 6 для m=5, А3=011,В4=100. На рисунку (Фіг.1) представлена блок-схема корисної моделі, де 1, 2 - перший та другий інформаційні входи пристрою; 3, 4 - перший та другий вхідні регістри; 5 - дешифратор (пристрій для перетворення двійкового коду в унітарний); 6 - кільцевий регістр зсуву; 7 - вихід пристрою; 8 - вихідний регістр; 9 - інвертор за модулем m; 10 - перша група елементів І; 11 - шина подачі значення модуля m, 12 - шина подачі сигналу ознаки "додавання", 13 - друга група елементів І; 14 - шина подачі сигналу ознаки "віднімання"; 15 - група елементів АБО; 16-прийомний регістр; 17 - схема порівняння; 20 - шифратор (пристрій для перетворення унітарного коду у двійковий); 21 - управляючий вхід пристрою (шина подачі імпульсів); 22 елемент заборони. Пристрій для додавання і віднімання чисел за модулем m модулярної системи числення містить перший і другий вхідні регістри, вихідний регістр, дешифратор, кільцевий регістр зсуву (КРЗ), інвертор за модулем m (m - модуль, за яким працює пристрій), першу, другу та третю групи елементів І, групу елементів АБО, прийомний регістр, схему порівняння (СП), лічильник імпульсів (ЛІ). Причому, перший і другий інформати 5 вні входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, вихід першого вхідного регістру підключено до входу дешифратора, виходи якого підключені до входів відповідних розрядів КРЗ. Вихід вихідного регістру є виходом пристрою, вихід другого вхідного регістру підключено до першого входу інвертору за модулем m і до перших входів елементів І першої групи, до другого входу інвертора за модулем m підключена шина подачі значення m, а до других входів елементів І першої групи підключена шина подачі сигналу ознаки "додавання", вихід інвертора за модулем m підключено до перших входів елементів І другої групи, до других входів яких підключена шина подачі сигналу ознаки "віднімання", виходи елементів І першої та другої груп, через групу елементів АБО, підключено до входу прийомного регістру, вихід якого підключено до перших входів СП, до других входів якої відключено виходи ЛІ. Виходи розрядів КРЗ через перші входи відповідних елементів І третьої групи підключено до входів шифратора, вихід якого підключено до входу вихідного регістру а управляючий вхід пристрою підключено до входу елемента заборони, вихід якого підключено до входу ЛІ і до керуючого входу КРЗ. Вихід СП підключено до других входів елементів І третьої групи, а також до другого (заборонного) входу елемента заборони. Введення вказаних ознак дозволяє у k=[Iog2(m-1)]+1 раз зменшити час реалізації арифметичних операцій (А±В)mod m, де [х] - ціла частина числа х, його не більша. Це досягається за рахунок того, що вміст розрядів КРЗ представляється не двійковим кодом (як у прототипу), а унітарним. Так, наприклад, (для m=5) для прототипу вихідний вміст розрядів КРЗ буде мати наступний вигляд: Для корисної моделі вихідний вміст розрядів КРЗ буде мати вигляд: Видно, що час реалізації модульних операцій для запропонованої корисної моделі, при m=5, зменшиться у k=Iog2(m-1)+1=3 рази. При збільшенні значення модуля m МСЧ ефект впровадження корисної моделі суттєво зростає. Сутність корисної моделі полягає у тому, що вміст розрядів КРЗ представляється унітарним кодом. Це скорочує час зсуву двійкових розрядів, що визначають результат операції модульного додавання та віднімання. Пристрій функціонує наступним чином. На перший 1 та другий 2 вхід подаються перший А та другий В операнди в двійковому коді. З виходу дешифратора 5 операнд А в унітарному коді поступає на вхід А-го двійкового розряду КРЗ 6. Вихідний стан двійкових розрядів КРЗ 6, наприклад, для m=5, має вигляд (нульовий стан): 49712 6 Двійкові розряди КРЗ 6 нумеруються з нульового (зліва) до (m-1)-го (справа). Операнд А (0≤А≤m-1) з виходу дешифратора 5 "записує" одиницю в А-й двійковий розряд КРЗ 6. Другий операнд В по шині 2 в двійковому коді поступає на регістр 4, з виходу якого поступає на перші входи елементів І першої 10 групи та на перший вхід інвертора 9 за модулем m. В залежності від типу операції операнд В (операція додавання, є сигнал шини 12) або операнд B m B (операція віднімання, є сигнал шини 14) через групу 15 елементів АБО поступає на вхід регістру 16. З початку роботи імпульси по шині 21 через відкритий елемент 22 заборони поступають на вхід ЛІ 18 та на керуючий вхід КРЗ 6, що здійснює зсув вихідного вмісту двійкових розрядів КРЗ на В (або на В) двійкових розрядів в негативному (за часовою стрілкою) напряму. При наявності у ЛІ 18 значення В (В) вихідний сигнал СП 17 закриває елемент 22 заборони і забороняє подачу імпульсів на ЛІ 18 та КРЗ 6 і одночасно відкриває елементи І третьої 19 групи. В цьому випадку вміст КРЗ 6 через відкриті елементи І третьої групи 19 поступає на вхід шифратора 20 з виходу якого значення (А±В)mod m результату модульної операції в МСЧ поступає на вхід вихідного регістру 8. Розглянемо приклад конкретної реалізації модульних операцій (А±В)mod m в МСЧ для m=5. В цьому випадку вихідний вміст КРЗ 6 має вигляд: Шифратор 20 має вигляд таблиці 1. Нехай А3=011, В4=100. Необхідно визначити (A+B)mod 5. Перший операнд А3=011 по входу 1 через регістр 3 поступає на вхід дешифратора 5, з третього (А3=011) виходу якого сигнал поступає на третій двійковий розряд КРЗ 6, що переводить його із нульового стану в одиничний (розряди КРЗ 6 нумеруються з нульового до (m-1)-ro зліва направо). Стан КРЗ визначається наступним чином: Другий операнд В4=100 за входом 2 через регістр 4 поступає на перші входи елементів І першої 10 групи та на перший вхід інвертора 9. З виходу елементів І першої 10 групи значення В4=100, а з виходу елементів І другої 13 групи значення B1 101 100 001 , в залежності від типу операції, через елементи 15 АБО поступають до входу регістру 16. За входом 21 імпульси через відкритий елемент 22 поступають на вхід ЛІ 18 і на вхід зсуву КРЗ 6, що здійснює зсув двійкових розрядів КРЗ 6 на чотири (здійснюється операція додавання (3+4)mod 5, присутній сигнал шини 12) розряди в негативному напрямі. В цьому випадку вміст КРЗ 6 буде мати наступний вигляд: В таблиці 2 представлено алгоритм функціонування КРЗ 6 для m=5, А3=011, В4=100. 7 49712 Якщо у ЛІ 18 буде знаходитися значення В4=100, тоді СП 17 видає сигнал "дорівнює", який закриває елемент 22 заборони та відчиняє елементи І третьої 19 групи, через які код 00100 КРЗ 6 поступає на вхід шифратора 20, з виходу якого (див. таблицю 1) значення (А+В)mod 5=(3+4)mod 5=010 поступає на вхід регістра 8. Перевірка: (3+4)=2 (mod 5). Нехай потрібно визначити результат операції (3-4)=mod 5 (присутній сигнал шини 14). В цьому випадку в прийомний регістр 16 поступає значення B1 m B4 101 100 001. Таким чином зміст КРЗ 6 (А3=011) здійснює зсув на один ( B1 =001) двійковий розряд, тобто КРЗ 6 буде мати вигляд (див. табл.2): 8 Код 00001 КРЗ 6 поступає на вхід шифратора 20, з виходу якого (див. табл.1) значення (А-В)mod 5=(3-4)mod 5=100 поступає на вхід регістра 8. Перевірка: (3-4)=4(mod 5). Таким чином, запропонована корисна модель дозволяє у k=[Iog2(m-1)]+1 раз зменшити час виконання модульних (A±B)mod m операцій у МСЧ. Це досягається за рахунок того, що вміст КРЗ складається не з лишків, безпосередньо представлених у двійковому коді, а з ознак цих лишків, що представлені унітарним кодом. Практичне застосування даної корисної моделі дозволяє значно зменшити обчислювальну складність криптографічних алгоритмів, за рахунок значного (у k раз) підвищення швидкодії реалізації криптографічних перетворень. З підвищенням значення модуля m ефективність використання даної корисної моделі збільшується. Таблиця 1 Вихід шифратора 20. (Результат операції (А±В)mod 5 у двійковому коді) 000 001 010 011 100 Вхід шифратора 20 (m=5) 10000 01000 00100 00010 00001 Таблиця 2 В ( B ), m=5 000 001 010 011 100 0 0 0 1 0 0 0 0 0 0 1 0 А3=011 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 9 Комп’ютерна верстка А. Рябко 49712 Підписне 10 Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601