Published January 1, 2020
| Version v1
Publication
Open
Implementation of RSA Signatures on GPU and CPU Architectures
Creators
- 1. Center for Research and Advanced Studies of the National Polytechnic Institute
- 2. Instituto Politécnico Nacional
Description
This paper reports a constant-time CPU and GPU software implementation of the RSA exponentiation by using algorithms that offer a first-line defense against timing and cache attacks. In the case of GPU platforms the modular arithmetic layer was implemented using the Residue Number System (RNS) representation. We also present a CPU implementation of an RNS-based arithmetic that takes advantage of the parallelism provided by the Advanced Vector Extensions 2 (AVX2) instructions. Moreover, we carefully analyze the performance of two popular RNS modular reduction algorithms when implemented on many- and multi-core platforms. In the case of CPU platforms we also report that a combination of the schoolbook and Karatsuba algorithms for integer multiplication along with Montgomery reduction, yields our fastest modular multiplication procedure. In comparison with previous literature, our software library achieves faster timings for the computation of the RSA exponentiation using 1024-, 2048- and 3072-bit private keys.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تشير هذه الورقة إلى تنفيذ برنامج وحدة المعالجة المركزية (CPU) ووحدة معالجة الرسومات (GPU) في الوقت الثابت لأس RSA باستخدام الخوارزميات التي توفر دفاعًا في الخط الأول ضد هجمات التوقيت وذاكرة التخزين المؤقت. في حالة منصات GPU، تم تنفيذ الطبقة الحسابية المعيارية باستخدام تمثيل نظام أرقام البقايا (RNS). نقدم أيضًا تنفيذ وحدة المعالجة المركزية لحساب قائم على RNS يستفيد من التوازي الذي توفره تعليمات ملحقات المتجهات المتقدمة 2 (AVX2). علاوة على ذلك، نقوم بتحليل أداء اثنين من خوارزميات الاختزال المعياري RNS الشائعة بعناية عند تنفيذها على العديد من المنصات متعددة النواة. في حالة منصات وحدة المعالجة المركزية، نبلغ أيضًا أن مزيجًا من خوارزميات الكتاب المدرسي وخوارزميات كاراتسوبا لضرب الأعداد الصحيحة جنبًا إلى جنب مع تقليل مونتغومري، ينتج عنه أسرع إجراء ضرب معياري لدينا. مقارنة بالأدبيات السابقة، تحقق مكتبتنا البرمجية أوقاتًا أسرع لحساب أس RSA باستخدام مفاتيح خاصة 1024 - و 2048 - و 3072 بت.Translated Description (French)
Cet article rapporte une implémentation logicielle CPU et GPU à temps constant de l'exponentiation RSA en utilisant des algorithmes qui offrent une défense de première ligne contre les attaques de synchronisation et de cache. Dans le cas des plates-formes GPU, la couche arithmétique modulaire a été mise en œuvre à l'aide de la représentation RNS (Residue Number System). Nous présentons également une implémentation CPU d'une arithmétique basée sur RNS qui tire parti du parallélisme fourni par les instructions Advanced Vector Extensions 2 (AVX2). De plus, nous analysons soigneusement les performances de deux algorithmes de réduction modulaires RNS populaires lorsqu'ils sont mis en œuvre sur des plates-formes à plusieurs cœurs et multicœurs. Dans le cas des plates-formes CPU, nous rapportons également qu'une combinaison du manuel scolaire et des algorithmes de Karatsuba pour la multiplication des entiers avec la réduction de Montgomery, donne notre procédure de multiplication modulaire la plus rapide. Par rapport à la littérature précédente, notre bibliothèque logicielle permet d'obtenir des temps plus rapides pour le calcul de l'exponentiation RSA à l'aide de clés privées de 1024, 2048 et 3072 bits.Translated Description (Spanish)
Este documento informa sobre una implementación de software de CPU y GPU en tiempo constante de la exponenciación RSA mediante el uso de algoritmos que ofrecen una defensa de primera línea contra ataques de tiempo y caché. En el caso de las plataformas GPU, la capa aritmética modular se implementó utilizando la representación del Sistema de Números de Residuos (RNS). También presentamos una implementación de CPU de una aritmética basada en RNS que aprovecha el paralelismo proporcionado por las instrucciones Advanced Vector Extensions 2 (AVX2). Además, analizamos cuidadosamente el rendimiento de dos algoritmos de reducción modulares de RNS populares cuando se implementan en plataformas de muchos y múltiples núcleos. En el caso de las plataformas de CPU, también informamos que una combinación del libro de texto y los algoritmos de Karatsuba para la multiplicación de enteros junto con la reducción de Montgomery, produce nuestro procedimiento de multiplicación modular más rápido. En comparación con la literatura anterior, nuestra biblioteca de software logra tiempos más rápidos para el cálculo de la exponenciación RSA utilizando claves privadas de 1024, 2048 y 3072 bits.Files
08949525.pdf.pdf
Files
(245 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:7eec019791bb5177ee0b703cd98b38c4
|
245 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- تنفيذ توقيعات RSA على معماريات وحدة معالجة الرسومات (GPU) ووحدة المعالجة المركزية (CPU)
- Translated title (French)
- Mise en œuvre des signatures RSA sur les architectures GPU et CPU
- Translated title (Spanish)
- Implementación de firmas RSA en arquitecturas de GPU y CPU
Identifiers
- Other
- https://openalex.org/W2997555836
- DOI
- 10.1109/access.2019.2963826
References
- https://openalex.org/W1507823573
- https://openalex.org/W1516729797
- https://openalex.org/W1552834175
- https://openalex.org/W1565956254
- https://openalex.org/W1613874182
- https://openalex.org/W1649758727
- https://openalex.org/W1773872090
- https://openalex.org/W1805549252
- https://openalex.org/W186989516
- https://openalex.org/W187332811
- https://openalex.org/W1996360405
- https://openalex.org/W2042923641
- https://openalex.org/W2045682094
- https://openalex.org/W2108157916
- https://openalex.org/W2132249288
- https://openalex.org/W2145218124
- https://openalex.org/W2203293987
- https://openalex.org/W2482539089
- https://openalex.org/W2505286155
- https://openalex.org/W2593653970
- https://openalex.org/W2594864105
- https://openalex.org/W2607866675
- https://openalex.org/W2621530037
- https://openalex.org/W2755396449
- https://openalex.org/W2890383074
- https://openalex.org/W4237773356
- https://openalex.org/W900968380