cryptography – Page 3 – neverendingbooks

key-compression

Published January 4, 2008 by lieven

The main application of tori to cryptography is to exchange keys more efficiently while preserving the same security standards.

In the Diffie-Hellman key-exchange one interchanges elements of the finite field $F_{q}$ where $q = p^{N}$ is a prime-power of a large prime number $p$ . If we call an element of the prime field $F_{p}$ a pit (similar to bit when $p = 2$ ) then we can measure transmssions in pits. An element $h \in F_{q}$ requires N pits, for we can write the finite field as the quotient of ring of polynomials $F_{p} [x]$

$F_{q} = \frac{F_{p} [x]}{(f (x))}$

modulo an _irreducible_ polynomial $f (x)$ of degree N. Hence, any $h \in F_{q}$ can be written as a polynomial of degree $< N$ ,
$h = a_{1} + a_{2} x + \dots + a_{N} x^{N - 1}$
with all $a_{i} \in F_{p}$ , so we can represent $h = (a_{1}, a_{2}, \dots, a_{N})$ as N pits. Now, we are going to limit this number of pits (from $N$ to about $ϕ (N)$ where $ϕ$ is the Euler totient function, that is the number of integers smaller than N and coprime to it) by restricting the elements $h$ to be transfered to a subgroup of the group of units of the finite field $F_{q}^{*}$ while not compromising on the security of the public key system (the large order of the basic element $g \in F_{q}^{*}$ of which $h$ is a power).

To see that this is indeed possible, let us consider the easiest case (that of $N = 2$ ) and keep the discussion tori-free (those of you who know more will realize that Hilbert’s Satz 90 is never too far away…). If $q = p^{2}$ then the order of the cyclic group $F_{q}^{*}$ is $p^{2} - 1 = (p - 1) (p + 1)$ so in order to get a safe system let us choose the large prime number $p$ such that also tex/2=r $ is a prime number.

Right, now define $T_{2}$ to be the subgroup of $F_{q}^{*}$ of order $p + 1$ and let $g$ be a generator of it that we will use in the Diffie-Hellman exchange. Can we describe the element of $T_{2}$ (our torus in disguise)? Take $d \in F_{p}^{*}$ a non-square element, then we can write
$F_{q} = F_{p} (\sqrt{d})$ and $T_{2} = a + b \sqrt{d} : (a + b \sqrt{d})^{p + 1} = 1$ (here, $a, b \in F_{p}$ ). But we claim that
$(a + b \sqrt{d})^{p} = a - b \sqrt{d}$ . Indeed, $a^{p} = a, b^{p} = b$ and from Fermat’s little theorem we deduce that

$- 1 = (\frac{d}{p}) \equiv d^{\frac{p - 1}{2}} m o d (p)$

where the middle term is the Legendre symbol which is equal to -1 because d was a non-square modulo p. That is, we can then write $T_{2}$ as the algebraic variety of dimension one defined over $F_{p}$ and given by the equation

$T_{2} = a + b \sqrt{d} \in F_{q}^{*} ∣ (a, b) \in F^{2} : a^{2} - d b^{2} = 1$

Because $T_{2}$ is of dimension one over $F_{p}$ we can hope that most of its elements can be represented by just one pit (instead of the two pits necessary to represent them as elements of $F_{q}$ ). This is indeed the case, for we have explicit maps (in geometric terms, these maps show that $T_{2}$ is a rational variety)

$j : F_{p} \to T_{2} j (a) = \frac{a + \sqrt{d}}{a - \sqrt{d}} = \frac{a^{2} + d}{a^{2} - d} + \frac{2 a}{a^{2} - d} \sqrt{d}$

which has a well-defined invers on the complement of $1, - 1$

$f : T_{2} - 1, - 1 \to F_{p} f (a + b \sqrt{d}) = \frac{1 + a}{b}$

From the right-hand description of $j (a)$ one deduces that indeed we have that $f (j (a)) = a$ . Using this we can indeed compress the Diffie-Hellman exchange by a factor 2.

Instead of giving you the element $g^{a} \in T_{2}$ computed using my secret number a, I’ll send you (using only one pit) the number $f (g^{a}) \in F_{p}$ . On this number, you can apply the j-function to recover $g^{a}$ and then compute the common key $(g^{a})^{b} = g^{a b}$ using your secret number b). Still, we didnt compromise on security because we used the most difficult elements around in $F_{q}^{*}$ . By going to higher dimensional tori one can even improve on the efficiency rate!

tori & crypto : Diffie-Hellman or GCHQ?

Published January 3, 2008 by lieven

Boris Kunyavskii arXived the paper Algebraic tori – thirty years after dedicated to the 80th anniversary of V. E. Voskresenskii. The goal is to give an overview of results of V. E. Voskresenskii on arithmetic and birational properties of algebraic tori which culminated in his monograph “Algebraic Tori” published in Russian 30 years ago. As Ive worked on this stuff a long time ago I glanced through the paper and it contains a nice summary of the work of V.E. Voskresenskii, and later of Jean-Louis Colliot-Thelene, Jean-Jacques Sansuc and David Saltman. To my surprise I also made a guest-appearance and even seem to have a conjecture (??!!). Fortunately the ‘conjecture’ turned out to be correct as was proved by Nicole Lemire and Martin Lorenz. But a much bigger surprise (at least to me) is contained in the final section of the paper where applications of (stable) rationality of certain tori are given to primality testing and public key cryptography!

