ELLIPTIC CURVE HANDBOOK
INTRODUCTION TO PUBLIC-KEY CRYPTOGRAPHY CRYPTOGRAPHY COMPLEXITY PUBLIC-KEY CRYPTOGRAPHY FACTORIZATION AND PRIMALITY PRIMALITY COMPLEXITY OF FACTORING RSA DISCRETE LOGARITHM SYSTEMS GENERIC DISCRETE LOGARITHM SYSTEMS DISCRETE LOGARITHM SYSTEMS WITH BILINEAR STRUCTURE PROTOCOLS DIF?E–HELLMAN KEY EXCHANGE ASYMMETRIC DIF?E–HELLMAN AND ELGAMAL ENCRYPTION SIGNATURE SCHEME OF ELGAMAL-TYPE TRIPARTITE KEY EXCHANGE OTHER PROBLEMS I MATHEMATICAL BACKGROUND ALGEBRAIC BACKGROUND ELEMENTARY ALGEBRAIC STRUCTURES GROUPS RINGS FIELDS VECTOR SPACES INTRODUCTION TO NUMBER THEORY EXTENSION OF ?ELDS ALGEBRAIC CLOSURE GALOIS THEORY NUMBER ?ELDS FINITE ?ELDS FIRST PROPERTIES ALGEBRAIC EXTENSIONS OF A ?NITE ?ELD FINITE ?ELD REPRESENTATIONS FINITE ?ELD CHARACTERS BACKGROUND ON P-ADIC NUMBERS DE?NITION OF QP AND ?RST PROPERTIES COMPLETE DISCRETE VALUATION RINGS AND ?ELDS LIFTING A SOLUTION OF A POLYNOMIAL EQUATION THE ?ELD QP AND ITS EXTENSIONS UNRAMI?ED EXTENSIONS TOTALLY RAMI?ED EXTENSIONS MULTIPLICATIVE SYSTEM OF REPRESENTATIVES WITT VECTORS BACKGROUND ON CURVES AND JACOBIANS ALGEBRAIC VARIETIES AF?NE AND PROJECTIVE VARIETIES FUNCTION ?ELDS MORPHISMS OF AF?NE VARIETIES RATIONAL MAPS OF AF?NE VARIETIES REGULAR FUNCTIONS GENERALIZATION TO PROJECTIVE VARIETIES ABELIAN VARIETIES ALGEBRAIC GROUPS BIRATIONAL GROUP LAWS HOMOMORPHISMS OF ABELIAN VARIETIES ISOMORPHISMS AND ISOGENIES POINTS OF ?NITE ORDER AND TATE MODULES BACKGROUND ON ?-ADIC REPRESENTATIONS COMPLEX MULTIPLICATION ARITHMETIC OF CURVES LOCAL RINGS AND SMOOTHNESS GENUS AND RIEMANN–ROCH THEOREM DIVISOR CLASS GROUP THE JACOBIAN VARIETY OF CURVES JACOBIAN VARIETY OF ELLIPTIC CURVES AND GROUP LAW IDEAL CLASS GROUP CLASS GROUPS OF HYPERELLIPTIC CURVES VARIETIES OVER SPECIAL FIELDS VARIETIES OVER THE ?ELD OF COMPLEX NUMBERS ANALYTIC VARIETIES CURVES OVER C COMPLEX TORI AND ABELIAN VARIETIES ISOGENIES OF ABELIAN VARIETIES OVER C ELLIPTIC CURVES OVER C HYPERELLIPTIC CURVES OVER C VARIETIES OVER ?NITE ?ELDS THE FROBENIUS MORPHISM THE CHARACTERISTIC POLYNOMIAL OF THE FROBENIUS ENDOMORPHISM THE THEOREM OF HASSE–WEIL FOR JACOBIANS TATE’S ISOGENY THEOREM BACKGROUND ON PAIRINGS GENERAL DUALITY RESULTS THE TATE PAIRING PAIRINGS OVER LOCAL ?ELDS THE LOCAL TATE PAIRING THE LICHTENBAUM PAIRING ON JACOBIAN VARIETIES AN EXPLICIT PAIRING THE TATE–LICHTENBAUM PAIRING SIZE OF THE EMBEDDING DEGREE BACKGROUND ON WEIL DESCENT AF?NE WEIL DESCENT THE PROJECTIVE WEIL DESCENT DESCENT BY GALOIS THEORY ZARISKI CLOSED SUBSETS INSIDE OF THE WEIL DESCENT HYPERPLANE SECTIONS TRACE ZERO VARIETIES COVERS OF CURVES THE GHS APPROACH COHOMOLOGICAL BACKGROUND ON POINT COUNTING GENERAL PRINCIPLE ZETA FUNCTION AND THE WEIL CONJECTURES COHOMOLOGY AND LEFSCHETZ ?XED POINT FORMULA OVERVIEW OF ?-ADIC METHODS OVERVIEW OF P-ADIC METHODS SERRE–TATE CANONICAL LIFT MONSKY–WASHNITZER COHOMOLOGY II ELEMENTARY ARITHMETIC EXPONENTIATION GENERIC METHODS BINARY METHODS LEFT-TO-RIGHT 2K-ARY ALGORITHM SLIDING WINDOW METHOD SIGNED-DIGIT RECODING MULTI-EXPONENTIATION FIXED EXPONENT INTRODUCTION TO ADDITION CHAINS SHORT ADDITION CHAINS SEARCH EXPONENTIATION USING ADDITION CHAINS FIXED BASE POINT YAO’S METHOD EUCLIDEAN METHOD FIXED-BASE COMB METHOD 10 1 MULTIPRECISION INTEGERS 10 1 1 INTRODUCTION 10 1 2 INTERNAL REPRESENTATION 10 1 3 ELEMENTARY OPERATIONS 10 2 ADDITION AND SUBTRACTION 10 3 MULTIPLICATION 10 3 1 SCHOOLBOOK MULTIPLICATION 10 3 2 KARATSUBA MULTIPLICATION 10 3 3 SQUARING 10 4 MODULAR REDUCTION 10 4 1 BARRETT METHOD 10 4 2 MONTGOMERY REDUCTION 10 4 3 SPECIAL MODULI 10 4 4 REDUCTION MODULO SEVERAL PRIMES 10 5 DIVISION 10 5 1 SCHOOLBOOK DIVISION 10 5 2 RECURSIVE DIVISION 10 5 3 EXACT DIVISION 10 6 GREATEST COMMON DIVISOR 10 6 1 EUCLID EXTENDED GCD 10 6 2 LEHMER EXTENDED GCD 10 6 3 BINARY EXTENDED GCD 10 6 4 CHINESE REMAINDER THEOREM 10 7 SQUARE ROOT 10 7 1 INTEGER SQUARE ROOT 10 7 2 PERFECT SQUARE DETECTION 11 FINITE FIELD ARITHMETIC 11 1 PRIME ?ELDS OF ODD CHARACTERISTIC 11 1 1 REPRESENTATIONS AND REDUCTIONS 11 1 2 MULTIPLICATION 11 1 3 INVERSION AND DIVISION 11 1 4 EXPONENTIATION 11 1 5 SQUARES AND SQUARE ROOTS 11 2 FINITE ?ELDS OF CHARACTERISTIC 11 2 1 REPRESENTATION 11 2 2 MULTIPLICATION 11 2 3 SQUARING 11 2 4 INVERSION AND DIVISION 11 2 5 EXPONENTIATION 11 2 6 SQUARE ROOTS AND QUADRATIC EQUATIONS 11 3 OPTIMAL EXTENSION ?ELDS 11 3 1 INTRODUCTION 11 3 2 MULTIPLICATION 11 3 3 EXPONENTIATION 11 3 4 INVERSION 11 3 5 SQUARES AND SQUARE ROOTS 11 3 6 SPECI?C IMPROVEMENTS FOR DEGREES 3 AND 5 12 1 REPRESENTATION 12 1 1 INTRODUCTION 12 1 2 COMPUTING THE TEICHMÜLLER MODULUS 12 2 MODULAR ARITHMETIC 12 2 1 MODULAR MULTIPLICATION 12 2 2 FAST DIVISION WITH REMAINDER 12 3 NEWTON LIFTING 12 3 1 INVERSE 12 3 2 INVERSE SQUARE ROOT 12 3 3 SQUARE ROOT 12 4 HENSEL LIFTING 12 5 FROBENIUS SUBSTITUTION 12 5 1 SPARSE MODULUS 12 5 2 TEICHMÜLLER MODULUS 12 5 3 GAUSSIAN NORMAL BASIS 12 6 ARTIN–SCHREIER EQUATIONS 12 6 1 LERCIER–LUBICZ ALGORITHM 12 6 2 HARLEY’S ALGORITHM 12 7 GENERALIZED NEWTON LIFTING 12 8 APPLICATIONS 12 8 1 TEICHMÜLLER LIFT 12 8 2 LOGARITHM 12 8 3 EXPONENTIAL 12 8 4 TRACE 12 8 5 NORM III ARITHMETIC OF CURVES 13 ARITHMETIC OF ELLIPTIC CURVES 13 1 SUMMARY OF BACKGROUND ON ELLIPTIC CURVES 13 1 1 FIRST PROPERTIES AND GROUP LAW 13 1 2 SCALAR MULTIPLICATION 13 1 3 RATIONAL POINTS 13 1 4 TORSION POINTS 13 1 5 ISOMORPHISMS 13 1 6 ISOGENIES 13 1 7 ENDOMORPHISMS 13 1 8 CARDINALITY 13 2 ARITHMETIC OF ELLIPTIC CURVES DE?NED OVER FP 13 2 1 CHOICE OF THE COORDINATES 13 2 2 MIXED COORDINATES 13 2 3 MONTGOMERY SCALAR MULTIPLICATION 13 2 4 PARALLEL IMPLEMENTATIONS 13 2 5 COMPRESSION OF POINTS 13 3 ARITHMETIC OF ELLIPTIC CURVES DE?NED OVER F2D 13 3 1 CHOICE OF THE COORDINATES 13 3 2 FASTER DOUBLINGS IN AF?NE COORDINATES 13 3 4 MONTGOMERY SCALAR MULTIPLICATION 13 3 5 POINT HALVING AND APPLICATIONS 13 3 6 PARALLEL IMPLEMENTATION 13 3 7 COMPRESSION OF POINTS 14 ARITHMETIC OF HYPERELLIPTIC CURVES 14 1 SUMMARY OF BACKGROUND ON HYPERELLIPTIC CURVES 14 1 1 GROUP LAW FOR HYPERELLIPTIC CURVES 14 1 2 DIVISOR CLASS GROUP AND IDEAL CLASS GROUP 14 1 3 ISOMORPHISMS AND ISOGENIES 14 1 4 TORSION ELEMENTS 14 1 5 ENDOMORPHISMS 14 1 6 CARDINALITY 14 2 COMPRESSION TECHNIQUES 14 2 1 COMPRESSION IN ODD CHARACTERISTIC 14 2 2 COMPRESSION IN EVEN CHARACTERISTIC 14 3 ARITHMETIC ON GENUS 2 CURVES OVER ARBITRARY CHARACTERISTIC 14 3 1 DIFFERENT CASES 14 3 2 ADDITION AND DOUBLING IN AF?NE COORDINATES 14 4 ARITHMETIC ON GENUS 2 CURVES IN ODD CHARACTERISTIC 14 4 1 PROJECTIVE COORDINATES 14 4 2 NEW COORDINATES IN ODD CHARACTERISTIC 14 4 3 DIFFERENT SETS OF COORDINATES IN ODD CHARACTERISTIC 14 4 4 MONTGOMERY ARITHMETIC FOR GENUS 2 CURVES IN ODD CHARACTERISTIC 14 5 ARITHMETIC ON GENUS 2 CURVES IN EVEN CHARACTERISTIC 14 5 1 CLASSI?CATION OF GENUS 2 CURVES IN EVEN CHARACTERISTIC 14 5 2 EXPLICIT FORMULAS IN EVEN CHARACTERISTIC IN AF?NE COORDINATES 14 5 3 INVERSION-FREE SYSTEMS FOR EVEN CHARACTERISTIC WHEN H2 ?= 0 14 5 4 PROJECTIVE COORDINATES 14 5 5 INVERSION-FREE SYSTEMS FOR EVEN CHARACTERISTIC WHEN H2 = 0 14 6 ARITHMETIC ON GENUS 3 CURVES 14 6 1 ADDITION IN MOST COMMON CASE 14 6 2 DOUBLING IN MOST COMMON CASE 14 6 3 DOUBLING ON GENUS 3 CURVES FOR EVEN CHARACTERISTIC WHEN H(X) = 14 7 OTHER CURVES AND COMPARISON 15 ARITHMETIC OF SPECIAL CURVES 15 1 KOBLITZ CURVES 15 1 1 ELLIPTIC BINARY KOBLITZ CURVES 15 1 2 GENERALIZED KOBLITZ CURVES 15 1 3 ALTERNATIVE SETUP 15 2 SCALAR MULTIPLICATION USING ENDOMORPHISMS 15 2 1 GLV METHOD 15 2 2 GENERALIZATIONS 15 2 3 COMBINATION OF GLV AND KOBLITZ CURVE STRATEGIES 15 2 4 CURVES WITH ENDOMORPHISMS FOR IDENTITY-BASED PARAMETERS 15 3 TRACE ZERO VARIETIES 15 3 1 BACKGROUND ON TRACE ZERO VARIETIES 15 3 2 ARITHMETIC IN G 16 1 THE BASIC ALGORITHM 16 1 1 THE SETTING 16 1 2 PREPARATION 16 1 3 THE PAIRING COMPUTATION ALGORITHM 16 1 4 THE CASE OF NONTRIVIAL EMBEDDING DEGREE K 16 1 5 COMPARISON WITH THE WEIL PAIRING 16 2 ELLIPTIC CURVES 16 2 1 THE BASIC STEP 16 2 2 THE REPRESENTATION 16 2 3 THE PAIRING ALGORITHM 16 2 4 EXAMPLE 16 3 HYPERELLIPTIC CURVES OF GENUS 16 3 1 THE BASIC STEP 16 3 2 REPRESENTATION FOR K > 2 16 4 IMPROVING THE PAIRING ALGORITHM 16 4 1 ELIMINATION OF DIVISIONS 16 4 2 CHOICE OF THE REPRESENTATION 16 4 3 PRECOMPUTATIONS 16 5 SPECI?C IMPROVEMENTS FOR ELLIPTIC CURVES 16 5 1 SYSTEMS OF COORDINATES 16 5 2 SUB?ELD COMPUTATIONS 16 5 3 EVEN EMBEDDING DEGREE 16 5 4 EXAMPLE IV POINT COUNTING 17 POINT COUNTING ON ELLIPTIC AND HYPERELLIPTIC CURVES 17 1 ELEMENTARY METHODS 17 1 1 ENUMERATION 17 1 2 SUB?ELD CURVES 17 1 3 SQUARE ROOT ALGORITHMS 17 1 4 CARTIER–MANIN OPERATOR 17 2 OVERVIEW OF ?-ADIC METHODS 17 2 1 SCHOOF’S ALGORITHM 17 2 2 SCHOOF–ELKIES–ATKIN’S ALGORITHM 17 2 3 MODULAR POLYNOMIALS 17 2 4 COMPUTING SEPARABLE ISOGENIES IN ?NITE ?ELDS OF LARGE CHARACTERISTIC 17 2 5 COMPLETE SEA ALGORITHM 17 3 OVERVIEW OF P-ADIC METHODS 17 3 1 SATOH’S ALGORITHM 17 3 2 ARITHMETIC–GEOMETRIC–MEAN ALGORITHM 17 3 3 KEDLAYA’S ALGORITHM 18 1 CM FOR ELLIPTIC CURVES 18 1 1 SUMMARY OF BACKGROUND 18 1 2 OUTLINE OF THE ALGORITHM 18 1 3 COMPUTATION OF CLASS POLYNOMIALS 18 1 4 COMPUTATION OF NORMS 18 1 5 THE ALGORITHM 18 1 6 EXPERIMENTAL RESULTS 18 2 CM FOR CURVES OF GENUS 18 2 1 SUMMARY OF BACKGROUND 18 2 2 OUTLINE OF THE ALGORITHM 18 2 3 CM-TYPES AND PERIOD MATRICES 18 2 4 COMPUTATION OF THE CLASS POLYNOMIALS 18 2 5 FINDING A CURVE 18 2 6 THE ALGORITHM 18 3 CM FOR LARGER GENERA 18 3 1 STRATEGY AND DIF?CULTIES IN THE GENERAL CASE 18 3 2 HYPERELLIPTIC CURVES WITH AUTOMORPHISMS 18 3 3 THE CASE OF GENUS V COMPUTATION OF DISCRETE LOGARITHMS 19 GENERIC ALGORITHMS FOR COMPUTING DISCRETE LOGARITHMS 19 1 INTRODUCTION 19 2 BRUTE FORCE 19 3 CHINESE REMAINDERING 19 4 BABY-STEP GIANT-STEP 19 4 1 ADAPTIVE GIANT-STEP WIDTH 19 4 2 SEARCH IN INTERVALS AND PARALLELIZATION 19 4 3 CONGRUENCE CLASSES 19 5 POLLARD’S RHO METHOD 19 5 1 CYCLE DETECTION 19 5 2 APPLICATION TO DL 19 5 3 MORE ON RANDOM WALKS 19 5 4 PARALLELIZATION 19 5 5 AUTOMORPHISMS OF THE GROUP 19 6 POLLARD’S KANGAROO METHOD 19 6 1 THE LAMBDA METHOD 19 6 2 PARALLELIZATION 19 6 3 AUTOMORPHISMS OF THE GROUP 20 INDEX CALCULUS 20 1 INTRODUCTION 20 2 ARITHMETICAL FORMATIONS 20 2 1 EXAMPLES OF FORMATIONS 20 3 THE ALGORITHM 20 3 1 ON THE RELATION SEARCH 20 3 2 PARALLELIZATION OF THE RELATION SEARCH 20 3 4 FILTERING 20 3 5 AUTOMORPHISMS OF THE GROUP 20 4 AN IMPORTANT EXAMPLE: ?NITE ?ELDS 20 5 LARGE PRIMES 20 5 1 ONE LARGE PRIME 20 5 2 TWO LARGE PRIMES 20 5 3 MORE LARGE PRIMES 21 INDEX CALCULUS FOR HYPERELLIPTIC CURVES 21 1 GENERAL ALGORITHM 21 1 1 HYPERELLIPTIC INVOLUTION 21 1 2 ADLEMAN–DEMARRAIS–HUANG 21 1 3 ENGE–GAUDRY 21 2 CURVES OF SMALL GENUS 21 2 1 GAUDRY’S ALGORITHM 21 2 2 RE?NED FACTOR BASE 21 2 3 HARVESTING 21 3 LARGE PRIME METHODS 21 3 1 SINGLE LARGE PRIME 21 3 2 DOUBLE LARGE PRIMES 22 TRANSFER OF DISCRETE LOGARITHMS 22 1 TRANSFER OF DISCRETE LOGARITHMS TO FQ-VECTOR SPACES 22 2 TRANSFER OF DISCRETE LOGARITHMS BY PAIRINGS 22 3 TRANSFER OF DISCRETE LOGARITHMS BY WEIL DESCENT 22 3 1 SUMMARY OF BACKGROUND 22 3 2 THE GHS ALGORITHM 22 3 3 ODD CHARACTERISTIC 22 3 4 TRANSFER VIA COVERS 22 3 5 INDEX CALCULUS METHOD VIA HYPERPLANE SECTIONS VI APPLICATIONS 23 ALGEBRAIC REALIZATIONS OF DL SYSTEMS 23 1 CANDIDATES FOR SECURE DL SYSTEMS 23 1 1 GROUPS WITH NUMERATION AND THE DLP 23 1 2 IDEAL CLASS GROUPS AND DIVISOR CLASS GROUPS 23 1 3 EXAMPLES: ELLIPTIC AND HYPERELLIPTIC CURVES 23 1 4 CONCLUSION 23 2 1 SECURITY UNDER INDEX CALCULUS ATTACKS 23 2 2 TRANSFERS BY GALOIS THEORY 23 3 EF?CIENT SYSTEMS 23 3 1 CHOICE OF THE ?NITE ?ELD 23 3 2 CHOICE OF GENUS AND CURVE EQUATION 23 3 3 SPECIAL CHOICES OF CURVES AND SCALAR MULTIPLICATION 23 4 CONSTRUCTION OF SYSTEMS 23 4 2 FINDING GROUPS OF SUITABLE SIZE 23 5 PROTOCOLS 23 5 1 SYSTEM PARAMETERS 23 6 SUMMARY 24 PAIRING-BASED CRYPTOGRAPHY 24 1 PROTOCOLS 24 1 1 MULTIPARTY KEY EXCHANGE 24 1 2 IDENTITY-BASED CRYPTOGRAPHY 24 1 3 SHORT SIGNATURES 24 2 REALIZATION 24 2 1 SUPERSINGULAR ELLIPTIC CURVES 24 2 2 SUPERSINGULAR HYPERELLIPTIC CURVES 24 2 3 ORDINARY CURVES WITH SMALL EMBEDDING DEGREE 24 2 4 PERFORMANCE 24 2 5 HASH FUNCTIONS ON THE JACOBIAN 25 COMPOSITENESS AND PRIMALITY TESTING – FACTORING 25 1 COMPOSITENESS TESTS 25 1 1 TRIAL DIVISION 25 1 2 FERMAT TESTS 25 1 3 RABIN–MILLER TEST 25 1 4 LUCAS PSEUDOPRIME TESTS 25 1 5 BPSW TESTS 25 2 PRIMALITY TESTS 25 2 1 INTRODUCTION 25 2 2 ATKIN–MORAIN ECPP TEST 25 2 3 APRCL JACOBI SUM TEST 25 2 4 THEORETICAL CONSIDERATIONS AND THE AKS TEST 25 3 FACTORING 25 3 1 POLLARD’S RHO METHOD 25 3 2 POLLARD’S P ?1 METHOD 25 3 3 FACTORING WITH ELLIPTIC CURVES 25 3 4 FERMAT–MORRISON–BRILLHART APPROACH VII REALIZATION OF DISCRETE LOGARITHM SYSTEMS 26 FAST ARITHMETIC IN HARDWARE 26 1 DESIGN OF CRYPTOGRAPHIC COPROCESSORS 26 1 1 DESIGN CRITERIONS 26 2 COMPLEMENT REPRESENTATIONS OF SIGNED NUMBERS 26 3 THE OPERATION XY + Z 26 3 1 MULTIPLICATION USING LEFT SHIFTS 26 3 2 MULTIPLICATION USING RIGHT SHIFTS 26 4 REDUCING THE NUMBER OF PARTIAL PRODUCTS 26 4 1 BOOTH OR SIGNED DIGIT ENCODING 26 5 ACCUMULATION OF PARTIAL PRODUCTS 26 5 1 FULL ADDERS 26 5 2 FASTER CARRY PROPAGATION 26 5 3 ANALYSIS OF CARRY PROPAGATION 26 5 4 MULTI-OPERAND OPERATIONS 26 6 MODULAR REDUCTION IN HARDWARE 26 7 FINITE ?ELDS OF CHARACTERISTIC 2 26 7 1 POLYNOMIAL BASIS 26 7 2 NORMAL BASIS 26 8 UNI?ED MULTIPLIERS 26 9 MODULAR INVERSION IN HARDWARE 27 SMART CARDS 27 1 HISTORY 27 2 SMART CARD PROPERTIES 27 2 1 PHYSICAL PROPERTIES 27 2 2 ELECTRICAL PROPERTIES 27 2 3 MEMORY 27 2 4 ENVIRONMENT AND SOFTWARE 27 3 SMART CARD INTERFACES 27 3 1 TRANSMISSION PROTOCOLS 27 3 2 PHYSICAL INTERFACES 27 4 TYPES OF SMART CARDS 27 4 1 MEMORY ONLY CARDS (SYNCHRONOUS CARDS) 27 4 2 MICROPROCESSOR CARDS (ASYNCHRONOUS CARDS) 28 PRACTICAL ATTACKS ON SMART CARDS 28 1 INTRODUCTION 28 2 INVASIVE ATTACKS 28 2 1 GAINING ACCESS TO THE CHIP 28 2 2 RECONSTITUTION OF THE LAYERS 28 2 3 READING THE MEMORIES 28 2 4 PROBING 28 2 5 FIB AND TEST ENGINEERS SCHEME ?AWS 28 3 NON-INVASIVE ATTACKS 28 3 1 TIMING ATTACKS 28 3 2 POWER CONSUMPTION ANALYSIS 28 3 3 ELECTROMAGNETIC RADIATION ATTACKS 28 3 4 DIFFERENTIAL FAULT ANALYSIS (DFA) AND FAULT INJECTION ATTACKS 29 MATHEMATICAL COUNTERMEASURES AGAINST SIDE-CHANNEL ATTACKS 29 1 COUNTERMEASURES AGAINST SIMPLE SCA 29 1 1 DUMMY ARITHMETIC INSTRUCTIONS 29 1 2 UNI?ED ADDITION FORMULAS 29 1 3 MONTGOMERY ARITHMETIC 29 2 COUNTERMEASURES AGAINST DIFFERENTIAL SCA 29 2 1 IMPLEMENTATION OF DSCA 29 2 2 SCALAR RANDOMIZATION 29 2 3 RANDOMIZATION OF GROUP ELEMENTS 29 3 COUNTERMEASURES AGAINST GOUBIN TYPE ATTACKS 29 4 COUNTERMEASURES AGAINST HIGHER ORDER DIFFERENTIAL SCA 29 5 COUNTERMEASURES AGAINST TIMING ATTACKS 29 6 COUNTERMEASURES AGAINST FAULT ATTACKS 29 6 1 COUNTERMEASURES AGAINST SIMPLE FAULT ANALYSIS 29 6 2 COUNTERMEASURES AGAINST DIFFERENTIAL FAULT ANALYSIS 29 6 3 CONCLUSION ON FAULT INDUCTION 29 7 COUNTERMEASURES FOR SPECIAL CURVES 29 7 1 COUNTERMEASURES AGAINST SSCA ON KOBLITZ CURVES 29 7 2 COUNTERMEASURES AGAINST DSCA ON KOBLITZ CURVES 29 7 3 COUNTERMEASURES FOR GLV CURVES 30 RANDOM NUMBERS – GENERATION AND TESTING 30 1 DE?NITION OF A RANDOM SEQUENCE 30 2 RANDOM NUMBER GENERATORS 30 2 1 HISTORY 30 2 2 PROPERTIES OF RANDOM NUMBER GENERATORS 30 2 3 TYPES OF RANDOM NUMBER GENERATORS 30 2 4 POPULAR RANDOM NUMBER GENERATORS 30 3 TESTING OF RANDOM NUMBER GENERATORS 30 4 TESTING A DEVICE 30 5 STATISTICAL (EMPIRICAL) TESTS 30 6 SOME EXAMPLES OF STATISTICAL MODELS ON ?N 30 7 HYPOTHESIS TESTINGS AND RANDOM SEQUENCES 30 8 EMPIRICAL TEST EXAMPLES FOR BINARY SEQUENCES 30 8 1 RANDOM WALK 30 8 2 RUNS 30 8 3 AUTOCORRELATION 30 9 PSEUDORANDOM NUMBER GENERATORS 30 9 1 RELEVANT MEASURES 30 9 2 PSEUDORANDOM NUMBER GENERATORS FROM CURVES 30 9 3 OTHER APPLICATIONS REFERENCES