Lattices in Physical Attacks

For more info about our services contact : help@bestpfe.com

Table of contents

I State Of The Art 
1 RSA on Embedded Devices and Physical Attacks 
1.1 RSA Cryptosystem on Embedded Devices
1.1.1 RSA Signature in Standard mode
1.1.2 RSA Signature in CRT mode
1.2 Physical Attacks
1.2.1 Non-invasive Attacks
1.2.2 Invasive Attacks
1.3 Lattices in Physical Attacks
1.3.1 SPA on Modular Exponentiation and Lattices:
1.3.2 CPA on CRT-Recombination and Lattices:
1.3.3 Fault Attacks on RSA and Lattices:
2 Lattice Reduction 
2.1 Euclidean Lattices
2.1.1 Some Basic Definitions
2.1.2 Volume and Determinant
2.1.3 Shortest Vector Problem and Orthogonality
2.2 LLL-Reduction
2.2.1 Size-Reduced Basis
2.2.2 LLL-Reduced Basis
2.2.3 A Basic Version of the LLL Algorithm
2.2.4 Bounds of LLL-Reduced Vectors
2.2.5 Complexities of the LLL, L2 and ~L1 Algorithms
2.2.6 Number of Iterations of LLL-Reduction Algorithms
2.3 Diophantine Problem and LLL-Reduction
2.3.1 Finding Small Integer Solutions
2.3.2 Simultaneous Diophantine Approximation
3 Finding Small Solutions to Polynomial Equations 
3.1 Coppersmith’s Method for Univariate Modular Equations
3.1.1 The Main Result
3.1.2 The Method
3.1.3 Complexity
3.1.4 Applications
3.2 Coppersmith’s Method for Bivariate Equations over Z
3.2.1 The Main Result
3.2.2 Core Idea of the Method
3.2.3 Applications
3.3 The BDH Method for Factoring N = prq
3.3.1 Motivations
3.3.2 The Main Result
3.3.3 The Method
II Contributions 
4 Rounding and Chaining LLL 
4.1 Speeding up Coppersmith’s Algorithm by Rounding
4.1.1 Rounding for Coppersmith’s Algorithm
4.1.2 Running time: proof of Theorem
4.1.3 A Remark on the Original Coppersmith’s Complexity
4.1.4 A Summary of the Complexities
4.2 Chaining LLL
4.2.1 Exploiting Relations Between Consecutive Lattices
4.2.2 Rounding and Chaining LLL
4.2.3 Complexity Analysis: A Heuristic Approach
4.3 Experiments
4.3.1 Practical Considerations
4.3.2 Implementation Results
4.4 Other Small-Root Algorithms
4.4.1 Gcd Generalization
4.4.2 Multivariate Equations
5 Factoring N = prqs for Large r 
5.1 BDH’s Theorem Slightly Revisited
5.2 Factoring N = prqs for Large r
5.2.1 Two Natural Approaches that Fail
5.2.2 The Main Theorem
5.2.3 An Outline of the Method
5.2.4 A Useful Lemma: Decomposition of r and s
5.2.5 Proof of the Main Theorem
5.2.6 Refinement of the Condition on r for Small s or for s Close to r
5.3 Generalization for N = Q pri i for Large ri’s
5.3.1 A Condition on r1 Depending on the Ratio r1=rk􀀀1
5.3.2 Factoring with Gaps
5.3.3 An Iterative Definition of Function t
5.3.4 Proof of the Generalization Theorem
5.4 Speeding-up by Rounding and Chaining
5.4.1 Rounding
5.4.2 Chaining
5.5 Experiments
5.5.1 Practical Considerations
5.5.2 Speed-up by Rounding and Chaining
5.5.3 Implementation Results
5.5.4 Comparison with ECM
6 Combined Attack on RSA-CRT 
6.1 Context and Principle
6.1.1 RSA Signature Using the CRT Mode
6.1.2 Countermeasures Against SCA and FI
6.2 A New Combined Attack on CRT-RSA
6.2.1 A Useful Relation
6.2.2 Recovering the Private Key
6.3 Experiments
6.4 Reducing the Complexity Using Coppersmith’s Methods
6.4.1 Bringing Up the Original Problem to Solving a Modular Equation
6.4.2 Results From Our Implementation
6.5 Countermeasures
6.5.1 Blind Before Splitting
6.5.2 Verification Blinding
6.6 Conclusion