Добро пожаловать!

Pages:     | 1 || 3 | 4 |   ...   | 18 |

Figure 1a) gives a graphical representation of the MSK3 algorithm, where e.g. the block label “12” refers to T12 and indicates which operand segments are added up before they are multiplied.

Obviously, some intermediate results are used twice to compute the final result. The results can always be grouped together to form one of the three possible patterns, which can be seen in figure 1b). In order to be able to accumulate the end result in a single shift register, these patterns are reordered by descending bitposition. The remaining degree of freedom in the pattern order is exploited to optimize the calculation of the multiplier operands. With the given pattern order in figure 1b) and the data path shown in figure 1c) it is possible to compute a partial multiplication in each cycle. These optimization techniques can be applied for any number of segments, as detailed in [6].

By generalization, the following formulas can be applied to derive multiplication schemes for arbitrary segment numbers:

where and.

These formulas have been integrated in a generator program that, based on an arbitrary operand bitwidth and number of segments, produces synthesizable and efficient VHDL code for complete elliptic curve coprocessors [3],[6].

Although the presented MSK approach has a slightly worse complexity class than the recursive KOA, it provides much better adaptation possibilities to available resources by supporting arbitrary numbers of segments. For the most interesting cases of three to seven segments, our approach needs only 56%66% of the multiplication count required by the schoolbook method and for four segments just 11% more than the recursive KOA. Furthermore, the optimizations mentioned above can not be applied to the KOA directly.

Target platform Atmel Xilinx AT94K XC4085XLA XC4085XLA XCV405E Finite field degree Combinational multiplier width MSK segments Clock cycles per multiplication Frequency [MHz] Device utilization [%] Tab. 1: Implementation Results Various instances of the proposed MSK multiplier where incorporated into different elliptic curve cryptoprocessors implemented on FPGAs [2 A field programmable gate array (FPGA) is a device that can be configured to behave like an arbitrary digital circuit.]. Some characteristic numbers for the multiplier module are shown in table 1. The Atmel AT94K40 is a low cost device with restricted logic resources. In contrast, the Xilinx devices can be applied to cover the high throughput demands of dedicated server applications. The high utilization on all devices demonstrates the scalability and the comparison to similar architectures as outlined in [6] illustrates the efficiency of the proposed approach.

Hardware Acceleration for FlexiProvider The Java Cryptography Architecture (JCA) provides an unified and standardized interface for third party applications. Operations offered at this interface


from the specific public key algorithms [3 The operation GenerateKeyPair, e.g., may be implemented for different public key systems.] and thus allow for transparent interchange of, e.g., RSA and ECC. The actual algorithms are made available by an underlying Cryptographic Service Provider. The FlexiProvider has been developed at the Institute for Cryptography and Computer Algebra at TU Darmstadt. It is available as open source and thus easily extendable. Figure 2 illustrates the FlexiProvider / JCA integration, in [7] more details are to be found.

Especially on the server side the Java implemented Flexi­Provider may not provide sufficient throughput. This is why a hardware elliptic curve cryptoprocessor (ECCP) was integrated for acceleration. Since the software drivers necessary to access the ECCP are available for C only, the provided operations are encapsulated in a dynamic link library and are accessed via the Java Native Interface (JNI). The hardware acceleration is completely transparent: If a run time check in FlexiProvider yields that the ECCP is not available, an alternative software implementation is used instead. The communication overhead due to JNI and PCI bus transfers is in the range of 0.3 ms only and thus not relevant for complex operations such as digital signature generation and verification. The achieved speedups reach factors of up to 37 depending on the key bitwidth.

