Introduction to Cryptology
Cryptography Basics Cryptographic systems
Signature schemas
Computer Security - collection of tools designed to protect data and to prevent hackers from succeeding.
Network Security - measures to protect data during their transmission. Internet Security - measures to protect data during their transmission over a collection of interconnected networks.
Goals of Information Security Confidentiality – ensuring that no one can read the message except the intended receiver Authentication – the process of proving one’s identity Integrity – assuring the receiver that the received message has not been altered in any way from the original
Non-repudiation – a mechanism to prove that the sender really sent this message.
What is Cryptology ?
Cryptography: the science that studies the mathematical techniques for keeping messages secure. Cryptanalysis: the science of defeating cryptography. Cryptology: the science that studies cryptography and cryptanalysis.
•
•
•
•
Cryptology is crucial to achieve Information Security Many challenging problems that have impact on every day life It covers a broad range of Mathematics and Computer Science We still have serious security gaps
Basic notions A cipher is a secret method of writing, where by plaintext is transformed into a ciphertext. The process of transforming plaintext into ciphertext is called encryption. The reverse process of transforming ciphertext into plaintext is called decryption. Encryption and decryption are controlled by cryptographic keys. 7
A brief history of Cryptography The oldest forms of cryptography date back to Ancient Egypt, when derivations of the standard hieroglyphs were used to communicate. Julius Caesar (100-44 BC) used a simple substitution cipher with the normal alphabet in communications with his army (Caesar cipher).
Thomas Jefferson, the father of American cryptography, invented a wheel cipher in the 1790’s which was used by the US Navy during World War II. 8
A brief history of Cryptography During World War II, two notable machines were used: German’s Enigma machine (A. Scherbius) Japanese Purple Machine (H. O. Yardley) W. Friedman, the father of American cryptanalysis, led a team which broke in 1940 the Japanese Purple Code. In the 1970s, H. Feistel developed ciphers while working at IBM Research Laboratory. In 1976, NSA worked with the Feistel ciphers to establish FIPS PUB-46, known today as DES.
9
A brief history of Cryptography
In 1976, M. Hellman and W. Diffie (1) have introduced the concept of public-key cryptography. In 1977, R. Rivest, A. Shamir and L. Adleman proposed the first public-key cipher based on the factoring problem (RSA cryptosystem). In 1985, T. El Gamal (2) proposed the first public-key cipher based on the discrete log problem.
(1) New Directions in Cryptography, 644 IEEE Transactions on Information Theory, Vol. 22, 1976 (2) A Public key Cryptosystem and A Signature Scheme based on discrete Logarithms , IEEE, 1985
10
A brief history of Cryptography
In 1984 Shafi Goldwasser and Silvio Micali proposed the first provably-secure probabilistic public-key encryption scheme. In 2009 Craig Gentry made a breakthrough discovery by proposing the first fully homomorphic cryptosystem (FHE). In 2010 Marten van Dijk, Gentry, Shai Halevi and Vinod Vaikuntannathan invented another homomorphic cryptosystmem based on so called approximate GCD.
Cryptographic system Definition. A cryptographic system or a cipher is a 5-tuple S = (P, C,K, E,D) where • • • •
P is a non-empty finite set of plaintext symbols C is a non-empty finite set of ciphertext symbols K is a non-empty finite set of keys E and D are two sets of functions
E = {eK : P C | K K } and D = {eK : C P | K K } such that dK(eK(x)) = x for any K K and x P. 12
Cryptographic system
P plaintext
ek
C ciphertext
dk
M plaintext
dk(ek (x))=x for k K
Cryptosystem requirements: • Efficient encrypting/decrypting algorithm. • System must be easy to use. • The security of the system depends only on the keys, not the secrecy of ek or dk 13
Secure cipher
Unconditionally secure A cipher is unconditionally secure if no matter how much ciphertext is intercepted, there is not enough information in the ciphertext to determine the plaintext uniquely. Computationally secure A cipher is computationally infeasible to break.
14
Cryptosystems
Message Source
P
C Encryption
P Decryption
Receiver
Secure Key Transmission
Symmetric or private-key cryptosystems characterized by the fact that the key is shared between the sender and the receiver and is kept secret .
Cryptosystems
Message Source
P
C
P
Encryption eK
Decryption dk
Public Key E
Secret key D
Receiver
Public key or assymetric key cryptosystems characterized by the fact that to each participant is assigned a pair of keys: E - public key and D - secret key.
Symmetric key cryptosystems: 1. In the case of multiple persons, multiple keys are needed 2. If key is stolen, security is lost 3. Handing over keys must be strictly controlled 4. Faster algorithms Public-key cryptosystems: 1. More secure 2. Slower algorithms
Digital Signatures Digital signatures are PKC that provide: • Authenticity • Integrity • Non-repudiation
Any public-key cryptosystem can be used for making digital signatures. Signing (encrypting with a private key) is very slow. The technique for time-saving and space saving step before signing is called message digesting or hashing. 18
Hash Functions A hash function is a function which applied to an arbitrary-length input data produces a fixed-length and short output data called a hash value or message digest.
Hash function requirements: • It should be hard to reverse a hash function. • Given a hash value it should be hard to identify a possible input data. • It should be hard to find two inputs that collide in their hash values. Hashing algorithms: MD4, MD5, SHA, SHA-1
19
Digital Signatures
An attempted cryptanalysis is called an attack. General type of attacks Ciphertext-only attack: The attacker has the ciphertext only. Known-plaintext attack: The attacker knows a plaintext and its ciphertext, and he knows another ciphertext, but not the corresponding plaintext. 21
Chosen-plaintext attack: The attacker has a temporary access to the encryption machinery. Chosen-ciphertext attack: The attacker has a temporary access to the decryption machinery.
