Cryptography complete course is currently being offered by University of Maryland through Coursera platform and is being taught by Jonathan Katz.

*About this Course*

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

**Skills You Will Gain**

- Number Theory
- Cryptography
- Public-Key Cryptography

**Also Check: ****How to Apply for Coursera Financial Aid**

**Course Link:**

**https://www.coursera.org/learn/cryptography**

Q1) Consider the Vigenere
cipher over the lowercase English alphabet, where the key length can be
anything from 8 to 12 characters. What is the size of the key space for this
scheme?

26!

4 * 26^12

26^12

** 26^8 + 26^9 + 26^10 + 26^11
+ 26^12**

Q2) Consider the Vigenere cipher over the lowercase English alphabet, where the
key has length 8. For which of the following message spaces will this scheme be
perfectly secret? (Check all that apply.)

** The set of all 8-character
strings of lowercase English letters.**

** The set of all 7-character
strings of lowercase English letters.**

The set of all 9-character strings of
lowercase English letters.

The set of all strings of lowercase English letters containing at most 8 characters.

Q3) What is the result of encrypting the ASCII plaintext "cool!"
using the variant Vigenere cipher (where encryption is done using byte-wise
XOR) and key 0x01 3F?

**0x62 50 6E 53 20**

0x62 50 6F 6C 21

0x63 6F 6F 6C 21

0x26 05 E6 35 02

Q4) Say we have a scheme with a claimed proof of security with respect to some
definition, based on some assumption. The scheme was successfully attacked when
used in the real world. What are possible reasons for this? (Check all that
apply.)

** The proof might be
incorrect.**

** The assumption may be
false.**

** The definition of security
may not correctly capture the real-world threat model.**

The attacker did not read the proof of security.

Q5) In the definition of perfect secrecy, what threat model is assumed?

The attacker can eavesdrop on as many
ciphertexts as it likes.

** The attacker can eavesdrop
on a single ciphertext.**

The attacker can carry out a chosen-plaintext
attack.

The attacker is able to interfere with the communication channel between the two honest parties.

Q6) Consider the Vigenere cipher over the lowercase English alphabet, where the
key can have length 1 or length 2, each with 50% probability. Say the distribution
over plaintexts is Pr[M='aa'] = 0.4 and Pr[M='ab'] = 0.6. What is Pr[C='bb']?
Express your answer to 4 decimal places with a leading 0, i.e., if your answer
was 1/2 then you would enter 0.5000 (without a trailing period).

**0.0084**

Q7) Consider the Vigenere cipher over the lowercase English alphabet, where the
key can have length 1 or length 2, each with 50% probability. Say the
distribution over plaintexts is Pr[M='aa'] = 0.4 and Pr[M='ab'] = 0.6. What is
Pr[M='aa' | C='bb']? Express your answer to 4 decimal places with a leading 0,
i.e., if your answer was 1/2 then you would enter 0.5000 (without a trailing
period). Note: carry out the calculation exactly (i.e., do not use the
truncated result that you entered as your answer in the previous question)
before truncating your answer to 4 decimal places.

** 0.9473**

Q8) Which of the following are true for obtaining perfect secrecy using the one-time pad, assuming the message space contains messages all of some fixed length? (Check all that apply.)

** The key should be chosen
uniformly.**

** The key must be as least as
long as the messages in the message space.The key should be shared between the
two communicating parties, and kept secret from any potential attacker.**

The all-0 key must be avoided, since when the all-0 key is used the ciphertext is equal to the message being encrypted.

Q9) Consider the one-time pad over the message space of 5-bit strings, where
Pr[M=00100] = 0.1 and Pr[M=11011] = 0.9. What is Pr[C=00000]? Express your
answer to 5 decimal places with a leading 0. I.e., if your answer was 1/2, then
you would enter 0.50000 (without a trailing period).

**0.03125**

Q10) Which of the following are true about the Vigenere cipher? (Check all that
apply.)

A Vigenere cipher with key of length 100 can
be broken (in a reasonable amount of time) using exhaustive search of the key
space.

** The Vigenere cipher is
perfectly secret if the length of the key is equal to the length of the
messages in the message space.**

The Vigenere cipher is computationally
infeasible to break if the key has length 100, even if 1000s of characters of
plaintext are encrypted.

