Fast digital signature

Fast digital signature is a variant of digital signature that uses an algorithm with a much smaller (tenfold) number of calculations of modular arithmetic compared to traditional EDS schemes. A fast electronic signature scheme, like a regular one, includes an algorithm for generating key user pairs , a function for calculating a signature, and a function for verifying a signature.

EDS Problems

Since the invention of EDS in 1976, it has been the most promising field of research in public-key cryptosystems . One of the standard mathematical solutions for building cryptographic algorithms is the discrete logarithm problem, on the basis of which many algorithms for obtaining digital signature have been developed. The main drawback of traditional EDS algorithms , such as the El-Gamal and RSA schemes , is their computational complexity. Calculation of exponentials in modular arithmetic requires the largest computational cost in public key cryptosystems . Currently, a large number of works are underway to improve the performance of cryptographic algorithms by reducing the number of exponential calculations. The shortest known EDS scheme is BLS (Boneh - Lynn - Shacham), using elliptic curves , but it is limited to groups in which there is a pairing function . Algorithm developers work both on improving traditional discrete logarithm schemes using parallel exponential computations, and are studying fundamentally different approaches based, for example, on graph theory instead of modular arithmetic .

Some Fast Digital Signature Algorithms

Fast EDS based on the Diffie-Hellman algorithm

Let be $\ G$ ${\ displaystyle \ G}$ $\ G$ - abelian group , $\ G_{g,q}$ ${\ displaystyle \ G_ {g, q}}$ $\ G_{g,q}$ - its cyclic subgroup with generator $\ g$ ${\ displaystyle \ g}$ $\ g$ of order $\ q$ ${\ displaystyle \ q}$ $\ q$ where $\ q$ ${\ displaystyle \ q}$ $\ q$ Is a large prime . Let be $\ l_{q}$ ${\ displaystyle \ l_ {q}}$ $\ l_q$ and $\ l_{p}$ ${\ displaystyle \ l_ {p}}$ $\ l_p$ - security settings, moreover $\ l_{q}=|q|$ ${\ displaystyle \ l_ {q} = | q |}$ $\ l_q = |q|$ . Let be $H:{\{0,1\}^{*}}\rightarrow \ G_{g,q}$ ${\ displaystyle H: {\ {0,1 \} ^ {*}} \ rightarrow \ G_ {g, q}}$ $H: { \{0, 1\}^* } \rightarrow\ G_{g,q}$ , $L:{\{0,1\}^{*}}\rightarrow \ Z_{q}^{*}$ ${\ displaystyle L: {\ {0,1 \} ^ {*}} \ rightarrow \ Z_ {q} ^ {*}}$ $L: { \{ 0, 1 \}^*}\rightarrow\ Z_q^*$ and $G:{\{0,1\}^{*}}\rightarrow \ Z_{q}^{*}$ ${\ displaystyle G: {\ {0,1 \} ^ {*}} \ rightarrow \ Z_ {q} ^ {*}}$ $G: { \{0, 1 \}^*}\rightarrow\ Z_q^*$ - hash functions . The signature scheme is as follows:

Key generation

User selects a random secret key. $x\in \ Z_{q}^{*}$ ${\ displaystyle x \ in \ Z_ {q} ^ {*}}$ $x \in\ Z_q^*$ and calculates the public key $y=g^{x}$ ${\ displaystyle y = g ^ {x}}$ $y = g^x$ .

Signature Creation

The input is the secret key. $x\in \ Z_{q}^{*}$ ${\ displaystyle x \ in \ Z_ {q} ^ {*}}$ $x \in\ Z_q^*$ and message $m\in \{0,1\}^{*}$ ${\ displaystyle m \ in \ {0,1 \} ^ {*}}$ $m \in \{ 0, 1 \}^*$ .

Further, the party creating the signature:

1. selects a random number $k\in \mathbb {Z} _{q}^{*}$ ${\ displaystyle k \ in \ mathbb {Z} _ {q} ^ {*}}$ and random bit $b_{m}\in \{0,1\}$ ${\ displaystyle b_ {m} \ in \ {0,1 \}}$ ;

2. calculates $\ h=H(m,b_{m})$ ${\ displaystyle \ h = H (m, b_ {m})}$ ;

3. calculates $\ u=h^{x}$ ${\ displaystyle \ u = h ^ {x}}$ ;

4. calculates $\ v=(g^{n}*h)^{k}$ ${\ displaystyle \ v = (g ^ {n} * h) ^ {k}}$ where $\ n=L(m,g,h,y,u)$ ${\ displaystyle \ n = L (m, g, h, y, u)}$ ;

5. calculates $\ r=G(m,g,h,y,u,v)$ ${\ displaystyle \ r = G (m, g, h, y, u, v)}$ ;

