Transcript Chapter 1 Security Problems in Computing

Chapter 3
Encryption Algorithms &
Systems
Outline

NP-completeness & Encryption
 Symmetric (secret key) vs Asymmetric (public key)
Encryptions
 Popular Encryption Algorithms
– Merkle-Hellman Knapsacks
– RSA Encryption
– El Gamal Algorithms
– DES
 Hashing Algorithms
 Key Escrow & Clipper
csci5233 computer security &
integrity (Chap. 3)
2
Review of Concepts

Rate of growth:
– Polynomial functions
Example: n, 10n, n2, 5n3, …
– Exponential functions
Example: 2n, 210n, …

The order of functions matters!
See next page.
csci5233 computer security &
integrity (Chap. 3)
3
Order wins out!


N
Cray-1 Fortran
3N3 nanosec.
TRS-80 Basic
19,500,000n ns.
10
3 s
200 ms.
100
3 ms.
2 sec.
1,000
3 sec.
20 sec.
2,500
50 sec.
50 sec.
10,000
49 min.
3.2 min.
1,000,000
95 years
5.4 hours
From Baase, Computer Algorithms (2nd ed.)
Exercise: How if a computer that runs at 2N ns.?
csci5233 computer security &
integrity (Chap. 3)
4
Review of Concepts

Polynomial bounded
An algorithm is said to be polynomial bounded if its
worst-case complexity is bounded by a polynomial
function of the input size.
That is, there exists a polynomial function p such
that the algorithm terminates after at most p(n)
steps, where n is the input size.
A problem is said to be polynomial bounded if there
is a polynomial bounded algorithm for it.

Exercise: Is an algorithm whose order is n10,000,000
polynomial-bounded?
csci5233 computer security &
integrity (Chap. 3)
5
Nondeterminism

A nondeterministic algorithm has two phases:
1. The nondeterministic phase (the guessing
phase)
– A guess at a solution for the problem is
proposed.
2. The deterministic phase (the checking phase)
– A deterministic algorithm is executed, with
or without the proposed solution from
phase 1.
csci5233 computer security &
integrity (Chap. 3)
6
Complexity Classes



Complexity Classes:
Class P
P is the class of problems that are polynomialbounded.
Class NP
NP is the class of problems for which there is a
nondeterministic polynomial-bounded
algorithm.
A theorem: P  NP
Implication: A deterministic algorithm is a special
case of a nondeterministic algorithm (with phase 1
ignored).
csci5233 computer security &
integrity (Chap. 3)
7
Characteristics of Hard Problems





P.72
Each problem is solvable, and a relatively simple
approach solves it (although the approach may be
time-consuming).
There are 2n cases to consider if we use the
approach of enumerating all possibilities, where n is
the input size.
The problems exist in various areas (logic, number
theory, graph theory, …).
If it were possible to guess perfectly, each problem
could be solved in relatively little time. That is, the
verification process is polynomial bounded.
csci5233 computer security &
integrity (Chap. 3)
8
Sample NP Problems

Satisfiability, p.71
 Knapsack
 Subset sum, a simpler version of Knapsack, p.72
 Clique, p.72
 Graph coloring
 Job scheduling with penalties
 Bin packing
 Hamilton paths (or circuits)
 Minimum tour (Traveling salesperson problem)
 ...
csci5233 computer security &
integrity (Chap. 3)
9
A broader Knapsack problem