The Vigenere cipher can always be broken, regardless of the length of the key and regardless of the length of plaintext being encrypted.

**Also Check: ****Computer Science: Programming with a Purpose Week 1 Quiz Answers - Coursera!**

**Cryptography
Week 2 Quiz Answers**

*Computational
Secrecy and Principles of Modern Cryptography*

Q1) Two ASCII messages containing English letters and spaces only are encrypted
using the one-time pad and the same key. The 10th byte of the first ciphertext
is observed to be 0xB7 and the 10th byte of the second ciphertext is observed
to be 0xE7. Let m1 (resp., m2) denote the 10th ASCII character in the first
(resp., second) message. What is the most you can conclude about m1 and m2?

m1 is the space character
and m2 is the character 'p'.

m1 is the character 'p'
and m2 is the space character.

m1 is the character 'B'
and m2 is the character 'E'.

** One of m1 or m2 is the space character, and the
other is the character 'p'.**

Nothing can be determined about m1 or m2 since the one-time pad is perfectly secret.

Q2) Three ASCII messages containing English letters and spaces only are
encrypted using the one-time pad and the same key. The 10th byte of the first
ciphertext is observed to be 0x66, the 10th byte of the second ciphertext is
observed to be 0x32, and the 10th byte of the third ciphertext is observed to
be 0x23. Let m1 (resp., m2, m3) denote the 10th ASCII character in the first
(resp., second, third) message. What is the most you can conclude about m1, m2,
and m3?

m1 is the character 't', m2 is the space
character, and m3 is the character 's'.

** m1 is
the space character, m2 is the character 't', and m3 is the character 'e'.**

Exactly one of m1, m2, or m3 is the space
character, but nothing else can be determined.

Nothing can be determined about m1, m2, or m3 since the one-time pad is perfectly secret.

Q3) Which of the following is true about computational secrecy? (Select all
that apply.)

** Computational
secrecy currently relies on unproven assumptions.**

Computational secrecy means that it is trivial
for an attacker to always learn the entire message.

** Computational
secrecy only ensures secrecy against attackers running in some bounded amount
of time.**

** Computational
secrecy allows an attacker to learn information about the message with small
probability.**

Q4) Let G be a function mapping n-bit inputs to 2n-bit outputs. Which of the
following is true of the pseudo one-time pad encryption scheme based on G?
(Check all that apply.)

The scheme is perfectly secret.

** The scheme is
computationally secret if G is a pseudorandom generator.**

The key space of the scheme is at least as large as the message space. The scheme can be used securely to encrypt multiple messages using the same key.

Q5) Which of the following attackers can be used to demonstrate that the shift
cipher for 3-character messages does not satisfy perfect indistinguishability?

Output m0 = 'aaa' and m1 = 'abc'. Given
challenge ciphertext C, output 0 if the first character of C is 'a'.

Output m0 = 'aaa' and m1 = 'bbb'. Given
challenge ciphertext C, output 0 if the first character of C is 'a'.

** Output
m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output 1 if the three
characters of C are all different.**

Output m0 = 'abc' and m1 = 'bcd'. Given challenge ciphertext C, output 1 if the three characters of C are all different.

Q6) Which of the following is a negligible function? (Check all that apply.)

f(n) = 1/n.

f(n) = 1/2^n

f(n) = 1/2

**f(n) =
n/2^n**

Q7) Define the following function G taking n-bit inputs and producing (n+1)-bit
outputs: G(x)=x∥0, where ∥ denotes concatenation. Which
of the following attackers shows that this G is not a pseudorandom function?

** On
input an (n+1)-bit string y, output 0 if the last bit of y is 0.**

On input an (n+1)-bit string y, output 1 if the
first bit of y is 0.

On input an (n+1)-bit string y, output 0 if the
first bit of y is 0.

On input an (n+1)-bit string y, output 0 if the first bit of y is equal to the last bit of y.

Q8) Say G is a pseudorandom generator taking n-bit inputs and producing 2n-bit
outputs. Which of the following are necessarily true? (Check all that apply.
The symbol '|' is used here for string concatenation.)

G(r) | G(r+1) is computationally
indistinguishable from a uniform, 4n-bit string if r is a uniform n-bit string.

** G(r)
is computationally indistinguishable from a uniform, 2n-bit string if r is a
uniform n-bit string.**

