Digital signature schemes

From CryptoWiki
Jump to: navigation, search

Contents

Explanation

While the transmission of electronic documents or messages via unprotected channels can occur threatening their interception. An attacker can get an electronic document, modify it and send the original to the addressee in order to reap the benefits. To avoid such situations was developed digital signature. Properly applied digital signature gives the recipient confidence that current electronic document is reliable and it was sent by the specified sender. Digital signature for electronic documents is the analog of manual signature for paper media. A digital signature also provides non-repudiation property. This means that the document signer can't later deny his signature.

Properties

1) Authenticity , we see that this person signed the document.

2) Uniqueness, as hand signature, part of the document that cannot be moved to other documents. Any single document will have its own unique digital signature .

3) Integrity of the signed document , i.e., the inability to change the signed document.

4) Non-repudiation of authorship or consent to the contents of the document from the one in the future cannot be waived.

Schemes based on symmetric cryptography

The first who used a symmetric digital signature scheme (see symmetric digital signature scheme), were Diffie and Hellman. They published a description of the signature algorithm using one bit block cipher (see block cipher). Symmetric schemes are less common than asymmetric. Asymmetric digital signature scheme (see asymmetric digital signature scheme) based on computationally complex tasks. Symmetric ciphers based on block ciphers.

Symmetric schemes have the following advantages:

  • Persistence symmetric schemes stems from resistance of used block ciphers, the reliability of which has been well studied.
  • If the cipher strength is insufficient, it can easily be replaced by a more stable with minimal changes in the implementation.

Disadvantages symmetric schemes:

  • It is necessary to sign separate each bit of transmitted information, which leads to a significant increase signature. Signature may exceed the message size by two orders of magnitude.
  • Generated signature keys can be used only once, because after signing revealed half the secret key.

Digital signature protocol with reliable mediator

A user wants to sign a digital message and send it to user B. There is an intermediary, which has key k_1 for secret communication with the A key and k_2 for secret communication with B. These keys are installed before the protocol and can be used repeatedly. Encryption is using a symmetric cipher E.


Protocol steps:

1. A sender encrypts the message on the key k_1 for a destination B and sends the cryptogram to b mediator.

2. Mediator decrypts the cryptogram b, using the key k_1.

3. Mediator generates a block of information I = [a, b, pa], where a - decrypted message , b - copy of the cryptogram , pa - subscriber identity A. Encrypts a block of information I on the key k_2 and sends the cryptogram c to user B.

4. B decrypts the block of information I, using the key k_2. B received a message and intermediary certificate pa, certifying that the message came from A.

Protocol advantages:

1. Only the sender and the intermediary have A secret key k_1, so only A can send mediator a message encrypted in the key k_1. (Digital signature protection against counterfeiting )

2. Signature is not duplicated and signed document is immutable.

3. Signing cannot be denied (non-repudiation).

Schemes based on asymmetric cryptography

Definition

Digital signature scheme - a set of probabilistic polynomial-time algorithms (Gen; Sign; Vrfy), satisfying the following:

1) Key generation algorithm Gen takes as input a secret parameter ScreenShot 2.png and output issues (pk; sk; s0) - a public key , private key and the initial state , respectively. Assume that ScreenShot 12.png and n can be calculated from pk.

2) Signing algorithm Sign takes as input a secret key sk, value ScreenShot 15.png and message m. The output is a signature ScreenShot 18.png along with the value ScreenShot 16.png, and written as ScreenShot 13.pngSignScreenShot 14.png.

3) Deterministic algorithm for verifying signatures Vrfy takes as input the public key pk, message m and signature ScreenShot 18.png. As the output data is bit b, and is written as ScreenShot 17.pngVrfyScreenShot 19.png.

RSA

The first and most famous worldwide specific digital signature scheme became RSA system, the mathematical scheme which was developed in 1977 at MIT USA.

First need to calculate the key pair (private key and public key). For this the sender (author) of electronic documents calculates two large prime numbers p and q, then finds the result of multiplying them

N = p * q

and the value of the function f(N) = (p - 1)(q - 1).

Next, the sender computes value E from conditions:

E <= f(N), gcd(Е, f(N)) = 1

and value D from conditions:

D < N, E*D is comparable to the identity modulo f(N).

The pair of values (Е, N) is the public key. This pair of numbers the author conveys the partners correspondence to verify its digital signature. D retained by the author as a private key for signing.

Scheme of generation and verification of digital signature RSA

Assume that the sender wants to sign a message M before sending it. First, the message M is compressed by a hash function (see Hash Function) ​​h(M) by an integer m:

m = h(М).

Then calculate the digital signature S for the electronic document M using a hash value m and secret key D:

