Cryptography

from Wikipedia, the free encyclopedia

Cryptography or cryptography ( ancient Greek κρυπτός kryptós , German 'hidden' , 'secret' and γράφειν gráphein , German 'write' ) is originally the science of encrypting information. Today she also deals in general with the topic of information security , i.e. the conception, definition and construction of information systems that are resistant to manipulation and unauthorized reading.

terminology

The term cryptography means secret writing. Historically, cryptography has dealt with the generation, consideration and description of procedures for “writing secretly”, i.e. with encryption procedures . They have been used for secure communication and secure calculations since the end of the 20th century.

Cryptanalysis (also cryptanalysis ), on the other hand, refers to the research and application of methods with which cryptographic processes can be broken ("cracked") .

A cryptosystem is used to keep transmitted or stored information confidential from third parties.

Often the terms cryptography and cryptology are used equally, while z. B. in the US military, cryptography mostly refers to cryptographic techniques and cryptology is used as a generic term for cryptography and cryptanalysis. Cryptography can therefore also be seen as a branch of cryptology.

Examining features of a language that are used in cryptography (e.g. letter combinations) is called cryptolinguistics .

Differentiation from steganography

Both cryptography and steganography aim to protect the confidentiality of a message. However, they differ in the approach of the procedure:

  • Cryptography encrypts the message . In this way, it ensures that an uninvolved third person who sees the (encrypted) data cannot grasp the meaning.
  • Steganographic processes hide the channel through which communication takes place. An uninvolved third person remains unaware of the communication .

Cryptographic and steganographic procedures can be combined. For example, an encryption (cryptography) of a message that is communicated via a hidden channel (steganography) means that the content of the message remains secret even after the channel has been discovered and successfully read out .

Goals of cryptography

Modern cryptography has four main goals for protecting data , messages and / or transmission channels:

  1. Confidentiality / access protection: Only authorized persons should be able to read the data or the message or obtain information about its content.
  2. Integrity / protection against changes: The data must be demonstrably complete and unchanged.
  3. Authenticity / protection against forgery: The originator of the data or the sender of the message should be clearly identifiable and his authorship should be verifiable.
  4. Liability / non-repudiation: The originator of the data or the sender of a message should not be able to dispute his authorship, i. That is, it should be proven to third parties.

Cryptographic methods and systems do not necessarily serve all of the goals listed here at the same time .

Methods of cryptography

Cryptographic methods are divided into the classic and modern methods.

  • Methods of classical cryptography: As long as no electronic computers were used for cryptography, complete letters or groups of letters were always replaced in encryption (at that time the only application of cryptography) . Such procedures are now outdated and unsafe.
  • Codebook , also a classic process.
  • Methods of modern cryptography: Corresponding to the way computers work, modern cryptographic methods no longer work with whole letters, but with the individual bits of the data. This significantly increases the number of possible transformations and also enables the processing of data that does not represent text. Modern cryptographic methods can be divided into two classes: Symmetrical methods, like classic cryptographic methods, use a secret key for each communication relationship and for all operations (e.g. encryption and decryption) of the method; asymmetric methods use one private (i.e. secret) and one public key per subscriber. Almost all asymmetric cryptographic methods are based on operations in discrete mathematical structures , such as B. finite bodies , rings , elliptic curves or grids . Your security is then based on the difficulty of certain computational problems in these structures. Many symmetrical methods and (cryptological) hash functions , on the other hand, are more of an ad-hoc construction based on bit links (e.g. XOR ) and substitution tables for bit sequences. Some symmetrical methods, such as B. Advanced Encryption Standard , Secret-Sharing or methods for stream encryption based on linear feedback shift registers , but also use mathematical structures or can be easily described in these.

History of cryptography

Classic cryptography

The earliest use of cryptography can be found in the third millennium BC. In ancient Egyptian cryptography of the Old Kingdom . Hebrew scholars used simple character exchange algorithms (such as the Atbash encryption) in the Middle Ages . In the Middle Ages , various secret scripts were in use all over Europe to protect diplomatic correspondence, such as the alphabetum Kaldeorum . Secret scripts were also in use for healing texts, for example to write down recipes against the syphilis that began to spread from 1495 .

At the end of the 19th century, the widespread use of the telegraph (which one could easily tap and eavesdrop on) led to new considerations in cryptography. Auguste Kerckhoffs von Nieuwenhof formulated a principle of cryptography with Kerckhoffs' principle , according to which the security of a cryptographic procedure should only depend on the secrecy of the key and not on that of the procedure. Rather, the process itself can be published and examined by experts for its suitability.

Cryptography in World War II

