implementaciones aritméticas en dispositivos de hardware...

Aritmética Computacional invierno 2005

Francisco Rodríguez Henríquez

Implementaciones Aritméticasen Dispositivos de Hardware

Reconfigurable



Antecedentes y Motivación

Modelo de Capas para Sistemas de Seguridad



Aplicaciones: correo electrónico seguro, monedero digital, elecciones electrónicas, cortafuegos, etc.

Aplicaciones: correo electrónico seguro, monedero digital, elecciones electrónicas, cortafuegos, etc.

Protocolos de Comunicación: SSL/TLS/WTLS, IPSEC, IEEE 802.11, etc.

Protocolos de Comunicación: SSL/TLS/WTLS, IPSEC, IEEE 802.11, etc.

Servicios de Seguridad: Confidencialidad, Integridad de Datos, Autenticación, No-Repudio

Servicios de Seguridad: Confidencialidad, Integridad de Datos, Autenticación, No-Repudio

Funciones Criptográficas: Cifrar/Descifrar, Firmar/Verificar

Funciones Criptográficas: Cifrar/Descifrar, Firmar/Verificar

Algoritmos de Llave Pública: RSA, ECCAlgoritmos de llave Simétrica: AES, DES, RC4, etc..

Algoritmos de Llave Pública: RSA, ECCAlgoritmos de llave Simétrica: AES, DES, RC4, etc..

Aritmética Computacional : Suma, Elevar al cuadrado, multiplicación, inversión y Exponenciación

Aritmética Computacional : Suma, Elevar al cuadrado, multiplicación, inversión y Exponenciación



Servicios de Seguridad

• Confidencialidad

• Autenticación

• Identificación

• Integridad

• No-repudio

• Control de acceso

• Disponibilidad



Seguridad: Bloques Básicos

• Cifrado/descifrado provee:– confidencialidad, puede proveer autenticación e

integridad de datos.• Funciones hash proveen:

– Protección de integridad, puede proveer autenticación

• Firmas Digitales proveen:– autenticación, protección de integridad, y no-

repudio.



Plataformas de implementación para algoritmos criptográficos

Software

µProcs de prop. Gen. yµProcs empotrados

µProcs de prop. Gen. yµProcs empotrados

Algoritmos Criptográficos

Hardware clásico Hardware Reconfigurable

•

FPGAsFPGAsVLSIVLSI



Pero: ¿Para qué implementar algoritmos Criptográficos en hardware?

Dos razones principales:

1. Implementaciones en software son demasiado lentas

(alg. simétricos: vel. de cifrado100 Mbit/sec alg. De

llave pública: del orden de mili segundos)

2. Las implementaciones en Hardware son

intrínsicamente más seguras: Acceso a las llaves y

modificaciones algorítmicas son considerablemente

más difíciles.



Virtex-II Platform FPGA

SwitchMatrix

SwitchMatrix

CLB,IOB,DCM

CLB,IOB,DCM

Powerful CLBActive Interconnect™

SwitchMatrix

Slice S0

Slice S1

Slice S2

Slice S3

• Fully buffered• Fast, predictable

• 18b x 18b multiplier• 200+ MHz pipelined

Multipliers

BRAM• 8 LUTs• 128b distributed RAM• Wide input functions (32:1)• Support for slices based

multipliers

Block RAM• 18KBit True Dual Port• Up to 3 Mbits / device



Tarjeta Spartan-3



Virtex-II Pro

Feature/Product XC2VP2

XC2VP4

XC2VP7

XC2VP20

XC2VP30

XC2VP40

XC2VP50

XC2VP70

XC2VP100

XC2VP125

EasyPath cost reduction - - - - XCE2VP30

XCE2VP40

XCE2VP50

XCE2VP70

XCE2VP100

XCE2VP125

Logic Cells 3,168 6,768 11,088 20,880 30,816 43,632 53,136 74,448 99,216 125,136

Slices 1,408 3,008 4,928 9,280 13,696 19,392 23,616 33,088 44,096 55,616BRAM (Kbits) 216 504 792 1,584 2,448 3,456 4,176 5,904 7,992 10,00818x18 Multipliers 12 28 44 88 136 192 232 328 444 556Digital Clock Management Blocks 4 4 4 8 8 8 8 8 12 12

