ESIGN

ESIGN ( English Efficient digital SIGNature - an effective digital signature) - a digital signature scheme with a public key , based on the problem of factorization of numbers. A distinctive feature of this scheme is the ability to quickly generate a signature. ^[one]

Content

History

The digital signature was developed at NTT in Japan in 1985. ^[2] The scheme proved to be effective in terms of the speed of digital signature generation. However, the first versions were cracked by Ernie Btickel and John DeLaurentis, after which the recommended algorithm parameters were modified. ^[3] Subsequent hacking attempts were unsuccessful. The authors claim that the complexity of hacking the latest version of ESIGN is comparable to the complexity of the problem of factoring a number $n$ ${\ displaystyle n}$ kind of $p^{2}q$ ${\ displaystyle p ^ {2} q}$ where $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ Are prime numbers . ^[four]

Protocol Description

Introduction

Two subjects are involved in the protocol: subject $A$ ${\ displaystyle A}$ whose purpose is to prove that he is the author of the message $m$ ${\ displaystyle m}$ , and subject $B$ ${\ displaystyle B}$ whose purpose is to verify authorship. At ESIGN to achieve your goals $A$ ${\ displaystyle A}$ and $B$ ${\ displaystyle B}$ must perform the following actions ^[5] .

Preliminary $A$ ${\ displaystyle A}$ generates keys : public, known to all, and private , known only to the subject $A$ ${\ displaystyle A}$ .
Subject $A$ ${\ displaystyle A}$ generates digital signature $s$ ${\ displaystyle s}$ for message $m$ ${\ displaystyle m}$ based on the private key.
$A$ ${\ displaystyle A}$ sends a message $m$ ${\ displaystyle m}$ with signature $s$ ${\ displaystyle s}$ subject $b$ ${\ displaystyle b}$ .
Subject $B$ ${\ displaystyle B}$ Validates the signature based on the public key.

Public and private key generation

ESIGN keys are generated as follows ^[6] .

Randomly selects two primes $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ same bit length.
The number is calculated $n=p^{2}q$ ${\ displaystyle n = p ^ {2} q}$ .
Selects a positive integer $k\geqslant 4$ ${\ displaystyle k \ geqslant 4}$ .
A pair of numbers $(n,k)$ ${\ displaystyle (n, k)}$ is a public key.
A pair of numbers $(p,q)$ ${\ displaystyle (p, q)}$ - private key.

Signature Generation

To sign a message $m$ ${\ displaystyle m}$ where $m$ ${\ displaystyle m}$ Is a binary number of arbitrary length, the following steps are taken ^[6] .

Calculated $\mu =h(m)$ ${\ displaystyle \ mu = h (m)}$ where $h$ ${\ displaystyle h}$ - a pre-selected hash function taking values from $0$ ${\ displaystyle 0}$ before $n-1$ ${\ displaystyle n-1}$ .
Random number selected $x$ ${\ displaystyle x}$ from interval $[0,pq)$ ${\ displaystyle [0, pq)}$ .
Calculated $\chi =\left\lceil {\frac {\mu -(x^{k}{\bmod {n}})}{pq}}\right\rceil$ ${\ displaystyle \ chi = \ left \ lceil {\ frac {\ mu - (x ^ {k} {\ bmod {n}})} {pq}} \ right \ rceil}$ and $\varkappa =\left({\frac {\chi }{k*x^{k-1}}}\right){\bmod {p}}$ ${\ displaystyle \ varkappa = \ left ({\ frac {\ chi} {k * x ^ {k-1}}} \ right) {\ bmod {p}}}$ where $\lceil \cdot \rceil \colon \mathbb {R} \to \mathbb {Z}$ ${\ displaystyle \ lceil \ cdot \ rceil \ colon \ mathbb {R} \ to \ mathbb {Z}}$ - function of rounding to the smallest integer, larger argument.
The signature is calculated $s=x+\varkappa pq$ ${\ displaystyle s = x + \ varkappa pq}$ .

Signature Verification

To verify that the signature $s$ ${\ displaystyle s}$ really signs the message $m$ ${\ displaystyle m}$ , the following steps are taken ^[6] .

