Topics – Module – 5 - Security
• Building blocks of cryptography.
• key pre-distribution
• Traditional Applications
• Multimedia Applications
Basics – Security CIA Triad – Triangle
Definitions
• Cryptography = the science (art) of encryption
• Cryptanalysis = the science (art) of breaking
encryption
• Cryptology = cryptography + cryptanalysis
History
• The Stone age to todays age
Friends and enemies: Alice, Bob, Trudy
• well-known in network security world
• Bob, Alice want to communicate “securely”
• Trudy (intruder) may intercept, delete, add messages
Alice Bob
data, control
channel
messages
data secure secure data
sender receiver
Trudy
Who might Bob, Alice be?
• Web client/server (e.g., on-line purchases)
• DNS servers
• Routers exchanging routing table updates
• Two computers in peer-to-peer networks
• Wireless laptop and wireless access point
• Cell phone and cell tower
• Cell phone and Bluetooth earphone
• RFID tag and reader
• .......
There are bad guys (and girls) out
there!
Q: What can a “bad guy” do?
A: a lot!
—eavesdrop: intercept messages
—actively insert messages into connection
—impersonation: can fake (spoof) source address in
packet (or any field in packet)
—hijacking: “take over” ongoing connection by removing
sender or receiver, inserting himself in place
—denial of service: prevent service from being used by
others (e.g., by overloading resources)
The language of cryptography
Alice’s Bob’s
K encryption K decryption
A
key B key
plaintext encryption ciphertext decryption plaintext
algorithm algorithm
Symmetric key crypto: sender, receiver keys identical
public-key crypto: encryption key public, decryption key secret
(private)
Classical Cryptography
• Transposition Cipher
• Substitution Cipher
—Simple substitution cipher (Caesar cipher)
—Vigenere cipher
—One-time pad
Transposition Cipher: rail fence
• Write plaintext in two rows in column order
• Generate ciphertext in row order
• Example: “HELLOWORLD”
HLOOL
ELWRD
ciphertext: HLOOLELWRD
Problem: does not affect the frequency of
individual symbols
Network Security 7-11
Simple substitution cipher
substituting one thing for another
—Simplest one: monoalphabetic cipher:
• substitute one letter for another (Caesar Cipher)
ABCDEFGHIJKLM NOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
Example: encrypt “I attack”
Problem of simple substitution
cipher
• The key space for the English Alphabet is very
large: 26! 4 x 1026
• However:
—Previous example has a key with only 26 possible
values
—English texts have statistical structure:
• the letter “e” is the most used letter. Hence, if one performs
a frequency count on the ciphers, then the most frequent
letter can be assumed to be “e”
Distribution of Letters in
English
Frequency analysis
Vigenere Cipher
• Idea: Uses Caesar's cipher with various different shifts, in
order to hide the distribution of the letters.
• A key defines the shift used in each letter in the text
• A key word is repeated as many times as required to
become the same length
Plain text: I a t t a c k
Key: 2342342 (key is “234”)
Cipher text: K d x v d g m
Problem of Vigenere Cipher
• Vigenere is easy to break (Kasiski, 1863):
• Assume we know the length of the key. We can organize
the ciphertext in rows with the same length of the key.
Then, every column can be seen as encrypted using
Caesar's cipher.
• The length of the key can be found using several
methods:
— 1. If short, try 1, 2, 3, . . . .
— 2. Find repeated strings in the ciphertext. Their distance is
expected to be a multiple of the length. Compute the gcd of
(most) distances.
— 3. Use the index of coincidence.
Cryptography components
Message in
readable form
Message in Decode - Message readable form
Encode - Message un readable form Plain Text
readable form
- Plain Text
Cipher Text
E[Plain Text] D[Cipher-text]
Categories of cryptography
Symmetric-key cryptography
Symmetric/shared Key
Cryptography
Both Sender and Receiver shares the Same key
!@#$%
^&*()
Must be Shared by
both Sender and
Receiver
Note
In symmetric-key cryptography, the
same key is used by the sender
(for encryption)
and the receiver (for decryption).
The key is shared.
30.21
Encryption - Decryption
Symmetric/Shared
Key Cryptography
Message in - Plain Text Message in
readable unreadable form
form
Today
meeting
at 3pm
Cipher Text
Cipher Text
Raj Today
meeting
at 3pm
Same Key - Message in
shared readable
form
Uma
Major Problems –
1. Key distribution
Encryption - Decryption
Symmetric Key Cryptography - 2. Every user -
Problems Maintaining huge no.
Message in
unreadable form
of Keys
Venkat Message in
readable
form
Today
meeting
atPlain
3pm Text Cipher Text
Cipher Text
Message
Raj Uma Today
meeting
at 3pm
Message in
readable
Cipher Text form
Message
Surya
Smitha
Suresh Sony
Diffie-Hellman Key
Exchange
Color Mixing Example
The Problem of Key Exchange
One of the main problems of symmetric key
encryption is it requires a secure & reliable channel
for the shared key exchange.
The Diffie-Hellman Key Exchange protocol offers a
way in which a public channel can be used to
create a confidential shared key.
Modular what?
In practice the shared encryption key relies on such
complex concepts as Modular Exponentiation,
Primitive Roots and Discrete Logarithm Problems.
Let’s see though is we can explain the Diffie-
Hellman algorithm with no complex mathematics.
A Difficult One-Way Problem
The first thing we require is a simple real-world operation that is easy to Do
but hard to Undo.
You can ring a bell but not unring one.
Toothpaste is easy to squeeze out of a tube but famously hard to put back in.
In our example we will use Mixing Colors.
Easy to mix 2 colors, hard to unmix
Alice & Bob with Eve listening wish to make a
secret shared color
Step 1 - Both publicly agree to a shared color
Step 2 - Each picks a secret color
Step 3 - Each adds their secret color to
the shared color
Step 3 - Each adds their secret color to
the shared color
Send the same to each other
Step 4 - Each sends the other their new
mixed color
Each combines the shared color
from the other with their own
secret color
Alice & Bob have agreed to a shared
color unknown to Eve
How is it that Alice & Bob’s final mixtures are
identical?
Alice mixed
[(Yellow + Teal) from Bob] + Orange
Bob mixed
[(Yellow + Orange) from Alice] + Teal
Alice & Bob have agreed to a shared
color unknown to Eve
How is it that Alice & Bob’s final mixture is secret?
Eve never has knowledge of the secret colors of
either Alice or Bob
Unmixing a color into its component colors is a hard
problem
Alice & Bob have agreed to a shared
color unknown to Eve
How is it that Alice & Bob’s final mixture is secret?
Eve never has knowledge of the secret colors of
either Alice or Bob
Un-mixing a color into its component colors is a hard
problem
Diffie-Hellman Key
Exchange
Adding Mathematics
A=4 B=10
Shared key = Shared key =
Let’s get back to math
We will rely on the formula below being an easy problem one direction and hard in
reverse.
s = gn mod p
Easy: given g, n, & p, solve for s
Hard: given s, g, & p, solve for n
And the property of
ga*b mod p = gb*a mod p
Step 1 –Publicly shared information
Alice & Bob publicly agree to a large prime number called the modulus, or
p.
Alice & Bob publicly agree to a number called the generator, or g, which
has a primitive root relationship with p.
In our example we’ll assume
p = 17
g=3
Eve is aware of the values of p or g.
Step 2 – Select a secret key
Alice selects a secret key, which we will call a.
Bob selects a secret key, which we will call b.
For our example assume:
a = 54
b = 24
Eve is unaware of the values of a or b.
Step 3 – Combine secret keys with
public information
Alice combines her secret key of a with the public information to compute
A.
A = ga mod p
A = 354 mod 17
A = 15
Step 3 – Combine secret key with
public information
Bob combines his secret key of b with the public information to compute B.
B = gb mod p
B = 354 mod 17
B = 16
Step 4 – Share combined values
Alice shares her combined value, A, with Bob. Bob shares his combined
value, B, with Alice.
Sent to Bob
A = 15
Sent to Alice
B = 16
Eve is privy to this exchange and knows the values of A and B
Step 5 – Compute Shared Key
Alice computes the shared key.
s = (B mod p)a mod p
s = gb*a mod p
s = 354*24 mod 17
s = 1
Bob computes the shared key.
s = (A mod p)a mod p
s = ga*b mod p
s = 324*54 mod 17
s = 1
Alice & Bob have a shared encryption
key, unknown to Eve
Alice & Bob have created a shared secret key, s, unknown to Eve
In our example s=1
The shared secret key can now be used to encrypt & decrypt messages by
both parties.
See the Youtube video on this example at:
[Link]
D2c4Xovk
Asymmetric-key cryptography
Asymmetric/Public Key Cryptography
Integrity – Security
Confidentiality – Privacy
Krishna
Radha Krishna
Key Pair
!@#$%
^&*() Public
key
Key Pair Radha
Public
key Only Krishna can Private
decrypt the message key
Private
key
!@#$%
^&*()
Radha Anybody/all in the network can
decrypt and read the message
Authentication – Digital signature
Public key store
Digital Signature
Authenticats – Digital signature
PB(Megha)
Non-Repudiation – can not Deny
Confidentiality
PR(Roopa)
Integrity
Encrypt
M Using Roopa’s
IN
Private Key
Transfer 20k to
Megha
Wallet address
of Roopa and
Megha !@#$3%^&1
et
*()2!f@#h$% Encrypt
Decryp
4k^b5&o*(r) t Using
_ Megha’s
!@#$3%^& Private Key
1*()2!f@#h
$%4k^b5&
o*(r)_ !@#$3%^&1
*()2!f@#h$%
4k^b5&o*(r)
_
Decryp Transfer 2B to
t Megha
Using
Roopa’s Wallet address
Public Key of Roopa and
Megha
Comparison between two categories of cryptography
ASYMMETRIC-KEY CRYPTOGRAPHY
An asymmetric-key (or public-key) cipher uses two
keys: one private and one public. We discuss two
algorithms: RSA and Diffie-Hellman.
Topics discussed in this section:
RSA
Diffie-Hellman
RSA
Rivest-Shamir-Adleman (RSA)
Scheme
• Developed in 1977 at MIT by Ron Rivest,
Adi Shamir & Len Adleman
• Most widely used general-purpose approach
to public-key encryption
• Is a cipher in which the plaintext and
ciphertext are integers between 0 and n – 1
for some n
—A typical size for n is 1024 bits, or 309 decimal
digits
RSA: Choosing keys
1. Choose two large prime numbers p, q.
(e.g., 1024 bits each)
2. Compute n = pq, F = (p-1)(q-1)
3. Choose e (with e<n) that has no common factors
with F. (e, F are “relatively prime”).
4. Choose d such that ed-1 is exactly divisible by F.
(in other words: ed mod F = 1 ).
5. Public key is (n,e). Private key is (n,d).
+ -
KB KB
RSA: Encryption, decryption
0. Given (n,e) and (n,d) as computed above
1. To encrypt bit pattern, m, compute
e
c = m mod n
e
(i.e., remainder when m is divided by n)
2. To decrypt received bit pattern, c, compute
m = c d mod n
(i.e., remainder when c d is divided by n)
Magic m = (m e mod n)
d
mod n
happens! c
RSA Example
1. Select primes: p=17 & q=11
2. Compute n = pq =17×11=187
3. Compute ø(n)=(p–1)(q-1)=16×10=160
4. Select e : gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160
Value is d=23 since 23×7=161= 10×160+1
6. Publish public key KU={7,187}
7. Keep secret private key KR={23,17,11}
RSA Example cont
• sample RSA encryption/decryption is:
• given message M = 88 (nb. 88<187)
• encryption:
C = 887 mod 187 = 11
• decryption:
M = 1123 mod 187 = 88
Note
In RSA, e and n are announced to the
public; d and F are kept secret.
Public cryptography is very
computational expensive.