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= 216+ 1, the proposal with a 1024-bit Montgomery multiplier is 1.4 times faster than the best previous technique. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-85893-5_6 | CARDIS |
Keywords | Field | DocType |
single-size montgomery multiplier,montgomery multiplier,double-size technique,signature verification,montgomery multiplication,1024-bit montgomery multiplier,black hen lays white,modulus-dependent precomputations,double-size multiplication,double-size modular multiplication,hardware montgomery multiplier,smartcard,modular multiplication,public key cryptography | Computer science,Cryptography,Bipartite graph,Algorithm,Arithmetic,Smart card,Real-time computing,Encryption,Multiplier (economics),NIST,Modular design,Euclidean geometry | Conference |
Citations | PageRank | References |
1 | 0.38 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masayuki Yoshino | 1 | 21 | 7.43 |
| Katsuyuki Okeya | 2 | 447 | 38.47 |
| Camille Vuillaume | 3 | 90 | 10.61 |