Topics – Module – 5 - Security
• Building blocks of cryptography.
• key pre-distribution
• Traditional Applications
• Multimedia Applications
• Session Initiated Protocols – SIP Protocol
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/girl” 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)
– DOS Attacks
The language of cryptography
Alice’s Bob’s
K encryptio K decryptio
A
n Bn
key 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
Simple substitution cipher
substituting one thing for another
—Simplest one: monoalphabetic cipher:
• substitute one letter for another (Caesar Cipher)
ABCDEFGHIJKLMNOPQRSTUVWXYZ
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
Categories of cryptography
Symmetric-key cryptography
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.20
Asymmetric-key cryptography
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
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
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
c = m e mod
e
n (i.e., remainder when m is divided by n)
2. To decrypt received bit pattern, c, compute
m = c d mod
d
n (i.e., remainder when c is divided by n)
Magicm d
= (me mod n) 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.
Diffie Helman
• Next Lecture