US8788827B2 — 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.
US008788827B2
(12) United States Patent (10) Patent No.: US 8,788,827 B2
Struik et al. (45) Date of Patent: *Jul. 22, 2014
(54) ACCELERATED VERIFICATION OF DIGITAL USPC ............................................. 713/171; 380/30
SIGNATURES AND PUBLIC KEYS (58) Field of Classification Search
CPC ......................................................... HO4L 9730
(75) Inventors: Marinus Struik, Toronto (CA); Daniel See application file for complete search history.
R. Brown, Mississauga (CA); Scott A.
Vanstone, Campbellville (CA); Robert (56) References Cited
P. Gallant, Corner Brook (CA); Adrian
Antipa, Brampton (CA); Robert J. U.S. PATENT DOCUMENTS
Lambert, Cambridge (CA) 4,519,036 A 5/1985 Green
4,745,568 A 5/1988 Onyszchuk et al.
(73) Assignee: Certicom Corp., Mississauga, Ontario
(CA) (Continued)
(*) Notice: Subject to any disclaimer, the term of this FOREIGN PATENT DOCUMENTS
patent is extended or adjusted under 35 EP 588339 A2 3, 1994
U.S.C. 154(b) by 0 days. FR 2536928 A1 6, 1984
This patent is Subject to a terminal dis- (Continued)
claimer. OTHER PUBLICATIONS
(21) Appl. No.: 13/620,206 Wang, C. et al.; “VLSI Architectures for Computing Multiplications
and Inverses in GF (2m)”; IEEE Transactions on Computers; vol.
(22) Filed: Sep. 14, 2012 C-34, No. 8: 1985; pp. 709-717.
(65) Prior Publication Data (Continued)
US 2013/OO64367 A1 Mar. 14, 2013 Primary Examiner — Pramila Parthasarathy
(74) Attorney, Agent, or Firm — Fish & Richardson P.C.
Related U.S. Application Data
(63) Continuation of application No. 13/478,288, filed on (57) ABSTRACT
May 23, 2012, which is a continuation of application Accelerated computation of combinations of group opera
No. 1 1/333,296, filed on Jan. 18, 2006, now Pat. No. tions in a finite field is provided by arranging for at least one
8,204.232. of the operands to have a relatively small bit length. In a
elliptic curve group, Verification that a value representative of
(60) Provisional application No. 60/644,034, filed on Jan. a point R corresponds the sum of two other points uG and VG
18, 2005. is obtained by deriving integers W.Z of reduced bit length and
so that v-w/Z. The verification equality R=uG+vO may then
(51) Int. Cl. be computed as -ZR--(uz mod n) G+wO-O with Z and w of
H04L 29/06 (2006.01) reduced bit length. This is beneficial in digital signature veri
H04L 9/30 (2006.01) fication where increased verification can be attained.
(52) U.S. Cl.
CPC ........................................ H04L 9/30 (2013.01) 13 Claims, 14 Drawing Sheets
Sign if it (itain Raccef
R
s
it sit}R - (e.g.
fi'i
(Q is giblic key of
US 8,788,827 B2
Page 2
(56) References Cited FOREIGN PATENT DOCUMENTS
U.S. PATENT DOCUMENTS FR 26724O2 A1 8, 1992
JP 2002-3286O2 11, 2002
4,748,668 A 5, 1988 Shamir et al. JP 2004-163687 6, 2004
4,890,323 A 12/1989 Beker et al. WO WO9116691 A1 10, 1991
4,989,171 A 1/1991 Hollmann WO WO98OO771 A1 1, 1998
5,146,500 A 9, 1992 Maurer WO WO9852319 A1 11, 1998
5,150,411 A 9, 1992 Maurer WO WOOO42733 A1 T 2000
5,159,632 A 10, 1992 Crandall WO 2006O76800 T 2006
5,202.995 A 4, 1993 O'Brien WO 2009030O21 3, 2009
5,218,637 A 6/1993 Angebaud et al.
5,271,061 A 12/1993 Crandall OTHER PUBLICATIONS
5,272,755 A 12/1993 Miyaji et al.
5,351,297 A 9/1994 Miyaji et al. Miyaji, A.; “Elliptic Curves Suitable for Cryptosystems'; IEICE
5,373,560 A 12, 1994 Schlafly Transactions on Fundamentals of Electronics, Communications and
38. A 88: E. al. Computer Sciences; vol. E77-A, No. 1; 1994; pp. 98-104.
5.497,423. A 3/1996 Miyaji Schnorr, C.P.: “Efficient Signature Generation by Smart Cards':
5,511, 198 A 4, 1996 Hotta Journal of Cryptology; vol. 4, No. 3; 1991; pp. 161-174.
5,524.222 A 6, 1996 Hervin Koyama, K. et al.; "Elliptic Curve Cryptosystems and Their Appli
5,627,893 A 5/1997 Demytko cations'; IEICE Transactions on Information and Systems; vol. E75
5,650,948 A 7, 1997 Gafter D, No. 1; 1992: pp. 50-57.
5,675.645 A 10, 1997 Schwartz et al. Waleffe, D. et al.: “CORSAIR: A Smart Card for Public Key
5,757,918 A 5/1998 Hopkins Cryptosystems'. Advances in Cryptology—CRYPTO 90; 1990; pp.
5,761,305 A 6, 1998 Vanstone et al. 502-513.
5,764,772 A 6, 1998 Kaufman et al. Koblitz. Neal; "Elliptic Curve Cryptosystems'; Mathematics of
5,768,389 A 6/1998 Ishii Computation: vol. 48, No. 177: 1987: pp. 203-209
5,778,069 A 7/1998 Thomlinson et al. omputation vol. 48, No. 1 / 1, 1981, pp. . .
5,825,880 A 10, 1998 Sudia et al. Menezes, Alfred: “Elliptic Curve Cryptosystems'; Athesis presented
5,889,865 A 3, 1999 Vanstone et al. to the University of Waterloo; 1992: pp. 1-121.
5,892,899 A 4/1999 AucSmith et al. Miller, Victor C.: “Use of Elliptic Curves in Cryptography”;
5,896.455 A 4/1999 Vanstone et al. CRYPTO 85; LNCS 218; 1985; pp. 417-426.
5.937,066 A 8, 1999 Gennaro et al. Menezes, A. et al.; "The Implementation of Elliptic Curve
5,987,131 A 1 1/1999 Clapp Cryptosystems' of “Lecture Notes in Computer Science': Advances
5.999,626 A 12, 1999 Mullin et al. in Cryptology–AUSCRYPT '90; International Conference on
6,122,736 A 9, 2000 Vanstone et al. Cryptology; vol. 453; 1990; 14 pages.
6,141,420 A 10, 2000 Vanstone et al. Lercier, R.; "Finding Good Random Elliptic Curves for
6,212.279 B1 4/2001 Reiter et al. Cryptosystems Defined over Finite Fields'; Advances in Cryptogra
6,243,467 B1 6, 2001 Reiter et al. phy EUROCRYPT '97; vol. 1233; 1997; pp. 379-392.
6.279, 110 B1 8/2001 Johnson et al. Menezes, Alfred. J.; “Handbook of Applied Cryptography: CRC
6.298,135 B1 10/2001 Messerges et al. Press; 1997; pp. 613, 614, 618.
6,304,658 B1 10/2001 Kocher et al. Mueller, Volker; “Fast Multiplication on Elliptic Curves over Small
6,334,189 B1 12/2001 Granger et al. Fields of Characteristic Two'; Submitted to Journal of Cryptology;
6,411,715 B1 6, 2002 Liskov et al. 1997; pp. 1.-19.
6,419,159 B1 7/2002 Odinak Cheon, J.H. et al.; "Two Efficient Algorithms for Arithmetic of Ellip
6,430,588 B1 8/2002 Kobayashi et al. tic Curves Using Frobenius Map”; Public Key Cryptography; First
6,446,207 B1 9, 2002 Vanstone et al. International Workshop on Practice and Theory in Public Key Cryp
6,496.929 B2 12/2002 Lenstra tography PCK98; 1998; pp. 195-202.
6,724,894 B1 4/2004 Singer Solinas, Jerome A.; "An Improved Algorithm for Arithmetic on a
6,816,594 B1 1 1/2004 Okeya Family of Elliptic Curves” of “LectureNotes in Computer Science':
6,829,356 B1 12/2004 Ford Advances in Cryptology—CRYPTO 97: 17th Annual International
6,873,706 B1 3/2005 Miyazaki et al. Cryptology Conference; 1997; pp. 357-371.
7,110,538 B2 9, 2006 Gallant et al. Koblitz. Neal: “CM-Curves with Good CrVotographic Properties':
7,127,063 B2 10/2006 Lambert et al. SIC. systeryggles
7.215,780 B2 5/2007 Lambert et al. vances in Cryptography 1, 1991,forpp.Arithmetic
Solinas, Jerome A.: “Improved Algorithms 419-281. on
7,421,074 B2 9, 2008 Jin et al. »s.
7,486,789 B2 2/2009 Futa et al. Anormalous Binary Curves s Technical Report; 1999; 69 pages.
7.593,527 B2 9, 2009 Beeson ........................... 380.30 Johnson, D. et al; The Elliptic Curve Digital Signature Algorithm
7.599.491 B2 10, 2009 Lambert (ECDSA)”; Certricom Corporation White Paper; 2001; pp. 2-56.
7,613,660 B2 11/2009 Pintsov Kelsy, J. et al.; "Side Channel Cryptanalysis of Product Ciphers';
8,069,346 B2 * 1 1/2011 Struik ........................... T13,156 Journal of Computer Security 8; 2000, pp. 141-158.
8,204.232 B2 * 6/2012 Struik et al. 380.282 Kocher, Paul C.; "Timing Attacks on Implementations of Diffie
8,307,211 B2 11/2012 Vanstone .... 713, 175 Hellman, RSA, DSS, and Other Systems”. Advances in Cryptol
8.467,535 B2 * 6/2013 Struik ........................... 380.282 ogy—CRYPTO 96; Proceedings of the 16th Annual International
2001/0053220 A1 12/2001 Kocher et al. Cryptology Conference; vol. 1109; 1996; pp. 104-113.
2002fOO44649 A1 4/2002 Gallant et al. Kocher, Petal.; “Differential Power Analysis”; Advances in Cryptol
2002fOO57796 A1 5, 2002 Lambert et al. ogy—CRYPTO 99; Proceedings of the 19th Annual International
2002fO166058 A1 11, 2002 Fueki Cryptology Conference; 1999: pp. 388-397.
2003/0021410 A1 1/2003 Miyazaki et al. Wharton, John; "An Introduction to the Intel-MCS-51 Single-Chip
2003/0044003 A1 3/2003 Chari et al. Microcomputer Family'; Intel Corporation; Intel Application No.
2003/00489.03 A1 3/2003 Ito et al. AP-69; 1980:30 pages.
2003/0059042 A1 3/2003 Okeya et al. Kocher, P. et al.: “Introduction to Differential Power Analysis and
2003/0059043 A1 3/2003 Okeya et al. Related Attacks”; Cryptography Research; 1998, 5 pages.
2003, OO61498 A1 3/2003 Drexler et al. Examiner's Report issued in Canadian Application No. 2,259,089 on
2005. O135606 A1 6, 2005 Brown Feb. 2, 2009; 3 pages.
US 8,788,827 B2
Page 3
(56) References Cited Hankerson, Darrel et al.; "Guide to Elliptic Curve Cryptography”;
ISBN 0-387-95273-X: 2004; 332 pages.
OTHER PUBLICATIONS Public-Key Cryptography for the Financial Services Industry: Digital
Signature Algorithms Providing Partial Message Recovery: Part 1:
Moller, Bodo; “Algorithms for Multi-Exponentiation'; Selected Elliptic Curve Pintsov-Vanstone Signatures (ECPVS). Draft Ameri
Areas in Cryptography—SAC 2001; LNCS 2259: pp. 165-180. can National Standard X9.92-2002, 2002, 65 pages.
Yen, S.M. et al.; “Multi-Exponentiation': IEEE Proceedings ANSI, X9.62-1998, Public Key Cryptography for the Financial Ser
Comput. Digit. Tech.; vol. 141, No. 6; 1994; pp. 325-326. vices Industry: The Elliptic Curve Digital Signature Algorithm
Proceeding further with the European Application Pursuant to Rule
70(2) EPC issued in European Application No. 0670 1572.7 on Oct. (ECDSA), Jan. 1999, 195 pages.
23, 2009; 6 pages. Dirichlet, “Bericht liber die Zur Bekanntmachung geeigneten
Communication Pursuant to Article 94(3) EPC issued in European Verhandlungen der Königl. Preufs. Akademie der Wissenschaften Zu
Application No. 06701572.7 on Mar. 8, 2010; 4 pages. Berlin', 1842, 4 pages; Certification and English Translation:
Communication Pursuant to Article 94(3) EPC issued in European “Report Concerning the Negotiations of the Royal Prussian Academy
Application No. 06701572.7 on Jul. 16, 2010; 4 pages. of Sciences at Berlin Suitable to be Announced”, 1842, 5 pages.
Communication under Rule 71(3) EPC issued in European Applica Bleichenbacher, “Compressing Rabin Signatures”. Lecture Notes in
tion No. 06701572.7 on Apr. 4, 2011; 6 pages. Computer Science, Springer, Berlin, 2004, pp. 124-126, ISBN 3-540
International Search Report and Written Opinion of the International 20996-4.
Searching Authority issued in International Application No. PCT/
CA2006/00058 on May 1, 2006; 11 pages. Website: http://cr.yp.to sigs/compress.html. Publication date of
International Preliminary Report on Patentability issued in Interna website: unknown, retreived on Jul. 15, 2009.
tional Application No. PCT/CA2006/00058 on Aug. 2, 2007; 8 Extended European Search Report issued in European Application
pageS. No. 11178908.7 on Nov. 15, 2011; 6 pages.
Deitel, H.M. et al., “C++How to Program”, 1994, Prentice-Hall, pp. Official Action issued in Japanese Application No. 2007-550647 on
58-62. Nov. 25, 2011; 4 pages.
A. Antipa, D. R. L. Brown, R. P. Gallant, R. Lambert, R. Struikand S. Ciet, M. et al.: “Improved Algorithms for Efficient Arithmetic on
A. Vanstone. Accelerated verification of ECDSA signatures. In B. Elliptic Curves Using Fast Endomorphisms'; Advances in Cryptol
Preneel and S. Tavares (eds.), Selected Areas in Cryptography: SAC ogy—Eurocrypt; International Conference on Theory and Applica
2005, Lecture Notes in Computer Science 3897, pp. 307-318. tion of Cryptographic Techniques; May 4, 2003; pp. 388-400.
Springer, Aug. 2005. Sakai, Y, et al.; "Algorithms for Efficient Simultaneous Elliptic Scalar
IEEE P1363a / D12 (Draft Version 12), Jul 16, 2003, 177 pages. Multiplication with Reduced Joint Hamming Weight Representation
P. Nguyen, D. Stehle, Low-Dimensional Lattice-Basis Reduction of Scalars'; Proceedings of the 5th Internaitonal Conference on
Revisited. ACM Transactions on Algorithms, vol. 5, No. 4. Article Information Security; Sep. 30, 2002: pp. 484-499.
46, Publication date: Oct. 2009, 48 pages. Park, Y-H. et al., “An Alternate Decomposition of an Integer for
R. Gallant, R. Lambert, S.A. Vanstone, Fast Point Multiplication on Faster Point Multiplication on Certain Elliptic Curves': Proceedings
Elliptic Curves with Efficient Endomorphisms, in Proceedings of of the 5th Internaitonal Workshop on Practice and Theory in Public
Advances in Cryptology CRYPTO 2001, Lecture Notes in Com Key Cryptosystems; Jan. 1, 2002: pp. 323-334.
puter Science, vol. 2139, pp. 190-200, 2001. Office Action issued in U.S. Appl. No. 13/041,759 issued on Aug. 22.
G.H. Hardy, E.M. Wright. An Introduction to the Theory of Numbers, 2012; 7 pages.
Fifth Edition, Oxford: Oxford University Press, 2000, pp. 169-170. Communication under Rule 71(3) EPC issued in European Applica
D.J. Johnson, A.J. Menezes, S.A. Vanstone, 'The Elliptic Curve tion No. 11178908.7 on Mar. 19, 2013; 7 pages.
Digital Signature Algorithm (ECDSA). International Journal of Office Action issued in Japanese Application No. 2011-230106 on
Information Security, vol. 1, pp. 36-63, 2001. Mar. 13, 2013; 10 pages.
L. Lovasz, An Algorithmic Theory of Numbers, Graphs and Con Examiner's Report issued in Canadian Application No. 2,592,870 on
vexity. CBMSNSF Regional Conference Series in Applied Math Aug. 9, 2012; 2 pages.
ematics, Band 50, SIAM Publications, 1986, 98 pages. Supplementary European Search Report issued in European Appli
P. Nguyen, D. Stehle, Low-Dimensional Lattice-Basis Reduction cation No. 06701572.7 on Oct. 6, 2009; 4 pages.
Revisited. ANTS 2004, Lecture Notes in Computer Science, vol. Communication Pursuant to Article 94(3) EPC issued in European
3076, pp. 338-357, 2004. Application No. 11178908.7 on May 30, 2012; 7 pages.
J. Solinas, “Low-Weight Binary Representations for Pairs of Inte Extended European Search Report issued in European Application
gers. Centre for Applied Cryptographic Research, Corr 2001-41. No. 12158215.9 on Jul. 2, 2012; 8 pages.
University of Waterloo, Ontario, Canada, 2001, 24 pages. Notice of Final Rejection issued in Japanese Application No. 2007
Henry Cohen, A Course in Computational Algebraic Number Theory, 550647 on Feb. 28, 2012; 8 pages.
Springer, ISBN 0-387-55640-0, pp. 83-96. Notice of Allowance issued in Japanese Application No. 2011
Official Action issued in Japanese Application No. 2007-550647 on 230106 on Aug. 28, 2013: 3 pages. No English translation.
Jul. 19, 2011 (3 pages); with English translation (5 pages). Office Action issued in Japanese Application No. 2012-143272 on
U.S. Department of Commerce/National Institute of Standards and Aug. 9, 2013; 2 pages. No English translation.
Technology; Federal Information Processing Standards Publication Office Action issued in Canadian Application No. 2,592,875 on Feb.
(FIPS PUB 180-2); “Secure Hash Standard”; Aug. 1, 2002; 75 pages. 10, 2014; 3 pages.
U.S. Department of Commerce/National Institute of Standards and Notice of Allowance issued in Canadian Application No. 2,770,001
Technology; Federal Information Processing Standards Publication on Dec. 9, 2013; 1 page.
(FIPS PUB 186-2); “Digital Signature Standard (DSS)”; Jan. 27.
2000; 76 pages. * cited by examiner
U.S. Patent US 8,788,827 B2
eun!,61-)
U.S. Patent Jul. 22, 2014 Sheet 2 of 14 US 8,788,827 B2
Gate as k
Cospite k3
ege citysio
x- x
Carpite
f : X is
Figure 2
Crite
e is hy
Corpsite
s is (a + i)ii.
Stegie
Set facis,
U.S. Patent Jul. 22, 2014 Sheet 3 of 14 US 8,788,827 B2
-
Co?pite
& S (M)
Corpsie
at eis not
W i is foci
Figure 3
Recover point R
fr; afic
Corpute
2R + (2 sod G + w(R
Werify
U.S. Patent Jul. 22, 2014 Sheet 4 of 14 US 8,788,827 B2
receive
E,S
CE
R.
co: Epite
Y,2,
Cife
cospite
a'G + 3"; + w(+zR
yY
VERY REET
Figure 4
U.S. Patent Jul. 22, 2014 Sheet 5 of 14 US 8,788,827 B2
receive
3
i.S.
cGEpute
W.2.
aG + w(R + zR
wer
s rege cospite w{ i zR.
REEC
WEREY
Figure 5
U.S. Patent Jul. 22, 2014 Sheet 6 of 14 US 8,788,827 B2
it essage wi SecWe:
R
corpute
W.2.
deteriaihe validation equation
insert precomputed
waites
O $REEC
VERFY
Figure 6
U.S. Patent Jul. 22, 2014 Sheet 7 of 14 US 8,788,827 B2
feceive
i.S
ecoy
R
Figure 7
U.S. Patent Jul. 22, 2014 Sheet 8 of 14 US 8,788,827 B2
cosapiite
co: Epite
FS
Figure 8
U.S. Patent Jul. 22, 2014 Sheet 9 of 14 US 8,788,827 B2
geneiate
k
sex,ysed 2)
Coute
S
arm
Figure 9
U.S. Patent Jul. 22, 2014 Sheet 10 of 14 US 8,788,827 B2
geteiaie
k
does yati 2 r 0 citage k
-kg dist
Y
seat
recover .
assistie i i" (
Figure 10
U.S. Patent Jul. 22, 2014 Sheet 11 of 14 US 8,788,827 B2
Ottai wa
w it wig
Corpute Cipute x of
x coordiate of 2R X w + (Z. not r}G
As these as --- - Roe
Figure 11
U.S. Patent Jul. 22, 2014 Sheet 12 of 14 US 8,788,827 B2
{Seeate
Corpute wyz.
die Wiig. cc f"
Co?pite
z - wis
N X
ses is e Or
Y
accept
Figure 12
U.S. Patent Jul. 22, 2014 Sheet 13 of 14 US 8,788,827 B2
$8.
x xx SXw Srr r
r
& S is fix: 8}& $ $3
XXXX-XXX
X----------- YYYXXXxxxxxx
S&S
: $8S is
AAAAYYYYYYYYA-AXAAA
c
Figure 13
U.S. Patent Jul. 22, 2014 Sheet 14 of 14 US 8,788,827 B2
Sign w to obtain Recover
,S R
Corpute
C. r. (Sir) R - (eirG
Figure 14 Corfi'i
Q is public key of
Seide
US 8,788,827 B2
1. 2
ACCELERATED VERIFICATION OF DIGITAL properties defining a group. The elliptic curve group has the
SIGNATURES AND PUBLIC KEYS further property that it is abelian, meaning that P+Q=Q+P.
Scalar multiplication can be defined from addition as fol
This application is a continuation of and claims priority lows. For any point P and any positive integerd, dP is defined
from U.S. patent application Ser. No. 13/478,288, filed on as P+P.+...+P, where d occurrences of Poccur. Thus 1P=P
May 23, 2012, which is a continuation of and claims priority and 2P=P+P, and 3P=P+P.+P, and so on. We also define OP=0
from U.S. patent application Ser. No. 1 1/333,296, filed on and (-d) P-d (-P).
Jan. 18, 2006, now U.S. Pat. No. 8,204.232 which claims For simplicity, it is preferable to work with an elliptic curve
priority from U.S. Provisional Application No. 60/644,034 10 that a
is cyclic (defined below) although in practice, sometimes
cyclic Subgroup of the elliptic curve is used instead. Being
filed Jan. 18, 2005. All three of the priority applications are cyclic means that there is a generator G, which is a point in the
hereby incorporated by reference. group Such that every other point P in the group is a multiple
The present invention relates to computational techniques of G, that is to say, P-dG, for some positive integerd. The
used in cryptographic algorithms. smallest positive integer n such that nG=O is the order of G
15 (and of the curve E, when E is cyclic). In cryptographic
BACKGROUND TO THE INVENTION
applications, the elliptic curves are chosen so that n is prime.
In an elliptic curve cryptosystem, the analogue to exponen
The security and authenticity of information transferred tiation is point multiplication. Thus it is a private key is an
through data communication systems is of paramount impor integerk, the corresponding public key is the point kP, where
tance. Much of the information is of a sensitive nature and P is a predefined point on the curve that is part of the system
lack of proper control may result in economic and personal parameters. The seed point P will typically be the generator
loss. Cryptographic systems have been developed to address G. The key pair may be used with various cryptographic
Such concerns. algorithms to establish common keys for encryption and to
Public key cryptography permits the secure communica perform digital signatures. Such algorithms frequently
tion over a data communication system without the necessity 25 require the verification of certain operations by comparing a
to transfer identical keys to other parties in the information pair of values as to confirm a defined relationship, referred to
exchange through independent mechanisms, such as a courier as the Verification equality, between a set of values.
or the like. Public key cryptography is based upon the gen One such algorithm is the Elliptic Curve Digital Signature
eration of a key pair, one of which is private and the other Algorithm (ECDSA) used to generate digital signatures on
public that are related by a one way mathematical function. 30 messages exchanged between entities. Entities using ECDSA
The one way function is such that, in the underlying math have two roles, that of a signer and that of a verifier. A signer
ematical structure, the public key is readily computed from selects a long term private key d, which is an integer d
the private key but the private key cannot feasibly be ascer between 1 and n-1 inclusive. The integerd must be secret, so
tained from the public key. it is generally preferable to choose d at random. The signer
One of the more robust one way functions involves expo 35 computes Q=dG. The point Q is the long-term public key of
nentiation in a finite field where an integer k is used as a the signer, and is made available to the verifiers. Generally,
private key and the generator of the field C. is exponentiated to the verifiers will have assurance generally by way of a cer
provide a public key K-C’. Even though C. and Kare known, tificate from a CA, that Q corresponds to the entity who is the
the underlying mathematical structure of the finite field signer. Finding the private key d from the public key Q is
makes it infeasible to obtain the private key k. Public key 40 believed to an intractable problem for the choices of elliptic
cryptography may be used between parties to establish a curves used today.
commonkey by both parties exchanging their public keys and For any message M, the signer can create a signature,
exponentiating the other parties public key with their private which is a pair of integers (r, s) in the case ECDSA. Any
key. Public key cryptography may also be used to digitally verifier can take the message M, the public key Q, and the
sign a message to authenticate the origin of the message. The 45 signature (r, s), and verify whether it was created by the
author of the message signs the message using his private key corresponding signer. This is because creation of a valid
and the authenticity of the message may then be verified using signature (r. S) is believed to possible only by an entity who
the corresponding public key. knows the private key d corresponding to the public key Q.
The security of such systems is dependent to a large part on The signing process is as follows. First, the signer chooses
the underlying mathematical structure. The most commonly 50 Some integerk in the interval 1, n-1 that is to be used as a
used structure for implementing discrete logarithm systems is session, or ephemeral, private key. The value k must be secret,
a cyclic Subgroup of a multiplicative group of a finite field in so generally it is preferable to choose k randomly. Then, the
which the group operation is multiplication or cyclic Sub signer computes a point R=kG that has co-ordinates (x, y).
groups of elliptic curve groups in which the group operation Next, the signer converts X to an integer X and then computes
is addition. 55 rx mod n, which is the first coordinate of the signature. The
An elliptic curve E is a set of points of the form (x,y) where signer must also compute the integer e=h(M) mod n, where h
Xandy are in a field F. Such as the integers modulo a prime p, is some hash function, generally one of the Secure Hash
commonly referred to as Fp, and Xandy satisfy a non-singular Algorithms (such as SHA-1 or SHA-256) defined in Federal
cubic equation, which can take the form y'-x+ax+b for Information Processing Standard (FIPS) 180-2. Finally, the
some a and b in F. The elliptic curve E also includes a point at 60 second coordinate S is computed as S-(e--dr)/s mod n. The
infinity, indicated as O. The points of E may be defined in such components (r, s) are used by the signer as the signature of the
a way as to form a group. The point O is the identity of the message, M, and sent with the message to the intended recipi
group, so that O--P-P-O-P for any point P in E. For each ent.
point P, there is another point, which we will write as-P, such The verifying process is as follows. First the verifier com
that P+(-P)=P+(-P)=O. For any three points P, Q, R in E, 65 putes an integer e=h(M) mod n from the received message.
associativity holds, which means that P+(Q+R)=(P+Q)+R. Then the verifier computes integers u and V such that u=e/mod
Identity, negation and associativity are the three axiomatic in and v=r?s mod n. Next, the verifier computes a value corre
US 8,788,827 B2
3 4
sponding to the point R that is obtained by adding uG+VO. so that saved repetition amount to less than pre-computation.
This has co-ordinates (x, y). Finally the verifier converts the Nevertheless, it has been found that with a judicious choice of
field element x to an integer x and checks that r=x" mod n. If table, the time need for a single computation can be reduced.
it does the signature is verified. The table takes time to compute, and computation of the table
From the above, the verification of an ECDSA signature 5 cannot be amortized over multiple computations, so is
appears to take twice as long as the creation of an ECDSA incurred for every computation. Experience has shown that
signature, because the verification process involves two sca
lar multiplications, namely uG and VO, whereas signing particular tables decrease the amount of time needed because
computing the table takes less time than the repetition opera
involves only one scalar multiplication, namely kG. Elliptic tions that would have otherwise been needed. Usually, there is
curve scalar multiplications consume most of the time of 10 an optimum size and choice of table. Another cost of Such
these processes, so twice as many of them essentially doubles tables is the memory needed to temporarily store the table.
the computation time. Methods are known for computing The cost of such memory may affect the optimal choice of
uG+VO that takes less time than computing uG and VG sepa table. Windowing
rately. Some of these methods are attributed to Shamir, some puted on the fly. methods are examples of such tables com
to Solinas, and some to various others. Generally, these meth 15
ods mean that computinguG+VO can take 1.5 times as long as Not withstanding all of the above known techniques for
computing kG. efficient implementation, further efficiency improvements
Another commonly used method to accelerate elliptic are desirable. In particular, the efficiency of verifying of
curve computations is pre-computing tables of multiples of ECDSA signatures is particularly desirable. Extensive pre
G. Such pre-computed tables save time, because the point G computation allows ECDSA signatures to be generated very
is generally a fixed system parameter that is re-used repeat quickly. In fact, ECDSA signature generation is one of the
edly. The simplest pre-compute table consists of all multiples fastest digital signature generation algorithms known. On the
2G for from 0 to t, where t is the bit-length of n. With such other hand, ECDSA signature verification is relatively
a pre-computed table, computing an arbitrary multiple kG can slower, and there are other signature algorithms have similar
be done with an average of t/2 point additions or less. 25 verification times to ECDSA. Improvement of ECDSA veri
Roughly, this a threefold improvement over the basic method fication time is therefore important, especially for environ
of computing kG, which clearly demonstrates the benefit of ments where verification time is a bottleneck.
pre-computation. Generally speaking, larger pre-computed In general, there is a need to enhance the efficiency of
tables yield better time improvements. The memory needed performing a computation to verify that a value corresponds
to store the pre-computed tables has a significant cost. There 30 to the sum of two of the values. It is therefore an object of the
fore, implementers must balance the benefit of faster opera present invention to obviate or mitigate the above disadvan
tions with the extra cost of larger tables. The exact balance tages.
generally depends of the relative importance of speed versus
memory usage, which can vary from one implementation to SUMMARY OF THE INVENTION
another. 35
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
fixed for a given system. Therefore the cost of one-time pre between the sum of scalar multiples of a pair of points on an
computation for Q is amortized over a smaller number of 40 elliptic curve and a third point on said curve. The method
repeated run-time computations involving Q. Nevertheless, if comprises the steps of i) obtaining a pair of integers of bit
Q is to be used more than once, some net savings on time will length less than one of said scalars and whose ratio corre
beachieved. Public keys that are heavily used include those of sponds to said scalar; ii) Substituting said integers for said
certification authorities (CA), especially root, trusted or Scalars in said relationship to obtain an equivalent relation
anchor CA public keys (that are pre-installed into a system). 45 ship in which at least one of said terms is a scalar multiple of
Therefore, pre-computation may be worthwhile for CA ellip one of said points with reduced bit length, and iii) computing
tic curve public keys where, for example, the protocol said equivalent relationship to verify said equality.
requires verification of a CA's certificate. Another difference The method may be used for verifying that a value repre
between pre-computations of Q versus G is the cost of storing sentative of a point R on an elliptic curve corresponds to the
or communicating the pre-computed tables. Each public key 50 Sum of two other points, uG and VO. Integers w and Z are
Q requires its own pre-computed table. In a system with many determined such that the bit lengths of the bit strings repre
distinct public keys, these costs may accumulate to the point senting w and Z are each less than the bit length of the bit
that any benefit of faster computation is offset by the need to string of the integer V, and such that V-w/Z mod n. With such
store or communicate keys. The net benefit depends on the w and Z, the equation R=uG+vO can be verified as -ZR--(Zu
relative cost of time, memory and bandwidth, which can vary 55 mod n)G+wO-O.
tremendously between implementations and systems. Again, Preferably, the bit lengths of w and Z are each about half the
in the case of CA public keys, especially root, trusted or bit length of n, which means that both w and Z are both no
anchor CA keys, these keys tend to be fewer in number than larger than about n'
end-entity public keys, so that the cost of pre-computation The point -ZR+(Zu mod n)G+wO can be computed effi
will generally be less and amortised over more operations. 60 ciently because Z and w are relatively small integers, and
Tables of multiples of points are not merely useful during various of the methods for computing a sum faster than its
pre-computation. In practice, such tables are commonly gen parts can be used. The multiple (Zu mod n) is full size, but
erated at run-time, during an initial phase of each computa within the context of an algorithm such as the ECDSA, the
tion. The savings provided by these tables is essentially that of point G may be fixed or recurring. In this case the computa
avoiding certain repetitious operations that occur within a 65 tion can be accelerated with the use of a stored table for G.
single computation. A single computation has less internal Estimates of the times savings for this approach compared to
repetitions than two distinct computations have in common, conventional verification with tables for G are around 40%.
US 8,788,827 B2
5 6
The values w and Z may be obtained by using a partial on an elliptic curve is required to groups other than elliptic
completed extended Euclidean algorithm computation. Alter curve groups. Therefore the accompanying description of the
natively, a continued fractions approach may be utilised to embodiments shown is exemplary and not exhaustive.
obtain w and Zefficiently. Referring therefore to FIG. 1, a data communication sys
In a further aspect of the invention there is provided a 5 tem 10 includes a pair of correspondents 12, 14 intercon
method of verifying a digital signature of a message per nected by a transmission line 16. The correspondents 12, 14
formed by a cryptographic operation in a group of a finite field each include cryptographic modules 20, 22 respectively that
having elements represented by bit strings of defined maxi are operable to implement one of a number of cryptographic
mum bit length. The signature comprises a pair of compo functions. The modules 20, 22 are each controlled by CPU's
nents, one of which is derived from an ephemeral public key 10 incorporated in the correspondents 12, 14 and interfacing
of a signer and the other of which combines the message, the between input devices, such as a keyboard 24, a display
first component and the ephemeral public key and a long term device 26, Such as a screen and a memory 28. Each crypto
public key of the signer. The method comprises the steps of graphic module includes internal processing capability
recovering the ephemeral public key from the first compo including a random number generator 30 and an arithmetic
nent, establishing a verification equality as a combination of 15 processor 32 for performing elliptic curve computations such
group operations on the ephemeral public key, the long term as point addition. It will be appreciated that the correspon
public key and a generator of the group with at least one of the dents 12, 14 may be general purpose computers connected in
group operations involving an operand represented by bit a network or specialised devices such as cell phones, pagers,
strings having a reduced bit length less than the defined maxi PDA's or the like. The communication link 16 may be a land
mum bit length, computing the combination and accepting 20 line or wireless or a combination thereof. Similarly the cryp
the signature if said equality holds and rejecting the signature tographic modules 20, 22 may be implemented as separate
if said equality fails. modules or incorporated as an application within the CPU.
Preferably, the group is a elliptic curve group. As a further In the present example, the correspondent 12 prepares a
aspect, a method of generating a signature of a message by a message M which it wishes to sign and send to the correspon
cryptographic operation in an elliptic curve group of finite 25 dent 14 using an elliptic curve cryptosystem embodied within
field comprising the steps of generating a pair of signature the modules 20, 22. The parameters of the system are known
components with one of said components derived from a to each party including the field over which the curve is
point representing an ephemeral public key and including in defined (in the present example Fp where p is a prime), the
said signature an indicator to identify one of a plurality of underlying curve, E, the generator point G that generates the
possible values of said public key that may be recovered from 30 elements that form the group in which crypto operations are
said one component. performed and therefore defines the order, n, of the group, and
Embodiments of the invention will now be described by a secure hash function H, generally one of the Secure Hash
way of example only with reference to the accompanying Algorithms (such as SHA-1 or SHA-256) defined in Federal
drawings in which:— Information Processing Standard (FIPS) 180-2. Each element
FIG. 1 is a schematic representation of a data communica- 35 is represented as a bit string having a maximum bit length
tion system, Sufficient to represent each element in the group.
FIG. 2 is a flow chart illustrating the steps in performing a The steps taken to sign the message are shown in FIG. 2.
signature for an ECDSA signature Scheme. Initially therefore the correspondent generates an integerkby
FIG.3 is a flow chart showing the verification of a ECDSA the random number generator 30 and utilises the arithmetic
signature. 40 unit 32 to compute a point R=kG that has co-ordinates (x, y).
FIG. 4 is a flow chart showing the verification of an The correspondent 12 converts the co-ordinate X to an integer
ECDSA signature using a precomputed value. x' and computes r=x mod n, which is the first component of
FIG. 5 is a flow chart showing the verification of an the signature. The correspondent 12 also computes the integer
ECDSA signature using a table of precomputed values. e=H(M) mod n, where H is the secure hash function. Finally,
FIG. 6 is a flow chart showing the verification of an 45 the second component S is computed as S-(e--dr)/k mod n.
ECDSA signature using a precomputed value provided by the In addition to the components r and S, the signature
signer includes informationi to permit the co-ordinates representing
FIG. 7 is a flow chart showing steps taken by a verifier upon the point R to be recovered from the component r. This infor
failing to verify. mation may be embedded in the message M, or forwarded as
FIG. 8 is a flow chart showing steps taken by a signor to 50 a separate component with r and S and will be used by the
simplify verification. verifier to compute the value R. If the elliptic curve is defined
FIG. 9 is a flow chart showing an alternative signature over a field F of prime orderp, and the elliptic curve E is cyclic
protocol to simplify verification or prime order n, theni can generally be taken asy mod 2, i.e.,
FIG. 10 is a flow chart showing an alternative technique a Zero or one. The indication i is required during recovery R.
performed by the signor to simply verification. 55 where the verifier sets X-r. It is very likely that x=r becausen
FIG. 11 is a flow chart showing an alternative verification and pare extremely close for typical implementations. Given
ECDSA. X, there are exactly two values y Such that (x, y) is on the
FIG. 12 is a flow chart showing point verification. curve, and these two valuesy andy' have different values mod
FIG. 13 is a flow chart showing a modified PVS verification 2. Thus i is just a single bit whose value indicates which of the
protocol. 60 y’s is to be used, and adds relatively little cost to the signature.
FIG. 14 shows a method of recovering a public key from an Once the message is signed it is forwarded together with
ECDSA signature. the components rs, and i across the link 16 to the recipient
The present invention is exemplified by reference to veri correspondent 14. To Verify the signature the steps set out in
fication of digital signatures, in particular those signatures FIG.3 are performed. First the correspondent 14 computes an
generated using ECDSA. It will be apparent however that the 65 integer e=H(M) mod n. Then the correspondent utilises the
techniques described are applicable to other algorithms in arithmetic unit 32 to compute a pair of integers u and v Such
which verification of a pair of values representative of points that u=efs mod n and v=r?s mod n.
US 8,788,827 B2
7 8
The correspondent 14 also computes a pair of integers w operations, assuming no pre-computation, for a total of about
and Z using an iterative algorithm such that the maximum bit 3t point operations. Computing uG+vO, which is the verifi
lengths of w and Z are each less than the maximum bit length cation normally used for ECDSA, require t doublings, some
of the elements of the group, and such that V-w/Z mod n. The of which can be simultaneous. Each ofu and v are expected to
bit lengths of w and Z are preferably about one half the bit have about t?2 bits set to one in their binary representation. In
length of the elements. Such w and Z can be found conve basic binary Scalar multiplication, each bit of one requires
niently with the extended Euclidean algorithm and stopping another addition. (In more advanced scalar multiplication,
at an appropriate point, typically half-way where w and V are signed binary expansion are used, and the average number of
half the bit length of the elements. Such an algorithm is additions is t?3.) The total number of point operations is
exemplified, for example as Algorithm3.74 in Guide to Ellip 10 therefore t+(2(t/2))=2t on average as simultaneous doubling
tic Curve Cryptography by Henkerson, Menezes and Van has saved t doublings.)
stone published by Springer under ISBN 0-387-95273, which The revised verification instead uses a computation of a
represents a quantity k as k-k+kW mod n, where the bit combination of the form aG+wO+ZR, wherea is an integer of
lengths of k and k are about half the length of n. This bit length t representative of the value Zu mod n and w and Z
equation can be re-written as w(k-k)/k mod n. By setting 15 are integers of bit length about (t/2). Organising the Verifica
k=1 and wV, then the above referenced Algorithm 3.74 can tion computation in this way permits a number of efficient
be used to obtain in established for the system, k set to 1 and techniques to be used to reduce the number of point opera
the value for V used as the variable input. The output obtained tions. An efficient way to compute this is to use a simulta
k k can then be used to compute w-l-k and k used as neous doubling and add algorithm. For example, if the rela
w=1-k and Zik. tionship 15G+20O+13R is to be computed it can be done in
Thus, the arithmetic unit 32 is used to implement the fol stages as 2CR; G+2O: G+2Q+R: 2G+4Q+2R; 3G+4Q+2R;
lowing pseudo-code to obtain the values of w and Z. 3G+5Q+2R:3G+5Q+3R; 6G+10O+6R: 7G--10O+6R; 14G+
Let r()=n and tO=0. 20O+12R; 15G+20O+13R, for a total of 12 point additions,
Let r1 =V and t1 =1. which is fewer than the method of generic scalar multiplica
For i>1, determineri, ti as follows: 25 tion for each term separately. The main way that this method
Use the division algorithm to writer (i-1)-qir (i-2)+ri, uses less operations is when it does simultaneous doubling, in
which defines ri. steps as going from G+2O+R to 2G+4Q+2R. In computing
Let tit (i-1)+qit (i-2). each term separately three operations would be used corre
Stop as soon as ri-sqrt(n)=n (/2), or some other desired sponding to this one operation. In fact, three simultaneous
S17C. 30 doubling were used, each saving two operations, so simulta
Set w=ri and Z=ti. Note that ri=tiv mod n, so w=Zv mod n, neous doubling account precisely for all the savings. The
so v=w/Z mod n, and both w and Z have about half the bit number of doublings to compute the combination is governed
length of n, as desired. by the length of the highest multiple, so it is t. The number of
The correspondent 14 also recovers a value corresponding additions for a is (t/2), on average, and for Q and R it is (t/4)
to the point Rutilising the information i. In its simplest form 35 each on average. The total, on average, is t+(t/2)+(t/4)+(t/4)
this is obtained by substituting the value of r received in the =2t. The algorithm is further exemplified as Algorithm 3.48 of
curve and determining which of the two possible values of y the Guide to Elliptic Curve Cryptography detailed above.
correspond to the sign indicated by the bit i. Although there does not appear to be any savings over the
With the value of R recovered, the verification of the previous method, which also took2t point operations, advan
ECDSA, namely that R=uG+vO, may proceed with a revised 40 tage can be taken of the fact that in practice, for ECDSA, the
Verification by confirming that the verification equality -ZR-- generator G is constant. This allows the point J-2 m G to be
(Zu mod n)G+wO=0. The verification equality -ZR+(Zu mod computed in advance, and stored in memory 28 for future use.
n)G+WO involves a combination of group operations on each If m is chosen to be approximately t2, then asa'+a" 2 m,
of the ephemeral public key R., generator G and long-term where a' and a' are integers of bit length about (t/2). Accord
public key Q and can be computed efficiently because Zandw 45 ingly, aG+wO+ZR can be written as a'G+a"J+wO+ZR. In this
are relatively small integers. As will be described below, form, all the scalar multiples have bit length (t/2). The total
various of the methods for computing a sum faster than its number of doublings is thus (t/2). Each of the four terms
parts can be used. The multiple (Zu mod n) is full size, but contributes on average (t/4) additions. The total number of
within the context of a system such as the ECDSA in which point operations, on average, is the t/2+4 (t/4)–3t/2.
the points have varying longevity, the point G may be con 50 Accordingly, to Verify the signaturer, S, as shown Schemati
sidered fixed or recurring. In this case the computation can be cally in FIG. 4, the recipient computes w, and Z as described
accelerated with a precomputed table for G, which may be above, determines the value ofa'anda" and performs a double
stored in the memory 28 and accessed by arithmetic unit 32 as and add computation to obtain the value of the verification
needed. The representations of the points -ZR and wO which representation. If this corresponds to the group identity, the
cannot effectively be precomputed have smaller bit lengths 55 verification is confirmed.
and therefore less time consuming computation. Assuming With the conventional verification equation approach of
the computation returns a value O, the signature is assumed to computing uG+vO, the multiple V will generally be full
be verified. length t, so the pre-computed multiple J of G will not help
A number of different known techniques may be utilised to reduce the number of simultaneous doublings.
compute the required relationship, each of which may be 60 Therefore, by pre-computing and storing the single point J.
implemented using the arithmetic processor 32. Each offers verifying using the relationship -ZR+(Zu mod n)G+wO-O
different advantages, either in speed or computing resources, allows an ECDSA signature to be verified in 25% less time. In
and so the technique or combination of techniques will other words, 33% more signatures can be verified in a given
depend to a certain extent on the environment in which the amount of time using the embodiment described above.
communication system is operating. For the sake of compari 65 Alternatively, many implementations have sufficient
son, it will be assumed that u and V are integers of bit length memory 32 to pre-compute and store essentially all power of
t. Computing uG and VO separately requires about 3t/2 point two multiples of G, essentially making it unnecessary to
US 8,788,827 B2
9 10
apply doubling operations to G. In Such situations uG+VO can puted multiples of Qare feasible, then the signing equation, in
be computed with tdoublings of Q and (t/2) additions for each the form above, again provide a significant benefit. The analy
of G and Q. The total is still 2t operations. However, as shown ses above would be slightly modified when signed binary
in FIG. 5, the value of aG can be retrieved from the precom expansions are used.
puted table stored in memory 32 so that computing aG+WO+ With yet other known advanced techniques for computing
ZR, can be attained with (t/2) doublings for the w(Rand ZR, no linear combinations of points, some of which are discussed
doublings for G, t?2 additions for G, and t?4additions for each below, the use of the relationship allows signature verification
of Q and R. The total is 3t/2 operations. The savings are the to take up to 40% less time.
same as described with FIG. 4, when only one multiple of G When implementing scalar multiplication and combina
was pre-computed and stored. 10 tions, it is common to build a table at run-time of certain
When signed binary expansions are used, then computing multiples. These tables allow signed bits in the representation
uG+VO (without any pre-computation) requires about t dou of Scalar multiple to be processed in groups, usually called
blings and (t/3) additions for each of G and Q, for a total of windows. The table costs time and memory to build, but then
(10/6)t operations, on average. When signed binary expan accelerates the rest of the computation. Normally, the size of
sions are used to finda'G+a"J+wO+ZR, about t?2 doublings 15 the table and associated window are optimized for overall
are needed, and (t/6) additions for each of G, J, Q and R, for performance, which usually means to minimize the time
a total of (7/6)t operations, on average. The time to verify taken, except on some hardware implementation where
using the verification representation described above is 70% memory is more critical. A full description and implementing
compared to without, or 30% less. This allows about 42% algorithms for Such techniques is to be found in Guide to
more signatures to Verified in a given amount of time. The Elliptic Curve Cryptography, referenced above at pages 98 et.
advantage of Verifying using the revised verification repre Sec.
sentation is increased when combined with a more advanced Such run-time tables, or windowing techniques, for Scalar
technique of scalar multiplication referred to as signed binary multiplication techniques can be combined with the revised
expansions. This technique is very commonly used today in verification equation in the embodiments described above.
elliptic curve cryptography, so today’s existing implementa 25 When using Such tables, the savings are approximately the
tions stand to benefit from adoption of the verification repre same as outlined above. The reason the savings are similar is
sentations. the following simple fact. Tables reduce the number of adds,
Accordingly, it will be seen that by reorganizing the veri by pre-computing certain patterns of additions that are likely
fication equation so that signature variables have a reduced bit occur repeatedly, whereas the use of the revised verification
length, the speed of Verification may be increased signifi 30 relationship reduces the number of doubles by providing for
cantly. more simultaneous doubling. In fact, when using tables, the
In the above embodiments, the recipient performs compu number of adds is reduced, so the further reduction of the
tations on the components rs. To further accelerate signature doubles provided by using the revised verification relation
Verification as shown in FIG. 6, a signer may provide a pre ship has even more impact.
computed multiple of the public key Q to the verifier. The 35 By way of an example, a common approach to tables, is to
verifier can use the pre-computed multiple to further acceler use a signed NAF window of size 5. Building a table for such
ate verification with Q. In this embodiment the verifier deter a NAF requires 11 adds. In the example above where the
mines an equivalent equation to the ECDSA verification signer sends a pre-computed multiple uQ of Q, the Verifier
equation in the form aR+bG+cQ-O, where a is approxi can build tables for R, Q and uO, at a cost of 33 adds. It is
mately n' and represents -Z, b is approximately n and rep 40 presumed that verifier already has the necessary tables built
resents -Zu mod n, and c is approximately n’ and represents for G. Using the pre-computed doubles, the verifier only
w. This can be done using the extended Euclidean algorithm needs to simultaneous additions for verification. These sav
as described above and stopping when the bit length of w is ings improve as the key size increases. For the largest key size
twice that of Z. Again, therefore, the signor signs the message in use today, the savings are in the order of 40%. Such tables
Mand generates the signature components r.s. It also includes 45 do of course require the necessary memory 32 and so selec
the identifier i in the message forwarded to the verifier. The tion of the appropriate techniques is governed by the hard
signor pre-computes a multiple BQ where the Scalar multiple ware available.
f is a power of two nearest to n' and forwards it with the Similarly, computation techniques known as joint sparse
signature. forms could be used for computational efficiency.
Upon receipt, the verifier computes w and Z. The verifier 50 As described above, the integers w, Zwere found using the
then determines c-c'+c"B and b-b'+b"B+b"B2. In addition, extended Euclidean algorithm. Alternative iterative algo
since G is a fixed parameter, the verifier has pre-computed rithms may be used, including the continued fractions
multiples of G of the form BG and B2G. If n is approximately approach. In the continued fractions approach, which is
2t, then the verifier needs just t?3 simultaneous doubles to essentially equivalent to the extended Euclidean algorithm,
compute aR+bG+cO. The verification can proceed on the 55 one finds a partial convergent Y/6 to the fraction V/n, such that
basis aR+(b'+b"B+b"B2)G+(c'+c"B)Q=0. The precomputed 8 is approximately n'. A property of the partial convergentis
values for G and Q can then be used and the verification that IY/ö-V/n|<1/82. Multiplying this inequality by on gives
performed. The verifier will need 2t/3 point additions, assum lyn-vö|<n/ö, which is approximately n'. Now set Z=8 and
ing that signed NAF is used to represent a, b and c. The total w=yn-vö. It is easy to check that V-w/Z mod n, and note that
number of point operations is thus t, which represents a fur 60 w and Z have the desired size.
ther significant savings compared to 3t/2 with the present As noted above, a conventional ECDSA signature, does not
invention and without the pre-computed multiple of Q Such as include the point R but instead, it includes an integer X
described in FIG. 4 and compared to 2t using the conventional obtained from r-X mod n, where R=(x, y). The verifier there
representations and without any pre-computed multiple of Q. fore needs to recover R.
Given a pre-computed multiple of both Q and G, then 65 The method to recover R discussed above is to supplement
uG+vO can be computed with (t/2)+4(t/4)=3t/2 point opera the signature (r, s) with additional information i. This infor
tions using conventional representations. When pre-com mation can be embedded in the message, for example. The
US 8,788,827 B2
11 12
verifier can user and i to compute R. When p>n, there is a r's and forwarded with the message M to the recipient 14. The
negligible chance that x>n and consequently r X-n. If how component r is composed of the X co-ordinate of the point R
ever Such a case does occur, the verification attempt will fail. and the first bit of the y co-ordinate. The component s is
Such a negligible failure rate for valid signatures can be computed as before.
accepted, or dealt with in the following manner. To verify the signature, the recipient 14 recovers the point
As shown in FIG. 7, upon failure of the verification, at the R directly from the component r" and uses the verification
verifier's expense the verifier can try x-r--n, and repeat the equality equation -ZR--(Zu mod n)G+WO-O to confirm it
verification for another value of R, which will succeed in this corresponds to the group identity. The transmission of the
particular case. Continued failure to verify will lead to rejec modified co-ordinate r simplifies the verification but does
tion of the signature. Alternatively, as shown in FIG. 8 the 10 increase the bandwidth required.
signer can detect when X >n, which should happen negligibly In some situations, no channel may be available for the
often, and when this happens generate a different k and R. In signer to send extra bits. For example, existing standards may
either of the approaches, the problem arises so rarely that strictly limit both the signature format and the message for
there is negligible impact on performance. mat leaving no room for the sender to provide additional
Other techniques for determining R can be utilized. In 15 information. Signers and verifiers can nevertheless coordi
non-cyclic curves, there is a cofactor h, which is usually 2 or nate their implementations so that R is recoverable from r.
4 in practice. This can lead to multiple possible values of X. This can be arranged by the signer, as shown in FIG. 10, by
The probability that r X is approximately 1/h. In other situa ensuring that the value of X conforms to prearranged criteria.
tions, we will generally have rX-n (if h=2), or more gener In the notation above, the signer will compute R=kG=(x,y) as
ally rx-mn where (m is between 0 and h-1). Because p is normal, and then in notation above compute i y mod2. If i=1,
approximately hn, then except in a negligible portion of cases the signer will change k to -k mod n, so that R changes to
there will be h possible values of x that are associated with r. -R=(x, -y) and i changes to 0. When the verifier receives the
To make recovery of X, and hence R easier, the signer can signature, the verifier presumes that i=0, and thus recovers the
compute mand send it to the verifier within the message or as signature. The value of i is thus conveyed implicitly as the
a further signature component. Alternatively, the verifier can 25 value 0, and the signer has almost negligible cost for arrang
make an educated guess form. This can be illustrated in the ing this. Similarly, in non-cyclic elliptic curves, the signer
case of h-2. may try to transmit m implicitly, which to Some extent has
Corresponding to r is a correct X and a false value x, The already been described. In the case of h=2, recall that the /4 of
false value x, has an approximately /2 chance of not corre the time, the verifier may need to verify two signatures.
sponding to a value of the X-coordinate on E, and a further 1/h 30 Instead of the Verifier doing this extra work, the signer can
chance of not corresponding to a multiple of G. If one of the detect this 4 case, and try another value for k and R instead,
two values for x is invalid, either by not being on E or if it is repeating the process until one is found that conforms to the
not having order n, both of which can be efficiently checked, criteria. The verifier can determine which value of X to use
then that value can be eliminated. Thus at least 3/4 of the time, without verifying two signatures.
the verifier will easily find the correctX. The remaining 4 of 35 As an alternative to modifying Ras described above, and to
the time at maximum, the verifier will not know which of the maintain strict conformity to the ECDSA standard, the value
two x-values to try. If the verifier can guess one of thex values ofs may be modified after computation rather than R. In this
to Verify, half the time, this guess will be right and the signa case, the signer notes that the value of R does not conform to
ture will verify, and the other half of the time, the first signa the prearranged criteria and proceeds to generater and S as
ture attempt will failand the verifier must try the other X value. 40 usual. After S is computed, the value is changed to (-s) to
Therefore the probability that the verifier must verify two ensure the verification will be attained with the presumption
signatures is /s. Despite this probability of two verifications, of the prearranged value of y.
the average verification is still improved. This can still pro When a signer chooses a signature (r, s) such that R is
vide the verifier time savings on average. If an accelerated implicitly recovered, an ordinary verifier will accept the sig
verification takes 70% as long as a normal verify, but 12.5% 45 nature as usual. Such signatures are perfectly valid. In other
of the Verifies require twice as long as an accelerated verify, words, the revised verification is perfectly compatible with
then the average time is 79% of a normal verify. Furthermore, existing implementations of ECDSA verification. An accel
as outlined further below, the signer can assist by providing m erated verifier expecting an implicitly efficient signature but
for the verifier or by doing the extra work of trying both values receiving a normally generated signature, will need to try two
to ensure that only one m is valid. 50 different values of i. If accelerated verification takes 60% of
A similar method may be utilized with a cofactor h=4. In the time of a normal verify, then in a cyclic curve (cofactor
fact, a higher value of h reduces the probability of each of the h=1), the average time to needed verify a normal signature is
potential x values from being valid. There are more potential 50% (60%)+50% (120%)=90% of a normal verify. This
X values, but the analysis shows a similar benefit to the veri because 50% of the time a normal signature will have i=0,
fier. There are three false values of X, and each has a prob 55 requiring just one implicitly accelerated verify, and the other
ability of /s of appearing valid with a fast check. The chance 50% of the time, two accelerated verifies are needed. Thus an
that no false values appear to be a valid X with a fast check is implicitly accelerated verify will still be faster than a normal
thus (7/s) which is about 77%. Most of the remaining 23% of Verifier, even when the signatures are not implicitly acceler
the time, just one of the false x values will appear valid and ated.
potentially require a full signature verification. 60 Conventional signatures may also be modified, either by
The inclusion of i (and of m if necessary) is quite similar to the signer or by a third party, to permit fast verification. In this
replacing r by a compressed version of R consisting of the X case the signature is forwarded by a requestor to a third party
coordinate and the first hit of they coordinate. This alterna who verifies the signature using the Verification equality. In so
tive, of sending a compressed value of R instead of r, has the doing the value of R is recovered. The signature is modified to
advantage of being somewhat simpler and not even a negli 65 include the indicator I and returned to the requestor. The
gible chance of false recovery. Accordingly, as shown in FIG. modified signature may then be used in Subsequent
9, the signature is computed to provide a pair of components, exchanges with recipients expecting fast verify signatures.
US 8,788,827 B2
13 14
The above techniques recover R to permit a revised verifi Another variant that takes advantage of this technique is to
cation using the relationship -ZR--(Zu mod n)G+wO-O. shorten all three multiples in the ECDSA signing equation.
However, where the ECDSA is being verified, the integers w Theoretically, each multiple can be shortened to a length
and Z may be used without recovery of Ras shown in FIG. 11. which is 2/3 the length of n (where n is the order of G). One
It is possible to compute the X coordinate of ZR and the x' way to achieve this shortening is by Solving the short vector
coordinate of the point wC--(Zu mod n)G, and then check the lattice problem in 3 dimensions. Algorithms exist for solving
equality of these two x-coordinates. Only the x-coordinate of such problems. Shortening all three multiples is most useful
the point ZR can be computed, as it is not possible to compute when no pre-computed multiples of G can be stored, which
the y-coordinate ZR directly without knowing the y-coordi makes it more efficient to reduce the length of the multiple of
nate of R. However, there are several known methods to 10 G as much as possible. Such techniques are described more
compute the x-coordinate of ZR from the x-coordinate of R fully in Henri Cohen, “A Course in Computational Algebraic
without needing the y coordinate of R. Such techniques Number Theory”, Springer, ISBN 0-387-55640-0. Sections
include Montgomery's method set out on page 102 of the 2.6 and 2.6 describe the LLL algorithm, its application to
Guide to Elliptic Curve Cryptography identified above. It is finding short vectors in lattices, and also mentions Vallee's
then sufficient to check the x-coordinates of ZR and wO+(Zu 15 special algorithm for 3 dimensional lattices.
mod n)G, because equality of the X-coordinates means that Anotherapplication of this technique is the application to a
wO+(Zu mod n)G equal ZR or -ZR, which means w/Z Q+u G modified version of the Pintsov-Vanstone Signature scheme
equals R or -R, which means uG+VO has the same X-coordi (PVS) with partial message recovery. A PVS signature is of a
nate as R. This is the condition for successful ECDSA vali triple (r. S., t). Verification of a signature and message recovery
dation. One recovers the x-coordinate of R from the signature from a signature under public Q, with base generator G, is
component r using the methods discussed above. The advan done as follows. The verifier computes e=H(rt), where H is a
tage of this approach is that it does not require extra work to hash function. The verifier then computes R=SG+eC. Next,
recover the y-coordinate. A disadvantage, compared to the the verifier derives a symmetric encryption key K from R.
previous methods above, is that the ZR has to be computed With this, the verifier decrypts rusing K to obtain a recovered
separately from WO+(Zu mod n) G meaning that some of the 25 message partu. The recovered message is some combination
savings of the joint Sum are not achieved. of t and u. The signature is valid only if u contains some
The above examples have verified a signature between a redundancy, which is checked by Verifying that u conforms to
pair of correspondents 12, 14. The technique may also be used some pre-determined format. The PVS scheme is part of draft
to verify an elliptic curve key pair (d, Q) as shown in FIG. 12. Standards IEEE P1363a and ANSIX9.92.
To verify the key pair means to check that Q=dG. This may be 30 In a modified variant of PVS, verification time can be
important when the key pair is provided by a third party under decreased by utilizing integers w and Z. The modified variant
secure conditions to ensure no tampering has occurred. If t is of PVS is shown in FIG. 13 and proceeds as follows. After
the bit length of d, then computing dG with the binary method computing eas usual, the verifier then finds w and Zare length
take (3t/2) operations on average. In the present embodiment, half that of n such that e=w/Z mod n, where n is the order of the
one of the correspondents, 12, 14 generates a random integer 35 point G. The verifier then computes R=(ZS mod n) G+wO, and
d and obtains a pair of integers W, Z Such that dw/Z mod n. proceeds as before, so deriving a key from R and then
Typically the integers w, Z are each of half the of length d. decrypting r with the key, and then Verifying that the decryp
Then the correspondent computes ZQ-wG, and checks that tion has the correct form. This form of verification is more
the result is the group identify 0. Computing ZQ-wG takes t efficient because the multiple of Q is smaller.
operations on average so a saving of 50% is obtained. This has 40 A method to further accelerate signature verification of
the most advantage in environments where storing a pre digital signature, in elliptic curve groups and similar groups is
computed multiple of G is too expensive. As an alternative illustrated as follows. The verification of an ECDSA signa
where limited memory is available, given a pre-computed ture is essentially equivalent to confirmation that a linear
multiple H=uG, then dG can be computed as d'G+d"H, where combination, such as aR+bQ+cG, of three elliptic curve
d=d'+d"u mod n, with roughly the same cost as above. 45 points, equals the point of infinity. One way to Verify this
Another application is implicit certificate verification. condition is to compute the point aR+bO+cG and then check
Implicit certificates are pairs (PI), where P is an elliptic curve if the result is the point O at infinity, which is the identity
point and I is some identity string. An entity Bob obtains an element of the group as described above. This verification can
implicit certificate from a CA by sending a request value R Sometimes be done more quickly than by directly computing
which is an elliptic curve point to the CA. The CA returns the 50 the entire sum. For example, if a=b=c, thenaR+bO+cG=O if
implicit certificate (PI) and in addition a private key recon and only if the points R. Q and G are collinear. Checking if
struction data value S. Bob can use S to calculate his private points are collinear is considerably faster than adding to ellip
key. More generally, any entity can use S to Verify that the tic curve points. Collinearity can be checked with just two
implicit certificate correctly corresponds to Bob's request field multiplication, by the equation (x-x)(yo-yo)-(Xo
value Rand the CA public key C. This is done by checking the 55 X)(y-y)=0. Adding points requires at least two field mul
verification equality H(P. I)R+sG=H(PI) P+C, where H is a tiplication, a field Squaring and a field inversion, which is
hash function. This equation is equivalent to eC+SG-C, generally equivalent to about 8 field multiplication. When
where e=H(P. I) and Q-R-P. The form of this equation is a=b=c, verification is thus possible in about 18% of the time
highly similar to the form of the standard ECDSA verification taken by adding the points. As such, this technique may be
equation. Consequently, the techniques discussed above may 60 used as a preliminary step of the Verification process where
be used to provide a means to accelerate verification of this the likelihood of these conditions existing is present.
equation. This is done optimally by determining relatively Similarly, when b-c=0, so that one wishes to verify that
smaller values w and Z such that e—w/Z mod n, then multiply aR-O, in principle one does not need to compute aR in its
ing the equation through by Z to give: w(Q+(SZ mod n)G- entirety. Instead one could evaluate the a' division polyno
ZC=O. Again, the multiple of G is this equation is full size, but 65 mial at the point R. The division polynomial essentially cor
generally multiples of G can be pre-computed, so this does responds to a recursive formula for the denominators of coor
not represent a problem. dinates the point aR, when expressed as rational functions of
US 8,788,827 B2
15 16
the coordinates of the point R. It is known that alr=O if and perform the verification with the information available. The
only if the denominator is zero. Furthermore, when b-c=0 verification is accelerated but the bandwidth increased.
and the elliptic curve group is cyclic of prime order n, it is Although the descriptions above were for elliptic curve
known that aR=O only if a=0 mod n or if R=O. This verifi groups, many of the methods described in the present inven
cation is comparably instantaneous, in that Zero elliptic curve 5 tion applies more generally to any group used in cryptogra
point operations are needed. When the cofactor is Small, Such phy, and furthermore to any other application that uses expo
as h=2 or h=4, point operations can replaced by a few very fast nentiation of group elements. For example, the present
field operations. Thus special cases of Verification that a Sum invention may be used when the group is a genus 2 hyperel
points is Zero can be done very quickly. liptic curve, which have recently been proposed as an alter
Recursive formula exist, similar to the recursive formulae 10 native to elliptic curve groups. The above techniques may also
for division polynomials, for the denominators of Sums like be used to accelerate the verification of the Digital Signature
aR+bO+cG, and these can be compute more quickly than the Algorithm (DSA), which is an analogue of the ECDSA. Like
computing the full value of the point aR+bQ+cG. Knowledge ECDSA, a DSA signature consists of a pair of integers (r, s),
of the group order n can further improve verification time. and r is obtained from an element R of the DSA group. The
Yet another application of this technique is to provide 15 DSA group is defined to be a subgroup of the multiplicative
efficient recovery of the public key Q from only the ECDSA group of finite field. Unlike ECDSA, however, recovery of R
digital signature as shown in FIG. 14. Suppose that one cor from r is not easy to achieve, even with the help of a few
respondent 12 signs a message M with signature (r, s) and additional bits. Therefore, the present technique applies most
wishes to send the signed message to the correspondent 14. easily to DSA if the value is R sent with as part of the signed
Normally correspondent 14 will send M and (r, s) to the message, or as additional part of the signature, or as a replace
correspondent, and will also often send the public key Q. If ment for the value r. Typically, the integer ris represented with
correspondent 12 did not send her public key, then normally 20 bytes, but the value R is represented with 128 bytes. As a
correspondent 14 will look up her public key up in some result, the combined signature and message length is about
database, which could stored locally or remotely via some 108 bytes longer. This could be a small price to pay to accel
network. To avoid this, it would be beneficial to be able to 25 erate verification by 33%, however.
recover the public key Q from the signature. In the DSA Setup, p is a large prime, and q is Smaller prime
Given an ordinary ECDSA signature (r. S), one can recover and q is a divisor of (p-1). An integerg is chosen Such that
several candidate points Q that could potentially be the public ga-1 mod p, and 1<g<p. (Note that q and g correspond to n
key. The first step is recover the point R. Several methods have and G, respectively, from ECDSA.)
already been described for finding R in the context of accel 30 The private key of the signer is some integer X and the
erated verification, Such as: by inclusion of extra information public key is Y-gx mod p.
with the signature; by inclusion of extra information in the The signer generates a signature in the form (R.s) instead of
message signed; by extra work on the signer's part to ensure the usual (r, s). Here, R=gk mod p, whereas, r-R mod q. In
one valid R can correspond to r, and by extra work on the both cases, s—k (-1) (h(M)+x r) mod q, where x is the private
verifier's part of trying a multiplicity of different R values 35 key of the signer, M is the message being signed, and his the
corresponding to r. Once R is recovered by one of these hash function being used to digest the message (as in
methods, then the public key Q can be recovered as follows. ECDSA).
The standard ECDSA verification equation is R=(e/s)G+(r/s) In normal DSA, the verifier verifies signature (r, s) by
Q, where e=H(M) is the hash of the message. Given Rand this computing u=h(M)/s mod q and V-ris mod q, much like the u
equation, solving for Q is done by Q=(s/r) R-(e/r) G. 40 and V in ECDSA embodiments, and then checks that r=(gu
However, since with a significant probability a pair (r. S) Yv mod p) mod q.
will yield some valid public key, the correspondent 14 needs In this embodiment, the verifier finds w and Z of bit length
a way to check that Q is correspondent's 12 public key. about half that of q, so that each of w and Z is approximately
Correspondent 12 can make available to correspondent 14 the sqrt(q). Such that VW/Z mod q. This is done by the same
signature, such as another ECDSA signature (r. S"), from a 45 method as in ECDSA embodiment above, with n replaced by
CA on correspondent 14 public key. Correspondent 12 can q. The verifier then computes:
send the CA signature, (r. S"), to correspondent 14, or corre Rzg (zli mod q)Yw modp.
spondent 14 can look it up in Some database. The CAS
signature will be on correspondent's 12 name and her public If this quantity equals 1, then Verifier accepts the signature,
key Q. Correspondent 14 will use the CA's certificate to 50 otherwise the signature is rejected.
verify the message which corresponds to the public key Q. If The Verifier computes this quantity using the square-and
the signature verifies then the correspondent 14 has recovered multiply algorithm, or some variants thereof, and exploits
the correct value for the public key Q. Omitting the public key simultaneous squaring, which is analogous to simultaneous
from the certificate can save on bandwidth and storage and the doubling in ECDSA. Many of the methods of ECDSA fast
verification process described above yields reduced verifica 55 verify may be used for DSA fast verify. A pre-computed
tion times. multiple of the g, sayj, may be used, so that the computation
Correspondent 14 could also verify that Q is correspon looks like: RZg sit Yw mod p
dent's 12 public key by checking Q against Some more com where each of Z, s, t and w has bit length about half that of q.
pact value derived from Q, such as the half of the bits of Q. If pre-computed powers of the public Y are made available,
The compact version of Q could then stored or communicated 60 then the lengths of the exponents can be further reduced,
instead of Q, again savings on storage and bandwidth. thereby further reducing the number of doublings, making the
H will also be appreciated that each of the values used in the verification yet faster.
Verification equality are public values. Accordingly, where What is claimed is:
limited computing power is available at the verifier it is pos 1. A computer-implemented method comprising:
sible for the signer to compute the values of w and Z and 65 receiving, from a signer, a signature on a message M.
forward them with R as part of the message. The recipient wherein the signature includes a first signature compo
then does not need to recover R or compute w and Z but can nent rand a second signature components;
US 8,788,827 B2
17 18
obtaining an elliptic curve point associated with the first G comprises a generator of an elliptic curve group that
signature component r, and includes the first elliptic curve point R and the second
generating, by operation of a cryptographic module com elliptic curve point Q.
prising one or more processors, a public key of the signer 7. The computer-readable medium of claim 6, the opera
based on the elliptic curve point and a hash value e 5 tionscurve
further comprising verifying that the second elliptic
point Q represents the public key of the signer.
computed from the message M: 8. The computer-readable medium of claim 6, wherein the
wherein the elliptic curve point comprises a first elliptic first elliptic curve point R is generated based on the first
curve point R, the public key of the signer comprises a signature component rand a cofactor h for an elliptic curve
Second elliptic curve point Q, generating the public key that includes the first elliptic curve point R and the second
of the signer comprises computing Q-r' (sR-eG), and 10 elliptic curve point Q.
G comprises a generator of an elliptic curve group that 9. The computer-readable medium of claim 6, wherein the
includes the first elliptic curve point R and the second public key of the signer can be used to verify the signature.
elliptic curve point Q. 10. A computing device comprising:
2. The method of claim 1, further comprising verifying that 15 a cryptographic module operable to:
the second elliptic curve point Q represents the public key of receive, from a signer, a signature on a message M.
the signer. wherein the signature includes a first signature com
3. The method of claim 1, wherein the first elliptic curve ponent rand a second signature components;
point R is generated based on the first signature component r obtain an elliptic curve point associated with the first
and a cofactor h for an elliptic curve that includes the first signature component r, and
elliptic curve point R and the second elliptic curve point Q. generate a public key of the signer based on the elliptic
4. The method of claim 1, wherein the public key of the curve point and a hash value e computed from the
signer can be used to verify the signature. message M:
5. The method of claim 4, wherein verifying the signature wherein the elliptic curve point comprises a first elliptic
comprises Verifying the signature according to an Elliptic 25 curve point R, the public key of the signer comprises
Curve Digital Signature Algorithm (ECDSA). a second elliptic curve point Q, generating the public
6. A non-transitory computer-readable medium storing key of the signer comprises computing Q-r' (sR
instructions that, when executed by one or more processors, eG), and G comprises a generator of an elliptic curve
perform operations comprising: group that includes the first elliptic curve point Rand
receiving, from a signer, a signature on a message M. 30 the second elliptic curve point Q.
11. The
wherein the signature includes a first signature compo tographic module computing device of claim 10, wherein the cryp
nent r and a second signature components; is further operable to verify that the second
obtaining an elliptic curve point associated with the first elliptic curve point Q represents the public key of the signer.
signature component r, and 12. The computing device of claim 10, wherein the first
elliptic curve point R is generated based on the first signature
generating a public key of the signer based on the elliptic 35 component
curve point and a hash value e computed from the mes includes the first r and a cofactor h for an elliptic curve that
sage M: elliptic curve point Rand the secondelliptic
wherein the elliptic curve point comprises a first elliptic curve point Q.
curve point R, the public key of the signer comprises a key13.ofThe computing device of claim 10, wherein the public
the signer can be used to verify the signature.
second elliptic curve point Q, generating the public key
of the signer comprises computing Q-r' (sR-eC), and ck ck ck ck ck