NumberWorld

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.

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

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}$.

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{...

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$ [i.e. the exponent $x$ from $g^x \equiv a\pmod{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} Note: This is a finite-sum identity that still costs $\approx \mathcal{O}(p)$ field ops, so it’s not a practical attack on discrete log for large primes but it’s conceptually neat (character sums / interpolation flavor). Although the discrete logarithm is naturally defined modulo $p-1$, the above identity evaluates in $\mathbb{F}_p$ and yields the unique integer representative in ${0,\dots,p-2}$. Th...