A MUST problem and EXTRAs:
• 5.11
(new) •
EXTRAs
(c)
Is the result of • 5.10 • still valid using the
decryption method of • 5.11 • ? Explain your answer.
(d)
Using MAPLE™ find two random 100-digit primes p and q with the property
that |gcd(p-1,q-1)|>75 digits.
(e)
Find exponents a,a’,b such that |a|=|b|=|n|=200 digits whereas |a’|<125 digits. Verify on
10 random examples that (mb)a’ mod n = m.
Any two of the following three problems:
• 4.5 (new)
•
•
6.7 (new) •
• 7.6 (formerly 6.5)
•
Let n=p*q, the product of two primes p=q=3
(mod 4), be a modulus
suitable for the Blum-Goldwasser cryptosystem. Suppose that we modify the
cryptosystem and that in order to encrypt an l-bit message x we use the BBS generator 2l+t+1 times instead of only l+1. The initial l+t extra bits are used to authenticate x into a t-bit tag as w=ax|t(+)b where a is from F2l and b is from F2t.
The encryption would then be (y, w, s2l+t+1)
where y is from the original scheme.
(1)
Explicit the
decryption/verification algorithm of this encryption/authentication scheme.
(2)
Show that
even this modified scheme fails under chosen cyphertext attack.
(Assume that the decryption device returns the
original plaintext x
only when (y,
w, s2l+t+1) is
correctly authenticated, otherwise an error message is issued)
Let n=p*q, the
product of two primes, and let n-1 be an element of QNRn[+1] i.e. the Jacobi symbol (n-1/n)
= +1. Let e be an RSA public exponent mod n.
1) Give explicit conditions on p and q to have the Jacobi symbol (n-1/n) = +1.
Let M be a
random variable describing the random choice of a plaintext 0<M<n.
2) Show that H[ lsbn(M) | (Me/n) ] = H[ lsbn(M) ].
3) Use MAPLE™ to show that this may be false if the Jacobi symbol (n-1/n)
= -1.
Let n=p*q, the product of two primes, and let y be an element of QNRn[+1]. Remember that the Goldwasser-Micali cryptosystem with public parameters (n,y) encrypts a zero bit by [a random square] x2
mod n and a one bit by [a random pseudo-square] x2y mod n.
Let GM(m1),GM(m2)
be the Goldwasser-Micali encryption of messages m1 and m2 as computed and sent by Bob to Alice. Suppose Bob
applied his personal signature to the encryption of each bit.
Imagine the government witnessed Bob's transmission
of both messages to Alice and they wish to have some minor information about
the messages as follows.
(a)
Show how Bob
can prove that both GM(m1),GM(m2)
were encryptions of the same message m1=m2 without disclosing anything else about
it.
(b)
Show how Bob
can prove that GM(m1),GM(m2)
were encryptions of messages m1 and m2 that differed in an even (including zero) or odd number of positions, without disclosing
anything else about them.
(c)
Assume m1,m2 have even length, |m1|=|m2|=2k. Show how Bob can prove that GM(m1),GM(m2) were encryptions of different messages m1≠m2 by disclosing nothing except for the fact
that they differed somewhere among all but one of the positions. (Bob can put
aside one encrypted bit at a fixed position of GM(m1) and GM(m2), and then prove that the remaining
truncated messages are different without disclosing anything about them except
for the fact that they differ). Explain why we need messages of even length 2k.
(d)
How much
uncertainty is left about m1,m2 when only learning that they differ ? How
much uncertainty is left about m1,m2 when learning that they differ by the
method suggested in (c) ?
(in both cases
assume that the a priori uncertainty was maximum.)