Reconfigurable RSA accelerator based on efficient modular multipliers using high-performance modulos

Abstract

O grande desenvolvimento das comunicações, alavancado pelo recente advento da internet das coisas (internet of things-IoT) e da indústria de edge computing, tem aumentado cada vez mais a troca de dados entre diferentes dispositivos. Este aumento do tráfego de informação leva inevitavelmente a um aumento da procura de segurança, que é garantida pela encriptação. Um exemplo é o Rivest-Shamir-Adleman (RSA), que é um dos primeiros sistemas criptográficos e continua a ser utilizado em diversas aplicações. Apesar disso, seu nível de segurança está diretamente ligado ao tamanho de sua chave, o que tende a reduzir o tempo total de cifragem/decifragem ao longo dos anos, contrastando com a imensa demanda por desempenho atual. A grande maioria dos aceleradores atuais faz uso do algoritmo de multiplicação modular Montgomery para realizar a exponenciação modular de blocos RSA. Apesar disso, esta abordagem é suscetível a um grande aumento no tempo total de execução com o aumento do tamanho das chaves criptográficas, devido à sua natureza iterativa. Porém, uma opção pouco explorada são os multiplicadores baseados em compressão, que fazem uso das árvores de compressão Dadda e Wallaca para realizar a multiplicação modular, eliminando a propagação de carry e extraindo o máximo de paralelismo da implementação, pois elimina iterações excessivas. Tais multiplicadores são suscetíveis ao tipo de módulo utilizado, de modo que 2n ± 1 são chamados de módulos eficientes, enquanto módulos do formato 2n ± k apresentam pior desempenho. Esses módulos eficientes podem ser obtidos a partir dos módulos 2n ± k uma vez que são seus múltiplos, sendo chamados de psuedo-módulos. Pensando nisso, o presente trabalho propõe um acelerador criptográfico RSA baseado em pseudomódulos, no qual a exponenciação modular será realizada completamente no domínio do pseudomódulo, e apenas o seu resultado final será retornado ao domínio do módulo original, através da redução modular. Esta estratégia visa aproveitar ao máximo o menor tempo de execução dos módulos 2n ± 1, evitando que o overhead de 2n ± k seja adicionado a todas as iterações da exponenciação modular. Esta abordagem foi comparada com duas outras: a multiplicação nativa e operação de módulo do FPGA, e a multiplicação modular de Montgomery. O sistema foi sintetizado para o FPGA Cyclone V GX 5CGXFC5C6F27C7N da Altera e integrado a um núcleo NEORV32 RISC-V. Os resultados mostraram que a abordagem baseada em compressão teve um tempo total de operação cerca de 107 vezes menor que o algoritmo de Montgomery, e apresentou uma frequência de operação cerca de três vezes maior que os demais casos, para cada comprimento de chave RSA até 1024, sendo o único sensível ao uso do pseudomódulo.

Abstract: The great development of communications, leveraged by the recent advent of the IoT and edge computing industry, has increasingly increased the exchange of data between different devices. This increase in information traffic inevitably leads to an increase in the demand for security, which is guaranteed by encryption. An example is RSA, which is one of the first cryptographic systems and continues to be used in several applications. Despite this, its security level is directly linked to the size of its key, which tends to reduce the total encryption/decryption time over the years, in contrast to the immense demand for performance today. The vast majority of current accelerators make use of the Montgomery modular multiplication algorithm to perform modular exponentiation of RSA blocks. Despite this, this approach is susceptible to a large increase in total execution time with increasing cryptographic key sizes, due to its iterative nature. However, a little explored option are compression-based multipliers, which make use of Dadda and Wallaca compression trees to perform modular multiplication, eliminating carry propagation and extracting maximum parallelism from the implementation, as it eliminates excessive iterations. Such multipliers are susceptible to the type of modulo used, so that 2n ± 1 are called efficient modulos, while modulos of the format 2n ± k present worse performance. These efficient modulos can be obtained from the 2n ± k modulos once they are their multiple, being called psuedo-modulos. With this in mind, the present work proposes an RSA cryptographic accelerator based on pseudo-modulos, in which the modular exponentiation will be completely carried out in the pseudo-modulo domain, and only its final result will be returned to the original modulus domain, through reduction modular. This strategy aims to make the most of the shorter execution time of the 2n ± 1 modules, preventing the overhead of 2n ± k from being added to all iterations of the modular exponentiation. This approach was compared with two others: the FPGA?s native multiplication and modulo operation, and Montgomery?s modular multiplication. The system was synthesized to the FPGA Cyclone V GX 5CGXFC5C6F27C7N from Altera, and integrated to a NEORV32 RISC-V core. The results showed that the compression-based approach had a total operation time about 107 times smaller than the Montgomery algorithm, and presented a frequency operation about three times higher than the other cases, to every RSA key-length untill 1024, being the only one sensitive to the pseudo-modulo usage.