A secure algorithm for inversion modulo 2k
de la Fé, Sadiel (Universitat Autònoma de Barcelona. Departament de Microelectrònica i Sistemes Electrònics)
Ferrer, Carles (Ferrer i Ramis)
(Universitat Autònoma de Barcelona. Departament de Microelectrònica i Sistemes Electrònics)
Fecha: |
2018 |
Resumen: |
Modular inversions are widely employed in public key crypto-systems, and it is known that they imply a bottleneck due to the expensive computation. Recently, a new algorithm for inversions modulo p k was proposed, which may speed up the calculation of a modulus dependent quantity used in the Montgomery multiplication. The original algorithm lacks security countermeasures; thus, a straightforward implementation may expose the input. This is an issue if that input is a secret. In the RSA-CRT signature using Montgomery multiplication, the moduli are secrets (primes p and q). Therefore, the moduli dependent quantities related to p and q must be securely computed. This paper presents a security analysis of the novel method considering that it might be used to compute secrets. We demonstrate that a Side Channel Analysis leads to disclose the data being manipulated. In consequence, a secure variant for inversions modulo 2 k is proposed, through the application of two known countermeasures. In terms of performance, the secure variant is still comparable with the original one. |
Derechos: |
Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original. |
Lengua: |
Anglès |
Documento: |
Article ; recerca ; Versió publicada |
Materia: |
Modular inversion ;
Montgomery multiplication ;
RSA ;
Side channel attack |
Publicado en: |
Criptography, Vol. 2 (2018) , p. 1-8 |
DOI: 10.3390/cryptography2030023
El registro aparece en las colecciones:
Artículos >
Artículos de investigaciónArtículos >
Artículos publicados
Registro creado el 2020-01-20, última modificación el 2022-11-14