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)
What is a PKI example?
To join the PKI, Alice
generates her own public/ private key pair
Takes her public key K to a certification authority (CA) that everybody trusts and says “Im Alice and K if my public key”
The CA verifies that Alice is who she says she is, and then signs a digital certificate that states
“K is Alice’s public key
Now any principal eg. Bob can now check the certificate to obtain Alice’s public key K and accept it is valid
Alice can similiarly obtain Bob’s public key J
thus, the CA can help establish mutual trust
What are the core services of a PKI?
Linking public keys to entities (certificates)
Key life-cycle management (key revocation, recovery, updates)
What is a Certificate?
A certificate is a token that binds (a representation of) an identity to a key
Every certificate has an expiry or can be revoked
What is X.509?
A standard, part of the X.500 Series of ITU-T recommendations, that defines a framework for authentication services
Based on public key cryptography
What are the components of an X.509 Certificate?
Serial Number
Signature algorithm Identifier
Issuer Name
