US10284370B2 — Accelerated verification of digital signatures and public keys
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
US010284370B2
(12) United States Patent ( 10) Patent No.: US 10 ,284 ,370 B2
Struik et al. (45) Date of Patent: *May 7 , 2019
(54 ) ACCELERATED VERIFICATION OF ( 58 ) Field of Classification Search
DIGITAL SIGNATURES AND PUBLIC KEYS CPC ....... H04L 9 /3066 ; H04L 9 /30 ; H04L 9/3252 ;
G06F 7 /725
( 71 ) Applicant: Certicom Corp ., Mississauga (CA ) See application file for complete search history .
(72) Inventors : Marinus Struik , Toronto (CA ); Daniel (56 ) References Cited
Richard L . Brown, Mississauga (CA );
Scott Alexander Vanstone, U .S . PATENT DOCUMENTS
Campbellville (CA ); Robert Philip 4 ,519 ,036 A 5/ 1985 Green
Gallant, Corner Brook (CA ); Adrian 4 ,745, 568 A 5 /1988 Onyszchuk et al.
Antipa , Brampton (CA ) ; Robert John (Continued )
Lambert , Cambridge (CA )
FOREIGN PATENT DOCUMENTS
(73) Assignee : Certicom Corp., Mississauga , Ontario
(CA ) EP 588339 3 / 1994
FR 2536928 6 / 1984
( * ) Notice : Subject to any disclaimer, the term of this (Continued )
patent is extended or adjusted under 35
U .S .C . 154 (b ) by 44 days. OTHER PUBLICATIONS
This patent is subject to a terminal dis Antipa , A ., D . R . L . Brown , R . P. Gallant, R . Lambert, R . Struik and
claimer. S . A . Vanstone. Accelerated verification of ECDSA signatures. In B .
Preneel and S . Tavares (eds. ), Selected Areas in Cryptography: SAC
(21) Appl.No.: 14/318,313 2005 , Lecture Notes in Computer Science 3897 , pp . 307 - 318 .
Springer, Aug . 2005 .
(22 ) Filed : Jun . 27, 2014 (Continued )
(65 ) Prior Publication Data Primary Examiner - Eleni A Shiferaw
US 2014 /0344579 A1 Nov . 20, 2014 Assistant Examiner — Sher A Khan
(74 ) Attorney, Agent, or Firm — Fish & Richardson P .C .
Related U .S . Application Data (57 ) ABSTRACT
(63) Continuation of application No. 13/620 ,206 , filed on Accelerated computation of combinations of group opera
Sep . 14 , 2012 , now Pat. No. 8,788 ,827 , which is a tions in a finite field is provided by arranging for at least one
(Continued ) of the operands to have a relatively small bit length . In a
elliptic curve group, verification that a value representative
(51) Int . CI. of a point R corresponds the sum of two other points ug and
H04L 29/ 06 ( 2006 .01) VG is obtained by deriving integers w ,z of reduced bit length
H04L 9 /30 (2006 .01 ) and that v = w /z . The verification equality R = uG + vQ may
(Continued ) then be computed as -zR + (uz mod n )G +wQ = 0 with z and
(52) U . S . CI. w ofreduced bit length . This is beneficial in digital signature
CPC ............ H04L 9 /3066 ( 2013 .01); G06F 7 / 725 verification where increased verification can be attained .
(2013.01); H04L 9/30 (2013 .01 ); H04L 9 /3252
(2013.01) 11 Claims, 14 Drawing Sheets
Sign M to obtain Recover
Tis
Compute
Q = ( s / r ) R - ( e / r /G
Confim
Q = public key of
sender
US 10 ,Page
284 ,2370 B2
Related U . S . Application Data 6 ,446 , 207 B19 / 2002 Vanstone et al.
6 ,490 ,352 B1 * 12/ 2002 Schroeppel ........... H04L 9 /3066
continuation of application No. 13 /478 ,288 , filed on 380 / 279
May 23 , 2012 , now Pat. No. 8 , 806 , 197, which is a 6 ,496 , 929 B2 12 / 2002 Lenstra
continuation of application No. 11 /333 ,296 , filed on 6 ,724 , 894 B1 4 / 2004 Singer
Jan . 18 , 2006 , now Pat. No . 8 , 204, 232 . 6 ,816 , 594 B1 * 11/ 2004 Okeya ............... G06F 7 / 725
380/ 59
6 , 829 ,356 B1 12 / 2004 Ford
(60 ) Provisional application No . 60/644 ,034 , filed on Jan . 6 . 873 ,706 B13 / 2005 Miyazaki et al.
18 , 2005. 6 ,876 ,745 B1 * 4 /2005 Kurumatani ............ GO6F 7 /725
380 /28
(51) Int. CI. 7 ,036 ,015 B2 * 4 / 2006 Vanstone ............. H04L 9 /3247
380 / 28
G06F 7 / 72 ( 2006 . 01) 7 ,092 ,522 B1 * 8/2006 Futa . .......... G06F 17 / 12
H04L 9 /32 ( 2006 .01) 380 / 28
7,110 ,538 B2 * 9 /2006 Gallant . ............ G06F 7 /725
(56 ) References Cited
7 , 127 ,063 B2 10 / 2006 Lambert et al.
380 / 28
U .S . PATENT DOCUMENTS 7 ,215 ,780 B25 /2007 Lambert et al.
7 ,218 , 735 B2 * 5 / 2007 Coron ...... ... H04L 9/0841
4 ,748,668 A 5 / 1988 Shamir et al. 380 / 30
4 ,890 , 323 A 12 / 1989 Becker et al. 7 ,353 ,541 B1 * 4 /2008 Ishibashi ... G06F 21/ 10
4 ,989, 171 A 1 / 1991 Hollmann 348 /E7.056
5 , 146 ,500 A 9 / 1992 Maurer 7 ,421,074 B2 9 / 2008 Jin et al.
5 , 150,411 A 9 /1992 Maurer 7 ,486 ,789 B2 2 /2009 Futa et al.
5 , 159,632 A 10 / 1992 Crandall 7 ,593, 527 B2 9 / 2009 Beeson
5 ,202, 995 A 4 / 1993 O 'Brien 7 ,599 ,491 B2 10 /2009 Lambert
5 ,218 ,637 A 6 / 1993 Angebaud et al . 7 ,603, 560 B2 * 10 /2009 Crandall G06F 7 /725
5 ,271, 061 A 12 / 1993 Crandall 380 / 30
5 , 272,755 A * 12 / 1993 Miyaji ................ H04L 9 /3073 7 ,613 ,660 B2 11/ 2009 Pintsov
380 / 28 7 ,620 , 179 B2 * 11/ 2009 Fahrny . ... ...... H04N 7 / 1675
5, 351,297 A 9 / 1994 Miyaji et al. 380 /210
5 ,373, 560 A 12/ 1994 Schlafly 8 ,069, 346 B2 11/2011 Struik
5 ,442 ,707 A 8 / 1995 Miyaji et al. 8 ,204 ,232 B2 6 /2012 Struik et al.
5 .463,690 A 10 / 1995 Crandall 8 , 307,211 B2 11 /2012 Vanstone
5 ,497,423 A 3 / 1996 Miyaji 8 ,467, 535 B2 6 / 2013 Struik
5 ,511 ,198 A 4 / 1996 Hotta 2001/0034834 Al * 10 /2001 Matsuyama .......... H04L 9 /3268
5 ,524 ,222 A 6 / 1996 Hervin 713/ 156
5 ,627,893 A * 5 / 1997 Demytko ............. G06F 7 /725 2001/ 0053220 Al 12 / 2001 Kocher et al.
380 /28 2002/0021810 A1 * 2 /2002 Solinas ........ ........ HO4L 9 /0841
5 ,650 , 948 A 7 / 1997 Gafter 380 / 278
5 ,675 ,645 A 10 / 1997 Schwartz et al. 2002/0044649 A1* 4 /2002 Gallant ................. G06F 7 /725
5 ,757,918 A 5 / 1998 Hopkins 380/30
5 , 761, 305 A 6 / 1998 Vanstone et al. 2002/ 0057796 AL 5 / 2002 Lambert et al.
5 , 764,772 A 6 / 1998 Kaufman et al. 2002/0108041 A1* 8/2002 Watanabe ............ HO4L 9/3252
5 , 768 ,389 A 6 / 1998 Ishii
5 ,778, 069 A 7 / 1998 Thomlinson et al. 713 / 175
5 ,825, 880 A 10 / 1998 Sudia et al. 2002/0152252 A1 * 10 /2002 Kaminaga .... GO6F 7 / 722
5 ,889, 865 A 3 / 1999 Vanstone et al. 708 /491
5 ,892, 899 A 4 / 1999 Aucsmith et al. 2002/0166058 AL 11/2002 Fueki
5 ,896 ,455 A 4 / 1999 Vanstone et al. 2002/0172356 A1 * 11/ 2002 Ono .............. G06F 7 /723
5 ,937, 066 A 8 / 1999 Gennaro et al. 380 / 28
5 ,987, 131 A 11/ 1999 Clapp 2003/0021410 A1 * 1/2003 Miyazaki ....... G06F 7 /728
5 , 999 ,626 A * 12 / 1999 Mullin G06Q 20380/341
/30 2003/0044003 Al 3/2003 Chari et al.
380 / 30
6 ,088 ,798 A * 7/ 2000 Shimbo ................ H04L 9 /3066 2003/ 0048903 Al 3 / 2003 Ito et al.
380 / 30 2003/ 0059042 Al 3 /2003 Okeya et al.
6 , 122 ,736 A 9 / 2000 Vanstone et al. 2003 /0059043 A1 3 / 2003 Okeya et al.
6 ,141,420 A 10 /2000 Vanstone et al . 2003/ 0061498 AL 3/ 2003 Drexler et al.
6 ,212 ,279 B14 /2001 Reiter et al. 2003/0194086 A1* 10 /2003 Lambert ......... GO6F 7 /725
6 ,243 ,467 B1 * 6 /2001 Reiter ... .... ...... . G06F 7 /725 380 /44
380 /30 2003 / 0235300 A1 * 12 /2003 Solinas ................. HO4L 9 /0866
6 ,263 ,081 B1* 7/2001 Miyaji .............. G06F 7 /725 380 /30
380 / 28 2004/0098440 A1 * 5 /2004 Koc ...................... GO6F 7 /5324
6 ,266 ,717 B1* 7/2001 Dworkin ................... GO6F 7 /72 708 /620
710 / 36 2004/0114760 A1 * 6 /2004 Brown ................. GO6F 7 /725
6 ,279 ,110 B1 8/2001 Johnson et al. 380/ 255
6 ,292 ,897 B1 * 9 / 2001 Gennaro .. .... HO4L 9 / 321
713 / 156 2004 /0131191 A1* 7/2004 Chen ..................... H04L 9 /3013
6 ,298 , 135 B1 10 /2001 Messerges et al. 380 /282
6 , 304,658 B1 10 / 2001 Kocher et al. 2004 /0221163 Al* 11/2004 Jorgensen ........... H04L 63/0428
6 ,307 ,935 B1 * 10 / 2001 Crandall ................. G06F 7 /725 713/ 182
380 / 28 2004/0249765 A1 * 12/2004 Leon ......... GO6F 21/ 32
6 , 334 ,189 B1 12 /2001 Granger et al. 705/64
6 ,411,715 B1 6 /2002 Liskov et al. 2005/0039100 A1 * 2/2005 Bade ............. G06Q 10 / 107
6 ,419 , 159 B1 7 /2002 Odinak 714 / 746
6 ,430 ,588 B1 * 8 / 2002 Kobayashi G06F 7 / 725 2005 /0102516 A1 * 5 /2005 Oishi H04L 9 /3066
708 /492 713 / 168
US 10 ,Page
284 ,3370 B2
( 56 ) References Cited Kelsy , J. et al., " Side Channel Cryptanalysis of Product Ciphers” ;
Journal of Computer Security 8 ; 2000,; pp . 141- 158 .
U . S . PATENT DOCUMENTS Koblitz, Neal; “ CM -Curves with Good Cryptographic Properties” ;
Advances in Cryptography — CRYPTO '91; 1991; pp . 279 - 287 .
2005/0135606 A1 * 6 /2005 Brown .............. H04L 9 / 3066 Koblitz , Neal; “ Elliptic Curve Cryptosystems" ; Mathematics of
380 / 28 Computation ,; vol. 48 , No. 177 , 1987 ; pp . 203 -209 .
2007/0121933 Al * 5/2007 Futa ................. H04L 9 /380
3066/ 1 Kocher, P. et al.; “ Differential Power Analysis ” ; Advances in
2007/0121935 A1 * 5/2007 Joye ..... ..... G06F 7 /723 Cryptology - CRYPTO ’ 99 ; Proceedings of the 19th Annual Inter
380 /30 national Cryptology Conference ; 1999 ; pp . 388 - 397 .
2007/0150735 Al* 6 / 2007 Futa .................. H04L 9/0844 Kocher, P. et al.; “ Introduction to Differential Power Analysis and
713 / 171 Related Attacks” ; Cryptography Research ; 1998 , 5 pages.
Kocher, Paul C .; “ Timing Attacks on Implementations of Diffie
FOREIGN PATENT DOCUMENTS Hellman , RSA , DSS , and Other Systems”, Advances in Cryptology
CRYPTO ' 96 ; Proceedings of the 16th Annual International Cryptol
FR 2672402 8 / 1992 ogy Conference ; vol. 1109; 1996 ; pp . 104 - 113.
JP 2002- 328602 11 / 2002 Koyama, K . et al.; " Elliptic Curve Cryptosystems and Their Appli
JP 2004 - 163687 6 / 2004
cations” ; IEICE Transactions on Information and Systems; vol.
WO WO1991016691 10 / 1991
WO WO199800771 1 / 1998 E75 - D , No. 1 ; 1992; pp . 50 -57 .
WO WO199852319 11/ 1998 Lercier, R .; “ Finding Good Random Elliptic Curves for Cryptosystems
WO WO200042733 7 /2000 Defined over Finite Fields” ; Advances in Cryptography ,
WO WO2006076800 7 /2006 EUROPCRYPT ' 97 ; vol. 1233 ; 1997; pp . 379 - 392 .
WO WO2009030021 3 / 2009 Loy ' asz , L ., 'An Algorithmic Theory of Numbers, Graphs and
Convexity,' CBMSNSF Regional Conference Series in Applied
OTHER PUBLICATIONS Mathematics, Band 50 , SIAM Publications, 1986 ; 98 pages.
Menezes , A . et al.; “ The Implementation of Elliptic Curve
ANSI X9.62- 1998 , Public Key Cryptography for the Financial Cryptosystems” of“ Lecture Notes in Computer Science " ; Advances
Services Industry : The Elliptic Curve Digital Signature Algorithm in Cryptology - AUSCRYPT ’ 90 ; International Conference on Cryptol
ogy ; vol. 453 ; 1990 ; 14 pages.
(ECDSA ), American National Standard for Financial Services , Menezes, Alfred ; “ Elliptic Curve Cryptosystems" ; A thesis pre
American Bankers Association , Jan . 7 , 1999 ; 195 pages . sented to the University of Waterloo ; 1992 , pp . 1 -121 .
ANSI X9 .92 - 2002, Public -Key Cryptography for the Financial Menezes, Alfred . J.; “ Handbook of Applied Cryptography” ; CRC
Services Industry : Digital Signature Algorithms Providing Partial Press, 1997 ; pp . 613 , 614 , 618 .
Message Recovery ; Part 1 : Elliptic Curve Pintsov - Vanstone Signa Miller , Victor C .; “ Use of Elliptic Curves in Cryptography ” ; CRYTPO
tures (ECPVS ); Draft American National Standard ; 2002; 65 pages. ' 85 ; LNCS 218 ; 1985 ; pp . 417 -426 .
Bleichenbacher; “ Compressing Rabin Signatures” ; Lecture Notes in Miyaji , A .; “ Elliptic Curves Suitable for Cryptosystems” ; IEICE
Computer Science ; Springer, Berlin ; 2004 ; pp . 124 - 126 ; ISBN Transactions on Fundamentals of Electronics , Communications and
3 - 540 - 20996 - 4 . Computer Sciences; vol. E77- A , No. 1 ; 1994 ; pp . 98 - 104.
Cheon , J. H . et al.; " Two Efficient Algorithms for Arithmetic of Moller, Bodo ; “ Algorithms for Multi-Exponentiation " ; Selected
Elliptic Curves Using Frobenius Map ” ; Public Key Cryptography ; Areas in Cryptography — SAC 2001 ; LNCS 2259 ; pp . 165 - 180 .
First International Workshop on Practice and Theory in Public Key Mueller, Volker; " FastMultiplication on Elliptic Curves over Small
Cryptography - PCK 98 ; 1998 ; pp. 195 -202. Fields of Characteristic Two” ; Submitted to Journal of Cryptology ;
Ciet, M . et al.; “ Improved Algorithms for Efficient Arithmetic on 1997; pp . 1 - 19 .
Nguyen , P ., D . Stehl’ e , ‘Low - Dimensional Lattice - Basis Reduction
Elliptic Curves Using Fast Endomorphisms” ;Advances in Cryptology Revisited ,' in Proceedings of Algorithmic No . Theory — ANTS VI,
Eurocrypt; International Conference on Theory and Application of Lecture Notes in Computer Science , vol. 3076 , pp . 338 - 357 , 2004 .
Cryptographic Techniques ; May 4 , 2003; pp . 388 - 400 . Park , Y - H . et al.; " An Alternate Decomposition of an Integer for
Cohen , Henry , A Course in Computational Algebraic Number Faster Point Multiplication on Certain Elliptic Curves ” ; Proceed
Theory , Springer, 1993, ISBN 0 - 387 - 55640 -0 ; pp . 83 - 96 . ings of the 5th International Workshop on Practice and Theory in
Deitel, H . M . et al., “ C + + How to Program ” , 1994 , Prentice -Hall, pp . Public Key Cryptosystems; Jan . 1 , 2002; pp . 323 -334.
58 -62 . Sakai, Y, et al.; “ Algorithms for Efficient Simultaneous Elliptic
Dirichlet, G .L ., Verallgemeinerung eines Satzes aus der Lehrere Scalar Multiplication with Reduces Joint Hamming Weight Repre
von Kettenbruchen nebst einigen Anwendungen auf die Theorie der sentation of Scalars” ; Proceedings of the 5th International Confer
Zahlen ,' Berichtuber die zur Bekanntmachung geeigneter Verhandlungen ence on Information Security ; Sep . 30 , 2002 ; pp. 484- 499 .
der Koniglich Preussischen Akademie der Wissenschaften zu Ber Schnorr, C .P .; “ Efficient Signature Generation by Smart Cards” ;
lin ; 1842; 4 pages; Certification and English Translation Report Journal of Cryptology ; vol. 4 , No. 3 ; 1991; pp . 161- 174 .
Concerning the Negotiations of the Royal Prussian Academy of Solinas, J., ‘Low -Weight Binary Representations for Pairs of Inte
Sciences at Berlin Suitable to be Announced ; 1842; 5 pages . gers,' Centre for Applied Cryptographic Research , Corr 2001- 41,
Gallant, R ., R . Lambert, S . A . Vanstone , ‘Fast Point Multiplication University of Waterloo , Ontario , Canada, 2001; 24 pages .
on Elliptic Curves with Efficient Endomorphisms,’ in Proceedings Solinas, Jerome A .; “ An Improved Algorithm for Arithmetic on a
of Advances in Cryptology - CRYPTO 2001, Lecture Notes in Family of Elliptic Curves” of “ Lecture Notes in Computer Science” ;
Computer Science , vol. 2139 , pp . 190 - 200 , 2001. Advances in Cryptology - CRYPTO ’97; 17th Annual International
Hankerson , Darrel et al., “ Guide to Elliptic Curve Cryptography” ; Cryptology Conference ; 1997 ; pp. 357 - 371.
ISBN 0 - 387 - 95273 - X ; 2004 ; 332 pages Solinas, Jerome A .; “ Improved Algorithms for Arithmetic on
Hardy , G . H ., E .M . Wright, An Introduction to the Theory of Anormalous Binary Curves” ; Technical Report ; 1999 ; 69 pages .
Numbers, Fifth Edition , Oxford : Oxford University Press, 2000 ; pp . U .S . Department of Commerce /National Institute of Standards and
169 - 170 . Technology ; Federal Information Processing Standards Publication
IEEE P1363a Draft 12, Jul. 26 , 2003 ; 177 pages . (FIPS PUB 180 - 2 ); “ Secure Hash Standard ” ; Aug . 1 , 2002 ; 75
Johnson , D . et al.; " The Elliptic Curve Digital Signature Algorithm pages.
(ECDSA )" ; Certricom Corporation White Paper; 2001; pp . 2 -56 . U . S . Department of Commerce /National Institute of Standards and
D .J . Johnson , A . J. Menezes , S . A . Vanstone, ‘ The Elliptic Curve Technology ; Federal Information Processing Standards Publication
Digital Signature Algorithm (ECDSA ) ' International Journal of (FIPS PUB 186 -2 ); “ Digital Signature Standard (DSS )” ; Jan . 27 ,
Information Security, vol. 1, pp . 36 -63, 2001. 2000 ; 76 pages.
US 10 ,Page
284,4370 B2
( 56 ) References Cited Notice of Allowance issued in Canadian Application No. 2 ,770 ,001
dated Dec . 9 , 2013 ; 1 page.
OTHER PUBLICATIONS Supplementary European Search Report issued in corresponding
European Application No. 06701572 .7 dated Oct. 6 , 2009 ; 4 pages.
Waleffe , D . et al .; " CORSAIR : A Smart Card for Public Key Proceeding further with the European Application Pursuant to Rule
Cryptosystems” , Advances in Cryptology - CRYPTO ' 90 ; 1990 ; 70 ( 2 ) EPC issued in European Application No. 06701572. 7 on Oct.
pp . 502 -513. 23 , 2009; 6 pages .
Wang , C . et al.; “ VLSI Architectures for ComputingMultiplications Communication Pursuant to Article 94 ( 3 ) EPC issued in European
Application No. 06701572 .7 dated Mar. 8 , 2010 ; 4 pages.
and Inverses in GF (2m )” ; IEEE Transactions on Computers; vol. Communication Pursuant to Article 94 ( 3 ) EPC issued in European
C -34 , No. 8 ; 1985; pp . 709 - 717 . Application No. 06701572 .7 dated Jul. 16 , 2010 ; 4 pages .
Website: http ://cr.yp .to /sigs .compress .html; publication date of web Communication under Rule 71 (3 ) EPC issued in European Appli
site: unknown ; retrieved on Jul. 15 , 2009. cation No. 06701572.7 dated Apr. 4, 2011; 6 pages.
Wharton , John ; “ An Introduction to the Intel-MCS -51 Single -Chip Extended European Search Report issued in European Application
Microcomputer Family” ; Intel Corporation ; Intel Application No . No . 11178908. 7 dated Nov. 15 , 2011 ; 6 pages .
AP-69; 1980 ; 30 pages. Communication Pursuant to Article 94 (3 ) EPC issued in European
Yen S .M , et al.; “ Multi-Exponentiation ” ; IEEE Proceedings Comput. Application No. 11178908 .7 dated May 30 , 2012 ; 7 pages.
Digit. Tech ., vol. 141 , No. 6 ; 1994 ; pp. 325 -326 . Communication under Rule 71 ( 3 ) EPC issued in European Appli
Office Action issued in U .S . Appl. No. 11/ 333 ,296 dated Apr. 20 , cation No . 11178908. 7 dated Mar. 19 , 2013 ; 7 pages.
2009 ; 17 pages . Extended European Search Report issued in European Application
Office Action issued in U .S . Appl. No. 11/ 333 ,296 dated Dec . 3 , No . 12158215 . 9 dated Jul. 2 , 2012 ; 8 pages .
2009; 9 pages. Official Action issued in Japanese Application No. 2007-550647
Office Action issued in U .S. Appl. No. 11/333,296 dated Jun . 25, dated Jul. 19 , 2011 ; 3 pages.
Official Action issued in Japanese Application No. 2007-550647
2010 ; 7 pages .
Notice of Allowance issued in U .S . Appl. No. 11/333, 296 dated Jan . dated Nov. 25 , 2011 ; 4 pages.
21, 2011 ; 8 pages . Notice of Final Rejection issued in Japanese Application No.
Office Action issued in U . S . Appl. No. 11 /333 , 296 dated Oct. 13 , 2007 - 550647 dated Feb . 28 , 2012 ; 8 pages.
2011 ; 9 pages. Office Action issued in Japanese Application No. 2011- 230106
Notice of Allowance issued in U .S . Appl. No. 11 /666 ,296 dated dated Mar. 13 , 2013; 10 pages .
Mar. 19 , 2012 ; 7 pages . Notice of Allowance issued in Japanese Application No. 2011
File History of U .S . Appl. No. 11/333 ,296 . 230106 dated Aug. 28 , 2013 ; 3 pages . No English translation .
Office Action issued in U .S . Appl. No. 13 /478, 288 dated Nov . 6 , Office Action issued in Japanese Application No. 2012 - 143272
2013 ; 8 pages. dated Aug. 9 , 2013 ; 2 pages.
Office Action issued in U . S. Appl. No . 13 /620,206 dated Nov. 8 , International Search Report and Written Opinion of the Interna
2013 ; 9 pages . tional Searching Authority issued in International Application No.
Office Action issued in U . S . Appl. No. 13/041,759 dated Aug. 22 , PCT/CA2006 /00058 dated May 1, 2006 ; 11 pages.
2012 ; 7 pages. International Preliminary Report on Patentability issued in Interna
Examiner 's Report issued in Canadian Application No. 2,259, 089 tional Application No. PCT/CA2006 / 00058 dated Aug. 2 , 2007; 8
dated Feb . 2 , 2009 ; 3 pages . pages .
Examiner 's Report issued in Canadian Application No. 2, 592, 870 Office Action issued in Canadian Application No. 2935823 dated
dated Aug. 9 , 2012 ; 2 pages . Nov. 1 , 2017 ; 4 pages.
Office Action issued in Canadian Application No. 2,592, 875 dated
Feb . 10 , 2014 ; 3 pages . * cited by examiner
U . S . Patent May 7 , 2019 Sheet 1 of 14 US 10 ,284 ,370 B2
HOFU
MALALALALALAL
CPU
TIENNE
gjydelodhoModule
www
EEENTE
E
m
ne
MENY AMAN
YYYTETIT
*
PERA
Fig1ure
E
-
-
WHETHER +
LITTLE
30
Cryptographic
W
{
32
AKA.LA
{
W
24
w
TER CPU
???
NouaN 11 3 . 4 . 2 . 7. 1 .
..
XYXYETEXTYYTE
Swab
U . S . Patent May 7 , 2019 Sheet 2 of 14 US 10 ,284 ,370 B2
Generate & W.W
*
Compute KG *
CAL.ARAS
Integer conversion
Compute
KLAUSKAXAAA Figure 2
FREEEE Compute
Determine
venement et SendMand r.si
U . S . Patent May 7, 2019 Sheet 3 of 14 US 10 ,284 ,370 B2
WWWW Compute
Compute
What els mod n
Varis mod n
Compute
wyYTY
Figure 3
Recover point R
YLYLSY
Compute
ZR (zu mod nG W
* ** * ** ** ** * * * * * *
U . S . Patent May 7, 2019 Sheet 4 of 14 US 10 ,284 ,370 B2
receive w
T EK
recover
compute
W ,Z
wwwwwwww
WWWXWWW
- ZR * ((zu )modn )G4 » Q
WWW.
convert
retrieve
from 28 forme
compute
a 'G + 2 " ) $VO ** ZR ACK
REECT
Figure 4
U . S . Patent May 7, 2019 Sheet 5 of 14 US 10 ,284 ,370 B2
receive
2*$
wwwwww MUTHU
recover
WR2
MW.-WM
Wtom.AtoWrt
v
aG + WQ + ZR
ww
Iecover compute wQ + ZR
Annamanny REJECT
WAKE
VERIFY
Figure 5
tent May 7 , 2019 Sheet 6 of 14 US 10,284 ,370 B2
message M recover
1 ,51 NA
compute
WZ
determine validation equation
who
insert precoinputed
values
AKURIKULUK
dKOok
UVUVANJE
compute
Moda
- REJECT
VERIFY
Figure 6
U . S . Patent May 7, 2019 Sheet 7 of 14 US 10 ,284 ,370 B2
V
receive
recover
Awww take
wwwww
Figure 7
U . S . Patent May 7, 2019 Sheet 8 of 14 US 10 ,284 ,370 B2
select
UNERARI
compute
Bananya
wwwwwwwwwwwww
compute
Mercy
Figure 8 .
U . S . Patent May 7, 2019 Sheet 9 of 14 US 10 ,284 ,370 B2
generate
.. . . . RUAN
KP (x ,y)
m = x , ymod2 )
computer
wwwwwwwwwwwwwwwwwwwwwwwwwwwwww
KERA . ..
compute
WS
NAR
send r 's M
Ww
Figure 9
atent May 7 , 2019 Sheet 10 of 14 US 10 ,284 ,370 B2
TNMYYYYYNTES
generate
Ww
KP (x,y ) VV
change k
VAAAAA does ymod2 = 0 wwwWwwWWWWWWW
compute
LULULU
Send
Tecover R
assume i = 0 PICH
www
verify
KERX
Figure 10
atent May 7 , 2019 Sheet 11 of 14 US 10 ,284 ,370 B2
.
Compute .
Compute
AKRANELER
Obtain wm
TURKVENKYNL
M .www
ALALOKKRAWAKELKOR Compute
X coordinate of zR W
Compute x or
po (zu mod n /G
VAMAMAMWW
Reject
Figure 11
atent May 7 , 2019 Sheet 12 of 14 US 10 ,284 ,370 B2
Generate de
w wwwwwwwwwwwwwwwwwww
A
Compute w
dWZmod n AAAA
WANAWAWWAAAAAAA* www
wwwwwwwwwwwwwwwwwwwwwwwwwwww W
Compute
Does this = 0 ? Reject
www 2
Accept
WWW
Figure 12
atent May 7 , 2019 Sheet 13 of 14 US 10 ,284 ,370 B2
Www AL
aveau YYYYYYY
WWW. MMMMMMMMMMMM ..
SYYYYYYY
VWwww
Figure 13
atent May 7 , 2019 Sheet 14 of 14 US 10 ,284 ,370 B2
Sign M to obtain
AVALUAREA yim
yox
+ + + + + + + + + + + +
Compute
Q = (sír )R - (er)G
SKRAK
Figure 14
YYYYY Confirm
Q = public key of
U UUUUUU
US 10 ,284 , 370 B2
ACCELERATED VERIFICATION OF are the three axiomatic properties defining a group . The
DIGITAL SIGNATURES AND PUBLIC KEYS elliptic curve group has the further property that it is abelian ,
meaning that P + Q = Q + P .
This application is a continuation of and claims priority Scalar multiplication can be defined from addition as
from U . S . patent application Ser. No. 13 /620 ,206 , filed on 5 follows. For any point P and any positive integer d , dP is
Sep . 14, 2012 , which is a continuation of and claims priority defined as P + P + . . . + P , where d occurrences of P occur.
from U .S . patent application Ser. No. 13/478 ,288 , filed on Thus 1P = P and 2P = P + P, and 3P = P + P + P , and so on . We also
May 23 , 2012 , which is a continuation of and claims priority define OP = O and ( - d ) P = d ( - P ).
from U . S . patent application Ser . No . 11 / 333 , 296 , filed on For simplicity , it is preferable to work with an elliptic
Jan . 18 , 2006 , which claims priority from U . S . Provisional 10 curve that is cyclic (defined below ) although in practice ,
Application No. 60 /644,034 filed Jan . 18 , 2005 . All of the sometimes a cyclic subgroup of the elliptic curve is used
priority applications are hereby incorporated by reference . instead . Being cyclic means that there is a generator G ,
The present invention relates to computational techniques which is a point in the group such that every other point P
used in cryptographic algorithms. 15 in the group is a multiple of G , that is to say , P = dG , for some
BACKGROUND TO THE INVENTION positive integer d . The smallest positive integer n such that
nG = 0 is the order of G (and of the curve E , when E is cyclic ).
The security and authenticity of information transferred In cryptographic applications, the elliptic curves are chosen
through data communication systems is of paramount so that n is prime.
importance .Much of the information is of a sensitive nature 20 In an elliptic curve cryptosystem , the analogue to expo
and lack of proper control may result in economic and nentiation is point multiplication . Thus it is a private key is
personal loss. Cryptographic systems have been developed an integer k , the corresponding public key is the point kP,
to address such concerns. where P is a predefined point on the curve that is part of the
Public key cryptography permits the secure communica - system parameters . The seed point P will typically be the
tion over a data communication system without the necessity 25 generator G . The key pair may be used with various cryp
to transfer identical keys to other parties in the information tographic algorithms to establish common keys for encryp
exchange through independent mechanisms, such as a cou - tion and to perform digital signatures . Such algorithms
rier or the like . Public key cryptography is based upon the frequently require the verification of certain operations by
generation of a key pair, one of which is private and the other comparing a pair of values as to confirm a defined relation
public that are related by a one way mathematical function . 30 ship , referred to as the verification equality , between a set of
The one way function is such that, in the underlying math values .
ematical structure, the public key is readily computed from One such algorithm is the Elliptic Curve Digital Signature
the private key but the private key cannot feasibly be Algorithm (ECDSA ) used to generate digital signatures on
ascertained from the public key . messages exchanged between entities . Entities using
One of the more robust one way functions involves 35 ECDSA have two roles, that of a signer and that of a verifier.
exponentiation in a finite field where an integer k is used as A signer selects a long term private key d , which is an
a private key and the generator of the field a is exponenti- integer d between 1 and n - 1 inclusive . The integer d must
ated to provide a public key K = a " . Even though a and K are be secret, so it is generally preferable to choose d at random .
known , the underlying mathematical structure of the finite The signer computes Q = dG . The point Q is the long- term
field makes it infeasible to obtain the private key k . Public 40 public key of the signer, and is made available to the
key cryptography may be used between parties to establish verifiers . Generally , the verifiers will have assurance gener
a common key by both parties exchanging their public keys ally by way of a certificate from a CA, that Q corresponds
and exponentiating the other parties public key with their to the entity who is the signer . Finding the private key d from
private key . Public key cryptography may also be used to the public key Q is believed to an intractable problem for the
digitally sign a message to authenticate the origin of the 45 choices of elliptic curves used today .
message . The author of the message signs the message using For any message M , the signer can create a signature ,
his private key and the authenticity of the message may then which is a pair of integers (r, s ) in the case ECDSA . Any
be verified using the corresponding public key. verifier can take the message M , the public key Q , and the
The security of such systems is dependent to a large part signature (r, s ), and verify whether it was created by the
on the underlying mathematical structure . The most com - 50 corresponding signer. This is because creation of a valid
monly used structure for implementing discrete logarithm signature (r, s) is believed to possible only by an entity who
systems is a cyclic subgroup of a multiplicative group of a knows the private key d corresponding to the public key Q .
finite field in which the group operation is multiplication or The signing process is as follows. First, the signer chooses
cyclic subgroups of elliptic curve groups in which the group some integer k in the interval [ 1, n – 1 ] that is to be used as
operation is addition . 55 a session , or ephemeral, private key . The value k must be
An elliptic curve E is a set of points of the form (x , y ) secret , so generally it is preferable to choose k randomly .
where x and y are in a field F , such as the integers modulo Then , the signer computes a point R = kG that has co
a prime p , commonly referred to as Fp , and x and y satisfy ordinates (x , y ). Next, the signer converts x to an integer x '
a non - singular cubic equation , which can take the form and then computes r = x ' mod n , which is the first coordinate
y = x + ax + b for some a and b in F. The elliptic curve E also 60 of the signature . The signer must also compute the integer
includes a point at infinity , indicated as O . The points of E e = h ( M ) mod n , where h is somehash function , generally one
may be defined in such a way as to form a group . The point of the Secure Hash Algorithms( such as SHA - 1 or SHA - 256 )
O is the identity of the group , so that O + P = P + O = P for any defined in Federal Information Processing Standard (FIPS )
point P in E . For each point P , there is another point, which 180 - 2 . Finally , the second coordinate s is computed as
we will write as – P, such that P + ( - P )= P + (- P ) = 0 . For any 65 s = (e + dr )/s mod n . The components (r, s) are used by the
three points P , Q , R in E , associativity holds , which means signer as the signature of the message , M , and sent with the
that P + ( Q + R )= (P + Q ) + R . Identity, negation and associativity message to the intended recipient.
US 10 ,284 ,370 B2
The verifying process is as follows. First the verifier Tables of multiples of points are notmerely useful during
computes an integer e = h ( M ) mod n from the received pre -computation . In practice , such tables are commonly
message . Then the verifier computes integers u and v such generated at run -time, during an initial phase of each com
that u - els mod n and v = r/s mod n . Next, the verifier putation . The savings provided by these tables is essentially
computes a value corresponding to the point R that is 5 that of avoiding certain repetitious operations that occur
obtained by adding uG + vQ . This has co -ordinates (x , y ). within a single computation . A single computation has less
Finally the verifier converts the field element x to an integer internal repetitions than two distinct computations have in
x ' and checks that r= x ' mod n . If it does the signature is pre common, so that saved repetition amount to less than
verified . -computation . Nevertheless , it has been found that with a
From the above, the verification of an ECDSA signature ture 10 judicious choice of table , the time need for a single com
appears to take twice as long as the creation of an ECDSA putation can be reduced . The table takes time to compute ,
and computation of the table cannot be amortized over
signature, because the verification process involves two multiple computations, so is incurred for every computation .
scalar multiplications, namely ug and vQ , whereas signing Experience has shown that particular tables decrease the
involves only one scalar multiplication , namely kG . Elliptic1615 amount of time needed because computing the table takes
curve scalar multiplications consume most of the time of less time than the repetition operations that would have
these processes, so twice as many of them essentially otherwise been needed . Usually , there is an optimum size
doubles the computation time. Methods are known for and choice of table . Another cost of such tables is the
computing uG + vQ that takes less time than computing ug memory needed to temporarily store the table . The cost of
and VG separately . Some of these methods are attributed to 20 such memory may affect the optimal choice of table . Win
Shamir, some to Solinas , and some to various others . Gen - dowing methods are examples of such tables computed on
erally , these methods mean that computing uG + vQ can take the fly .
1 . 5 times as long as computing KG . Not withstanding all of the above known techniques for
Another commonly used method to accelerate elliptic efficient implementation , further efficiency improvements
curve computations is pre - computing tables of multiples of 25 are desirable . In particular, the efficiency of verifying of
G . Such pre - computed tables save time, because the point G ECDSA signatures is particularly desirable . Extensive pre
is generally a fixed system parameter that is re -used repeat computation allows ECDSA signatures to be generated very
edly . The simplest pre -compute table consists of all mul- quickly.. In fact
fact, ECDSA sisignature generation is one of the
tiples 2 ^;G for j from 0 to t, where t is the bit- length of n . fastest digital signature generation algorithms known . On
With such a pre - computed table , computing an arbitrary 30 the other hand , ECDSA signature verification is relatively
multiple kG can be done with an average of t/2 point slower, and there are other signature algorithmshave similar
additions or less. Roughly , this a threefold improvement verification times to ECDSA . Improvement of ECDSA
over the basic method of computing KG , which clearly verification time is therefore important, especially for envi
demonstrates the benefit of pre - computation . Generally ronments where verification time is a bottleneck . In general,
speaking , larger pre -computed tables yield better time 35 there is a need to enhance the efficiency of performing a
improvements . The memory needed to store the pre -com computation to verify that a value corresponds to the sum of
puted tables has a significant cost. Therefore, implementers two of the values. It is therefore an object of the present
must balance the benefit of faster operations with the extra invention to obviate or mitigate the above disadvantages .
cost of larger tables. The exact balance generally depends of
the relative importance of speed versus memory usage , 40 SUMMARY OF THE INVENTION
which can vary from one implementation to another. Pre
computation can also be applied to the public key Q . In general terms the present invention provides a method
Generally, the public key Q tends to vary more often than G : and apparatus for verifying the equality of a relationship
as it is different for each correspondent, whereas G is always between the sum of scalar multiples of a pair of points on an
fixed for a given system . Therefore the cost of one- time 45 elliptic curve and a third point on said curve . The method
pre - computation for Q is amortized over a smaller number comprises the steps of i ) obtaining a pair of integers of bit
of repeated run - time computations involving Q . Neverthe - length less than one of said scalars and whose ratio corre
less , if Q is to be used more than once , some net savings on sponds to said scalar ; ii) substituting said integers for said
time will be achieved . Public keys that are heavily used scalars in said relationship to obtain an equivalent relation
include those of certification authorities (CA ), especially 50 ship in which at least one of said terms is a scalar multiple
root, trusted or anchor CA public keys (that are pre -installed of one of said points with reduced bit length , and iii )
into a system ). Therefore , pre -computation may be worth - computing said equivalentrelationship to verify said equal
while for CA elliptic curve public keys where , for example , ity .
the protocol requires verification of a CA 's certificate . The method may be used for verifying that a value
Another difference between pre -computations of Q versus G 55 representative of a point R on an elliptic curve corresponds
is the cost of storing or communicating the pre - computed to the sum of two other points , uG and vQ . Integers w and
tables . Each public key Q requires its own pre-computed z are determined such that the bit lengths of the bit strings
table . In a system with many distinct public keys , these costs representing w and z are each less than the bit length of the
may accumulate to the point that any benefit of faster bit string of the integer v , and such that v = w / z mod n . With
computation is offset by the need to store or communicate 60 such w and z , the equation R = uG + VQ can be verified as
keys . The net benefit depends on the relative cost of time, -ZR + ( zu mod n )G +wQ = 0 .
memory and bandwidth , which can vary tremendously Preferably , the bit lengths of w and z are each about half
between implementations and systems. Again , in the case of the bit length of n , which means that both w and z are both
CA public keys , especially root, trusted or anchor CA keys , no larger than about n12
these keys tend to be fewer in number than end -entity public 65 The point -zR + ( zu mod n )G +wQ can be computed effi
keys , so that the cost of pre - computation will generally be ciently because z and w are relatively small integers , and
less and amortised over more operations. various of the methods for computing a sum faster than its
US 10 ,284 , 370 B2
parts can be used . The multiple (zu mod n ) is full size , but FIG . 14 shows a method of recovering a public key from
within the context of an algorithm such as the ECDSA , the an ECDSA signature .
point G may be fixed or recurring . In this case the compu The present invention is exemplified by reference to
tation can be accelerated with the use of a stored table for G . verification of digital signatures, in particular those signa
Estimates of the times savings for this approach compared to 5 tures generated using ECDSA . It will be apparent however
conventional verification with tables for G are around 40 % . that the techniques described are applicable to other algo
The values w and z may be obtained by using a partial rithms in which verification of a pair of values representative
completed extended Euclidean algorithm computation . of points on an elliptic curve is required to groups other than
elliptic curve groups . Therefore the accompanying descrip
Alternatively , a continued fractions approach may be uti 10 tion of the embodiments shown is exemplary and not
lised to obtain w and z efficiently. exhaustive.
In a further aspect of the invention there is provided a Referring therefore to FIG . 1 , a data communication
method of verifying a digital signature of a message per system 10 includes a pair of correspondents 12 , 14 inter
formed by a cryptographic operation in a group of a finite connected by a transmission line 16 . The correspondents 12 ,
field having elements represented by bit strings of defined 15 14 each include
maximum bit length . The signature comprises a pair of that are operablecryptographic modules 20 , 22 respectively
to implement one of a number of crypto
components , one of which is derived from an ephemeral graphic functions. The modules 20 , 22 are each controlled
public key of a signer and the other of which combines the by CPU ' s incorporated in the correspondents 12 , 14 and
message , the first component and the ephemeral public key interfacing between input devices , such as a keyboard 24 , a
and a long term public key of the signer. The method 20 display device 26 , such as a screen and a memory 28 . Each
comprises the steps of recovering the ephemeral public key cryptographic module includes internal processing capabil
from the first component, establishing a verification equality ity including a random number generator 30 and an arith
as a combination of group operations on the ephemeral metic processor 32 for performing elliptic curve computa
public key, the long term public key and a generator of the tions such as point addition . It will be appreciated that the
group with at least one of the group operations involving an 25 correspondents 12 , 14 may be general purpose computers
operand represented by bit strings having a reduced bit connected in a network or specialised devices such as cell
length less than the defined maximum bit length , computing phones, pagers , PDA 's or the like . The communication link
the combination and accepting the signature if said equality 16 may be a land line or wireless or a combination thereof.
holds and rejecting the signature if said equality fails . Similarly the cryptographic modules 20 , 22 may be imple
Preferably , the group is a elliptic curve group . As a further 30 mented as separate modules or incorporated as an applica
aspect, a method of generating a signature of a message by tion within the CPU .
a cryptographic operation in an elliptic curve group of finite In the present example , the correspondent 12 prepares a
field comprising the steps of generating a pair of signature message M which it wishes to sign and send to the corre
components with one of said components derived from a spondent 14 using an elliptic curve cryptosystem embodied
point representing an ephemeral public key and including in 35 within the modules 20 , 22 . The parameters of the system are
said signature an indicator to identify one of a plurality of known to each party including the field over which the curve
possible values of said public key that may be recovered is defined in the presentexample Fp where p is a prime), the
from said one component. underlying curve , E , the generator point G that generates the
Embodiments of the invention will now be described by elements that form the group in which crypto operations are
way of example only with reference to the accompanying 40 performed and therefore defines the order, n , of the group ,
drawings in which : and a secure hash function H , generally one of the Secure
FIG . 1 is a schematic representation of a data communi - Hash Algorithms (such as SHA - 1 or SHA - 256 ) defined in
cation system , Federal Information Processing Standard (FIPS) 180 -2 .
FIG . 2 is a flow chart illustrating the steps in performing Each element is represented as a bit string having a maxi
a signature for an ECDSA signature scheme. 45 mum bit length sufficient to represent each element in the
FIG . 3 is a flow chart showing the verification of a group.
ECDSA signature . The steps taken to sign the message are shown in FIG . 2 .
FIG . 4 is a flow chart showing the verification of an Initially therefore the correspondent generates an integer k
ECDSA signature using a precomputed value. by the random number generator 30 and utilises the arith
FIG . 5 is a flow chart showing the verification of an 50 metic unit 32 to compute a point R = kG that has co -ordinates
ECDSA signature using a table of precomputed values . ( x , y ). The correspondent 12 converts the co - ordinate x to an
FIG . 6 is a flow chart showing the verification of an integer x ' and computes rex' mod n , which is the first
ECDSA signature using a precomputed value provided by component of the signature . The correspondent 12 also
the signer computes the integer e = H (M ) mod n , where H is the secure
FIG . 7 is a flow chart showing steps taken by a verifier 55 hash function . Finally, the second component s is computed
upon failing to verify . as s = ( e + dr )/k mod n .
FIG . 8 is a flow chart showing steps taken by a signor to In addition to the components r and s, the signature
simplify verification . includes information i to permit the co -ordinates represent
FIG . 9 is a flow chart showing an alternative signature ing the point R to be recovered from the component r. This
protocol to simplify verification 60 information may be embedded in the message M , or for
FIG . 10 is a flow chart showing an alternative technique warded as a separate component with r and s and will be
performed by the signor to simply verification. used by the verifier to compute the value R . If the elliptic
FIG . 11 is a flow chart showing an alternative verification curve is defined over a field F of prime order p , and the
ECDSA . elliptic curve E is cyclic or prime order n , then i can
FIG . 12 is a flow chart showing point verification . 65 generally be taken as y mod 2 , i.e ., a zero or one . The
FIG . 13 is a flow chart showing a modified PVS verifi indication i is required during recovery R , where the verifier
cation protocol. sets x = r. It is very likely that x = r because n and p are
US 10 ,284 , 370 B2
extremely close for typical implementations. Given x , there arithmetic unit 32 as needed . The representations of the
are exactly two values y such that (x , y ) is on the curve , and points - ZR and wQ which cannot effectively be precom
these two values y and y ' have different values mod 2 . Thus puted have smaller bit lengths and therefore less time
i is just a single bit whose value indicates which of the y ' s consuming computation . Assuming the computation returns
is to be used , and adds relatively little cost to the signature . 5 a value 0 , the signature is assumed to be verified .
Once the message is signed it is forwarded together with A number of different known techniques may be utilised
the components r,s, and i across the link 16 to the recipient to compute the required relationship , each of which may be
correspondent 14 . To verify the signature the steps set out in implemented using the arithmetic processor 32 . Each offers
FIG . 3 are performed . First the correspondent 14 computes different advantages, either in speed or computing resources ,
an integer e = H ( M ) mod n . Then the correspondent utilises 10 and so the technique or combination of techniques will
the arithmetic unit 32 to compute a pair of integers u and v depend to a certain extent on the environment in which the
such that u els mod n and v = r/ s mod n . communication system is operating. For the sake of com
The correspondent 14 also computes a pair of integers w parison , it will be assumed that u and v are integers of bit
and z using an iterative algorithm such that the maximum bit length t. Computing uG and vQ separately requires about
lengths of w and z are each less than the maximum bit length 15 3t/ 2 point operations, assuming no pre - computation , for a
of the elements of the group , and such that v = w /z mod n . The total of about 3t point operations. Computing uG + vQ , which
bit lengths of w and z are preferably about one half the bit is the verification normally used for ECDSA , require t
length of the elements . Such w and z can be found conve - doublings , some of which can be simultaneous . Each of u
niently with the extended Euclidean algorithm and stopping and v are expected to have about t/ 2 bits set to one in their
at an appropriate point, typically half-way where w and v are 20 binary representation . In basic binary scalar multiplication ,
half the bit length of the elements . Such an algorithm is each bit of one requires another addition . (In more advanced
exemplified , for example as Algorithm 3 .74 in Guide to scalar multiplication , signed binary expansion are used , and
Elliptic Curve Cryptography by Henkerson , Menezes and the average number of additions is t/3 .) The total number of
Vanstone published by Springer under ISBN 0 - 387 - 95273, point operations is therefore t + (2 (t / 2 )) = 2t on average as
which represents a quantity k as k = k , + k mod n , where the 25 simultaneous doubling has saved t doublings. ) The revised
bit lengths of k , and k , are about half the length of n . This verification instead uses a computation of a combination of
equation can be re -written as 2 = (k - k )/k , mod n . By setting the form aG + wQ + zR , where a is an integer of bit length t
k = 1 and À = v , then the above referenced Algorithm 3 .74 can representative of the value zu mod n and w and z are integers
be used to obtain n established for the system , k set to 1 and of bit length about (t/ 2 ). Organising the verification com
the value for v used as the variable input. The output 30 putation in this way permits a number of efficient techniques
obtained k , k2 can then be used to compute w = 1 - k , and k2 to be used to reduce the number of point operations. An
used as w = 1 - k , and z = k ) . efficient way to compute this is to use a simultaneous
Thus, the arithmetic unit 32 is used to implement the doubling and add algorithm . For example , if the relationship
following pseudo -code to obtain the values of w and z . 15G + 200 + 13R is to be computed it can be done in stages as
Let 70 = n and 10 = 0 . 2Q ; G + 2Q ; G + 2Q + R ; 2G + 4Q + 2R ; 3G + 4Q + 2R ; 3G + 5Q +
2R ; 3G +5Q + 3R ; 6G + 10Q +6R ; 7G + 10Q + 6R ; 14G + 20Q +
Let rl = v and t1 = 1. 12R ; 15G + 20Q + 13R , for a total of 12 point additions, which
is fewer than the method of generic scalar multiplication for
For i> 1 , determine ri, ti as follows: each term separately . The main way that this method uses
Use the division algorithm to write r_ (i - 1) = qi r _ (1 - 2 ) + ri, 40 less operations is when it does simultaneous doubling, in
which defines ri. steps as going from G + 2Q + R to 2G +4Q + 2R . In computing
each term separately three operations would be used corre
Let ti = t_ (i- 1)+ qi t_ (- 2 ). sponding to this one operation . In fact, three simultaneous
Stop as soon as ri < sqrt(n )= n ^ (1/2), or some other desired doubling were used , each saving two operations, so simul
size. Set w = ri and z = ti . Note that ri = ti v mod n , so w = Z V 45 taneous doubling account precisely for all the savings . The
mod n , so v = w / z mod n , and both w and z have about half number of doublings to compute the combination is gov
the bit length of n , as desired . erned by the length of the highest multiple, so it is t. The
The correspondent 14 also recovers a value corresponding number of additions for a is (t/ 2 ), on average , and for Q and
to the point R utilising the information i. In its simplest form R it is (t/4 ) each on average . The total, on average , is
this is obtained by substituting the value of r received in the 50 t + (t/2 ) + (t/4 ) + (t/ 4 ) = 2t. The algorithm is further exemplified
curve and determining which of the two possible values of as Algorithm 3.48 of the Guide to Elliptic Curve Cryptog
y correspond to the sign indicated by the bit i. raphy detailed above .
With the value of R recovered , the verification of the Although there does not appear to be any savings over the
ECDSA , namely that R = uG + vQ , may proceed with a previous method , which also took 2t point operations,
revised verification by confirming that the verification equal- 55 advantage can be taken of the fact that in practice , for
ity - zR + (zu mod n )G +wQ = 0 . The verification equality ECDSA , the generator G is constant. This allows the point
- ZR + (zu mod n )G +wQ involves a combination of group J = 2 ^ m G to be computed in advance , and stored in memory
operations on each of the ephemeral public key R , generator 28 for future use . Ifm is chosen to be approximately t/ 2 , then
G and long -term public key Q and can be computed effi - a a ' + a" 2 ^ m , where a ' and all are integers of bit length about
ciently because z and w are relatively small integers. As will 60 (t/ 2 ). Accordingly , aG + wQ + zR can be written as a'G + a " J +
be described below , various of the methods for computing a WQ + ZR . In this form , all the scalar multiples have bit length
sum faster than its parts can be used . The multiple (zu mod (t/2 ). The total number of doublings is thus (t/ 2 ). Each of the
n ) is full size , but within the context of a system such as the four terms contributes on average (t/4 ) additions . The total
ECDSA in which the points have varying longevity , the number of point operations, on average , is the t/2 + 4 (t/4 )
point G may be considered fixed or recurring . In this case the 65 = 3t/2 .
computation can be accelerated with a precomputed table for Accordingly , to verify the signature r,s, as shown sche
G , which may be stored in the memory 28 and accessed by matically in FIG . 4 , the recipient computes w , and z as
US 10 ,284 , 370 B2
10
described above, determines the value of a' and a " and Upon receipt, the verifier computes w and z . The verifier
performs a double and add computation to obtain the value then determines c = c'+ c" B and b = b ' + b " B + b '" B ^2 . In addition ,
of the verification representation . If this corresponds to the since G is a fixed parameter , the verifier has pre- computed
group identity , the verification is confirmed . multiples of G of the form BG and ß ^ 2G . If n is approxi
With the conventional verification equation approach of 5 mately 2 t, then the verifier needs just t/3 simultaneous
computing uG + vQ , the multiple v will generally be full doubles to compute aR + bG + CQ . The verification can pro
length t, so the pre -computed multiple J of G will not help ceed on the basis aR + (b '+ b " B + b '" B ^ 2 )G + (c'+ c" B ) Q = 0 . The
reduce the number of simultaneous doublings . precomputed values for G and Q can then be used and the
Therefore , by pre -computing and storing the single point verification performed . The verifier will need 2t/3 point
J , verifying using the relationship - R + (zumod n )G +wQ = 0 " additions, assuming that signed NAF is used to represent a ,
allows an ECDSA signature to be verified in 25 % less time. b and c . The total number of point operations is thus t, which
In other words , 33 % more signatures can be verified in a represents a further significant savings compared to 3t/ 2
given amount of time using the embodiment described with the present invention and without the pre -computed
above . 1
15 multiple of such as described in FIG . 4 and compared to
Alternatively , many implementations have sufficient 2t using the conventional representations and without any
memory 32 to pre - compute and store essentially all power of pre -computed multiple of Q .
two multiples of G , essentially making it unnecessary to Given a pre - computed multiple of both Q and G , then
apply doubling operations to G . In such situations uG +vQ u G + vQ can be computed with (t/2 )+ 4 (t/ 4 ) = 3t/2 point opera
can be computed with t doublings of Q and (t/2 ) additions 20 tions using conventional representations. When pre -com
for each of G and Q . The total is still 2t operations. However, puted multiples of Q are feasible , then the signing equation ,
as shown in FIG . 5 , the value of a can be retrieved from in the form above, again provide a significant benefit . The
the precomputed table stored in memory 32 so that com - analyses above would be slightly modified when signed
puting aG +wQ + zR , can be attained with (t/ 2 ) doublings for binary expansions are used .
the wQ and zR , no doublings for G , t/2 additions for G , and 25 With yet other known advanced techniques for computing
t/4 additions for each of Q and R . The total is 3t/2 operations. linear combinations of points, some of which are discussed
The savings are the same as described with FIG . 4 , when below , the use of the relationship allows signature verifica
only one multiple of G was pre - computed and stored . When tion to take up to 40 % less time.
signed binary expansions are used , then computing uG + vQ When implementing scalar multiplication and combina
(without any pre - computation ) requires about t doublings 30 tions, it is common to build a table at run -time of certain
and ( t/ 3 ) additions for each of G and Q , for a total of ( 10 /6t multiples . These tables allow signed bits in the representa
operations, on average . When signed binary expansions are tion of scalar multiple to be processed in groups, usually
used to find a'G + a " J +wQ +zR , about t/ 2 doublings are called windows. The table costs time and memory to build ,
needed , and (t/6 ) additions for each of G , J, Q and R , for a but then accelerates the rest of the computation . Normally ,
total of ( 7 / 6 t operations, on average . The time to verify 35 the size of the table and associated window are optimized for
using the verification representation described above is 70 % overall performance , which usually means to minimize the
compared to without, or 30 % less. This allows about 42 % time taken , except on some hardware implementation where
more signatures to verified in a given amount of time. The memory is more critical. A full description and implement
advantage of verifying using the revised verification repre - ing algorithms for such techniques is to be found in Guide
sentation is increased when combined with a more advanced 40 to Elliptic Curve Cryptography , referenced above at pages
technique of scalar multiplication referred to as signed 98 et . seq .
binary expansions. This technique is very commonly used Such run -time tables, or windowing techniques , for scalar
today in elliptic curve cryptography, so today 's existing multiplication techniques can be combined with the revised
implementations stand to benefit from adoption of the veri verification equation in the embodiments described above.
fication representations. 45 When using such tables , the savings are approximately the
Accordingly, it will be seen that by reorganizing the same as outlined above . The reason the savings are similar
verification equation so that signature variables have a is the following simple fact. Tables reduce the number of
reduced bit length , the speed of verification may be adds, by pre -computing certain patterns of additions that are
increased significantly. likely occur repeatedly , whereas the use of the revised
In the above embodiments , the recipient performs com - 50 verification relationship reduces the number of doubles by
putations on the components r,s . To further accelerate sig - providing for more simultaneous doubling. In fact, when
nature verification as shown in FIG . 6 , a signer may provide using tables, the number of adds is reduced , so the further
a pre - computed multiple of the public key Q to the verifier. reduction of the doubles provided by using the revised
The verifier can use the pre - computed multiple to further verification relationship has even more impact.
accelerate verification with Q . In this embodiment the veri- 55 By way of an example, a common approach to tables , is
fier determines an equivalent equation to the ECDSA veri- to use a signed NAF window of size 5 . Building a table for
fication equation in the form aR + bG + Q = 0 , where a is such a NAF requires 11 adds. In the example above where
approximately n '' and represents - z , b is approximately n the signer sends a pre - computed multiple uQ of Q , the
and represents –zu mod n , and c is approximately n23 and verifier can build tables for R , Q and uQ , at a cost of 33 adds.
represents w . This can be done using the extended Euclidean 60 It is presumed that verifier already has the necessary tables
algorithm as described above and stopping when the bit built for G . Using the pre - computed doubles, the verifier
length of w is twice that of z . Again , therefore, the signor only needs t/6 simultaneous additions for verification . These
signs the message M and generates the signature compo - savings improve as the key size increases . For the largest key
nents r,s . It also includes the identifier i in the message size in use today , the savings are in the order of 40 % . Such
forwarded to the verifier . The signor pre - computes a mul- 65 tables do of course require the necessary memory 32 and so
tiple BQ where the scalar multiple B is a power of two selection of the appropriate techniques is governed by the
nearest to n and forwards it with the signature . hardware available .
US 10 ,284 ,370 B2
12
Similarly, computation techniques known as joint sparse of a normal verify . Furthermore , as outlined further below ,
forms could be used for computational efficiency. the signer can assist by providing m for the verifier or by
As described above , the integers w , z were found using the doing the extra work of trying both values to ensure that only
extended Euclidean algorithm . Alternative iterative algo - one m is valid .
rithms may be used , including the continued fractions 5 A similar method may be utilized with a cofactor h = 4 . In
approach . In the continued fractions approach , which is fact, a higher value of h reduces the probability of each of
essentially equivalent to the extended Euclidean algorithm , the potential x values from being valid . There are more
one finds a partial convergent yld to the fraction v /n , such potential x values, but the analysis shows a similar benefit to
that d is approximately n12. A property of the partial the verifier. There are three false values of x , and each has
convergent is that ly / d - v /nl< 1 / 8 2 . Multiplying this inequal- 10 a probability of 1/8 of appearing valid with a fast check . The
ity by Sn gives lyn - vd < n / d , which is approximately n12 . chance that no false values appear to be a valid x with a fast
Now set z = d and w = yn - vd. It is easy to check that v = w /z check is thus (7/8)3 which is about 77 % .Most of the remain
mod n , and note that w and z have the desired size . ing 23 % of the time, justone of the false x values will appear
As noted above, a conventional ECDSA signature, does valid and potentially require a full signature verification .
not include the point R but instead , it includes an integer x ' 15 The inclusion of i ( and of m if necessary ) is quite similar
obtained from r = x mod n , where R = ( x , y ) . The verifier to replacing r by a compressed version of R consisting of the
therefore needs to recover R . x coordinate and the first hit of the y coordinate. This
The method to recover R discussed above is to supple- alternative , of sending a compressed value of R instead of r,
ment the signature (r, s ) with additional information i. This has the advantage of being somewhat simpler and not even
information can be embedded in the message , for example . 20 a negligible chance of false recovery . Accordingly , as shown
The verifier can use r and i to compute R . When p > n , there in FIG . 9 , the signature is computed to provide a pair of
is a negligible chance that x ' > n and consequently r= x - n . If components , r ', s and forwarded with the message M to the
however such a case does occur, the verification attemptwill recipient 14 . The component r is composed of the x co
fail. Such a negligible failure rate for valid signatures can be ordinate of the point R and the first bit of the y co -ordinate .
accepted , or dealt with in the following manner. 25 The component s is computed as before .
As shown in FIG . 7 , upon failure of the verification , at the To verify the signature , the recipient 14 recovers the point
verifier 's expense the verifier can try x = r + n , and repeat the R directly from the component r' and uses the verification
verification for another value of R , which will succeed in equality equation - zR + ( zu mod n )G + wQ = 0 to confirm it
this particular case . Continued failure to verify will lead to corresponds to the group identity . The transmission of the
rejection of the signature . Alternatively , as shown in FIG . 8 30 modified co - ordinate r simplifies the verification but does
the signer can detect when x > n , which should happen increase the bandwidth required .
negligibly often , and when this happens generate a different In some situations, no channel may be available for the
k and R . In either of the approaches , the problem arises so signer to send extra bits. For example , existing standards
rarely that there is negligible impact on performance . may strictly limit both the signature format and the message
Other techniques for determining R can be utilized . In 35 format leaving no room for the sender to provide additional
non -cyclic curves , there is a cofactor h , which is usually 2 information . Signers and verifiers can nevertheless coordi
or 4 in practice . This can lead to multiple possible values of nate their implementations so that R is recoverable from r.
x . The probability that r = x is approximately 1/h . In other This can be arranged by the signer, as shown in FIG . 10 , by
situations , we will generally have r = x - n ( if h = 2 ) , or more ensuring that the value of x conforms to prearranged criteria .
generally r = x - mn where (m is between 0 and h - 1 ) . Because 40 In the notation above, the signer will compute R = G = ( x , y )
p is approximately hn , then except in a negligible portion of as normal, and then in notation above compute i = y mod 2 .
cases there will be h possible values of x that are associated If i= 1 , the signer will change k to - k mod n , so that R
with r. To make recovery of x , and hence R easier, the signer changes to - R = ( x , - y ) and i changes to 0 . When the verifier
can compute m and send it to the verifier within the message receives the signature, the verifier presumes that i = 0 , and
or as a further signature component. Alternatively, the 45 thus recovers the signature . The value of i is thus conveyed
verifier can make an educated guess for m . This can be implicitly as the value 0 , and the signer has almost negligible
illustrated in the case of h = 2 . cost for arranging this . Similarly , in non -cyclic elliptic
Corresponding to r is a correct x and a false value X . The curves , the signer may try to transmit m implicitly , which to
false value x , has an approximately 1/2 chance of not corre - some extent has already been described . In the case of h = 2 ,
sponding to a value of the x - coordinate on E , and a further 50 recall that the 1/4 of the time, the verifier may need to verify
1 /h chance of not corresponding to a multiple of G . If one two signatures . Instead of the verifier doing this extra work ,
of the two values for x is invalid , either by not being on E the signer can detect this 1/4 case , and try another value for
or if it is not having order n , both of which can be efficiently k and R instead , repeating the process until one is found that
checked , then that value can be eliminated . Thus at least 3/4 conforms to the criteria . The verifier can determine which
of the time, the verifier will easily find the correct x . The 55 value of x to use without verifying two signatures .
remaining 1/4 of the time at maximum , the verifier will not As an alternative to modifying R as described above , and
know which of the two X -values to try . If the verifier can to maintain strict conformity to the ECDSA standard , the
guess one of the x values to verify , half the time, this guess value of s may be modified after computation rather than R .
will be right and the signature will verify , and the other half In this case , the signer notes that the value of R does not
of the time, the first signature attempt will fail and the 60 conform to the prearranged criteria and proceeds to generate
verifiermust try the other x value . Therefore the probability r and s as usual. After s is computed , the value is changed
that the verifier must verify two signatures is 1/8. Despite this to ( - s ) to ensure the verification will be attained with the
probability of two verifications, the average verification is presumption of the prearranged value of y . When a signer
still improved . This can still provide the verifier time savings chooses a signature ( r, s ) such that R is implicitly recovered ,
on average. If an accelerated verification takes 70 % as long 65 an ordinary verifier will accept the signature as usual. Such
as a normal verify , but 12 . 5 % of the verifies require twice as s ignatures are perfectly valid . In other words , the revised
long as an accelerated verify, then the average time is 79 % verification is perfectly compatible with existing implemen
US 10 ,284 , 370 B2
13 14
tations of ECDSA verification . An accelerated verifier can be computed as d ' G + d " H , where d = d '+ d " u mod n , with
expecting an implicitly efficient signature but receiving a roughly the same cost as above .
normally generated signature , will need to try two different Another application is implicit certificate verification .
values of i. If accelerated verification takes 60 % of the time Implicit certificates are pairs (P, I), where P is an elliptic
of a normal verify , then in a cyclic curve ( cofactor h = 1 ), the 5 curve point and I is some identity string . An entity Bob
average time to needed verify a normal signature is 50 % obtains an implicit certificate from a CA by sending a
(60 % )+ 50 % ( 120 % )= 90 % of a normal verify . This because request value R which is an elliptic curve point to the CA .
50 % of the time a normal signature will have i= 0 , requiring The CA returns the implicit certificate ( P, I) and in addition
just one implicitly accelerated verify, and the other 50 % of a private key reconstruction data value s . Bob can use s to
the time, two accelerated verifies are needed . Thus an " calculate his private key . More generally , any entity can use
implicitly accelerated verify will still be faster than a normal s to verify that the implicit certificate correctly corresponds
verifier, even when the signatures are not implicitly accel- to Bob ' s request value R and the CA public key C . This is
erated . Conventional signatures may also be modified , either done by checking the verification equality H (P , IR + SG = H
by the signer or by a third party , to permit fast verification . 1 ( P . 1) P + C , where H is a hash function . This equation is
In this case the signature is forwarded by a requestor to a equivalent to eQ + sG = C , where e = H (P , I) and Q = R - P . The
third party who verifies the signature using the verification form of this equation is highly similar to the form of the
equality . In so doing the value of R is recovered . The standard ECDSA verification equation . Consequently, the
signature is modified to include the indicator I and returned techniques discussed above may be used to provide a means
to the requestor. The modified signature may then be used in 20 to accelerate verification of this equation . This is done
subsequent exchanges with recipients expecting fast verify optimally by determining relatively smaller values w and z
signatures . such that e = w /z mod n , then multiplying the equation
The above techniques recover R to permit a revised through by z to give: WQ + (sz mod n )G - zC = 0 . Again , the
verification using the relationship - R + ( zu mod n )G + multiple of G is this equation is full size , but generally
WQ = 0 . However, where the ECDSA is being verified , the 25 multiples of G can be pre - computed , so this does not
integers w and z may be used without recovery of R as represent a problem .
shown in FIG . 11. It is possible to compute the x coordinate Another variant that takes advantage of this technique is
of zR and the x coordinate of the point wQ + ( zu mod n )G , to shorten all three multiples in the ECDSA signing equa
and then check the equality of these two X - coordinates . Only tion . Theoretically , each multiple can be shortened to a
the x - coordinate of the point ZR can be computed , as it is not 30 length which is 2 /3 the length of n (where n is the order of G ).
possible to compute the y -coordinate zR directly without One way to achieve this shortening is by solving the short
knowing the y - coordinate of R . However, there are several vector lattice problem in 3 dimensions. Algorithms exist for
known methods to compute the x - coordinate of zR from the solving such problems. Shortening all three multiples is
x -coordinate of R without needing the y coordinate of R . most useful when no pre -computed multiples of G can be
Such techniques include Montgomery ' s method set out on 35 stored , which makes it more efficient to reduce the length of
page 102 of the Guide to Elliptic Curve Cryptography the multiple of G as much as possible . Such techniques are
identified above. It is then sufficient to check the x -coordi described more fully in Henri Cohen , “ A Course in Com
nates of zR and wQ + ( zu mod n ) , because equality of the putational Algebraic Number Theory ” , Springer, ISBN
X -coordinates means that wQ + (zu mod nG equal zR or - zR , 0 - 387 - 55640 -0 . Sections 2 .6 and 2 .6 describe the LLL
which means w /z Q + u G equals R or - R , which means 40 algorithm , its application to finding short vectors in lattices ,
G + vQ has the same x - coordinate as R . This is the condition and also mentions Vallee 's special algorithm for 3 dimen
for successful ECDSA validation . One recovers the x - coor - sional lattices .
dinate of R from the signature component r using the Another application of this technique is the application to
methods discussed above . The advantage of this approach is a modified version of the Pintsov - Vanstone Signature
that it does not require extra work to recover the y - coordi- 45 scheme (PVS ) with partial message recovery . A PVS signa
nate . A disadvantage , compared to the previous methods ture is of a triple (r, s, t ). Verification of a signature and
above , is that the zR has to be computed separately from message recovery from a signature under public Q , with
WQ + (zu mod n ) G meaning that some of the savings of the base generator G , is done as follows. The verifier computes
joint sum are not achieved . e = H (r||t), where H is a hash function . The verifier then
The above examples have verified a signature between a 50 computes R = sG + eQ . Next, the verifier derives a symmetric
pair of correspondents 12 , 14 . The technique may also be encryption key K from R . With this, the verifier decrypts r
used to verify an elliptic curve key pair (d , Q ) as shown in using K to obtain a recovered message part u . The recovered
FIG . 12 . To verify the key pair means to check that Q = dG . message is some combination of t and u . The signature is
This may be important when the key pair is provided by a valid only if u contains someredundancy, which is checked
third party under secure conditions to ensure no tampering 55 by verifying that u conforms to some pre -determined format.
has occurred . If t is the bit length of d , then computing dG The PVS scheme is part of draft standards IEEE P1363a and
with the binary method take ( 3t/2 ) operations on average. In ANSI X9. 92 .
the present embodiment, one of the correspondents, 12 , 14 In a modified variant of PVS, verification time can be
generates a random integer d and obtains a pair of integers decreased by utilizing integers w and z . The modified variant
W , z such that d = w /z mod n . Typically the integers w , z are 60 of PVS is shown in FIG . 13 and proceeds as follows. After
each of half the of length d . Then the correspondent com - computing e as usual, the verifier then finds w and z are
putes zQ -wG , and checks that the result is the group identify length half that of n such that e = w / z mod n , where n is the
0 . Computing zQ -wG takes t operations on average so a order of the point G . The verifier then computes R = ( zs mod
saving of 50 % is obtained . This has the most advantage in n ) G +WQ, and proceeds as before , so deriving a key from R
environments where storing a pre - computed multiple of G is 65 and then decrypting r with the key , and then verifying that
too expensive . As an alternative where limited memory is the decryption has the correct form . This form of verification
available , given a pre- computed multiple H = uG , then dG is more efficient because the multiple of Q is smaller.
US 10 ,284 , 370 B2
15
A method to further accelerate signature verification of these methods, then the public key Q can be recovered as
digital signature, in elliptic curve groups and similar groups follows. The standard ECDSA verification equation is R = (el
is illustrated as follows. The verification of an ECDSA s )G + (r/s) Q , where e = H (M ) is the hash of the message .
signature is essentially equivalent to confirmation that a Given R and this equation , solving for Q is done by Q = (s/r )
linear combination , such as aR + bQ + cG , of three elliptic 5 R - ( e /r ) G .
curve points , equals the point of infinity . One way to verify However, since with a significant probability a pair (r, s )
this condition is to compute the point aR +bQ + CG and then will yield some valid public key, the correspondent 14 needs
check if the result is the point o at infinity , which is the a way to check that is correspondent's 12 public key .
identity element of the group as described above . This Correspondent 12 can make available to correspondent 14
verification can sometimes be done more quickly than by 10 the signature , such as another ECDSA signature (r', s '), from
directly computing the entire sum . For example , if a = b = c , a CA on correspondent 14 public key . Correspondent 12 can
then aR + bQ + cG = 0 if and only if the points R , Q and G are send the CA signature , (r', s'), to correspondent 14 , or
collinear. Checking if points are collinear is considerably correspondent 14 can look it up in some database . The CA ' s
faster than adding to elliptic curve points . Collinearity can signature will be on correspondent' s 12 name and her public
be checked with just two field multiplication, by the equa - 15 key Q . Correspondent 14 will use the CA ' s certificate to
tion (xr - xG )(yo - yG) - (x , -86) (yr - YG )- 0 . Adding points verify the message which corresponds to the public key Q .
requires at least two field multiplication , a field squaring and If the signature verifies then the correspondent 14 has
a field inversion , which is generally equivalent to about 8 recovered the correct value for the public key Q . Omitting
field multiplication . When a = b = c , verification is thus pos - the public key from the certificate can save on bandwidth
sible in about 18 % of the time taken by adding the points . 20 and storage and the verification process described above
As such , this technique may be used as a preliminary step of yields reduced verification times .
the verification process where the likelihood of these con - Correspondent 14 could also verify that Q is correspon
ditions existing is present. dent' s 12 public key by checking Q against some more
Similarly, when b = c = 0 , so that one wishes to verify that compact value derived from Q , such as the half of the bits
aR = 0 , in principle one does not need to compute aR in its 25 of Q . The compact version of a could then stored or
entirety . Instead one could evaluate the ath division polyno - communicated instead of Q , again savings on storage and
mial at the point R . The division polynomial essentially bandwidth .
corresponds to a recursive formula for the denominators of H will also be appreciated that each of the values used in
coordinates the point aR , when expressed as rational func - the verification equality are public values . Accordingly ,
tions of the coordinates of the point R . It is known that aR = 0 30 where limited computing power is available at the verifier it
if and only if the denominator is zero . Furthermore , when is possible for the signer to compute the values of w and z
b = = 0 and the elliptic curve group is cyclic of prime order and forward them with R as part of the message . The
n , it is known that aR = 0 only if a = 0 mod n or if R = 0 . This recipient then does not need to recover R or compute w and
verification is comparably instantaneous, in that zero elliptic z but can perform the verification with the information
curve point operations are needed . When the cofactor is 35 available . The verification is accelerated but the bandwidth
small, such as h = 2 or h = 4 , point operations can replaced by increased .
a few very fast field operations. Thus special cases of Although the descriptions above were for elliptic curve
verification that a sum points is zero can be done very groups, many of the methods described in the present
quickly . invention applies more generally to any group used in
Recursive formula exist, similar to the recursive formulae 40 cryptography , and furthermore to any other application that
for division polynomials , for the denominators of sums like uses exponentiation of group elements . For example, the
aR + bQ + cG , and these can be compute more quickly than the present invention may be used when the group is a genus 2
computing the full value of the point aR +bQ + cG . Knowl- hyperelliptic curve, which have recently been proposed as an
edge of the group order n can further improve verification alternative to elliptic curve groups. The above techniques
time. 45 may also be used to accelerate the verification of the Digital
Yet another application of this technique is to provide Signature Algorithm (DSA ), which is an analogue of the
efficient recovery of the public key Q from only the ECDSA ECDSA . Like ECDSA , a DSA signature consists of a pair of
digital signature as shown in FIG . 14 . Suppose that one integers (r, s ), and r is obtained from an element R of the
correspondent 12 signs a messageMwith signature ( r, s ) and DSA group . The DSA group is defined to be a subgroup of
wishes to send the signed message to the correspondent 14 . 50 the multiplicative group of finite field . Unlike ECDSA ,
Normally correspondent 14 will send M and (r, s ) to the however, recovery of R from r is not easy to achieve, even
correspondent, and will also often send the public key Q . If with the help of a few additional bits . Therefore , the present
correspondent 12 did not send her public key, then normally technique applies most easily to DSA if the value is R sent
correspondent 14 will look up her public key up in some with as part of the signed message, or as additional part of
database , which could stored locally or remotely via some 55 the signature , or as a replacement for the value r. Typically ,
network . To avoid this, it would be beneficial to be able to the integer r is represented with 20 bytes, but the value R is
recover the public key from the signature. Given an represented with 128 bytes . As a result , the combined
ordinary ECDSA signature (r, s ), one can recover several signature and message length is about 108 bytes longer . This
candidate points Q that could potentially be the public key could be a small price to pay to accelerate verification by
The first step is recover the point R . Several methods have 60 33 % , however. In the DSA setup , p is a large prime, and q
already been described for finding R in the context of is smaller prime and q is a divisor of (p - 1 ). An integer g is
accelerated verification , such as : by inclusion of extra infor- chosen such that gºq = 1 mod p , and 1 < g < p . (Note that q and
mation with the signature; by inclusion of extra information g correspond to n and G , respectively, from ECDSA .)
in the message signed ; by extra work on the signer 's part to The private key of the signer is some integer x and the
ensure one valid R can correspond to r; and by extra work 65 public key is Y = g ‘x mod p .
on the verifier ' s part of trying a multiplicity of different R The signer generates a signature in the form (R $ ) instead
values corresponding to r. Once R is recovered by one of of the usual (r, s). Here, R = g?k mod p , whereas, r - R mod q .
US 10 ,284 , 370 B2
17 18
In both cases, s = k ^ ( - 1 ) (h (M ) + x r ) mod q, where x is the 3. Themethod ofclaim 1 ,wherein the elliptic curve point
private key of the signer, M is the message being signed , and R is generated based on the first signature component r and
h is the hash function being used to digest the message (as a cofactor h for an elliptic curve that includes the elliptic
in ECDSA ). curve point R and the elliptic curve point Q .
In normal DSA , the verifier verifies signature (r, s ) by 5 4 . The method of claim 1 , wherein the public key of the
computing u = h ( M )/ s mod q and v = r /s mod q ,much like the signer can be used to verify the signature .
u and v in ECDSA embodiments, and then checks that 5 . Themethod of claim 4 , wherein verifying the signature
r = ( g ‘ u Y v mod p ) mod q . comprises verifying the signature according to an Elliptic
In this embodiment, the verifier finds w and z ofbit length Curve Digital Signature Algorithm (ECDSA ).
about half that of q , so that each of w and z is approximately 10 6 . A non -transitory computer -readable medium storing
sqrt( q ), such that v = w /z mod q . This is done by the same instructions that, when executed by one or more hardware
method as in ECDSA embodiment above , with n replaced by processors of a computing device , cause the computing
q . The verifier then computes: device to perform operations comprising :
Rºz gº (zu mod q)Yºw mod p . receiving, by a receiver of the computing device and
15 through a network , an electronic message including a
If this quantity equals 1, then verifier accepts the signa signature , wherein the electronic message omits a pub
ture, otherwise the signature is rejected . lic key of a signer, and the signature comprises a
The verifier computes this quantity using the square- and signature on the electronic message M ;
multiply algorithm , or some variants thereof, and exploits receiving, by the receiver of the computing device and
simultaneous squaring, which is analogous to simultaneous 20 through the network , a first elliptic curve point associ
doubling in ECDSA . Many of the methods of ECDSA fast ated with a signature component from the signer,
verify may be used for DSA fast verify. A pre - computed wherein the signature component comprises a first
multiple of the g , say j, may be used , so that the computation signature component r, the signature includes the first
looks like : Rºz gîs j' t Yw mod p signature component r and a second signature compo
where each of z, s, t and w has bit length about half that 25 nent s, and the first elliptic curve point comprises an
of q . If pre -computed powers of the public Y are made elliptic curve point R ;
available , then the lengths of the exponents can be further recovering, by the one ormore hardware processors of the
reduced , thereby further reducing the number of doublings, computing device , the omitted public key of the signer
making the verification yet faster . based on the received first elliptic curve point and the
What we claim is: 30 received signature, wherein the public key comprises a
1 . A method performed by a hardware processor of a second elliptic curve point in an elliptic curve group
computing device, comprising : different from the first elliptic curve point, wherein the
receiving, by a receiver of the computing device and elliptic curve group includes the first and second ellip
through a network , an electronic message including a tic curve points, wherein the second elliptic curve point
signature , wherein the electronic message omits a pub - 35 comprises an elliptic curve point Q , wherein recovering
lic key of a signer, and the signature comprises a the omitted public key of the signer comprises com
signature on the electronic message M ; puting Q = r ^ - (SR - eG ), wherein G comprises a genera
receiving, by the receiver of the computing device and tor of an elliptic curve group that includes the elliptic
through the network , a first elliptic curve point associ curve point R and the elliptic curve point Q , and
ated with a signature component from the signer, 40 whereine is a hash value computed from the electronic
wherein the signature component comprises a first message M ; and
signature component r, the signature includes the first verifying, by the one or more hardware processors of the
signature component r and a second signature compo computing device, the received signature using the
nent s, and the first elliptic curve point comprises an recovered public key which provides an accelerated
elliptic curve point R ; 45 verification of the received signature .
recovering, by the hardware processor of the computing 7 . The computer -readable medium of claim 6 , the opera
device , the omitted public key of the signer based on tions further comprising verifying that the elliptic curve
the received first elliptic curve point and the received point Q represents the public key of the signer.
signature , wherein the public key comprises a second 8 . The computer -readable medium of claim 6 , wherein the
elliptic curve point in an elliptic curve group different 50 elliptic curve point R is generated based on the first signature
from the first elliptic curve point, wherein the elliptic component r and a cofactor h for an elliptic curve that
curve group includes the first and second elliptic curve includes the elliptic curve point R and the elliptic curve point
points , wherein the second elliptic curve point com - Q .
prises an elliptic curve point Q , wherein recovering the 9 . The computer- readable medium of claim 6 , wherein the
omitted public key of the signer comprises computing 55 public key of the signer can be used to verify the signature .
Q = r -? (sR - eG ), wherein G comprises a generator of an 10 . A computing device comprising :
elliptic curve group that includes the elliptic curve a receiver configured to receive an electronic message
point R and the elliptic curve point Q , and wherein e is including a signature , wherein the electronic message
a hash value computed from the electronic message M ; omits a public key of a signer, and the signature
and 60 comprises a signature on the electronic message M ;
verifying , by the hardware processor of the computing a memory ; and
device , the received signature using the recovered a hardware processor communicatively coupled with the
public key which provides an accelerated verification memory and configured to :
of the received signature . receive, from the receiver, a first elliptic curve point
2 . The method of claim 1 , further comprising verifying 65 associated with a signature component from the signer,
that the elliptic curve point Q represents the public key of the wherein the signature component comprises a first
signer. signature component r, the signature includes the first
US 10 ,284 , 370 B2
19
signature component r and a second signature compo
nent s , and the first elliptic curve point comprises an
elliptic curve point R ;
recover, by the hardware processor of the computing
device, the omitted public key of the signer based on 5
the received first elliptic curve point and the received
signature, wherein the public key comprises a second
elliptic curve point in an elliptic curve group different
from the first elliptic curve point, wherein the elliptic
curve group includes the first and second elliptic curve 10
points, wherein the second elliptic curve point com
prises an elliptic curve point Q , wherein recovering the
omitted public key of the signer comprises computing
Q = r - (sR - G ), wherein G comprises a generator of an
elliptic curve group that includes the elliptic curve 15
point R and the elliptic curve point Q , and wherein e is
a hash value computed from the electronic message M ;
and
verify , by the hardware processor of the computing
device, the received signature using the recovered 20
public key which provides an accelerated verification
of the received signature .
11 . The computing device of claim 10 , wherein the
hardware processor is further configured to verify that the
elliptic curve point Q represents the public key of the signer. 25
*