Файл: 2015.05.26 - Матеріали ХVІ Міжнародної науково-практичної конференції «Безпека інформації в інформаційно-телекомунікаційних системах».pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.04.2019
Просмотров: 4501
Скачиваний: 4
УДК 004.383
ТРАНСГРАНИЧНА ТА ТЕХНІЧНО ІНТЕРОПЕРАБЕЛЬНА
ІНФРАСТРУКТУРА ВІДКРИТИХ КЛЮЧІВ
А.В. Карпов
ТОВ «АВТОР»
e-mail: Andrey.Karpov@author.kiev.ua
У зв’язку зі стрімким розвитком організації та надання електронних довірчих послуг
виникає необхідність у розбудові єдиного простору довіри на основі трансграничної
інфраструктури відкритих ключів та визнання в Україні іноземних сертифікатів відкритих
ключів, електронних підписів і печаток. Впровадження даного рішення забезпечить активний
розвиток транскордонного співробітництва та інтеграцію України у світовий електронний
інформаційний простір.
Багаторічний досвід компанії «АВТОР» забезпечив можливість реалізації
комплексного рішення, що дозволяє створити інфраструктуру відкритих ключів з
підтримкою як міжнародних, так і національних криптографічних алгоритмів. Реалізація
даного рішення базується на основі впровадження засобів криптографічного захисту
інформації (КЗІ) вітчизняного виробництва: центр сертифікації ключів «CryptoKDC», засіб
електронного цифрового підпису «CryptoLibV2», носії ключової інформації (НКІ), а також
додаткових сервісів.
Центр сертифікації ключів (ЦСК) призначений для впровадження інфраструктури
відкритих ключів в бізнес процеси і технологічні операції, які здійснюються в
автоматизованих системах інформаційно-телекомунікаційних мереж з метою реалізації
різноманітних електронних довірчих послуг. ЦСК забезпечує застосування сертифікатів
відкритих ключів сформованих у відповідності до національних або міжнародних стандартів.
Засіб ЕЦП «CryptoLib2» відповідає за виконання криптографічних перетворень і
високорівневих функцій. Завдяки вбудованим бібліотекам взаємодії, що реалізують
стандартні криптографічні інтерфейси: Windows CryptoAPI, PKCS#11, Java Cryptography
Architecture, забезпечується простота інтеграції ЦСК та НКІ з різноманітними операційними
системами та прикладними програмними комплексами, з метою реалізації технічної
інтероперабельності.
НКІ компанії «АВТОР»: «SecureToken-337» , «CryptoCard-337» і «SecureToken-337Fx»
–
це універсальні інструменти, призначені для використання в інфраструктурі відкритих
ключів, платіжних системах, системах доступу. НКІ використовується в якості електронного
ідентифікатора, носія персональної інформації, а також як засоби формування ЕЦП з
закритим ключем, що неможливо скопіювати (працюють в активному режимі).
Для повноти реалізації інфраструктури відкритих ключів компанія «АВТОР»
розробила додаткові сервіси, призначені для шифрування і підпису електронних фалів та
листів («CryptoSign», «CryptoFiles»).
А.В. Карпов Трансгранична та технічно інтероперабельна інфраструктура
відкритих ключів
Розглянуто набір рішень компанії «АВТОР», необхідних для організації
трансграничної та технічно інтероперабельної інфраструктури відкритих ключів.
Ключові слова: інфраструктура відкритих ключів, носії ключової інформації, центр
сертифікації ключів, криптографічний захист інформації.
A.V. Karpov Transboundary and technically interoperable public key infrastructure
Presented suite of solutions of "AVTOR" LLC. which are necessary for organizing
transboundary and technically interoperable public key infrastructure.
Keywords: public key infrastructure, carriers of key information, certification authority,
cryptographic protection of information.
11
УДК 004.051 (043.2)
БЫСТРОЕ ДЕЛЕНИЕ ЦЕЛЫХ ЧИСЕЛ ДЛЯ КРИПТОГРАФИЧЕСКИХ
ПРИЛОЖЕНИЙ
*В.Ю. Ковтун, к-т. техн. наук; **М.Г. Ковтун; **С.А. Гнатюк, к-т. техн. наук;
*ООО «Сайфер БИС»
**Национальный авиационный университет
e-mail:
e-mail:
Вопросы защиты информации принимают значительную актуальность, для
обеспечения конфиденциальности, целостности, подлинности и т.д. Именно
криптографические методы, в том числе и с открытым ключом, позволяют гарантировано
решить перечисленные задачи. Несмотря на известные преимущества преобразований с
открытым ключом, они обладают значительной сложностью в реализации и низкой
производительностью. В связи с этим, актуальной научно-технической задачей является
повышение производительности криптографических преобразований с открытым ключом.
Большинство криптографических преобразований оперируют большими целыми числами
(сложение/вычитание, умножение, приведение по модулю и мультипликативное
инвертирование). Авторы, обратили внимание, что операции деления, не уделяется должное
внимание.
Анализ публикаций, посвященных целочисленному делению [2-5], обосновал интерес
к операции деления больших целых чисел двойной точности на большие целые числа
одинарной точности с остатком и без него. Указанное соотношение длин делимого и
делителя вызвано необходимостью деления чисел двойной точности, после умножения чисел
одинарной точности, без их предварительного приведения по модулю. В криптосистемах на
эллиптических кривых, деление используется при генерации общесистемных параметров,
восстановлении точки из сжатого состояния, поиске случайной точки эллиптической кривой
и т.д. Среди известных алгоритмов деления [2-5], выделяется, для дальнейших исследований,
расширенная версии алгоритма Евклида (РАЕ). Ниже остановимся более подробно на
основных недостатках и предложенных модификациях.
На подготовительном этапе происходит выравнивание делимого и делителя, что
требует циклического сравнения больших целых чисел, а также сдвиги влево на один бит.
Применение представления целых чисел фиксированной длины в виде массива машинных
слов, требует производить сравнение и сдвиги по всем машинным словам даже, когда
заведомо известно, что большая часть из них нулевая и разница между номерами старших
битов сравниваемых делимого и делителя – весомая. Также в основном цикле РАЕ
производится несколько циклических сравнений делимого и делителя, а также делимого и
выровненного делителя, с последующими сдвигами, сложениями и вычитаниями. Знание
закона изменения параметров уравнения Безу, лежащего в основе алгоритма РАЕ, позволяет
предсказывать направление изменения двоичной длины делимого, частного и выровненного
делителя. Авторы предлагают сократить количество вычислительно сложных операций
сравнения, выполняемых в цикле, перейдя к приближенному сравнению целых чисел,
посредством сравнения заранее известных номеров старших битов, а в случае их равенства
переходить к сравнению чисел лишь по значимым словам. Кроме сравнения, знание
двоичной длины позволяет уменьшить число операций над машинными словами при
сдвигах, а также в вычитаниях – из закона изменения параметров уравнения Безу известно,
что уменьшаемое больше вычитаемого. Предложенные модификации позволили
существенно изменить классический РАЕ, который был переименован в модифицированный
РАЕ (МРАЕ).
По результатам теоретического и экспериментального изучения характеристик МРАЕ,
можно сделать следующие выводы:
12
1.
Разработанный МРАЕ обладает уменьшенной вычислительной сложностью за счет
операции приближенного сравнения больших целых чисел и учета специфики закона
изменения параметров уравнения Безу при вычислении числа значимых машинных слов в
элементарных операциях (вычитания, сдвиг и сравнение).
2.
Проведенная оценка вычислительной сложности РАЕ и МРАЕ, показала выигрыш в
1,24-
196,91 раз при сравнении количества операций сравнения и выигрыш в 1,34-3,26 раз
(начиная с числа 256 бит) при сравнении арифметических операций с ростом двоичной
длины большого целого числа.
3.
Производительность программной реализации МРАЕ в 1,5-3 раза выше РАЕ, с
ростом двоичной длины чисел.
4.
Вычислительная сложность МРАЕ линейно зависит от разности двоичной длины
делимого и делителя, что ограничивает область применения РАЕ/МРАЕ в случае
существенной разницы в двоичных длинах делителя и делимого.
5.
Описанный МРАЕ, не ориентирован на многопоточное выполнение, что не
позволило полностью реализовать потенциал современных многоядерных процессоров.
6.
Дальнейшие исследования будут нацелены на распараллеливание с использованием
арифметики «с отложенным переносом» [1].
Литература
1.
Охрименко А.А. Арифметика с отложенным переносом для целых чисел// Захист
інформації. – 2014. – Т.16, №2. – С. 130-138.
2. P. Barrett. Implementing the Rivest Shamir and Adleman Public Key Encryption
Algorithm on a Standard Digital Signal Processor// Proceedings CRYPTO'86. – pp. 311-323.
3. P. Montgomery. Modular multiplication without trial division // Mathematics of
Computation.-Vol. 44(170). – 1985. – pp. 519–521.
4. Stehle, P.Zimmermann: A Binary Recursive GCD Algorithm. Algorithmic Number
Theory. – LNCS Volume 3076 – 2004. – pp. 411-425.
5. T. Jebelean. An Algorithm for Exact Division. Computation Volume 15, Issue 2. – 1993. –
pp. 169–180.
В.Ю. Ковтун, М.Г. Ковтун, С.О. Гнатюк. Швидке ділення цілих чисел для
криптографічних застосувань.
В роботі розглядаються підходи до підвищення продуктивності операції ділення
великих цілих чисел подвійної точності на великі цілі числа одинарної точності на основі
розширеного алгоритму Евкліда за рахунок оперування значимими машинними словами;
використання наближеного порівняння великих цілих чисел та знання закону зміни
параметрів рівняння Безу.
Ключові слова: ділення, залишок від ділення, великі цілі числа, розширений алгоритм
Евкліда.
V.Yu. Kovtun, M.G. Kovtun, S.A. Gnatyuk. Hi-Speed Integer Division for Cryptographic
Applications.
In paper proposed approaches to improve performance of division large integers with
double-precision on single-precision integer based on the Extended Euclidean Algorithm by
operation with significant machine words, approximate comparison of large integers and knowledge
of Bezout′s equation parameters changing law.
Keywords: division, quotient, remainder, large integer’s, Extended Euclidean Algorithm.
13
УДК 004.056.5
ИСПОЛЬЗОВАНИЕ ПРЕДСТАВЛЕНИЯ ЦЕЛЫХ ЧИСЕЛ С ОТЛОЖЕННЫМ
ПЕРЕНОСОМ В КРИПТОГРАФИЧЕСКИХ ПРЕОБРАЗОВАНИЯХ
*В.Ю. Ковтун, к-т техн. наук; *А.А. Охрименко; **А.Л. Стокипный, к-т техн. наук
*ООО «Сайфер БИС»
** Харьковский национальный экономический университет
e-mail:
e-mail:
В настоящее время проходит очередной этап развития модели общественного
устройства – переход от индустриального к информационному обществу, в котором
первичную роль играет информация. Наблюдается глобальный процесс информатизации,
связанный с кардинальными изменениями структуры и характера мирового экономического
и социального развития, с переходом к наукоемкому производству и новым видам
информационного обмена. Поэтому все больше становится понятным важность защиты
информации от различных угроз, в том числе защита конфиденциальности, авторства,
целостности и т.д. Для решения указанных задач защиты информации применяются
криптографические методы, среди которых особое место отводится методам с открытым
ключом. К ним следует отнести криптопреобразования RSA, DSA, ECDSA, ECKAS-DH [4],
NTRU
[5] и другие. Несмотря на ряд преимуществ криптографических преобразований с
открытым ключом над симметричными преобразованиями, они обладают и существенным
недостатком высокой вычислительной и пространственной сложностью. Учитывая тот факт,
что практически все криптосистемы оперируют большими числами, актуальность в
повышении производительности операций над целыми числами, не вызывает сомнений.
Проведенный авторами анализ алгоритмов операций над целыми числами (сложение,
вычитание, умножение, возведение в квадрат, деление и приведение по модулю,
мультипликативное инвертирование, возведение в степень) показал, что необходимость
последовательного выполнения операций с машинными словами вызвана тем, что нужно
учитывать переносы и займы. Это, в свою очередь, накладывает существенные ограничения
на алгоритмы этих операций. Кроме того, при программной и/или аппаратной реализации
алгоритмов арифметических операций над целыми числами, эти же ограничения
накладываются на возможности компиляторов и самих процессоров, по оптимизации
программы, на этапе компиляции и этапе выполнения.
Ранее [1], авторами использовалась технология отложенного переноса из старшего
разряда младшего машинного слова в младший разряд старшего машинного слова, а также
займа в обратном направлении. Это позволило предложить новое представление целых
чисел [2], где зарезервировано несколько старших разрядов машинного слова для
накопления возможных переносов. Такое представление целых чисел получило название
Delayed Carry Form (DCF).
Дальнейшей изучение представления целых чисел с отложенным переносом, позволило
сформировать перечень арифметических операций, необходимых для работы с такими
числами, а именно: переход от двоичной-непрерывной формы к DCF и наоборот, сложение и
вычитание, сдвиг влево и вправо, умножение и возведение в квадрат. Также возможно
использование смешанного представления целых чисел двоичной-непрерывной формы и
DCF [1-
3]. В этом случае, входные данные представлены в двоичной-непрерывной форме, а
полученный результат в DCF. Так, например, для операций умножения и возведения в
квадрат обязательным является представление входных параметров операции в двоично-
непрерывной форме.
14
Применение DCF в арифметических операциях [1-3], позволило до 3-х раз повысить их
производительность на современных процессорах (32- и 64-разрядных), что, в свою очередь,
существенно повысило производительность криптосистемы в целом.
Кроме прямого увеличения производительности арифметических операций, появляется
возможность выполнения операции в два и более параллельных потока, что дает
возможность повысить их производительность до 10 раз, с ростом двоичной длины чисел до
16 тыс. бит [1-3].
В качестве дальнейших перспектив, авторы видят адаптацию предложенных
алгоритмов арифметических операций на вычислительных системах GPGPU для реализации
криптографических преобразований.
Литература
1.
Ковтун В.Ю., Охрименко А.А., Умножение целых чисел с использованием
отложенного переноса для криптосистем с открытым ключом // Информационные
технологии и системы в управлении, образовании, науке: Монография / Под ред. проф. В.С.
Пономаренко. – Х.: Цифрова друкарня №1, 2013. – С. 69-82.
2.
Охрименко А.А. Арифметика с отложенным переносом для целых чисел// Захист
інформації. – 2014. – Т.16, №2. – С. 130-138.
3.
Ковтун В.Ю., Охрименко А.А., Метод повышения производительности операции
приведения по простому модулю / А.А. Охрименко, В.Ю. Ковтун // Информационные
системы в управлении, образовании, промышленности: Монография / под ред. В.С.
Пономаренко. – Х.: Вид-во ТОВ «Щедра садиба плюс», 2014. – С. 204-219.
4. IEEE P1363-2000. Standard Specification for Public Key Cryptography.
5. IEEE P1363.1-2008. Standard Specification for Public Key Cryptographic Techniques
Based on Hard Problems over Lattices.
В.Ю. Ковтун, А.О. Охріменко, О.Л. Стокіпний. Використання представлення цілих
чисел з відкладеним переносом в криптографічних перетвореннях
Авторами запропонована форма представлення цілих чисел – DCF (Delayed Carry
Form)
, у якій резервується декілька бітів у кожному машинному слові для зберігання
накопичуваного переносу чи займу. Це дозволяє підвищити швидкодію арифметичних
операцій над цілими числами, що в свою чергу, позитивно позначається на швидкодії
криптографічних перетворень Для роботи з числами в DCF формі розроблено алгоритми
найбільш поширених арифметичних операцій.
Ключові слова: криптографічні перетворення, арифметичні операції, відкладений
перенос, представлення цілих чисел, DCF.
V.Yu. Kovtun, A.A. Okhrimenko, A.L. Stokipny. Using integer representation with
delayed carry for cryptographic transformations
Authors proposed presentation form of integers with delayed carry – DCF (Delayed Carry
Form). In DCF reserved several bits for accumulation of carry or borrow in each machine word.
This allows increase performance of arithmetic operations on integers and it has a positive effect on
performance of cryptographic transformations. For integers in DCF-form proposed algorithms of
most widely used arithmetic operations.
Keywords: cryptographic transformations, arithmetic operations, delayed carry, integer
representation, DCF.
15