Skip to content →

neverendingbooks Posts

overloaded iTouch

Published January 5, 2008 by lievenlb

A jailbroken iTouch can do many wonderful tricks : by sarting up an AFDd server one can use it in Disk mode, exactly as an iPodClassic, one can use it as a WebServer by installing Apache and PHP and run a Wiki, one can install OpenSSH and secure shell to the rest of the world, one can even turn the iTouch into a music streamer via the FireFly server, one can …

And all of this on a gadget with only 116Mb RAM and one processor running at 412MHz… is asking for overload problems both on memory and battery. A couple of days ago I wanted to start up the iTouch and was greeted by a bright flickering screen and thought I’d finally bricked it…

Fortunately, there’s a simple lesson to be learned : with every new feature you install, learn how to switch if off and monitor your iTouch using the SysInfo.app (under Utilities) which allows to view basic system info (screenshot below) as well as all active processes.

Here a few tricks to turn on/off the major consumers :

  1. To turn off the Apache-sever, ssh into the iTouch and give a apachectl stop command (you can always restart it with apachectl start.

  2. To control OpenSSH, install the Services.app (under Utilities) which allows to toggle Wifi, Edge, SSH and Bluetooth on or off (screenshot below).

  3. To control APFd, use its control pannel to toggle the Broadcast active feature only when you need your iTouch in Disk mode (it will then appear under Shared in your Finder window, at least under Leopard. For more on this see Mount and use your iPod touch as a Thumb Drive.

  4. To control FireFly, use the UIctl.app (under Multimedia) and scroll down (after staring for about 15 seconds to a white screen) to org.fireflymediaserver.mt-daapd, tap it and start or stop the server.

Another major consumer is the MobileRSS.app (under Productivity). Maybe I should restrict my subscriptions to the hottest blogs only…

4 Comments

key-compression

Published January 4, 2008 by lievenlb

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 $p $. 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 + \ldots + a_N x^{N-1} $
with all $a_i \in \mathbb{F}_p $, so we can represent $h=(a_1,a_2,\ldots,a_N) $ as N pits. Now, we are going to limit this number of pits (from $N $ 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 $h $ 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 $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 $\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 $p $ such that also tex/2=r $ is a prime number.

Right, now define $T_2 $ to be the subgroup of $\mathbb{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 \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 = (\frac{d}{p}) \equiv d^{\frac{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!

3 Comments

tori & crypto : Diffie-Hellman or GCHQ?

Published January 3, 2008 by lievenlb

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 first challenging
problem here is to obtain an explicit rational parameterization of the
8-dimensional torus $T_{30} $ , deïfined over a finite field 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 $\mathbb{F}_q $ which is known to have a cyclic group of units $\mathbb{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 \mathbb{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^{ab}=(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 $\mathbb{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.

2 Comments