Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Number Theory > CS408 > Flashcards

CS408 Flashcards

1
Q

What are the three main components of public key encryption (G, E, D)?

A
  • G: Key generation algorithm generates (Pub, Priv) key pair
  • E: Encryption algorithm computes C = EPub(M)
  • D: Decryption algorithm recovers M = DPriv(C)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the steps of RSA key generation?

A
  1. Select two large prime numbers p and q
    1. Compute n = pq and φ(n) = (p-1)(q-1)
    2. Select e where 1 < e < φ(n) and gcd(e, φ(n)) = 1
    3. Compute d where ed ≡ 1 mod φ(n)
      Public key is (n,e), Private key is d
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Why are e = 3 and e = 65537 common choices for RSA encryption exponent?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the RSA Problem (RSAP)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the relationship between RSAP and FACTORING?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the small message space attack in RSA?

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Why can’t deterministic public key encryption achieve semantic security?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is ciphertext indistinguishability?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the three main properties of cryptographic hash functions?

A
  1. First pre-image resistance: Given h(x), cannot find x
    1. Second pre-image resistance: Given x and h(x), cannot find y≠x where h(y)=h(x)
    2. Collision resistance: Cannot find any x,y where x≠y and h(x)=h(y)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is HMAC and how is it constructed?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the key properties of El Gamal encryption?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What makes Z*p special when p is prime?

A
  • Z*p is always cyclic (has primitive roots)
    • Contains numbers {1, 2, …, p-1}
    • Has order p-1
    • Essential for discrete logarithm-based cryptography
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the common modulus attack in RSA?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is RSA’s multiplicative property and why is it a concern?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Birthday paradox

A

Probability in set of N ppl, 2 ppl have same bday

N = 23 -> PR = 50%
N = 57 -> PR = 99%

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Birthday attack on collision resistance

A

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

17
Q

Why is Hash not sufficient

A

Only provides data integrity not data source authentication or message authentication

18
Q

Key components of MAC

A

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

19
Q

HMAC

A

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

20
Q

How does HMAC differ from Cryptographic Hash Functions

A

Both ensure data integrity but HMAC provides data source integrity

Neither provide confidentiality or non-repudation

21
Q

OAEP

A

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

22
Q

What are the three key components of Digital Signatures

A

G: key gen
Public and private keys

S: Signature gen
Sig = S_priv(M)

C: Signature validation
V_pub(M, Sig) = “valid” or “invalid”

23
Q

What are attack goals for Digital Signatures

A
  1. Total Break: get secret for signing to forge any sig on any message
  2. Selective Forgery: create valid sig on message chosen by someone else
  3. Existential Forgery: create pair of (sig, Message) such that sig of message is valid
24
Q

What are attack models for Digital Signatures

A
  1. Key only Attack: attack only knows public verification key
  2. Known message attack: attacker has lis of (M, Sig) pairs signed by target entity
  3. Chosen message attack: attacker can choose what message target entity will sign and knows (M, Sig) pair
25
Q

Digital signatures with appendix

A

A computes sig = S_privA(M)
Sends (M,Sig) to B
B validates sig is valid on M

Example Schnorr Signature Scheme

26
Q

Digital Signatures with message recovery

A

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

27
Q

RSA digital Signature

A

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)

28
Q

Multiplicative property attack on RSA digital signature

A

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

29
Q

RSA digital signature padding scheme

A

PKCS#1

Similar to OAEP for RSA encryption

30
Q

What is PKI

A

Public Key Infrastructure which provides infrastructure to support Asymmetric Key Encryption

31
Q

How are public keys authenticated in PKI

A

A Certification Authority signs a CERT that validates one’s identity with their public key

32
Q

Root Certificate

A

The CA has a public key which is publicly made available and is signed by itself

Serves as anchor point in chain of trust

33
Q

How is a public key authenticated in PKI

A

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

34
Q

Common Certificate fields

A

Identity of owner
Public key
Serial number
Expiration date

35
Q

What is the CRL

A

Certification Revocation List

When a certificate is revoked before expiration, marked in CRL

Best practice to check CRL for validating CERT

36
Q

Problem with CRL

A

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

37
Q

Advantages of Public key cryptography over Symmetric Key cryptography

A

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

Number Theory (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions