Evaluation of Security Level of Cryptography:
ESIGN Identification Scheme
Alfred Menezes, Minghua Qu, Doug Stinson, Yongge Wang
Certicom ResearchContact: amenezes@certicom.com
January 15, 2001

2

Protocol specification

1

SummaryPage 1

The ESIGN identification scheme was proposed in 1985 by Tatsuaki Okamoto, and is closely
related to the ESIGN signature scheme. It has been proven to be a secure identification scheme
assuming that the approximate e-th root (AER) problem is hard and that the employed hashfunction is a random function. While the AER problem has been studied by some researchers, it
has not received as much attention as the integer factorization problem or the discrete logarithm
problem. One way to solve the AER problem is to factor the integer n, where n p 2 q and p andq are primes of the same bitlength. The parameters recommended ensure that ESIGN resists all
known attacks for factoring integers of this form.

2Protocol specification

2.1 ESIGN key pairs
For the security parameter kpLen, each entity does the following:

1. Randomly select two distinct primes, p, q, each of bitsize k and compute n 4.
3. A’s public key is  n  e  k  ; A’s private key is  p  q  .
In addition, one needs to specify a hash function H  whose output length is k bits.

p 2 q.

2. Select an integer e

2.2 ESIGN identification
In the ESIGN identification scheme, the verifier sends a random message to the prover whosigns the message using her ESIGN private key. The process whereby an entity A verifies
herself to entity B is the following:
1. (random challenge) Verifier B generates a random string m 0  1 k 1 and sends it to A.

2. (response) A generates an ESIGN signature s of the challenge m as follows:  Z pq : gcd  r p  1 .
 I  z  re  mod n, where the function I  converts a

2.1. Pick r uniformly at random from r

 



2.2. Set z
0 H m 02k and αbinary string into an integer in the usual way.

3

Security level of cryptographic techniques

Page 2  

2.3. Set w0 w1 such thatαpq w0 pqw0w1
2.4. If w1  22k 1, then go back to step 2a.



(1)
α(2)



2.5. Set t erwe0 1 mod p and s B3k  r  t pq mod n , where B3k  X  converts an integer
X to a binary string of length 3k (by prepending 0’s if necessary).
2.6. A sends s to B.
3. (verification)
3.1. B checks whether the following equation holds: B3k  I s e mod n k 0 H m(3)where the function  X  k takes the most significant k bits of the input X .
3.2. If it holds, B accepts A’s identity; otherwise B rejects A’s identity.
Note: The response algorithm computes the integer s such that se mod n lies in a certain interval
determined by the message. The verification algorithm demonstrates that s e mod n does indeed
lie in the specified interval.
Note: In order to speed up the response time, step 2d in the response process could be optional.
The condition w1  22k 1 ensures the value w1 se I z is uniformly distributed in the interval
2k 1 1 as required by the security proof for ESIGN. However, no security weakness is0 2
known if the test is omitted.

 Performance note: Fujioka, Okamoto, and Miyaguchi [7] describe an implementation of ESIGN (with e 32) which suggests that it is twenty times faster than RSA signatures (withe 216  1) with comparable key and signature lengths.

3

Security level of cryptographic techniques

Roughly speaking, the security objectives of any identification scheme are the following:
1. In the case of honest parties A and B, A is able to successfully authenticate itself to B, i.e.,
B will complete the protocol having accepted A’s identity.
2. (transferability) B cannot reuse an identification exchange with A so as to successfully
impersonate A to a third party C.

4Security level of cryptographic primitive functions

Page 33. (impersonation) The probability is negligible that any party C distinct from A, carryingout the protocol and playing the role of A, can cause B to complete and accept A’s identity.
This property should remain true even if a large number of previous authentications between A and B have been observed; the adversary C has participated in previous protocol
executions with either or both A and B; and multiple instances of the protocol, possibly
initiated by C, may be run simultaneously.
Since the ESIGN identification scheme has been derived from the ESIGN signature scheme in astandard way, once can conclude from well-known results that the ESIGN identification scheme
is secure provided that the ESIGN signature scheme is secure. Hence, security examinationof the ESIGN identification scheme reduces to studying the security of the ESIGN signaturescheme.
The security objective of any signature scheme is to be existentially unforgeable against achosen-message attack. The goal of an adversary who launches such an attack against a legitimate entity A is to obtain a valid signature on a single message m, after having obtained A’s
signature on a collection of messages (not including m) of the adversary’s choice.
ESIGN bases its security on the AER (approximate e-th root) assumption which is defined next.
Let n p2 q, where p and q are primes of the same
bitlength. The AER problem is to find x,
given n e y, such that a portion (specifically, the n 3-most significant bits) of x e mod n equals
the corresponding part of y, i.e.,  xe mod n n   3  y n   3. The AER assumption is that there isno efficient algorithm for solving the AER problem.

 

