Digital Signature

 

What’s that – a digital signature?

A digital signature is a data string which associates a message (in digital form) with

some originating entity.

 

What’s a digital signature for?

A digital signature of a message is a number dependent on some secret known

only to the signer, and, additionally, on the content of the message being signed. Signatures must be verifiable; if a dispute arises as to whether a party signed a document (e.g. caused by either a lying signer), an unbiased third party should be able to resolve the matter equitably, without requiring access to the signer’s secret information (private key).

Digital signatures have many applications in information security, including authenti-cation, data integrity, and non-repudiation. One of the most significant applications of digital signatures is the certification of public keys in large networks. Certification is a means for a trusted third party (TTP) to bind the identity of a user to a public key, so that at some later time, other entities can authenticate a public key without assistance from a trusted third party.

 

How do we create a digital signature?

There exist several procedures to generate a digital signature. The first method discovered was the RSA signature scheme, which remains today one of the most practical and versatile techniques available. Subsequent research has resulted in many alternative digital signature techniques (e.g. Rabin, Nyberg-Rueppel), but we concentrate on RSA.

 

RSA-Algorithm to generate the keys:

  1. Generate two large distinct random primes p and q
  2. Compute n = pq
  3. Compute a = (p - 1)(q – 1)
  4. Select a random integer e with the following conditions:

- 1 < e< a

- gcd(e; a) =1     (gcd: greatest common divider)

  1. Use the extended Euclidean algorithm (see exercises) to compute the unique integer d with the following condition;

- 1 < d< a

- ed = 1 (mod a)

  1. now, n and e are the public keys, d is the private key

 

RSA-Algorithm to verify the signature and recover the message from the signature:

  1. Signature generation for a message m:
  2. compute m’ = R(m),
  3. compute s = (m’)d (mod n).
  4. The signature for the message m is s

Verification of s:

  1. Obtain the authentic public keys n and e,
  2. compute m’ = se (mod n),
  3. verify that m’ is an element of MR ist, if not, reject the signature.
  4. Recover m = R-1(m’)

 

additional explanations:

The redundancy function R and its inverse R-1 are publicly known. It adds redundant information to the message m. If M is the quantity of all possible messages m, then MR is the quantity of all messages m out of M after having executed the redundancy function R.

Example: a message contains eight figures. So M is the quantity of all messages containing eight figures. R is a function which adds a ‘5’ at the end of the message. now MR is the quantity of all messages containing nine figures and ending with a ‘5’. R-1 cuts off the last figure of a message. Obviously: m = R-1(R(m)).

 

RSA-Example:

key generation:

  1. p = 23, q = 13
  2. n = 23 * 13 = 299
  3. a = 22 * 12 = 264
  4. e = 53, correspond to the conditions 1 < e < a und ggT(e, a) = 1
  5. for e * d – y * a = 1 (y positive integer) we find d = 5 and y = 1
  6. n = 299 and e = 53 are the public keys, d = 5 the private key

 

signing the message m = 9:

  1. R is a function which concatenates a message with itself. so m’ = R(m) = 99
  2. s = (m’)d (mod n) = 995 mod 299 = 86
  3. s = 86 is the signature of m

 

verification of s = 86:

  1. n = 299 and e = 53 are the public keys
  2. m’ = se (mod n) = 8653 mod 299 = 99
  3. m’ = 99 looks like a message that has been concatenated with itself, so the signature is valid.
  4. R-1 cuts the redundant part of m’ and we recover m: R-1(m’) = R-1(99) = 9