Cryptography Exam 2

Confidentiality

ensures secrecy of the message — only intended recipient can see contents

Integrity

ensures data has not been altered in an unauthorized manner since the time it was transmitted

Authentication

ensures message really comes from the stated sender

Non-repudiation

ensures a party cannot deny the validity of the message it creates

What security goals does symmetric key encryption and asymmetric key (public key) encryption provide

Only confidentiality

What provides integrity and authentication?

Message Authentication Codes and Digital Signatures

What provides integrity, authentication, and non-repudiation

Digital Signatures

How does RSA key gen work

Select 2 large primes p and q
n = p*q and Φ(n) = (p-1)(q-1)
Select a random integer e less than Φ(n) where gcd(e, Φ(n))=1
Compute d, where e*d = 1 (mod Φ(n)) → (d = e^-1 mod Φ(n))

What is the RSA public key

(e, n)

What is the RSA private key

d

What is kept secret in RSA

p and q

How does RSA encyrption work

get recipient’s (n, e)
c = M^e (mod n)

How does RSA decryption work

Given c, M = C^d (mod n)

What is Φ(n)

the number of relatively prime numbers to n

What is a cyclic group

The group has a generator g such that every h in the group can be written as h = gⁱ for some int i (in mod n)

What is a discrete logarithmic function

Let p be prime, G is a cyclic group, g is generator of G. Every element a of G can be written as g^k=a (mod p) for some integer k. k is the discrete logarithm of a to base g mod p
Can be defined for any cyclic group

The RSA Problem

given c, find m such that m^e = c (mod n) where e and n are defined in RSA settings
not solvable when n, p, q are very large
if adversary knows p and q they can use Euler phi function and calculate d such that d*e = 1 (mod Φ(n)) and break RSA

Small message space attack on RSA

encrypt all possible plaintexts until c is obtained

Solution to small message space attack

Salting: append random bitstring to plaintext before encryption

Common Modulus Attack on RSA

if two entities use the same n attacker can find m from c1 = m^e1 (mod n) and c2 = m^e2 (mod n)
gcd(e1, e2) = 1 → attacker finds u, v such that ue1 + ve2 = 1 and computes c1^uc2^v = m

Malleability attack on RSA

takes advantage of multiplicative property
attacker can transform c so that it is still valid upon decryption but is incorrect

What is semantic security

no partial info about plaintext can be obtained from ciphertext

What is ciphertext indistinguishability

Adversary unable to distinguish pairs of c based on plaintexts they encrypt

What is probabilistic encryption

to get semantic security, use randomness so that the same message is encrypted to different ciphertexts

Is textbook RSA IND-CPA secure

No

When is a scheme IND-CPA secure

if adversary winning the IND-CPA security game has probability with a negligible advantage over random guessing

What is a cryptographic hash function

takes a string as input and outputs fixed size string (smaller than input size)

many-to-one function so collisions are possible

Cost of semantic security in public key encryption

some expansion is necessary for semantic security

ciphertext must be larger than corresponding plaintext

padding scheme
Cost: requires extra random number generation and an XOR op for each bit

What is the discrete logarithm problem

you cannot find x from g^x (mod p)

Advantages of public key encryption

better for key management - do not need secure channel to transmit secret keys + do not need O(n²) keys for n entities

Disadvantages of public key cryptography

slower than symmetric key

How does digital signature work

Sig = S_priv(M) and V_pub(M, Sig) should be “valid”

provides authentication, integrity, non-repudiation

What is Fermat’s Little Theorem

if p is prime and a is not a multiple of p (gcd(a, p) = 1) then a^p-1 = 1 (mod p) and a^p = a (mod p)