Brand sign of the German ENIGMA

During the Second World War, mechanical and electromechanical key machines such as the T52 or SZ 42 were used extensively, even if manual keys such as the double box key were still used in areas where this was not possible . During this time great advances were made in mathematical cryptography. However, this was necessarily done in secret. The German military made extensive use of a as ENIGMA known machine , which in 1932 by Polish and from 1939 by British code breaker broken was.

Modern cryptography

Beginning of modern cryptography

The age of modern cryptography began with Claude Shannon , possibly the father of mathematical cryptography. In 1949 he published the article Communication Theory of Secrecy Systems . This article, along with his other work on information and communication theory , established a strong mathematical basis for cryptography. This also ended a phase of cryptography that relied on the secrecy of the process in order to prevent or make decryption by third parties more difficult. Instead of this tactic - also known as security by obscurity - cryptographic procedures now have to face open scientific discourse.

Data Encryption Standard (DES)

The Feistel structure of DES

In 1976 there were two major advances. First, there was the DES (Data Encryption Standard) algorithm developed by IBM and the National Security Agency (NSA) to create a secure, unified standard for inter-agency encryption (DES was founded in 1977 under the name FIPS 46-2 ( Federal Information Processing Standard ) published). DES and more secure variants of it (3DES) are still used today. B. used for banking services. DES was replaced in 2001 by the new FIPS-197 standard AES .

Asymmetric cryptosystems (public key cryptography)

The second and more important advance was the publication of the article New Directions in Cryptography by Whitfield Diffie and Martin Hellman in 1976. This essay introduced a radically new method of key distribution and gave the impetus to the development of asymmetric cryptosystems (public key methods) . The key exchange has been one of the fundamental problems of cryptography up to now.

Before this discovery, keys were symmetrical, and possession of a key allowed a message to be both encrypted and decrypted. Therefore, the key had to be exchanged between the communication partners in a secure way, for example by a trustworthy courier or when the communication partner met directly. This situation quickly became unmanageable as the number of people involved increased. A new key was also required for each communication partner if the other participants were not able to decrypt the messages. Such a method is referred to as symmetrical or also as a secret key method or shared key method (shared secret).

In an asymmetric cryptosystem, a pair of matching keys is used. One is a public key which - in the case of an encryption process - is used to encrypt messages for the key holder. The other is a private key that must be kept secret by the key holder and is used for decryption. Such a system is called asymmetric , because different keys are used for encryption and decryption. With this method, only a single key pair is required for each participant, since possession of the public key does not compromise the security of the private key. Such a system can also be used to create a digital signature . The digital signature is calculated from the data to be signed or its hash value and the private key. The correctness of the signature - and thus the integrity and authenticity of the data - can be checked by appropriate operations with the public key. Public key methods can also be used for authentication in interactive communication.

On December 17, 1997, the UK Government Communications Headquarters (GCHQ) published a document in which they stated that they had found a public key process before the Diffie and Hellman article was published. Various documents classified as secret were published in the 1960s and 1970s and a. written by James H. Ellis , Clifford Cocks, and Malcolm Williamson , which resulted in designs similar to those of RSA and Diffie-Hellman.

Homomorphic encryption

A homomorphic encryption method allows calculations to be carried out on encrypted data. In 2009, the cryptologist Craig Gentry was able to prove that an encryption method exists that allows any calculations on encrypted data. Homomorphic encryption plays an important role in cloud computing . In order to avoid misuse of data when processing sensitive data, it is desirable that the service provider only counts on the encrypted data and never sees the plain text.

Cryptography and math

The security of most asymmetric cryptosystems relies on the difficulty of problems that are examined in algorithmic number theory . The best known of these problems are prime factorization and finding discrete logarithms .

Factorization

The security of factorization-based public key cryptography lies in the use of a product of large prime numbers which serves as the public key. The private key consists of the associated prime factors or values ​​derived from them. The decomposition of a sufficiently large number is considered impractical due to the very complex factorization .

Example for factoring
In plain words, it is despite sophisticated factorization difficult to a given number, which is the product of two large prime factors, eg. B. the number 805963 to find one of these factors. The computational effort to find a factor grows very quickly with increasing length of the number, which, if the numbers are large enough, means that the factorization would take thousands of years even on a supercomputer. In practice, numbers with several hundred decimal places are used. For the multiplication of large numbers, however, there are efficient algorithms; it is therefore easy to calculate the product (805963) from two factors (919 and 877). This asymmetry in the effort of multiplication and factorization is used in factoring-based public key processes. Cryptographically secure methods are those for which there is no better method of breaking security than factoring a large number; in particular, the private key cannot be calculated from the public key.