r | G(r) is computationally indistinguishable
from a uniform, 3n-bit string if r is a uniform n-bit string.

G(0 | r) is computationally indistinguishable from a uniform, 2n-bit string if r is a uniform (n-1)-bit string.

Q9) Which of the following is a setting in which a pseudorandom generator could
be applied?

You have a 1 MB file that you would like to
compress.

You have a 1 MB file and you would like to make
sure that it has not been tampered with.

** You
have a way to generate random bits at the rate of 100 bits/second, but you need
1,000,000 random bits to run a statistical simulation.**

Q10)
Consider a pseudo one-time pad encryption scheme Î constructed using some
function G. Which of the following did our proof of security for the pseudo
one-time pad show?

Î is always perfectly secret, for any G.

Î is always computationally secret, for any
G.

If G is a pseudorandom generator, then Î is
perfectly secret.

** If G
is a pseudorandom generator, then Î is computationally secret.**

**Cryptography Week 3 Quiz Answers**

*
*

*Private-Key Encryption*

Q1) Any private-key encryption scheme that is CPA-secure must also be
computationally indistinguishable:

**True**

False

Q2) Any private-key encryption scheme that is CCA-secure must also be perfectly
secret:

True

**False**

Q3) Any private-key encryption scheme that is CCA-secure must also be CPA-secure:

**True**

False

Q4) Let F be a block cipher with 128-bit block
length. Consider the following encryption scheme for 256-bit messages: to
encrypt message M=m1∥m2 using key k (where
|m1|=|m2|=128), choose random 128-bit r and compute the ciphertext r∥Fk(r)⊕m1∥Fk(m1)⊕m2. Which strategy would lead
to a valid chosen-plaintext attack?

**Let m1
and m2 be arbitrary but distinct. Using the encryption oracle, obtain an
encryption r∥c1∥c2 of m1∥m2. Output messages M0=m1∥m2 and M1=m2∥m1. Output 0
if the third block of the challenge ciphertext is c2.**

There is no attack; this scheme is randomized,
so it is CPA-secure.

Let m; and m2 be arbitrary but distinct. Using
the encryption oracle, obtain an encryption rc1 C2 of m2 m2. Output messages Mo
= m m , and M = m m2. Output o if the third block of the challenge
ciphertext is cz. = mm.

Choose random r and let m be arbitrary but not equal to r. Output messages Mo = rm and M Output 0 if the second block of the challenge ciphertext is all-Os.

Q5) Let F be a pseudorandom function with
128-bit key and 256-bit block length. The following functions G are
pseudorandom generators:

**G(x)=Fx(0…0),
where x is a 128-bit input.**

** G(x)=Fx(0…0)∥Fx(1…1),
where x is a 128-bit input.**

G(x) = Fo...0(2)||F11(2), where r is a 256-bit
input.

G(x) = F.0...0)||F:(1...1), where x is a 128-bit input.

Q6) Define the keyed function F as follows:
Fk(x)=k⊕x. Which of the following distinguishers
demonstrates that F is not a pseudorandom function?

**Given
access to an oracle g, query y0=g(0…0) and y1=g(1…1). Then output 1 if and only
if y0⊕y1=1…1.**

Given access to an oracle g. query
g(0...0). Then output 1 because we now have the key.

Given access to an oracle g. query y=
g(0...0). Then output 1 if and only if the first bit of y is equal to 1.

Given access to an oracle g. query y = g(0...0) and y' = g(0...0). Then output 1 if and only if y=y.

Q7) Say we use CBC-mode encryption based on a
block cipher with 256-bit key length and 128-bit block length to encrypt a
512-bit message. How long is the resulting ciphertext?

**640 bits**

512 bits

768 bits

Not enough information to determine.

Q8) Assume CTR-mode encryption with PKCS #5 padding and a block cipher with 8-byte block length. Say a 4-byte message is encrypted, resulting in ciphertext 0x00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07. Which of the following ciphertexts will NOT yield an error upon decryption?

** 0x00
01 02 03 04 05 06 07 00 01 02 04 04 05 06 07**

0x00 01 02 03 04 05 06 07 00 01 02 03 04 05 07 07

0x00 01 02 03 04 05 06 07 00 01 02 03 05 05 06
07

Ox00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 F7

