Elliptic Curve Abe-Okamoto-Suzuki Message
Recovery Signature Scheme (ECAOS)
Working Draft 20080825
August 25, 2008

1

Introduction

This section gives an overview of this standard, its use, its aims, and its development.

1.1

Overview

This document specifies public-key cryptographic schemes based on elliptic
curve cryptography (ECC). In particular, it specifies signature scheme.
It also describes cryptographic primitives which are used to construct theschemes, and ASN.1 syntax for identifying the schemes.
The schemes are intended for general application within computer and communications systems.

1.2

Aim

The aim of this document is threefold:• Firstly, to facilitate deployment of ECC by completely specifying efficient,well-established, and well-understood public-key cryptographic schemes
based on ECC.
• Secondly, to encourage deployment of interoperable implementations ofECC by profiling standards such as ANSI X9.62 [X9.62a], WAP WTLS
[WTLS], ANSI X9.63 [X9.63] and IEEE 1363 [1363], and recommendation
NIST SP 800-56 [800-56A], but restricting the options allowed in thesestandards to increase the likelihood of interoperability and to ensure conformance with as many standards as possible.
• Thirdly, to help ensure ongoing detailed analysis of ECC by cryptographers by clearly, completely, and publicly specifying baseline techniques.

11.3

Compliance

Implementations may claim compliance with the cryptographic schemes specified in this document provide the external interface (input and output) to theschemes is equivalent to the interface specified here. Internal computations may
be performed as specified here, or may be performed via an equivalent sequenceof operations.
Note that this compliance definition implies that conformant implementations must perform all the cryptographic checks included in the scheme specifications in this document. This is important because the checks are essential tothe prevention of subtle attacks.
It is intended to make a validation system available so that implementors cancheck compliance with this document — see the SECG website, http://www.secg.org,
for further information.

1.4

Document Evolution

This document will be reviewed every five years to ensure it remains up to datewith cryptographic advances. The next scheduled review will therefore takeplace in November, 2013.
This current draft, version 0.9.0, is a work in progress and is subject tochange without notice. Its purpose is review at the annual SECG meeting inNovember, 2008.
Additional intermittent reviews may also be performed occasionally, as deemednecessary by the Standards for Efficiency Cryptography Group.

1.5Intellectual Property

The reader’s attention is called to the possibility that compliance with this document may require use of an invention covered by patent rights. By publicationof this document, no position is taken with respect to the validity of this claim
or of any patent rights in connection therewith. The patent holder(s) may have
filed with the SECG a statement of willingness to grant a license under theserights on reasonable and nondiscriminatory terms and conditions to applicants
desiring to obtain such a license. Additional details may be obtained from thepatent holder and from the SECG website, http://www.secg.org.

1.6

Organization

This document is organized as follows.
The main body of the document focuses on the specification of signaturescheme based on ECC. Section 2 describes the Elliptic Curve Abe-OkamotoSuzuki Message Recovery Signature Scheme (ECAOS).
The appendices to the document provide additional relevant material. Appendix A provides recommendation for mask generation function. Appendix B
provides requirement for domain parameters. Appendix C provides recommendation for domain parameters. Appendix D provides test vectors.
2

2ECAOS Message Recovery Signature Scheme

The Elliptic Curve Abe-Okamoto-Suzuki Message Recovery Signature Scheme(ECAOS) [2] is a message recovery signature scheme based on ECC. It is designed to be existentially unforgeable, even in the presence of an adversarycapable of launching chosen-message attacks.
The setup procedure for ECAOS is specified in Section 2.1, the key deployment procedure is specified in Section 2.2, the signing operation is specified inSection 2.3, and the verifying operation is specified in Section 2.4.

2.1

Scheme Setup