S = (m^D)(mod N).

Pair (M, S) is passed to the recipient partner as electronic document M digitally signed S, where S is formed owner of signature secret key D.

After receiving the pair (M, S), the recipient computes the hash value of the message M by two different methods. Above all, it restores the hash value m ', using cryptographic transformation of signature S by using a public key E:

m' = (S^E)(mod N).

Besides, it calculates a hash of the received message M using a hash-function h(M):

m = h(М).

If the equality of the calculated values​​, i.e.

(S^E)(mod N ) = h ( М ),

then the receiver recognizes the pair (M, S) genuine. It is proved that only the owner of the private key D can form a digital signature S for a document M and to determine secret value D by known value E is not easier than the decomposed module N factored. In addition, we can rigorously prove mathematically that the result of verifying the digital signature S will be positive only if the calculation of S was used secret key D, corresponding to the public key E. Therefore the public key E is sometimes called the "identificator" of the signatory.

RSA-PSS

RSA - PSS (Probabilistic signature scheme) - it is a probability digital signature scheme. Probabilistic version of the RSA scheme is a modification of the RSA function with a randomized filling. Signature scheme based on hash functions. In the RSA - PSS scheme signing procedure is transformation using a secret function RSA, as solely author owns the private key.


The key-generation algorithm

Signature and verification algorithms use two hash functions. The first function, which is called a compressor:

                         F 1.png

The second function is called generator:

                         F 2.png

(N, e, d, G, H, k_0, k_1) - digital signature parameters, where

(N, e, d) - RSA key parameters, (N, e) - public parameters, а d = e^(-1)(mod φ(N)) - secret parameters.

K= k_0+k_1

The singing algorithm

SingPss(M, d, N) =

  r = u{0,1}^k0; w = H(M || r); r* = G_1(w) XOR r;
  y = 0 || w || r* || G_2(w);
  return (U = y^d(mod N)).

Visually, the signature generation can be represented as follows:


The generation algorithm of RSA PSS digital signature
The verification algorithm

Given: M, U, e, N

1. U^e (mod N) = y;

2.We represent y as a string of bits b || w || r* || γ ;

3. r = r* XOR G_1(w);

4. If H( M || r) = w and

G_2(w) = γ and

b = 0

then digital signature is correct

Rabin signature scheme

Rabin signature based on a public key cryptography system. This system is based on the complexity of computing square roots by module n when this module is the result of multiplying two large prime values. Rabin cryptography scheme parameters:

p – prime number, p ≡ 3 mod 4, p – secret key;

q – prime number, secret key;

n = pq – public key of cryptographic system.

Creating a Signature

1. Generated random sequence R of length t bits

R = (r(0), r(1), …, r(t-1)),

r(i) ∈ {0,1}, i = 0, 1, …, t-1.

2. Message M is combined with the sequence R

M||R = (m(0), m(1), m(2), …, m(k-1), r(0), r(1), …, r(t-1) ).

3. Sequence of bits M | | R is placed in accordance value a < n.

4. Verifying the conditions a ^((p-1)/2) ≡ 1 mod p, a ^((q-1)/2) ≡ 1 mod q.

5. If the conditions are not satisfied, then go to step 1.

6. Computing values z ≡ a(p+1)/4 mod p, z ≡ a(q+1)/4 mod q.

7. According to Chinese remainder theorem calculated value

Z = a ^(1/2) mod n.

8. Is formed the signature of two numbers (R, Z) to the message M.

Signature verification

1. Computing value a´

a´ ≡ Z^2 mod n.

2. If a=a´, then the signature is accepted, otherwise rejected.

Schemes based on elliptic curves

The group of points of an elliptic curve (see elliptic curve), being originally an abstract algebraic object is used to construct a digital signature algorithm.

You can overlay restrictions on the set of values ​​of the variables x, y, and the coefficients a, b, c. Limiting the scope of the definition equation numerically significant for the application set (the field), we obtain an elliptic curve defined over the field under consideration.

A general view of an elliptic curve defined on the set of real numbers

Elliptic curve over finite field GF (p) is defined as the set of pairs (x, y), such that x, y ≡ GF(p), satisfying the equation:

y^2 = x^3 + ax + b mod p, a, b ≡ GF(p)

Pairs (x, y) are called points. Elliptic curve points can be added. The sum of two points, in turn, also lies on the elliptic curve.

Besides points on an elliptic curve, also considered the zero point. Believed that the sum of two points - A with coordinates (x', y') and B with coordinates (x*,y*) – is 0, if x' = x*, y' = –y* (mod p). Zero point does not lie on the elliptic curve, but, nevertheless, is involved in the calculations. It can be regarded as the point at infinity.