Config (Mbits) 1.31 3.01 4.49 8.21 11.36 15.56 19.02 25.6 33.65 42.78

PowerPC Processors 0 1 1 2 2 2 2 2 2 4

Max Available Multi-Gigabit Transceivers* 4 4 8 8 8 12* 16* 20 20* 24*

Max Available User I/O* 204 348 396 564 644 804 852 996 1164 1200

1 Logic Cell = (1) 4-input LUT + (1) FF + (1) Carry Logic1 CLB = (4) Slices

http://www.xilinx.com/products/tables/fpga.htm#v2p



Cómputo Reconfigurable

ASIC HardwareReconfigurable

Procesador

Desempeño

Flexibilidad

Costo por Unidad

Costo de Desarrollo



Cómo se escoge la plataforma de Implementación

Algunos factores que determinan esta elección son:• Desempeño deseado• Costo [por unidad, costo de desarrollo]• Consumo de energía • Flexibilidad

– Cambio de parámetros– Agilidad algorítmica

• Seguridad Física

Ventajas del hardware Reconfigurable



1. Agilidad Algorítmica2. Algoritmos actualizables [upgrading]3. Eficiencia Arquitectural4. Eficiencia en disposición de recursos5. Modificación algorítimica6. Aceleración (speedup) con respecto al software7. Eficiencia de costo (con respecto a ASIC)



Algoritmos aritméticos en FPGAs

Ventajas algorítmicasOperaciones lógicas simples (a nivel de bit)Replicación de BloquesAlta longitud de bloque

FPGAsFPGAs funcionan a nivel bitLos bloques pueden ser replicadosEs posible obtener paralelismo real (Alto número de puertos Entrada/Salida)Mayor Seguridad FísicaFlexibilidadAlta Densidad

Propiedades útiles de FPGAs



Operaciones a nivel bit (XOR, AND, OR, etc.)

LUT4 x 1

X = a + bY = X + cZ = Y + d

Z = a + b + c + d

Uso de lógica 4-input/1-output usa menos espacio




Substitución

a. Valores precalculados almacenados en memoria→ ahorra tiempo de cómputob. Valores calculados en tiempo de cómputo → consume tiempoc. Misma idea que en (a) pero uso de memorias dedicadas → solución rápida




Permutación

Permutación = [1, 5, 4, 3, 2, 6]

Rearreglo de bits (realambrado) → operación gratuita




Corrimientos y rotación

A[31:24]

B[23:16]

C[15:8]

D[7:0]

A[31:24]

B[23:16]

C[15:8]

D[7:0] IN[24:0]

OUT[31:0]

8-bit

Shift left IN[31:0] 8-bitA[31:24] B[23:16] C[15:8] D[7:0]

(rotación a la izquierda 8 bit)B[23:16] C[15:8] D[7:0] A[31:24]




1st

Round2nd

Roundnth

RoundLatch Latch Latch

CE CLK CE CLK CE CLK

IN Out

OneRound

CE CLK

INSelect

OutLatch

Estrategia Iterativa:• ejecuta n ciclos de reloj para una

operación.• Utiliza menos hardware.• baja velocidad.Estrategia Pipeline:• La salida es producida en cada ciclo de reloj.• Utiliza mucho hardware.• Alta velocidad.

Iterative

Pipeline

Propiedades útiles de FPGAs: Paralelismo



X = a + bY = X + cZ = Y + d

X = a + bY = a + b + cZ = a + b + c + d

Un cicloTres ciclos

Y espera a X y Z espera a Y X, Y, y Z son independientes

bloques de 128-bit

8 8

16 16

32 32

...

...

...

procesadoresDe 8 bits

procesadoresde 16 bitsprocesadoresde 32 bits

Software

bloques de 128 bits

bloques de 128 bits

FPGAs



Case of Study 1: GF(2m) Squaring



Squaring: Example

• Let A be an element of the finite field F=GF(25). Then, the square of Ais given as,

a4 0 a3 0 a2 0 a1 0 a0

In general, for an arbitrary element A in the field F=GF(25), we have,

( ) ( ) ( ) ( ) ∑∑∑−

=

−

=

−

=

=⎟⎠⎞

⎜⎝⎛⎟⎠⎞

⎜⎝⎛===

1

0

21

0

1

0

2m

