Basics of Cryptography: Ancient Origins to Modern Techniques

Data Security and Cryptology, VI Basics of Contemporary Cryptography October 7th, 2015 Valdo Praust mois@mois.ee Lecture Course in Estonian IT College Autumn 2015

Two Stages of Cryptography Pre-computer cryptography or traditional cryptography (arvutieelne ehk traditsiooniline kr ptograafia). Uses paper-pencil or some simple mechanical devices (until 1940s). Was a tool only for military, diplomacy and intelligence areas (until 1970-80s). Uses empirical tehcniques (until 1949) Contemporary cryptology or computer- age cryptography, usually called only cryptography ((kaasaja) kr ptograafia). Uses computers as encrypting/breaking tools (since 1940s). Is an essential tool for each e-systems (since 1970-80s). Uses scientific-based algoritms(since 1949)

Essence of Traditional Cryptography Traditional or pre-computer cryptography (traditsiooniline ehk arvutieelne kr ptograafia) was a discipline which aim was a hiding of information (hiding meaning of data) for foreign or alien people by the way of strange writing The name of the discipline comes from the Greek name (like most of other classic disciplines): (kryptos) hidden (graph ) I write Cryptography means hidden word in Greek

Sources of Cryptography Cryptography derives probably from ancient times, when the writing was invented and there also arised a necessity to write down the information in a way that is understandable only by own people but and non- understandable for others (aliens) How old it actually is? An alphabet is some thousand years old (first used by Phoenicians), hieroglyphs are much older (at least 5000 years) Cryptography is probably also about 3000-5000 years old

The Oldest Known Utilization Fact Hieroglyphs on cliff-tomb of Egyptian Pharaoh Khnumhotep, which are completly different from other knows hieroglyphs from these times About 4000 years old (1900 BC)

Main Methods of Pre- Computer Cryptography, I substitution (substitutsioon) replacing of original characters (letters) by another characters (letters) transposition or permutation (transpositsioon, permutatsioon) changing the order of characters (letters)

Main Methods of Pre- Computer Cryptography, II The simplest pre-computer (ancient) ciphers were different variants of substitution or transposition ciphers. More complex ancient ciphers were certain combinations of substitution and transposition By the way, even a lot of modern (computer- age) cryptoalgorithms are still a complex combinations of substitution and transposition

An ENIGMA Cipher Machine ENIGMA was constructed by Germans during 1930s. ENIGMA ciphers was considered unbreakable in these times ENIGMA was a complex substitution-permutation cipher, where the key was an initial position of permutative rotors (usually there was 3 rotors) Rotor was disk with 26 electrical contacts on both side and realises a permutation of 26-letter alphabet

ENIGMA - A Breaking Story ENIGMA cipher was theoretically broken by a Polish cryptographer Rejewski in 1930s but it needed large amount of calculations (a lot of time and/or machine work) In 1943, a British matematician Alan Turing constructed a special electronic computer (first in world!) named COLOSSUS, which only aim was the breaking of ENIGMA ciphers This fact was kept secret for a long time (until the end of cold war in late 1980s) because COLOSSUS was made by British intelligence MI5

COLOSSUS Was built in 1943 in UK (MI5) especially for breaking ENIGMA ciphers Was a top secret device until 1980s Was the first electronic computer in world The exact functional copy of original COLOSSUS was built in UK in 1990s

End of Traditional Cryptography, I End of traditional cryptography was mainly caused by an appearing of electronic computer in 1940s (COLOSSUS, ENIAC), which has made a computational work thousands times faster than before It ended the era of pre-computer ciphers (crypotoalgorithms) and a traditional (pre-computer) cryptography Since 1940s for both during encryption and cipher breaking processe there was used (electronical) computers

End of Traditional Cryptography, II Around the same time with the appearance of electronic computers, Shannon published his information theory (1949). It led cryptology from previous empirical basis to scientific basis Since 1949 we can speak about contemporary (modern, scientifical) cryptography. It is a branch of applied mathematics. It is used as an useful tool for data security (both confidentiality and integrity)

A Tool for Diplomats and Warriors Traditional or pre-computer cryptography was used for a narrow purposes - for diplomacy, intelligence and military purposes The transition from paper-based into computer-based encrypting during 1940-50s did not change these traditional usage fields In many countries until 1970-80s the encryption equipment/devices was considered to be handled as weapons