References [1] The FlexiProvider Group, http://www.flexiprovider.de, [2] Jung, M., Madlener, F. and Huss, S.A. A Reconfigurable Coprocessor for Finite Field Multiplication in GF(2n), Proc. of the IEEE Workshop on Heterogenous Reconfigurable Systems on Chip, Hamburg, Germany, April [3] Ernst, M., Henhapl, B., Klupsch, S. and Huss, S.A. FPGAbased Hardware Acceleration for Elliptic Curve Public Key Cryptosystems, J. of Systems and Software, 70(3), pp. 219233, Elsevier Science, March [4] Niederreiter, H. and Lidl, R. Introduction to Finite Fields and their Applications, Cambridge University Press, [5] Karatsuba, A. and Ofman, Y. Multiplication of ManyDigital Numbers by Automatic Computers, Doklady Akad. Nauk SSSR 145, 293294, 1962. Translation in PhysicsDoklady 7, 595596, [6] Ernst, M., Jung, M., Madlener, F., Huss, S.A. and Blumel, R. A Reconfigurable System on Chip Implementation for Elliptic Curve Cryptography over GF(2n), Proc. of the Workshop on Cryptographic Hardware and Embedded Systems (CHES 2002), SpringerVerlag, [7] Henhapl, B. Zur Effizienz von Elliptische Kurven Kryptographie, PhD Thesis, TU Darmstadt, А.М. Ковалев, В.Г. Скобелев Украина, Донецк, ИПММ НАН НЕСТАЦИОНАРНЫЕ СТОЙКИЕ ШИФРЫ: МОДЕЛИ И МЕТОДЫ 1. Введение. Актуальность защиты информации на современном уровне развития информационных технологий и осознание практической необходимости перехода от попыток построения абсолютно стойких шифров [1] к построению вычислительно стойких шифров [2] стимулировали интенсивную разработку парадигм, моделей и методов криптографии без достаточной теоретической проработки их основ. В результате – обилие плохо сравнимых друг с другом разработок (см., напр., [3,4]) при отсутствии их системного анализа, причем многие важные для практики вопросы, такие как поддержка работоспособного состояния криптосистемы, вообще остаются в тени. Поэтому проработка основ, связанных с систематической разработкой вычислительно стойких шифров, исследование внутренних связей между применяемыми математическими моделями и методами актуальны и с теоретической, и с прикладной точки зрения. Цель настоящего доклада – обзор полученных под руководством авторов результатов в этом направлении.

2. Основная концепция. Решение задач дискретной математики (ЗДМ) основано на поиске, алгебраических методах и/или их комбинации. Понижение сложности решения ЗДМ достигается, как правило, за счет возможности перехода от поиска к алгебраическим операциям. Поэтому естественно повысить сложность решения ЗДМ за счет такой их переформулировки, что алгебраические операции заменяются не сводящимся к ним поиском с линейной емкостной и временной сложностью генерации объекта [5]. Результат –обобщение парадигмы блок управляемых подстановок [4] до парадигмы блок управляемых бинарных отношений (БУО), аксиоматика которой разработана в [6]. Переход от операции к отношению – основа систематического построения нестационарных вычислительно стойких поточных шифров. Действительно, нестационарность обеспечивается изменением параметров отношений, а также действиями автоморфизмов конечных векторных пространств, переводящих блоки управляемых отношений в изоморфные им блоки, вычислительная стойкость – экспоненциальным ростом числа ключей и возможностью управления размерами окон (как зашифрования, так и расшифрования), поточность – выбором элементов, принадлежащих 2й проекции отношения.

Задание в неявном виде каждого отношения, принадлежащего БУО, выделяет в качестве основной операции поиск с возвращением [5,7], эффективность которого, в конечном счете, определяет скорость шифрования. Линейная емкостная и временная сложность генерации объекта делает перспективными не только чисто программные, но и аппаратнопрограммные методы реализации БУО связками «CPURAM». Применение последних существенно снижает возможности взлома, повышает скорость по сравнению с чисто программными реализациями, позволяет обеспечить работоспособное состояние на основе стандартных решений технической диагностики дискретных устройств.