Calculated $\mu =h(m)$ ${\ displaystyle \ mu = h (m)}$ where $h$ ${\ displaystyle h}$ - The same hash function that was used to generate the signature.
Calculated $\xi =\left\lceil {\frac {2}{3}}\log _{2}{n}\right\rceil$ ${\ displaystyle \ xi = \ left \ lceil {\ frac {2} {3}} \ log _ {2} {n} \ right \ rceil}$ .
Check for inequality $\mu \leqslant s^{k}{\bmod {n}}\leqslant \mu +2^{\xi }$ ${\ displaystyle \ mu \ leqslant s ^ {k} {\ bmod {n}} \ leqslant \ mu +2 ^ {\ xi}}$ .
A signature is considered valid if the inequality is satisfied.

Previous Versions

In the originally proposed ESIGN option, the parameter $k$ ${\ displaystyle k}$ was equal to two. ^[5] However, after the successful attack by Ernie Brickell and John DeLaurentis, which also extended to a variant of the scheme with $k=3$ ${\ displaystyle k = 3}$ , the authors changed the requirement for this parameter to the existing one $k\geqslant 4$ ${\ displaystyle k \ geqslant 4}$ . ^[7]

Cryptanalysis

Attack on a hash function

Hash Attacks $h$ ${\ displaystyle h}$ for the purpose of falsifying a signature, they are based on its imperfection, that is, on the hash function mismatching with one or more criteria of cryptographic strength with the caveat that in the case of ESIGN, equality in the criteria should be understood to the accuracy $(\log _{2}{n})/3$ ${\ displaystyle (\ log _ {2} {n}) / 3}$ high bits. This relief is due to the signature verification condition, which is satisfied not only for the initial value of the hash function, but also for the others that coincide in the first $(\log _{2}{n})/3$ ${\ displaystyle (\ log _ {2} {n}) / 3}$ high bits.

Assume that the function $h$ ${\ displaystyle h}$ unstable to search for collisions, that is, you can find such different $m$ ${\ displaystyle m}$ and $m^{'}$ ${\ displaystyle m '}$ , what $h(m)$ ${\ displaystyle h (m)}$ and $h(m')$ ${\ displaystyle h (m ')}$ match in the first $(\log _{2}{n})/3$ ${\ displaystyle (\ log _ {2} {n}) / 3}$ high bits. Then, signing the message $m$ ${\ displaystyle m}$ author $A$ ${\ displaystyle A}$ Suspecting nothing, automatically signs the message $m^{'}$ ${\ displaystyle m '}$ , since the inequality $h(m')\leqslant s^{k}{\bmod {n}}\leqslant h(m')+2^{\left\lceil {\frac {2}{3}}\log _{2}{n}\right\rceil }$ {\ displaystyle h (m ') \ leqslant s ^ {k} {\ bmod {n}} \ leqslant h (m') + 2 ^ {\ left \ lceil {\ frac {2} {3}} \ log _ {2} {n} \ right \ rceil}}

If the selected hash function is cryptographically strong, then an attack using collisions will take $2^{(\log _{2}{n})/3}$ ${\ displaystyle 2 ^ {(\ log _ {2} {n}) / 3}}$ hash function calculation operations, attack using the second prototype - $2^{(\log _{2}{n})/6}$ ${\ displaystyle 2 ^ {(\ log _ {2} {n}) / 6}}$ operations, which is considered impracticable, at large $n$ ${\ displaystyle n}$ . ^[8] ^[9]

Public Key Attack

Attack on the public key $(n,k)$ ${\ displaystyle (n, k)}$ consists in trying to get a private key based on it $(p,q)$ ${\ displaystyle (p, q)}$ . You can do this by solving the equation $n=p^{2}q$ ${\ displaystyle n = p ^ {2} q}$ , i.e. factoring the number $n$ ${\ displaystyle n}$ . You may notice that in RSA the number $n$ ${\ displaystyle n}$ generated in a similar way there $n=pq$ ${\ displaystyle n = pq}$ , but today the question of in which case factorization becomes easier or more complicated remains open, since there are still no effective factorization algorithms. Right now the fastest way to factor a number $n$ ${\ displaystyle n}$ that for ESIGN, that for RSA, is a sieve method of a number field that does this with a speed depending on the bit length $n$ ${\ displaystyle n}$ . However, with a large bit length of the number $n$ ${\ displaystyle n}$ the factorization task becomes impossible. ^[10] ^[9]

Recommended Options

In addition to the restrictions already introduced in the ESIGN description, it is recommended that you select a size $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ equal or greater $320$ ${\ displaystyle 320}$ bit size $n$ ${\ displaystyle n}$ equal or greater $960$ ${\ displaystyle 960}$ respectively, and the parameter $k$ ${\ displaystyle k}$ greater than or equal to 8 ^[11] :

