Public Key | neverendingbooks

Posts Tagged ‘public key’

key-compression

Friday, January 4th, 2008

rationality & cryptography

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 $\mathbb{F}_q$ where q=p^N is a prime-power of a large prime number . If we call an element of the prime field $\mathbb{F}_p$ a pit (similar to bit when p=2 ) then we can measure transmssions in pits. An element $h \in \mathbb{F}_q$ requires N pits, for we can write the finite field as the quotient of ring of polynomials $\mathbb{F}_p[x]$

$\mathbb{F}_q = \frac{\mathbb{F}_p[x]}{(f(x))}$

modulo an irreducible polynomial f(x) of degree N. Hence, any $h \in \mathbb{F}_q$ can be written as a polynomial of degree < N , $h = a_1 + a_2 x + \hdots + a_N x^{N-1}$ with all $a_i \in \mathbb{F}_p$ , so we can represent $h=(a_1,a_2,\hdots,a_N)$ as N pits. Now, we are going to limit this number of pits (from to about $\phi(N)$ where $\phi$ is the Euler totient function, that is the number of integers smaller than N and coprime to it) by restricting the elements to be transfered to a subgroup of the group of units of the finite field $\mathbb{F}_q^_$ while not compromising on the security of the public key system (the large order of the basic element $g \in \mathbb{F}_q^_$ of which 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 $\mathbb{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 such that also tex/2=r[/tex] is a prime number.

Right, now define T_2 to be the subgroup of $\mathbb{F}_q^_$ of order p+1 and let 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 \mathbb{F}_p^_$ a non-square element, then we can write $\mathbb{F}_q = \mathbb{F}_p(\sqrt{d})$ and $T_2 = \{ a+b\sqrt{d}~:~(a+b\sqrt{d})^{p+1}=1 \}$ (here, $a,b \in \mathbb{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 = (\tfrac{d}{p}) \equiv d^{\tfrac{p-1}{2}}~mod(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 $\mathbb{F}_p$ and given by the equation

$T_2 = \{ a+b\sqrt{d} \in \mathbb{F}_q^*~\mid~(a,b) \in \mathbb{F}^2~:~a^2-db^2=1 \}$

Because T_2 is of dimension one over $\mathbb{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 $\mathbb{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~:~\mathbb{F}_p \rightarrow T_2~\quad~j(a) = \frac{a+\sqrt{d}}{a-\sqrt{d}}=\frac{a^2+d}{a^2-d}+\frac{2a}{a^2-d}\sqrt{d}$

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

$f~:~T_2 - \{ 1,-1 \} \rightarrow \mathbb{F}_p~\quad~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 \mathbb{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^{ab}$ using your secret number b). Still, we didnt compromise on security because we used the most difficult elements around in $\mathbb{F}_q^*$ . By going to higher dimensional tori one can even improve on the efficiency rate!