# The SED Algorithm

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.

## The strength of the SED Algorithm

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.

## The SED algorithm and the others

Comparison of the SED algorithm and other algorithms highlights the following :

• SED and RSA have the same space for the key and the data. The encrypting and deciphering keys are different in both systems. For RSA, the space for the key and for the data is function of the key. For SED, the space is always the same and corresponds to 2127.
• Unlike the RSA and the DES, every value of the space GF(2127-1) may be used as key for the SED algorithm : there is no fixed point or weak key.
• A calculation stratagem can extend the space from 2127 to 2128 (or 2exp(27)) which facilitates the manipulation of data and makes printing of integrated circuits easier.
• The length of the key and data block is between 4 to 8 times lower for the SED algorithm than for the RSA, this allows a faster encryption and reduced volume of hardware. Moreover, the SED algorithm uses only XOR and branching functions which enable an implementation in an ASIC or microprocessor with low level instructions.
• There is no known way to reconstruct by cryptanalysis the secret key, knowing the clear and the corresponding encrypted message.
• Differential cryptanalysis is not suitable to the SED algorithm. On average, there is only one key corresponding to a clear and its associated encrypted text and therefore, every bit of the key act with the same weight in the algorithm.
• The SED algorithm is very fast for the following reasons :
• the algorithm uses only the OR-exclusive functions and branching.
• the length of the blocks (key and data) is small (128 bits against more than 512 bits) but long enough to disable every exhaustive cryptanalysis.
• on average, it is possible to compute at 1/3 of clock frequency.
• The SED algorithm permits chained mode cyphering, allowing reduction of the authentication information to one block of 128 bits, whatever the length of the data to authenticate.

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 pour le calcul de la vitesse de chiffrement