Yoshino, M.
Okeya, K.
Vuillaume, C.
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.
- Koc C.K., Montgomery reduction with even modulus, 10.1049/ip-cdt:19941291
- Chevallier-Mames Benoît, Joye Marc, Paillier Pascal, Faster Double-Size Modular Multiplication from Euclidean Multipliers, Lecture Notes in Computer Science (2003) ISBN:9783540408338 p.214-227, 10.1007/10931455_18
- European Network of Excellence in Cryptology (ECRYPT). ECRYPT Yearly Report on Algorithms and Keysizes (2006),
http://www.ecrypt.eu.org/documents/D.SPA.21-1.1.pdf
- EMV. EMV Issuer and Application Security Guidelines, Version 2.1 (2007),
http://www.emvco.com/specifications.asp?show=4
- Fischer Wieland, Seifert Jean-Pierre, Increasing the Bitlength of a Crypto-Coprocessor, Cryptographic Hardware and Embedded Systems - CHES 2002 (2003) ISBN:9783540004097 p.71-81, 10.1007/3-540-36400-5_7
- Kaihara Marcelo E., Takagi Naofumi, Bipartite Modular Multiplication, Cryptographic Hardware and Embedded Systems – CHES 2005 (2005) ISBN:9783540284741 p.201-210, 10.1007/11545262_15
- Arjen, K.: Lenstra. Key Lengths (2004),
http://cm.bell-labs.com/who/akl/key_lengths.pdf
- Montgomery Peter L., Modular multiplication without trial division, 10.1090/s0025-5718-1985-0777282-x
- Menezes Alfred, van Oorschot Paul, Vanstone Scott, Handbook of Applied Cryptography, ISBN:9780849385230, 10.1201/9781439821916
- National Institute of Standards ant Technology. NIST Special Publication 800-57 Recommendation for KeyManagement Part 1: General (Revised) (2007),
http://csrc.nist.gov/CryptoToolkit/tkkeymgmt.html
- Naccache, D., M’Raïhi, D.: Arithmetic co-processors for public-key cryptography: The state of the art. In: CARDIS, pp. 18–20 (1996)
- Paillier Pascal, Low-Cost Double-Size Modular Exponentiation or How to Stretch Your Cryptoprocessor, Public Key Cryptography (1999) ISBN:9783540656449 p.223-234, 10.1007/3-540-49162-7_18
- Rivest R. L., Shamir A., Adleman L., A method for obtaining digital signatures and public-key cryptosystems, 10.1145/359340.359342
- RSA Laboratories. The Secure Use of RSA. CryptoBytes 1(3) (1995),
ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto1n3.pdf
- Yoshino Masayuki, Okeya Katsuyuki, Vuillaume Camille, Unbridle the Bit-Length of a Crypto-coprocessor with Montgomery Multiplication, Selected Areas in Cryptography ISBN:9783540744610 p.188-202, 10.1007/978-3-540-74462-7_14
- Yoshino Masayuki, Okeya Katsuyuki, Vuillaume Camille, Double-Size Bipartite Modular Multiplication, Information Security and Privacy ISBN:9783540734574 p.230-244, 10.1007/978-3-540-73458-1_18
Bibliographic reference |
Yoshino, M. ; Okeya, K. ; Vuillaume, C.. A black hen lays white eggs. Bipartite multiplier out of Montgomery one for on-line RSA verification.Smart Card Research and Advanced Applications. 8th IFIP WG 8.8/11.2 International Conference, CARDIS 2008 (London, UK, 8-11 September 2008). In: Grimaud, G.; Standaert, F.-X.;, Smart Card Research and Advanced Applications. 8th IFIP WG 8.8/11.2 International Conference, CARDIS 2008, Springer-verlag2008, p. 74-88 |
Permanent URL |
http://hdl.handle.net/2078.1/67657 |