From Baase, Computer Algorithms (2nd ed.)
Given:
– a knapsack of capacity C (a positive integer
– N objects with sizes s1, …, sn and “profits” p1, …,
pn, where s1, …, sn and p1, …, pn are positive
integers.
Problem: Find the largest total profit of any subset of
the objects that fits in the knapsack (and find a
subset that achieves the maximum profit).
csci5233 computer security &
integrity (Chap. 3)
10
The Graph Coloring Problem



A coloring of a graph G = (V, E) is a mapping C:
VS, where S is a finite set of “coloring”, such that if
vw  E then C(v)  C(w); that is, adjacent vertices are
not assigned the same color.
A decision problem: Given G and a positive integer k,
is there a coloring of G using at most k colors? (Is G
k-colorable?)
An application: Scheduling the final exams at a
university without conflicts.
Let V be the set of courses.
Let E be the pairs of courses whose exams must not be at the
same time.
Suppose there are 15 time slots (3 exams per day X 5 days).
Then the exams can be scheduled in the 15 time slots without
conflicts if and only if the graph G = (V, E) is 15-colorable.
csci5233 computer security &
integrity (Chap. 3)
11
NP-completeness

P.75
 [Cook 71]
 A problem is called NP-complete if it can represent the
entire class NP.
 Example: The ‘satisfiability’ problem (p.71) is a NPcomplete problem. (Cook’s theorem)
 Implication: If a NP-complete problem can be solved
by a deterministic, polynomial time algorithm, then all
NP problems can be solved by such algorithms.
 The converse implication: “If for even one of the NPcomplete problems it could be shown that there was
no deterministic algorithm that ran in polynomial time,
then no deterministic algorithm could exist for any of
them.”
csci5233 computer security &
integrity (Chap. 3)
12
Does P = NP or P  NP?


P.76
NP-complete problems have been studied for a long
time by many different groups of people and so far no
polynomial, deterministic solution has been found for
any one of the problems.

Implication: It is very likely that no polynomial,
deterministic solution exists for NP-complete
problems. That is, NP  P.

Note: The question ‘Does P = NP?’ is still an open
question.
csci5233 computer security &
integrity (Chap. 3)
13
NP-completeness & Cryptography


Hard-to-solve problems are fundamental to
cryptography, because the interceptor would need
to work hard to break the encryption.
But, be aware of the fallacies:
1. An NP-complete problem does not guarantee
that there is no solution easier than exponential.
2. Every NP-complete problem has a deterministic
exponential time solution. That is, O(2n).
3. Continuing advances in hardware make
problems of larger size tractable.
4. The interceptor does not always have to solve
the had problem in order to crack the encryption.
csci5233 computer security &
integrity (Chap. 3)
14
Review of Some Arithmetic Concepts

Inverses
A number i is an identity for an operation op if, for
every number x, x op i = x and i op x = x.
Example:
0 is an identity for +, because x + 0 = 0 + x = x.
1 is an identity for *, because x * 1 = 1 * x = x.
The inverse of a number x, x-1, under an operation
op, is a number that makes x * x-1 = x-1 * x = i,
where i is the identity under op.
Example: The inverse of 5, under +, is –5. The
inverse of 5, under *, is 1/5.
csci5233 computer security &
integrity (Chap. 3)
15
Review of Some Arithmetic Concepts




Prime numbers
GCD
Euclidean algorithm for computing GCD
Modular arithmetic
Two integers, a and b, are equivalent under
modulus n, if a mod n = b mod n.
If a is equivalent to b, under modulus n,
then (x – y) = k * n for some k. (That is, the
difference between x and y is divisible by n.)
csci5233 computer security &
integrity (Chap. 3)
16
Modular arithmetic


Table on p.79
Reducibility
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a * b) mod n = ((a mod n) * (b mod n)) mod n

Modular operations on negative numbers
-13 mod 3 = ?

The inverse under modular operations
Example: The inverse of 3 mod 5, under *, is 2
because (3 * 2) mod 5 = 1. (See the
multiplication table on p.80.)
csci5233 computer security &
integrity (Chap. 3)
17
The inverse under modular operations

Exercise: What is the inverse of 4 mod 5 under * ?

Fermat’s Theorem:
ap mod p = a (and ap-1 mod p = 1),
where p is a prime number and a < p.

Computing the inverse of a number
The inverse of a number a =
ap-2 mod p (p.81)
Example: The inverse of 3 mod 5 = 35-2 mod 5 = 2.
Verify: 3 * 2 mod 5 = 1.
csci5233 computer security &
integrity (Chap. 3)
18
Secret versus Public Key Encryptions

Secret Key Encryption Algorithms
Also called single key, symmetric, private key, or
conventional algorithms.
Both the encryptor and the decryptor use the same
key.
Example: DES

Public Key Encryption Algorithms
The sender uses the receiver’s public key to
encrypt the message. The receiver uses his
own private key to decrypt the encrypted
message.
Examples: Merkle-Hellman Knapsacks, RSA
Encryption, El Gamal Algorithms
csci5233 computer security &
integrity (Chap. 3)
19
Secret Key Encryptions

Advantages
The symmetry of the key provides a two-way
channel. Both ends can both encrypt and
decrypt information.
Authentication of incoming messages: An incoming
ciphertext is authenticated because only
legitimate sender can produce the ciphertext.
csci5233 computer security &
integrity (Chap. 3)
20
Secret Key Encryptions

Disadvantages
1. A single-point failure: A compromised key allows
the interceptor not only to decrypt all the
ciphertext encrypted by the key, but also to
fabricate “bogus” ciphertext to be sent to
legitimate receivers.
2. Distribution of keys can be a problem. (See Fig.
3-10, p.101: key distribution in pieces)
3. The number of keys increases rapidly, roughly
half of the square of the number of people. (See
Fig. 3-11, p.101: distribution center)
– Adding a new user into an existing network of
N users requires the addition of N new keys.
4. The symmetric key encryptions can be relatively
weak, unless based on hard problems.
csci5233 computer security &
integrity (Chap. 3)
21
Public Key Encryptions



Proposed by Diffie and Hellman in 1976.
Each user has two keys: a public key and a private
key, which operate as inverses.
P = C (KPRIV, E (KPUB, P ) )
Advantage:
No need for a shared key between every two users.
csci5233 computer security &
integrity (Chap. 3)
22
Next



Popular Encryption Algorithms
– Merkle-Hellman Knapsacks
– RSA Encryption
– El Gamal Algorithms
– DES
Hashing Algorithms
Key Escrow & Clipper
csci5233 computer security &
integrity (Chap. 3)
23