A black hen lays white eggs. Bipartite multiplier out of Montgomery one for on-line RSA verification

Yoshino, M.;Okeya, K.;Vuillaume, C.
(2008) Smart Card Research and Advanced Applications. 8th IFIP WG 8.8/11.2 International Conference, CARDIS 2008 — Location: London, UK (8.September.2008)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 277.32 KB
No access

Details

Authors
  • Yoshino, M.
    Author
  • Okeya, K.
    Author
  • Vuillaume, C.
    Author
Abstract
This paper proposes novel algorithms for computing double- size modular multiplications with few modulus-dependent precomputations. Low-end devices such as smartcards are usually equipped with hardware Montgomery multipliers. However, due to progresses of mathematical attacks, security institutions such as NIST have steadily demanded longer bit-lengths for public-key cryptography, making the multipliers quickly obsolete. In an attempt to extend the lifespan of such multipliers, double-size techniques compute modular multiplications with twice the bit-length of the multipliers. Techniques are known for extending the bit-length of classical Euclidean multipliers, of Montgomery multipliers and the combination thereof, namely bipartite multipliers. However, unlike classical and bipartite multiplications, Montgomery multiplications involve modulus-dependent precomputations, which amount to a large part of an RSA encryption or signature verification. The proposed double-size technique simulates double-size multiplications based on single-size Montgomery multipliers, and yet precomputations are essentially free: in an 2048-bit RSA encryption or signature verification with public exponent e = 2/sup 16/ + 1, the proposal with a 1024-bit Montgomery multiplier is 1.4 times faster than the best previous technique.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Yoshino, M., Okeya, K., & Vuillaume, C. (2008). A black hen lays white eggs. Bipartite multiplier out of Montgomery one for on-line RSA verification. In Grimaud, G.; Standaert, F.-X.; (ed.), Smart Card Research and Advanced Applications. 8th IFIP WG 8.8/11.2 International Conference, CARDIS 2008 (p. p. 74-88). Springer-verlag. https://doi.org/10.1007/978-3-540-85893-5_6