1970-80s From Military to Commerce Use Mass-use of cryptographic means in commerce began together with the spread on wide-area computer networks (Internet) during 1970-80s where the transferred information confidentialy often needed a protection Additionally this process was heavily led by the invention of new types of cryptoalgorithms which aim is to protect integrity, not the (traditional) confidentiality

The Essence and Role of Contemporary Cryptology The aim of contemporary cryptology is not only confidentiality. The additional aim the avoiding of unauthorized changes (integrity) was added. Ensuring of integrity should be considered the main function of contemporary cryptology (ca 85% of its total usage) But the classical (Greek) name cryptography (a hidden word) has stille remained as a relict (even in these cases when the aim is not confidentiality)

1990s: Liberalizing of Cryptology The mass-usage of Internet (the early and mid 1990s) caused the final liberalizing of cryptographical means/devices use Last essential old relicts were: France - until the mid-1990s the cryptographivc devices usage were considered as weapons U.S.- until 1999 there was an export ban of unbreakable algorithms (algorithms with tke keylenght more than 40 bits)

Contemporary Cryptology as a Typical Tool of IT and Data Security Without the using of cryptographical tools as an essentials tools for protecting digital data, there s usually impossible to realize any information system. The observation of crypto-tools as weapons are lost forever already for long years Contemporary cryptology is a basic mean to protecting both the integrity and confidentiality of any digital data. For protecting the availabilty the cryptology has an auxiliary role

Contemporary Cryptography an Official Definition (Contemporary) cryptology ((kaasaja) kr ptograafia) is a discipline that embodies the principles, means, and methods for the transformation of data in order to hide their semantic content, prevent their unauthorized use, or prevent their undetected modification (Source: ISO 7498-2)

Basic Concepts of (Contemporary) Cryptology Encryptable (convertable from readable to unreadable form) text is called plaintext (avatekst) Encrypted text (the text which is already converted to unreadable form) is called ciphertext (kr ptogramm) The converting process from plaintext to ciphertext (from readable to unreadable form) is called encryption or encipherment (kr pteerimine, ifreerimine) The converting process from ciphertext back to plaintext (beck to readable form) under normal circumstances is called decryption or deciphering (de ifreerimine)

Basic Concepts of (Contemporary) Cryptology Usually both the enciphering and deciphering processes are performed by using a key or secret key (v ti, salajane v ti) Deciphering is a transforming of ciphertext into a plaintext using an appropriate key Successful transforming of ciphertext into a plaintext without a key is called breaking a cryptoalgorithm (kr ptoalgoritmi murdmine) In pre-computer (traditional) cryptoalgoritms the key was often undistinguishable from an algoritm itself

Format of Digital Data Format of (digital) data ((digi)andmete vorming) is the way, how different types of information are encoded using the actual bits (0 s and 1 s) Pre-agreed format gives meaning to data (in other words: associates data with the bearanle information) Conclusion: if we have data but we don t have information about the data format then we often don t have the (correct) information beared by data This fact serves as a base of cryptology (as a tool for confidentiality) when we create such a situation

Cryptography and Cryptalaysis Cryptography (kr ptograafia) is a set of data conversion methods (algorithms) which can protect confidentiality or integrity Cryptanalysis (kr ptoanal s) is a set of opposite tasks tasks for breaking these cryptosystems or -algorithms Cryptography and cryptalaysis together form (or can be called) as a cryptology (kr ptoloogia) which is usually considered as an unified discipline

Main Properties of Contemporary Cryptology, I Technical descriptions of all wide- spread cryptoalgoritms are usually public. All security usually bases on a secure key which is used in actual (practical) cases This allows to evaluate the algorthm s security for a wide range of independent experts (without having access to real confidential data which needs a key) In practice the security was usually evaluated by the cryptologists (kr ptoloogid) who are usually deep matematicians by the education and specialization

Main Properties of Contemporary Cryptology, II Contemporary cryptology uses always standardized algorithms which are worked out by cryptologists (matematicians). Composing of own algorithms by itself has been already history for a long times (and remains forever) Composing a secure (practically unbreakable) cryptoalgorithms needs a deep knowledge of cryptology and mathematics As longer the cryptoalgorithm has been in public use (has been available for testing by several experts/cryptologists), it s less probable, that there are some effective breaking (cryptoanalytic) methods

