Introduction in cryptography

• The preface
• Base terminology
• The basic algorithms of enciphering
• Digital signatures
• Cryptographic hesh-functions
• Cryptographic generators of random numbers
• Degree of protection provided with the code number
• Криптоанализ and attacks on криптосистемы

The preface

In process of formation of an information society, technological means of total supervision of millions people become accessible to the large states. Therefore the cryptography becomes one of the basic tools providing confidentiality, trust, authorisation, electronic payments, corporate safety and uncountable set of other important things.

The cryptography is not more an idea of military men from which it is not necessary to communicate. Has come it is time to remove covers of mystery from cryptography and to use all its possibilities on advantage to a modern society. The cryptography wide circulation is one of few ways to protect the person from a situation when he suddenly finds out that lives in the totalitarian state which can supervise its each step.

Base terminology

In cryptographic terminology the initial message call in clear (plaintext or cleartext). Change of the initial text so that to hide from other its maintenance, name enciphering (encryption). The ciphered message name шифротекстом (ciphertext). Process at which from шифротекста the clear text is taken name decoding (decryption). Usually in the course of an encryption and decoding a certain key (key) is used and the algorithm provides that decoding can be made only knowing this key.

The cryptography - is a science how to provide privacy of the message. Криптоанализ - is a science how to open шифрованное the message, that is how to take a clear text without knowing a key. In cryptography are engaged криптографы, and криптоанализом are engaged криптоаналитики.

The cryptography covers all practical aspects of a confidential exchange with messages, including аутенфикацию, digital signatures, ecash and many other things. The cryptology - is the section of mathematics studying mathematical bases of cryptographic methods.

Algorithms share with key use on two classes: symmetric (or algorithms a confidential key) and асиметричные (or algorithms with an open key). A difference that symmetric algorithms use the same key for enciphering and for decoding (or the key for decoding is simply calculated on an encryption key). While asymmetric algorithms use different keys, and the key for decoding cannot be calculated on an encryption key.

Smmetrichnye algorithms subdivide on потоковые code numbers and block code numbers. Потоковые allow to cipher the information побитово while the block work with some set of bats of the data (usually the size of the block makes 64 bits) and cipher this set as a unit.

Dissymetric code numbers (also called by algorithms with an open key, or - - in more general plan - - cryptography with an open key) suppose, that the open key was доступн all (we will tell, it is published in the newspaper). It allows any to cipher the message. However decipher this message the necessary person (the one who owns a decoding key) can only. A key for enciphering name an open key, and a key for decoding - - the closed key or a confidential key.

Modern algorithms of an encryption/decoding are difficult enough also them it is impossible to spend manually. The present cryptographic algorithms are developed for use by computers or special hardware devices. In the majority of appendices the cryptography is made by the software and there is a set of accessible cryptographic packages.

Generally speaking, symmetric algorithms work faster, than dissymetric. On практке both types of algorithms are often used together: the algorithm with an open key is used to transfer in a random way generated confidential key which then is used for message decoding.

Many qualitative cryptographic algorithms are accessible widely - in a bookshop, library, patent bureau or in the Internet. Widely known symmetric algorithms concern DES and IDEA, Probably the best asymmetric algorithm is RSA.

Digital signatures

Digital signatures are used to confirm that the message has come really from the given sender (in the assumption that only the sender possesses the confidential key corresponding to its open key). Also signatures are used for putting down of a stamp of time (timestamp) on documents: the party to which we trust, signs the document with a stamp of time with помошью the confidential key and, thus, confirms that the document already existed during the moment declared in a stamp of time.

Digital signatures also can be used for the certificate (certification - - to certify) that the document belongs to the certain person. It becomes so: the open key and the information on the one to whom he belongs subscribe the party by which it is trusted. Thus to trust the signing party we can on the basis of that its key has been signed by the third party. Thus there is a hierarchy of trust. It is obvious that some key should be a hierarchy root (that is we trust it not because it is signed by someone, that is why that we believe a-priori that he can be trusted). In the centralised infrastructure of keys there is very much a small amount of root keys of a network (for example, the state agencies invested with authority; them also name certified agencies - - certification authorities). In the distributed infrastructure there is no necessity to have universal for all root keys, and each of the parties can trust the set of root keys (we will tell to an own key and keys, it signed). This concept carries the name of a network of trust (web of trust) and is realised, for example, in PGP.