The set of points of an elliptic curve with zero point and introduced the addition operation will be called a "group." For each number of points of an elliptic curve in the group of course, but large enough. Estimation of the order (number of elements) of the elliptic curve m is as follows:

p + 1 – 2√p ≤ m ≤ p + 1 + 2√p,

where p - the order of the field over which the curve is defined. If the ElGamal scheme recommended by the order of 2 ^ p 512, in the case of an elliptic curve is enough to take p> 2 ^ 255.

Important role in the signature algorithm using elliptic curves play "multiple" point. Point Q is a point of multiplicity k, if for some point P k times the equality:

P = Q + Q + Q + … + Q = kQ

f for some point P there exists a number k, that kP = 0 , this number is called the order of P. Multiple points of the elliptic curve are analogous powers of the numbers in a simple box . The problem of calculating the multiplicity of terms is equivalent to computing discrete logarithms . Actually, on the complexity of calculating the " multiplicity " elliptic curve points and reliability based digital signature. Although the equivalence of the discrete logarithm problem and the problem of computing the multiplicity and proved , the second is more complex . Secret key , as before, put some random number x. Public key will be assumed coordinates of the point on the elliptic curve P, defined as P = xQ, where Q - specially chosen elliptic curve point (" reference point "). Coordinates of the point Q together with the coefficients of the equation defining the curve parameters are signature scheme and should be known to all participants messaging . Choice of Q depends on the algorithms used and very easy. Thus, standard GOST 34.10-2001 determines that the point Q must be of the order q, where q - prime with "good algebraic properties." The number q is quite large (2254 <q <2256). In constructing a specific algorithm that implements the computation of digital signature standard assumes the use of the algorithm DSA. Russia's new standard uses a modified version of the old GOST R 34.10-94.

GOST R 34.10-2012

Digital signature parameters

Parameters of digital signature schemes are:

– prime number p - module of an elliptic curve;

– elliptic curve E, defined by its invariant J (E) or the coefficients a, b;

- integer m - the order of the elliptic curve E;

- prime number q - the order of the cyclic subgroup of the elliptic curve E, for which the following conditions:

ScreenShot 22.png;

– point P ScreenShot 25.png O elliptic curve E, ​​with coordinates ScreenShot 23.png, satisfying the equality qP=O.

– hash-function ScreenShot 26.png, showing messages represented as binary vectors of arbitrary finite length, in binary vector of length l bits. Hash-function defined in GOST R 34.11. If ,2^254 < q < 2^256 than l = 256. If , 2^508 < q < 2^512 than l = 512.

Each user of the digital signature scheme must have personal keys:

- signature key - integer d, satisfying 0 < d < q;

- key signature verification - an elliptic curve point Q with coordinates ScreenShot 24.png, satisfying the equality dP = Q. For the parameters specified above digital signature schemes have the following requirements:

- Should be satisfied, for all integers t = 1, 2, … B, where B = 31, if 2^254< q < 2^256, and B = 131, if 2^508 < q < 2^512;

– must be following inequality holds mScreenShot 25.pngp;

– invariant of curve must satisfy J(Е)ScreenShot 25.png0 and J(E)ScreenShot 25.png1728.

Binary vectors

To determine the processes of generation and verification of digital signature is necessary to establish a correspondence between integers and binary vectors of length l bits.

Consider the following binary vector of length l bits, in which the least significant bits are located on the right, and senior - left:

ScreenShot 27.png (10)

where ScreenShot 28.png, i= 0 ,..,l - 1 is or 1, or 0.

The number corresponds to the binary vector ScreenShot 29.png, if have the equality

ScreenShot 30.png

For two binary vectors

ScreenShot 32.png (*)

corresponding integers and concatenation (union)is defined as follows:

ScreenShot 34.png (**)

Association is a binary vector of length 2l bits, consisting the coefficients of the vectors ScreenShot 35.png .

Formula (*) and (**) determine the method of partitioning a binary vector of length 2l bit two binary vectors of length l bits, of which he is the concatenation .

Digital Signature Generation Process

It is necessary to perform the following actions (steps) according to Algorithm I to obtain the digital signature for the message M belonging to V_all:

Step 1. Calculate the message hash code M:

H = h(M).

Step 2. Calculate an integer alpha, binary representation of whichis the vector H, and determine:

e = alpha (mod q ).

If e = 0, then assign e = 1.

Step 3. Generate a random (pseudorandom) integer k, satisfying the inequality:

0 < k < q.

Step 4. Calculate the elliptic curve point C = k * P and determine:

r = x_C (mod q),

where x_C is x-coordinate of the point C. If r = 0, return to step 3.