Main Properties of Contemporary Cryptology, III Contemporary cryptology uses computers. Encrypting with a paper and pencil has remained history already for a decades The speed of calculations is very important for both encrypting and cryptanalysis. Computers working performance is some millions times faster as human s performace using paper-pencil (GHz s versus 10 Hz) Cryptography (actually the whole cryptology) is one of the many applications of informatics

Main Properties of Contemporary Cryptology, IV Contemporary cryptology uses a lot of pre-agreed standards, which are same in all around the world Cryptography is a tool for securing of information systems, but IT tools (software and hardware) are same in all around the world An IT tool with a good (secure), but uncommon cryptoalgorithm is usually uncompatible with other IT infrastructure components (internet etc)

Main Types of Cryptoalgorithms 1. Symmetric cryptoalgorithms or secret-key crypotoalgorithms are traditional (historical) cryptoalgorithms 2. Asymmetric cryptoalgorithms or public-key crypotoalgorithms are widely spread within last 25-30 years 3. Cryptographic message digests and similar constructions 4. Special-purpose algorithms for proofing, authentication etc

Secret-Key Cryptoalgorithm Secret-key cryptoalgorithm (salajase v tmega kr ptoalgoritm) or symmetric cryptoalgorithm (s mmeetriline kr ptoalgorithm) is such a cryptoalgorithm where the same secret key is used both for enciphering and deciphering purposes Some famous examples: AES (128-, 192- or 256-bit key) IDEA (128-bit key) Skipjack (80-bit key) (DES (56-bit key)) ?

Role of Key in Enciphering and Deciphering Process Encrypting or encipherment (kr pteerimine, ifreerimine) needs the using of certain key as a pre-defined queue of bits Opposite process is a decrypting or deciphering (de ifreerimine), which needs a same key in order to restore the initial data (plaintext) from the encrypted text (ciphertext) Without the knowing of a key it s impossible to perform these processes

Secret-Key Cryptoalgorithm

Secret-Key Cryptoalgorithm Possibility to Break Secret-key cryptoalgorithm is considered to be practically secure if the keylength is at least 80 bits (for enhanced security cases 128 bits) DES is already considered insecure because its keylenght is only 56 bits (until 2005 it was allowed to use DES in triple mode as 3DES) Additionally to sufficient keylenght it is necessary that no effective cryptoanalytic attacks exist

Secret-Key Cryptoalgorithm: Fields of Use transmitting of confidential information using some (interceptable) networks secure storing of confidential information (with an appropriate key management system) secure erasing of confidential data

Secret-Key Cryptoalgorithm: Arised Problem Problem: if we use encryption as a tool for confidential information communication we must be able to deliver securely the used secret key Therefore we need a secure (non-interceptable) channel to deliver the secret key. We can t use a secret-key encryption for this purpose Using a courier service may be insecure. Delivering the key by the traveling is both very time- and money consumable

Public-Key Cryptoalgorithm Public-key cryptoalgorithm (avaliku v tmega kr ptoalgoritm) or asymmetric cryptoalgorithm (as mmeetriline kr ptoalgoritm) uses two keys if we encrypt using one key, we can decrypt it by another key These keys are mathematically related to each other but there s impossible in practice to found from one key another

Public-Key Cryptoalgorithm: Keys Keys of public-key cryptoalgorithm are called usually public key and private key (avalik v ti ja privaatv ti) Public key is usually known for all parties (is public) Private key is usually known only by a subject or a keypair owner (people, software, server, company, chipcard etc)

Most-of-Spread Public-Key Cryptoalgorithm: RSA The most-of-spread public-key cryptoalgorithm is RSA. RSA is considered to be practically secure with no less than 1024-bit keylenght ( in enhanced security cases no less that 2048-bit keylength) For RSA it is easy to calculate the public key from a private key, but it s practically infeasible to calculate the private from a public key Public and private key are mathematically related with each other, but the finding of private key using a public key needs for a typical computer million years or more

Public-Key Cryptoalgorithm: Usage For a key exchanging purposes. We can transmit a symmetric cryptoalgorithm s key in an encrypted manner without any tamper- proof channel. We only need that a public key must be really public For ensuring the integrity. This is the main usage of public-key cryptoalgorithm (and even the main field of contemporary cryptography) Public-key cryptoalgorithm gives a basic idea of a digital signature (digisignatuur, digiallkiri)

