. 1
( 10)



>>

This page intentionally left blank
LONDON MATHEMATICAL SOCIETY LECTURE NOTE SERIES

Managing Editor: Professor N.J. Hitchin, Mathematical Institute,
University of Oxford, 24“29 St Giles, Oxford OX1 3LB, United Kingdom

The titles below are available from booksellers, or from Cambridge University Press at www.cambridge.org

152 Oligomorphic permutation groups, P. CAMERON
153 L-functions and arithmetic, J. COATES & M.J. TAYLOR (eds)
155 Classi¬cation theories of polarized varieties, TAKAO FUJITA
¨
158 Geometry of Banach spaces, P.F.X. MULLER & W. SCHACHERMAYER (eds)
159 Groups St Andrews 1989 volume 1, C.M. CAMPBELL & E.F. ROBERTSON (eds)
160 Groups St Andrews 1989 volume 2, C.M. CAMPBELL & E.F. ROBERTSON (eds)
¨
161 Lectures on block theory, BURKHARD KULSHAMMER
163 Topics in varieties of group representations, S.M. VOVSI
164 Quasi-symmetric designs, M.S. SHRIKANDE & S.S. SANE
166 Surveys in combinatorics, 1991, A.D. KEEDWELL (ed)
168 Representations of algebras, H. TACHIKAWA & S. BRENNER (eds)
169 Boolean function complexity, M.S. PATERSON (ed)
170 Manifolds with singularities and the Adams-Novikov spectral sequence, B. BOTVINNIK
171 Squares, A.R. RAJWADE
172 Algebraic varieties, GEORGE R. KEMPF
173 Discrete groups and geometry, W.J. HARVEY & C. MACLACHLAN (eds)
174 Lectures on mechanics, J.E. MARSDEN
175 Adams memorial symposium on algebraic topology 1, N. RAY & G. WALKER (eds)
176 Adams memorial symposium on algebraic topology 2, N. RAY & G. WALKER (eds)
177 Applications of categories in computer science, M. FOURMAN, P. JOHNSTONE & A. PITTS (eds)
178 Lower K- and L-theory, A. RANICKI
179 Complex projective geometry, G. ELLINGSRUD et al
180 Lectures on ergodic theory and Pesin theory on compact manifolds, M. POLLICOTT
181 Geometric group theory I, G.A. NIBLO & M.A. ROLLER (eds)
182 Geometric group theory II, G.A. NIBLO & M.A. ROLLER (eds)
183 Shintani zeta functions, A. YUKIE
184 Arithmetical functions, W. SCHWARZ & J. SPILKER
185 Representations of solvable groups, O. MANZ & T.R. WOLF
186 Complexity: knots, colourings and counting, D.J.A. WELSH
187 Surveys in combinatorics, 1993, K. WALKER (ed)
188 Local analysis for the odd order theorem, H. BENDER & G. GLAUBERMAN
189 Locally presentable and accessible categories, J. ADAMEK & J. ROSICKY
190 Polynomial invariants of ¬nite groups, D.J. BENSON
191 Finite geometry and combinatorics, F. DE CLERCK et al
192 Symplectic geometry, D. SALAMON (ed)
194 Independent random variables and rearrangement invariant spaces, M. BRAVERMAN
195 Arithmetic of blowup algebras, WOLMER VASCONCELOS
¨
196 Microlocal analysis for differential operators, A. GRIGIS & J. SJOSTRAND
197 Two-dimensional homotopy and combinatorial group theory, C. HOG-ANGELONI et al
198 The algebraic characterization of geometric 4-manifolds, J.A. HILLMAN
Invariant potential theory in the unit ball of Cn , MANFRED STOLL
199
200 The Grothendieck theory of dessins d™enfant, L. SCHNEPS (ed)
201 Singularities, JEAN-PAUL BRASSELET (ed)
202 The technique of pseudodifferential operators, H.O. CORDES
203 Hochschild cohomology of von Neumann algebras, A. SINCLAIR & R. SMITH
204 Combinatorial and geometric group theory, A.J. DUNCAN, N.D. GILBERT & J. HOWIE (eds)
205 Ergodic theory and its connections with harmonic analysis, K. PETERSEN & I. SALAMA (eds)
207 Groups of Lie type and their geometries, W.M. KANTOR & L. DI MARTINO (eds)
208 Vector bundles in algebraic geometry, N.J. HITCHIN, P. NEWSTEAD & W.M. OXBURY (eds)
´
209 Arithmetic of diagonal hypersurfaces over ¬nite ¬elds, F.Q. GOUVEA & N. YUI
210 Hilbert C*-modules, E.C. LANCE
211 Groups 93 Galway / St Andrews I, C.M. CAMPBELL et al (eds)
212 Groups 93 Galway / St Andrews II, C.M. CAMPBELL et al (eds)
214 Generalised Euler-Jacobi inversion formula and asymptotics beyond all orders, V. KOWALENKO et al
215 Number theory 1992“93, S. DAVID (ed)
216 Stochastic partial differential equations, A. ETHERIDGE (ed)
217 Quadratic forms with applications to algebraic geometry and topology, A. PFISTER
218 Surveys in combinatorics, 1995, PETER ROWLINSON (ed)
220 Algebraic set theory, A. JOYAL & I. MOERDIJK
221 Harmonic approximation, S.J. GARDINER
222 Advances in linear logic, J.-Y. GIRARD, Y. LAFONT & L. REGNIER (eds)
223 Analytic semigroups and semilinear initial boundary value problems, KAZUAKI TAIRA
224 Computability, enumerability, unsolvability, S.B. COOPER, T.A. SLAMAN & S.S. WAINER (eds)
225 A mathematical introduction to string theory, S. ALBEVERIO et al
226 Novikov conjectures, index theorems and rigidity I, S. FERRY, A. RANICKI & J. ROSENBERG (eds)
227 Novikov conjectures, index theorems and rigidity II, S. FERRY, A. RANICKI & J. ROSENBERG (eds)
Ergodic theory of Zd actions, M. POLLICOTT & K. SCHMIDT (eds)
228
229 Ergodicity for in¬nite dimensional systems, G. DA PRATO & J. ZABCZYK
230 Prolegomena to a middlebrow arithmetic of curves of genus 2, J.W.S. CASSELS & E.V. FLYNN
231 Semigroup theory and its applications, K.H. HOFMANN & M.W. MISLOVE (eds)
232 The descriptive set theory of Polish group actions, H. BECKER & A.S. KECHRIS
233 Finite ¬elds and applications, S. COHEN & H. NIEDERREITER (eds)
234 Introduction to subfactors, V. JONES & V.S. SUNDER
235 Number theory 1993“94, S. DAVID (ed)
236 The James forest, H. FETTER & B. GAMBOA DE BUEN
237 Sieve methods, exponential sums, and their applications in number theory, G.R.H. GREAVES et al
238 Representation theory and algebraic geometry, A. MARTSINKOVSKY & G. TODOROV (eds)
240 Stable groups, FRANK O. WAGNER
241 Surveys in combinatorics, 1997, R.A. BAILEY (ed)
242 Geometric Galois actions I, L. SCHNEPS & P. LOCHAK (eds)
243 Geometric Galois actions II, L. SCHNEPS & P. LOCHAK (eds)
244 Model theory of groups and automorphism groups, D. EVANS (ed)
245 Geometry, combinatorial designs and related structures, J.W.P. HIRSCHFELD et al
246 p-Automorphisms of ¬nite p-groups, E.I. KHUKHRO
247 Analytic number theory, Y. MOTOHASHI (ed)
248 Tame topology and o-minimal structures, LOU VAN DEN DRIES
249 The atlas of ¬nite groups: ten years on, ROBERT CURTIS & ROBERT WILSON (eds)
250 Characters and blocks of ¬nite groups, G. NAVARRO
251 Gr¨ bner bases and applications, B. BUCHBERGER & F. WINKLER (eds)
o
¨
252 Geometry and cohomology in group theory, P. KROPHOLLER, G. NIBLO, R. STOHR (eds)
253 The q-Schur algebra, S. DONKIN
254 Galois representations in arithmetic algebraic geometry, A.J. SCHOLL & R.L. TAYLOR (eds)
255 Symmetries and integrability of difference equations, P.A. CLARKSON & F.W. NIJHOFF (eds)
¨
256 Aspects of Galois theory, HELMUT VOLKLEIN et al
257 An introduction to noncommutative differential geometry and its physical applications 2ed, J. MADORE
258 Sets and proofs, S.B. COOPER & J. TRUSS (eds)
259 Models and computability, S.B. COOPER & J. TRUSS (eds)
260 Groups St Andrews 1997 in Bath, I, C.M. CAMPBELL et al
261 Groups St Andrews 1997 in Bath, II, C.M. CAMPBELL et al
262 Analysis and logic, C.W. HENSON, J. IOVINO, A.S. KECHRIS & E. ODELL
263 Singularity theory, BILL BRUCE & DAVID MOND (eds)
264 New trends in algebraic geometry, K. HULEK, F. CATANESE, C. PETERS & M. REID (eds)
265 Elliptic curves in cryptography, I. BLAKE, G. SEROUSSI & N. SMART
267 Surveys in combinatorics, 1999, J.D. LAMB & D.A. PREECE (eds)
¨
268 Spectral asymptotics in the semi-classical limit, M. DIMASSI & J. SJOSTRAND
269 Ergodic theory and topological dynamics, M.B. BEKKA & M. MAYER
270 Analysis on Lie groups, N.T. VAROPOULOS & S. MUSTAPHA
271 Singular perturbations of differential operators, S. ALBEVERIO & P. KURASOV
272 Character theory for the odd order theorem, T. PETERFALVI
273 Spectral theory and geometry, E.B. DAVIES & Y. SAFAROV (eds)
274 The Mandlebrot set, theme and variations, TAN LEI (ed)
275 Descriptive set theory and dynamical systems, M. FOREMAN et al
276 Singularities of plane curves, E. CASAS-ALVERO
277 Computational and geometric aspects of modern algebra, M.D. ATKINSON et al
278 Global attractors in abstract parabolic problems, J.W. CHOLEWA & T. DLOTKO
279 Topics in symbolic dynamics and applications, F. BLANCHARD, A. MAASS & A. NOGUEIRA (eds)
280 Characters and automorphism groups of compact Riemann surfaces, THOMAS BREUER
281 Explicit birational geometry of 3-folds, ALESSIO CORTI & MILES REID (eds)
282 Auslander-Buchweitz approximations of equivariant modules, M. HASHIMOTO
283 Nonlinear elasticity, Y. FU & R.W. OGDEN (eds)
¨
284 Foundations of computational mathematics, R. DEVORE, A. ISERLES & E. SULI (eds)
285 Rational points on curves over ¬nite ¬elds, H. NIEDERREITER & C. XING
286 Clifford algebras and spinors 2ed, P. LOUNESTO
Topics on Riemann surfaces and Fuchsian groups, E. BUJALANCE, A.F. COSTA & E. MART`
287 INEZ (eds)
288 Surveys in combinatorics, 2001, J. HIRSCHFELD (ed)
289 Aspects of Sobolev-type inequalities, L. SALOFF-COSTE
290 Quantum groups and Lie theory, A. PRESSLEY (ed)
291 Tits buildings and the model theory of groups, K. TENT (ed)
292 A quantum groups primer, S. MAJID
293 Second order partial differential equations in Hilbert spaces, G. DA PRATO & J. ZABCZYK
294 Introduction to the theory of operator spaces, G. PISIER
295 Geometry and integrability, LIONEL MASON & YAVUZ NUTKU (eds)
296 Lectures on invariant theory, IGOR DOLGACHEV
297 The homotopy category of simply connected 4-manifolds, H.-J. BAUES
299 Kleinian groups and hyperbolic 3-manifolds, Y. KOMORI, V. MARKOVIC, & C. SERIES (eds)
300 Introduction to M¨ bius differential geometry, UDO HERTRICH-JEROMIN
o
301 Stable modules and the D(2)-problem, F.E.A. JOHNSON
302 Discrete and continuous nonlinear Schr¨ dinger systems, M.J. ABLOWITZ, B. PRINARI, & A.D. TRUBATCH
o
303 Number theory and algebraic geometry, MILES REID & ALEXEI SKOROBOGATOV (eds)
304 Groups St Andrews 2001 in Oxford Vol. 1, COLIN CAMPBELL, EDMUND ROBERTSON & GEOFF SMITH (eds)
305 Groups St Andrews 2001 in Oxford Vol. 2, C.M. CAMPBELL, E.F. ROBERTSON & G.C. SMITH (eds)
307 Surveys in combinatorics 2003, C.D. WENSLEY (ed)
309 Corings and comodules, TOMASZ BRZEZINSKI & ROBERT WISBAUER
310 Topics in dynamics and ergodic theory, SERGEY BEZUGLYI & SERGIY KOLYADA (eds)
312 Foundations of computational mathematics, Minneapolis 2002, FELIPE CUCKER et al (eds)
London Mathematical Society Lecture Note Series. 317




Advances in Elliptic Curve
Cryptography

Edited by

Ian F. Blake
University of Toronto
Gadiel Seroussi
Hewlett-Packard Laboratories
Nigel P. Smart
University of Bristol
cambridge university press
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo

Cambridge University Press
The Edinburgh Building, Cambridge cb2 2ru, UK
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
Information on this title: www.cambridge.org/9780521604154

© Cambridge University Press 2005


This book is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.

First published in print format 2005

isbn-13 978-0-511-11161-7 eBook (MyiLibrary)
isbn-10 0-511-11161-4 eBook (MyiLibrary)

isbn-13 978-0-521-60415-4 paperback
isbn-10 0-521-60415-x paperback




Cambridge University Press has no responsibility for the persistence or accuracy of
urls for external or third-party internet websites referred to in this book, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
Contents




Preface page ix
Abbreviations and Standard Notation xi
Authors xv
Part 1. Protocols
Chapter I. Elliptic Curve Based Protocols
N.P. Smart 3
I.1. Introduction 3
I.2. ECDSA 4
I.3. ECDH/ECMQV 8
I.4. ECIES 12
I.5. Other Considerations 18
Chapter II. On the Provable Security of ECDSA
D. Brown 21
II.1. Introduction 21
II.2. De¬nitions and Conditions 23
II.3. Provable Security Results 32
II.4. Proof Sketches 33
II.5. Further Discussion 36
Chapter III. Proofs of Security for ECIES
A.W. Dent 41
III.1. De¬nitions and Preliminaries 42
III.2. Security Proofs for ECIES 50
III.3. Other Attacks Against ECIES 58
III.4. ECIES-KEM 61




v
vi Contents
Part 2. Implementation Techniques
Chapter IV. Side-Channel Analysis
E. Oswald 69
IV.1. Cryptographic Hardware 70
IV.2. Active Attacks 71
IV.3. Passive Attacks 72
IV.4. Simple SCA Attacks on Point Multiplications 77
IV.5. Differential SCA Attacks on Point Multiplications 84
Chapter V. Defences Against Side-Channel Analysis
M. Joye 87
V.1. Introduction 87
V.2. Indistinguishable Point Addition Formul¦ 88
V.3. Regular Point Multiplication Algorithms 93
V.4. Base-Point Randomization Techniques 97
V.5. Multiplier Randomization Techniques 98
V.6. Preventing Side-Channel Analysis 100
Part 3. Mathematical Foundations
Chapter VI. Advances in Point Counting
F. Vercauteren 103
VI.1. p-adic Fields and Extensions 104
VI.2. Satoh™s Algorithm 105
VI.3. Arithmetic Geometric Mean 115
VI.4. Generalized Newton Iteration 121
VI.5. Norm Computation 128
VI.6. Concluding Remarks 132
Chapter VII. Hyperelliptic Curves and the HCDLP
P. Gaudry 133
VII.1. Generalities on Hyperelliptic Curves 133
VII.2. Algorithms for Computing the Group Law 136
VII.3. Classical Algorithms for HCDLP 140
VII.4. Smooth Divisors 142
VII.5. Index-Calculus Algorithm for Hyperelliptic Curves 144
VII.6. Complexity Analysis 146
VII.7. Practical Considerations 149
Chapter VIII. Weil Descent Attacks
F. Hess 151
VIII.1. Introduction “ the Weil Descent Methodology 151
VIII.2. The GHS Attack 153
VIII.3. Extending the GHS Attack Using Isogenies 166
Contents vii
VIII.4. Summary of Practical Implications 173
VIII.5. Further Topics 175
Part 4. Pairing Based Techniques
Chapter IX. Pairings
S. Galbraith 183
IX.1. Bilinear Pairings 183
IX.2. Divisors and Weil Reciprocity 184
IX.3. De¬nition of the Tate Pairing 185
IX.4. Properties of the Tate Pairing 187
IX.5. The Tate Pairing over Finite Fields 189
IX.6. The Weil Pairing 191
IX.7. Non-degeneracy, Self-pairings and Distortion Maps 192
IX.8. Computing the Tate Pairing Using Miller™s Algorithm 196
IX.9. The MOV/Frey“R¨ ck Attack on the ECDLP
u 197
IX.10. Supersingular Elliptic Curves 198
IX.11. Applications and Computational Problems from Pairings 201
IX.12. Parameter Sizes and Implementation Considerations 203
IX.13. Suitable Supersingular Elliptic Curves 204
IX.14. Ef¬cient Computation of the Tate Pairing 205
IX.15. Using Ordinary Curves 208
Appendix: Proof of Weil Reciprocity 212
Chapter X. Cryptography from Pairings
K.G. Paterson 215
X.1. Introduction 215
X.2. Key Distribution Schemes 218
X.3. Identity-Based Encryption 221
X.4. Signature Schemes 228
X.5. Hierarchical Identity-Based Cryptography and Related Topics 235
X.6. More Key Agreement Protocols 240
X.7. Applications and Infrastructures 242
X.8. Concluding Remarks 250
Bibliography 253
Summary of Major LNCS Proceedings 271
Author Index 273
Subject Index 277
Preface

It is now more than ¬ve years since we started working on the book Elliptic
Curves in Cryptography and more than four years since it was published. We
therefore thought it was time to update the book since a lot has happened
in the intervening years. However, it soon became apparent that a simple
update would not be su¬cient since so much has been developed in this area.
We therefore decided to develop a second volume by inviting leading experts
to discuss issues which have arisen.

Highlights in the intervening years which we cover in this volume include:

Provable Security. There has been considerable work in the last few years
on proving various practical encryption and signature schemes secure. In this
new volume we will examine the proofs for the ECDSA signature scheme and
the ECIES encryption scheme.

Side-Channel Analysis. The use of power and timing analysis against
cryptographic tokens, such as smart cards, is particularly relevant to elliptic
curves since elliptic curves are meant to be particularly suited to the con-
strained environment of smart cards. We shall describe what side-channel
analysis is and how one can use properties of elliptic curves to defend against
it.

Point Counting. In 1999 the only method for computing the group order of
an elliptic curve was the Schoof-Elkies-Atkin algorithm. However, for curves
over ¬elds of small characteristic we now have the far more e¬cient Satoh
method, which in characteristic two can be further simpli¬ed into the AGM-
based method of Mestre. We shall describe these improvements in this book.

Weil Descent. Following a talk by Frey in 1999, there has been considerable
work on showing how Weil descent can be used to break certain elliptic curve
systems de¬ned over “composite ¬elds” of characteristic two.

Pairing-Based Cryptography. The use of the Weil and Tate pairings was
until recently con¬ned to breaking elliptic curve protocols. But since the
advent of Joux™s tripartite Di¬e“Hellman protocol there has been an interest
in using pairings on elliptic curves to construct protocols which cannot be
implemented in another way. The most spectacular example of this is the
ix
x PREFACE

identity-based encryption algorithm of Boneh and Franklin. We describe not
only these protocols but how these pairings can be e¬ciently implemented.

As one can see once again, the breadth of subjects we cover will be of
interest to a wide audience, including mathematicians, computer scientists
and engineers. Once again we also do not try to make the entire book relevant
to all audiences at once but trust that, whatever your interests, you can ¬nd
something of relevance within these pages.
The overall style and notation of the ¬rst book is retained, and we have
tried to ensure that our experts have coordinated what they write to ensure
a coherent account across chapters.

Ian Blake
Gadiel Seroussi
Nigel Smart
Abbreviations and Standard Notation

Abbreviations

The following abbreviations of standard phrases are used throughout the
book:


AES Advanced Encryption Standard
AGM Arithmetic Geometric Mean
BDH Bilinear Di¬e“Hellman problem
BSGS Baby Step/Giant Step method
CA Certi¬cation Authority
CCA Chosen Ciphertext Attack
CDH Computational Di¬e“Hellman problem
CM Complex Multiplication
CPA Chosen Plaintext Attack
DBDH Decision Bilinear Di¬e“Hellman problem
DDH Decision Di¬e“Hellman problem
DEM Data Encapsulation Mechanism
DHAES Di¬e“Hellman Augmented Encryption Scheme
DHIES Di¬e“Hellman Integrated Encryption Scheme
DHP Di¬e“Hellman Problem
DLP Discrete Logarithm Problem
DPA Di¬erential Power Analysis
DSA Digital Signature Algorithm
DSS Digital Signature Standard
ECDDH Elliptic Curve Decision Di¬e“Hellman problem
ECDH Elliptic Curve Di¬e“Hellman protocol
ECDHP Elliptic Curve Di¬e“Hellman Problem
ECDLP Elliptic Curve Discrete Logarithm Problem
ECDSA Elliptic Curve Digital Signature Algorithm
ECIES Elliptic Curve Integrated Encryption Scheme
ECMQV Elliptic Curve Menezes“Qu“Vanstone protocol
GHS Gaudry“Hess“Smart attack
GRH Generalized Riemann Hypothesis
HCDLP Hyperelliptic Curve Discrete Logarithm Problem
HIBE Hierarchical Identity-Based Encryption
xi
xii ABBREVIATIONS AND STANDARD NOTATION

IBE Identity-Based Encryption
IBSE Identity-Based Sign and Encryption
ILA Information Leakage Analysis
KDF Key Derivation Function
KDS Key Distribution System
KEM Key Encapsulation Mechanism
MAC Message Authentication Code
MOV Menezes“Okamoto“Vanstone attack
NIKDS Non-Interactive Key Distribution System
PKI Public Key Infrastructure
RSA Rivest“Shamir“Adleman encryption scheme
SCA Side Channel Analysis
SEA Schoof“Elkies“Atkin algorithm
SHA Secure Hash Algorithm
SPA Simple Power Analysis
SSCA Simple Side-Channel Attack
TA Trusted Authority
ABBREVIATIONS AND STANDARD NOTATION xiii

Standard notation

The following standard notation is used throughout the book, often with-
out further de¬nition. Other notation is de¬ned locally near its ¬rst use.

Basic Notation
Z, Q, R, C integers, rationals, reals and complex numbers
Z>k integers greater than k; similarly for ≥, <, ¤
Z/nZ integers modulo n
#S cardinality of the set S
gcd(f, g), lcm(f, g) GCD, LCM of f and g
deg(f ) degree of a polynomial f
φEul Euler totient function
·
Legendre symbol
p
logb x logarithm to base b of x; natural log if b omitted
function g(n) such that |g(n)| ¤ c|f (n)| for some
O(f (n))
constant c > 0 and all su¬ciently large n
o(f (n)) function g(n) such that limn’∞ (g(n)/f (n)) = 0
Pn projective space

Group/Field Theoretic Notation
Fq ¬nite ¬eld with q elements
— +
K , K , K for a ¬eld K, the multiplicative group, additive group
and algebraic closure, respectively
char(K) characteristic of K
g cyclic group generated by g
ord(g) order of an element g in a group
Aut(G) automorphism group of G
Zp , Qp p-adic integers and numbers, respectively
trace of x ∈ Fq over Fp , q = pn
Trq|p (x)
µn nth roots of unity
NL/K norm map

Function Field Notation
deg(D) degree of a divisor
(f ) divisor of a function
f (D) function evaluated at a divisor
∼ equivalence of divisors
ordP (f ) multiplicity of a function at a point

Galois Theory Notation
Gal(K/F ) Galois group of K over F
σ(P ) Galois conjugation of point P by σ
σ
f Galois conjugation of coe¬cients of function f by σ
xiv ABBREVIATIONS AND STANDARD NOTATION

Curve Theoretic Notation
E elliptic curve (equation)
(xP , yP ) coordinates of the point P
x(P ) the x-cordinate of the point P
y(P ) the y-cordinate of the point P
E(K) group of K-rational points on E
[m]P multiplication-by-m map applied to the point P
E[m] group of m-torsion points on the elliptic curve E
End(E) endormorphism ring of E
O point at in¬nity (on an elliptic curve)
„˜ Weierstraß ˜pay™ function
• Frobenius map
P, Q n Tate pairing of P and Q
en (P, Q) Weil pairing of P and Q
e(P, Q) pairing of P and Q
e(P, Q) modi¬ed pairing of P and Q
ˆ
Tr(P ) trace map
T trace zero subgroup
Authors

We would like to acknowledge the following people who contributed chap-
ters to this book.

Dan Brown, Alex Dent,
Certicom Corp., Mathematics Department,
Mississauga, Royal Holloway,
Canada. University of London,
United Kingdom.

Steven Galbraith, Pierrick Gaudry,
Mathematics Department, Laboratoire d™Informatique (LIX),
´
Royal Holloway, Ecole Polytechnique ,
University of London, France.
United Kingdom.

Florian Hess, Marc Joye,
Institut f¨r Mathematik,
u Card Security Group,
T.U. Berlin, Gemplus,
Germany. France.

Elisabeth Oswald, Kenneth G. Paterson,
Institute for Applied Information Info. Sec. Group,
Processing and Communications, Royal Holloway,
Graz University of Technology, University of London,
Austria. United Kingdom.

Nigel Smart, Frederik Vercauteren,
Deptartment of Computer Sci- Department of Computer Science,
ence, University of Bristol,
University of Bristol, United Kingdom.
United Kingdom.


The editors would like to thank Marc Joye for various bits of LaTeX help
and Georgina Cranshaw and Ian Holyer for organizing our system for ex-
changing various ¬les and keeping things up to date. As always, Roger Astley
xv
xvi AUTHORS

of Cambridge University Press was very helpful throughout the whole process.

The authors of each chapter would like to thank the following for helping
in checking and in the creation of their respective chapters:
• Nigel Smart: Alex Dent and Dan Brown.
• Dan Brown: Nigel Smart, Alex Dent, Kenneth Patterson and Ian
Blake.
• Alex Dent: Bill and Jean Dent, Steven Galbraith, Becky George,
Louis Granboulan, Victor Shoup, Andrew Spicer and Christine Swart
(twice).
• Steven Galbraith: Paulo Barreto, Dan Boneh, Young-Ju Choie,
Keith Harrison, Florian Hess, Neal Koblitz, Wenbo Mao, Kim Nguyen,
Kenny Paterson, Maura Paterson, Hans-Georg R¨ck, Adam Saunders,
u
Alice Silverberg, Lawrence Washington, Annegret Weng, Bill Williams
and The Nu¬eld Foundation (Grant NUF-NAL 02).
• Elisabeth Oswald: The power traces presented in this chapter were
made with the FPGA measurement-setup which was built by S±dd±ka
¨
Berna Ors and has been presented in [268].
• Marc Joye: Benoˆ Chevallier-Mames and Tanja Lange.
±t
• Kenneth G. Paterson: Sattam Al-Riyami, Alex Dent, Steven Gal-
braith, Caroline Kudla and The Nu¬eld Foundation (Grant NUF-NAL
02).
Part 1

Protocols
CHAPTER I

Elliptic Curve Based Protocols

N.P. Smart

I.1. Introduction
In this chapter we consider the various cryptographic protocols in which
elliptic curves are primarily used. We present these in greater detail than in
the book [ECC] and focus on their cryptographic properties. We shall only
focus on three areas: signatures, encryption and key agreement. For each of
these areas we present the most important protocols, as de¬ned by various
standard bodies.
The standardization of cryptographic protocols, and elliptic curve proto-
cols in particular, has come a long way in the last few years. Standardization
is important if one wishes to deploy systems on a large scale, since di¬er-
ent users may have di¬erent hardware/software combinations. Working to a
well-de¬ned standard for any technology aids interoperability and so should
aid the takeup of the technology.
In the context of elliptic curve cryptography, standards are de¬ned so
that one knows not only the precise workings of each algorithm, but also the
the format of the transmitted data. For example, a standard answers such
questions as
• In what format are ¬nite ¬eld elements and elliptic curve points to be
transmitted?
• How are public keys to be formatted before being signed in a certi¬cate?
• How are conversions going to be performed between arbitrary bit strings
to elements of ¬nite ¬elds, or from ¬nite ¬eld elements to integers, and
vice versa?
• How are options such as the use of point compression, (see [ECC,
Chapter VI]) or the choice of curve to be signalled to the user?
A number of standardization e¬orts have taken place, and many of these re-
duce the choices available to an implementor by recommending or mandating
certain parameters, such as speci¬c curves and/or speci¬c ¬nite ¬elds. This
not only helps aid interoperability, it also means that there are well-de¬ned
sets of parameter choices that experts agree provide a given security level. In
addition, by recommending curves it means that not every one who wishes
to deploy elliptic curve based solutions needs to implement a point counting
method like those in Chapter VI or [ECC, Chapter VII]. Indeed, since many
3
4 I. ECC PROTOCOLS

curves occur in more than one standard, if one selects a curve from the in-
tersection then, your system will more likely interoperate with people who
follow a di¬erent standard from you.
Of particular relevance to elliptic curve cryptography are the following
standards:
• IEEE 1363: This standard contains virtually all public-key algo-
rithms. In particular, it covers ECDH, ECDSA, ECMQV and ECIES,
all of which we discuss in this chapter. In addition, this standard con-
tains a nice appendix covering all the basic number-theoretic algorithms
required for public-key cryptography.
• ANSI X9.62 and X9.63: These two standards focus on elliptic curves
and deal with ECDSA in X9.62 and ECDH, ECMQV and ECIES in
X9.63. They specify both the message formats to be used and give a
list of recommended curves.
• FIPS 186.2: This NIST standard for digital signatures is an update
of the earlier FIPS 186 [FIPS 186], which details the DSA algorithm
only. FIPS 186.2 speci¬es both DSA and ECDSA and gives a list of
recommended curves, which are mandated for use in U.S. government
installations.
• SECG: The SECG standard was written by an industrial group led
by Certicom. It essentially mirrors the contents of the ANSI standards
but is more readily available on the Web, from the site
http://www.secg.org/
• ISO: There are two relevant ISO standards: ISO 15946-2, which covers
ECDSA and a draft ISO standard covering a variant of ECIES called
ECIES-KEM; see [305].

I.2. ECDSA
ECDSA is the elliptic curve variant of the Digital Signature Algorithm
(DSA) or, as it is sometimes called, the Digital Signature Standard (DSS).
Before presenting ECDSA it may be illustrative to describe the original DSA
so one can see that it is just a simple generalization.

In DSA one ¬rst chooses a hash function H that outputs a bit-string of
length m bits. Then one de¬nes a prime q, of over m bits, and a prime p of
n bits such that
• q divides p ’ 1.
• The discrete logarithm problem in the subgroup of Fp of order q is
infeasible.
With current techniques and computing technology, this second point means
that n should be at least 1024. Whilst to avoid birthday attacks on the hash
function one chooses a value of m greater than 160.
I.2. ECDSA 5

One then needs to ¬nd a generator g for the subgroup of order q in F— .
p
This is done by generating random elements h ∈ F— and computing
p

g = h(p’1)/q (mod p)
until one obtains a value of g that is not equal to 1. Actually, there is only a
1/q chance of this not working with the ¬rst h one chooses; hence ¬nding a
generator g is very simple.
Typically with DSA one uses SHA-1 [FIPS 180.1] as the hash function,
although with the advent of SHA-256, SHA-384 and SHA-512 [FIPS 180.2]
one now has a larger choice for larger values of m.
The quadruple (H, p, q, g) is called a set of domain parameters for the
system, since they are often shared across a large number of users, e.g. a user
domain. Essentially the domain parameters de¬ne a hash function, a group
of order q, and a generator of this group.
The DSA makes use of the function
F— ’’ Fq
p
f:
x ’’ x (mod q),
where one interprets x ∈ F— as an integer when performing the reduction
p
modulo q. This function is used to map group elements to integers modulo q
and is often called the conversion function.
As a public/private-key pair in the DSA system one uses (y, x) where
y = g x (mod p).
The DSA signature algorithm then proceeds as follows:


Algorithm I.1: DSA Signing

INPUT: A message m and private key x.
OUTPUT: A signature (r, s) on the message m.
Choose k ∈R {1, . . . , q ’ 1}.
1.
t ← g k (mod p).
2.
r ← f (t).
3.
If r = 0 then goto Step 1.
4.
e ← H(m)
5.
s ← (e + xr)/k (mod q)
6.
If s = 0 then goto Step 1.
7.
Return (r, s).
8.

The veri¬cation algorithm is then given by
6 I. ECC PROTOCOLS



Algorithm I.2: DSA Veri¬cation
INPUT: A message m, a public key y and a signature (r, s).
OUTPUT: Reject or Accept.
1. Reject if r, s ∈ {1, . . . , q ’ 1}.
2. e ← H(m).
3. u1 ← e/s (mod q), u2 ← r/s (mod q).
4. t ← g u1 y u2 (mod p).
5. Accept if and only if r = f (t).


For ECDSA, the domain parameters are given by (H, K, E, q, G), where
H is a hash function, E is an elliptic curve over the ¬nite ¬eld K, and G
is a point on the curve of prime order q. Hence, the domain parameters
again de¬ne a hash function, a group of order q, and a generator of this
group. We shall always denote elliptic curve points by capital letters to aid
understanding. With the domain parameters one also often stores the integer
h, called the cofactor, such that
#E(K) = h · q.
This is because the value h will be important in other protocols and oper-
ations, which we shall discuss later. Usually one selects a curve such that
h ¤ 4.
The public/private-key pair is given by (Y, x), where
Y = [x]G,
and the role of the function f is taken by
E ’’ Fq
f:
P ’’ x(P ) (mod q),
where x(P ) denotes the x-coordinate of the point P and we interpret this as
an integer when performing the reduction modulo q. This interpretation is
made even when the curve is de¬ned over a ¬eld of characteristic two. In the
case of even characteristic ¬elds, one needs a convention as to how to convert
an element in such a ¬eld, which is usually a binary polynomial g(x), into an
integer. Almost all standards adopt the convention that one simply evaluates
g(2) over the integers. Hence, the polynomial
x 5 + x2 + 1
is interpreted as the integer 37, since
37 = 32 + 4 + 1 = 25 + 22 + 1.
The ECDSA algorithm then follows immediately from the DSA algorithm
as:
I.2. ECDSA 7



Algorithm I.3: ECDSA Signing

INPUT: A message m and private key x.
OUTPUT: A signature (r, s) on the message m.
1. Choose k ∈R {1, . . . , q ’ 1}.
2. T ← [k]G.
3. r ← f (T ).
4. If r = 0 then goto Step 1.
5. e ← H(m)
6. s ← (e + xr)/k (mod q).
7. If s = 0 then goto Step 1.
8. Return (r, s).

The veri¬cation algorithm is then given by

Algorithm I.4: ECDSA Veri¬cation

INPUT: A message m, a public key Y and a signature (r, s).
OUTPUT: Reject or Accept.
1. Reject if r, s ∈ {1, . . . , q ’ 1}.
2. e ← H(m).
3. u1 ← e/s (mod q), u2 ← r/s (mod q).
4. T ← [u1 ]G + [u2 ]Y .
5. Accept if and only if r = f (T ).

One can show that ECDSA is provably secure, assuming that the elliptic
curve group is modelled in a generic manner and H is a “good” hash function;
see Chapter II for details.
An important aspect of both DSA and ECDSA is that the ephemeral
secret k needs to be truly random. As a simple example of why this is so,
consider the case where someone signs two di¬erent messages, m and m , with
the same value of k. The signatures are then (r, s) and (r , s ), where
r = r = f ([k]G);
s = (e + xr)/k (mod q), where e = H(m);
s = (e + xr)/k (mod q), where e = H(m ).
We then have that
(e + xr)/s = k = (e + xr)/s (mod q).
In which case we can deduce
xr(s ’ s) = se ’ s e,
8 I. ECC PROTOCOLS

and hence
se ’ s e
x= (mod q).
r(s ’ s)
So from now on we shall assume that each value of k is chosen at random.
In addition, due to a heuristic lattice attack of Howgrave-Graham and
Smart [174], if a certain subset of the bits in k can be obtained by the
attacker, then, over a number of signed messages, one can recover the long
term secret x. This leakage of bits, often called partial key exposure, could
occur for a number of reasons in practical systems, for example, by using
a poor random number generator or by side-channel analysis (see Chapter
IV for further details on side-channel analysis). The methods of Howgrave-
Graham and Smart have been analysed further and extended by Nguyen and
Shparlinski (see [261] and [262]). Another result along these lines is the
attack of Bleichenbacher [31], who shows how a small bias in the random
number generator, used to produce k, can lead to the recovery of the long-
term secret x.

I.3. ECDH/ECMQV
Perhaps the easiest elliptic curve protocol to understand is the elliptic
curve variant of the Di¬e“Hellman protocol, ECDH. In this protocol two
parties, usually called Alice and Bob, wish to agree on a shared secret over
an insecure channel. They ¬rst need to agree on a set of domain parame-
ters (K, E, q, h, G) as in our discussion on ECDSA. The protocol proceeds as
follows:
Alice Bob
[a]G
’’ [a]G
a
[b]G
←’
[b]G b
Alice can now compute
KA = [a]([b]G) = [ab]G
and Bob can now compute
KB = [b]([a]G) = [ab]G.
Hence KA = KB and both parties have agreed on the same secret key. The
messages transferred are often referred to as ephemeral public keys, since they
are of the form of discrete logarithm based public keys, but they exist for only
a short period of time.
Given [a]G and [b]G, the problem of recovering [ab]G is called the Elliptic
Curve Di¬e“Hellman Problem, ECDHP. Clearly, if we can solve ECDLP
then we can solve ECDHP; it is unknown if the other implication holds. A
proof of equivalence of the DHP and DLP for many black box groups follows
from the work of Boneh, Maurer and Wolf. This proof uses elliptic curves in
a crucial way; see [ECC, Chapter IX] for more details.
I.3. ECDH/ECMQV 9

The ECDH protocol has particularly small bandwidth if point compression
is used and is very e¬cient compared to the standard, ¬nite ¬eld based, Di¬e“
Hellman protocol.
The Di¬e“Hellman protocol is a two-pass protocol, since there are two
message ¬‚ows in the protocol. The fact that both Alice and Bob need to be
“online” to execute the protocol can be a problem in some situations. Hence,
a one-pass variant exists in which only Alice sends a message to Bob. Bob™s
ephemeral public key [b]G now becomes a long-term static public key, and
the protocol is simply a mechanism for Alice to transport a new session key
over to Bob.
Problems can occur when one party does not send an element in the
subgroup of order q. This can either happen by mistake or by design. To
avoid this problem a variant called cofactor Di¬e“Hellman is sometimes used.
In cofactor Di¬e“Hellman the shared secret is multiplied by the cofactor h
before use, i.e., Alice and Bob compute
KA = [h]([a]([b]G)) and KB = [h]([b]([a]G)).


The simplicity of the Di¬e“Hellman protocol can however be a disguise,
since in practice life is not so simple. For example, ECDH su¬ers from the
man-in-the-middle attack:
Alice Eve Bob
[a]G
’’ [a]G
a
[x]G
←’
[x]G x
[y]G
’’ [y]G
y
[b]G
[b]G ←’ b
In this attack, Alice agrees a key KA = [a]([x]G) with Eve, thinking it is
agreed with Bob, and Bob agrees a key KB = [b]([y]G) with Eve, thinking
it is agreed with Alice. Eve can now examine communications as they pass
through her by essentially acting as a router.
The problem is that when performing ECDH we obtain no data-origin
authentication. In other words, Alice does not know who the ephemeral public
key she receives is from. One way to obtain data-origin authentication is to
sign the messages in the Di¬e“Hellman key exchange. Hence, for example,
Alice must send to Bob the value
([a]G, (r, s)),
where (r, s) is her ECDSA signature on the message [a]G.
One should compare this model of authenticated key exchange with the
traditional form of RSA-based key transport, as used in SSL. In RSA-based
key transport, the RSA public key is used to encrypt a session key from one
10 I. ECC PROTOCOLS

user to the other. The use of a signed Di¬e“Hellman key exchange has a
number of advantages over an RSA-based key transport:
• In key transport only one party generates the session key, while in
key agreement both can parties contribute randomness to the resulting
session key.
• Signed ECDH has the property of forward secrecy, whereas an RSA-
based key transport does not. An authenticated key agreement/transport
protocol is called forward secure if the compromise of the long-term
static key does not result in past session keys being compromized. RSA
key transport is not forward secure since once you have the long-term
RSA decryption key of the recipient you can determine the past ses-
sion keys; however, in signed ECDH the long-term private keys are only
used to produce signatures.
However, note that the one-pass variant of ECDH discussed above, being a
key transport mechanism, also su¬ers from the above two problems of RSA
key transport.

The problem with signed ECDH is that it is wasteful of bandwidth. To
determine the session key we need to append a signature to the message ¬‚ows.
An alternative system is to return to the message ¬‚ows in the original ECDH
protocol but change the way that the session key is derived. If the session
key is derived using static public keys, as well as the transmitted ephemeral
keys, we can obtain implicit authentication of the resulting session key. This
is the approach taken in the MQV protocol of Law, Menezes, Qu, Solinas and
Vanstone [216].
In the MQV protocol both parties are assumed to have long-term static
public/private key pairs. For example, we shall assume that Alice has the
static key pair ([a]G, a) and Bob has the static key pair ([c]G, c). To agree
on a shared secret, Alice and Bob generate two ephemeral key pairs; for
example, Alice generates the ephemeral key pair ([b]G, b) and Bob generates
the ephemeral key pair ([d]G, d). They exchange the public parts of these
ephemeral keys as in the standard ECDH protocol:
Alice Bob
[b]G
’’ [b]G
b
[d]G
←’
[d]G d.
Hence, the message ¬‚ows are precisely the same as in the ECDH protocol.
After the exchange of messages Alice knows
a, b, [a]G, [b]G, [c]G and [d]G,
and Bob knows
c, d, [c]G, [d]G, [a]G and [b]G.
The shared secret is then determined by Alice via the following algorithm:
I.3. ECDH/ECMQV 11



Algorithm I.5: ECMQV Key Derivation

A set of domain parameters (K, E, q, h, G)
INPUT:
and a, b, [a]G, [b]G, [c]G and [d]G.
OUTPUT: A shared secret G,
shared with the entity with public key [c]G.
1. n ← log2 (#K) /2.
2. u ← (x([b]G) (mod 2n )) + 2n .
3. s ← b + ua (mod q).
4. v ← (x([d]G) (mod 2n )) + 2n .
5. Q ← [s]([d]G + [v]([c]G)).
6. If Q is at infinity goto Step 1.
7. Output Q.

Bob can also compute the same value of Q by swapping the occurance
of (a, b, c, d) in the above algorithm with (c, d, a, b). If we let uA , vA and sA
denote the values of u, v and s computed by Alice and uB , vB and sB denote
the corresponding values computed by Bob, then we see
uA = vB ,
vA = uB .
We then see that
Q= [sA ] ([d]G + [vA ]([c]G))
= [sA ][d + vA c]G
= [sA ][d + uB c]G
= [sA ][sB ]G.
In addition, a cofactor variant can be used by setting Q ← [h]Q before the
test for whether Q is the point at in¬nity in Step 6.
In summary, the ECMQV protocol allows authentic key agreement to
occur over an insecure channel, whilst only requiring the same bandwidth as
an unauthenticated Di¬e“Hellman.

One can also have a one-pass variant of the ECMQV protocol, which
enables one party to be o¬„ine when the key is agreed. Suppose Bob is the
party who is o¬„ine; he will still have a long-term static public/private key
pair given by [c]G. Alice then uses this public key both as the long-term key
and the emphemeral key in the above protocol. Hence, Alice determines the
shared secret via
Q = [sA ] (([c]G) + [vA ]([c]G)) = [sA ][vA + 1]([c]G),
12 I. ECC PROTOCOLS

where, as before, sA = b + uA a, with a the long-term private key and b the
ephemeral private key. Bob then determines the shared secret via
Q = [sB ] (([b]G) + vB ([a]G)) ,
where sB is now ¬xed and equal to (1 + uB )c.

It is often the case that a key agreement protocol also requires key con-
¬rmation. This means that both communicating parties know that the other
party has managed to compute the shared secret. For ECMQV this is added
by slightly modifying the protocol. Each party, on computing the shared
secret point Q, then computes
(k, k ) ← H(Q),
where H is a hash function (or key derivation function). The key k is used as
the shared session key, whilst k is used as a key to a Message Authentication
Code, MAC, to enable key con¬rmation.
This entire procedure is accomplished in three passes as follows:
Alice Bob
[b]G
’’
b [b]G
[d]G,M
←’
[d]G d
M
’’
where
M = M ACk (2, Bob, Alice, [d]G, [b]G),
M = M ACk (3, Alice, Bob, [b]G, [d]G).
Of course Alice needs to verify that M is correct upon recieving it, and Bob
needs to do likewise for M .

I.4. ECIES
The elliptic curve integrated encryption system (ECIES) is the standard
elliptic curve based encryption algorithm. It is called integrated, since it is
a hybrid scheme that uses a public-key system to transport a session key
for use by a symmetric cipher. It is based on the DHAES/DHIES protocol
of Abdalla, Bellare and Rogaway [1]. Originally called DHAES, for Di¬e“
Hellman Augmented Encryption Scheme, the name was changed to DHIES,
for Di¬e“Hellman Integrated Encryption Scheme, so as to avoid confusion
with the AES, Advanced Encryption Standard.
ECIES is a public-key encryption algorithm. Like ECDSA, there is as-
sumed to be a set of domain parameters (K, E, q, h, G), but to these we also
add a choice of symmetric encryption/decryption functions, which we shall
denote Ek (m) and Dk (c). The use of a symmetric encryption function makes
I.4. ECIES 13

it easy to encrypt long messages. In addition, instead of a simple hash func-
tion, we require two special types of hash functions:
• A message authentication code M ACk (c),
M AC : {0, 1}n — {0, 1}— ’’ {0, 1}m .
This acts precisely like a standard hash function except that it has a
secret key passed to it as well as a message to be hashed.
• A key derivation function KD(T, l),
KD : E — N ’’ {0, 1}— .
A key derivation function acts precisely like a hash function except
that the output length (the second parameter) could be quite large.
The output is used as a key to encrypt a message; hence, if the key is
to be used in a xor-based encryption algorithm the output needs to be
as long as the message being encrypted.
The ECIES scheme works like a one-pass Di¬e“Hellman key transport,
where one of the parties is using a ¬xed long-term key rather than an ephemeral
one. This is followed by symmetric encryption of the actual message. In the
following we assume that the combined length of the required MAC key and
the required key for the symmetric encryption function is given by l.
The recipient is assumed to have a long-term public/private-key pair
(Y, x), where
Y = [x]G.
The encryption algorithm proceeds as follows:

Algorithm I.6: ECIES Encryption

INPUT: Message m and public key Y .
OUTPUT: The ciphertext (U, c, r).
1. Choose k ∈R {1, . . . , q ’ 1}.
2. U ← [k]G.
3. T ← [k]Y .
4. (k1 k2 ) ← KD(T, l).
5. Encrypt the message, c ← Ek1 (m).
6. Compute the MAC on the ciphertext, r ← M ACk2 (c).
7. Output (U, c, r).

Each element of the ciphertext (U, c, r) is important:
• U is needed to agree the ephemeral Di¬e“Hellman key T .
• c is the actual encryption of the message.
• r is used to avoid adaptive chosen ciphertext attacks.
14 I. ECC PROTOCOLS

Notice that the data item U can be compressed to reduce bandwidth, since
it is an elliptic curve point.
Decryption proceeds as follows:

Algorithm I.7: ECIES Decryption

INPUT: Ciphertext (U, c, r) and a private key x.
OUTPUT: The message m or an ˜˜Invalid Ciphertext™™ message.
1. T ← [x]U .
2. (k1 k2 ) ← KD(T, l).
3. Decrypt the message m ← Dk1 (c).
4. If r = M ACk2 (c) then output ˜˜Invalid Ciphertext™™.
5. Output m.

Notice that the T computed in the decryption algorithm is the same as
the T computed in the encryption algorithm since
Tdecryption = [x]U = [x]([k]G) = [k]([x]G) = [k]Y = Tencryption .
One can show that, assuming various properties of the block cipher, key
derivation function and keyed hash function, the ECIES scheme is secure
against adaptive chosen ciphertext attack, assuming a variant of the Di¬e“
Hellman problem in the elliptic curve group is hard; see [1] and Chapter
III.
In many standards, the function KD is applied to the x-coordinate of
the point T and not the point T itself. This is more e¬cient in some cases
but leads to the scheme su¬ering from a problem called benign malleability.
Benign malleability means that an adversary is able, given a ciphertext C,
to produce a di¬erent valid ciphertext C of the same message. For ECIES,
if C = (U, c, r), then C = (’U, c, r) since if KD is only applied to the x-
coordinate of U , so both C and C are di¬erent valid ciphertexts corresponding
to the same message.
The problem with benign malleability is that it means the scheme cannot
be made secure under the formal de¬nition of an adaptive chosen ciphertext
attack. However, the issue is not that severe and can be solved, theoretically,
by using a di¬erent but equally sensible de¬nition of security. No one knows
how to use the property of benign malleability in a “real-world” attack, and
so whether one chooses a standard where KD is applied to T or just x(T ) is
really a matter of choice.
In addition, to avoid problems with small subgroups, just as in the ECDH
and ECMQV protocols, one can select to apply KD to either T or [h]T . The
use of [h]T means that the key derivation function is applied to an element
in the group of order q, and hence if T is a point in the small subgroup one
would obtain [h]T = O.
I.4. ECIES 15

The fact that ECIES su¬ers from benign malleability, and the fact that
the cofactor variant can lead to interoperability problems, has led to a new
approach being taken to ECIES in the draft ISO standard [305].
The more modern approach is to divide a public-key encryption algorithm
into a key transport mechanism, called a Key Encapsulation Mechanism,
or KEM, and a Data Encapsulation Mechanism, or DEM. This combined
KEM/DEM approach has proved to be very popular in recent work because
it divides the public key algorithm into two well-de¬ned stages, which aids in
the security analysis.
We ¬rst examine a generic DEM, which requires a MAC function M ACk
of key length n bits and a symmetric cipher Ek of key length m bits. The
Data Encapsulation Mechanism then works as follows:

Algorithm I.8: DEM Encryption

INPUT: A key K of length n + m bits and a message M .
OUTPUT: A ciphertext C
1. Parse K as k1 k2 ,
where k1 has m bits and k2 has n bits.
2. c ← Ek1 (M ).
3. r ← M ACk2 (c).
4. C ← (c r).

Decryption then proceeds as follows:

Algorithm I.9: DEM Decryption

INPUT: A key K of length n + m bits and a ciphertext C.
OUTPUT: A message M or ˜˜Invalid Ciphertext™™.
1. Parse K as k1 k2 ,
where k1 has m bits and k2 has n bits.
2. Parse C as c r,
this could result in an ˜˜Invalid Ciphertext™™ warning.
3. Decrypt the message M ← Dk1 (c).
4. If r = M ACk2 (c) then output ˜˜Invalid Ciphertext™™.
5. Output M .

To use a DEM we require a KEM, and we shall focus on one based on
ECIES called ECIES-KEM. A KEM encryption function takes as input a pub-
lic key and outputs a session key and the encryption of the session key under
the given public key. The KEM decryption operation takes as input a pri-
vate key and the output from a KEM encryption and produces the associated
session key.
16 I. ECC PROTOCOLS

As mentioned before, the de¬nition of ECIES-KEM in the draft ISO stan-
dard is slightly di¬erent from earlier versions of ECIES. In particular, the
way the ephemeral secret is processed to deal with small subgroup attacks
and how chosen ciphertext attacks are avoided is changed in the following
scheme. The processing with the cofactor is now performed solely in the de-
cryption phase, as we shall describe later. First we present the encryption
phase for ECIES-KEM.
Again, the recipient is assumed to have a long-term public/private-key
pair (Y, x), where
Y = [x]G.
The encryption algorithm proceeds as follows:

Algorithm I.10: ECIES-KEM Encryption

INPUT: A public key Y and a length l.
OUTPUT: A session key K of length l and
an encryption E of K under Y .
Choose k ∈R {1, . . . , q ’ 1}.
1.
E ← [k]G.
2.
T ← [k]Y .
3.
K ← KD(E T, l),
4.
Output (E, K).
5.

Notice how the key derivation function is applied to both the ephemeral
public key and the point representing the session key. It is this modi¬cation
that removes problems associated with benign malleability in chosen cipher-
text attacks and aids in the security proof. In addition, no modi¬cation to
the KEM is made when one wishes to deal with cofactors; this modi¬cation
is only made at decryption time.
To deal with cofactors, suppose we have a set of domain parameters
(K, E, q, h, G). We set a ¬‚ag f as follows:
• If h = 1, then f ← 0.
• If h = 1, then select f ← 1 or f ← 2.
We can now describe the ECIES-KEM decryption operation.

Algorithm I.11: ECIES-KEM Decryption

An encryption session key E, a private key x,
INPUT:
a length l and a choice for the flag f as above.
OUTPUT: A session key K of length l
I.4. ECIES 17

If f = 2 then check whether E has order q,
1.
if not return ˜˜Invalid Ciphertext™™.
x ← x and E ← E.
2.
If f = 1 then
3.
x ← x /h (mod q).
4.
E ← [h]E .
5.
T ← [x ]E .
6.
If T = 0 then return ˜˜Invalid Ciphertext™™.
7.
K ← KD(E T, l),
8.
Output K.
9.


We now explain how an encryption is performed with a KEM/DEM ap-
proach, where we are really focusing on using ECIES-KEM. We assume a
KEM and DEM that are compatible, i.e., a pair whose KEM outputs an l-bit
key and whose DEM requires an l-bit key as input.


Algorithm I.12: ECIES-KEM-DEM Encryption

INPUT: A public key Y , a message M .
OUTPUT: A ciphertext C.
(E, K) ← ECIES ’ KEMEnc (Y, l).
1.
(c r) ← DEMEnc (K, M ).
2.
Output (E c r).
3.




Algorithm I.13: ECIES-KEM/DEM Decryption


INPUT: A ciphertext C, a private key x.
OUTPUT: A message m or ˜˜Invalid Ciphertext™™.
Parse C as (E c r).
1.
K ← ECIES ’ KEMDec (E, x, l).
2.
If K equals ˜˜Invalid Ciphertext™™ then
3.
4. Return ˜˜Invalid Ciphertext™™.
M ← DEMDec (K, (c r)).
5.
If M equals ˜˜Invalid Ciphertext™™ then
6.
7. Return ˜˜Invalid Ciphertext™™.
Output M .
8.
18 I. ECC PROTOCOLS

I.5. Other Considerations
When receiving a public key, whether in a digital certi¬cate or as an
ephemeral key in ECDH, ECMQV or ECIES, one needs to be certain that
the ephemeral key is a genuine point of the correct order on the given curve.
This is often overlooked in many academic treatments of the subject.
The ANSI and SECG standards specify the following check, which should
be performed for each received public key.

Algorithm I.14: Public-Key Validation

A set of domain parameters (K, E, q, h, G)
INPUT:
and a public key Q
OUTPUT: Valid or Invalid
1. If Q ∈ E(K) then output ˜˜Invalid™™.
2. If Q = O then output ˜˜Invalid™™.
3. (Optional) If [q]Q = O then output ˜˜Invalid™™.
4. Output ˜˜Valid™™.

The last check is optional, because it can be quite expensive, especially if
h = 1 in the case of large prime characteristic or h = 2 in the case of even
characteristic. However, the check is needed to avoid problems with small
subgroups. It is because this check can be hard to implement that the option
of using cofactors in the key derivation functions is used in ECDH, ECMQV
and ECIES.

Just as public keys need to be validated, there is also the problem of
checking whether a given curve is suitable for use. The following checks
should be performed before a set of domain parameters is accepted; however,
this is likely to be carried out only once for each organization deploying elliptic
curve based solutions.

Algorithm I.15: Elliptic Curve Validation

INPUT: A set of domain parameters (K, E, q, h, G)
OUTPUT: Valid or Invalid
1. Let l ← #K = pn .
2. Check #E(K) = h · q, by generating random points
and verifying that they have order h, , q , or h · q.
3. Check that q is prime.
4. Check that q > 2160 to avoid the BSGS/Rho attacks,
see [ECC, Chapter V] for details.
5. Check that q = p to avoid the anomalous attack,
again see [ECC, Chapter V] for reasons.
6. Check that lt = 1 (mod q) for all t ¤ 20 to avoid the
I.5. OTHER CONSIDERATIONS 19

MOV/Frey--R¨ck attack, see [ECC, Chapter V].
u
Check that n is prime, to avoid attacks based on
7.
Weil descent, see Chapter VIII of this volume.
Check that G lies on the curve and has order q.
8.

But how do you know the curve has no special weakness known only to a
small (clever) subset of people? Since we believe that such a weak curve must
come from a very special small subset of all the possible curves, we generate
the curve at random. But even if you generate your curve at random, you
need to convince someone else that this is the case. This is done by generating
the curve in a veri¬ably random way, which we shall now explain in the case of
characteristic two curves. For other characteristics a similar method applies.


Algorithm I.16: Veri¬able Random Generation of Curves
INPUT: A field K = F2n of characteristic two
OUTPUT: A set of domain parameters (K, E, q, h, G) and a seed S
1. Choose a random seed S.
2. Chain SHA-1 with input S to produce a bit string B of
length n.
3. Let b be the element of K with bit representation B.
4. Set E : Y 2 + X · Y = X 3 + X 2 + b.
5. Apply the methods of Chapter VI of this volume
or [ECC, Chapter VII] to compute the group order
N ← #E(K).
6. If N = 2q with q prime then goto the Step 1.
7. Generate an element G ∈ E(K) of order q.
8. Check that (E, K, q, 2, G) passes Algorithm I.15,
if not then goto Step 1.
9. Output (K, E, q, 2, G) and S.

With the value of S, any other person can verify that the given elliptic
curve is determined by S. Now if the generator knew of a subset of curves
with a given weakness, to generate the appropriate S for a member of such
a subset, they would need to be able to invert SHA-1, which is considered
impossible.
CHAPTER II

On the Provable Security of ECDSA

D. Brown


II.1. Introduction
II.1.1. Background. The Elliptic Curve Digital Signature Algorithm is
now in many standards or recommendations, such as [ANSI X9.62], [SECG],
[FIPS 186.2], [IEEE 1363], [ISO 15946-2], [NESSIE] and [RFC 3278].
Organizations chose ECDSA because they regarded its reputational security
su¬cient, on the grounds that (a) it is a very natural elliptic curve analogue of
DSA, and that (b) both elliptic curve cryptography and DSA were deemed to
have su¬ciently high reputational security. The standardization of ECDSA
has created more intense public scrutiny. Despite this, no substantial weak-
nesses in ECDSA have been found, and thus its reputational security has
increased.
At one point, proofs of security, under certain assumptions, were found for
digital signature schemes similar to DSA and ECDSA. The proof techniques
in these initial proofs did not, and still do not, appear applicable to DSA and
ECDSA. Thus, for a time, provable security experts suggested a change to the
standardization of reputationally secure schemes, because slight modi¬cations
could improve provable security.
Further investigation, however, led to new provable security results for
ECDSA. New proof techniques and assumptions were found that overcame
or avoided the di¬culty in applying the initial techniques to ECDSA. This
chapter describes some of these results, sketches their proofs, and discusses
the impact and interpretation of these results.
Interestingly, in some cases, the new proof techniques did not apply to
DSA, which was the ¬rst, though mild, indication that ECDSA may have
better security than DSA. Furthermore, some of the new proof techniques
do not work for the modi¬ed versions of ECDSA for which the initial proof
techniques applied. Therefore, it can no longer be argued that the modi¬ed
versions have superior provable security; rather, it should be said that they
have provable security incomparable to ECDSA.
Cryptanalysis results are the converse to provable security results and are
just as important. In this chapter, conditional results are included, because
no successful, practical cryptanalysis of ECDSA is known. The hypotheses of
21
22 II. ON THE PROVABLE SECURITY OF ECDSA

a provable security result is a su¬cient condition for security, while a crypt-
analysis result establishes a necessary condition for security. For example,
one conditional cryptanalysis result for ECDSA is that if a hash collision can
be found, then a certain type of forgery of ECDSA is possible. Therefore,
collision resistance of the message digest hash function is a necessary condi-
tion for the security of ECDSA. Note however that this is not yet a successful
cryptanalysis of ECDSA, because no collisions have been found in ECDSA™s
hash function.



II.1.2. Examining the ECDSA Construction. The primary purpose of
the provable security results are to examine the security of ECDSA. The
purpose is not to examine the security of the primitives ECDSA uses (elliptic
curve groups and hash functions). Even with the secure primitives, it does
not follow a priori that a digital signature built from these primitives will be
secure. Consider the following four signature scheme designs, characterized
by their veri¬cation equations for signatures (r, s). Each is based on ECDSA
but with the value r used in various di¬erent ways, and in all cases signatures
can be generated by the signer by computing r = [k]G and applying a signing
equation.
• The ¬rst scheme, with veri¬cation r = f ([s’1 r]([H(m)]G + Y )), is
forgeable through (r, s) = (f ([t]([H(m)]G + Y )), t’1 r), for any t and
message m. Evidently, the veri¬cation equation does not securely bind,
informally speaking, the ¬ve values r, s, m, G, Y .
• The second scheme, ECDSA, is veri¬ed with r = f ([s’1 ]([H(m)]G +
[r]Y )). Moving the position of r on the right-hand side of the veri¬ca-
tion equation seems to turn an insecure scheme into a secure one. Now
all ¬ve values have become securely bound.
• The third scheme, veri¬ed with r = f ([s’1 ]([H(m, r)]G + Y )), has r
in yet another position. The third scheme seems secure, and the prov-
able security results of Pointcheval and Stern [276] using the Forking
Lemma seem adaptable to this scheme.
• A fourth scheme, veri¬ed with r = f ([s’1 ]([H(m, r)]G + [r]Y )), com-
bines the second and third in that r appears twice on the right, once
in each location of the second and third. Although the fourth scheme
could well have better security than both the second and third schemes,
it is argued that the overuse of r in the right-hand side of the third and
fourth schemes is an obstacle to certain security proof techniques. Be-
cause the value r occurs both inside a hash function evaluation and
as a scalar multiple in the elliptic curve group, formulating mild and
independent hypotheses about the two primitives is not obvious and
inhibits the construction of a security proof.
II.2. DEFINITIONS AND CONDITIONS 23

II.2. De¬nitions and Conditions
II.2.1. Security for Signatures. Goldwasser, Micali and Rivest introduced
in [150] the now widely accepted formal de¬nition for signature schemes and
their security.
Definition II.1 (Signature Scheme). A signature scheme is a triple of prob-
abilistic algorithms Σ = (K, G, V ), such that K has no input (except random-
ness) and outputs a public key Y and private key x; G has input of the private
key x and an arbitrary message m and outputs a signature S; and V has input
of the public key Y , message m and signature S and outputs either valid or
invalid.
A signature scheme is correct if the following holds: For any message m
and any randomness, computing K :’ (x, Y ) and then G : (x, m) ’ S will
ensure the result V : (Y, m, S) ’ Valid. If G does not use its randomness
input, then Σ is said to be deterministic. If, for each message m and public
key Y , at most one signature S satis¬es V (Y, m, S) = Valid, then Σ is said
to be veri¬ably deterministic.
Definition II.2. A forger of signature scheme (K, G, V ) is a probabilistic
algorithm F , having input of either a public key Y or a signature S and an
internal state X, and having output of a message m, state X, and R, which
is either a signature or a request for a signature of a message mi .
A forger F is measured by its ability to win the following game.
Definition II.3. The forgery game for a forger F of signature scheme Σ =
(K, G, V ) has multiple rounds, each consisting of two plays, the ¬rst by the
signer and the second by the forger.
• In Round 0, the signer uses K to output public key Y and a private
key x.
• Next, the forger is given input of the public key Y and a ¬xed initial
state X0 , and it outputs a message mi , a state X1 and a request or
signature R1 .
• For i ≥ 1, Round i works as follows.
“ If Ri is a request for a signature, then the signer uses G with
input of x and the message mi to output a signature Si . Next, the
forger is called again with input of the signature Si and the state
Xi . It will then return a new message mi+1 , a new state Xi+1 ,
and a new request or signature Ri+1 .
“ If Ri is a signature, not a request, then the game is over.
When the game ends, at Round i, the forger has won if both mi+1 = m1 , . . . , mi
and V (Y, mi+1 , Ri+1 ) = Valid; otherwise, the forger has lost.
We can now de¬ne a meaningful forger.
24 II. ON THE PROVABLE SECURITY OF ECDSA

Definition II.4 (Forger). A forger F is a (p, Q, t)-forger of signature scheme
(K, G, V ) if its probability of winning the forgery game in at most Q rounds
using computational e¬ort at most t is at least p. A signature Σ is (p, Q, t)-

. 1
( 10)



>>