Further applications of number theory

In addition to the factorization problem, both the discrete logarithm problem ( Elgamal cryptosystem ) and advanced methods of algebraic number theory, such as encryption using elliptic curves ( ECC ), are widely used.

Another area of ​​application is coding theory , which in its modern form is based on the theory of algebraic function fields.

Future developments

The currently most important public key procedures ( RSA ), procedures based on the discrete logarithm in finite fields (e.g. DSA or Diffie-Hellman ), and elliptic curve cryptography could theoretically be broken down into polynomial time by so-called quantum computers thus lose their security.

Cryptography and society

In the age of the Internet, there was also a loud call for private encryption. So far, it has been governments and global corporations who have been able to use RSA encryption due to the need for powerful computers. The American physicist Phil Zimmermann then developed RSA encryption for the general public, which he called Pretty Good Privacy (PGP) and published it on Usenet in June 1991 . A new feature of this procedure was the ability to sign an email with a digital signature that clearly identifies the originator of the message.

Cryptography and law

Since modern, computer-aided processes make it possible for everyone to securely encrypt information, there is a need on the part of governments to be able to decrypt this information. In 1996, the US government examined whether proceedings could be initiated against the inventor of PGP, Phil Zimmermann, for illegal arms exports. However, she dropped the case after public protests. In the USA, as in many other countries, cryptography is subject to an export restriction law . In the USA, the Arms Export Control Act and the International Traffic in Arms Regulations regulate the export of cryptographic techniques.

Investigative authorities often only succeed in deciphering an item of evidence with the help of the private key. In various countries there are obligations to cooperate in the decryption of evidence. Sometimes the suspect is also required to reveal the key. In Great Britain , violators have been punished with long prison terms. According to critics, this contradicts the right to refuse to testify .

In France there was a law from 1990 to 1996 that required the key to be deposited with a “trustworthy authority”. Associated with this was a ban on other procedures and keys. However, a journalist who wanted to practice this did not succeed in finding a competent authority. After the law was relaxed in 1996, the use of certain cryptography methods is subject to approval. In Germany and the EU, too, there have been debates about legal control of cryptography for years. A ban on cryptography is impractical because the algorithms are known and anyone with the necessary programming knowledge could write a corresponding program themselves. Web applications such as B. electronic banking or shopping are inconceivable without cryptography.

In the context of digital rights management , cryptography processes are used, circumventing them (by means of cryptanalysis ) is a criminal offense.

See also

literature

Web links

Commons : cryptography  - collection of images, videos and audio files
Wiktionary: Cryptography  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. ^ Wilhelm Gemoll : Greek-German school and hand dictionary . G. Freytag Verlag / Hölder-Pichler-Tempsky, Munich / Vienna 1965.
  2. ↑ Norbert Pohlmann: Cyber ​​Security: The textbook for concepts, principles, mechanisms, architectures and properties of cyber security systems in digitization . Ed .: Springer Vieweg. 2019, ISBN 3-658-25397-5 .
  3. ↑ Oded Goldreich : Foundations of Cryptography, Volume 1: Basic Tools , Cambridge University Press, 2001, ISBN 0-521-79172-3
  4. ^ Wolfgang Ertel : Applied cryptography , 2nd, edited edition. Fachbuchverlag Leipzig in Carl Hanser Verlag, Munich / Vienna 2003, ISBN 3-446-22304-5 , p. 18
  5. ↑ Hans J. Vermeer : An old German collection of medical prescriptions in secret writing. In: Sudhoffs Archiv 45, 1961, pp. 235–246, especially p. 243 f.
  6. ^ W. Diffie, ME Hellman: New Directions in Cryptography . In: IEEE Transactions on Information Theory . tape 22 , no. 6 , 1976, p. 644–654 ( Other version [PDF; 267 kB ]).
  7. ↑ Craig Gentry: A Fully Homomorphic Encryption Scheme. (PDF; 952 kB) Stanford Crypto Group, August 1, 2009, pp. 169–178 , accessed on July 24, 2012 (English).
  8. ↑ Erich Möchel: NSA scandal drives encryption , ORF , November 11, 2013 - 4:19 pm
  9. ↑ Compare the references in en: Key disclosure law
  10. ↑ Christopher Williams: UK jails schizophrenic for refusal to decrypt files , The Register , November 4, 2009
  11. ↑ See Konrad Becker u. a .: The politics of the infosphere - World-Information.Org (= series of publications. Vol. 386). Bpb Federal Agency for Civic Education , Bonn 2002, ISBN 3-89331-464-4 , p. 160.