ELLIPTIC CURVE CRYPTOGRAPHY

By Z. CAINK

CONTENTS INTRODUCTION AND OVERVIEW CRYPTOGRAPHY BASICS PUBLIC-KEY CRYPTOGRAPHY RSA SYSTEMS DISCRETE LOGARITHM SYSTEMS ELLIPTIC CURVE SYSTEMS WHY ELLIPTIC CURVE CRYPTOGRAPHY? ROADMAP NOTES AND FURTHER REFERENCES FINITE FIELD ARITHMETIC INTRODUCTION TO ?NITE ?ELDS PRIME ?ELD ARITHMETIC ADDITION AND SUBTRACTION INTEGER MULTIPLICATION INTEGER SQUARING REDUCTION INVERSION NIST PRIMES BINARY ?ELD ARITHMETIC ADDITION MULTIPLICATION POLYNOMIAL MULTIPLICATION POLYNOMIAL SQUARING INVERSION AND DIVISION OPTIMAL EXTENSION ?ELD ARITHMETIC MULTIPLICATION AND REDUCTION ELLIPTIC CURVE ARITHMETIC SIMPLI?ED WEIERSTRASS EQUATIONS GROUP LAW GROUP ORDER GROUP STRUCTURE ISOMORPHISM CLASSES POINT REPRESENTATION AND THE GROUP LAW PROJECTIVE COORDINATES THE ELLIPTIC CURVE Y2 = X3 +AX +B THE ELLIPTIC CURVE Y2 + XY = X3 +AX2 +B POINT MULTIPLICATION UNKNOWN POINT FIXED POINT MULTIPLE POINT MULTIPLICATION KOBLITZ CURVES THE FROBENIUS MAP AND THE RING Z[?] CURVES WITH EF?CIENTLY COMPUTABLE ENDOMORPHISMS POINT MULTIPLICATION USING HALVING POINT HALVING PERFORMING POINT HALVING EF?CIENTLY POINT MULTIPLICATION COSTS CRYPTOGRAPHIC PROTOCOLS THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM POHLIG-HELLMAN ATTACK POLLARD’S RHO ATTACK ISOMORPHISM ATTACKS RELATED PROBLEMS DOMAIN PARAMETERS DOMAIN PARAMETER GENERATION AND VALIDATION DETERMINING THE NUMBER OF POINTS ON AN ELLIPTIC CURVE KEY PAIRS SIGNATURE SCHEMES ECDSA EC-KCDSA PUBLIC-KEY ENCRYPTION ECIES PSEC KEY ESTABLISHMENT STATION-TO-STATION ECMQV IMPLEMENTATION ISSUES SOFTWARE IMPLEMENTATION INTEGER ARITHMETIC FLOATING-POINT ARITHMETIC SIMD AND ?ELD ARITHMETIC PLATFORM MISCELLANY TIMINGS HARDWARE IMPLEMENTATION DESIGN CRITERIA FIELD ARITHMETIC PROCESSORS SECURE IMPLEMENTATION POWER ANALYSIS ATTACKS ELECTROMAGNETIC ANALYSIS ATTACKS ERROR MESSAGE ANALYSIS FAULT ANALYSIS ATTACKS TIMING ATTACKS