Hello,
I am a 20 year old german student and hobby cryptographer, with
strong interests in public key algorithms, cryptographic protocolls
and cryptanalysis. In the year 2003 I came up with a new signature
scheme based on the closest vector problem. This scheme was successfully
presented at germans biggest youth science fair "Jugend Forscht" and one
year later at the Intel ISEF (International Science and Engineering Fair)
in Phoenix, Arizona.
By now, I have not only added an public key encryption algorithm but
also analyzed the algorithm for weaknesses. Hence, the time has come,
where this algorithm has to be presented to a great audience to analyze
it even further.
Here is a first small (and simplyfied) overview: In order to get a
new type of public key encryption algorithm, that is not based on the
factoring problem or the discrrete logarithm in finite fields, we have
to find a suitable hard mathematical problem.
The closest vector problem (i.e. given a random n-dimensional lattice A,
and a random n-dimensional point B, find a lattice point, that is closest
to B. A lattice is just a normal basis for a vector space, with the
addition requirement, that you are only allowed to multiply the basis
with integer-vectors (not real-vectors), to obtain a lattice point).
This closest-vector problem can be solved in practise up to dimensions
of 300. However, a basis for such a lattice contains 300*300 real values
(= 90000), hence it is a bit too large to be practical.
I came up with a new method, to get a hard instance (whether this is
really true, has to be analyzed) of this problem with a cyclic modular
lattice. I need only n values, to save a complete basis. Hence I can
use dimension up to 1000 efficiently.
The new algorithm is based upon a "almost linear homomorphic oneway
function", i.e. a function, which preserves the original group structure:
f(a, x) + f(b, x) = f(a+b, x) + e, where e is a small error for each
addition (hence, it's only almost linear). Furthermore we can exchange
a and x. (-> f(x, a) + f(x, b) = f(x, a+b) )
This function (and my first cryptanalytical research) is described
completely in the paper, which you can find on this website:
http://turbo-crypt.sourceforge.net/
You can download the paper directly,
from: http://turbo-crypt.sourceforge.net/TurboCrypt.pdf
Using this function, we can compute a public key in the following way:
PublicKey = {y1 = f(x1, g), y2 = f(x2, g), x1, x2}
The private key is g.
Now we can sign by computing:
1. Choose r at random
2. Compute R = {R1 = f(x1, r), R2 = f(x2, r)}
3. Compute {e1, e2} = Hash(R + Message)
4. Signature s = e1*g + e2*r
The Signature = {R, s}
The signature is verificated by:
1. Recompute {e1, e2} as has been done above
2. Compute U = {f(x1, s), f(x2, s)}
3. Compute V = {e1*y1 + e2*R1, e1*y2 + e2*R2}
4. Check, that U-V is small
There are some more details, which you can find in the paper.
The encryption function is similiar to the El Gamal encryption function.
You can find a complete description in the paper on the ciphers website:
http://turbo-crypt.sourceforge.net/
I would like, if you could send me any comment, critics or cryptanalysis
you can come up with, to my email address. Your contribution will be
honored: I will publish you critics with your name (unless, of course,
you do not want me to do so) on my website for the cryptosystem.
I look forward to hearing from you.
Sincerly,
Gerold Gruenauer
Jetzt neu! Sch=FCtzen Sie Ihren PC mit McAfee und WEB.DE. 3 Monate
kostenlos testen. http://www.pc-sicherheit.web.de/startseite/
|