Q9) Assume an honest user wants to send an 8-bit integer to their bank indicating how much money should be transferred to the bank account of an attacker. The user uses CTR-mode encryption based on a block cipher F with 8-bit block length. (Yes, this is a made-up example.) The attacker knows that the amount of money the user wants to transfer is exactly $16, and has compromised a router between the user and the back. The attacker receives the ciphertext 10111100 01100001 (in binary) from the user. What ciphertext should the attacker forward to the bank to initiate a transfer of exactly $32? (Recall that CTR-mode decryption of a ciphertext c0,c1 using key k is done by outputting c1⊕Fk(c0+1).)

**01100001
10111100**

10001100 01100001

1011100 00100000

10111100 01010001

Q10) Let F be a block cipher with n-bit block length. Consider the following encryption scheme: to encrypt a message viewed as a sequence of n-bit blocks m1,m2,…,mt using a key k, choose a random n-bit value r and then output the ciphertext r,Fk(r+1+m1),Fk(r+2+m2),…,Fk(r+t+mt), where addition is done modulo 2n. Which of the following attackers demonstrates that this scheme is not computationally indistinguishable:

**Let m
be an arbitrary n-bit block, and output M0=m,m and M1=m,m−1. Given challenge ciphertext
r,c1,c2, output 1 if and only if c1=c2.**

Choose random n-bit blocks m and m', and
output Mo = m,m and M T, C1, C2, output 1 if and only if c = 62.

Choose random n-bit blocks mi, m2, m3,
74, and output Mo = m, m2 and M:=m3, m. Given challenge ciphertext r, C1, C2,
output o ifr=0...0, and output 1 otherwise.

Let m be an arbitrary n-bit block, and output Mo = m and M = m, m. Given a challenge ciphertext, output o if the challenge ciphertext contains 2 blocks, and output 1 otherwise.

**Cryptography Week 4 Quiz Answers**

** Message Authentication Codes**

Q1) True or false: CBC-mode encryption with PKCS#5 padding
provides message integrity, as long as the receiver makes sure to verify the
padding upon decryption

True

**False**

Q2) Let F be a block cipher with n-bit block length. Consider the message authentication code for 2n-bit messages defined by Mac (mi, m2) = F (m m 2). Which of the following gives a valid attack on this scheme?

Obtain tag ton message m, 0....0, and then
output the tagte (1...1) on the message m, 1... 1.

Obtain tag ton message m, m, and then output the
tag 0...0 on the message 0...0, m.

Obtain tag t on message m, 0...0(with m +0...0),
and then output the tag t on the message 0...0,0...0

**Obtain tag ton message mi,
m2 (with mÄ± + m2), and then output the tagt on the message m2, mÄ±.**

Q3) Let F be a block cipher with n-bit block length. Consider the message authentication code for 2n-bit messages defined by Mac (mi, m2) = F (mi) e F (m2). Which of the following gives a valid attack on this scheme?

There is no attack; the scheme is secure.

Obtain tagt on the message 0...0,1... 1, and
output the tagte (1...1) on the message 1...1,1...1.

Obtain tagt on the message 0...0,1... 1, and
output the tagte (1...1) on the message 1...1,0...0.

**Output the tag 0...0 on
the message 0...0.0...0.**

Q4) Assume a sender and receiver use basic CBC-MAC but authenticate/accept messages of different lengths. Which of the following is a valid attack?

**Obtain tag ta on message
mÄ±, and tag ta on message mi, m2. Then output the tag to on the message t1 o m2.**

Obtain tag ti on message mÄ±, and tag ta on
message m2, m. Then output the tag t2 on the message mi, m2.

Obtain tag ti on message mi, and tag ta on
message mi, m2. Then output the tag ti on the message t2 m2.

Obtain tag ti on message mÄ±, and tag ta on message t1, m2. Then output the tag t2 on the message m1 m 2.

Q5) Assume we want to use a hash function with output length as small as possible, subject to being collision resistant against a birthday attack running in time 212. Which hash function would be the best choice?

SHA-2, with output truncated to 192 bits.

**SHA-3 with 384-bit output.**

OSHA-1

OMDS.

Q6) Let H, H' be collision-resistant hash
functions. Which of the following functions H" is NOT necessarily
collision-resistant?

H"(x) = H(H'(x)).

**H"(x) = H (2) H'(x). **

