Session: Contemporary Mathematics, Cryptography and Modern Applications

The P versus NP problem
Jan Krajíček
Faculty of Mathematics and Physics, Charles University in Prague


Over a hundred years ago mathematics turned its attention onto itself and started to investigate its own foundations. One of the main mathematical concepts coming from this era is that of an algorithmically solvable mathematical problem. Examples of natural problems that are not solvable algorithmically were discovered.

With the development of computer science, it gradually became clear that it is not enough to distinguish algorithmically solvable problems from those that are unsolvable, but that it is necessary to take into account also the efficiency of algorithms. It became a fundamental issue how to measure the efficiency, how to determine for various problems what the most efficient algorithms are, or how to show that every algorithm solving a particular problem has to be inefficient. The modern name for this research area is computational complexity theory. It is believed that the right basic concepts were discovered and the key fundamental problems asked. The prototype of these problems is the most famous among them, the P versus NP problem. The significance of this problem can be hardly overstated.

In the talk I will attempt to explain what it is about, why it is so important, and what we know about it. I will not assume from the audience any specific knowledge except a general mathematical background.

Cryptography in Mobile Phones
Michal Hojsík
Faculty of Mathematics and Physics, Charles University in Prague


In this talk we look at the cryptography used in mobile phones. In the beginning we give an overview of the GSM with the focus on its security features. We describe stream ciphers A5/1 and A5/2 that were designed to ensure over-the-air voice privacy. Then we focus on cryptanalysis.

First, we describe an attack on A5/2 which is the weaker of the two algorithms and which is not supported in GSM anymore.

Second, we review several attacks on A5/1 (still in use) including a brute force attack used in the A5/1 Cracking Project and we look at the practicality of these attacks.

Finally, we describe the A5/3 block cipher KASUMI and its recent cryptanalysis.

After a short introduction of the background in logic, we try to underpin scope and limits of the logical approach by suitable theorems.

Quantum Cryptanalysis and Quantum Cryptography
Štepán Holub
Faculty of Mathematics and Physics, Charles University in Prague


Quantum phenomena offer interesting perspectives in the theory of computing, information processing and, consequently, cryptology. These have been explored intensively during the past three decades.

There are two opposite contributions the quantum mechanical approach can make to cryptology. The first one is the celebrated fact that prospective quantum computers would be able to effectively factorize integers, whereby breaking a large part of current security protocols. We touch upon the Quantum Fourier Transform that makes this possible.

The second contribution consists in providing a genuinely quantum key exchange protocol, which is secure thanks to fundamental properties of quantum measurement. We present the basic idea of the protocol and the sense in which it is claimed to be provably secure.

Despite a fairly well established theoretical framework, the factual impact of quantum cryptology is still very unclear due to technical difficulties. We briefly comment on the present situation concerning attempts to implement theoretic proposals of quantum information science.

Industrial applications of Cryptography
David Podhola
Vladímír Švagr
School of Computing, Prague College


In this talk we introduce some industrial implementations of cryptography. It is focusing on the electric power industry with specific aspects to power generation, transmission, distribution, and retail in nuclear powerplants. The implications of storing sensitive personal data, invoicing, and customer’s money transfers will be described and discussed.

Session: History of Cryptography

Veronika Douchová
Stefano Cavagnetto
School of Computing, Prague College


This talk is about the famous Enigma cipher machine that is well known for the vital role it played during WWII. We offer some descriptions of the various models, their manufacturers, some accessories and patents.

There is no such thing as the Enigma. In fact, Enigma is the brand name of a series of cipher machines that were developed before and during WWII, some of which are compatible with each other, and some of which are not. However, what we will try to do during this talk is to give a representation of the main idea behind it and its working principles and components.

In the last part of the talk we discuss the theoretical and practical strength of the Enigma machine, with a different number of rotors, by computing the key settings and configurations. This should offer an insight behind the motivation of why the machine was so trusted by its designers and led the German Army to place an undeserved confidence in its security.

The Polish Contribution to Breaking the Enigma Cipher
Jiří Tůma
Faculty of Mathematics and Physics, Charles University in Prague


