SED stands for Secure
Encryption Device. It is built on a modular basis by multiplicative functions
applied to groups of different types being an integral part of the finite field
GF(2127-1).
The SED algorithm consists
in two consecutive mappings of the DLM algorithm in 2 different logarithmic bases (63
and 30) and is illustrated by the following formulas :
E = SED(K,C) = DLM30(K,DLM63(K,C))
C = SED(K-1,E) = DLM63(K-1,DLM30(K-1,E))
K*K-1 = 1 modulo(2127-1)
C is the clear message, E is the encrypted
message, K encryption key, K-1 decryption key
For example in GF(2n=5-1),
for C = 22 and K = 23, the SED gives E = DLM3(23,DLM2(23,22))
= 23
The transparency of the
above formulas allows us to claim that there is no place for a Trojan Horse in
the SED algorithm.
On its own, the DLM algorithm
does not offer any security when working with blocks of 127 bits
(reference : Shanks and Pohlig-Helleman, "An improved algorithm for
computing logarithms in GF(p) and its cryptographic significance", IEEE
Trans. Inform. Theory, vol. IT-24, 1978, pp. 106-110). Today, it seems that
blocks of 800 bits are necessary to ensure a high level of security.
However, the association of
two consecutive DLM mappings with blocks of 127 bits, operated in different
logarithmic bases, allows the transformation of one element of the above
mentioned space to another element of the same space under the control of a
key, also of the same space, this, with a high level of security.
The SED algorithm ciphers
with the key K and the mappings DLMdlb1 and DLMdlb2,
while the deciphering operation is done by using the inverse key K-1
and by inverting the ranking of these mappings : DLMdlb2 and then
DLMdlb1.
In the finite field GF(2n=127-1),
there exist several primitive trinomes P0+Pdlb+P127 =
0 that allow the creation of a maximum sequence (dlb = 1, 7, 15, 30, 63, 64,
97, 112, 120, 126).
In it's present version,
the SED algorithm works with dlb1 = 63, dlb2 = 30.
You will find numerous
works in cryptographic litterature dealing with discrete logarithms. They
generaly refer to arithmetic multiplications of discrete logarithms. Some of
these articles deal with matrix mutiplication, but they are always done on the
same basis. They all conclude that, if you are able to reduce the multiplications
to one operation (commutativity of the multiplication), you should at least
work with blocks of 800 bits to offer some security.
To our knowledge, until
today, nobody has proposed two consecutive matrix multiplications in two
different basis in the same finite field. By doing this, it is impossible to
reduce the number of operations to one operation in one finite field. The
conclusion is that there is no polynomial relation between the discrete
logarithm of the entry block in the first basis and the discrete logarithm in
the second basis.
To break the SED algorithm
(i.e. finding the corresponding key to a pair of entry and exit vectors) one
would have to establish the inter-linking number whose discrete logarithm in
different logarithmic bases, would offer the same relation of proportionality
with the discrete logarithms of the entry and exit vectors !
For each pair of given
entry or exit vectors, of the DLM algorithm, there is one and only one
key. However, for each pair of two given entry or exit vectors, of the SED
algorithm, formed by two different (in their logarithmic basis) DLM mappings,
there is on average one key and the probability of zero, one or several keys is
given by a Poisson distribution with an average of 1. This allows us to confirm
that, for 20 given pairs, the probability that there are no values X verifying
the relationship
DLM30(X,DLM63(X,X)) = (2125) *Ln a
is determined by :
prob (X does not exist) = (1/2.7182818284..)20 = 2.061 10-09.
As a consequence of this,
unlike the RSA and the DES, who have fixed points during encryption, we can
prove that the SED doesn't have any fixed point.
Comparison of the SED
algorithm and other algorithms highlights the following :
�������������������������� Algorithmes pour vecteurs de 128 bits
���� A partir de la version 2.00 de ClassicTit.exe et de ClassicTaPr.exe
1� G�n�ralit�s
L�algorithme DLM est appliqu� � un vecteur de 127 bits avec une clef de 127 bits. L�inverse de cette clef a aussi 127 bits. La multiplication modulaire, utilis�e dans les algorithmes SED et SEDxor s�effectue �galement avec des nombres de 127 bits. Pour des raisons pratiques, ces op�rations sont �tendues � des vecteurs ayant tous 128 bits. Un bit est enlev� � ceux-ci; ensuite l�op�ration est effectu�e et un bit est ajout� au r�sultat obtenu. Pour ce faire, les r�gles suivantes sont appliqu�es.
R�gle 1
Position du bit enlev� � un vecteur de 128 bits
En consid�rant le vecteur de 128 bits comme un nombre, le bit enlev� est le bit le moins significatif si la parit� du vecteur de 128 bits est vraie (nombre pair de bits 1) ou c�est le bit le plus significatif dans le cas contraire.
R�gle 2
Valeur du bit ajout� � un vecteur de 127 bits
Apr�s ex�cution de l�op�ration effectu�e sur les vecteurs r�duits � 127 bits, un bit est ajout� au r�sultat.
La valeur de ce bit est choisie de telle sorte que la parit� du vecteur recompos� de 128 bits est semblable � celle du vecteur de 128 bits auquel, apr�s r�duction � 127 bits, l�op�ration a �t� appliqu�e.
Ainsi, la clef inverse de 128 bits a la m�me parit� que la clef directe de 128 bits.
Le vecteur de 128 bits r�sultant d�une application de l�algorithme DLM a la m�me parit� que le vecteur de 128 bits auquel, apr�s r�duction � 127 bits, l�op�ration a �t� appliqu�e et cela ind�pendamment de la parit� de la clef.
Le vecteur de 128 bits r�sultant de la multiplication modulaire incorpor�e aux algorithmes SED et SEDxor a la m�me parit� que le vecteur de 128 bits auquel, apr�s r�duction � 127 bits, l�op�ration a �t� appliqu�e et cela ind�pendamment de la parit� de la clef qui est utilis�e comme multiplicateur.
R�gle 3
Position du bit ajout� � un vecteur de 127 bits
Le bit ajout� au vecteur de 127 bits est plac� de telle sorte qu�il devienne le bit le moins ou le plus significatif du vecteur recompos� (consid�r� comme un nombre) suivant que la parit� de ce vecteur recompos� est vraie ou fausse.
2� Calculs
Calcul d�une clef inverse de 128
bits
La clef directe de 128 bits est transform�e en clef directe de 127 bits en suivant la r�gle 1. Cette clef directe est invers�e. La clef inverse de 127 bits obtenue est transform�e en clef inverse de 128 bits en suivant les r�gles 2 et 3.
La clef directe de 128 bits est retrouv�e � partir de la clef inverse de 128 bits en appliquant une proc�dure semblable.
Algorithme DLM-128 appliqu� � un
vecteur de 128 bits
Le vecteur et la clef sont r�duits � 127 bits en suivant la r�gle 1. L�algorithme DLM est appliqu� au vecteur de 127 bits avec la clef de 127 bits. Le vecteur r�sultant de 127 bits est transform� en vecteur de 128 bits en suivant les r�gles 2 et 3.
Dans le texte ci-dessous, cette suite d�op�rations appliqu�e � un vecteur de 128 bits avec une clef de 128 bits et donnant un vecteur r�sultant de 128 bits est appel�e algorithme DLM-128, DLM63-128 ou DLM30-128.
Algorithme MAM-128 appliqu� �
deux vecteurs de 128 bits
Les vecteurs sont transform�s en nombres de 127 bits en suivant la r�gle 1.
La multiplication modulo (2exp127 -1) de ces nombres, l�un par l�autre, est effectu�e.
Le nombre r�sultant de 127 bits est transform� en vecteur de 128 bits en suivant les r�gles 2 et 3.
Dans le texte ci-dessous, cette suite d�op�rations appliqu�e � deux vecteurs de 128 bits et donnant un vecteur r�sultant de 128 bits est appel�e algorithme MAM-128. L�algorithme MAM-128� a �t� introduit en 1999 suite � l��tude de Mieczyslaw Kula : A cryptosystem based on double discrete logarithm.
Algorithme SED appliqu� � un
vecteur de 128 bits
L�algorithme SED63/30 comporte les op�rations suivantes:
����� application de
l�algorithme DLM63-128� au vecteur
d�entr�e de 128 bits avec la clef de 128 bits,
����� si la parit� du vecteur
de 128 bits obtenu � l�op�ration pr�c�dente est fausse, recherche du vecteur
compl�ment (bit � bit),
����� application de
l�algorithme MAM-128 au vecteur de 128 bits, obtenu � l�op�ration pr�c�dente,
avec la clef de 128 bits utilis�e comme multiplicateur,
����� application de
l�algorithme DLM30-128� au vecteur de
128 bits, obtenu � l�op�ration pr�c�dente, avec la clef de 128 bits.
Un m�me vecteur est utilis� comme clef pour les algorithmes DLM-128 et comme multiplicateur pour l�algorithme MAM-128.
L�algorithme inverse SED30/63 comporte les m�mes op�rations; mais celles-ci sont ex�cut�es en ordre inverse et avec la clef inverse.
Algorithme SEDxor appliqu� � un
vecteur de 128 bits
L�algorithme SEDxor63/30 comporte les op�rations suivantes:
����� application de
l�algorithme DLM63-128� au vecteur
d�entr�e de 128 bits avec la clef de 128 bits,
�si la parit� du vecteur de 128 bits obtenu � l�op�ration pr�c�dente est fausse, recherche du vecteur compl�ment (bit � bit),
�application de l�algorithme MAM-128 au vecteur de 128 bits, obtenu � l�op�ration pr�c�dente, avec la clef de 128 bits utilis�e comme multiplicateur,
����� application d�une
op�ration XOR (bit � bit) au vecteur de 128 bits, obtenu � l�op�ration
pr�c�dente, avec un vecteur Vxor de 128 bits,
�application de l�algorithme DLM30-128� au vecteur de 128 bits, obtenu � l�op�ration pr�c�dente, avec la clef de 128 bits.
Un m�me vecteur est utilis� comme clef pour les algorithmes DLM-128 et comme multiplicateur pour l�algorithme MAM-128.
Il est � noter que l�op�ration XOR peut modifier la parit� du vecteur.
L�algorithme inverse SEDxor30/63 comporte les m�mes op�rations; mais celles-ci sont ex�cut�es en ordre inverse et avec la clef inverse.
Chiffrement SEDxor d�un texte ou
d�un fichier binaire
Les op�rations suivantes sont effectu�es:
����� tron�onnage du texte ou
du fichier binaire en tranches de 128 bits; si n�cessaire il faut compl�ter la
derni�re tranche en ajoutant des lettres U ou des octets de valeur H55 suivant
qu'il s'agit d'un texte en code ASCII ou d�un fichier binaire,
����� Application de
l�algorithme SEDxor63/30 � chaque tranche avec une m�me clef et avec un m�me
vecteur Vxor; l�ensemble des vecteurs r�sultants forment le texte chiffr�,
����� devant le texte chiffr�,
placement d�un vecteur chiffr� SEDxor contenant notamment la date et l�instant
du chiffrement, le nombre de vecteurs du texte chiffr� et le nombre de
caract�res ajout�s � la derni�re tranche.
Chiffrement SED-cha�n� d�un texte
ou d�un fichier binaire
Les op�rations suivantes sont effectu�es pour obtenir un condens� significatif:
����� tron�onnage et
transposition �ventuelle du texte ou du fichier binaire en tranches de 128
bits; si n�cessaire il faut compl�ter la derni�re tranche en ajoutant des lettres
U, des chiffres 5 ou des octets de valeur H55 suivant qu'il s'agit d'un texte,
d�une suite de chiffres hexad�cimaux� en
code ASCII ou d�un fichier binaire,
����� application de
l�algorithme SEDxor63/30 � chaque tranche avec ce m�me vecteur comme clef et
avec la r�sultat du chiffrement de la tranche pr�c�dente comme vecteur Vxor;
pour la premi�re tranche le vecteur Vxor est nul (000....00).
Le vecteur de 128 bits r�sultant du chiffrement de la derni�re tranche est le condens� significatif recherch�.
Conventions concernant les
vecteurs singuliers
Les vecteurs singuliers sont: (111...111), (011..111), (000..000), (100...000).
Les r�gles suivantes sont appliqu�es:
����� un vecteur singulier ne
peut �tre utilis� comme clef; les clefs �tant normalement choisies au hasard,
les vecteurs singuliers peuvent �tre rejet�s; mais lors d�un chiffrement
SED-cha�n�, si une tranche forme un vecteur singulier, le chiffrement doit �tre
arr�t� et le r�sultat est par convention le vecteur nul (000...000),
����� le r�sultat de
l�application de l�algorithme DLM-128 � un vecteur singulier au moyen d�une
clef non singuli�re est, par convention, le vecteur singulier inchang�,
����� le r�sultat de l�application
de l�algorithme MAM-128 � un vecteur singulier avec un vecteur non singulier
comme multiplicateur est, par convention, le vecteur singulier inchang�.
Lorsque le vecteur d�entr�e n�est pas singulier l�application de l�algorithme SED ne donne jamais un r�sultat singulier; il n�en est pas de m�me pour l�algorithme SEDxor o� l�op�ration XOR pourrait �ventuellement donner un vecteur singulier. Il importe de remarquer que le vecteur Vxor doit �tre consid�r� comme ayant une valeur al�atoire, et de ce fait, la probabilit� d�obtention d�un vecteur singulier peut �tre consid�r�e comme pratiquement nulle.
Programme de d�monstration et son logiciel code source
Programme pour le calcul de la vitesse de chiffrement