Step 5. Calculate the value:

s = (r * d + k * e) (mod q).

If s = 0, return to step 3.

Step 6. Calculate the binary vectors R and S, corresponding to r and s, and determine the digital signature zeta = (R || S) as a concatenation of these two binary vectors.

The initial data of this process are the signature key d and the message M to be signed. The output result is the digital signature zeta.

Digital Signature Verification

To verify digital signature for the received message M, it is necessary to perform the following actions (steps) according to Algorithm II:

Step 1. Calculate the integers r and s using the received signature zeta. If the inequalities 0 < r < q, 0 < s < q hold, go to the next step. Otherwise, the signature is invalid.

Step 2. Calculate the hash code of the received message M:

H = h(M)

Step 3. Calculate the integer alpha, the binary representation of which is the vector H, and determine if:

e = alpha (mod q)

If e = 0, then assign e = 1.

Step 4. Calculate the value:

v = e^(-1) (mod q).

Step 5. Calculate the values:

z_1 = s * v (mod q), z_2 = -r * v (mod q)

Step 6. Calculate the elliptic curve point C = z_1 * P + z_2 * Q and determine:

R = x_C (mod q),

where x_C is x-coordinate of the point.

Step 7. If the equality R = r holds, then the signature is accepted.

Otherwise, the signature is invalid.

The input data of the process are the signed message M, the digital signature zeta, and the verification key Q. The output result is the witness of the signature validity or invalidity.

Elgamal digital signature scheme

Generation parameters (keys)

1. Choose a random prime p.

2. Calculate the random generator of the multiplicative F 4.png

3. Choose x_A - secret integer satisfying x_A < p - 1

4. Calculate y_A = g^x_A (mod p)

Thus, (g, y, p) - a public key parameters. x_A - private key.

Signature generation

For digital signing a message m the user A generates a random number l such that l is less than p - 1 and gcd(l, p-1) = 1, and forms a pair (r, s), where

F 5.png

l^(-1) can be found using Euclid's algorithm.

Signature verification

User B must verify that your public key really belongs to the user A. To this end, the user B uses to the pair (m, (r, s)) the following procedure of verification:

F 6.png

Attacks and precautions

Attack №1

This attack was invented by Blaynbaher. If r> p, the attacker can forge a new signature arbitrary messages m 'as follows:

1. u = m'm^(-1) (mod p-1).

2. s' = su(mod p-1).

3. Compute r', satisfying r' ≡ ru(mod p-1) and r' ≡ r(mod p). This can be done using the Chinese Remainder Theorem.

The attacker performs the following operations:

F 7.png

Attack is impossible, if r <p, because in this case, r ', calculated on the third step of the Chinese Remainder Theorem in magnitude comparable to p (p-1).

Precaution

When verifying digital signatures, primarily it's need to check r <p.


Attack №2

This attack was invented by Blayhenbaher. G parameter cannot be selected by the user A. Suppose that g and p are chosen by the attacker. p can be chosen as follows: p-1 = bq, where q - a large prime number, and b - smooth number (in this case, the discrete logarithm in the group of order b is easily calculated)

Attacker creates an parameter as follows g = β ^ t (mod p), where β = cq and c <b. Thus, the discrete logarithm calculation does not create difficulties, and it is equal to z ≡ x_A (mod b), i.e. performed the following comparison:

F-8.png

Calculating z, the attacker can forge the signature of user A:

r = β = cq

s = t(m - cqz) (mod p-1)

Then,

F 9.png

Precaution

Must be checked at the stage of verifying the digital signature how much parameter g is random.

Lamport One-Time Signature Scheme

This is special kind of signature. One-Time signature remains safe with her one-time use for a particular message. Reuse is unsafe. At the heart of Lamport One-Time Signature is the use of one-way function.

Generation parameters

The input is a message m of length l bits.

For each bit i is performed the following operations:

1. Choose randomly x_i,0 x_i,1 of {0, 1}.

2. Calculate using one-way function f y_i,0 = f(x_i,0) и y_i,1 = f(x_i,1).

Forming public (pk) and secret (sk) keys:

F 10.png

Signature generation

Each bit of the message m = m_1 m_2 ... m_l is replaced according to the secret key obtaining the signature σ = (x_1, m_1; x_2, m_2; ...; x_l, m_l). Thus, instead of the i bit put x_i, m_i key value sk.

Signature verification

Public key pk, message m and signature σ = (x_1, ..., x_l) are known.

For each bit of the message m_i is checked whether the following condition: f (x_i) = y_i, m_i is correct. If the condition is performed for all message bits, the digital signature is considered correct.

Glossary

References

Go to references.


Pavlov P.,

Kochetov P.