TThe breaking of Naval Enigma was the turning point in the battle for the Atlantic during WWII. What is less known is that the Wehrmacht Enigma had been broken already at the end of 1932 by a group of Polish mathematicians. Their calculation of the internal structure of the Enigma machine by solving a system of equations in the symmetric group over 26 letters is one of the most remarkable events in the history of cryptology.

Moreover, between 1933 and 1938 they developed many sophisticated methods to recover daily keys to match up with the ever-changing protocol of using the Enigma machine and further improvements made by the German army.

Many of these methods also played important roles in British cryptanalysis success during the WWII.

The Turing Contribution to the Solution of Enigma
Bruce Gahir
School of Computing, Prague College


During the Second World War, Turing was a main participant in the efforts at Bletchley Park to break German ciphers. Building on cryptanalysis work carried out in Poland by Marian Rejewski, Jerzy Rozycki and Henryk Zygalski from the Cipher Bureau before the war, he contributed several insights into breaking both the Enigma machine and the Lorenz SZ 40/42 (a Teleprinter (Teletype) cipher attachment codenamed Tunny by the British), and was, for a time, head of Hut 8, the section responsible for reading German naval signals. He devised a number of techniques for breaking German ciphers, including the method of the Bombe, an electromechanical machine that could find settings for the Enigma machine.

In this talk we consider in detail Turing’s contribution in the construction of the Bombe. Loosely speaking, the idea behind the Turing Bombe is to make an initial assumption, draw logical deductions, and prove that it yields a contradiction. The assumption is that some specific rotor orders and rotor settings are correct. We then try to solve the problem with the plugboard settings (stecker connections). If there is no solution, the assumption must be wrong.

Cipher Machines during World War II. The German ENIGMA and the Small and Simple HAGELIN M-209 from the USA
Max O. Altmann


At the end of the 1930’s, Eastern Europe was a meeting place for emigrants, democrats and for people who were against Hitler and the war.

The main topics of the intellectual circles in the Cafes of Prague and Warsaw were war and peace. This is why former Czechoslovakia and Poland also were countries frequented by European secret services, mathematicians and cryptologists.

These illustrious intellectual circles knew that specialists of the Germans Armed Forces were working on a mysterious cipher machine - ENIGMA.

Up to 1934, the ENIGMA was still available on the free market for banks and big enterprises. Only after the German Armed Forces intensified their interest in this machine was it withdrawn from the free market.

History of Czechoslovak Army Solutionists in the Times of the Cold War
Jiří Janeček


  1. Deciphering service in the Czechoslovak people army,
  2. Cyphers of the Moravec London intelligence service in 1939 - 1945,
  3. Organization of army deciphering service after 1945,
  4. Accession of new powers, reorganisation in 1957,
  5. Mathematics and computers in deciphering - start in 1963 (ELLIOT 803-B, EPOS, MINSK-22, ZPA-600, HEWLETT PACKARD 9845-B + floppy disk, snimaˇ DP S-1500, dalnopis TRANSTEL),
  6. Few curiosities about deciphering.
StB Ciphering and Cryptoanalysis until the 70’s
Daniel Povolný


  1. StB (State Police) and ciphering from the beginning of the 50’s until the 70’s
    • Establishment and functions of the cipher service in Czechoslovakia
    • Production of ciphering materials for the StB
    • Development of the ciphering equipment and techniques for the security services
    • At the beginning of the 1950’s the ciphering services in Czechoslovakia was practically at its beginning. Everything was being developed under the Soviet model and with the use of Soviet ciphering material. Gradually the tendency to develop its own technology that would produce such material on the needed level grew. However, in spite of certain partial successes, suitable types of techniques for the highest level of security were not developed until the beginning of the 1970’s.
  2. StB and the nonstandard breaking of cyphers in the 50’s and 60’s
    • Operation K - infiltration into the Austrian consulate in Bratislava
    • Operation Šachová Hra (Chess game) - radio counter game against Intelligence Service
    • Operation Cikán (Gipsy), Mamut (Mammoth) - radio counter game of StB against Counterintelligence Corps
    • Operation Turista (Tourist) - discovery of the Bundesnachrichtendienst express transmitter
    • Together with standard deciphering, the StB also used either planned actions or accidents for getting a hold of ciphering materials from the western intelligence services. This talk will demonstrate concrete cases where the “human factor” failure made it possible for the StB to get a hold of these highly valuable materials..