The domain parameters of ECAOS consist of the elliptic curve domain parameters and the octet length domain parameters described below.
The elliptic curve domain parameters T of ECAOS are described below:• T = (p, a, b, G, n, h) or (m, f (x), a, b, G, n, h) or (p, m, f (x), a, b, G, n, h),where hGi is an additive cyclic group of prime order n, with cofactor h,with a base point G, in an elliptic curve E with coefficients a, b, over anfinite field F explicitly given by characteristic p, extension degree m, anddefining polynomial f (x).
These elliptic curve domain parameters are specified in section 3.1 of SEC1[3]and section ?? of SEC6[4].
The octet length domain parameters of ECAOS are described below:• Ln : octet length of prime integer n,• LF : octet length of an element of finite field F ,• K: octet length of the extended part of a mask string,• Lred : octet length of added redundancy, and• Lminrec : octet length of minimum recovable message.
These length domain parameters are required to satisfy the following conditions
w.r.t. security parameter κ > 0 to ensure 8κ-bit security: Ln ≥ 2κ, LF ≥ 2κ,K ≥ κ, Lred ≥ κ, and Lred + Lminrec ≥ 2κ.
Lred and Lminarerequiredtosatisfy the following conditions because of therec
maximum output octet length Lout
MGF of mask generation function MGF specifiedoutin appendix A: Lred ≤ LoutandLminrec ≤ LMGF .
MGF
ECAOS uses mask generation function MGF specified in appendix A.
ECAOS uses conversion functions OS2IP and I2OSP specified in section 2.3
of SEC1[3], EC2OSP specified in section 2.3 of SEC1[3], and EC2OSP for OEF
specified in section ?? of SEC6[4].
We denote by L(s) octet length of octet string s.

3

2.2

Key Deployment

ECAOS key generation algorithm KeyGen is defined as follows:
Input:• elliptic curve domain parameters T .
Output:• private key x ∈ [1, n − 1] and• public key Y ∈ hGi.
Actions: ECAOS key generation algorithm KeyGen creates keys as follows:
1. select random integer x ∈ [1, n − 1],
2. compute Y = xG ∈ hGi, and3. output private key x ∈ [1, n − 1] and public key Y ∈ hGi.

2.3

Signing Operation

ECAOS signing algorithm Sig takes as input octet strings Mrec of octet lengthout0 ≤ L(Mrec ) ≤ min(LinMGF − (LF + 11), LMGF − 1) and Mclr of octet lengthe0 ≤ L(Mclr ) ≤ Lin
MGF − (Lred + Lrec + 1), and is defined as follows:
Input:• domain parameters,• private key x ∈ [1, n − 1],• recoverable message Mrec ∈ {0, 1}8∗ , and• non-recoverable message Mclr ∈ {0, 1}8∗ .
Output:e• signature (r, s) ∈ {0, 1}8(Lred +Lrec ) × [1, n − 1].
Actions: ECAOS signing algorithm Sig creates signature as follows:
1. compute Lrec = L(Mrec ) and Lclr = L(Mclr ),e rec = max(Lmin , Lrec +1) and M
frec = I2OSP(1, Le rec −Lrec )||Mrec ∈2. compute Lrece8Lrec{0, 1},
3. compute L0rec = I2OSP(Lrec , 8) ∈ {0, 1}64 ,4. select random integer k ∈ [1, n − 1],
5. compute R = kG ∈ hGi,4

