chapter 2
chapter 2
chapter 2
Fundaments of Cryptography
1
Outline
• Cryptography
• Symmetric and asymmetric encryption
• Caesar cipher, Vigenère encryption
• Cryptanalysis
• Block vs Stream Ciphers
• Substitution-Permutation Ciphers
• Cryptographic Algorithms
2
Cryptography
• Cryptography, a word with Greek origins, means “secret writing.”
• However, we use the term to refer to the science and art of
transforming messages to make them secure and immune to
attacks.
4
Services Provided by Cryptography
• Confidentiality
– provides privacy for messages and stored data by hiding
• Message Integrity
– provides assurance to all parties that a message remains
unchanged
• Non-repudiation
– Can prove a document came from X even if X denies it
• Authentication
– identifies the origin of a message
– verifies the identity of person using a computer system
5
Relevance of Cryptography
• The applications of Cryptography
– Cash machines ATM, money transfer between
banks
– Electronic cash, online banking, secure email
– Phone cards, cell phones, remote controls
– Cloud, IoT
– Crypto currency
– Electronic Signature
– Secure communication
– End-to-end encryption
– Military communications
– Electronic commerce
– Computer Passwords
6
Cryptography Components
• Cryptography has five components:
- Plaintext: This is what you want to encrypt.
- Ciphertext: The encrypted output.
- Enciphering or encryption: The process by which plaintext is
converted into ciphertext.
- Encryption algorithm: The sequence of data processing steps
that go into transforming plaintext into ciphertext.
- Secret Key: is used to set some or all of the various parameters
used by the encryption algorithm.
- Deciphering or decryption: Recovering plaintext from
ciphertext.
- Decryption algorithm: The sequence of data processing steps that
go into transforming ciphertext back into plaintext. 7
Keys
• A key can be thought of as 010100111
simply a collection of bits 0
• The more bits, the stronger the 101111011
key 101100101
• Keys are tied to specific
encryption algorithms
• Lengths vary depending on the
encryption algorithm
– e.g. 128 bits is long for some
algorithms, but short for
others
8
Cryptography…
• Encryption Overview
– Plain text is converted to cipher text by use of an
algorithm and key.
• Algorithm is publicly known
• Key is held private
– Three Main Categories
• Secret Key
– single key is used to encrypt and decrypt information
• Public/Private Key
– two keys are used: one for encryption (public key) and one for
decryption (private key)
• One-way Function
– information is encrypted to produce a “digest” of the original 9
information that can be used later to prove its authenticity
Encryption
• Encryption is the process of
taking some data and a key
and feeding it into a function
and getting encrypted data
out
Encryption
• Encrypted data is, in
Function
principle, unreadable unless
decrypted
10
Decryption
• Decryption is the process
of taking encrypted data
and a key and feeding it
into a function and getting
out the original data
– Encryption and decryption
functions are linked
Decryption
Function
11
Encryption Techniques
Symmetric Encryption
14
ENCRYPTION DECRYPTION
Same Key
Message 2 SYMMETRIC
The Internet knows no geographical boundaries. Encrypted Message 2
It has redefined time and space. Advances in a520eecb61a770f947ca856cd675463f1c95a9a2b
computer and telecommunication technologies 8d4e6a71f80830c87f5715f5f59334978dd7e97da
have led to the explosive growth of the Internet. 0707b48a1138d77ced56feba2b467c398683c7db
This in turn is affecting the methods of eb86b854f120606a7ae1ed934f5703672adab0d7
communication, work, study, education, be66dccde1a763c736cb9001d0731d541106f50b
interaction, leisure, health, governance, trade b7e54240c40ba780b7a553bea570b99c9ab3df13
and commerce. d75f8ccfdddeaaf3a749fd1411
Encrypted Message 2 Message 2
a520eecb61a770f947ca856cd675463f1c95 The Internet knows no geographical boundaries. It has
a9a2b8d4e6a71f80830c87f5715f5f5933497 redefined time and space. Advances in computer and
8dd7e97da0707b48a1138d77ced56feba2b4 telecommunication technologies have led to the
67c398683c7dbeb86b854f120606a7ae1ed9 explosive growth of the Internet. This in turn is
Different Keys
34f5703672adab0d7be66dccde1a763c736c affecting the methods of communication, work, study,
b9001d0731d541106f50bb7e54240c40ba7 education, interaction, leisure, health, governance,
[Keys of a pair – Public and Private]
80b7a553bea570b99c9ab3df13d75f8ccfddd trade and commerce.
ASYMMETRIC
eaaf3a749fd1411
[PKI] 15
Encryption Techniques…
• One-Way Function
– non-reversible “quick” encryption
– produces a fixed length value called a hash or message
digest
– used to authenticate contents of a message
– Common message digest functions
• MD4 and MD5
– produces 128 bit hashes
• SHA
– produces 160 bit hashes
16
Cryptographic Services Allow
• Digital Signatures
– sign messages to validate source and integrity of the contents
• Digital Envelopes (combination of symmetric/asymmetric)
– secure delivery of secret keys
• Message Digests
– short bit string hash of message
• Digital Certificates
– used to authenticate: users, web sites, public keys of public/private
pair, and information in general
• Secure Channels
– Encryption can be used to create secure channels over private or
public networks 17
Cryptanalysis
18
Cryptanalysis…
• Cryptanalysis:
– relies on the nature of the algorithm plus
– some knowledge of the general characteristics of the plaintext or
– even some sample plaintext - ciphertext pairs.
• This type of attack exploits the characteristics of the algorithm to
attempt to:
– deduce a specific plaintext or
– to deduce the key being used.
• Brute-force attacks:
– try every possible key on a piece of ciphertext until an intelligible
translation into plaintext is obtained.
– On average, half of all possible keys must be tried to achieve success.
– WHY?
19
Cryptanalysis…
• Defense method
– Use longer keys and
– stronger encryption algorithm
20
Cryptanalytic Attacks
• Known ciphertext only
– only know algorithm & ciphertext, know or can identify plaintext
• Known plaintext
– know/suspect plaintext & ciphertext to get keys or algorithms
• Chosen plaintext
– Here, the attacker, chooses the plaintext for any cipher and
understands the 'key' and the algorithm.
• Chosen ciphertext
– select ciphertext and obtain plaintext and key
21
Brute Force Search
• always possible to simply try every key
• most basic attack, proportional to key size
128 2128 = 3.4 1038 2127 µs = 5.4 1024 5.4 1018 years
years
168 2168 = 3.7 1050 2167 µs = 5.9 1036 5.9 1030 years
years
22
Steganography
Steganography is
the art and science
of writing hidden
message in images,
audios, or videos.
23
Cryptography + Steganography
• Enciphering on source side
24
Cryptography + Steganography
Deciphering
25
Building Blocks of Encryption Techniques
• Two building blocks of all classical encryption techniques are
substitution and transposition.
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC
Example
plaintext: are you ready
ciphertext: duh brx uhdgb 28
Cryptography example
Caesar cipher
• If we represent each letter of the alphabet by an integer that
corresponds to its position in the alphabet, the formula for replacing
each character ’P’ of the plaintext with a character ’C’ of the
ciphertext can be expressed as
C = E( 3, P) = (P + 3) mod 26
• A more general version of this cipher that allows for any degree of
shift would be expressed by
C = E( k, P) = (P + k) mod 26
• The formula for decryption would be
P = D( k, C ) = (C - k) mod 26
• In these formulas, ’k’ would be the secret key.
• The symbols ’E’ and ’D’ represent encryption and decryption. 29
Weakness of the Caesar Cipher
30
Ciphering with Transposition
31
Ciphering with Transposition…
Key: 4 1 3 6 2 5
Plaintext: m e e t m e
a t s q u a
r e g u a r
d e n f o r
g o o d d i
n n e r o k
Ciphertext: tqufdrmardgnesgnoeearriketeeonmuaodo
• Keyword: CHIFFRE
• Encrypting: VIGENERE becomes XPOJSVVG
• The plaintext character (V) is replaced by the character in the
corresponding row and in the column of the first keyword character (C).
• The next plaintext character (I) is replaced by the character in the
corresponding row and in the column of the next keyword character (H),
and so on.
• If all characters of the keyword have been used, then the next keyword
character is the first key character. 33
Vigenère Keyword character
encryption …
• Example
• Keyword:
CHIFFRE
• Encrypting:
VIGENERE Plaintext
becomes
XPOJSVVG
Ciphertext
35
Plaintext
Plaintext: THANKYOU
Key: COVERCOVER…
Cipher: VVVRBACP
Key: COVERCOVER…
Plaintext ?
36
Symmetric and Asymmetric ciphering
37
Requirements
• Two requirements for secure use of symmetric
encryption:
– a strong encryption algorithm
– a secret key known only to sender / receiver
C = DK [EK (P)]
39
Number of persons
Cryptography – Important Insights - 1
Solving the key distribution problem through asymmetric
cryptography.
• Asymmetric cryptography
– For centuries it was believed that sender and receiver need to
know the same secret.
– New idea: Every person needs a key pair (which solves the key
distribution problem).
• Asymmetric encryption
– MIT, 1977: Leonard Adleman, Ron Rivest, Adi Shamir (well known
as RSA)
• Key distribution
– Stanford, 1976: Whitfield Diffie, Martin Hellman, Ralph Merkle
(Diffie-Hellman key exchange)
40
Asymmetric ciphering…
• Asymmetric Cryptography
• Also called public-key cryptosystem
keys for encryption and decryption are different but form a unique pair
C = DKD [EKE (P)]
Only one of the keys need to be private while the other can be public.
• Invented by Diffie and Hellman in 1976.
• It is a revolutionary concept since it avoids the need of using a secure
channel to communicate the key.
• It has made cryptography available for the general public and made
many of today’s on-line application feasible.
Security in open networks (such as the Internet) would be extremely expensive
and complex without asymmetric cryptography!
41
Cryptography – Important Insights (2)
43
Block vs Stream Ciphers
44
Substitution-Permutation Ciphers
• In his 1949 paper, Shannon introduced the idea
of substitution-permutation (S-P) networks,
which now form the basis of modern block
ciphers.
45
Substitution-Permutation Ciphers…
• Substitution Operation
– a binary word is replaced by some other binary word
– the whole substitution function forms the key
– if use n bit words, the key is 2n ! bits, grows rapidly
– will call them S-Boxes
• Permutation Operation
– a binary word has its bits reordered (permuted)
– the re-ordering forms the key
– if use n bit words, the key is n! bits, which grows more slowly, and
hence is less secure than substitution
– will call these P-Boxes 46
Substitution-Permutation Ciphers…
• Shannon combined these two primitives
• he called these mixing transformations
• Shannon's mixing transformations are a special form of product
ciphers where
• S-Boxes
– provide confusion of input bits
• P-Boxes
– provide diffusion across S-box inputs
47
Substitution-Permutation Ciphers…
48
Cryptography – Important Insights (3)
• Kerckhoffs’ principle (first stated in 1883)
– Separation of algorithm (method) and key e.g. Caesar encryption:
• Algorithm: “Shift alphabet by a certain number of positions to the left”
• Key: The “certain number of positions”
– Kerckhoffs’ principle: The secret lies within the key and not within
the algorithm; “security through obscurity” is invalid
• Shannon’s concepts: Confusion and Diffusion
– Relation between M, C, and K should be as complex as possible
(M=message, C=cipher, K=key)
– Every ciphertext character should depend on:
• as many plaintext characters and
• as many characters of the encryption key as possible
– “Avalanche effect” (small modification, big impact) 49
Cryptographic Algorithms
50