H"(x) = H()|| H'(x), where | denotes
concatenation.

H"(x) = H20...0, where | denotes concatenation.

Q7) Assume a sender and receiver use the encrypt-and-authenticate approach for variable-length messages, using CTR-mode encryption and a variant of CBC-MAC secure for authenticating variable-length data (and independent keys for each). Which of the following statements is true?

The combination is CPA-secure, but it does not
provide integrity.

**The combination is not
CPA-secure, but it does provide integrity.**

The combination is not CPA-secure, and it does
not provide integrity because the CTR-mode encryption allows the attacker to
forge a tag in the CBC-MAC.

The combination is not CPA-secure, and it does not provide integrity because CTR-mode encryption is malleable.

Q8) Let F be a block cipher with block length n. Consider the following encryption scheme for n-bit messages: to encrypt message m using key k, choose a random co € {0,1}" and output the ciphertext co, C1, F(F(Co) e C), where c = Fx (co) em. Which of the following statements is true?

This can be viewed as an example of the
encrypt-and-authenticate approach using CBC-mode and CBC-MAC (with the same
key), and is insecure.

This looks like the authenticate-then-encrypt
approach using CBC-MAC and CBC-mode encryption (with the same key) -- but here
it's ok, since CBC-MAC is applied to something random.

**This is an example of the
encrypt-then-authenticate approach using CTR-mode and CBC-MAC, so is secure.**

This looks like the encrypt-then-authenticate approach using CTR-mode and CBC-MAC, except that here the same key is being used for both -- Prof. Katz warned us about that; this looks insecure!

Q9) Which of the following is the most appropriate primitive for achieving message integrity between two users sharing a key?

**Message authentication
code.**

Block cipher.

Collision-resistant hash function.

Private-key encryption scheme.

Q10) Which of the following is an example of a message authentication code used widely in practice?

**HMAC.**

CBC-mode encryption.

SHA-1.

AES

**Cryptography Week 5 Quiz Answers**

*Number Theory*

Q1) Consider the following algorithm for
factoring an integer N provided as input in binary): For i = 2 to (i, N/i).
Which of the following statements is true?

This algorithm is not correct, because it will
sometimes fail to find a factorization of N even if N is composite.

This algorithm is not correct, because it will
sometimes output a non-trivial factorization of N even when N is prime.

This algorithm runs in sub-linear time, and
always factors N if N is composite.

**This algorithm is correct,
but it runs in exponential time.**

Q2) Which of the following is NOT a group?

The integers under addition.

The set {0, 1, 2,..., 27} under addition
modulo 28.

The set {1,3,7,9} under multiplication modulo
10.

**The integers under
multiplication.**

Q3) Which of the following is the
multiplicative inverse of 10 modulo 15?

**There is none, since
gcd(10, 15) =1.**

5

10

1

Q4) What
is [5^{80} mod 79]? (Note that 79 is prime. Don't use a
calculator/computer!)

**25**

Q5) How many elements are in the group Z_{403}?
(Note that 403 = 13. 31.)

403

402

290

**360**

Q6) Which of the following gives the 3rd root
of 92 modulo 187 ? (Note that 187 = 11. 17.)

**[92 ^{107} mod
187] **

[92^{160} mod 187]

[92^{3}mod 187]

[92^{107} mod 160]

Q7) Which of the following problems is hard if
the RSA assumption holds? In all the below, *N *is a product of
distinct, large primes p and q, and e is relatively prime o (N).

**Given N, e, and a uniform
value y € Z _{N}, find x such that x^{c} = y mod
N.**

Given N, e, and a uniform value x € Z_{N},
find x such that x^{c} = y mod

Given N and e, find a, y such that x = y mod N.

Given N and e, find a such that = 8 mod N.

Q8) Which of the following is a generator of Z_{i3}?

4

**2**

Z_{i3} does not have a generator
since it is not a cyclic group.

3

Q9) Z_{23} is a cyclic group
with generator 5. In this group, what is DHS(2.20)? 1/1 point

17

5

**9**

22

Q10) Let G be a cyclic group of order q and
with generator g. Based only on the assumption that the discrete-logarithm
problem is hard for this group, which of the following problems is hard?

Find x, y such that gÊ» = y.

Given uniform 3 € Z, and uniformy e G, compute
y* .g.