The submission includes a proof that the ESIGN signature scheme is existentially unforgeable
against adaptive chosen-message attacks in the random oracle model under the AER assumption. In the random oracle model, the hash function employed is modeled by a random function.
The security proof of the ESIGN signature scheme is similar to the security proof of Bellareand Rogaway for the Full Domain Hash (FDH) RSA signature scheme. The proof guarantees
resistance to attacks that do not use specific properties of the hash function, assuming only that
the AER problem is intractable. As with all proofs in the random oracle model, it should not
be regarded as an unconditional security proof due to known (albeit theoretical) pitfalls in therandom oracle model (see [5]).

4Security level of cryptographic primitive functions

4.1 Attacks on the hash function
D EFINITION. A (cryptographic) hash function H is a function that maps bit strings of arbitrary
lengths to bit strings of a fixed length t such that:
1. H can be computed efficiently;

4

Security level of cryptographic primitive functions

Page 4 

2. (preimage resistance) For y selected uniformly at random from 0 1 t , it is computationy.
ally infeasible to find a bit string x such that H x 

3. (second preimage resistance) Given x1 , it is computationally infeasible to find a different
bit string x2 such that H x1
H x2 .

  4. (collision resistance) It is computationally infeasible to find distinct bit strings x 1 and x2
H x2 .
such that H x1

  

H ASH F UNCTION S ECURITY R EQUIREMENTS. The following explains how attacks on ESIGN can be successfully launched if hash function is not collision resistant or second preimage
resistant.
1. If the hash function is not collision resistant, then an entity A may be able to repudiatesignatures as follows. A first generate two messages m and m such that H m
H m ;such a pair of messages is called a collision for H. She then signs m, and later claims tohave signed m (note that every signature for m is also a signature for m ).

  

2. If H is not collision resistant, then an entity B could use the birthday attack to swindle A
as follows. B prepares two versions (m1 and m2 ) of a contract, where m1 is favorable to
A and m2 bankrupts A. B makes several subtle changes to each document and compares
whether H m1H m2 , where m1 (m2 ) is a subtle variant of m1 (m2). When B finds
two such variants, B gets the signature s of m1 from A. Then s is also a signature of m2 .

  



3. If the hash function H is not second preimage resistant, then an entity B may be able toforge signatures as follows. B generates a message m, find another message m such thatH m
H m , and gets the signature s of m from A. Then s is also a signature of m.

  I DEAL S ECURITY. A t-bit hash function is said to be have ideal security [9] if both: (i) given ahash output, producing a preimage (or a second preimage) requires approximately 2t operations;and (ii) producing a collision requires approximately 2t  2 operations (this is the best that canbe hoped for, in view of the birthday attacks). The hash function used in ESIGN is a k-bit
hash function and is required to have ideal security. The fastest method known for attacking
ESIGN by exploiting properties of hash function is to find collisions for the hash function. Since
this is believed to take 2k  2 steps, attacking ESIGN in this way is computationally infeasible.
Note, however, that this attack imposes an upper bound of 2 k  2 on the security level of ESIGN,
regardless of the size of the primary security parameter n. Of course, this is also the case withall present signature schemes with appendix.

5

Security level of cryptographic primitive problem

Page 5

5Security level of cryptographic primitive problem: the approximate eth roots problem

ESIGN was originally proposed by Okamoto and Shiraishi [11] and was motivated by the digital
signature mechanism OSS devised by Ong, Schnorr, and Shamir [12]. The OSS scheme wasshown to be insecure by Pollard in a private communication to them. Ong, Schnorr, and Shamir[12] modified their original scheme but this too was shown insecure by Estes et al. [6].
ESIGN bases its security on the AER (approximate e-th root) assumption which is defined next.
Let n p2 q, where p and q are primes of the same
bitlength. The AER problem is to find x,
given n e y, such that a portion (specifically, the n 3-most significant bits) of x e mod n equals
the corresponding part of y, i.e.,  xe mod n n   3  y n   3. The AER assumption is that there isno efficient algorithm for solving the AER problem.

 