Session: Secret Communication and Intelligence

Intelligence Organisations and the Media
Wilhelm Dietl
Covername: Dali


A very personal account of my life in the German foreign intelligence service BND. A rather individual report about the gathering of secret information in the Near and Middle East, in North Africa and South Asia during the period between 1982 until 1992.

How common is it that intelligence services use journalists to the point that they are run sources and even spy rings? The practical work, the risks, the dangers, the advantages of working for an intelligence service will be highlighted.

Is there a clash between individual moral and national security concerns? What if professional intelligence officers are posing as journalists? This talk is an intimate look at a very dangerous liaison and a world full of “mine fields”. And, finally, what happens after the service outs its own personnel?

Clandestine Communication and Cryptography in Germany during the Cold War
Detlev Vreisleben


Both German states (FRG, West Germany and GDR, East Germany) used similar methods for the communication with spies. Till 1958 “HV A” (Hauptverwaltung Aufklärung, Foreign Intelligence Service of the GDR) encrypted the messages with a Soviet cipher system (Double Transposition) which was broken by the West-German ”Verfassungsschutz”(Federal Office for the Protection of the Con- stitution).

Later on, the HV A used OTP. Concerning BND (Bundesnachrichtendienst, Foreign Intelligence Service of the FRG), it is only known that they used OTP. Both German states transmitted the encrypted messages by radio or sent letters with messages in invisible ink.

Radio counter-intelligence and radio intelligence as a means of capture of the cipher messages from the end of the 40’s until the first half of the 70’s
Daniel Povolný


Radio counter-intelligence (and radio intelligence) took up the prewar organisation and the work of its predecessor and considerably expanded them. Its main goal was to uncover the enemy’s radio stations within state territory. Due to the specific radio waves broadcast, the radio counter-intelligence services of the eastern block affiliated within the Coordination Group in 1955 in order to cooperate in this field. Since the express transmitters appeared in the 60’s of the 20th century, significance of the radio counter-intelligence has declined and it is focused mainly on the capture of diplomatic documents.

Ways of Connection for Foreign Agents in the Territorry of Czechoslovakia 1970 - 1990
Prokop Tomek


This talk will deal with the topic of the collaboration of the western intelligence services during the last 20 years of the existence of the totalitarian regime in Czechoslovakia.

Control of the society and connection with citizens abroad was very intensive. In spite of this, the counter-intelligence of the State Police did not achieve much success in uncovering these activities. Using a few concrete examples, we can become acquainted with the means of connection from the field of non-personal connection use at that time and the ways they were detected.

Situation in Organization, Management and Development of Cryptography in Czechoslovakia Shortly Before and After the Velvet Revolution
Oldřich Pekárek
Jiří Douša
Jaroslav Šmíd


It is a description of the situation in the organisation, management and development of cryptography in Czechoslovakia shortly before and after the “Velvet Revolution” in November 1989.

Defence Intelligence of the Czech Republic from Warsaw Pact to NATO
Andor Šándor


Defence Intelligence of the Czech Republic was not part of State secret police during the communist regime. It never worked against the citizens of Czechosloovakia and did not follow Czech emigrants abroad. Those two facts were decisive in the thought process of whether to dissolve it or not after the Velvet Revolution. It does not mean that it did not go through a number of measures that made it suitable to operate in a democratic state.

The first Gulf War, the war in Yugoslavia and the disintegration of the USSR showed a necessity to have intelligence provided by the soldiers for the leadership of the country as the only then functional service. The Defence Intelligence created many cooperation links with foreign counterparts and de facto became a member of NATO earlier then the country itself de jure.

Quantum of Necessary Concealment
Tomáš Weiss, Chair
Jan Schneider
Pavel Štalmach
Jaroslav Bašta


The panel will address the issue of concealment besides encryption as a technical matter; it is necessary to discuss the matter of what is getting encrypted (concealed) and why are powerful technical instruments almighty or where are their limits and what kind of roles are played by loyalty and the motivations of those involved.

We will talk about the paradox of concealment, when the unclassified documents are the safest because almost nobody reads them while the classified documents are in the focus of all because access to them is a indicator of your rank, personal prestige etc. The panel will address also the specific cases (e.g. Wikileaks).