Skip to main content
Engineering LibreTexts

1.4: Exercises

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    1.1: The one-time pad encryption of plaintext “mario” (written in ASCII) under key \(k\) is:


    What is the one-time pad encryption of “luigi” under the same key?

    1.2: Alice is using one-time pad and notices that when her key is the all-zeroes string \(k = 0^{\lambda}\), then \(\text{Enc(}k, m) = m\) and her message is sent in the clear! To avoid this problem, she decides to modify KeyGen to choose a key uniformly from \(\{0, 1\}^{\lambda}\ \{0^{\lambda}\}\). In this way, her plaintext is never sent in the clear.

    Does Claim 1.3 still hold with respect to this modified one-time pad? Prove or disprove.

    1.3: When Alice encrypts the key k itself using one-time pad, the ciphertext will always be the all-zeroes string! So if an eavesdropper sees the all-zeroes ciphertext, she learns that Alice encrypted the key itself. Does this contradict Claim 1.3? Why or why not?

    1.4: Describe the flaw in this argument:

    Consider the following attack against one-time pad: upon seeing a ciphertext c, the eavesdropper tries every \(k\in ?\) until she has found the one that was used, at which point she outputs the plaintext \(m\). This contradicts the argument in Section 1.3 that the eavesdropper can obtain no information about m by seeing the ciphertext.

    1.5: Suppose Alice encrypts two plaintexts m and m’ using one-time pad with the same key \(k\). What information about \(m\) and \(m\)’ is leaked to an eavesdropper by doing this (assume the eavesdropper knows that Alice has reused \(k\))? Be as specific as you can!

    1.6: Suppose we modify the subroutine discussed in Claim 1.3 so that it also returns \(k\):

    \[\underline{\text{CTXT'}(m\in \{0,1\}^{\lambda}):}\\\space\space k\space\leftarrow\space\{0,1\}^{\lambda}\\\space\space\text{return}\space(k,k\oplus m)\nonumber\]

    Is it still true that for every m, the output of \(\text{CTXT’} (m)\) is distributed uniformly in \((\{0,1\}^{\lambda})^2\)?

    1.7: In this problem we discuss the security of performing one-time pad encryption twice:

    (a). Consider the following subroutine that models the result of applying one-time pad encryption with two independent keys:

    \[\underline{\text{CTXT'}(m\in \{0,1\}^{\lambda}):}\\\space\space k_1\space\leftarrow\space\{0,1\}^{\lambda}\\\space\space k_2\space\leftarrow\space\{0,1\}^{\lambda}\\\space\space\text{return}\space k_2\oplus (k_1\oplus m)\nonumber\]

    Show that the output of this subroutine is uniformly distributed in \(\{0,1\}^{\lambda}\)

    (b). What security is provided by performing one-time pad encryption twice with the same key?

    1.8: Show that the output of the following subroutine is uniformly distributed in \(\mathbb{Z}_n\):

    \[\underline{\text{CTXT'}(m\in \mathbb{Z}_n):}\\\space\space k\space\leftarrow\space \mathbb{Z}_n\\\space\space\text{return}\space(k + m)\% n\nonumber\]

    1.4: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.

    • Was this article helpful?