The original version of ESIGN [11] proposed e 2 as the appropriate value for the public
key. Brickell and DeLaurentis [3] demonstrated that this choice was insecure. Their attack alsoextends to the case e 3; see Brickell and Odlyzko [4]. Okamoto [10] then revised the methodby requiring e  4. No weakness for these values of e have been reported in the literature.

 

The problem is related to the RSA problem which is one of finding x, given n e y, such thaty xe mod n . Clearly, if one can efficiently solve the RSA problem then one can also
efficient solve the AER problem. The submission conjectures that the RSA and AER problems are polynomial-time equivalent (and that the integer factorization and AER problems andpolynomial-time equivalent when e is even); however no proof of this is known.

  One way in which an adversary can break the scheme is to compute A’s private key p q fromA’s public key n e k . If this is done, the adversary can subsequently forge A’s signature on
any message of its choice.

   Problem Definition. The integer factorization problem is the following: given an integer n,determine the factorization of n.

Known algorithms for integer factorization
This subsection overviews the algorithms known for factoring and discusses how they can be
avoided in practice.
1. Trial division. Once it is established that an integer is composite, before expending vast
amount of time with more powerful techniques, the first thing that should be attempted
is trial division by all “small” primes. Here “small” is determined as a function of thesize of n. As an extreme case, trial division can be attempted by all primes up to n. If
this is done, trial division will completely factor n but the procedure will take roughly ndivisions in the worst case when n is a product of two primes of the same size.
5

Security level of cryptographic primitive problem

Page 6

2. Pollard’s rho factoring algorithm. Pollard’s rho algorithm is a special-purpose factoringalgorithm for finding small factors of a composite integer. Let f : SS be a randomfunction, where S is a finite set of cardinality m. Let x0 be a random element of S, andconsider the sequence x0 x1    defined by xi 1 f xi for i  0. Since S isfinite, thesequence must eventually cycle, and consists of a tail of expected length nπ 8 followed
by an endless repeating cycle of expected length nπ 8. A problem that arises in thefactorization problem is of finding distinct indices i and j such that x i x j . The expected
time for finding such a collision is O p where p is a prime factor of n.

  



3. Pollard’s p-1 factoring algorithm. Pollard’s p 1 factoring algorithm is a specialpurpose factoring algorithm that can be used to efficiently find any prime factors p ofa composite integer n for which p 1 is smooth with respect to some relatively small
B. Let n be an integer having a prime factor p such that p 1 is B-smooth.
The running time of Pollard’s p 1 algorithm for finding the factor p is O B ln n lnB modular
multiplication.



4. Elliptic curve factoring. The elliptic curve factoring method (ECM) has an expectedrunning time of O exp
2  o 1 ln p 1  2 ln ln p 1  2 to find a prime factor p of n. It
is the fastest factoring algorithm known when the running time is measured in terms of
the smallest prime factor of n, and is thus useful for finding factors of n in some situations
when n has a prime factor that is significantly smaller than the other prime factors of n.

   

5. Quadratic sieve factoring. The quadratic sieve factoring algorithm has the same expected running time as the elliptic curve factoring algorithm in the special case when n is
the product of two primes of equal size. However, for such numbers, the quadratic sieve
is superior in practice.
6. Number field sieve factoring. The general version of the number field sieve factoringalgorithm has an expected running time of O expc  o 1 ln n 1  3 ln ln n 2  3 tofactor n, where c is approximately 1  923. This is asymptotically superior to the quadratic
sieve factoring method. This superiority has also been validated by numerous researchers
through extensive experimentation.

   

7. Factoring n p2q. Although it is not known whether n p2 q is easier to factor thann pq, some special algorithms to factor n p2q have been studied in [1, 13]. These
techniques are specific to the elliptic curve factoring method, and are just several times
faster than the traditional ECM. The fastest algorithm known for factoring both integers
n of the form n p2q and n pq (where the primes p and q have the same bit length) is
the number field sieve (NFS) method, whose running time depends only on the bit lengthof n.
8. Factoring n pr q. Boneh, et al. [2] presented an algorithm for factoring n pr q withlarge r using the LLL algorithm. Their algorithm, however, is only effective for the casewhere r is large (at least log p 1  2). If r is constant or small, the running time of their6

Recommended parameters

