Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Index calculation attacks on RSA signature and encryption
Coron J., Naccache D., Desmedt Y., Odlyzko A., Stern J. Designs, Codes and Cryptography38 (1):41-53,2006.Type:Article
Date Reviewed: Jul 3 2006

This paper reports on a chosen ciphertext attack on the use of the RSA algorithm for digital signatures. It also describes a related attack on RSA-based privacy, but the main interest is in signatures. This attack is applied to a working encryption standard, ISO/IEC 9796-2, which has been revised in light of this attack.

The main idea is to choose integers (the messages to be encrypted) with suitable smoothness (small prime divisors) and likelihood. The chosen ciphertexts provide a system of linear equations in exponents tied to the RSA scheme, which can reveal the message. The obstacle to this method is that subexponential running time (in the RSA modulus N) for privacy depends on the nonce &mgr; (m) for the message m being small, which is generally not the case. For signatures, the authors explain how to reduce the nonce size to hash sizes (at most a few hundred bits) by working with !28&mgr;(m) - i ... N, rather than &mgr;(m). All running times are based on the subexponential function Lx(&bgr;) = exp(&bgr;√log(x) ... loglog(x)).

The chief contribution of the paper lies not so much in the analysis of the method discussed, but in the demonstration of its practical limitations.

Reviewer:  Bruce Litow Review #: CR133016 (0705-0487)
Bookmark and Share
 
Code Breaking (E.3 ... )
 
 
Security and Protection (C.2.0 ... )
 
 
Security, Integrity, And Protection (H.2.7 ... )
 
 
Standards (E.3 ... )
 
 
Database Administration (H.2.7 )
 
 
General (C.2.0 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Code Breaking": Date
Correlation properties of an improved summation generator with 2-bit memory
Chan C., Cheng L. Signal Processing 82(6): 907-909, 2002. Type: Article
Feb 14 2003
Strength of two data encryption standard implementations under timing attacks
Hevia A., Kiwi M. ACM Transactions on Information and System Security 2(4): 416-437, 1999. Type: Article
Jul 1 2000
An information-theoretic model for steganography
Cachin C. Information and Computation 192(1): 41-56, 2004. Type: Article
Oct 5 2004
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy