Multiplicadores de arquitectura segmentada y su aplicación al cómputo de emparejamiento bilineales

Nidia Asunción Cortez Duarte

            
Texto completo de la Tesis    


Resumen

Las aplicaciones criptográficas requieren de implementaciones eficientes de aritmética básica sobre campos finitos tales como suma, resta, multiplicación, división, exponenciación y cálculo de raíces, por mencionar algunas, siendo la multiplicación, la operación que requiere mayor atención debido a su costo en recursos y tiempo de ejecución, además de que es la operación más utilizada en la mayoría de los algoritmos criptográficos. En esta tesis centramos nuestro interés en los algoritmos de multiplicación; partiendo del algoritmo original de Karatsuba-Ofman, analizamos algunas de sus variantes y describimos las estrategias que consideramos para diseñar una arquitectura la cual esta basada en una estructura segmentada de k-estados. Implementamos nuestras arquitecturas en dispositivos de hardware reconfigurable en el campo finito binario F2239 con k = 1,...., 3, donde cada estado está compuesto por un multiplicador de 120-bits. Asimismo, se diseño un multiplicador para el campo finito ternario F397 con k = 1,...., 4, donde cada estado esta compuesto por un multiplicador de 49-trits. Nuestras arquitecturas son capaces de cálcular en promedio k multiplicaciones cada 3 ciclos de reloj. En el campo F397 mediante una arquitectura segmentada de 4 estados fue posible calcular más de una multiplicación polinomial por cada ciclo de reloj.

Debido a que una de las aplicaciones más relevantes para este tipo de multiplicaciones es el cálculo de emparejamientos bilineales decidimos estudiarlos en esta tesis. Un emparejamiento necesita el cómputo eficiente de un ciclo principal junto con una operación adicional denominada exponenciación final. En ambos módulos se requiere evaluar muchas multiplicaciones. En este trabajo se decidió utilizar como caso de estudio el diseño del módulo de exponenciación final en característica dos. Todos los diseños se implementaron utilizando el lenguaje de descripción de hardware VHDL y se sintetizaron para dispositivos Virtex II-Pro y Virtex 5 de Xilinx. Se ocuparon las herramientas de Xilinx para descripción y simulación. De acuerdo a nuestros resultados de la simulación post-place and route en las FPGAs de Xilinx, nuestros multiplicadores son los más eficientes y nuestra implementación de la exponenciación final resulta ser competitiva con respecto a otros diseños reportados.


          Abstract

Cryptographic applications require efficient implementation of the basic arithmetic finite field operations such as field addition, subtraction, multiplication, division, exponentiation, squaring, square root, cubing and cube root computation. Among the aforementioned arithmetic operations, multiplication is by far the one that has received more attention, mostly because of its crucial role in the aforementioned cryptographic schemes besides the cost of area and time calculation. In this thesis, we focus our attention in parallel subquadratic multiplication algorithms. From the original Karatsuba-Ofman algorithm, we studied some variants recently published and we also describe the strategies that were considered to design our reconfigurable hardware architecture.We decided to use a k-stage pipeline structure. We implemented our architectures in reconfigurable hardware in the binary finite field F2239 with k = 1,..., 3, where each stage is composed of a 120 bit polynomial multiplier unit and over the ternary finite field F397 with k = 1,..., 4, where each stage is composed of a 49 trit polynomial multiplier unit. Our architectures can compute in average k field multiplications every three clock cycles. In the field F397 , our four-stage pipeline design can compute in average more than one field multiplication per clock cycle.

Since the most relevant applications of this kind of multipliers lie on bilinear pairing computation, where several field multiplications need to be computed at once, we decided to study it. A bilinear pairing needs the efficient computation of a main cycle and one additional operation called final exponentiation which is required to obtain a unique value. Both modules imply the computation of many multiplications. Therefore, the final exponentiation was considered as a good case of study for our multipliers in characteristic two. All the designs were implemented utilizing the hardware description language VHDL and were also sintetized for Virtex II-Pro and Virtex 5 FPGA devices. The Xilinx tools were utilized for description and simulation. According to our post-place and route results on Xilins FPGAs, our multipliers are the most efficient and our design of final exponentiation is competitive compared to previously published works.