Public-Key Cryptoalgorithm: Key Exchange

Public-Key Cryptoalgorithm: an Idea of Digital Signing

Cryptographic Message Digest Cryptographic message digest (kr ptograafiline s numil hend) or cryptographic hash (kr ptor si) is a digest with a fixed small lenght which is calculated from a message by some deterministic mathematical one-way function One-way function ( hesuunaline funktsioon): is a function which is easily computable but the inverse function (p rdfunktsioon) is infeasible (impossible to compute in practice) For a given cryptographic hash value it s always impossible to find a corresponding message For a given message-hash pair it s impossible to modify a message in a way which remains the hash intact

Cryptographic Message Digest: Usage If we have a given message-hash pair and the hash corresponds to the message then we can always sure that the actual hash has been certainly calculated from the actual message Main usage of hashes are just ensuring the integrity (it usually helps the public- key algorithm to protect integrity) Practically secure hash functions find a hash which lenght is at least 160 bit (in enhanced security cases 256 bits)

Cryptographic Message Digest: Principle

Theoretical and Practical Security Theoretical security (teoreetiline turvalisus) is a situation where it s impossible to break the cryptoalgorithm even with the help of huge amount computational resources (time, processors etc) Practical security (praktiline turvalisus) is a situation where it s impossible to break crytpoalgorithm with a reasonable amount of resources (usually by mainframe hosts less than some years)

Theoretical versus Practical Security Conclusion from Shannon s information theory (1949): for thetheoretical security it s necessary that the keylenght is no less than the length of plaintext. This aim is achievable only for a symmetric cryptoalgorithms. Example: one-time-pad or Vernam s Cipher As a rule, almost all practical crypto- algorithms have only practical security Teoretically all of them are breakable within millions or billions of years

Typical Demands to Contemporary Cryptoalgorithms (by Ascending Strength), I 1. All security must be based on secret key, algorithm is usually publicly available (traditional Kerckhoff s assumption from 19th century) 2. Resistatnce to a known ciphertext attack (teadaoleva kr ptogrammi r nne). If we have only ciphertext we can t find neither plantext nor key

Typical Demands to Contemporary Cryptoalgorithms (by Ascending Strength), II 3. Resistatnce to a known plaintext attack (teadaoleva avateksti r nne). If we have a plaintext-ciphertext pair (some pairs), we can t find a used key 4. Resistatnce to a chosen plaintext attack (valitud avateksti r nne). If we can choose a plaintext and can receive get a corresponding ciphertext, we can t find a used key

Typical Demands to Contemporary Cryptoalgorithms (by Ascending Strength), III 5. Resistance to a adaptive chosen plaintext attack (adaptiivselt valitud avateksti r nne). If we can many times (adaptively) choose the plaintext and receive corresponding ciphertexts (all done with the same key), we can t find a used key. Contemporary cryptoalgorithms usually satisfy all these five classical demands

Basics of Cryptanalysis Cryptanalysis (kr ptoanal s) is a breaking of some mentioned five properties (demands) of an algorithm A more trivial way for a cryptanalysis is a testing of all key combinations. This technique is called an exhaustive search (ammendav otsing) For a N-bit key we have 2Ndifferent key variants. For a big N it is a very huge number. Therefore, an exhaustive search is infeasible to perform since a certain value of N. The typical (lower) limit is 80 it s infeasible to perform 280or more operations in practice

Basics of Cryptanalysis All these methods which permit to break a N-bit cryptalgorithm less than during 2N operations are called cryptoanalytic techniques A simplest way an exhaustive search is usually not considered to be a cryptoanalytic technique Usually the actual crypotoanalytic techniques are allowed in practice when they reduce the cryptoanalytic work only for 2, 4 or 8 times (needs consequently to consider 2N -1 , 2N-2 or2N-3 key variants). These are not considered as an effective cryptoanalytic means.

Practical Security of Algorithms A cryptoalgorithm is considered to be practically secure if we cannot perform an exhaustive search and there are no effective cryptoanalytic techniques available for all above- mentioned five types of attacks As longer the cryptoalgorithm is used in practice, the probability that these exists some effective cryptoanalytic (breaking) technique will became smaller. All cryptologists try always to found them But there increases a probability to break them by an exhaustive search (according to the Moore s rule)