Week 4 Flashcards
What is a One Way Function?
A function which is easy to compute but hard to find the inverse
What is a Trapdoor One Way Function? (very similiar to a one way)
A function which is easy to compute but hard to find the inverse, however it is easy to find the inverse with additional information
What does it mean for two numbers to be “Congruent Modulo?”
Two numbers are congruent modulo n if they have the same remainder when divided by n
eg. 10 and 7 are congruent modulo 3
What is the Greatest Common Divisor (GCD)?
For 2 numbers, its the largest number that divides into both numbers
eg. GCD of 12 and 8 is 4
The GCD can be computed quickly using Euclid’s algorithm
When are 2 numbers relatively prime?
Two numbers are relatively prime if their GCD is 1 (don’t share any factors except 1)
Multiplicative Inverse Modulo???
Write card on this
What is Modification Detection Code?
Provides a checkable fingerprint to make sure an encrypted message hasnt been tampered with
Can also be called a hash
What is Hashing?
A pure one way function
Generates a unique hash for a piece of data
Changes to the data = changes to the hash
What are the properties of a Hash Function?
A hash function h(x) (in the general sense) has the properties:
- Compression: h maps an input x of an arbitrary bit length to an output h(x) of fixed bit length n
- Polynomial time computable
What are the requirements for a Hash Function to be a Cryptographic Hash Function?
- One-way (or pre-image resistant)
Given y, it is hard to compute an x where h(x) = y
- And usually either:
2nd-preimage resistance
It is computationally infeasible to find a second input that has the same output as any specified input, given x to find an x’ != x such that h(x) = h(x’)
Collision resistance
It is difficult to find 2 distinct inputs x, x’ where h(x) = h(x’)
The hash value is also called message digest or modification detection code (MDC)
What does One-Way (Pre-image resistance) mean?
Given a hash output y=h(x), it is computationally hard to find original input x
What does Second Pre-image Resistanc mean?
Given an input x, it is computationally infeasible to find another input x’ (x! = x’) such that both inputs produce the same hash output i.e. h(x) = h(x’)
What does Collision Resistance mean?
It is difficult to find any 2 distinct inputs x and x’, such that h(x) = h(x’)
Stronger than pre-image resistance
What are the purpose of a Cryptographic Hash Function?
To provide data integrity
What is a PKI?
An infrastructure that allows principals to recognize which public key belongs to whom (i.e to bind public keys to principals)