The digital signature of the document is usually created so: from the document the so-called digest (message digest) is generated and to it the information on the one who signs the document, a stamp of time and other is added. The turned out line is ciphered further by a confidential key of this or that algorithm signing with use. The turned out ciphered set of bats also represents the signature. The open key of the signing is usually put to the signature. Whether the addressee at first solves for itself he trusts that the open key belongs to the one to whom should belong (by means of a network of trust or aprioristic knowledge), and then will decode the signature by means of an open key. If the signature was normally decoded, and its contents correspond to the document (the digest, etc.) the message is considered confirmed.

Some methods of creation and check of digital signatures are freely accessible. The most known is algorithm RSA.

Cryptographic hesh-functions

Cryptographic hesh-functions usually make values of 128 and more bits. This number much more, than quantity собщений which will ever exist in the world.

Many good cryptographic hesh-functions well free of charge. Widely known include MD5 and SHA.

Cryptographic generators of random numbers

In an ideal random numbers should be based on the present physical source of the casual information which cannot be predicted. Examples of such sources include rustling semi-conductor devices, younger bits of the digitized sound, intervals between interruptions of devices or pressing of keys. The noise received from a physical source then "is distilled" by cryptographic hesh-function so that each bit depended on each bit. Often enough for storage of the casual information enough big pool (some thousand bats) and each bit of a pool is used becomes dependent on each bit noise информаци and each other bit of a pool криптографически reliable (strong) in the way.

When there is no the present physical source of noise, it is necessary to use pseudo-random numbers. Such situation is undesirable, but often arises on general purpose computers. Always it is desirable to receive a certain noise of an environment - - we will tell from size of delays in devices, figures of statistics of use of resources, the network statistics, interruptions from the keyboard or something other. A problem is to obtain the data, unpredictable for the external observer. For achievement of it the casual pool should contain at least 128 bits of the present entropy.

Cryptographic generators of pseudo-random numbers usually use the big pool (seed-value) containing the casual information. Bits it is generated by sample of a pool with possible run through cryptographic hesh-function to hide contents of a pool from the external observer. When the new portion of bats is required, the pool mixes up by an encryption with a casual key (it it is possible to take from not used while pool parts) so that each bit of a pool depended on each other bit. New noise of an environment should be added to a pool before hashing to make a prediction of new values of a pool even more difficult.

In spite of the fact that at accurate designing криптографически the reliable generator of random numbers to realise not too difficultly, this question often lose sight. Thus, it is necessary to underline importance of the cryptographic generator of random numbers - - if it is made badly, it can is easy to become the most vulnerable element of system.

Degree of protection provided with the code number

Theoretically, any шифровальный the algorithm with key use can be opened by a method of search of all values of a key. If the key steals up a brute force method (brute force), demanded capacity of the computer grows экспоненциально with increase in length of a key. The key of 32 bits demands 2^32 (nearby 10^9) steps. Such problem under force to any layman also dares on the house computer. Systems with a 40-bit key (for example, an export American variant of algorithm RC4) demand 2^40 steps - - such computer capacities are available in the majority of universities and even in the small companies. Systems with 56-bit keys (DES) demand for opening of appreciable efforts, however can be easily opened by means of special equipment. Cost of such equipment is considerable, but is accessible to a mafia, the large companies and the governments. Keys in length of 64 bits at the moment, probably, can be opened by the large states and in the nearest some years will be already accessible to opening criminal организацими, the large companies and the small states. Keys in length of 80 bits can become vulnerable in the future. Keys in length of 128 bits possibly remain inaccessible to opening by a brute force method in the foreseeable future. It is possible to use and longer keys. In a limit it is easy to achieve that the energy demanded for opening (considering that is spent for one step minimum квантовомеханический energy quantum) will surpass weight of the sun or the Universe.

However, length of a key there is more to come. It is possible to open many code numbers and without touching all possible combinations. Generally speaking, it is very difficult to think up the code number with which it would be impossible to open in other more effective way. Working out of own code numbers can become pleasant employment, but for real appendices to use self-made code numbers it is not recommended if you are not the expert and are not assured for 100 percent that do.

