Staff :: Nosov Valentin Alexandrovich :: Publications of V.A.Nosov

History of Cryptography in Lomonosov Moscow State University

Valentin A. Nosov

See also: "Information Security: Teaching, Training, Research"

Introduction.

History of cryptography is a part of the military history. Cryptography is an area of science that studies methods of information concealment in order to prevent unauthorized access; it is a component of information security. Cryptography deals with the necessity to distinguish between those who receive information according to their rights on the access to the information. Cryptography is an ancient speciality; it is as old as the written language. In the course of its development, cryptography passed through the stages of handicraft, art, and became an area of science in the 1940s.

Cryptography can be conditionally divided into technical cryptography, which is connected with the design and operation of enciphering systems, and theoretical cryptography, which deals with the development of general methods, analysis of enciphering systems and substantiation of their reliability (reliability of a cipher is treated as its ability to resist attempts of breaking it; substantiation of a cipher consists in obtaining quantitative estimates for the costs of revealing the information enciphered with the help of it).

Cryptography involves advanced mathematical tools, which stimulates its development in many directions. For instance, modern cryptography widely employs the theory of probability, mathematical statistics, algebra, theory of numbers, mathematical logic, and discrete mathematics.

Evolution of cryptography.

Cryptography developed under the aegis of governmental services responsible for the security of information and, consequently, was confidential in large part. The personnel was taught and trained in cryptography by the governmental services themselves. At the same time, the development of the cryptography was promoted by people of various occupations; namely, scientists, military professionals, and politicians. Let us mention the most famous scientists who enriched cryptography with new ideas and methods.

In ancient times, cryptography fell within the range of interests of classics of science such as Pythagoras, Aristotle, and Plato; in the middle ages, it was studied by permanent mathematicians G. Cardano, F. Viete, J. Wallis; later, much attention was paid to cryptography by W. Leibniz, L. Euler, and Ch. Goldbach; and finally, a considerable progress of cryptography in the XX-th century is due to C. Shannon, A. Turing, and V. Kotel'nikov.

An eminent American engineer and mathematician Claude Elwood Shannon (1916-2001) in many respects contributed to the transformation of cryptography into a scientific discipline. His fundamental work "Communication Theory of Secrecy Systems" was prepared in 1946 as a confidential report, and was declassified and published in 1949. In that paper, Shannon proved, in particular, that only those ciphers can be perfect (absolutely reliable) which have the key uncertainty not less than the amount of information enciphered (in other words, the number of different keys is at least as great as the number of messages). He also gave examples of such ciphers, which were already familiar to practitioners.

A famous English mathematician Alan Turing (1912‑1954) formalized the concept of algorithm by putting it in the form of an abstract computer, which is now called Turing machine. He also designed a specialized machine for key testing, a participant of operation ULTRA.

Vladimir Aleksandrovich Kotel'nikov (1908‑2005), a prominent Russian scientist and radio engineer, in his work "Basic principles of automatic encryption" dated June 19, 1941, formulated and proved by mathematical means some necessary and sufficient conditions for the unbreakability of an enciphering system; namely, the interception of the ciphertext by the opponent should not change the probabilities of the keys being used.

Remarks on the history of cryptography in the USSR.

In 1917, after Russia has experienced a socialist revolution, cryptographers of the tsarist regime took the counterrevolution side. Soviet Government used both tsar and revolutionary ciphers, which caused a lot of trouble. In 1921, a special department was founded by the government, which had to deal with design and exploitation of ciphers. So, they have to start from scratch.

Role of MSU in cryptography.

Mathematicians of MSU have also made an appreciable contribution to the development of cryptography.

Andrei Andreevich Markov (1903‑1979) gave a classification of ciphers which do not propagate distortions. In mathematics, he is also known for the development of the theory of normal algorithms, which are now called Markov algorithms.

Aleksandr Osipovich Gel'fond (1906‑1968), who graduated from MSU in year 1927, investigated the complexity of the discrete logarithm problem long before works on this subject were published. In mathematics, he is known for the solution of Hilbert problem № 7 on transcendentality of degrees of algebraic numbers.

Andrei Nikolaevich Kolmogorov (1903‑1987), an MSU graduate of 1925, is known in mathematics for his fundamental findings in mathematical logic, functional analysis, and theory of probability. Of great cryptographic significance are his results on substantiation of the theory of information from the complexity viewpoint and on the concept of random sequence.