**Given a uniform y € G,
find x such that g ^{x} = y.**

Given a uniform 2 € Zg, find y such that gÊ» = y.

**Cryptography Week 6 Quiz Answers**

*Key Exchange and
Public-Key Encryption*

Q1) Which of the following is a drawback of the private-key setting that is NOT addressed by the public-key setting?

The communicating parties need to share some
secret information in advance.

Users must manage and securely store keys for
every other party with whom they wish to communicate securely.

**The communicating parties
need the ability to generate random bits.**

The communicating parties need to have some prior relationship.

Q2) Which of the following BEST describes the
security offered by the Diffie-Hellman key-exchange protocol (assuming
the DDH problem is hard)?

An attacker eavesdropping on an execution of the protocol does not know whether the parties have shared a key or not.

An attacker eavesdropping on an execution of
the protocol cannot compute the key shared by the parties.

An attacker is unable to impersonate either
party taking part in the protocol.

**An attacker eavesdropping
on an execution of the protocol cannot distinguish the key shared by the
parties from a uniform key.**

Q3) Assume the Diffle-Hellman protocol is run by two parties in the subgroup of Zyg generated by 2. (This subgroup has order 11.) If the first party chooses private exponent 3 and the second chooses private exponent 10, which of the following characterizes the execution of the protocol in this case?

**The first party sends 8,
the second party sends 12, and they share the key 3.**

The first party sends 8, the second party
sends 1, and they share the key 1.

The first party sends 3, the second party
sends 10, and they share the key 11.

The first party sends 8, the second party sends 12, and they share the key 20.

Q4) In which of the following scenarios is public-key encryption a better choice than private key encryption?

Two police officers want to set up their
communication devices to communicate securely before heading out to an
operation

**A user wants to send his
credit card number to a merchant on the web.**

A user wants to encrypt the contents of her
hard drive.

A general wants to communicate securely with a lieutenant.

Q5) Which of the following would NOT be a
secure way for a receiver to distribute her key for a public-key encryption
scheme?

(Assume a passive, eavesdropping attacker here.)

post the public key on one's webpage.

Email the public key to the other party upon
request.

Put the public key into a public directory.

**Post the private key on
one's webpage.**

Q6) Which of the following is true in the public-key setting, but NOT true in the private key setting?

(Under standard assumptions) there exist
schemes that are CPA-secure, but are not CCA-secure.

It is possible to achieve perfect secrecy.

A deterministic encryption scheme cannot be
CPA-secure.

**Allowing the attacker to
have access to an encryption oracle makes no difference when defining security.**

Q7) Assume for the purposes of this question a public-key encryption scheme for which the time to encrypt a 128-bit message is 100 times slower than the time to compute one AES evaluation. Which of the following is true if we want to encrypt a 100MB message M?

Public-key encryption of M using the given
scheme is going to be only about 10 times slower than private key encryption of
M, because for secure private key encryption AES would have to be used in a
chaining mode of operation.

Public-key encryption of M is not possible
with the given scheme, since the scheme only supports 128-bit messages.

**If hybrid encryption is
used, then public-key encryption of M will take roughly the same time as
private key encryption of M.**

Public key encryption of M using the given scheme is inherently going to be 100 times slower than private-key encryption of M.

Q8) Assume El Gamal encryption, where the group being used is Zar with generator 5. (This group has order 46, which is not prime. But El Gamal encryption can be defined in any cyclic group.) Assume the public key contains h = 10. Say an attacker sees a ciphertext (41, 18) that is the encryption of some unknown message m. Which of the following is an encryption of (5m mod 47]?

(1,5)

(41,5)

(17,18)

**(41, 43)**

Q9) Assume "plain RSA" encryption is used with public key (N = 33, e = 3). What is the encryption of the message m = 2?

2

**8**

32

7

Q10) Which of the following is true about "plain RSA" encryption (assuming the RSA problem is hard)?

The scheme is CPA-secure, but not CCA-secure.

If the message m is a uniform, 128-bit string
then m cannot be recovered in its entirety from the ciphertext in polynomial
time. (Here, assume N is at least 1000 bits long, and e = 3.)

If the message m is uniform in Zj. then no
information about m can be recovered from the ciphertext in polynomial time.

**if the message m is uniform
in Z, then m cannot be recovered in its entirety from the ciphertext in
polynomial time.**