i

ii

m

i

ii

m

i

ii xaxaxaxAxAxAxC

a4a3a2a1a0 * a4a3a2a1a0

a4a0 a3a0 a2a0 a1a0 a0a0a4a1 a3a1 a2a1 a1a1 a0a1

a4a2 a3a2 a2a2 a1a2 a0a2a4a3 a3a3 a2a3 a1a3 a0a3

a4a4 a3a4 a2a4 a1a4 a0a4



Squaring: Software Solution

rct_word sqr_table_low[256] = {0, 1, 4, 5, 16, 17, 20, 21, 64 65, 68, 69, 80, 81, 84, 85,

256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 1024, 1025, 1028, 1029, 1040, 1041, 1044, 1045, 1088, 1089, 1092, 1093, 1104, 1105, 1108, 1109, 1280, 1281, 1284, 1285, 1296, 1297, 1300, 1301, 1344, 1345, 1348, 1349, 1360, 1361, 1364, 1365, 4096, 4097, 4100, 4101, 4112, 4113, 4116, 4117, 4160, 4161, 4164, 4165, 4176, 4177, 4180, 4181, 4352, 4353, 4356, 4357, 4368, 4369, 4372, 4373, 4416, 4417, 4420, 4421, 4432, 4433, 4436, 4437, 5120, 5121, 5124, 5125, 5136, 5137, 5140, 5141, 5184, 5185, 5188, 5189, 5200, 5201, 5204, 5205, 5376, 5377, 5380, 5381, 5392, 5393, 5396, 5397, 5440, 5441, 5444, 5445, 5456, 5457, 5460, 5461,

16384, 16385, 16388, 16389, 16400, 16401, 16404, 16405, 16448, 16449, 16452, 16453, 16464, 16465, 1646816469, 16640, 16641, 16644, 16645, 16656, 16657, 16660, 16661, 16704, 16705, 16708, 16709, 16720, 1672116724, 16725, 17408, 17409, 17412, 17413, 17424, 17425, 17428, 17429, 17472, 17473, 17476, 17477, 1748817489, 17492, 17493, 17664, 17665, 17668, 17669, 17680, 17681, 17684, 17685, 17728, 17729, 17732, 1773317744, 17745, 17748, 17749, 20480, 20481, 20484, 20485, 20496, 20497, 20500, 20501, 20544, 20545, 2054820549, 20560, 20561, 20564, 20565, 20736, 20737, 20740, 20741, 20752, 20753, 20756, 20757, 20800, 2080120804, 20805, 20816, 20817, 20820, 20821, 21504, 21505, 21508, 21509, 21520, 21521, 21524, 21525, 2156821569, 21572, 21573, 21584, 21585, 21588, 21589, 21760, 21761, 21764, 21765, 21776, 21777, 21780, 2178121824, 21825, 21828, 21829, 21840, 21841, 21844, 21845};



Squaring: Software Implementationvoid rce_FieldSqr2k_Random(rct_word *ax, rct_word *tx, rce_context *cntxt,

rct_octet *offsetptr){

rct_index i;rct_word C, S;rct_index wlen, blen_p;rct_word *tmp;

wlen = cntxt->ecp->wlen;blen_p = cntxt->ecp->blen_p;

tmp = (rct_word *) offsetptr;

tmp[0]=0; tmp[1]=0;

for (i=0; i<wlen; i++) {S = sqr_table_low[(ax[i]&0xff)];S ^= (sqr_table_low[(ax[i]>>8)&0xff]<<16);C = sqr_table_low[(ax[i]>>16)&0xff];C ^= (sqr_table_low[(ax[i]>>24)&0xff]<<16);

tmp[i*2] = S; tmp[i*2+1] = C;}

RCE_FIELD_REDUC2K(cntxt) (tmp, blen_p, cntxt->ecp->poly);

//rce_residue2k(tmp, blen_p, cntxt->ecp->poly);

for (i=0; i<wlen; i++) tx[i] = tmp[i];}



Squaring: Polynomial Multiplication Step FPGA Implementation [by Nazar Saqib]

0

2

2

4

4

6

6

2

01

2

2

3

3

axaxaxaAaxaxaxaA+++=

+++=

A = 1111A2= 1010101

implementaciones aritméticas en dispositivos de hardware...

Documents