# These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

 Page 19/24 Date 03.05.2017 Size 186.06 Kb. #18863

## RSA Applications

• The receiver "encrypts" the decrypted signature to restore the original signature. The receiver then runs the same processing algorithm on the message, and compares the result with the signature. If they match, the message is valid – otherwise it has been tampered with
• How do we know that the key used actually belonged to the sender?
• Ex: Joe Schmoe gets fired by his boss and sends a digitally signed message stating that his boss is a total weasel. Before getting the message, his boss decides to rehire Joe, but then sees the message. Joe says "well, I didn't send that message – I haven't used that RSA key for years – it must be from someone pretending to be me"
• How does the boss know if Joe is lying?
• We need authentication of keys

## Intro. to Graphs

• Graph: G = (V, E)
• Where V is a set of vertices and E is a set of edges connecting vertex pairs
• Used to model many real life and computer-related situations
• Ex: roads, airline routes, network connections, computer chips, state diagrams, dependencies
• Ex:
• V = {A, B, C, D, E, F}
• E = {(A,B), (A,D), (A,E), (A,F), (B,C), (C,D), (C, F), (D, E)

## Intro. to Graphs

• Undirected graph
• Edges are unordered pairs: (A,B) == (B,A)
• Directed graph
• Edges are ordered pairs: (A, B) != (B,A)
• Vertices connected by an edge
• Let v = |V| and e = |E|
• What is the relationship between v and e?
• Let's look at two questions:
• Given v, what is the minimum value for e?
• Given v, what is the maximum value for e?

## Intro. to Graphs

• Given v, minimum e?
• Graph definition does not state that any edges are required: 0
• Given v, maximum e? (graphs with max edges are called complete graphs)
• Directed graphs
• Each vertex can be connected to each other vertex
• "Self-edges" are typically allowed
• Vertex connects to itself – used in situations such as transition diagrams
• v vertices, each with v edges, for a total of v2 edges

## Intro. to Graphs

• Undirected graphs
• "Self-edges" are typically not allowed
• Each vertex can be connected to each other vertex, but (i,j) == (j,i) so the total edges is ½ of the total number of vertex pairs
• Assuming v vertices, each can connect to v-1 others
• This gives a total of (v)(v-1) vertex pairs
• But since (i,j) == (j,i), the total number of edges is (v)(v-1)/2
• If e <= vlgv, we say the graph is SPARSE
• If e  v2, we say the graph is DENSE

## Intro. to Graphs

• Representing a graph on the computer
• Most often we care only about the connectivity of the graph
• Different representations in space of the same vertex pairs are considered to be the same graph
• Two primary representations of arbitrary graphs
• Square matrix labeled on rows and columns with vertex ids
• M[i][j] == 1 if edge (i,j) exists
• M[i][j] == 0 otherwise

## Intro to Graphs

• Plusses:
• Minuses:
• Theta(v2) memory, regardless of e
• Theta(v2) time to initialize
• Theta(v) to find neighbors of a vertex
 A B C D E F A 0 1 0 1 1 1 B 1 0 1 0 0 0 C 0 1 0 1 0 1 D 1 0 1 0 1 0 E 1 0 0 1 0 0 F 1 0 1 0 0 0

## Intro to Graphs

 A B C D E F
• F
• D
• B
• E
• C
• A
• D
• A
• C
• A
• B
• A
• C
• E
• F
• D