Cryptographic needs stimulated the development of many areas of discrete mathematics such as combinatorial analysis, Boolean functions, theory of finite automata, theory of permutation groups, and finite fields. A considerable contribution to the development of these directions was made by specialists of MSU.

In MSU, there are long-standing traditions of training specialists in cryptography. Many graduates of MSU were directed to work at the cryptographic service in pre-war years and during the war (1941‑1945). In the years of cold war, an important role in preparation of the personnel for the cryptographic service was played by the closed school at the Department of Mechanics and Mathematics of MSU. Let us give a scratch of its history.

On September 23, 1949, Council of Ministers of the USSR adopted resolution № 4028-1658cc on the organization of the closed school at the Department of Mechanics and Mathematics of MSU with the enrollment of 50 students per year. The classes of the school were open on February 1, 1950. The school enrolled most advanced senior students, which allowed the first graduation in 1951. Since the training of experts in this area was of high importance, a number of benefits were established by the governmental resolution. Graduates of the closed school received the diplomas of the Department of Mechanics and Mathematics of MSU.

The training was organized in accordance with the educational plan for mathematicians complemented by a number of special disciplines and a cycle of additional chapters of mathematics. The program of training included courses on additional sections of algebra, theory of probability, theory of numbers, theory of finite differences and, certainly, courses on cryptography.

During the existence period, the closed school graduated about 200 experts, a lot of which have subsequently grown into outstanding mathematicians and cryptographers. Among those who have finished the school, prominent mathematicians O.B. Lupanov, A.I. Kostrikin, and A.A. Borovkov should be mentioned.

New facets of cryptography.

From 1970s, the field of application of cryptography began widening and changing. Cryptography became a civil area of knowledge and was then applied to protect commercial information. For this purpose, appropriate standards of enciphering were designed. In 1976, American experts in computer science W. Diffie and M. Hellman published a revolutionary paper "New Directions in Cryptography". That work laid the foundations of the "public key cryptography". Public key systems exploit no secure channels for the distribution of confidential keys; instead, there is a channel for information interchange between a sender and an addressee. A certain procedure of such an exchange (protocol) makes it possible to produce a common confidential key.

From that moment, the number of open publications on cryptography began avalanching. This can be explained by three reasons. First, mathematical tools applied in construction and substantiation of ciphers have significantly widened. Secondly, the above mentioned ideas stimulated mathematical authorities' inquiring into problems of cryptography. Finally, cryptography began developing in new directions. For instance, there appeared a concept of one-way function, which can be easily calculated for any value of its argument whereas the value of the argument can hardly be restored by the value of the function. In cryptographic applications, this concept has transformed into the concept of a trapdoor function. Although the existence of one-way functions still remains unproved, a lot of candidates for such functions have been found and are used in construction of cryptosystems. Another direction in cryptography is the involvement of hard mathematical problems in substantiation of the reliability of ciphers. For instance, in the RSA cryptosystem (named after its inventors R. Rivest, A. Shamir, and L. Adleman), messages are encoded by integers and encryption consists in exponentiating the encoded message (raising it to a high power) and reducing the result modulo a certain number. The breaking of this system is related to the "discrete logarithm problem", which is so far unsolved (no effective algorithm has been found for taking discrete logarithms).

In that period, Soviet scientific investigations in the above mentioned directions seemed to fall behind. In order to amend the situation and catch up with the backlog, in MSU, the Laboratory of mathematical problems of cryptography was set up in 1990. The scientific activity of the laboratory included research in coding theory, complexity problems in cryptography, number-theoretic problems in cryptography, discrete functions in cryptography, and cryptographic aspects of automata theory. In addition, some special courses on information security for students were introduced.

At the present moment, MSU trains specialists in mathematical methods of information security: such specializations are open at the Department of Mechanics and Mathematics (0101123 "mathematical methods of information security") and at the Department of Computational Mathematics and Cybernetics (010213.01 "mathematical and software support of information security"). Students of these specializations also study fundamentals of cryptography as a special discipline.

Fall of Iron Curtain in cryptography.

A significant event in Russian cryptographic life was the conference "Moscow State University and Development of Cryptography in Russia" held in MSU on October 17‑18, 2002 (over 300 participants). The conference was dedicated to the 250^th anniversary of MSU, the 70^th anniversary of the Department of Mechanics and Mathematics, and the 50^th anniversary of the first graduate from the closed school.

The topics of the plenary meetings at the conference included