CS408 Flashcards
(37 cards)
What are the three main components of public key encryption (G, E, D)?
- G: Key generation algorithm generates (Pub, Priv) key pair
- E: Encryption algorithm computes C = EPub(M)
- D: Decryption algorithm recovers M = DPriv(C)
What are the steps of RSA key generation?
- Select two large prime numbers p and q
- Compute n = pq and φ(n) = (p-1)(q-1)
- Select e where 1 < e < φ(n) and gcd(e, φ(n)) = 1
- Compute d where ed ≡ 1 mod φ(n)
Public key is (n,e), Private key is d
Why are e = 3 and e = 65537 common choices for RSA encryption exponent?
- Both have few 1’s in binary representation
- Leads to faster encryption (fewer multiplications)
- 3 = 11₂ (two 1’s)
- 65537 = 10000000000000001₂ (two 1’s)
- 65537 is considered more secure than 3
What is the RSA Problem (RSAP)?
Given an integer c, find m such that mᵉ ≡ c (mod n), where:
- n is product of two distinct large primes
- e is positive integer where gcd(e, φ(n)) = 1
- No known efficient algorithm exists to solve this
What is the relationship between RSAP and FACTORING?
- If adversary can solve FACTORING, they can solve RSAP
- Widely believed (but not proven) that if adversary can solve RSAP, they can solve FACTORING
- RSAP and FACTORING might be equivalent
What is the small message space attack in RSA?
- Occurs when message space is limited (e.g., yes/no)
- Attacker can try encrypting all possible messages until match
- Solution: Use salting (append random bits before encryption)
Why can’t deterministic public key encryption achieve semantic security?
- Same message always encrypts to same ciphertext
- Attacker can encrypt guessed messages and compare
- Makes patterns in communication visible
- Must use probabilistic encryption for semantic security
What is ciphertext indistinguishability?
Security property where adversary cannot distinguish which of two chosen plaintexts was encrypted, even with:
- Access to public key
- Ability to encrypt any messages
- Choice of the two possible messages
What are the three main properties of cryptographic hash functions?
- First pre-image resistance: Given h(x), cannot find x
- Second pre-image resistance: Given x and h(x), cannot find y≠x where h(y)=h(x)
- Collision resistance: Cannot find any x,y where x≠y and h(x)=h(y)
What is HMAC and how is it constructed?
Hash-based Message Authentication Code:
- HMAC_K(m) = h((K⊕opad) || h((K⊕ipad) || m))
- Provides authentication and integrity
- Security depends on underlying hash function
- Output length matches hash function length
What are the key properties of El Gamal encryption?
- Ciphertext is twice size of plaintext
- Uses randomization
- Each message has p-1 possible different encryptions
- Security based on Discrete Log Problem, computational diffie-hellman probelm, decisional diffie-hellman problem
What makes Z*p special when p is prime?
- Z*p is always cyclic (has primitive roots)
- Contains numbers {1, 2, …, p-1}
- Has order p-1
- Essential for discrete logarithm-based cryptography
What is the common modulus attack in RSA?
If two entities use same modulus n with different e₁,e₂:
- If gcd(e₁,e₂)=1, can find u,v where e₁u + e₂v = 1
- Given c₁ = mᵉ¹ mod n and c₂ = mᵉ² mod n
- Can compute m = c₁ᵘ × c₂ᵛ mod n
What is RSA’s multiplicative property and why is it a concern?
Property: (m₁ × m₂)ᵉ = m₁ᵉ × m₂ᵉ mod n
- Allows modification of ciphertext without knowing plaintext
- Can multiply ciphertext by (k)ᵉ to get k×m after decryption
- Problem for integrity but doesn’t break confidentiality
Birthday paradox
Probability in set of N ppl, 2 ppl have same bday
N = 23 -> PR = 50%
N = 57 -> PR = 99%
Birthday attack on collision resistance
Break collision resistance in Hash Functions. Works against all un-keyed hash functions
Assuming output of h(x) is m bits
Attack runs in O(2^(m/2))
m should be double key length
Why is Hash not sufficient
Only provides data integrity not data source authentication or message authentication
Key components of MAC
Message authentication code
[G, MAC, VMAC]
G: generates secret key for data source authentication
MAC: authentication tag generation T = MACk(m)
VMAC: authentication tag verification VMACk(m)
Valid if received T matches computer MACk(m) on recipients side
Invalid otherwise
HMAC
Hash based message authentication code
s = k+ xor opad
t = k+ xor ipad
HMACk(m) = h( s || h(t || m))
Where k+ is key padded to match input size of hash function h
Both ipad and opad are fixed public strings
How does HMAC differ from Cryptographic Hash Functions
Both ensure data integrity but HMAC provides data source integrity
Neither provide confidentiality or non-repudation
OAEP
Optimized Asymmetric Encryption Padding
Ek[m xor G(r) || r xor H(m xor G(r))]
G and H are hash functions,
G takes input of same size as r and outputs of same size as m
H takes input of same size as m and outputs of same size as r
r is random integer
Adds semantic security onto RSA
What are the three key components of Digital Signatures
G: key gen
Public and private keys
S: Signature gen
Sig = S_priv(M)
C: Signature validation
V_pub(M, Sig) = “valid” or “invalid”
What are attack goals for Digital Signatures
- Total Break: get secret for signing to forge any sig on any message
- Selective Forgery: create valid sig on message chosen by someone else
- Existential Forgery: create pair of (sig, Message) such that sig of message is valid
What are attack models for Digital Signatures
- Key only Attack: attack only knows public verification key
- Known message attack: attacker has lis of (M, Sig) pairs signed by target entity
- Chosen message attack: attacker can choose what message target entity will sign and knows (M, Sig) pair
