Digital signature

This article covers the technical / cryptographic term digital signature . In contrast, the article electronic signature deals with a legal term. More detailed information can be found in the section Differentiating from digital signature in the article on electronic signature.

A digital signature , also called digital signature method , is an asymmetrical cryptosystem in which a sender uses a secret signature key (the private key ) to calculate a value for a digital message (i.e. for any data), which is also called a digital signature . This value enables anyone to use the public key to verify the non-repudiable authorship and integrity of the message. In order to be able to assign a signature created with a signature key to a person, the associated verification key must be assigned to this person without any doubt.

With digital signatures, secure electronic signatures (Article 3 No. 10 to 12 of the eIDAS Regulation , until July 2017 in Section 2 of the Signature Act ) can be generated. However, the terms digital signature and electronic signature do not have the same content: First, electronic signatures (at least simple and advanced) do not necessarily have to be based on digital signatures; second, digital signature is a mathematical or technical term, while electronic signature is a legal term.

The basic principle

The signature is calculated from the data to be signed and the private signature key using a unique calculation rule. Different data must with almost certainty lead to a different signature, and the signature must result in a different value for each key. With deterministic digital signature methods , the digital signature is clearly defined by the message and the key; with probabilistic digital signature methods, random values ​​are included in the signature calculation so that the digital signature for a message and a key can take on many different values.

With a digital signature, the private key is usually not applied directly to the message, but to its hash value, which is calculated from the message using a hash function (such as SHA-1 ). To prevent attacks, this hash function must be collision-resistant , i.e. that is, it must be practically impossible to find two different messages with the same hash value.

If the public key has been assigned to a person by means of a digital certificate, the identity of the signature creator can be determined or checked via the public directory of the certification service provider (ZDA) due to the fact that there is only one private key corresponding to the public key. The entirety of the technical infrastructure with which the certificates and information about their validity are generated and made publicly available is referred to as PKI (Public Key Infrastructure).

A widespread misconception is that signing is encryption with the private key of an asymmetric encryption method. This assumption results from the fact that this is actually the case with a naive and insecure variant of RSA , namely “Textbook-RSA”. With secure variants of RSA (e.g. RSA-FDH , RSA-PSS , RSA-OAEP ) this is never the case despite certain similarities in details. With other encryption and signature methods, there are usually only very superficial similarities.

safety

With digital signatures it should be practically impossible to forge or falsify a signature or to generate a second message for which this signature is also valid. This assumes that the private key cannot be calculated from the digital signatures generated with it and the public key. However, it is possible that a digital signature process is insecure (i.e. that signatures can or can be forged) without the private key being able to be calculated. Is an example of RSA without using a hash function or padding: From the signature and the message and can be the signature of by the formula ${\displaystyle S(x)\equiv x^{d}{\bmod {n}}}$ ${\displaystyle S(y)\equiv y^{d}{\bmod {n}}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xy}$

${\displaystyle S(x\cdot y)\equiv (x\cdot y)^{d}\equiv x^{d}\cdot y^{d}\equiv S(x)\cdot S(y){\bmod {n}}}$

calculate without the private key being or being able to be determined.

Another important property of a signature procedure is the non-repudiation of the signature . If a signature was verified with a public key, it should also prove that the signature was generated with the associated private key. Many signature methods do not fulfill this property if the public verification key is not attached to the message before it is signed. Otherwise an attacker can generate a further key pair for a given signature with a matching verification key, with the verification key of which this signature is verified as valid (key substitution attack).

The security of a digital signature process depends primarily on the parameters selected; in particular, the keys must have a minimum length in order to ward off attacks. The security of a signature method also depends on the hash function used. This usually has to be collision-resistant in order to guarantee a secure digital signature. In addition, there are often effective attacks on certain implementations of (theoretically secure) digital signature methods, e.g. B. side-channel attacks or the determination of the private key from an inadequately protected personal security environment (PSE) .

The theoretical investigation of the security of digital signatures is the subject of cryptanalysis . Different attack targets and scenarios are considered. Evidence of security is usually based on a reduction in the security of a digital signature procedure to the difficulty of a known calculation problem .

Known procedures

By far the best known and most widely used digital signature method is RSA , for which various methods for filling the hash value ( padding ), such as the PSS standardized in PKCS # 1 , can be used. The security of RSA is based on the difficulty of breaking down large numbers into their prime factors ( factorization ). This is also the basis for the security of Rabin's signature process .

Many digital signature methods are based on the discrete logarithm in finite fields , such as B. DSA , the El-Gamal , the Schnorr signature , the Pointcheval star signature, XTR or the Cramer-Shoup signature . The security of ECDSA , ECGDSA or Nyberg-Rueppel signatures is based on the discrete logarithm in elliptic curves - these methods belong to the elliptic curve cryptosystems . All procedures that are based on the discrete logarithm (in finite fields or on elliptic curves) are probabilistic and use other public parameters in addition to the key length.

Other digital signature methods are based on linear codes , such as the McEliece-Niederreiter signature, or on grids , such as the Goldreich-Goldwasser-Halevi signature or NTRU. The Merkle signature uses hash trees and is based solely on the security of the hash function used.

Some digital signature methods have certain properties, such as: B. undeniable digital signatures ( undeniable signatures ) or blind signatures ( blind signatures ) where the signer does not know what he is signing; others make it possible to recover the signed message from the signature ( message recovery ), e.g. B. the Nyberg-Rueppel signature or RSA with the padding method according to ISO 9796.

In principle, any digital signature process can be combined with any hash functions as long as the length of the hash values ​​is suitable for the selected parameters of the signature process. However, international and national standards often also specify the hash function with the signature procedure (e.g. FIPS-PUB 186-2 ) or at least give recommendations (e.g. ANSI X9.62).

Legal norms

Germany

The Federal Network Agency published each year a list of minimum requirements for cryptographic algorithms and the creation of qualified electronic signatures . In the "Announcement on the electronic signature according to the Signature Act and the Signature Ordinance" of January 18, 2012, RSA, DSA and DSA variants based on elliptic curves (e.g. EC-DSA, EC-KDSA, EC-GDSA), recommended. For each of these methods, the minimum lengths for the keys and other requirements for the parameters and the hash function are specified.

United States

In the USA, the NSA publishes Suite B - a collection of valid cryptographic algorithms. This was last updated in 2005.

Use in practice

PGP systems

PGP stands for Pretty good Privacy and was developed by Phil Zimmermann from 1986 to 1991 . PGP is not an encryption algorithm itself, but a software product that combines many, sometimes quite complex, procedures for symmetrical and asymmetrical encryption and electronic signature.

PGP systems enable each communication partner to generate a key pair at any time. The trust in the assignment of the keys to a person should be guaranteed by a type of mutual electronic authentication. This creates a web of trust based on transitive trust relationships. If a person A to a person B familiar and that person B to a third person C. familiar, so this means that person A and person C familiar without there being an explicit trust relationship. The advantage of this method is the low requirements for the individual user.

This is also the great weakness of PGP. Bi-lateral keys and authenticity information for the key must be exchanged with each participant in a trustworthy manner. There is no general way of removing "lost" or known keys from circulation.

Common variants of the software originally developed by Phil Zimmermann are PGP (commercial) and GnuPG ( GNU-GPL ). The GNU Privacy Project took care of a GnuPG based graphical front end for all common operating systems. Since 2003 the project doesn't seem to have shown much activity. The WinPT (Windows Privacy Tools) program, which is also based on GnuPG, also offers a graphical interface under Windows for the convenient operation of digital signatures.

For the mail clients Mozilla Thunderbird , Mozilla Mail and Netscape Mail, there is the convenient Enigmail plug-in , which allows the user to use the encryption and signature functions provided by GnuPG directly in the mail program. The plug-in is open source and placed under the GNU GPL and the Mozilla Public License . The Bat program can also offer corresponding encryption and signing functions by default using OpenPGP .

