Transcript Presentation Layer - CS Course Webpages

Presentation Layer
Information
Transformation
Network
Format
Local
Format
“few standards, but a lot of ideas”
Presentation Functions
These are examples!
• Syntax (format) conversion
• Compression
• Encryption
– Sub-issue: Does it belong here?
Presentation Layer, cont.
• Providing a way to specify complex data
structures
• Managing the set of data structures required
• Converting data between internal and
external form
Data Representation
• ASCII vs. EBCDIC
• two’s complement vs. one’s complement
• FFF0 hex is -15 1’s complement; -16 2’s
complement
• byte order right left vs. left right
Abstract Syntax Notation 1
(ASN.1)
•
•
•
•
•
Data Structures
Abstract Syntax
Transfer Syntax
International Standard 8825
Notation used to encode, transfer and
decode data structures across a wide range
of applications
• Both connection-oriented and
connectionless primitives
Data Compression
• Encoding a Finite Set of Equally Likely
Symbols
– Finiteness of the set of symbols.
• Frequency Dependent Coding
– The relative frequencies with which the
symbols are used.
• Context Dependent Encoding
– The context in which a symbol appears.
Compression
• Elimination of Redundancy
– (increased susceptibility to error)
• Examples
–
–
–
–
Run Length Encoding
Predictive Codes
Huffman
LZW
Frequency Dependent Coding
• In English, “E” occurs ~100 times more
than the letter “Q”
• So give common symbols short codes and
longer symbols longer codes.
• Theoretical minimum encoding often
requires fractional bits, but close
approximations available.
Huffman Coding
• 1. Write down all symbols and associated probability of
each. Eventually a binary tree is built on these nodes, with
the symbols representing terminal nodes.
• 2. Find the two smallest nodes and mark them. Add a new
node with arcs to each of the nodes just marked. Set the
probability of the new node to the sum of the probabilities
of the two nodes connected to the new node.
• 3. Repeat until all symbols are marked except one. The
probability of the unmarked node will always be 1.0.
• 4. The encoding for each symbol is found by tracing the
path from the unmarked symbol to that symbol, recording
the sequence of left and right branches taken. The code is
Context Dependent Encoding
• Uses conditional probability instead of
independent probability.
• What is P(u|q)?
• So determine the conditional probability for
each possible predecessor and store in a
table.
• For k symbols this requires k2 entries.
Network Security and Privacy
• Protecting data from being read by
unauthorized persons.
• Preventing unauthorized persons from
inserting and deleting messages.
• Verifying the sender of each message.
• Allowing electronic signatures on
Cryptography
• Traditional Cryptography
– Substitution Ciphers
– Codes
– Transposition Ciphers
• Data Encryption Standard
• Key Distribution
• Public Key Crytography
– MIT Algorithm
• Authentication & Digital Signatures
Cryptography Users
• Military
• Diplomatic
• Diarists
• Lovers
• Curmugdeons
Cyptography Terms
• Ciphertext or Cryptogram -- encrypted
message
• Cryptanalysis -- breaking ciphers
• Cryptography -- devising ciphers
• Cryptology := Cryptanalysis and
Cryptography
Encryption Model
Passive Listener
Plaintext
Ciphertext
Plaintext
Key-1
Active Intruder
Key-2
Keys
• If Key-1 is the same as Key-2, then it has to
be a secret key process. They can differ,
making it a Public Key Process.
• Big Problems: key distribution and key
security
Fundamental Truths of
Cryptology
• Potential intruders know the general
encryption method.
• Message contents may be guessed.
• Cryptographic systems may be changed, but
rarely are.
• Non-technical compromises always
Ciphers
• Substitution (preserve order, disquise)
–
–
–
–
Caesar code = “shift 4”
Alphabet shifted by k letters --”enigma”
Exhaustive search infeasible
Words and phrases may be guessed
• Codes
– Purple code, Japanese translated into Latin
– Navajo talkers
• Transposition Ciphers (reorder, do not
Data Encryption Standard
•
•
•
•
Developed by IBM in 1977
Implemented in hardware
Widely used
128 bit key proposed, 56 bit key specified
Any guesses why?
Public Key Encryption
• Applying the decryption key to an
encrypted message must return the plaintext
message.
• The decryption key can’t be guessed from
an encyption key.
• The encryption key cannot be broken by a
plaintext attack.
RSA Algorithm
• 1. Choose two large primes, p and q, each
greater than 10100.
• 2. Compute n = p * q and z = (p - 1) * (q 1).
• 3. Choose a number relatively prime to z
and call it d.
Implementation of the MIT
Algorithm
• To encrypt
– divide plaintext P into k bits where k is the
largest integer for 2k < n.
– compute C = Pe(mod n)
• To decrypt
– P = Cd(mod n)
• Encryption requires e and n (public key)
• Decryption requires d and n (private key)
• If n can be factored, then this yields p an q,
Digital Signatures
• A’s secret key must remain secret
• B has A’s public key and A has B’s public
key
• B received a encypted message from A that
he decypts with A’s public key
• B can later show that lacking A’s private
Politics of Cryptography
•
•
•
•
•
Software as Munition
“Clipper” Chip
Digital Telephony Bill
Digital Signature Standard
Other Countries
• Current Legislation