$\log _{2}{p}\geqslant 320$ ${\ displaystyle \ log _ {2} {p} \ geqslant 320}$ ;
$k\geqslant 8$ ${\ displaystyle k \ geqslant 8}$ ;

Security level relative to other digital signature schemes

The table below shows the correspondence of the ESIGN security level to RSA and ECDSA security levels for various parameter sizes $n$ ${\ displaystyle n}$ in bits. You may notice that with the same size $n$ ${\ displaystyle n}$ RSA and ESIGN are comparable in terms of security. ^[12]

The size $n$ ${\ displaystyle n}$ in ESIGN, bits	The size $n$ ${\ displaystyle n}$ in RSA, bits	The size $n$ ${\ displaystyle n}$ in ECDSA, bits
960	960	152
1024	1024	160
2048	2048	224
3072	3072	256
7680	7680	384

Benefits

The ESIGN scheme allows you to quickly generate a signature. Since computationally complex operations such as exponentiation $(x^{k}{\bmod {n}})$ ${\ displaystyle (x ^ {k} {\ bmod {n}})}$ and finding the inverse element $(k*x^{k-1})^{-1}$ ${\ displaystyle (k * x ^ {k-1}) ^ {- 1}}$ are independent of the message being signed $m$ ${\ displaystyle m}$ , they can be carried out in advance and save the obtained values in memory. Thus, to sign a message, it is enough to perform the remaining operations of addition, multiplication and division, the proportion of which is small in the computational complexity of the signature creation algorithm . In the case when $k=4$ ${\ displaystyle k = 4}$ , and the bit length $n$ ${\ displaystyle n}$ is equal to $768$ ${\ displaystyle 768}$ signature generation speed in $10\div 100$ ${\ displaystyle 10 \ div 100}$ more than for RSA with the corresponding parameters. As for the verification of the signature, its speed is comparable to the speed of signature verification in the RSA algorithm , whose open exponent is small. ^[13] ^[9]

ESIGN-based authentication protocols

With ESIGN, zero-disclosure identification protocols can be implemented that allow the subject $P$ ${\ displaystyle P}$ ( Eng. Prover - proving) prove to the subject $V$ ${\ displaystyle V}$ ( English Verifier - checking) the fact of the availability of information, keeping it secret from $V$ ${\ displaystyle V}$ . ESIGN-based authentication protocols are not inferior to the Feig-Fiat-Shamir protocol in their effectiveness. We will consider two such protocols: three-round and two-round. ^[14]

Three Round Identification Scheme

$P$ ${\ displaystyle P}$ generates open $(n,k)$ ${\ displaystyle (n, k)}$ and secret $(p,q)$ ${\ displaystyle (p, q)}$ ESIGN keys.
$P$ ${\ displaystyle P}$ randomly selects numbers $r$ ${\ displaystyle r}$ and $u$ ${\ displaystyle u}$ calculates $x=f(r\|u)$ ${\ displaystyle x = f (r \ | u)}$ where $f$ ${\ displaystyle f}$ - one - way function , $\|$ ${\ displaystyle \ |}$ - concatenation operation, and sends $x$ ${\ displaystyle x}$ inspector $V$ ${\ displaystyle V}$ .
$V$ ${\ displaystyle V}$ randomly selects a number $y$ ${\ displaystyle y}$ and sends it to the reviewer.
$P$ ${\ displaystyle P}$ calculates $m=r\oplus y$ ${\ displaystyle m = r \ oplus y}$ generates a signature $s$ ${\ displaystyle s}$ for $m$ ${\ displaystyle m}$ and sends a three $(s,r,u)$ ${\ displaystyle (s, r, u)}$ to the inspector.
$V$ ${\ displaystyle V}$ checks equality $x=f(r\|u)$ ${\ displaystyle x = f (r \ | u)}$ and signature accuracy $s$ ${\ displaystyle s}$ for message $m$ ${\ displaystyle m}$ .

Two Round Identification Scheme

$P$ ${\ displaystyle P}$ generates open $(n,k)$ ${\ displaystyle (n, k)}$ and secret $(p,q)$ ${\ displaystyle (p, q)}$ ESIGN keys.
$V$ ${\ displaystyle V}$ randomly selects a number $r$ {\ displaystyle r} and sends it to the reviewer.
$P$ ${\ displaystyle P}$ randomly selects a number $u$ ${\ displaystyle u}$ calculates $m=f(r\|u)$ ${\ displaystyle m = f (r \ | u)}$ generates a signature $s$ ${\ displaystyle s}$ for $m$ ${\ displaystyle m}$ and sends $(s,u)$ ${\ displaystyle (s, u)}$ to the inspector.
$V$ ${\ displaystyle V}$ checks equality $m=f(r\|u)$ ${\ displaystyle m = f (r \ | u)}$ and signature accuracy $s$ ${\ displaystyle s}$ for message $m$ ${\ displaystyle m}$ .