Even with the v. a. The mail and groupware client Novell Evolution , which is widespread under Linux, allows the encryption and signature functions of GnuPG to be used directly and without plug-in. Evolution is also open source and is licensed under the GNU GPL.

The desktop suite KDE also allows the use of GnuPG in many of the supplied programs (e.g. Kopete and KMail ).

For the desktop environment Gnome , which is used, among other things, in Ubuntu , there is a frontend for GnuPG with Seahorse.

Certificate-based systems

In certificate-based systems, every user receives a digital certificate which contains information about his identity and the public key. Each certificate is certified by an issuing body, which in turn can be certified by higher authorities. The trust system of this PKI is strictly hierarchical. The common anchor of trust is a so-called root certificate.

Certificate-based systems fit in well with company hierarchies. Disadvantages are the high costs for construction and operation as well as the technical complexity of a public key infrastructure (PKI).

The S / MIME standard is based on digital certificates.

A certificate links data of a cryptographic key (or key pair, consisting of a public and a secret key) with data of the owner and a certification authority as well as other specifications such as version, period of validity, intended use and fingerprint . The definitions according to PKCS determine the content format, the standard X.509 (more precisely: ITU x.509 v3 according to RFC 3280 , based on ASN.1 format) describes the binary data format, often coded as DER or as DER- Base64 .

During web data exchange, the server transmits its certificate with the public key to the client. The client, in this case the user's web browser, checks whether it can trust the received certificate. To do this, he looks in the list of his certificates that were given to him during installation or that the user installed himself and tries to verify the signature of the server certificate with one of the certificates integrated in the browser. If the certificate could be verified, it starts an encrypted data transfer. Otherwise the user is asked via a dialog whether he wants to check and accept the certificate. It is fatal if a certificate, which is actually not trustworthy, is carelessly pronounced trustworthy.

Example: A fraudulent server pretends to be the house bank. During the first visit, the web browser realizes that it does not know the fraudster's certificate. The web browser user, because he doesn't know any better, clicks on Accept certificate . The fraudster's server and the user's client then communicate via a tap-proof web connection. The certainty of communicating with the right partner is no longer given due to the carelessness of the user in accepting the unknown certificate. Worse still: the fact that the browser saves the certificate not only classifies subsequent visits to the fraudulent server as safe, but also certificates that the fraudulent server has signed. In this case, one speaks of a persistent man-in-the-middle attack .

literature

• Alfred J. Menezes, Paul C. Van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography . CRC Press, Boca Raton FL et al. 1997, ISBN 0-8493-8523-7 .
• Judith Balfanz, Jan CE Wendenburg (ed.): Digital signatures in practice. Guide to process optimization and cost reduction in companies and authorities. AWV-Verlag, Eschborn 2003, ISBN 3-931193-47-0 .

Individual evidence

1. ^ Alfred Menezes, Nigel Smart : Security of signature schemes in a multi-user setting . In: Designs, Codes and Cryptography . tape 33 , no. 3 , 2004, ISSN  0925-1022 , p. 261-274 , doi : 10.1023 / B: DESI.0000036250.18062.3f ( uwaterloo.ca ).
2. ↑ most recently BAnz AT 02/01/2016 B5
3. ↑ Federal Network Agency for Electricity, Gas, Telecommunications, Post and Railways: Announcement on the electronic signature according to the Signature Act and the Signature Ordinance. (Overview of suitable algorithms). February 18, 2013, (PDF; 189 kB).

Web links

• Definitions of “digital signature” and “electronic signature” from the Marburg Archive School, with references, 2010
• Common PKI (formerly ISIS-MTT) interoperability specification and testbed for signatures

	This article is available as an audio file:
	Save | Information  | mm: ss min (29.3 MB) Text of the spoken version (March 14, 2015)
	More information on spoken Wikipedia