**Cryptography Week 7 Quiz Answers**

*Digital Signatures*

Q1) The Federal Government wants to be able to
issue advisories to the general public while ensuring that no one will be able
to tamper with their messages or spoof a fake advisory. Which of the following
is the best cryptographic approach to address this problem?

**Use a digital signature
scheme, with the public key known to everyone, to sign each advisory when it is
released.**

Use a message authentication code, with the
key known to everyone, to generate a tag for each advisory when It is released.

Use multiple message authentication codes,
with each member of the public being given a unique key, and generate one tag
per key each time an advisory is released.

Use a public-key encryption scheme, with the public key known to everyone, and decrypt each advisory when it is released.

Q2) The president and vice president of a
company want to communicate while ensuring integrity of
their communication. Which of the following is the best cryptographic
approach to address this problem?

Use a digital signature scheme, with the
public key known to everyone, and sign each message they send.

Use a CPA-secure private key encryption
scheme, with the key shared between them, and encrypt each message they send.

**O Use a message
authentication code, with the key shared between them, and generate a tag for
each message they send.**

Use a message authentication code, with the key made public, and generate a tag for each message they send.

Q3) Assume for the purposes of this question a
digital signature scheme for which the time to sign a 256-bit message is
100 times slower than the time to evaluate SHA-256 on a 512-bit input. Which of
the following is true if we want to sign a 500MB message M?

We can sign M by simply hashing it, and avoid
using the digital signature scheme altogether

Signing M using the given scheme is not
possible, since it only supports 256-bit messages.

We can securely sign M by breaking it into
256-bit chunks, and signing each chunk.

**if the hash-and-sign
approach is used, then signing M will take roughly the same time as hashing M.**

Q4) Assume the "plain" RSA signature
scheme, with public key (N = 55, e = 3). Which of the following
verifies correctly as the signature on the message m = 17?

**8 **

7

4

43

Q5) Assume the "plain" RSA signature scheme with public key (N, e = 3). For which of the following messages is it always possible to forge a signature without seeing any prior signatures or factoring N? (Assume N > 1000, and N relatively prime to each of the messages that follow.)

**27**

37

2

47

Q6) Assume the "plain" RSA signature scheme with public key (Ne). Say we want to forge a signature on m = 289 but can only obtain a signature on one other message. Which of the following strategies will work? (Assume N > 1000.)

Obtain signature o on m' = 288. Output 0 + 1
mod N as the signature on m.

Obtain signature o on m' = 578. Output 2-1.0
mod N as the signature on m.

Obtain signature o on m' = 288. Output o - 1
mod N as the signature on m

**Obtain signature o on m' =
17. Output (o2 mod N) as the signature on m.**

Q7) In this and the next question, assume the Schnorr identification protocol is run in the subgroup of Z3 generated by 2. (This subgroup has order 11.) Say the prover's private key is x = 7. What is the prover's public key?

14

3

**13**

7

Q8) (This is a continuation of the previous question.) Say the prover runs an execution of the Schnorr identification protocol with a verifier. The prover chooses r = 4 and sends A = 16. The verifler sends challenge 3. What response does the prover send?

**3**

7

13

4

Q9)As in the lectures, let cert 4-5 denote a certificate issued by A for B. i.e., cert-B = Sign.,(Bpkb). Assuming D knows pkc and trusts C, which of the following provides evidence to D that A's public key is pk A?

**Cert _{C->B}, pk_{B},
cert_{B->A}, and pk_{A}.**

Q10) Consider the SSL/TLS handshake protocol
as described on slide 5 of the SSL/TLS lecture. Say the encryption of pmk
were changed from using a CCA-secure public-key encryption scheme to using a
CPA-secure public-key encryption scheme. Which of the following attacks would
this change potentially enable ?

A passive eavesdropper can now learn Nc and Ng.In combination with other known information, this allows the attacker to recover mk.

An attacker can impersonate the server by
sending its own public key pk to the client. By doing so, it can convince the
client to encrypt pmk again, but this time using a public key for which the
attacker can decrypt.

**An attacker can eavesdrop
on an execution of the protocol to learn the ciphertext c. Then, it can
impersonate the client, send modified versions of c to the server, and learn
pmk by using information about whether the server returns an error or not in
response to these ciphertexts.**