6. compute R0 = EC2OSPE (R, compressed) ∈ {0, 1}8(LF +1) ,frec ||L0rec ||R0 ||I2OSP(0, 1), Lred ) ∈ {0, 1}8Lred ,7. compute h0 = MGF(Me rec ) ∈ {0, 1}8Lerec ,8. compute h1 = MGF(h0 ||R0 ||I2OSP(1, 1), Lfrec ⊕ h1 ) ∈ {0, 1}8(Lred +Lerec ) ,9. compute r = h0 ||(M10. compute u = MGF(Mclr ||r||I2OSP(2, 1), Ln + K) ∈ {0, 1}8(Ln +K) ,11. compute t = OS2IP(u) mod n ∈ [0, n − 1],
12. if t = 0, goto step 4,
13. compute random integer s = k − xt mod n ∈ [0, n − 1],
14. if s = 0, goto step 4, ande

15. output signature (r, s) ∈ {0, 1}8(Lred +Lrec ) × [1, n − 1].

2.4

Verifying Operation

ECAOS verification algorithm V er takes as input octet string r and integer s
and octet string Mclr , and is defined as follows:
Input:• domain parameters,• public key Y ∈ hGi,
• signature (r, s) ∈ {0, 1}8∗ × Z, and• non-recoverable message Mclr ∈ {0, 1}8∗ .
Output:• recoverable message Mrec ∈ {0, 1}8Lrec or ‘invalid’.
Actions: ECAOS verification algorithm V er checks signature as follows:
1. compute Lr = L(r) and Lclr = L(Mclr ),inout
2. check Lred + Lminrec ≤ Lr ≤ Lred + min(LMGF − (LF + 10), LMGF ), 1 ≤ s ≤en − 1, and 0 ≤ Lclr ≤ Lin
MGF − (Lred + Lrec + 1),

3. if it does not hold, output ‘invalid’ and stop,
4. compute u = MGF(Mclr ||r||I2OSP(2, 1), Ln + K) ∈ {0, 1}8(Ln +K) ,5. compute t = OS2IP(u) mod n ∈ [0, n − 1],
6. if t = 0, output ‘invalid’ and stop,5

7. compute R = sG + tY ∈ hGi,
8. if R is the point at infinity, output ‘invalid’ and stop,
9. compute R0 = EC2OSPE (R, compressed) ∈ {0, 1}8(LF +1) ,e rec = Lr − Lred ,10. compute Le

11. decompose r = r0 ||r1 ∈ {0, 1}8(Lred +Lrec ) s.t. r0 ∈ {0, 1}8Lred and r1 ∈e{0, 1}8Lrec ,e rec ) ∈ {0, 1}8Lerec ,12. compute h1 = MGF(r0 ||R0 ||I2OSP(1, 1), Le

frec = r1 ⊕ h1 ∈ {0, 1}8Lrec ,13. compute M
frec = I2OSP(1, i)||Mrec s.t. 1 ≤ i ≤ Lmin
14. decompose M
rec , if there exists
such unique i,
15. if there exists no such i, output ‘invalid’ and stop,e rec − i,16. compute Lrec = L
17. compute L0rec = I2OSP(Lrec , 8) ∈ {0, 1}64 ,frec ||L0rec ||R0 ||I2OSP(0, 1), Lred ) ∈ {0, 1}8Lred ,18. compute h0 = MGF(M
19. if r0 6= h0 , output ‘invalid’ and stop, and
20. output recovered message Mrec ∈ {0, 1}8Lrec .

References[1] Iso/iec 9796-3. In ISO/IEC, 2006.
[2] Masayuki Abe, Tatsuaki Okamoto, and Koutarou Suzuki. Message recovery
signature schemes from sigma-protocols. In NTT Technical Review, January
2008 Vol. 6 No. 1, 2008.
[3] Certicom Corp. Sec 1. In SECG specification, 2000.
[4] NTT Laboratories. Sec 6. In SECG specification, 2008.

A

Mask Generation Function

ECAOS uses mask generation function MGF that takes as input octet string x
and octet length l and output octet string MGF(x, l) of length l. We denote byoutLinMGF maximal octet length of input x, and by LMGF maximal octet length ofoutput MGF(x, l).

6The following implementation of mask generation function MGF is recommended. It uses mask generation function MGF1 specified in ISO9796-3[1], andinout
64 outinoutwith Lin
MGF = LHash − 8 and LMGF = 2 LHash . Here, LHash and LHash are
maximal octet length of input and output of the hash function used in MGF1,respectively.
32 outMGF(x, l) = MGF1(x||I2OSP(0, 4), 232 Lout
Hash )||MGF1(x||I2OSP(1, 4), 2 LHash )||8l. . . ||MGF1(x||I2OSP(b − 1, 4), l − 232 Lout
Hash (b − 1)) ∈ {0, 1} ,32 out
where b = dl/(232 LoutHash )e. If l ≤ 2 LHash , it can be written as follows.

MGF(x, l) = MGF1(x||I2OSP(0, 4), l) ∈ {0, 1}8l .

BRequirements for Parameters

Length parameters Ln , LF , K, Lred , and Lminrec are required to satisfy the following conditions.
• Ln ≥ 20,• LF ≥ 20,• K ≥ 10,
• Lred ≥ 10,min• Lminrec ≥ 0 and Lred + Lrec ≥ 20.

Hash function in MGF1 is required to be one of the following hash functions.
• SHA-1, SHA-224, SHA-256, SHA-384, SHA-512.

CRecommendations for Parameters

Length parameters Ln , LF , K, Lred , and Lminrec are recommended to be thefollowing value, and hash function in MGF1 is recommended to be the following
hash function.
• Ln = 32, LF = 32, K = 16, Lred = 16, Lminrec = 16.
• SHA-256.
In general, length parameters Ln , LF , K, Lred , and Lminrec are recommended
to be the following value, and hash function in MGF1 is recommended to bethe following hash function.
• κ ≥ 16, Ln = 2κ, LF = 2κ, K = κ, Lred = κ, Lminrec = κ.
• Hash function with κ-bit security from the list in requirements.

7