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