Schmeh's cryptogram finally solved after 6 years!

Heureka, the cryptogram that was published in 2007 by Klaus Schmeh [1] was finally solved on 26.11.2013 by George Lasry. MysterieTwister (user: george4096) made today the official announcement about his achievement.

Elliptic Curves with trace t = 1 [Practice]

So here comes the practical aspect of the previous post about elliptic curves with trace $1$.

I use SAGE for practical demonstration. You can use the online notebook functionality of it, e.g., under sagenb.org or nt.sagenb.org.

I use the curve $y^2 = x^3 + x + 4$, which has $19$ points over $\mathbb{F}_{19}$ and hence has trace equal to one.

--- Input
p = 19;
K = GF(19);
E = EllipticCurve(K,[1,4]); #y^2 = x^3 + x + 4
print "E is: ",E;
print "#E[K] = ",E.count_points();  
--- Output
E is:  Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 19
#E[GF(19)] =  19

Elliptic Curves with trace t = 1 [Theory]

In this post, i will show the proof that one could efficiently compute the discrete logarithm on a curve $E[\mathbb{F}_p]$ if the number of points on that curve is equal to $p$. Such a curve is called anomalous. Since $$\#E[\mathbb{F}_p] = p+1-t$$ this is again equal to the statement that the trace $t$ of the curve is equal to $1$. The proof was given by Nigel Smart [1], Satoh and Araki [2], or Semaev [3] independently roughly at the same time ($\sim$ 1999).

Remark: The attack is somehow similar to the described lift in that post, which executes the lift $\mathbb{Z}/p\mathbb{Z} \rightarrow \mathbb{Z}/p^2\mathbb{Z}$, and that solves the dlp in the subgroup of order $p$ in $\mathbb{Z}/p^2\mathbb{Z}$.

Pairings-based Cryptography (Part 1)

This post contains some basic facts about Pairing-based Cryptography. I write this post mainly for the reason to have a easy to find reference for myself and to recall some definitions. For readers that are more interested in pairings in context of cryptography, a good further reading source is the dissertation of Lynn [1], wherefrom i also adopted the usage of the multiplicative notation as a shortcut to represent $$\underbrace{a\circ a\circ ... \circ a}_{n\;times} = a^n$$ if $\circ$ is the group operation of $\mathbb{G}$ and $a \in \mathbb{G}$.

Definition [Pairing] Let $r$ be a prime number and $\mathbb{G}_1$ and $\mathbb{G}_T$ be cyclic groups of order $r$. Let $\mathbb{G}_2$ [not necessary cyclic] in which every element has order $r$. Then a pairing is the map \begin{equation} e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T \end{equation} and which has the properties ($\mathsf{e}$ is the neutral element in the group): (Non-Degeneracy) $e(g_1,g_2) = \mathsf{e}_{\mathbb{G}_T}$ for all $g_2\in\mathbb{G}_2$ if and only if $g_1 = \mathsf{e}_{\mathbb{G}_1}$ (Non-Degeneracy) $e(g_1,g_2) = \mathsf{e}_{\mathbb{G}_T}$ for all $g_1\in\mathbb{G}_1$ if and only if $g_2 = \mathsf{e}_{\mathbb{G}_2}$ (Bilinearity) $e(g_1^a,g_2^b) = e(g_1,g_2)^{ab}$ for all $g_1\in\mathbb{G}_1$ and $g_2\in\mathbb{G}_2$ for all $a,b\in\mathbb{Z}$.

An explicit formula for the discrete logarithm

I guess, but i am not sure, many people don't know that there is an explicit formula for the discrete logarithm in finite fields $\mathbb{F}^*_p$. I remember that i was quite surprised when i learned the formula many years ago.

Theorem [Explicit DL Formula] Let $p$ be a prime number $>2$ and $g$ be a primitive root in $\mathbb{F}^*_p$. Then the discrete logarithm of the element $a \in \mathbb{F}^*_p$ is equal to \begin{equation} \mathsf{dlog}_{p,g}(a) = \sum^{p-2}_{k=1} \frac{a^k}{1-g^k}\pmod{p}\end{equation}

The proof is actually not that complicated and can be found in Niederreiter [1]. I will give here a new proof for you: