For this assignment, you will want to:
•Include all of your wriNen solutions (proves, computations, etc) into a single .pdf file.
•Include all of your accompanying code into a single package. Your package should also include a short README, leNing us know how to run your code.
Problem 1
In a RSA system, the public key of a given user is e = 31, n = 3599. What is the private key of this user?
Problem 2
Assume a good hash function h. Assume there is a particular value d for the hash, and you would like to find a message that has a hash value of d. Given that there are many more 2000-bit messages that map to a particular 128-bit hash than 1000-bit messages, would you theoretically have to test fewer 2000-bit messages to find one that has a hash of d than if you were to test 1000-bit messages?
Problem 3
If we define a hash function (or compression function) h that will hash an n-bit binary string to an m-bit binary string, we can view h as a function from Z2n to Z2m . It is tempting to define h using integer operations modulo 2m. We show in this exercise that some simple constructions of this type are insecure, and should therefore be avoided.
Suppose that n = m > 1 and h : Z2m → Z2m is defined as
h(x) = x2 + ax + b (mod 2)
Prove that it is easy to solve Second Preimage for any x ∈ Z2m without having to solve a quadratic equation.
Problem 4
Suppose that f : {0, 1}m → {0, 1}m is a preimage resistant bijection. Define h : {0, 1}2m → {0, 1}m as follows. Given x ∈ {0, 1}2m, write x = xj||xjj where xj, xjj ∈ {0, 1}m., and operation || represents bitstring concatenation. Then define h(x) = f (x ⊗ xjj). where ⊗ represents a bitwise logical XOR operation. Prove that h is not second preimage resistant.
Problem 5
Valentine’s day is approaching, so Edward is writing a love leNer to Bella. He would like to make sure that Bella knows with certainty that the beautiful words that she will be reading are from him, and that nobody has altered them en route to Bella. Bella proposes that they use digital signatures to ensure that. More specifically, she proposes that they use one of the possible modifications of the ElGamal digital signature, referred to as the Twilight ElGamal Digital Signatures.
The Twilight ElGamal Digital Signatures has the same key generation as the original ElGamal Digital Signature, which means that Bella generates the public key PKA and private key SKA as follows:
(a)Bella generates a large prime p and an integer α satisfying 1 ≤ α < (p − 1). Number α must be a primitive element.
(b)Bella then generates an integer a with 1 ≤ a < (p − 1), and computes β = αa mod p.
(c)Bella’s public key i PKA = (p, α, β), an her private key is SKA = a. Bella publishes PKA, and keeps SKA as a secret.
Edward generates his (public key, private key) pair, (PKK, SKK) in a similar fashion.
The Twilight ElGamal Digital Signature diKers, however, in the signing and the verification phases.
(a)Assume that Edward generates a random number k such that 1 k (p 2) and gcd (k, p 1) = 1, and then computes:
r = αk (mod p)
s = am + kr (mod p − 1)
Show that the verification:
is a valid verification procedure.
αs = (αa)mrr (mod p)
(b)Assume again that Edward generates a random number k such that 1 k (p 2) and gcd (k, p 1) = 1, and then computes:
r = αk (mod p)
s = a−1(m − kr) (mod p − 1)
Show that the verification:
is a valid verification procedure.
Problem 6
αm = (αa)srr (mod p)
Suppose I implement the ElGamal Signature Scheme with p = 31847, α = 5 and β = 26379. Write a computer program which does the following:
(a)Verify the signature (20679, 11082) on the message x = 20543.
(b)Determine my private key, a, by solving an instance of the bf Discrete Logarithm problem.
(c)Then determine the random value k used in signing the message x, without solving an instance of the
DiscreteLogarithm problem.
Problem 7
Bob, Ted, Carol and Alice want to agree on a common key (cryptographic key, that is). They publicly choose a large prime p and a primitive root α. They privately choose numbers b, t, c, a, respectively. Describe a protocol that allows them to securely compute (in doing so, please ignore the man-in-the-middle aNack):
K := αbtca (mod p)
Problem 8
In a large undergraduate class, a professor is considering posting class grades on Piazza, but for privacy reasons, he proposes to use only last four digits of a student’s Social Security as a “pseudo-identifier”. PuNing on a side possible privacy issues of such an approach, please compute for the professor the probability that at least two students have the same last four digits.
Note: this problem can easily be solved using birthday paradox.