Generally speaking, it is necessary to keep aloof from the neopublished or confidential algorithms. Often developer of such algorithm is not assured of its reliability, or reliability depends on privacy of the algorithm. Generally speaking, any algorithm, which privacy depends on privacy of the algorithm not явяется the reliable. In particular, having ciphering program, it is possible to employ прграммиста which дизассемблирует it and will restore algorithm a method of return engineering. Experience shows that the majority of the confidential algorithms which have become subsequently by property of the public, have appeared to ridiculous unreliable.

Lengths of the keys used in cryptography with an open key usually much more, than in symmetric algorithms. Here the problem consists not in key selection, and in a reconstruction of a confidential key on the opened. In case of RSA the problem is equivalent to decomposition on a multiplier of the big integer which is product of pair unknown simple numbers. In case of some other криптосистем, the problem is equivalent to calculation of the discrete logarithm on the module of the big integer (such problem is considered approximately to a problem of decomposition similar on difficulty on a multiplier). Are available криптосистемы which use other problems.

To provide guidance on degrees of complexity of opening RSA, say, that modules in length of 256 bits easily факторизуются usual programmers. Keys in 384 bits can be opened by research group of university or the company. 512-bit keys are within reach of the large states. Keys of 768 bits possibly will not be reliable long time. Keys of 1024 bits can be considered safe until will be essential progress in algorithm факторизации; keys of 2048 majority considers reliable for decades. More detailed information on lengths of keys RSA can be gathered from Bruce Shnajera's article (Bruce Scheier).

It is important to underline that degree of reliability of cryptographic system is defined by its weakest link. It is impossible to lose sight any aspect of system engineering - - from a choice of algorithm to a policy of use and distribution of keys.

Криптоанализ and attacks on криптосистемы

• Attack with knowledge only a text in code (ciphertext-only attack): It is a situation when attacking does not know anything about the message maintenance, and to it приходтся to work only with a text in code. In practice, it is often possible to make plausible assumptions of text structure as many messages have standard headings. Even usual letters and documents begin with easy предсказумой information. Also it is often possible to assume that some block of the information contains the set word.
• Attack with knowledge of contents of an encryption (known-plaintext attack): Attacking knows or can guess contents of all or parts of the ciphered text. The problem consists in decoding of other message. It can be made or by calculation of a key of an encryption, or passing it.
• Attack with the set text (chosen-plaintext attack): Attacking has возможнот to receive шифрованный the document for any text necessary to it, but does not know a key. A problem is the key finding. Some methods of enciphering and, in particular, RSA, are rather vulnerable for attacks of this type. At use of such algorithms it is necessary to watch carefully that the attacking could not cipher the text set by it.
• Attack with a support (Man-in-the-middle attack): Attack is directed on an exchange шифрованными by messages and, in particular, on the report of an exchange of keys. The idea consists that when two parties exchange keys for confidential communications (for example, using the code number of Diffi-Helmana, Diffie-Hellman), the opponent takes root between them on a line of an exchange of messages. Further the opponent gives out to each party the keys. As a result, each of the parties will have different keys, each of which is known to the opponent. Now the opponent will decipher each message the key and then to cipher it by means of other key before sending to the addressee. The parties will have illusion of confidential correspondence while actually the opponent reads all messages.

  One of ways to prevent such type of attacks consists that the parties at an exchange of keys calculate cryptographic hesh-function of value of the report of an exchange (or at least values of keys), sign its algorithm of the digital signature and send the signature to other party. The addressee will check up the signature and that value of hesh-function coincides with the calculated value. Such method is used, in particular, in system Foturis (Photuris).

• Attack by means of the timer (timing attack): This new type of attacks is based on consecutive measurement of times spent for performance of operation of erection in стенень on the module of an integer. Following code numbers are subject to it at least: RSA, Diffi-Hellman and a method of elliptic curves. The additional information look in original article and in set of followed articles.

Disclaimer. All opinions resulted here and conclusions are the subjective point of view of the author, and the author cannot bear responsibility for them ильность.