(PhD Thesis presented May 6th, 1998)

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

- 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
- Conclusion

- 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
- Implementation
- 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
- Loops

- 2.2.8 Modular Squaring
- 2.3 Multiplication using Karatsuba method
- 2.4 Conclusion

- 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

- 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

- 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
- Conclusion

- 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

- 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
- Compression
- Decompression
- Memory requirements
- Speed

- 6.1.4 Arithmetic algorithm
- Description

- 6.1.5 Compression effciency
- Definitions
- Obtained results
- Remarks

- 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
- Personalization
- Key distribution
- Application download

- 6.2.4 Using zero-knowledge techniques
- Initialization
- 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
- Initialization
- Transaction request from the mobile (MS) to the Bank
- Transaction response from Bank to MS

- 6.3.3 Remarks

(See also my general BiBTeX bibliography)

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
*