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 XXth century is due to C. Shannon,
A. Turing, and V. Kotel'nikov.
An eminent American
engineer and mathematician Claude Elwood Shannon (19162001) 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 longstanding traditions of training specialists in cryptography. Many
graduates of MSU were directed to work at the cryptographic service in prewar 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 № 40281658cc 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 oneway 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 oneway 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, numbertheoretic 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
Cryptography
as an impetus to the development of mathematics,
Contribution
of MSU graduates to the development of cryptography and cryptographic education
in Russia;
There were
made a number of survey reports:

Mathematical
problems of computer security,

Outlook
for quantum communications,

Coding
theory and cryptography,

Theory
of numbers and cryptography,

Linear
recurrence sequences in cryptography, etc.
In our days,
there are more than a thousand Internet sites devoted to cryptography. Internet
resources of MSU on cryptography are basically presented on the web site www.cryptography.ru and on the web site www.intsys.msu.ru of the Chair Mathematical
Theory of Intelligent Systems (Department of Mathematics and Mechanics of MSU).
Conclusion.
Thus, the example
of MSU gives an idea of how the problem of training specialists in information
security has been solved at different times in the USSR and Russia by means of invoking civil educational institutions. This example is very illustrative when discussing
modifications of education systems. It is of particular importance for those
who are interested in information security for their own purposes. Now when
information technologies are so widespread (Internet, mobile communication),
the knowledge of methods of information security became the "third literacy".
Valentin A.
Nosov
Leading
Researcher
Chair of
MaTIS
To the top
