<B>Générateur électrique de signaux quasi-aléatoires pour appareils</B> cryptographiques La présente invention .a pour objet un générateur électrique de signaux quasi-aléatoires pour appareils cryptographiques formant des chiffres de clé, compre nant une pluralité -de compteurs binaires alimentés par un générateur d'impulsions électriques, de manière à engendrer à leurs sorties un certain nombre de chiffres binaires, et des ensembles décodeurs-permutateurs co- deurs formés d e circuits électriques de décodage, de per mutation et de codage desdits chiffres.
Des générateurs de ce type ont été décrits dans le brevet suisse No. 389 678. Dans les modes d'exécution décrits dans ledit brevet, les chiffres binaires engendrés par des compteurs binaires, dit compteurs d'avance, sont répartis en plusieurs groupes dont chacun est décodé, permuté, puis .de nouveau codé séparément avant d'être réunis aux autres, et chacun des ensembles décodeur- permutateur-codeur qui effectue ces opérations sur un groupe déterminé de sorties des compteurs comporte autant de sorties que d'entrées.
Les décodeurs sont constitués par exemple par des matrices à diodes. Le signal de sortie des décodeurs est transmis à un permutateur lui-même relié à des codeurs qui retransforment les signaux reçus du permutateur en un ensemble de signaux binaires. Plusieurs étages peu vent être prévus.
Le dispositif selon l'invention consiste en un généra teur électrique de signaux quasi-aléatoires, pour appa reils cryptographiques, formant des chiffres de clé, com prenant une pluralité de compteurs binaires alimentés par un générateur d'impulsions électriques, de manière à engendrer à leurs sorties un certain nombre de chiffres binaires, et des ensembles décodeurs-permutateurs co- deurs formés de circuits électriques de décodage, de per mutation et de codage desdits chiffres,
caractérisé par le fait que dans certains au moins desdits ensembles sur les fils de sortie des circuits permutateurs sont insérés des circuits logiques OU , de façon à rendre le nombre des sorties binaires de ces ensembles inférieur au nombre de leurs entrées binaires.
Cette disposition augmente la sécurité cryptographi- que, du fait qu'une configuration déterminée des sorties des divers ensembles décodeur-permutateur-codeur ainsi modifiées, peut provenir d'un nombre élevé de configurations distinctes de sorties correspondantes des compteurs d'avance.
Le dessin ci-annéxé représente, à titre d'exemple, une forme d'exécution de l'objet de l'invention et des varian tes de celles-ci: La fig. 1 représente un ensemble décodeur-permu- tateur-codeur , la fig. 2 donne le schéma de ladite forme d'éxécution dont les figures 3, 4 et 5 représentent des variantes d'exécution; la fig. 6 représente une réducteur.
A la fig. 1, on a représenté un décodeur 101 à quatre entrées binaires et à seize sorties (ces nombres ne sont nullement limitatifs). Les seize sorties du décodeur 101i sont connectées à un permutateur 102 à seize entrées et seize sorties. Ces dernières sont réparties en quatre groupes de quatre, dont chacun attaque un circuit logi que de somme ou circuit ou . Les quatres sorties des circuits ou 103, 104, 105 et 106 sont connectées à un codeur 107 à quatre entrées à ;deux sorties binaires.
Ces organes peuvent être réalisés suivant les indica tions du brevet précité.
La particularité du circuit que l'on va décrire en regard de la fig. 2 consiste dans la présence des circuits ou ; ceux-ci ont pour fonction de transmettre un signal à leur sortie chaque fois qu'il existe un signal sur l'une quelconque de leurs entrées. Par conséquent, plusieurs fils différents à l'entrée de l'ensemble,des sorties ou , donc plusieurs nombres binaires à l'entrée du décodeur 101, pourront aboutir au même nombre binaire à la sor tie du codeur 107.
Le générateur de symbols quasi-aléatoires ou géné rateur de clé de la fig. 2 comporte quatre compteurs binaires 1, 2, 3, 4, dont les comptes maximaux sont respectivement égaux à 7, 15, 29 et 31, dans l'exemple non limitatif décrit. Ces quatre compteurs sont alimentés par une pre mière section 5 d'une horloge 5 - 6 - 7 - 8.
Cette horloge, à laquelle sont appliqués les signaux d'un générateur de synchronisation 9, comporte en outre des sections 6, 7 et 8 dont le rôle apparaîtra :dans la suite. On a représenté, au-dessus des sorties correspon dantes, les impulsions engendrées par les diverses sec tions de ladite horloge.
Les trois sorties du compteur 1 sont respectivement connectées à trois décodeurs 10, 11, 12; les quatre sor ties du compteur 2 sont respectivement connectées aux quatre décodeurs 10, 11, 12 et 13. Quatre des sorties de chacun des compteurs 3 et 4 sont respectivement con nectées à ces quatre décodeurs tandis que la cinquième sortie du compteur 3 est en l'air, et que la cinquième sortie. du compteur 4 est connectée au décodeur 13.
Les décodeurs 10 à 13,à quatre entrées binaires et à seize sorties, attaquent des permutateurs 14 à 17, à seize entrées et à seize sorties. Ces dernières sorties sont divi sées en groupes de quatre .dont chacun attaque l'un des circuits logiques de somme (circuit ou ) 18 à 33.
On remarquera que, à l'exclusion des sections 6,7 et 8 de l'horloge, la partie du montage que l'on a décrite jusqu'ici est. du type décrit dans le brevet susvisé.
Les sorties des circuits ou 18, 22, 26 et 30 ne sont pas connectées, tandis que les sorties.,des autres circuits ou sont connectées à quatre compteurs auxiliaires respectifs 34 à 37 par l'intermédiaire de circuits logiques de produit (circuits et ) 38 à 49.
Les circuits et 38, 41, 44 et 47 sont reliées à la sortie de la section 6 de l'horloge, les circuits et 39, 42, 45 et 48 à la section 7, les circuits et 40, 43, 46 et 49 à la section 8.
Entre deux impulsions :d'avance principale produites par la section 5 de l'horloge, 1a section 6 produit une impulsion d'avance, la section 7 en produit deux et la section 8 en produit trois.
Les impulsions produites par les sections 6, 7 et 8 coïncident dans le temps, comme l'indique la fig. 2.
Il en résulte que l'apparition d'un signal sur les fils de sortie de circuits ou 18, 22, 26 et 30 ne produit aucune avance .des compteurs auxiliaires; que l'appari tion d'un signal sur les fils de sortie des circuits ou 19, 23, 27 et 31 fait respectivement avancer les compteurs auxiliaires d'un pas;
que l'apparition d'un signal sur les fils de sortie ou 20, 24, 28 et 32 fait avancer les compteurs auxiliaires de deux pas, et que l'apparition d'.un signal sur les fils de sortie des circuits ou 21, 25, 29 et 33 fait avancer les compteurs auxiliaires de trois pas.
On peut démontrer que, grâce à cette disposition, les 2$ = 256 combinaisons de sorties de l'étage des comp teurs auxiliaires 34 à 37 sont mathématiquement équi- probables, ce qui est important du point de vue de la sécurité cryptrographique.
On peut voir par ailleurs que chaque sortie finale du dispositif de la fig. 2 est déterminée à la fois par l'état des compteurs 1 à 4 et par la sortie précédente et que la période de l'appareil est en général égale à quatre fois celle des compteurs d'avance.
Les sorties des compteurs auxiliaires 34 à 37 peu vent directement constituer les sorties du générateur, ou encore, comme dans le cas de la figure, être reliées à un bloc 50 qui peut comporter .des ensembles décodeur- permutateur-codeur supplémentaires, éventuellement suivis d'un dispositif de réduction du nombre des sorties. On donnera plus loin un exemple de réalisation du bloc 50, illustré par 1a fig. 4.
Bien entendu, de nombreuses modifications du mon tage décrit peuvent être envisagées.
On pourrait, en particulier, réaliser les sections 5, 6, 7 et 8 de l'horloge représentée à la figure de manière telle que les premiers cycles de sections respectives ne coïncident pas dans le temps.
En plus de l'équiprobabilité des sorties, il est dési rable de réaliser l'équiprobabilité des avances, c'est-à- dire de s'arranger pour que, pour une sortie donnée de l'un des compteurs auxiliaires, une transition quelconque aboutisse indifféremment à l'un quelconque des chiffres 0,1,2,3ou4.
On peut obtenir ce résultat de diverses manières. L'une d'elles consiste à répartir inégalement, entre les différents circuits ou déjà mentionnés, les sorties des permutateurs. Elle est illustrée par la fig. 3, dans laquelle les mêmes éléments sont désignés par les mêmes numéros de référence qu'à la fig. 2.
On voit que les seize sorties de l'un quelconque des permutateurs, tel que 14., au lieu d'être également répar ties entre les quatre circuits ou correspondants, tels que 18 à 21, comme c'est le cas à la fig. 2, sont, à la fig. 3, réparties de la manière suivante:
Circuit ou 18 (non figuré) : zéro sortie circuit ou 19 : 7 sorties circuit ou 20 : 5 sorties circuit ou 21 : 4 sorties On peut montrer que cette répartition, ainsi que cer taines autres répartitions inégales, améliore l'équiproba- bilité des avances des compteurs 34 à 37.
La fig. 4 illustre à la fois une autre de ces réparti tions inégales (un - six - cinq - quatre) et une autre manière d'améliorer l'équiprobabilité des avances.
Bien entendu, on pourra utiliser d'autres répartitions des impulsions .d'avance auxiliaire, et les combiner à différentes répartitions des sorties des permutateurs.
A la fig. 5, on a représenté un dispositif susceptible de constituer 1a partie terminale (bloc 50) de l'un des ensembles des fig. 2 à 4.
Ce dispositif comprend .deux décodeurs 4/16, désig nés par legs numéros de référence 51 et 52, et connectés aux huit sorties .des compteurs 34 à 37 de la fig. 2.
Ces décodeurs sont suivis de deux permutateurs 53 et 54 à seize entrées et à seize sorties, ces dernières étant connectées, par groupe de quatre à des circuits ou 55 à 62.
Les sorties des circuits ou de rang un (à savoir: 55 et 59) ne sont pas connectées, tandis que les sorties des autres circuits ou sont connectées à deux comp teurs auxiliaires 63 et 64 de la manière suivante: sorties des circuits ou 56 et 60, par l'intermédiaire des cir cuits et respectifs 65 et 68, reliés à la section 71 d'une horloge à sept sections 5 - 6 - 7 - 8 - 71 - 72 - 73; sortie des circuits ou 57 et 61, par l'intermédiaire des cir cuits et respectifs 66 et 69, reliés à la section 72 de ladite horloge, et sorties des circuits ou 58 et 62, par l'intermédiaire des circuits et respectifs 67 et 70, reliés à la section 73 de l'horloge.
Les sections 5 à 8 de cette dernière sont celles qui ont été représentées à la fig. 2 et sont donc connectées de la même façon. Les sections supplémentaires 71 à 73 fournissent -des impulsions calées par exemple comme l'indique la fig. 5. Les compteurs auxiliaires 63 et 64 sont connectés à un décodeur 74, dont les sorties sont connectées à un permutateur 75, lui-même relié à un codeur 76.
On remarque que dans le montage de la fig. 5, les différentes entrées d'avance d'un même compteur auxi liaire sont reliées aux sorties d'un même permutateur, alors que, dans le dispositif<B>de</B> la fig. 1, elles provenaient de permutateurs différents. Cette combinaison a l'avan tage de rendre plus indépendantes les unes des autres les avances de ces compteurs auxiliaires.
Connectée à la suite du ,dispositif des fig. 2, 3 ou 4, elle assure l'équi- prob.abilité des couples de combinaisons de sortie de la clé.
Il est évident qu'un tel dispositif n'est pas limité à deux étages de compteurs auxiliaires connectés en série. Le réducteur de la fig. 6 comporte huit fils d'entrée principaux a à h issus d'un bloc de calcul principal 81, et neuf fils d'entrée auxiliaires issus d'un bloc de calcul auxiliaire 82. Ce dernier peut être constitué par un bloc analogue au bloc principal, ou simplement par un per- mutateur alimenté par le bloc principal.
Chaque fil d'en trée principal attaque trois circuits et , désignés par la même lettre que le fil d'entrée qui leur est associé, affec tée des indices 1, 2 -et 3 qui indiquent leur rang.
Les circuits et de rang 1, à savoir al b<B>.......</B> hl, sont encore attaqués par huit sorties d'un permuta- teur pl; de même, les circuits et a2 b2 <B>......</B> h2 sont attaqués par huit sorties d'un permutateur p2 et les cir cuits et as b, <B>.....</B> h3 sont attaqués par huit sorties d'un permutateur pg.
Dans l'exemple décrit, on a représenté des permuta- teurs à seize entrées et à seize sorties, et huit des sorties de chacun de ces permutateurs sont alors connectées à huit entrées (cette octuple connexion est symbolisée à la figure par un trait renforcé). L'emploi de permutateurs d'ordre seize est simplement destiné à permettre d'utili ser le même type de permutateurs dans l'ensemble de l'appareil cryptographique qui utilise le réducteur décrit, et n'a donc aucun caractère limitatif.
Les permutateurs p1 p2 p, sont connectés au bloc de calcul 82 par l'intermédiaire de décodeurs k1 k2 kg à trois entrées binaires et à huit sorties.
Les huit sorties des circuits et de rang un sont connectées à un circuit logique de somme (circuit ou ) de sorties s1 ; les huit sorties des circuits et de rang doux sont connectées à un circuit ou de sortie s2 et les huit sorties des circuits et de rang trois sont connec tées à un circuit ou de sortie s, .
La réalisation de chacun .des éléments du dispositif que l'on vient @de décrire est à la portée de l'homme de l'art, compte tenu en particulier des indications conte nues dans le brevet susvisé. Le fonctionnement de ce dispositif est le suivant: Une seule des sorties du déco deur Kl est excitée et ceci ouvre une seule des portes et d'indice 1. Le signal a à h appliqué à l'entrée de cette porte et ouverte se retrouve à la sortie s, De même, on retrouve en s1 et s2 l'un des signaux a à h.
Finalement, trois des signaux a à h sont appliquées aux sorties s1 s2 s, (éventuellement plusieurs fois le même) et ceci d'une façon qui dépend des nombres binaires fournis par le compteur 82.
<B> Electric generator of quasi-random signals for cryptographic devices </B> The present invention relates to an electrical generator of quasi-random signals for cryptographic devices forming key figures, comprising a plurality of powered binary counters by an electrical pulse generator, so as to generate at their outputs a certain number of binary digits, and decoder-permutation encoder assemblies formed of electrical circuits for decoding, per mutation and coding of said digits.
Generators of this type have been described in Swiss Patent No. 389,678. In the embodiments described in said patent, the binary digits generated by binary counters, called advance counters, are divided into several groups, each of which is decoded, permuted, then coded again separately before being combined with the others, and each of the decoder-permutator-encoder sets which performs these operations on a determined group of counter outputs has as many outputs as there are inputs.
The decoders consist for example of diode matrices. The output signal of the decoders is transmitted to a permutator itself connected to encoders which retransform the signals received from the permutator into a set of binary signals. Several floors can be planned.
The device according to the invention consists of an electric generator of quasi-random signals, for cryptographic devices, forming key digits, comprising a plurality of binary counters supplied by an electric pulse generator, so as to generate at their outputs a certain number of binary digits, and decoder-permutator encoder assemblies formed of electrical circuits for decoding, permutation and coding of said digits,
characterized by the fact that in at least some of the said assemblies on the output wires of the permutator circuits are inserted OR logic circuits, so as to make the number of binary outputs of these assemblies less than the number of their binary inputs.
This arrangement increases cryptographic security, owing to the fact that a determined configuration of the outputs of the various decoder-permutator-encoder assemblies thus modified, may come from a large number of distinct configurations of corresponding outputs of the advance counters.
The appended drawing represents, by way of example, an embodiment of the object of the invention and of the variations thereof: FIG. 1 represents a decoder-permutator-encoder assembly, FIG. 2 gives the diagram of said embodiment of which Figures 3, 4 and 5 represent variant embodiments; fig. 6 represents a reducing agent.
In fig. 1, there is shown a decoder 101 with four binary inputs and sixteen outputs (these numbers are in no way limiting). The sixteen outputs of decoder 101i are connected to a sixteen input and sixteen output permutator 102. These are divided into four groups of four, each of which drives a sum logic circuit or circuit or. The four outputs of the circuits or 103, 104, 105 and 106 are connected to an encoder 107 with four inputs with two binary outputs.
These components can be produced according to the indications of the aforementioned patent.
The particularity of the circuit which will be described with reference to FIG. 2 consists in the presence of circuits or; these have the function of transmitting a signal to their output whenever there is a signal on any of their inputs. Consequently, several different wires at the input of the set, of the outputs or, therefore, several binary numbers at the input of the decoder 101, may end up at the same binary number at the output of the encoder 107.
The quasi-random symbol generator or key generator of FIG. 2 comprises four binary counters 1, 2, 3, 4, the maximum counts of which are respectively equal to 7, 15, 29 and 31, in the non-limiting example described. These four counters are fed by a first section 5 of a clock 5 - 6 - 7 - 8.
This clock, to which the signals of a synchronization generator 9 are applied, further comprises sections 6, 7 and 8, the role of which will appear below. The pulses generated by the various sections of said clock have been shown above the corresponding outputs.
The three outputs of counter 1 are respectively connected to three decoders 10, 11, 12; the four outputs of counter 2 are respectively connected to the four decoders 10, 11, 12 and 13. Four of the outputs of each of the counters 3 and 4 are respectively connected to these four decoders while the fifth output of the counter 3 is in l 'air, and that the fifth exit. of counter 4 is connected to decoder 13.
Decoders 10 to 13, with four binary inputs and sixteen outputs, drive permutators 14 to 17, with sixteen inputs and sixteen outputs. These latter outputs are divided into groups of four, each of which drives one of the sum logic circuits (circuit or) 18 to 33.
Note that, excluding sections 6, 7 and 8 of the clock, the part of the assembly that has been described so far is. of the type described in the aforementioned patent.
The outputs of the circuits or 18, 22, 26 and 30 are not connected, while the outputs., Of the other circuits or are connected to four respective auxiliary meters 34 to 37 through logical product circuits (circuits and) 38 to 49.
The circuits and 38, 41, 44 and 47 are connected to the output of section 6 of the clock, the circuits and 39, 42, 45 and 48 to section 7, the circuits and 40, 43, 46 and 49 to section 8.
Between two main feed pulses produced by section 5 of the clock, section 6 produces one feed pulse, section 7 produces two and section 8 produces three.
The pulses produced by sections 6, 7 and 8 coincide in time, as shown in fig. 2.
As a result, the appearance of a signal on the output leads of circuits or 18, 22, 26 and 30 does not produce any advance of the auxiliary counters; that the appearance of a signal on the output wires of circuits or 19, 23, 27 and 31 respectively advance the auxiliary counters by one step;
that the appearance of a signal on the output wires or 20, 24, 28 and 32 advances the auxiliary counters by two steps, and that the appearance of a signal on the output wires of the circuits or 21, 25, 29, and 33 advance the auxiliary counters three steps.
It can be shown that, thanks to this arrangement, the 2 $ = 256 combinations of outputs of the stage of the auxiliary counters 34 to 37 are mathematically equal, which is important from the point of view of cryptographic security.
It can also be seen that each final output of the device of FIG. 2 is determined both by the state of counters 1 to 4 and by the previous output and that the period of the device is generally equal to four times that of the advance counters.
The outputs of the auxiliary counters 34 to 37 can directly constitute the outputs of the generator, or again, as in the case of the figure, be connected to a block 50 which can comprise additional decoder-permutator-encoder assemblies, possibly followed by 'a device for reducing the number of exits. An embodiment of the block 50, illustrated by FIG. 1, will be given below. 4.
Of course, many modifications of the assembly described can be envisaged.
In particular, sections 5, 6, 7 and 8 of the clock shown in the figure could be made in such a way that the first cycles of respective sections do not coincide in time.
In addition to the equiprobability of the outputs, it is desirable to achieve the equiprobability of the advances, that is to say to arrange that, for a given output of one of the auxiliary meters, any transition leads indifferently to any one of the digits 0,1,2,3 or 4.
This can be achieved in various ways. One of them consists in distributing unequally, between the various circuits or already mentioned, the outputs of the permutators. It is illustrated by fig. 3, in which the same elements are designated by the same reference numbers as in FIG. 2.
It can be seen that the sixteen outputs of any one of the permutators, such as 14., instead of being equally distributed between the four circuits or corresponding ones, such as 18 to 21, as is the case in FIG. 2, are, in FIG. 3, distributed as follows:
Circuit or 18 (not shown): zero circuit output or 19: 7 circuit outputs or 20: 5 circuit outputs or 21: 4 outputs It can be shown that this distribution, as well as certain other unequal distributions, improves the equiprobability of advances from meters 34 to 37.
Fig. 4 illustrates both another of these unequal distributions (one - six - five - four) and another way of improving the equiprobability of advances.
Of course, it is possible to use other distributions of the auxiliary advance pulses, and to combine them with different distributions of the outputs of the permutators.
In fig. 5, there is shown a device capable of constituting the end part (block 50) of one of the assemblies of FIGS. 2 to 4.
This device comprises .two decoders 4/16, designated by legacy reference numbers 51 and 52, and connected to the eight outputs of the counters 34 to 37 of FIG. 2.
These decoders are followed by two permutators 53 and 54 with sixteen inputs and sixteen outputs, the latter being connected, in groups of four to circuits or 55 to 62.
The outputs of the circuits or of rank one (namely: 55 and 59) are not connected, while the outputs of the other circuits or are connected to two auxiliary counters 63 and 64 as follows: outputs of the circuits or 56 and 60, through the respective circuits 65 and 68, connected to section 71 of a clock with seven sections 5 - 6 - 7 - 8 - 71 - 72 - 73; output of the circuits or 57 and 61, through the respective circuits 66 and 69, connected to section 72 of said clock, and outputs of the circuits or 58 and 62, through the respective circuits and 67 and 70 , connected to section 73 of the clock.
Sections 5 to 8 of the latter are those which have been shown in FIG. 2 and are therefore connected in the same way. The additional sections 71 to 73 provide stalled pulses, for example, as shown in FIG. 5. The auxiliary counters 63 and 64 are connected to a decoder 74, the outputs of which are connected to a permutator 75, itself connected to an encoder 76.
Note that in the assembly of FIG. 5, the various advance inputs of the same auxiliary counter are connected to the outputs of the same permutator, whereas, in the device <B> of </B> FIG. 1, they came from different permutators. This combination has the advantage of making the advances of these auxiliary meters more independent of each other.
Connected after the device of fig. 2, 3 or 4, it ensures the equilibrium of the pairs of key output combinations.
It is obvious that such a device is not limited to two stages of auxiliary meters connected in series. The reducer of fig. 6 comprises eight main input wires a to h coming from a main calculation block 81, and nine auxiliary input wires coming from an auxiliary calculation block 82. The latter can be constituted by a block similar to the main block , or simply by a switch powered by the main unit.
Each main input wire attacks three circuits and, designated by the same letter as the input wire which is associated with them, assigned indices 1, 2 -and 3 which indicate their rank.
The circuits and of rank 1, namely al b <B> ....... </B> hl, are still attacked by eight outputs of a permutator pl; similarly, circuits and a2 b2 <B> ...... </B> h2 are attacked by eight outputs of a permutator p2 and circuits and as b, <B> ..... </ B> h3 are attacked by eight outputs of a permutator pg.
In the example described, permutators with sixteen inputs and sixteen outputs have been represented, and eight of the outputs of each of these permutators are then connected to eight inputs (this eight-fold connection is symbolized in the figure by a reinforced line). . The use of sixteen-order permutators is simply intended to allow the same type of permutators to be used throughout the cryptographic apparatus which uses the reducer described, and therefore has no limiting character.
The permutators p1 p2 p are connected to the computation block 82 via decoders k1 k2 kg with three binary inputs and eight outputs.
The eight outputs of the circuits and of rank one are connected to a sum logic circuit (circuit or) of outputs s1; the eight outputs of the circuits and of row three are connected to a circuit or output s2 and the eight outputs of the circuits and of row three are connected to a circuit or output s,.
The production of each of the elements of the device which has just been described is within the reach of those skilled in the art, in particular given the indications contained in the aforementioned patent. The operation of this device is as follows: Only one of the decoder outputs K1 is excited and this opens only one of the doors and of index 1. The signal a to h applied to the input of this door and open is found at the output s, Similarly, we find in s1 and s2 one of the signals a to h.
Finally, three of the signals a to h are applied to the outputs s1 s2 s, (possibly several times the same) and this in a way which depends on the binary numbers supplied by the counter 82.