3. Стандартная техника. Развитый в [6] общий метод построения БУО, состоящего из представленных в неявном виде отношений, основан на выборе отношений, у которых 2е проекции элементов – попарно непересекающиеся хорошо изученные комбинаторные структуры [8] достаточно большой мощности (именно последнее свойство обеспечивает абсолютную стойкость БУО по отношению к частотному анализу). Такой подход дает возможность выразить в единых терминах эффективность применения БУО через сложность их представления, сложность порождения элементов, принадлежащих 2м проекциям и сложность вычисления элемента, принадлежащего 1й проекции, по элементу, принадлежащему 2й проекции. Отметим, что построение 2х проекций на основе выбора попарно непересекающихся шаров дает возможность встраивать в БУО способность к исправлению ошибок [9]. При аппаратнопрограммной реализации БУО связками «CPURAM» декомпозиция на основе принципов разделяй и властвуй и балансировка [10] дает возможность эффективно применять структурнопроцедурную организацию вычислений [11], что иллюстрирует общий метод построения схем треугольного типа, разработанный в [6] и его детализации.

Перспективным является применение множеств стандартных структур данных для построения вычислительно стойких нестационарных поточных шифров. Нестационарность обеспечивается за счет выбора конкретной структуры с помощью псевдослучайных генераторов. Такой подход проиллюстрирован: в [12] – применением ограниченнодетерминированных отображений [13], представленных бинарными деревьями, в [14] – применением множества векторов рюкзачного типа с вариацией размера окна шифрования, а в [15] – применением булевых функций для зависимого от содержимого контейнера занесения информации.

4. Динамический хаос. Среди многочисленных приложений динамического хаоса [16] важную роль играет применение дискретных динамических систем (ДДС) для разработки методов защиты информации. Это направление развивается в значительной степени параллельно и независимо от криптографии. Однако можно показать, что между этими двумя направлениями имеется глубокая внутренняя связь. Действительно, применение ансамблей одномерных отображений типа «зуб пилы» для построения стойких нестационарных шифров, по своей сути, эквивалентно параллельному применению блоков управляемых перестановок, а запись информации на одномерном циклическом аттракторе эквивалентна представлению информации перестановками элементов специально подобранных множеств. Принципиально отличным от криптографических методов является зашифрование информации на основе итераций в обратном времени.

На основе развитой в [17] техники построения обратных динамических систем в [18] предложен общий метод построения стойких нестационарных поточных шифров и рассмотрены некоторые его детализации. Стойкость таких шифров обеспечивает хаос, присущий используемой ДДС. Представляется перспективным переход от ДДС над полем характеристики нуль к ее аналогам над конечными полями.

5. Примеры. Полученные результаты иллюстрируются применением программно реализованных шифров, основанных: 1) на ансамбле отображений типа «зуб пилы»; 2) ограниченнодетерминированных отображениях; 3) записи информации на циклическом аттракторе; 4) системе Лоренца.

Библиографический список Shannon C.E. Communication Theory of Secrecy Systems // Bell System Technical Journal. – 1949. – № 4.

Диффи У., Хеллмен М.Э. Защищенность и имитостойкость: Введение в криптографию // ТИИЭР.– 1979. – Т.67. – № 3.

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ. М. ТРИУМФ, 2003.

Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптография. Скоростные шифры. – СПб.: БХВПетербург, 2002.

Скобелев В.Г. Анализ дискретных систем. – Донецк: ИПММ НАНУ, 2002.

Скобелев В.В. Построение стойких к частотному анализу криптосистем на основе регулярных комбинаторных структур // Искусственный интеллект. 2004. № 1.

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М. Мир, 1980.

Дискретная математика и математические вопросы кибернетики. Т.1 / Под ред. С.В. Яблонского и О.Б. Лупанова. М. Наука, 1974.

Блейхут Р. Теория и практика кодов, контролирующих ошибки. М. Мир, 1986.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М. Мир, 1979.

Каляев А.В., Левин И.И. Модульнонаращиваемые многопроцессорные системы со структурнопроцедурной организацией вычислений. М. ЯнусК, 2003.

Pages:     | 1 || 3 | 4 |   ...   | 18 |

© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.