<commit_before>\input{macros_TD}

\lhead{<NAME>}
\chead{\textbf{TP Cryptography}}
\rhead{28/02/2015}



\hypersetup{
    pdftitle={TP Cryptography},
    pdfauthor={<NAME>}
}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}[label=\textbf{\arabic*})]
    \setlength\itemsep{2em}
    \item See source code.

    \item
        \[
        \bordermatrix{
        & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\cr
        0 & 16 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8\cr
        1 & 8 & 10 & 8 & 6 & 8 & 14 & 8 & 10 & 10 & 8 & 6 & 8 & 6 & 8 & 10 & 8\cr
        2 & 8 & 4 & 8 & 8 & 6 & 10 & 6 & 6 & 8 & 8 & 4 & 8 & 10 & 10 & 6 & 10\cr
        3 & 8 & 6 & 8 & 6 & 6 & 8 & 6 & 8 & 10 & 8 & 10 & 8 & 8 & 10 & 8 & 2\cr
        4 & 8 & 10 & 8 & 10 & 8 & 6 & 8 & 6 & 14 & 8 & 6 & 8 & 10 & 8 & 10 & 8\cr
        5 & 8 & 8 & 4 & 8 & 8 & 8 & 12 & 8 & 8 & 12 & 8 & 8 & 8 & 12 & 8 & 8\cr
        6 & 8 & 10 & 4 & 10 & 10 & 8 & 6 & 8 & 6 & 4 & 6 & 8 & 8 & 10 & 8 & 6\cr
        7 & 8 & 8 & 8 & 8 & 10 & 10 & 10 & 2 & 8 & 8 & 8 & 8 & 6 & 6 & 6 & 6\cr
        8 & 8 & 4 & 6 & 6 & 10 & 6 & 8 & 8 & 8 & 8 & 6 & 10 & 6 & 6 & 12 & 8\cr
        9 & 8 & 10 & 6 & 8 & 2 & 8 & 8 & 6 & 6 & 8 & 8 & 10 & 8 & 6 & 10 & 8\cr
        10 & 8 & 8 & 10 & 10 & 8 & 8 & 10 & 10 & 8 & 8 & 6 & 14 & 8 & 8 & 6 & 6\cr
        11 & 8 & 6 & 10 & 12 & 8 & 10 & 10 & 8 & 6 & 8 & 8 & 6 & 10 & 8 & 12 & 6\cr
        12 & 8 & 6 & 6 & 8 & 6 & 8 & 12 & 10 & 10 & 4 & 8 & 6 & 8 & 6 & 6 & 8\cr
        13 & 8 & 8 & 10 & 10 & 6 & 6 & 8 & 8 & 8 & 8 & 6 & 6 & 2 & 10 & 8 & 8\cr
        14 & 8 & 6 & 6 & 12 & 8 & 10 & 6 & 8 & 10 & 8 & 12 & 10 & 6 & 8 & 8 & 10\cr
        15 & 8 & 8 & 10 & 6 & 8 & 8 & 10 & 6 & 8 & 4 & 10 & 10 & 8 & 12 & 10 & 10\cr
        }
        \]
    \item
    The probability the farthest from $\frac{1}{2}$ is $p_{0, 0} = 1$.

    Then the ouples $(a, b)$ with probability $p_{a, b} = \frac{1}{2} \pm \frac{6}{16}$ are:

    $(1, 5), (3, 15), (4, 8), (7, 7), (9, 4), (10, 11), (13, 12)$

    \item
    Notice that we have $x \cdot (a \oplus b) = (x \oplus a)\cdot(x \oplus b)$
    Take $(a, b) = (13, 12) = (1101_2, 1100_2)$. We have $p_{13, 12} = 2$.

    Let $A = 1101\underbrace{0\dots0}_{28}$ and $B = 1100\underbrace{0\dots0}_{28}$.

    Fix $K_0, K_1$. Take $m \hookleftarrow \cU\left(\zo^{32}\right)$

    \begin{align*}
        \prob{A\cdot m = P(B)\cdot x_1} &= \prob{A\cdot (x_0 \oplus K_0) = P(B) \cdot (P(S(x_0))\oplus K_1)} && \text{by definition}\\
            &= \prob{(A\cdot x_0) \oplus (A \cdot K_0) = (P(B) \cdot P(S(x_0)) \oplus (P(B) \cdot K_1)} && \text{by distributivity}\\
    \end{align*}

    \begin{itemize}
        \item If $A \cdot K_0 = P(B) \cdot K_1$, then:
        \begin{align*}
            \prob{A\cdot m = P(B)\cdot x_1} &= \prob{A\cdot x_0 = P(B) \cdot P(S(x_0)}\\
                &= \prob{A\cdot x_0 = B \cdot S(x_0)} && \text{since } P(x) \cdot P(y) = x \cdot y\\
                &= \frac{2}{16} && \text{by question 3}
        \end{align*}
        \item If $A \cdot K_0 \neq P(B) \cdot K_1$, then:
        \begin{align*}
            \prob{A\cdot m = P(B)\cdot x_1} &= 1-\prob{A\cdot x_0 = P(B) \cdot P(S(x_0)}\\
                &= 1-\prob{A\cdot x_0 = B \cdot S(x_0)} && \text{since } P(x) \cdot P(y) = x \cdot y\\
                &= \frac{14}{16} && \text{by question 3}
        \end{align*}
    \end{itemize}
    Thus:
    \[\prob{A\cdot m = P(B)\cdot x_1} = \frac{1}{2} \pm \frac{6}{16}\]

    We check that the experimental distribution is close to the properties $\frac{2}{16} = 0.125$ or $\frac{14}{16} = 0.875$.<commit_msg>Do not take a particular (a, b).<commit_after>\input{macros_TD}

\lhead{<NAME>}
\chead{\textbf{TP Cryptography}}
\rhead{28/02/2015}



\hypersetup{
    pdftitle={TP Cryptography},
    pdfauthor={<NAME>}
}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}[label=\textbf{\arabic*})]
    \setlength\itemsep{2em}
    \item See source code.

    \item
        \[
        \bordermatrix{
        & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\cr
        0 & 16 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8\cr
        1 & 8 & 10 & 8 & 6 & 8 & 14 & 8 & 10 & 10 & 8 & 6 & 8 & 6 & 8 & 10 & 8\cr
        2 & 8 & 4 & 8 & 8 & 6 & 10 & 6 & 6 & 8 & 8 & 4 & 8 & 10 & 10 & 6 & 10\cr
        3 & 8 & 6 & 8 & 6 & 6 & 8 & 6 & 8 & 10 & 8 & 10 & 8 & 8 & 10 & 8 & 2\cr
        4 & 8 & 10 & 8 & 10 & 8 & 6 & 8 & 6 & 14 & 8 & 6 & 8 & 10 & 8 & 10 & 8\cr
        5 & 8 & 8 & 4 & 8 & 8 & 8 & 12 & 8 & 8 & 12 & 8 & 8 & 8 & 12 & 8 & 8\cr
        6 & 8 & 10 & 4 & 10 & 10 & 8 & 6 & 8 & 6 & 4 & 6 & 8 & 8 & 10 & 8 & 6\cr
        7 & 8 & 8 & 8 & 8 & 10 & 10 & 10 & 2 & 8 & 8 & 8 & 8 & 6 & 6 & 6 & 6\cr
        8 & 8 & 4 & 6 & 6 & 10 & 6 & 8 & 8 & 8 & 8 & 6 & 10 & 6 & 6 & 12 & 8\cr
        9 & 8 & 10 & 6 & 8 & 2 & 8 & 8 & 6 & 6 & 8 & 8 & 10 & 8 & 6 & 10 & 8\cr
        10 & 8 & 8 & 10 & 10 & 8 & 8 & 10 & 10 & 8 & 8 & 6 & 14 & 8 & 8 & 6 & 6\cr
        11 & 8 & 6 & 10 & 12 & 8 & 10 & 10 & 8 & 6 & 8 & 8 & 6 & 10 & 8 & 12 & 6\cr
        12 & 8 & 6 & 6 & 8 & 6 & 8 & 12 & 10 & 10 & 4 & 8 & 6 & 8 & 6 & 6 & 8\cr
        13 & 8 & 8 & 10 & 10 & 6 & 6 & 8 & 8 & 8 & 8 & 6 & 6 & 2 & 10 & 8 & 8\cr
        14 & 8 & 6 & 6 & 12 & 8 & 10 & 6 & 8 & 10 & 8 & 12 & 10 & 6 & 8 & 8 & 10\cr
        15 & 8 & 8 & 10 & 6 & 8 & 8 & 10 & 6 & 8 & 4 & 10 & 10 & 8 & 12 & 10 & 10\cr
        }
        \]
    \item
    The probability the farthest from $\frac{1}{2}$ is $p_{0, 0} = 1$.

    Then the ouples $(a, b)$ with probability $p_{a, b} = \frac{1}{2} \pm \frac{6}{16}$ are:

    $(1, 5), (3, 15), (4, 8), (7, 7), (9, 4), (10, 11), (13, 12)$

    \item
    Notice that we have $x \cdot (a \oplus b) = (x \oplus a)\cdot(x \oplus b)$

    Take $(a, b)$ in the above list. We have $p_{a, b} = \frac{1}{2} \pm \frac{6}{16}$.

    Let $A = a\underbrace{0\dots0}_{28}$ and $B = b\underbrace{0\dots0}_{28}$.

    Fix $K_0, K_1$. Take $m \hookleftarrow \cU\left(\zo^{32}\right)$

    \begin{align*}
        \prob{A\cdot m = P(B)\cdot x_1} &= \prob{A\cdot (x_0 \oplus K_0) = P(B) \cdot (P(S(x_0))\oplus K_1)} && \text{by definition}\\
            &= \prob{(A\cdot x_0) \oplus (A \cdot K_0) = (P(B) \cdot P(S(x_0)) \oplus (P(B) \cdot K_1)} && \text{by distributivity}\\
    \end{align*}

    \begin{itemize}
        \item If $A \cdot K_0 = P(B) \cdot K_1$, then:
        \begin{align*}
            \prob{A\cdot m = P(B)\cdot x_1} &= \prob{A\cdot x_0 = P(B) \cdot P(S(x_0)}\\
                &= \prob{A\cdot x_0 = B \cdot S(x_0)} && \text{since } P(x) \cdot P(y) = x \cdot y\\
                &= \frac{1}{2} \pm \frac{6}{16} && \text{by question 3}
        \end{align*}
        \item If $A \cdot K_0 \neq P(B) \cdot K_1$, then:
        \begin{align*}
            \prob{A\cdot m = P(B)\cdot x_1} &= 1-\prob{A\cdot x_0 = P(B) \cdot P(S(x_0)}\\
                &= 1-\prob{A\cdot x_0 = B \cdot S(x_0)} && \text{since } P(x) \cdot P(y) = x \cdot y\\
                &= \frac{1}{2} \pm \frac{6}{16} && \text{by question 3}
        \end{align*}
    \end{itemize}
    Thus:
    \[\prob{A\cdot m = P(B)\cdot x_1} = \frac{1}{2} \pm \frac{6}{16}\]

    We check that the experimental distribution is close to the probabilities $\frac{2}{16} = 0.125$ or $\frac{14}{16} = 0.875$.
{'fraction_non_alphanumeric': 0.23447057224412124, 'fraction_numerical': 0.13225499524262607, 'mean_word_length': 1.6036801132342533, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 72, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3990739', 'n_tokens_mistral': 3969, 'n_tokens_neox': 3113, 'n_words': 1039}