The strength of the SED Algorithm...

The details that follow, are given for people who have no major difficulties with the understanding of the book "Cryptography, theory and practice" from Douglas Stinson (CRC Press, Inc. 2000 Corporate Blvd., Boca Raton, Florida 33431 USA).

A new cryptographic algorithm always led to serious suspicions. Its strength, which is its most important element, is impossible to prove mathematically.

Everything that concerns the LFSR have always had a negative image because, twenty years ago, the schema of Whitfield Diffie and Martin Hellman (IEEE Transaction on Information Theory, vol. IT-22, N° 6, 1976), dealing with the transmission of session keys, was broken by Don Coppersmith (IEEE Transaction on Information Theory, Vol. IT-30, N° 4, 1984). He proved it was easy to find the discrete logarithm of a vector from a LFSR sequence.

Therefore, experts left beside this domain.

It is important to note that these theories are not applicable to the SED algorithm because it combines two mappings of discrete logarithms in two different bases.

The discrete logarithms of vectors E and C are linked as follows:

DL_dlb=63(C) * K * X * K = DL_dlb=30(E)

Where:

E = SED(K,C) = DLM₃₀(K,DLM₆₃(K,C))
K is the ciphering key
X is the ratio DL₃₀(V)/DL₆₃(V), with V being the DLM₆₃(K,C).

The strength of the SED algorithm lays in the fact that X has a different value for each V (which is determined by K and C).

It is easy to compute the discrete logarithms of E and C in their own basis, but there is no known algorithm that permits the computation of K. Furthermore, there is no polynomial relationship between X and K !

We explain now that every value of X has the same probability to appear and there is no particular set of values that must be used to make SED work properly.

Exhaustive analysis of GF(127) with basis P⁰+P³+P⁷=0 and P⁰+P¹+P⁷=0 shows that the probability for every vector V to have a different X value corresponds to a Poisson’s distribution.

The results are as follows:

Poisson Probability	Experimental value	Theoretical value
P(0)	54	46.35 (=126/e)
P(1)	41	46.35 (=126/e)
P(2)	18	23.35 (=126/2*e)
P(3)	9	7.73 (=126/23e)
P(4)	1	1.93 (=126/234*e)
P(5)	1	0.39 (=126/2345e)
P(6)	1	0.06 (=126/23456*e)
P(7)	1	0.009 (=126/234567e)

The experimental values from this table indicate :

that 54 different values of X have no correspondent value of V,
that 41 different values of X have only 1 correspondent value of V,
that 18 different values of X have 2 different corresponding values of V,
that 9 different values of X have 3 different corresponding values of V,
that 1 value of X has 4 different corresponding values of V,
that 1 value of X has 5 different corresponding values of V,
that 1 value of X has 6 different corresponding values of V,
that 1 value of X has 7 different corresponding values of V.

The theoretical values are given in the second column.

We may conclude from this, that there is no preferential value for X. All the values of X have the same probability to appear so that the "great number law" applies.