Check out the new USENIX Web site.

Home About USENIX Events Membership Publications Students
CARDIS '02 Abstract

A Protected Division Algorithm

Marc Joye and Karine Villegas, Gemplus Card International


Side-channel analysis is a powerful tool for retrieving secrets embedded in cryptographic devices such as smart cards. Although several practical solutions have been proposed to prevent the leakage of sensitive data, mainly the protection of the basic cryptographic operation itself has been thoroughly investigated. For example, for exponentiation-based cryptosystems (including RSA, DH or DSA), various exponentiation algorithms protected against sidechannel analysis are known. However, the exponentiation algorithm itself or the underlying cryptoalgorithm often involve division operations (for computing a quotient or a remainder). The first case appears in the normalization (resp. denormalization) process in fast exponentiation algorithms and the second case appears in the data processing before (resp. after) the call to the exponentiation operation.

This paper proposes an effcient division algorithm protected against simple side-channel analysis. The proposed algorithm applies equally well to software and hardware implementations. Furthermore, it does not impact the running time nor the memory requirements.

Keywords. Division algorithms, smart cards, side-channel analysis, SPA protected implementations.

  • View the presentation slides in HTML.
  • View the full text of this paper in PDF and Postscript. Until November 2003, you will need your USENIX membership identification in order to access the full papers.
    The Proceedings are published as a collective work, © 2002 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.

  • If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.

  • To become a USENIX Member, please see our Membership Information.

?Need help? Use our Contacts page.

Last changed: 4 Nov. 2002 aw
Technical Program
CARDIS '02 Home