Curve25519: new Diﬃe-Hellman speed records

Posted at 2025-07-19

Curve25519: new Diﬃe-Hellman speed records
Daniel J. Bernstein
https://iacr.org/archive/pkc2006/39580209/39580209.pdf

References

— (no editor), 17th annual symposium on foundations of computer science, IEEE Computer Society, Long Beach, California, 1976. MR 56:1766. See [52].
Kazimierz Alster, Jerzy Urbanowicz, Hugh C. Williams (editors), Public-key cryptography and computational number theory: proceedings of the international conference held in Warsaw, September 11–15, 2000, Walter de Gruyter, Berlin, 2001. ISBN 3–11–017046–9. MR 2002h:94001. See [60].
Adrian Antipa, Daniel Brown, Alfred Menezes, Ren´e Struik, Scott Vanstone, Vali- dation of elliptic curve public keys, in [21] (2003), 211–223. MR 2171928. Citations in this paper: §1.
Roberto M. Avanzi, Aspects of hyperelliptic curves over large prime fields in soft-
ware implementations, in [36] (2004), 148–162. Citations in this paper: §1, §5.
Roberto M. Avanzi, Generic algorithms for computing discrete logarithms, in [19]
(2005), 477–494. MR 2162735. Citations in this paper: §3, §3.
Roberto M. Avanzi, Preda Mih˘
ailescu, Generic eﬃcient arithmetic algorithms for
PAFFs (processor adequate finite fields) and related algebraic structures (extended
abstract), in [43] (2004), 320–334. Citations in this paper: §4.
Daniel V. Bailey, Christof Paar, Eﬃcient arithmetic in finite field extensions with
application in elliptic curve cryptography, Journal of Cryptology 14 (2001), 153–
ISSN 0933–2790. Citations in this paper: §1, §4.
Mihir Bellare (editor), Advances in cryptology—CRYPTO 2000: proceedings of
the 20th Annual International Cryptology Conference held in Santa Barbara, CA,
August 20–24, 2000, Lecture Notes in Computer Science, 1880, Springer-Verlag,
Berlin, 2000. ISBN 3–540–67907–3. MR 2002c:94002. See [14].
Andreas Bender, Guy Castagnoli, On the implementation of elliptic curve cryp-
tosystems, in [16] (1990), 186–192. MR 91d:11154. Citations in this paper: §4.
Kamel Bentahar, The equivalence between the DHP and DLP for elliptic curves
used in practical applications, revisited (2005). URL: http://eprint.iacr.org/
2005/307. Citations in this paper: §3.
Daniel J. Bernstein, The Poly1305-AES message-authentication code, in [32]
(2005), 32–49. URL: http://cr.yp.to/papers.html#poly1305. ID 0018d9551b55
46d97c340e0dd8cb5750. Citations in this paper: §4.
Daniel J. Bernstein, Cache-timing attacks on AES (2005). URL: http://cr.yp.to/
papers.html#cachetiming. ID cd9faae9bd5308c440df50fc26a517b4. Citations in
this paper: §1, §4.
Daniel J. Bernstein, Salsa20 specification (2005). URL: http://cr.yp.to/
snuffle.html. Citations in this paper: §3.
Ingrid Biehl, Bernd Meyer, Volker M¨
uller, Diﬀerential fault attacks on elliptic curve
cryptosystems (extended abstract), in [8] (2000), 131–146. URL: http://lecturer.
ukdw.ac.id/vmueller/publications.php. Citations in this paper: §1, §3.
Colin Boyd (editor), Advances in cryptology—ASIACRYPT 2001: proceedings of
the 7th international conference on the theory and application of cryptology and
information security held on the Gold Coast, December 9–13, 2001, Lecture Notes
in Computer Science, 2248, Springer-Verlag, Berlin, 2001. ISBN 3–540–42987–5.
MR 2003d:94001. See [59].
Gilles Brassard (editor), Advances in cryptology—CRYPTO ’89, Lecture Notes in
Computer Science, 435, Springer-Verlag, Berlin, 1990. ISBN 0–387–97317–6. MR
91b:94002. See [9].
Michael Brown, Darrel Hankerson, Julio L´
opez, Alfred Menezes, Software im-
plementation of the NIST elliptic curves over prime fields (2000); see also
newer version [18]. URL: http://www.cacr.math.uwaterloo.ca/techreports/
2000/corr2000-56.ps. Citations in this paper: §1, §5.
Michael Brown, Darrel Hankerson, Julio L´
opez, Alfred Menezes, Software imple-
mentation of the NIST elliptic curves over prime fields, in [49] (2001), 250–265;
see also older version [17]. MR 1907102.
Henri Cohen, Gerhard Frey (editors), Handbook of elliptic and hyperelliptic curve
cryptography, CRC Press, 2005. ISBN 1–58488–518–1. See [5], [24], [25], [30].
Yvo Desmedt (editor), Advances in cryptology—CRYPTO ’94, Lecture Notes in
Computer Science, 839, Springer-Verlag, Berlin, 1994. See [44].
Yvo Desmedt, Public Key Cryptography—PKC 2003, 6th international workshop
on theory and practice in public key cryptography, Miami, FL, USA, January 6–
8, 2003, proceedings, Lecture Notes in Computer Science, 2567, Springer, Berlin,
ISBN 3–540–00324–X. See [3].
Claus Diem, The GHS attack in odd characteristic, Journal of the Ramanujan
Mathematical Society 18 (2003), 1–32. MR 2004a:14030. URL: http://www.math.
uni-leipzig.de/~diem/preprints. Citations in this paper: §4.
Whitfield Diﬃe, Martin Hellman, New directions in cryptography, IEEE Transac-
tions on Information Theory 22 (1976), 644–654. ISSN 0018–9448. MR 55:10141.
URL: http://cr.yp.to/bib/entries.html#1976/diffie. Citations in this paper:
§3.
Christophe Doche, Tanja Lange, Arithmetic of elliptic curves, in [19] (2005), 267–
MR 2162729. Citations in this paper: §A.
Christophe Doche, Tanja Lange, Arithmetic of special curves, in [19] (2005), 355–
MR 2162731. Citations in this paper: §4.
Kenny Fong, Darrel Hankerson, Julio L´
opez, Alfred Menezes, Field inversion and
point halving revisited (2003); see also newer version [27]. URL: http://www.
cacr.math.uwaterloo.ca/techreports/2003/tech reports2003.html. Citations
in this paper: §1.
Kenny Fong, Darrel Hankerson, Julio L´
opez, Alfred Menezes, Field inversion and
point halving revisited, IEEE Transactions on Computers 53 (2004), 1047–1059;
see also older version [26]. ISSN 0018–9340.
Jens Franke, Thorsten Kleinjung, Christof Paar, Jan Pelzl, Christine Priplata, Mar-
tin Simka, Colin Stahlke, An eﬃcient hardware architecture for factoring integers
with the elliptic curve method, Workshop Record of SHARCS 2005 (2005), 51–62.
URL: http://www.best.tuke.sk/simka/pub.html. Citations in this paper: §3, §3.
Gerhard Frey, How to disguise an elliptic curve (Weil descent) (1998).
URL: http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/slides.
html. Citations in this paper: §4.
Gerhard Frey, Tanja Lange, Transfer of discrete logarithms, in [19] (2005), 529–543.
MR 2162738. Citations in this paper: §3.
Robert P. Gallant, Robert J. Lambert, Scott A. Vanstone, Faster point multiplica-
tion on elliptic curves with eﬃcient endomorphisms, in [38] (2001), 190–200. MR
2003h:14043. Citations in this paper: §5.
Henri Gilbert, Helena Handschuh (editors), Fast software encryption: 12th interna-
tional workshop, FSE 2005, Paris, France, February 21–23, 2005, revised selected
papers, Lecture Notes in Computer Science, 3557, Springer, 2005. ISBN 3–540–
26541–4. See [11].
Darrel Hankerson, Julio Lopez Hernandez, Alfred Menezes, Software imple-
mentation of elliptic curve cryptography over binary fields (2000); see also
newer version [34]. URL: http://www.cacr.math.uwaterloo.ca/techreports/
2000/corr2000-42.ps. Citations in this paper: §1.
Darrel Hankerson, Julio Lopez Hernandez, Alfred Menezes, Software implementa-
tion of elliptic curve cryptography over binary fields, in [40] (2000), 1–24; see also
older version [33].
Darrel Hankerson, Alfred Menezes, Scott Vanstone, Guide to elliptic curve cryp-
tography, Springer, New York, 2004. ISBN 0–387–95273–X. MR 2054891. Citations
in this paper: §4.
Marc Joye, Jean-Jacques Quisquater (editors), Cryptographic hardware and embed-
ded systems—CHES 2004: 6th international workshop, Cambridge, MA, USA, Au-
gust 11–13, 2004, proceedings, Lecture Notes in Computer Science, 3156, Springer,
ISBN 3–540–22666–4. See [4].
Burton S. Kaliski Jr. (editor), Advances in cryptology—CRYPTO ’97: 17th annual
international cryptology conference, Santa Barbara, California, USA, August 17–
21, 1997, proceedings, Lecture Notes in Computer Science, 1294, Springer, 1997.
ISBN 3–540–63384–7. MR 99a:94041. See [42].
Joe Kilian (editor), Advances in cryptology: CRYPTO 2001, 21st annual inter-
national cryptology conference, Santa Barbara, California, USA, August 19–23,
2001, proceedings, Lecture Notes in Computer Science, 2139, Springer, 2001. ISBN
3–540–42456–3. MR 2003d:94002. See [31].
Neal Koblitz, Alfred J. Menezes, Another look at “provable security”
(2004). URL: http://www.cacr.math.uwaterloo.ca/~
ajmeneze/publications/
provable.pdf. Citations in this paper: §3.
C ¸
etin Kaya Ko
c, Christof Paar, Cryptographic hardware and embedded systems—
¸
CHES 2000: Proceedings of the 2nd International Workshop held in Worcester,
MA, USA, August 2000, Lecture Notes in Computer Science, Springer, 2000. ISBN
3–540–42521–7. See [34].
Fabian Kuhn, Rene Struik, Random walks revisited: extensions of Pollard’s rho
algorithm for computing multiple discrete logarithms, in [64] (2001), 212–229. URL:
http://www.distcomp.ethz.ch/publications.html. Citations in this paper: §3.
Chae Hoon Lim, Pil Joong Lee, A key recovery attack on discrete log-based
schemes using a prime order subgroup, in [37] (1997), 249–263. URL: http://
dasan.sejong.ac.kr/~
chlim/english pub.html. Citations in this paper: §3, §3.
Mitsuru Matsui, Robert Zuccherato (editors), Selected areas in cryptography: 10th
annual international workshop, SAC 2003, Ottawa, Canada, August 14–15, 2003,
revised papers, Lecture Notes in Computer Science, 3006, Springer, 2004. ISBN
3–540–21370–8. See [6].
Ueli M. Maurer, Towards the equivalence of breaking the Diﬃe-Hellman protocol
and computing discrete logarithms, in [20] (1994), 271–281. URL: http://www.
crypto.ethz.ch/~
maurer/publications.html. Citations in this paper: §3.
Alfred Menezes, Another look at HMQV (2005). URL: http://eprint.iacr.org/
2005/205. Citations in this paper: §2.
Victor S. Miller, Use of elliptic curves in cryptography, in [65] (1986), 417–426. MR
88b:68040. Citations in this paper: §1.
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of fac-
torization, Mathematics of Computation 48 (1987), 243–264. ISSN 0025–5718.
MR 88e:11130. URL: http://cr.yp.to/bib/entries.html#1987/montgomery. Ci-
tations in this paper: §5.
A. Muzereau, Nigel P. Smart, Frederik Vercauteren, The equivalence between the
DHP and DLP for elliptic curves used in practical applications, LMS Journal of
Computation and Mathematics 7 (2004), 50–72. URL: http://www.lms.ac.uk/
jcm/7/lms2003-034/. Citations in this paper: §3.
David Naccache (editor), Topics in cryptology—CT-RSA 2001: Proceedings of the
Cryptographers’ Track at the RSA Conference held in San Francisco, CA, April
8–12, 2001, Lecture Notes in Computer Science, 2020, Springer, 2001. ISBN 3–
540–41898–9. MR 2003a:94039. See [18].
Dag Arne Osvik, Adi Shamir, Eran Tromer, Cache atacks and countermeasures:
the case of AES (extended version) (2005). URL: http://www.wisdom.weizmann.
ac.il/~tromer/. Citations in this paper: §1.
Colin Percival, Cache missing for fun and profit (2005). URL: http://www.
daemonology.net/hyperthreading-considered-harmful/. Citations in this pa-
per: §1.
Nicholas Pippenger, On the evaluation of powers and related problems (prelimi-
nary version), in [1] (1976), 258–263; newer version split into [53] and [54]. MR
58:3682. URL: http://cr.yp.to/bib/entries.html#1976/pippenger. Citations
in this paper: §5.
Nicholas Pippenger, The minimum number of edges in graphs with prescribed
paths, Mathematical Systems Theory 12 (1979), 325–346; see also older version
[52]. ISSN 0025–5661. MR 81e:05079. URL: http://cr.yp.to/bib/entries.html#
1979/pippenger.
Nicholas Pippenger, On the evaluation of powers and monomials, SIAM Journal
on Computing 9 (1980), 230–250; see also older version [52]. ISSN 0097–5397. MR
82c:10064. URL: http://cr.yp.to/bib/entries.html#1980/pippenger.
John M. Pollard, Kangaroos, Monopoly and discrete logarithms, Journal of Cryp-
tology 13 (2000), 437–447. ISSN 0933–2790. Citations in this paper: §3.
John Proos, Christof Zalka, Shor’s discrete logarithm quantum algorithm for elliptic
curves (2003). URL: http://www.cacr.math.uwaterloo.ca/techreports/2003/
tech reports2003.html. Citations in this paper: §1.
Nigel P. Smart, A comparison of diﬀerent finite fields for use in elliptic curve
cryptosystems (2000); see also newer version [58]. URL: http://www.cs.bris.ac.uk/Publications/pub info.jsp?id=1000458.
Nigel P. Smart, A comparison of diﬀerent finite fields for elliptic curve cryptosystems, Computers and Mathematics with Applications 42 (2001), 91–100; see also older version [57]. MR 2002c:94033. Citations in this paper: §1.
Martijn Stam, Arjen K. Lenstra, Speeding up XTR, in [15] (2001), 125–143. MR 2003h:94049. Citations in this paper: §5.
Edlyn Teske, Square-root algorithms for the discrete logarithm problem (a survey), in [2] (2001), 283–301. MR 2003c:11156. URL: http://www.cacr.math.uwaterloo.ca/~eteske/publications.html. Citations in this paper: §3.
Edlyn Teske, Computing discrete logarithms with the parallelized kangaroo method (2001); see also newer version [62]. URL: http://www.cacr.math.uwaterloo.ca/techreports/2001/tech reports2001.html. Citations in this paper: §3.
Edlyn Teske, Computing discrete logarithms with the parallelized kangaroo method, Discrete Applied Mathematics 130 (2003), 61–82; see also older version [61]. MR 2004h:11112.
Paul C. van Oorschot, Michael Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology 12 (1999), 1–28. ISSN 0933–2790. URL:http://members.rogers.com/paulv/papers/pubs.html. Citations in this paper:§3.64. Serge Vaudenay, Amr M. Youssef (editors), Selected areas in cryptography: 8th annual international workshop, SAC 2001, Toronto, Ontario, Canada, August 16–17, 2001, revised papers, Lecture Notes in Computer Science, 2259, Springer, 2001. ISBN 3–540–43066–0. MR 2004k:94066. See [41].
Hugh C. Williams (editor), Advances in cryptology: CRYPTO ’85, Lecture Notes in Computer Science, 218, Springer, Berlin, 1986. ISBN 3–540–16463–4. See [46].

Curve25519: new Diﬃe-Hellman speed records

References

Related Article on Qiita