Page 7algorithm is exponential in the bitsize of n. For nthan the ECM and NFS methods.

p2q, their algorithm is less efficient

Summary: If n is carefully chosen, namely n p2q where p and q are randomly chosen primesof the same bitlength which is at least 320 (so n has bit length at least 960), then all known
algorithms for factoring n are thwarted.

6

Recommended parameters

The recommended ESIGN parameters are as follows:
k: larger than or equal to 320 (the size of n should be more than 960 bits), ande: larger than or equal to 8.
In Table 1, the security levels of ESIGN with these parameters are compared with other submitted schemes, with RSA, and with symmetric schemes (e.g., the Advanced Encryption Standard–AES). Some of the comparisons among symmetric key cryptography, RSA security, and ECDSA
security are adapted from Lenstra and Verheul [8].

Symmetric
Key Size
4048
7680(SKIPJACK)112(Triple-DES)
128(128-bit AES)
192
(192-bit AES)
256
(256-bit AES)

Table 1: Rough Comparison of Security Levels
RSAESIGNACEECDSA
ModulusModulus
ModulusKey Size
Size
Size
Size

MY-ELLTY
Key Size
160
192

960

960

960

152

1024

1024

1024

160

2048

2048

2048

224

3072

3072

3072

256

7680

7680

7680

384

15360

15360

15360

512

7

Performance comparison

7

Performance comparison

Page 8

Table 1 presented comparable key lengths of several schemes. Generally, the ESIGN signaturescheme is faster than both ECDSA and RSA signature schemes with comparable key lengths.
ACE, RSA, and ESIGN have roughly the same public key size for comparable security level.
ACE and RSA have roughly  the same private key size for comparable security level. ESIGN’s
private key size is roughly 2 3 of the ACE (or RSA) private key size for comparable security
level. ECDSA and MY-ELLTY have significantly smaller key size for comparable security
level. However, the hash function used in MY-ELLTY is not collision resistant, thus it is notsecure against attacks on the hash function.

References

Page 9References[1] L.M. Adleman and K.S.McCurley. Open problems in number theoretic complexity II,
Proc. of ANTS I, LNCS 877, pages 291–322, 1995.
[2] D. Boneh. G. Durfee, and N. Howgrave-Graham. Factoring N
in Cryptology, Crypto 99, LNCS 1666, pages 326–337, 1999.

p r q for large r. Advances[3] E.F. Brickell and J.M. DeLaurentis. An attack on a signature scheme proposed by Okamato
and Shiraishi. Advances in Cryptology, Crypto 85, LNCS 218, pages 28–32, 1986.
[4] E.F. Brickell and A.M. Odlyzko. Cryptanalysis: A survey of recent results. G.J. Simmons,editor, Contemporary Cryptology: The Science of Information Integrity, pages 501–540,IEEE Press, 1992.
[5] R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. Proc.
of the STOC, pages 209–218, ACM Press, 1998.
[6] D. Estes, L.M. Adleman, K. Kompella, K.S. McCurley, and G.L. Miller. Breaking theOng-Schnorr-Shamir signature scheme for quadratic number fields. Advances in Cryptology, Crypto 85, LNCS 218, pages 3–13, 1086.
[7] A. Fujioka, T.Okamoto, and S. Miyaguchi. ESIGN: An efficient digital signature implementation for smart cards. Advances in Cryptology, Eurocrypt 91, LNCS 547, pages 446–457, 1991.
[8] A. Lenstra and E. Verheul. Selecting cryptographic key sizes. Distributed in the 3rd workshop on Elliptic Curve Cryptography (ECC 99). Available from http://www.cryptosavvy.
com/[9] A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC
Press, 1997.
[10] T. Okamoto. A fast signature scheme based on congruential polynomial operations. IEEETransactions on Information Theory, 36:47–53, 1990.
[11] T. Okamoto and A. Shiraishi. A fast signature scheme based on quadratic inequalities.
Proceedings of the 1985 IEEE Symposium on Security and Privacy, pages 123–132, 1985.
[12] H. Ong, C.P. Schnorr, and A. Shamir. An efficient signature scheme based on quadraticequations. Proceedings of the 16th Annual ACM Symposium on Theory pf Computing,pages 208–216, 1984.
[13] R. Peralta and E. Okamoto. Faster factoring of integers of a special form, IEICE Trans.
Fundamentals, E79-A, 4:489–493, 1996.