A secure algorithm for inversion modulo 2k
| Autor: | Carles Ferrer, Sadiel de la Fe |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Security analysis
Speedup Computer Networks and Communications Computer science Computation Modulo Modular inversion lcsh:Technology Bottleneck Public-key cryptography RSA Side channel attack Hardware_ARITHMETICANDLOGICSTRUCTURES side channel attack Computer Science::Cryptography and Security Montgomery multiplication lcsh:T business.industry Applied Mathematics Modular design modular inversion Computer Science Applications Computational Theory and Mathematics montgomery multiplication business Algorithm Software |
| Zdroj: | Dipòsit Digital de Documents de la UAB Universitat Autònoma de Barcelona Cryptography Volume 2 Issue 3 Cryptography, Vol 2, Iss 3, p 23 (2018) |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|