Here is today’s first problem:

Let the public key be $(y, p, g) = (64, 101, 2)$. The El Gamal Digital Signature of $11$ is $(r, s) = (8, s)$, where $s=$?

  • What is the El Gamal Signature Scheme?
    wikipedia: The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.

    my notes:

    1. Public / Private Keys:
      A triple $(y, p, g)$, where $p$ is a prime number, $g$ is a generator for $\mathbb{Z}_{p}^{*}$ and $y \equiv g^x \pmod p$ where x is the private Key.

    2. Signing:
      The signature of a message $m$ is a pair $(r, s)$. Since this is a probabilistic signature scheme, in order to generate such a pair, the signer begins by choosing a random number $k$ such that $0 \ne k \ne p-1$ and $\gcd (k, p-1) = 1$. Then,

      \[r \equiv g^{k} \pmod p \\ s \equiv (m - xr)\cdot k^{-1} \pmod{(p-1)}\]
    3. Verifying:
      Check that $g^{m} \equiv y^{r} r^{s} \pmod p$

    The equation for s in the Signing step was obtained as follows:

    \[g^m \equiv y^r r^s \pmod p \\ g^m \equiv g^{xr} g^{ks} \pmod p \\ g^m \equiv g^{xr + ks} \pmod p \\ m \equiv xr + ks \pmod{(p-1)} \\ s \equiv (m - xr) k^{-1} \pmod{(p-1)}\]

    The second-to-last step might be confusing. Since $g$ is a generator of $\mathbb{Z}_p^*$ and $p$ is a prime number, we have that

    \[g^z \equiv g^{z + (p-1)} \pmod p\]

    for any $z \in \mathbb{Z}$. In other words, the powers of $g$ are congruent modulo $p-1$.

For this problem, we need to find $s$. We already have the values of $m$,$r$ and $p$, which means we need the values of $x$ and $k$. Those can be found easily by examining these equations:

\[64 \equiv 2^{x} \pmod{101} \\ 8 \equiv 2^{k} \pmod{101}\]

It is clear that $x=6$ and $k=3$. We can now find $s$ as,

\[s \equiv (11 - 6 \cdot 8) \cdot 3^{-1} \equiv \frac{-37}{3} \equiv \frac{63}{3} \equiv 21 \pmod{100}\]

Therefore, $s=21$ is the solution to this problem.

Let’s move on to the next one:

The Hadamard gate is applied to the two qubits of a 2-qubit system in state

\[\frac{1}{2} (|00 \rangle + |01 \rangle + |10 \rangle + |11 \rangle).\]

What is the resulting state of the 2-qubit system?

My notes, this youtube video and this stackexchange answer allowed me to understand how we can apply a Hadamard gate to two qubits.

First, we can rewrite the given state of the 2-qubit system as:

\[\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)\otimes\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)\]

Now we will apply the Hadamard operation on each of these qubits,

\[H \left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right) = \left(\frac{1}{\sqrt{2}} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix}\right) \left(\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}\right) = \begin{bmatrix}1\\0\end{bmatrix}\]

And finally take the tensor product of the output from the operation,

\[\begin{bmatrix}1\\0\end{bmatrix} \otimes \begin{bmatrix}1\\0\end{bmatrix} = \begin{bmatrix}1\\0\\0\\0\end{bmatrix}\]

which is equivalent to $\lvert 00\rangle$, the solution to this problem.

Even though I was able to solve this problem, I do not know anything about quantum computing. It seems like a very cool subject and I’d love to read and learn more about it. Until next time!