6. calculates $s=k-xr\ mod\ q$ ${\ displaystyle s = k-xr \ mod \ q}$ .

Message signature $\ m$ ${\ displaystyle \ m}$ is an $\sigma \ =(u,r,s,b_{m})$ ${\ displaystyle \ sigma \ = (u, r, s, b_ {m})}$ .

Signature Verification

To verify the signature $\ \sigma$ ${\ displaystyle \ \ sigma}$ message m, the following is done:

one. $\ \sigma$ ${\ displaystyle \ \ sigma}$ appears as $\ (u,r,s,b_{m})$ ${\ displaystyle \ (u, r, s, b_ {m})}$ ;

2. is calculated $\ h=H(m,b_{m})$ ${\ displaystyle \ h = H (m, b_ {m})}$ and $\ n=L(m,g,h,y,u)$ ${\ displaystyle \ n = L (m, g, h, y, u)}$ ;

3. is calculated $v\prime \ =(g^{n}*h)^{s}*(y^{n}*u)^{r}$ ${\ displaystyle v \ prime \ = (g ^ {n} * h) ^ {s} * (y ^ {n} * u) ^ {r}}$ ;

4. checks to see if $\ r=G(m,g,h,y,u,v\prime )$ ${\ displaystyle \ r = G (m, g, h, y, u, v \ prime)}$ .

If the equality in step 4 is satisfied, the signature is verified.

Fast EDS based on the Fiat-Shamir algorithm

ZN denotes the ring of integers modulo $\ N$ ${\ displaystyle \ N}$ , $\ t$ ${\ displaystyle \ t}$ and $\ p$ ${\ displaystyle \ p}$ - security settings, usually $\ t\leqslant \ 4$ ${\ displaystyle \ t \ leqslant \ 4}$ , $\ p\leqslant \ 20$ ${\ displaystyle \ p \ leqslant \ 20}$

The role of the key authentication center (CAC)

CAC selects:

random primes $\ p$ ${\ displaystyle \ p}$ and $\ q$ ${\ displaystyle \ q}$ so that $\ p,q\geqslant \ 2^{256}$ ${\ displaystyle \ p, q \ geqslant \ 2 ^ {256}}$ ;

unidirectional hash function $\ h:Z_{N}\otimes Z\rightarrow \ {\{0,1\}}^{t}k$ ${\ displaystyle \ h: Z_ {N} \ otimes Z \ rightarrow \ {\ {0,1 \}} ^ {t} k}$ ;

your own private and public keys.

CAC publishes $\ N=p*q$ ${\ displaystyle \ N = p * q}$ , $\ h$ ${\ displaystyle \ h}$ and public key .

The CAC secret key is used to sign the public keys it creates. To create such signatures, the CAC can use any secure digital signature scheme.

Custom Key Generation.

Each user selects a secret key $\ s=(s_{1},\cdots \,s_{k})$ ${\ displaystyle \ s = (s_ {1}, \ cdots \, s_ {k})}$ consisting of random numbers $\ s_{i}$ ${\ displaystyle \ s_ {i}}$ , $\ s_{i}$ ${\ displaystyle \ s_ {i}}$ varies from 1 to $\ N$ ${\ displaystyle \ N}$ such that GCD $\ (si,N)=1$ ${\ displaystyle \ (si, N) = 1}$ for all $\ s$ ${\ displaystyle \ s}$ from 1 to $\ k$ ${\ displaystyle \ k}$ . Signature creation can be accelerated by choosing as $\ s_{1},\cdots \,s_{k}$ ${\ displaystyle \ s_ {1}, \ cdots \, s_ {k}}$ small integers . The security of such a scheme is based on the assumption that root computation $2^{t}\mod \ N$ ${\ displaystyle 2 ^ {t} \ mod \ N}$ is difficult. Currently unknown about the existence of algorithms that calculate the roots $2^{t}\mod \ N$ ${\ displaystyle 2 ^ {t} \ mod \ N}$ provided that these roots of order $\ N^{2^{-t+1}}$ {\ displaystyle \ N ^ {2 ^ {- t + 1}}} .

User registration.

CAC checks user compliance, creates a string $\ I$ ${\ displaystyle \ I}$ containing the name, address, etc., and creates a signature $\ S$ ${\ displaystyle \ S}$ for a couple $\ (I,v)$ ${\ displaystyle \ (I, v)}$ consisting of $\ I$ ${\ displaystyle \ I}$ and user public key $\ v$ ${\ displaystyle \ v}$ .

Create a signature.

Input message $\ m$ ${\ displaystyle \ m}$ secret key $\ s=(s_{1},\cdots \,s_{k})$ ${\ displaystyle \ s = (s_ {1}, \ cdots \, s_ {k})}$ and $\ N$ ${\ displaystyle \ N}$ - the module by which calculations are performed.