In the above protocols, the secret information is keys $(p,q)$ ${\ displaystyle (p, q)}$ whose knowledge is proved by the subject $P$ ${\ displaystyle P}$ . If the results of all checks at the final stages are successful, then it is considered that $P$ ${\ displaystyle P}$ really has a secret.

Notes

↑ Menezes, Oorschot, Vanstone, 1996 , §11.7 p. 2, pp. 473–474.
↑ Minghua, 2001 , p. one.
↑ Schneier, 2002 , chapter 20, p. 6.
↑ Atsushi, 1991 , chapter 2, paragraph 3: "We conjective that to break our higher degree version (ESIGN) is as hard as facctoring N".
↑ ¹ ² Schneier, 2002 , chapter 2, paragraph 6.
↑ ¹ ² ³ Menezes, Oorschot, Vanstone, 1996 , §11.7 p. 2, p. 473.
↑ Menezes, Oorschot, Vanstone, 1996 , §11.9, pp. 486-487.
↑ Minghua, 2001 , p. 3.
↑ ¹ ² ³ Menezes, Oorschot, Vanstone, 1996 , §11.7 p. 2, p. 474.
↑ Minghua, 2001 , p. four.
↑ Minghua, 2001 , p. 6.
↑ Minghua, 2001 , p. 7.
↑ Atsushi, 1991 , chapter 3.
↑ Atsushi, 1991 , chapter 4.

Literature

Schneier B. Applied Cryptography. Protocols, algorithms, C source code = Applied Cryptography. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002 .-- 816 p. - 3000 copies. - ISBN 5-89392-055-4 .
Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Chapter 11. Digital Signatures // Handbook of Applied Cryptography . - 5th ed. - CRC Press , 1996 .-- S. 473-474. - 816 s. - ISBN 0-8493-8523-7 .
Atsushi Fujioka, Tatsuaki Okamoto, Shoji Miyaguchi. ESIGN: An Efficient Digital Signature Implementation for Smart Cards // Advances in Cryptology - EUROCRYPT '91: Conf. / Advances in Cryptology - EUROCRYPT '91, Brighton, Great Britain, April 8-11, 1991 .-- Springer Berlin Heidelberg, 1991 .-- S. 446-457 . - ISBN 978-3-540-54620-7 . (inaccessible link)
Alfred Menezes, Minghua Qu, Doug Stinson, Yongge Wang. Evaluation of security level of cryptography: ESIGN signature scheme : project materials / CRYPREC Project, Japan. - 2001. - January.

[_e85a624698acaedc-1] Menezes, Oorschot, Vanstone, 1996 , §11.7 p. 2, pp. 473–474.

[_f5af9d8b767acea2-2] Minghua, 2001 , p. one.

[_9cf85d91ed615248-3] Schneier, 2002 , chapter 20, p. 6.

[_6bfb894c155433de-4] Atsushi, 1991 , chapter 2, paragraph 3: "We conjective that to break our higher degree version (ESIGN) is as hard as facctoring N".

[_f23f21c6595050ae-5] ¹ ² Schneier, 2002 , chapter 2, paragraph 6.

[_c7c9cb3c902476b7-6] ¹ ² ³ Menezes, Oorschot, Vanstone, 1996 , §11.7 p. 2, p. 473.

[_d5a058aebafa937f-7] Menezes, Oorschot, Vanstone, 1996 , §11.9, pp. 486-487.

[_f5af9d8b767acea0-8] Minghua, 2001 , p. 3.

[_c7c9cb3c902476b0-9] ¹ ² ³ Menezes, Oorschot, Vanstone, 1996 , §11.7 p. 2, p. 474.

[_f5af9d8b767acea7-10] Minghua, 2001 , p. four.

[_f5af9d8b767acea5-11] Minghua, 2001 , p. 6.

[_f5af9d8b767acea4-12] Minghua, 2001 , p. 7.

[_3f940a2a255b4815-13] Atsushi, 1991 , chapter 3.

[_6e49712a40c66a4c-14] Atsushi, 1991 , chapter 4.