A passive eavesdropper can now learn prk. In combination with Nc and Ns, this allows the attacker to recover mk.

**Cryptography Final Quiz Answer
Coursera**

*Week 7 Final Quiz*

*
*

Q1) What was your favorite part of this class?

**Learning about Hash And
Encrypt**

Q2) What is the most appropriate cryptographic
primitive to use if a company wants to distribute authenticated software
updates to its customers?

Message authentication code.

Pseudorandom function/block cipher.

Hash function.

**Digital signature scheme.**

Public-key encryption scheme.

Q3) What
is the most appropriate cryptographic primitive to use if an individual wants
to ensure confidentiality of the files stored on her hard drive?

Message authentication code.

**Private-key encryption.**

Hash function.

Pseudorandom function/block cipher.

Public-key encryption.

Q4) A user wants to design a CPA-secure
public-key encryption scheme to be used for emailing large files. Of
the following, which would be the best approach?

To encrypt a file M, hash the file to a short
value h = H(M), and then encrypt h using El Gamal encryption.

To encrypt a file M break it into a sequence
of blocks M1, M2, .... Then encrypt each block independently using El Gamal
encryption.

**To encrypt a file, use El
Gamal encryption to encrypt a random AES key; then use AES (with that key) in
CBC mode to encrypt the file.**

To encrypt a file Muse DSS to encrypt a random key, and then use that key to encrypt M using HMAC

Q5) Consider the following "hybrid"
signature scheme, which will give better efficiency when signing long messages.
To sign message M using private key sk, choose a uniform keyk for a message
authentication code and then sendk, Sign. (k), Mac (M). Verification is done in
the natural way. Which of the following is true regarding this scheme?

This is a secure signature scheme, if the
underlying signature scheme and MAC are secure.

**This is not secure because
given k, Sign.:(k), Mac (M) an attacker can forge k, Sign. (k), Mac (M') on any
M' of its choice.**

This is not secure because it is very likely
that a key k will be used twice by the signer.

This is not secure because given the
message/signature pair (k, Sign, (k)) an attacker can easily forge Sign.:(K) on
a key k' of its choice.

Q7) Let G be a group, and consider the following private-key encryption scheme with message space G: The shared key is a uniform element k = G. To encrypt a message me G using key k, output the ciphertext k. m. To decrypt a ciphertext c E G using key k, output the message k-1.c. Which of the following is true about this scheme?

The scheme is CCA-secure.

**The scheme is perfectly
secret.**

The scheme is CPA-secure, but not CCA-secure.

The scheme is computationally indistinguishable, but not perfectly secret.

Q7) Consider hybrid encryption using plain RSA and AES-128 in CTR mode, with public key N, e. Say a 128-bit message m is encrypted, ylelding ciphertext C, Co, C, with c e Zy and Co, € {0, 1}128. Which of the following would be an encryption of Ã±the bitwise complement of m?

**C _{1}, C_{0},
C_{1}.**

Q8) Say El Gamal encryption is used in the subgroup of Zor generated by 4. The public key is 21 and the private key is 4. The ciphertext (34, 42) is an encryption of some message m. Which of the following is an encryption of 4m mod 47?

**(34, 27) **

(42, 42)

(42, 27)

(34,46)

Q9) Consider the plain RSA encryption scheme
with public key N = 55, e = 3. Say the encryption of some unknown message
m Is 6. What Is the encryption of [2m mod N]?

31

**48**

3

12

Q10) Say you have "oracle access to a
plece of code that, given a message m, appends an unknown 8-byte
password p, applies PKCS #7 padding, and then encrypts the result using
AES-128 in ECB mode with an unknown key. Which of the following attacks can be
used to confirm that the first byte of p is 'Z?

Submit the 16-byte message
"ZZZZZZZZZZZZZZZZ," and check whether the first byte of the first
block of the resulting ciphertext is equal to the first byte of the second
block of that ciphertext.

Submit the null message and check whether the
first byte of the ciphertext is equal to 'Z'.

**Submit the 15-byte message
"ABCDEFGHIJKLMNO" and the 16-byte message
"ABCDEFGHIJKLMNOZ," and check If the first blocks of the resulting
ciphertexts are equal.**

Submit the 1-byte message "Z" and check whether any two bytes in the resulting ciphertext are equal.

## Post a Comment