Name
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(16) + 1, the proposal with a 1024-bit Montgomery multiplier is at least 1.5 times faster than previous double-size Montgomery multiplications. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1587/transfun.E92.A.1851 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
Montgomery multiplication, double-size technique, RSA, efficient implementation, smartcard | Discrete mathematics,Multiplication algorithm,Montgomery reduction,Bipartite graph,Arithmetic,Kochanski multiplication,Theoretical computer science,Multiplication,Mathematics | Journal |
Volume | Issue | ISSN |
E92A | 8 | 0916-8508 |
Citations | PageRank | References |
2 | 0.46 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masayuki Yoshino | 1 | 21 | 7.43 |
| Katsuyuki Okeya | 2 | 447 | 38.47 |
| Camille Vuillaume | 3 | 90 | 10.61 |