In [GPS]
the authors propose to use a similar idea of compression for using tori
in an even more recent cryptographic protocol (so-called pairing-based
cryptography). It is interesting to note that the efficiency (compression factor) of the above mentioned cryptosystems heavily depends on
rationality of tori under consideration (more precisely, on an explicit
rational parameterization of the underlying variety). As the tori used
by Rubin and Silverberg are known to be stably rational, the seemingly abstract question on rationality of a given stably rational torus
is moving to the area of applied mathematics. The first challenging
problem here is to obtain an explicit rational parameterization of the
8-dimensional torus $T_{30}$ , deïfined over a finite field k and splitting over
its cyclic extension L of degree 30.

This is a particular case of a problem posed by Voskresenskii [Vo77,
Problem 5.12] 30 years ago. Let us hope that we will not have to wait
another 30 years for answering this question on a degree 30 extension.

That’s all it takes to get me seriously side-tracked… so the last couple of hours I’ve been reading up on this connection between tori and cryptography. I will spend a couple of posts on these beautiful results. The latest seems to be that, while rationality of $T_{30}$ is still unknown, one can use an explicit stable-rationality description of it to get a better bound than the XTR-system (the system corresponding to the torus $T_{6}$ ) which in turn is better than the LUC-system (corresponding to $T_{2}$ ), which is turn is twice as efficient as the Diffie-Hellman key exchange system… So let us start gently with the latter one…

Whitfield Diffie (r.) and Martin Hellman (m.) published in 1976 their public key-exchange system. Take a large prime power $q = p^{N}$ , make it public and consider the finite field $F_{q}$ which is known to have a cyclic group of units $F_{q}^{*}$ of order $q - 1$ . Now, take $g$ to be an element in it of large order (preferable a generator but that isnt necessary) and also make this element public.

Now choose a random integer $a$ (your hidden secret) and compute the element $g^{a} \in F_{q}$ and publicize this element. Suppose someone else published his/her element $g^{b}$ constructed from his/her secret integer $b$ then both you and this other person can compute from the published data and their secret numbers the element (the shared key)

$g^{a b} = (g^{b})^{a} = (g^{a})^{b}$

(because you know $a$ and the published $g^{b}$ and your correspondent knows $b$ and the published $g^{a}$ ) but nobody else can compute it from the public-available data only because discrete logarithms cannot be feasibly computed in the group $F_{q}^{*}$ . Hellman suggests to call this system the Diffie-Hellman-Merkl key-exchange (via this link)

The first researchers to discover and publish the concepts of PKC were Whitfield Diffie and Martin Hellman from Stanford University, and Ralph Merkle from the University of California at Berkeley. As so often happens in the scientific world, the two groups were working independently on the same problem — Diffie and Hellman on public key cryptography and Merkle on public key distribution — when they became aware of each other’s work and realized there was synergy in their approaches. In Hellman’s words: “We each had a key part of the puzzle and while it’s true one of us first said X, and another of us first said Y, and so on, it was the combination and the back and forth between us that allowed the discovery.”

And that was the full story until 1997. In December, 1997, it was revealed that researchers at the GCHQ organization did some work in the early 1970’s in the field of “non-secret encryption”. The people involved are James Ellis, Clifford Cocks and Malcolm Williamson (r.).

Here is a note by Ellis on his recollection of the history of ‘Non-secret encryption” :

Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work,
because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography
is realised by minimising the information available to potential adversaries. Thus professional cryptographers
normally work in closed communities to provide sufficient professional interaction to ensure quality while
maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests
of historical accuracy after it has been demonstrated clearly that no further benefit can be obtained from
continued secrecy.
In keeping with this tradition it is now appropriate to tell the story of the invention and development within
CESG of non-secret encryption (NSE) which was our original name for what is now called PKC. The task of writing
this paper has devolved on me because NSE was my idea and I can therefore describe these early developments from
personal experience. No techniques not already public knowledge, or specific applications of NSE will be mentioned…

The once secret notes of Williamson are also available. NON-SECRET ENCRYPTION USING A FINITE FIELD
by M J Williamson, 21 January 1974 and THOUGHTS ON CHEAPER NON-SECRET ENCRYPTION
M J Williamson, 10 August 1976.

daddy wasn’t impressed

Published December 19, 2007 by lieven

A first year-first semester course on group theory has its hilarious moments. Whereas they can relate the two other pure math courses (linear algebra and analysis) _somewhat_ to what they’ve learned before, with group theory they appear to enter an entirely new and strange world. So, it is best to give them concrete examples : symmetry groups of regular polygons and Platonic solids, the symmetric group etc. One of the lesser traditional examples I like to give is Nim addition and its relation to combinatorial games.

For their first test they had (among other things) to find a winning move for the position below in the Lenstra’s turtle turning game. At each move a player must put one turtle on its back and may also turn over any single turtle to the left of it. This second turtle, unlike the first, may be turned either onto its feet or onto its back. The player wins who turns the last turtle upside-down.

So, all they needed to see was that one turtle on its feet at place n is equivalent to a Nim-heap of height n and use the fact that all elements have order two to show that any zero-move in the sum game can indeed be played by using the second-turtle alternative. (( for the curious : the answer is turning both 9 and 4 on their back ))

A week later, one of the girls asked at the start of the lecture :

Are there real-life applications of group-theory? I mean, my father asked me what I was learning at school and I told him we were playing games turning turtles. I have to say that he was not impressed at all!.

She may have had an hidden agenda to slow me down because I spend an hour talking about a lot of things ranging from codes to cryptography and from representations to elementary particles…

For test three (on group-actions) I asked them to prove (among other things) Wilson’s theorem that is

$(p - 1)! \equiv - 1 mod p$

for any prime number $p$ . The hint being : take the trivial action of $S_{p}$ on a one-element set and use the orbit theorem. (they know the number of elements in an $S_{n}$ -conjugacy class)

Fingers crossed, hopefully daddy approved…

Tag: cryptography

key-compression

tori & crypto : Diffie-Hellman or GCHQ?

daddy wasn’t impressed