Design of an efficient public-key cryptographic library for RISC-basedsmart cards

by Jean-François DHEM
(PhD Thesis presented May 6th, 1998)

A complete version (without Appendixes) of my PhD Thesis can be found here in Adobe PDF format.

Chapter 1: Introduction

Chapter 2: Modular multiplication

2.1 Introduction
2.1.1 History
Brickell method
Sedlak method
Multiplication by the inverse
Working in residue/redundant number systems (RNS)
2.2 Recent results on modular multiplications
2.2.1 Notations
2.2.2 Interleaved multiplications-reductions
2.2.3 Scholar method
2.2.4 Improved Barrett algorithm
Bounds on the error on the quotient
Interleaved reduction and multiplication
Choice of the parameters to avoid corrections during a modular exponentiation
2.2.5 Quisquater's algorithm
Computation of
Choice of the smallest
Bounds on the error on the quotient
Choice of the parameters to avoid corrections during a modular exponentiation
2.2.6 Montgomery algorithm
2.2.7 Number of operations and implementation
Note on the multiply-accumulate
Software implementation of Barrett/Quisquater modular multiplication
Comparison between Barrett and Quisquater methods
Evaluation of the number of operations
"Hardware" implementation 1
"Hardware" implementation 2
Remark on the construction of a 32 X 32 + 32 + 32 multiplier
Implementation of Montgomery method
Timing of our algorithms with all the improvements
2.2.8 Modular Squaring
2.3 Multiplication using Karatsuba method
2.4 Conclusion

Chapter 3: Exponentiation

3.1 Addition chains
3.2 Addition-subtraction chain
3.3 Square and multiply (binary algorithm)
3.4 m-ary method
3.5 Sliding window
3.5.1 Choice and minimization of the precomputations for the sliding window
Unknown exponent in advance
Computation of the "optimal" size for the sliding window
3.6 Fixed exponent
3.7 Multi-exponentiation
3.8 Fixed base methods (BGMW)
3.9 Exponent recoding
3.10 Conclusion

Chapter 4: Timing Attack

4.1 The vulnerable model
4.2 A theoretical example
4.3 A practical attack
4.3.1 The implementation
4.3.2 The model
4.3.3 A first attempt: mean-based attack
4.3.4 Variance-based attack
4.3.5 Attacking the next bits
4.3.6 Practical results
4.3.7 Choice of delta
4.3.8 Erroneous deductions
4.3.9 Respect of the hypotheses
4.3.10 Possible improvements and further research
4.4 Conclusion

Chapter 5: Details on the DECA cryptographic library

5.1 Low level functions for multi-precision integer arithmetic
5.2 Functions based on the modular exponentiation
5.2.1 RSA decryption/signature using Chinese Remainder Theorem
5.2.2 DSS signature and veri,cation algorithms
5.3 Secret key algorithms and hash functions
5.4 Random number generators (RNG)
5.4.1 Statistical tests
5.4.2 Types of generators
True RNG
Software based generators
Linear congruential generators (LCG)
Linear feedback shift registers (LFSR)
Blum-Blum-Shub (BBS) and RSA generators
Micali-Schnorr generator
Other generators
5.4.3 DECA generator
Quick description of the generator
Explanation of the choices
Update of the seed
Protection against physical attacks
5.5 Prime numbers generation
5.5.1 Distribution of primes
5.5.2 Sieve
5.5.3 Pseudo-primality tests
Fermat test
Solovay-Strassen test
Miller-Rabin test
Random quadratic Frobenius test (RQFT)
5.5.4 True primality tests
Pocklington-Lehmer test
5.5.5 RSA primes generation
5.5.6 Strong primes
Elliptic curve factoring
Random square factoring
Cycling encryption attack
Probability to occur for a large prime factor
5.5.7 DECA primality test function
5.5.8 RSA strong-primes generation process of DECA
5.5.9 RSA parameters generation for DECA
5.6 Greatest common divisor (GCD) of two integers
5.6.1 Euclidean GCD
5.6.2 Binary GCD
5.6.3 Complexity of GCD algorithms
5.6.4 Our GCD implementation
5.7 Tests
5.8 Remark about elliptic curves
5.9 Conclusion

Chapter 6: Complementary studies

6.1 Lossless compression algorithms for smart cards
Decompressor alone, used EEPROM
Decompressor alone, without EEPROM
Compressor and decompressor with EEPROM
6.1.1 Algorithms options
Lossy or lossless
Dynamic or static
Size of the conversion table
Resistance to noise attack
6.1.2 Types of compression
Size of the alphabet
6.1.3 Huffman algorithm
Creation of the table by the modeler
Memory requirements
6.1.4 Arithmetic algorithm
6.1.5 Compression effciency
Obtained results
6.1.6 Conclusions
6.2 Download of applications in smart cards
6.2.1 General scenario
6.2.2 Card point of view
Download by blocks using chained hashing
Download by blocks using multiplicative properties of some hash functions
6.2.3 Download using public-key certificates
Key distribution
Application download
6.2.4 Using zero-knowledge techniques
Key distribution
Application download
6.3 Securization of a GSM-banking application
6.3.1 Basic banking applications with GSM
6.3.2 Example of implementation
Transaction request from the mobile (MS) to the Bank
Transaction response from Bank to MS
6.3.3 Remarks

Chapter 7: Conclusions and perspectives



The jury was constituted by:

Prof. J.-J. Quisquater (UCL/DICE) - Promoter
Prof. J.-D. Legat (UCL/DICE)
Dr. M. Girault (CNET Caen - France)
Prof. B. Macq (UCL/TELE)
Dr. P. Paradinas (GEMPLUS - France)
Prof. C. Trullemans (UCL/DICE) - Chair

Goto : J-F Dhem's homepage

Last modified: Tue Jan 30 22:24:32 2001