Abstract
On Crypto’ 88, Matsumoto, Kato, and Imai presented protocols to speed up secret computations with insecure auxiliary devices. The two most important protocols enable a smart card to compute the secret RSA operation faster with the help of a server that is not necessarily trusted by the card holder.
It was stated that if RSA is secure, the protocols could only be broken by exhaustive search in certain spaces. Our main attacks show that much smaller search spaces suffice. These attacks are passive and therefore undetectable.
It was already known that one of the protocols is vulnerable to active attacks. We show that this holds for the other protocol, too. More importantly, we show that our attack may still work if the smart card checks the correctness of the result; this was previously believed to be an easy measure excluding all active attacks.
Finally, we discuss attacks on related protocols.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
89 Martin Abadi, Joan Feigenbaum, Joe Kilian: On Hiding Information from an Oracle; Journal of Computer and System Sciences 39/1 (1989) 21–50.
92 Ross Anderson: Personal communication, 26.5.1992; to be submitted to Electronics Letters.
90 Paul Barrett, Raymund Eisele: The smart diskette — A universal user token and personal crypto-engine; Crypto’ 89, LNCS 435, Springer-Verlag, Heidelberg 1990, 74–79.
92 Jurjen Bos: Practical Privacy; Proefschrift, Technische Universiteit Eindhoven 1992.
86 Joan Feigenbaum: Encrypting Problem Instances, Or..., Can You Take Advantage of Someone Without Having to Trust Him?; Crypto’ 85, LNCS 218, Springer-Verlag, Berlin 1986, 477–488.
90 Shin-ichi Kawamura, Atsushi Shimbo: Performance Analysis of Server-Aided Secret Computation Protocols for the RSA Cryptosystem; The Transactions of The Institute of Electronics, Information and Communication Engineers IEICE, E73/7 (1990) 1073–1080.
91 Chi-Sung Laih, Sung-Ming Yen, Lein Harn: Two Efficient Server-Aided Secret Computation Protocols Based on the Addition Sequence; Asiacrypt’ 91 — Abstracts, 270–274.
91 Tsutomu Matsumoto, Hideki Imai: Human Identification Through Insecure Channel; Eurocrypt’ 91, LNCS 547, Springer-Verlag, Berlin 1991, 409–421.
90 Tsutomu Matsumoto, Koki Kato, Hideki Imai: Speeding up Secret Computations with Insecure Auxiliary Devices; Crypto’ 88, LNCS 403, Springer-Verlag, Berlin 1990, 497–506.
89 Wyn L. Price, Bernard Chorley: The Intelligent Token or’ super-Smart’ Card; SMART CARD 2000 (1987), North-Holland, Amsterdam 1989, 133–138.
82 Jean-Jaques Quisquater, C. Couvreur: Fast Decipherment Algorithm for RSA Public-Key Cryptosystem; Electronics Letters 18/21 (1982) 905–907.
91 Jean-Jaques Quisquater, Marijke De Soete: Speeding up Smart Card RSA Computation with Insecure Coprocessors; Proceedings Smart Cards 2000 (1989), North-Holland, Amsterdam 1991, 191–197.
91 Jean-Jaques Quisquater, Dominique de Waleffe, Jean-Pierre Bournas: Corsair: A chip card with fast RSA capability; Proceedings Smart Cards 2000 (1989), North-Holland, Amsterdam 1991, 199–206.
78 Ronald L. Rivest, Adi Shamir, Leonard Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems; Communications of the ACM 21/2 (1978) 120–126, reprinted: 26/1 (1983) 96–99.
90 Atsushi Shimbo, Shin-ichi Kawamura; Factorisation attack on certain server-aided computation protocols for the RSA secret transformation; Electronics Letters 26/17 (1990) 1387–1388.
91 Dominique de Waleffe, Jean-Jaques Quisquater: CORSAIR: A Smart Card for Public Key Cryptosystems; Crypto’ 90, LNCS 537, Springer-Verlag, Berlin 1991, 502–513.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pfitzmann, B., Waidner, M. (1993). Attacks on Protocols for Server-Aided RSA Computation. In: Rueppel, R.A. (eds) Advances in Cryptology — EUROCRYPT’ 92. EUROCRYPT 1992. Lecture Notes in Computer Science, vol 658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47555-9_13
Download citation
DOI: https://doi.org/10.1007/3-540-47555-9_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56413-3
Online ISBN: 978-3-540-47555-2
eBook Packages: Springer Book Archive