×

Index calculation attacks on RSA signature and encryption. (English) Zbl 1142.94338

Summary: At Crypto’85, Desmedt and Odlyzko described a chosen-ciphertext attack against plain RSA encryption. The technique can also be applied to RSA signatures and enables an existential forgery under a chosen-message attack. The potential of this attack remained untapped until a twitch in the technique made it effective against two very popular RSA signature standards, namely ISO/IEC 9796-1 and ISO/IEC 9796-2. Following these attacks, ISO/IEC 9796-1 was withdrawn and ISO/IEC 9796-2 amended. In this paper, we explain in detail Desmedt and Odlyzko’s attack as well as its application to the cryptanalysis of ISO/IEC 9796-2.

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Canfield, E. R.; Erdos, P.; Pomerance, C., On a Problem of Oppenheim Concerning ‘Factorisation Numerorum’, J. Number Th., 17, 1-28 (1983) · Zbl 0513.10043
[2] D. Coppersmith, S. Halevi and C. Jutla, ISO 9796-1 and the new forgery strategy, Research contribution to P1363, (1999) available at http://grouper.ieee.org/groups/1363/contrib.html
[3] J. S. Coron, D. Naccache and J. P. Stern, On the security of RSA Padding, In Proceedings of Crypto ’99, LNCS Vol. 1666 (1999) Springer-Verlag, pp. 1-18. · Zbl 0940.94010
[4] Y. Desmedt and A. Odlyzko. A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, In Proceedings of Crypto ’85, LNCS Vol. 218, pp. 516-522.
[5] Dickman, K., On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv för matematik, astronomi och fysik, 22A, 10, 1-14 (1930) · JFM 56.0178.04
[6] ISO/IEC 9796, Information technology - Security techniques - Digital signature scheme giving message recovery, Part 1: Mechanisms using redundancy (1999).
[7] ISO/IEC 9796-2, Information technology - Security techniques - Digital signature scheme giving message recovery, Part 2: Mechanisms using a hash-function (1997).
[8] Lanczos, C., An iterative method for the solution of the eigenvalue problem of linear differential and integral operator, J. Res. Nat. Bur. Standards, 45, 255-282 (1950)
[9] Lenstra, A. K.; Lenstra, H. W. Jr., The Development of the Number Field Sieve (1993), Berlin: Springer-Verlag, Berlin · Zbl 0777.00017
[10] Lenstra, H. Jr., Factoring integers with elliptic curves, Ann. of Math., 126, 2, 649-673 (1987) · Zbl 0629.10006
[11] J.-F. Misarsky, How (not) to design RSA signature schemes, Public-key cryptography, Lectures Notes in Computer Science, Vol. 1431, Springer-Verlag, (1998) pp. 14-28. · Zbl 1067.94553
[12] C. Pomerance, The Quadratic Sieve Factoring Algorithm, In Advances in Cryptology, Proceedings of Eurocrypt ’84. Springer-Verlag (1985) pp. 169-182. · Zbl 0596.10006
[13] R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public key cryptosystems, CACM, Vol. 21 (1978). · Zbl 0368.94005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.