Time efficient dual-field unit for cryptography-related processing

[ITALIAN VERSION, English version below] Il lavoro si colloca nell'ambito dell'aritmetica dei calcolatori. In particolare, esso tratta la moltiplicazione modulare, un'operazione centrale in diverse aree quali i codici per il controllo degli errori e l'implementazione di algoritmi crittografici. In effetti, gli onerosi algoritmi di crittografia a chiave pubblica, quali i crittosistemi basati sull’algoritmo Rivest-Shamir-Adleman (RSA) e su Curve Ellittiche (EC), sono profondamente influenzati nelle loro prestazioni dalla moltiplicazione modulare. In crittografia, tale operazione può essere effettuata in due differenti strutture algebriche, precisamente i campi finiti GF(N) e GF(2^m), che normalmente richiedono soluzioni hardware distinte per velocizzare i calcoli. Il prodotto di Montgomery rappresenta la soluzione maggiormente adottata in quanto essa consente un'efficiente implementazione hardware, purché si adotti una definizione leggermente modificata di prodotto modulare. In questo lavoro, si propone una innovativa architettura unificata per il prodotto di Montgomery parallelo che consenta operazioni sia nel campo finito GF(N) che in GF(2^m), critici per i crittosistemi a chiave pubblica RSA ed ECC. Lo schema hardware intercala moltiplicazione e riduzione modulare. Inoltre, esso manipola il moltiplicando attraverso uno schema modificato di ricodifica di Booth, ed adotta uno approccio radix-4 per il modulo, consentendo tempi di esecuzione ridotti anche per dimensioni degli operandi ragionevolmente grandi. Si presenta inoltre nell’articolo un'architettura pipelined basata sui blocchi paralleli precedentemente introdotti, che richiede un numero di colpi di clock estremamente ridotto ed alti livelli di throughput per gli operandi lunghi tipicamente adoperati in applicazioni crittografiche. Una serie di risultati sperimentali, basati su una tecnologia CMOS a 0,18 µm, dimostra l'efficacia delle tecniche proposte superando i migliori risultati presentati precedentemente in letteratura. [ENGLISH VERSION] This work deals with computer arithmetic. Specifically, it focuses on modular multiplication, a central operation in several areas such as error control codes and cryptographic computing. In fact, computational demanding public key cryptographic algorithms, such as Rivest-Shamir-Adleman (RSA) and Elliptic Curve (EC) cryptosystems, are deeply affected by modular multiplication for their performance. Modular multiplication used in cryptography may be performed in two different algebraic structures, namely GF(N) and GF(2^n), which normally require distinct hardware solutions for speeding up performance. Montgomery multiplication is the most widely adopted solution, as it enables efficient hardware implementations, provided that a slightly modified definition of modular multiplication is adopted. In the paper, we propose a novel unified architecture for parallel Montgomery multiplication supporting both GF(N) and GF(2^n) finite field operations, which are critical for RSA ad ECC public key cryptosystems. The hardware scheme interleaves multiplication and modulo reduction. Furthermore, it relies on a modified Booth recoding scheme for the multiplicand and a radix-4 scheme for the modulus, enabling reduced time delays even for moderately large operand widths. In addition, we present a pipelined architecture based on the parallel blocks previously introduced, enabling very low clock counts and high throughput levels for long operands used in cryptographic applications. Experimental results, based on 0.18 µm CMOS technology, prove the effectiveness of the proposed techniques, and outperform the best results previously presented in the technical literature.