CS408 Flashcards
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
Digital signatures with appendix
A computes sig = S_privA(M)
Sends (M,Sig) to B
B validates sig is valid on M
Example Schnorr Signature Scheme
Digital Signatures with message recovery
A computes Sig = S_privA(M)
A sends Sig to B
B uses Sig to recover M and verifies validity of Sig in process
Example RSA Signature Scheme
RSA digital Signature
G: RSA key gen Pub=(n,e) Priv=(d)
S: message is represented as integer
Sig = M^d mod (n)
V: obtain Pub and compute
M = Sig^e mod (n)
Multiplicative property attack on RSA digital signature
Using a known message attack allows for an EXISTENTIAL FORGERY
Given the same signature private key generates two signatures y1 and y2, and corresponding messages x1 and x2 are known
A valid signature message pair of x1x2 and y1y2 can be created
Y1 = x1^d mod n
Y2 = x2^d mod n
Sig(x1x2) = (x1)^d(x2)^d = y1y2 mod n
RSA digital signature padding scheme
PKCS#1
Similar to OAEP for RSA encryption
What is PKI
Public Key Infrastructure which provides infrastructure to support Asymmetric Key Encryption
How are public keys authenticated in PKI
A Certification Authority signs a CERT that validates one’s identity with their public key
Root Certificate
The CA has a public key which is publicly made available and is signed by itself
Serves as anchor point in chain of trust
How is a public key authenticated in PKI
One will retrieve the CERT of the sender from the CA, then will validate the CERT using root certificate, and then retrieves public key of sender from CERT
Common Certificate fields
Identity of owner
Public key
Serial number
Expiration date
What is the CRL
Certification Revocation List
When a certificate is revoked before expiration, marked in CRL
Best practice to check CRL for validating CERT
Problem with CRL
Requires an online entity to provide CRL which breaks the key establishment afbatnge of Public Key over symmetric key
Meaning it needs a secure channel to transmit secret keys
Advantages of Public key cryptography over Symmetric Key cryptography
Key establishment : no need for secure channel to transmit secret key
Key distribution : does not require O(n^2) keys to be managed to communicate with n entities
Non-Repudiation
