Affordable Access

A Black Hen Lays White Eggs

IFIP Lecture Notes in Computer Science (LNCS)
Publication Date
  • Computer Science
  • Mathematics


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 ?=?2?+?1, the proposal with a 1024-bit Montgomery multiplier is 1.4 times faster than the best previous technique.Full Text at Springer, may require registration or fee

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times