1. Choose a random number $\ r$ ${\ displaystyle \ r}$ out of range $\ [1,N]$ ${\ displaystyle \ [1, N]}$ is calculated $\ x=r^{2^{t}}$ ${\ displaystyle \ x = r ^ {2 ^ {t}}}$ .

2. Calculated $\ e=(e_{1}1,\cdots \,e_{t}k)=h(x,m)$ ${\ displaystyle \ e = (e_ {1} 1, \ cdots \, e_ {t} k) = h (x, m)}$ .

3. Calculated $\ y=r\prod \nolimits _{j=1}^{k}s_{j}^{\sum \nolimits _{i=1}^{t}e_{ij}*2^{i-1}}\mod \ N$ ${\ displaystyle \ y = r \ prod \ nolimits _ {j = 1} ^ {k} s_ {j} ^ {\ sum \ nolimits _ {i = 1} ^ {t} e_ {ij} * 2 ^ {i -1}} \ mod \ N}$ .

The signature on the output is a pair $\ (e,y)$ ${\ displaystyle \ (e, y)}$ .

Signature creation requires no more than $\ {k*t+t-1}$ ${\ displaystyle \ {k * t + t-1}}$ modulation operations, and on average for random $\ e$ ${\ displaystyle \ e}$ only required $\ t(k+2)/2+1$ ${\ displaystyle \ t (k + 2) / 2 + 1}$ multiplication operations.

Signature Verification.

Input - Signature $\ (e,y)$ ${\ displaystyle \ (e, y)}$ , message $\ m$ ${\ displaystyle \ m}$ , $\ v=(v_{1},\cdots \,v_{k})$ ${\ displaystyle \ v = (v_ {1}, \ cdots \, v_ {k})}$ , $\ I,S,N$ ${\ displaystyle \ I, S, N}$ .

1. Signature verified $\ S$ ${\ displaystyle \ S}$ for $\ (I,v)$ ${\ displaystyle \ (I, v)}$ .

2. Calculated $\ z=y^{2^{t}}\prod \nolimits _{j=1}^{k}v_{j}^{\sum \nolimits _{i=1}e_{ij}*2^{i-1}}\mod \ N$ ${\ displaystyle \ z = y ^ {2 ^ {t}} \ prod \ nolimits _ {j = 1} ^ {k} v_ {j} ^ {\ sum \ nolimits _ {i = 1} e_ {ij} * 2 ^ {i-1}} \ mod \ N}$ .

3. It is verified that $\ e=h(z,m)$ ${\ displaystyle \ e = h (z, m)}$ .

Signature verification requires an average for random $\ e$ ${\ displaystyle \ e}$ $\ t(k+2)/2+1$ ${\ displaystyle \ t (k + 2) / 2 + 1}$ multiplication operations modulo maximum $\ {k*t+t}$ ${\ displaystyle \ {k * t + t}}$ .

Signature Security.

To fake a message signature $\ m$ ${\ displaystyle \ m}$ cryptanalyst must solve the equation $\ e=h(y^{2^{t}}\prod \nolimits _{j=1}^{k}v_{j}^{\sum \nolimits _{i=1}^{t}e_{i,j}*2^{i-1}},m)\mod \ N$ ${\ displaystyle \ e = h (y ^ {2 ^ {t}} \ prod \ nolimits _ {j = 1} ^ {k} v_ {j} ^ {\ sum \ nolimits _ {i = 1} ^ {t } e_ {i, j} * 2 ^ {i-1}}, m) \ mod \ N}$ for $\ e$ ${\ displaystyle \ e}$ and $\ y$ ${\ displaystyle \ y}$ .

There are currently no algorithms for solving this equation.

Application of fast EDS

Fast digital signature algorithms are most effective in cases where the key acquisition speed and small signature size are of primary importance. Similar requirements occur in mobile, sensor or personal networks (the radius of which is limited to one room) when transmitting multimedia traffic. The use of a digital signature in GSM mobile phones allows users to create a PIN code on their own, rather than receiving it from an operator.

Implementation of accelerated EDS algorithms for devices with limited resources, such as PDAs, built-in smart cards and mobile phones, whose computing power is much inferior to the capabilities of personal computers, will allow you to spend less energy on creating and storing a signature and thereby increase the device’s battery life without recharging .

Literature

Fast Digital Signature Schemes as Secure as Diffie-Hellman Assumptions, Changshe Ma , Jian Weng and Dong Zheng , January 22, 2007

Fasr Signature Generation with a Fiat Shamir-Like Scheme, H.Ong , CPSchnorr

Links

US Patent 5,263,085