To see the other types of publications on this topic, follow the link: Code correcteur d'erreurs.
Dissertations / Theses on the topic 'Code correcteur d'erreurs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Code correcteur d'erreurs.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Bieliczky, Peter. "Implantation vlsi d'un algorithme de code correcteur d'erreurs et validation formelle de la realisation." Paris 6, 1993. http://www.theses.fr/1993PA066670.
Full textAbstract:
Datasafe est un circuit integre specialise dans le calcul d'une nouvelle famille de codes correcteurs d'erreurs: les codes belekamp-massey-dornstetter (bmd). Les performances des codes bmd en matiere de correction d'erreurs sont proches des codes de reed-solomon actuellement tres utilises dans l'industrie (deux symboles de redondance corrigent une erreur). Toutefois, les codes bmd ont l'avantage d'etre systematiques, tres performants en cas d'erreurs groupees, de prendre en compte de facon naturelle le traitement des effacements et de conduire a une realisation electronique plus simple. Le code retenu ici est de longueur 30 octets, la redondance est entierement parametrable de 5% a 95%. Le circuit datasafe a ete realise en standard-cell, sous alliance, la chaine de cao du laboratoire methodologie et architecture des systemes informatiques (masi) de l'universite pierre et marie curie. Datasafe comprend 4 000 portes et 35 000 transistors. Il code a la volee 30 mbit/s en technologie cmos 1. 2. Une carte prototype au standard isa et un logiciel de pilotage ont ete developpes pour utiliser datasafe a partir d'un ordinateur compatible pc. La conception de datasafe repose sur l'utilisation de methodes formelles inspirees des techniques de preuve de programmes: automates a etats finis, preuve par invariants. La correction des specifications est assuree par une analyse statique de l'automate sous-jacent, puis la conformite de la realisation avec ces specifications est demontree. Datasafe peut etre utilise comme macro cell d'un circuit plus important, en particulier dans le domaine des transmissions rapides
2
Kakakhail, Syed Shahkar. "Prédiction et estimation de très faibles taux d'erreurs pour les chaînes de communication codées." Cergy-Pontoise, 2010. http://www.theses.fr/2010CERG0437.
Full textAbstract:
Dans cette thèse, nous abordons le sujet d’optimisation des méthodes utilisées pour l’évaluation de performance des codes correcteurs d’erreurs. La durée d’une simulation Monte Carlo pour estimer le taux d’erreurs dans un système de communication augmente exponentiellement avec l’accroissement du Rapport Signal sur Bruit (RSB). Importance Sampling (IS) est une des techniques qui permettent à réduire le temps de ces simulations. Dans ce travail, on a étudié et mis en oeuvre une version avancée d’IS, appelé Adaptive Importance Sampling (AIS), pour l’évaluation efficace des codes correcteurs d’erreurs aux taux d’erreur très bas. D’abord, nous présentons les inspirations et motivations en analysant différentes approches actuellement mises en pratique. On s’intéresse plus particulièrement aux méthodes inspirées de la physique statistique. Ensuite, basé sur notre analyse qualitative, nous présentons une méthode optimisée, appelé laméthode de Fast Flat Histogram (FFH) qui est intrinsèquement très générique. La méthode emploie l’algorithme de Wang-Landau, l’algorithme de Metropolis-Hastings et les chaines de Markov. Elle fonctionne dans le cadre de l’AIS et nous donne un gain de simulation satisfaisant. Différents paramètres sont utilisés pour assurer une précision statistique suffisante. L’extension vers d’autres types de codes correcteurs d’erreurs est direct. Nous présentons les résultats pour les codes LDPC et turbocodes ayant différentes tailles et différents rendements. Par conséquent, nous montrons que la méthode FFH est générique et valable pour une large gamme des rendements, tailles et structures. De plus, nous montrons que la méthode FFH est un outil puissant pour trouver des pseudocodewords dans la région de RSB élévé en appliquant l’algorithme de décodage Belief Propagation aux codes LDPCThe time taken by standard Monte Carlo (MC) simulation to calculate the Frame Error Rate (FER) increases exponentially with the increase in Signal-to-Noise Ratio (SNR). Importance Sampling (IS) is one of the most successful techniques used to reduce the simulation time. In this thesis, we investigate an advanced version of IS, called Adaptive Importance Sampling (AIS) algorithm to efficiently evaluate the performance of Forward Error Correcting (FEC) codes at very low error rates. First we present the inspirations and motivations behind this work by analyzing different approaches currently in use, putting an emphasis on methods inspired by Statistical Physics. Then, based on this qualitative analysis, we present an optimized method namely Fast Flat Histogram (FFH) method, for the performance evaluation of FEC codes which is generic in nature. FFH method employs Wang Landau algorithm and is based on Markov Chain Monte Carlo (MCMC). It operates in an AIS framework and gives a good simulation gain. Sufficient statistical accuracy is ensured through different parameters. Extension to other types of error correcting codes is straight forward. We present the results for LDPC codes and turbo codes with different code lengths and rates showing that the FFH method is generic and is applicable for different families of FEC codes having any length, rate and structure. Moreover, we show that the FFH method is a powerful tool to tease out the pseudo-codewords at high SNR region using Belief Propagation as the decoding algorithm for the LDPC codes
3
Barbier, Johann. "Analyse de canaux de communication dans un contexte non coopératif : application aux codes correcteurs d'erreurs et à la stéganalyse." Phd thesis, Palaiseau, Ecole polytechnique, 2007. http://www.theses.fr/2007EPXX0039.
Full textAbstract:
Dans cette thèse, nous étudions les canaux de communication dans un contexte non coopératif sous l'angle des codes correcteurs d 'erreurs, d'une part, et de la stéganographie, d'autre part. Nous prenons la place d'un observateur non légitime qui veut avoir accès à l'information échangée entre deux protagonistes. Nos travaux sur les algorithmes de reconstruction de codes correcteurs nous ont amenés à proposer un formalisme commun pour l'étude des codes linéaires, des codes convolutifs et des turbo-codes. Nous analysons tout d'abord finement l'algorithme de Sicot-Houcke, puis l'employons ensuite comme brique de base pour concevoir une technique de reconstruction des codes convolutifs totalement automatique et de complexité meilleure que les techniques existantes. Enfin, nous utilisons ces résultats pour retrouver les paramètres des turbo-codeurs. Dans le cadre de l'analyse stéganographique, nous proposons tout d'abord deux nouveaux modèles de sécurité qui mettent en oeuvre des jeux avec des attaquants réels. Nous adaptons ensuite l'analyse RS en un schéma de détection pour l'algorithme Multi Bit Plane Image steganography pour le domaine spatial proposé par Nguyen et al. à IWDW'06. Enfin, nous développons une approche nouvelle pour analyser les images JPEG. En étudiant les statistiques des coefficients DCT compressés, nous mettons en évidence des détecteurs possédant des performances élevées et indépendantes en pratique de la quantité d'information dissimulée. Nous illustrons ces résultats par un schéma de stéganalyse universelle d'une part, et un schéma de stéganalyse spécifique pour Outguess, F5 et JPHide and JPSeek, d'autre part.
4
Barbier, Johann. "Analyse de canaux de communication dans un contexte non coopératif." Phd thesis, Ecole Polytechnique X, 2007. http://pastel.archives-ouvertes.fr/pastel-00003711.
Full textAbstract:
Dans cette thèse, nous étudions les canaux de communication dans un contexte non coopératif sous l'angle des codes correcteurs d'erreurs, d'une part, et de la stéganographie, d'autre part. Nous prenons la place d'un observateur non légitime qui veut avoir accès à l'information échangée entre deux protagonistes. Nos travaux sur les algorithmes de reconstruction de codes correcteurs, nous ont amenés à proposer un formalisme commun pour l'étude des codes linéaires, des codes convolutifs et des turbo-codes. Nous analysons tout d'abord finement l'algorithme de Sicot-Houcke, puis l'employons ensuite comme brique de base pour concevoir une technique de reconstruction des codes convolutifs totalement automatique et de complexité meilleure que les techniques existantes. Enfin, nous utilisons ces résultats pour retrouver les paramètres des turbo-codeurs. Dans le cadre de l'analyse stéganographique, nous proposons tout d'abord deux nouveaux modèles de sécurité qui mettent en oeuvre des jeux avec des attaquants réels. Nous adaptons ensuite l'analyse RS en un schéma de détection pour l'algorithme Multi Bit Plane Image steganography pour le domaine spatial, proposé par Nguyen et al. à IWDW'06. Enfin, nous développons une approche nouvelle pour analyser les images JPEG. En étudiant les statistiques des coefficients DCT compressés, nous mettons en évidence des détecteurs possédant des performances élevées et indépendantes en pratique de la quantité d'information dissimulée. Nous illustrons ces résultats par un schéma de stéganalyse universelle d'une part, et un schéma de stéganalyse spécifique pour Outguess, F5 et JPHide and JPSeek, d'autre part.
5
Legeay, Matthieu. "Utilisation du groupe de permutations d'un code correcteur pour améliorer l'efficacité du décodage." Rennes 1, 2012. http://www.theses.fr/2012REN1S099.
Full textAbstract:
Les codes correcteurs d'erreur et le problème lié de leur décodage constituent une des variantes envisagées en cryptographie post-quantique. De façon générale, un code aléatoire possède un groupe de permutations bien souvent trivial. Cependant, les codes impliqués dans la construction des cryptosystèmes et des fonctions cryptographiques basées sur les codes correcteurs possèdent généralement un groupe de permutations non-trivial. De plus, peu d'articles de cryptanalyse ne tiennent compte de l'information que représentent ces groupes de permutations. L'idée est donc d'utiliser le groupe de permutations des codes correcteurs afin d'améliorer les algorithmes de décodage. Il existe une multitude de façons de l'appliquer. La première à laquelle nous nous intéressons dans cette thèse est celle utilisant la permutation cyclique appelée “shift” sur du décodage par ensembles d'information. De cette façon, nous reprenons un travail initié par MacWilliams et y apportons une analyse précise de la complexité. Une autre façon est d'utiliser une permutation d'ordre deux afin de créer algébriquement un sous-code des codes de départ. Le décodage dans ce sous-codes, donc de paramètres plus petits, y est plus aisé et permet de récupérer de l'information pour effectuer le décodage dans le code de base. Pour terminer, nous étudions cette dernière technique sur les codes correcteurs bien connus que sont les codes de Reed-Muller permettant ainsi de prolonger les travaux lancés par Sidel'nikov-PershakovError correcting codes and the linked decoding problem are one of the variants considered in post-quantum cryptography. In general, a random code has oftenly a trivial permutation group. However, the codes involved in the construction of cryptosystems and cryptographic functions based on error correcting codes usually have a non-trivial permutation group. Moreover, few cryptanalysis articles use the information contained in these permutation groups. We aim at improving decoding algorithms by using the permutation group of error correcting codes. There are many ways to apply it. The first one we focus on in this thesis is the one that uses the cyclic permutation called “shift” on information set decoding. Thus, we dwell on a work initiated by MacWilliams and put forward a detailed analysis of the complexity. The other way we investigate is to use a permutation of order two to create algebraically a subcode of the first code. Decoding in this subcode, of smaller parameters, is easier and allows to recover information in a perspective of decoding in the first code. Finally, we study the last pattern on the well known correcting codes, i. E. Reed-Muller codes, which extends the work initiated by Sidel'nikov-Pershakov
6
Roux, Antoine. "Etude d’un code correcteur linéaire pour le canal à effacements de paquets et optimisation par comptage de forêts et calcul modulaire." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS337.
Full textAbstract:
La transmission fiable de données sur un canal de transmission est un problème récurrent en Informatique. En effet, quel que soit le canal de transmission employé, on observe obligatoirement de la détérioration de l’information transmise, voire sa perte pure et simple. Afin de palier à ce problème, plusieurs solutions ont été apportées, notamment via l’emploi de codes correcteurs. Dans cette thèse, nous étudions un code correcteur développé en 2014 et 2015 pour l’entreprise Thales durant ma deuxième année de Master en apprentissage. Il s’agit d’un code actuellement utilisé par Thales pour fiabiliser une transmission UDP passant par un dispositif réseau, l’Elips-SD. L’Elips-SD est une diode réseau qu’on place sur une fibre optique et qui garantit physiquement que la transmission est unidirectionnelle. Le cas d’utilisation principal de cette diode est de permettre le suivi de la production d’un site sensible, ou encore de superviser son fonctionnement, tout en garantissant à ce site une protection face aux intrusions extérieures. A l’opposé, un autre cas d’utilisation est la transmission de données depuis un ou plusieurs sites non-sécurisés vers un site sécurisé, dont on souhaite s’assurer qu’aucune information ne pourra par la suite fuiter. Le code correcteur que nous étudions est un code correcteur linéaire pour le canal à effacements de paquets, qui a reçu la certification OTAN de la Direction Générale des Armées. Nous l’avons babtisé "Fauxtraut", anagramme de "Fast algorithm using Xor to repair altered unidirectionnal transmissions". Afin d’étudier ce code correcteur, de présenter son fonctionnement et ses performances, et les différentes modifications apportées durant cette thèse, nous établissons tout d’abord un état de l’art des codes correcteurs, en nous concentrant principalement sur les codes linéaires non-MDS, tels que les codes LDPC. Puis nous présentons le fonctionnement de Fauxtraut, et analysons son comportement (complexité, consommation mémoire, performances) par la théorie et par des simulations. Enfin, nous présenterons différentes versions de ce code correcteur développées durant cette thèse, qui aboutissent à d’autres cas d’utilisation, tels que la transmission d’information sur un canal unidirectionnel à erreurs ou sur un canal bidirectionnel, à l’image de ce que permet de faire le protocole H-ARQ. Dans cette partie, nous étudierons notamment le comportement de notre code correcteur via la théorie des graphes : calculer la probabilité de décoder convenablement ou non revient à connaître la probabilité d’apparition de cycles dans le sous-graphe de graphes particuliers, les graphes de Rook et les graphes bipartis complets. Le problème s’énonce simplement et s’avère compliqué, et nous espérons qu’il saura intéresser des chercheurs du domaine. Nous présentons une méthode permettant de calculer exactement cette probabilité pour de petits graphes (qui aboutit à un certain nombre de formules closes), et une fonction tendant asymptotiquement vers cette probabilité pour de plus grands graphes. Nous étudierons aussi la manière de paramétrer automatiquement notre code correcteur par le calcul modulaire et la combinatoire, utilisant la fonction de Landau, qui retourne un ensemble de nombres entiers dont la somme est fixée et le plus commun multiple est maximal. Dans une dernière partie, nous présentons un travail effectué durant cette thèse ayant conduit à une publication dans la revue Theoretical Computer Science. Il concerne un problème non-polynomial de la théorie des graphes : le couplage maximal dans les graphes temporels. Cet article propose notamment deux algorithmes de complexité polynomiale : un algorithme de 2-approximation et un algorithme de kernelisation pour ce problème. L’algorithme de 2- approximation peut notamment être utilisé de manière incrémentale : arêtes du flot de liens nous parviennent les unes après les autres, et on construit la 2-approximation au fur et à mesure de leur arrivéeReliably transmitting information over a transmission channel is a recurrent problem in Informatic Sciences. Whatever may be the channel used to transmit information, we automatically observe erasure of this information, or pure loss. Different solutions can be used to solve this problem, using forward error correction codes is one of them. In this thesis, we study a corrector code developped in 2014 and 2015 for Thales society during my second year of master of apprenticeship. It is currently used to ensure the reliability of a transmission based on the UDP protocole, and passing by a network diode, Elips-SD. Elip-SD is an optical diode that can be plugged on an optical fiber to physically ensure that the transmission is unidirectional. The main usecase of such a diode is to enable supervising a critical site, while ensuring that no information can be transmitted to this site. At the opposite, another usecase is the transmission from one or multiple unsecured emitters to one secured receiver who wants to ensure that no information can be robbed. The corrector code that we present is a linear corrector code for the binary erasure channel using packets, that obtained the NATO certification from the DGA ("Direction Générale de Armées" in French). We named it Fauxtraut, for "Fast algorithm using Xor to repair altered unidirectional transmissions". In order to study this code, presenting how it works, its performance and the modifications we added during this thesis, we first establish a state of the art of forward error correction, focusing on non-MDS linear codes such as LDPC codes. Then we present Fauxtraut behavior, and analyse it theorically and with simulations. Finally, we present different versions of this code that were developped during this thesis, leading to other usecases such as transmitting reliable information that can be altered instead of being erased, or on a bidirectionnal channel, such as the H-ARQ protocole, and different results on the number of cycles in particular graphs. In the last part, we present results that we obtained during this thesis and that finally lead to an article in the Technical Computer Science. It concerns a non-polynomial problema of Graphs theorie : maximum matching in temporal graphs. In this article, we propose two algorithms with polynomial complexity : a 2-approximation algorithm and a kernelisation algorithm forthis problema
7
Charaf, Akl. "Etudes de récepteurs MIMO-LDPC itératifs." Phd thesis, Télécom ParisTech, 2012. http://pastel.archives-ouvertes.fr/pastel-00913457.
Full textAbstract:
L'objectif de cette thèse est l'étude de récepteurs MIMO LDPC itératifs. Les techniques MIMO permettent d'augmenter la capacité des réseaux sans fil sans la nécessité de ressources fréquentielles additives. Associées aux schémas de modulations multiporteuses CP-OFDM, les techniques MIMO sont ainsi devenues la pierre angulaire pour les systèmes sans fil à haute efficacité spectrale. La réception optimale peut être obtenue à l'aide d'une réception conjointe (Egalisation/Décodage). Étant très complexe, la réception conjointe n'est pas envisagée et l'égalisation et le décodage sont réalisés disjointement au coût d'une dégradation significative en performances. Entre ces deux solutions, la réception itérative trouve son intérêt pour sa capacité à s'approcher des performances optimales avec une complexité réduite. La conception de récepteurs itératifs pour certaines applications, de type WiFi à titre d'exemple doit respecter la structure du code imposée par la norme. Ces codes ne sont pas optimisés pour des récepteurs itératifs. En observant l'effet du nombre d' itérations dans le processus itératif, on montre par simulation que l'ordonnancement des itérations décodage LDPC/Turbo-égalisation joue un rôle important dans la complexité et le délai du récepteur. Nous proposons de définir des ordonnancements permettant de réduire la complexité globale du récepteur. Deux approches sont proposées, une approche statique ainsi qu'une autre dynamique. Ensuite nous considérons un système multi-utilisateur avec un accès multiple par répartition spatiale. Nous étudions l'intérêt de la réception itérative dans ce contexte tenant en compte la différence de puissance signale utile/interférence.
8
Goy, Guillaume. "Contribution à la sécurisation des implémentations cryptographiques basées sur les codes correcteurs d'erreurs face aux attaques par canaux auxiliaires." Electronic Thesis or Diss., Limoges, 2024. http://www.theses.fr/2024LIMO0036.
Full textAbstract:
Les attaques par canaux auxiliaires sont des attaques pouvant nuire à la sécurité de schémas cryptographiques parmi lesquels les schémas post-quantiques, résistantes aux attaques connues des ordinateurs quantique, dont la cryptographie basée sur les codes correcteurs d'erreurs fait partie. Afin de se protéger au mieux contre ces attaques, il est nécessaire d'identifier les vulnérabilités présentes dans les implémentations afin de les protéger. Dans cette thèse, nous présentons trois attaques contre le schéma Hamming Quasi-Cyclic (HQC), candidat au concours du NIST pour la standardisation de schémas post-quantiques, ainsi que des contre-mesures permettant de se protéger contre ces attaques. La structure concaténée du code publique de HQC, c’est-à-dire avec deux codes imbriqués, offre plusieurs vecteurs d’attaques. Dans un premier temps, nous présentons une attaque par chiffrés choisis, visant le code externe de HQC, dans le but de retrouver la clef secrète du schéma. L’analyse du comportement physique de transformée rapide d’Hadamard, utilisée dans le décodage des codes de Reed-Muller, nous permet de retrouver la clef secrète en moins de 20 000 mesures physiques du décodage. Ensuite, nous avons construit une attaque théorique contre le code interne afin de retrouver la clef partagée à l’issue du protocole. Cette attaque vise les codes de Reed-Solomon et plus particulièrement les fuites physiques pendant l’exécution de la multiplication dans un corps de Galois. L’analyse de ces fuites, combiné avec une attaque de type CPA (Correlation Power Analysis) nous a permis de montrer que la sécurité de clef partagée de HQC pouvait être réduite de 2^128 à 2^96 opérations avec l’analyse d’une unique mesure physique. Enfin, nous avons utilisé des outils issus de la théorie de la propagation de croyance afin d’améliorer la précédente attaque et de pouvoir la réaliser en pratique. Cette nouvelle approche permet de retrouver en pratique la clef partagée de HQC, en quelques minutes et pour tous les niveaux de sécurité. Ces travaux nous ont aussi permis de montrer que des contre-mesures connues de l’état de l’art ne sont pas efficaces. Pour contrer ces attaques, nous proposons des contre-mesures au niveau de l’implémentation des opérations sensibles basées soit sur du masquage, soit sur un mélange des données manipuléesSide-channel attacks are a threat for cryptographic security, including post-quantum cryptography (PQC) such as code-based cryptography. In order to twarth these attacks, it is necessary to identify vulnerabilities in implementations. In this thesis, we present three attacks against Hamming Quasi-Cyclic (HQC) scheme, a candidate in the NIST PQC standardization contest for the standardization of post-quantum schemes, along with countermeasures to protect against these attacks. The concatenated code structure of the publickly known HQC’s gives several targets for side-channel attacks. Firstly, we introduce a chosen ciphertext attack targeting HQC outer code, aiming at recovering the secret key. The physical behavior of the fast Hadamard transform (FHT), used during the Reed-Muller decoding step, allows to retrieve the secret key with less than 20,000 physical measurements of the decoding process. Next, we developed a theoretical attack against the inner code to recover the shared key at the end of the protocol. This attack targets the Reed-Solomon code and more specifically the physical leaks during the execution of a Galois field multiplication. These leaks, combined with a Correlation Power Analysis (CPA) strategy, allows us to show that the security of HQC shared key could be reduced from 2^128 to 2^96 operations with the knowledge of a single physical measurement. Finally, we used Belief Propagation tools to improve our attack and make it practically executable. This new approach allows us to practically recover HQC shared key within minutes for all security levels. These efforts also demonstrated that known state-of-the-art countermeasures are not effective against our attack. In order to twarth these attacks, we present maksing and shuffling countermeasures for the implementation of sensitive operations which manipulate secret data
9
Chaulet, Julia. "Etude de cryptosystèmes à clé publique basés sur les codes MDPC quasi-cycliques." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066064/document.
Full textAbstract:
L’utilisation des codes MDPC (Moderate Density Parity Check) quasi-cycliques dans le cryptosystème de McEliece offre un schéma de chiffrement post-quantique dont les clés ont une taille raisonnable et dont le chiffrement et le déchiffrement n’utilisent que des opérations binaires. C’est donc un bon candidat pour l’implémentation embarquée ou à bas coût.Dans ce contexte, certaines informations peuvent être exploitées pour construire des attaques par canaux cachés.Ici, le déchiffrement consiste principalement à décoder un mot de code bruité. Le décodeur utilisé est itératif et probabiliste : le nombre d’itérations de l'algorithme varie en fonction des instances et certains décodages peuvent échouer. Ces comportements ne sont pas souhaitables car ils peuvent permettre d’extraire des informations sur le secret.Une contremesure possible est de limiter le nombre d’instances de chiffrement avec les mêmes clés. Une autre façon serait de recourir à un décodage à temps constant dont la probabilité d’échec au décodage est négligeable. L’enjeu principal de cette thèse est de fournir de nouveaux outils pour analyser du comportement du décodeur pour la cryptographie.Dans un second temps, nous expliquons pourquoi l'utilisation des codes polaires n'est pas sûre pour le cryptosystème de McEliece. Pour ce faire, nous utilisons de nouvelles techniques afin de résoudre une équivalence de codes. Nous exhibons de nombreux liens entre les codes polaires et les codes de Reed-Muller et ainsi d'introduire une nouvelle famille de codes : les codes monomiaux décroissants. Ces résultats sont donc aussi d'un intérêt indépendant pour la théorie des codesConsidering the McEliece cryptosystem using quasi-cylcic MDPC (Moderate Density Parity Check matrix) codes allows us to build a post-quantum encryption scheme with nice features. Namely, it has reasonable key sizes and both encryption and decryption are performed using binary operations. Thus, this scheme seems to be a good candidate for embedded and lightweight implementations. In this case, any information obtained through side channels can lead to an attack. In the McEliece cryptosystem, the decryption process essentially consists in decoding. As we consider the use of an iterative and probabilistic algorithm, the number of iterations needed to decode depends on the instance considered and some of it may fail to be decoded. These behaviors are not suitable because they may be used to extract information about the secrets. One countermeasure could be to bound the number of encryptions using the same key. Another solution could be to employ a constant time decoder with a negligible decoding failure probability, that is to say which is about the expected security level of the cryptosystem. The main goal of this thesis is to present new methods to analyse decoder behavior in a cryptographic context.Second, we explain why a McEliece encryption scheme based on polar code does not ensure the expected level of security. To do so, we apply new techniques to resolve the code equivalence problem. This allows us to highlight several common properties shared by Reed-Muller codes and polar codes. We introduce a new family of codes, named decreasing monomial codes, containing both Reed-Muller and polar codes. These results are also of independent interest for coding theory
10
Dila, Gopal Krishna. "Motifs de codes circulaires dans les gènes codant les protéines et les ARN ribosomaux." Electronic Thesis or Diss., Strasbourg, 2020. http://www.theses.fr/2020STRAD027.
Full textAbstract:
La thèse porte sur les motifs du code circulaire X, un code correcteur d'erreurs trouvé dans les gènes, qui ont la capacité de trouver le cadre de lecture. Nous avons étudié la conservation des motifs X dans les gènes de différentes espèces et identifié des pressions sélectives spécifiques pour les maintenir. Nous avons aussi identifié des motifs X universels dans l'ARN ribosomique, situés dans des régions fonctionnelles importantes du ribosome et suggérant que les codes circulaires ont représenté une étape importante dans l'émergence du code génétique standard (SGC). Ensuite, nous avons étudié le rôle fonctionnel des motifs X dans la traduction moderne et identifié une forte corrélation entre l'enrichissement des motifs X et le niveau de traduction des gènes. Enfin, nous avons comparé l'optimalité du code X avec le SGC et d'autres codes circulaires maximaux, et identifié une nouvelle fonctionnalité de X dans la minimisation des effets des erreurs après un décalage du cadreThe thesis focuses on motifs of the circular code X, an error-correcting code found in protein-coding genes, which have the ability to synchronize the reading frame. We first investigated the evolutionary conservation of X motifs in genes of different species and identified specific selective pressures to maintain them. We also identified a set of universal X motifs in ribosomal RNAs, which are located in important functional regions of the ribosome and suggest that circular codes represented an important step in the emergence of the standard genetic code (SGC). Then, we investigated the functional role of X motifs in modern translation processes and identified a strong correlation between X motif enrichment in genes and translation levels. Finally, we compared the frameshift optimality of the circular code X with the SGC and other maximal circular codes, and identified a new functionality of the code X in minimizing the effects of translation errors after frameshift events
11
Chaulet, Julia. "Etude de cryptosystèmes à clé publique basés sur les codes MDPC quasi-cycliques." Electronic Thesis or Diss., Paris 6, 2017. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2017PA066064.pdf.
Full textAbstract:
L’utilisation des codes MDPC (Moderate Density Parity Check) quasi-cycliques dans le cryptosystème de McEliece offre un schéma de chiffrement post-quantique dont les clés ont une taille raisonnable et dont le chiffrement et le déchiffrement n’utilisent que des opérations binaires. C’est donc un bon candidat pour l’implémentation embarquée ou à bas coût.Dans ce contexte, certaines informations peuvent être exploitées pour construire des attaques par canaux cachés.Ici, le déchiffrement consiste principalement à décoder un mot de code bruité. Le décodeur utilisé est itératif et probabiliste : le nombre d’itérations de l'algorithme varie en fonction des instances et certains décodages peuvent échouer. Ces comportements ne sont pas souhaitables car ils peuvent permettre d’extraire des informations sur le secret.Une contremesure possible est de limiter le nombre d’instances de chiffrement avec les mêmes clés. Une autre façon serait de recourir à un décodage à temps constant dont la probabilité d’échec au décodage est négligeable. L’enjeu principal de cette thèse est de fournir de nouveaux outils pour analyser du comportement du décodeur pour la cryptographie.Dans un second temps, nous expliquons pourquoi l'utilisation des codes polaires n'est pas sûre pour le cryptosystème de McEliece. Pour ce faire, nous utilisons de nouvelles techniques afin de résoudre une équivalence de codes. Nous exhibons de nombreux liens entre les codes polaires et les codes de Reed-Muller et ainsi d'introduire une nouvelle famille de codes : les codes monomiaux décroissants. Ces résultats sont donc aussi d'un intérêt indépendant pour la théorie des codesConsidering the McEliece cryptosystem using quasi-cylcic MDPC (Moderate Density Parity Check matrix) codes allows us to build a post-quantum encryption scheme with nice features. Namely, it has reasonable key sizes and both encryption and decryption are performed using binary operations. Thus, this scheme seems to be a good candidate for embedded and lightweight implementations. In this case, any information obtained through side channels can lead to an attack. In the McEliece cryptosystem, the decryption process essentially consists in decoding. As we consider the use of an iterative and probabilistic algorithm, the number of iterations needed to decode depends on the instance considered and some of it may fail to be decoded. These behaviors are not suitable because they may be used to extract information about the secrets. One countermeasure could be to bound the number of encryptions using the same key. Another solution could be to employ a constant time decoder with a negligible decoding failure probability, that is to say which is about the expected security level of the cryptosystem. The main goal of this thesis is to present new methods to analyse decoder behavior in a cryptographic context.Second, we explain why a McEliece encryption scheme based on polar code does not ensure the expected level of security. To do so, we apply new techniques to resolve the code equivalence problem. This allows us to highlight several common properties shared by Reed-Muller codes and polar codes. We introduce a new family of codes, named decreasing monomial codes, containing both Reed-Muller and polar codes. These results are also of independent interest for coding theory
12
Candau, Marion. "Codes correcteurs d'erreurs convolutifs non commutatifs." Thesis, Brest, 2014. http://www.theses.fr/2014BRES0050/document.
Full textAbstract:
Un code correcteur d'erreur ajoute de la redondance à un message afin de pouvoir corriger celui-ci lorsque des erreurs se sont introduites pendant la transmission. Les codes convolutifs sont des codes performants, et par conséquent, souvent utilisés. Le principe d'un code convolutif consiste à se fixer une fonction de transfert définie sur le groupe des entiers relatifs et à effectuer la convolution d'un message avec cette fonction de transfert. Ces codes ne protègent pas le message d'une interception par une tierce personne. C'est pourquoi nous proposons dans cette thèse, des codes convolutifs avec des propriétés cryptographiques, définis sur des groupes non-commutatifs. Nous avons tout d'abord étudié les codes définis sur le groupe diédral infini, qui, malgré de bonnes performances, n'ont pas les propriétés cryptographiques recherchées. Nous avons donc étudié ensuite des codes convolutifs en bloc sur des groupes finis, avec un encodage variable dans le temps. Nous avons encodé chaque message sur un sous-ensemble du groupe différent à chaque encodage. Ces sous-ensembles sont générés de façon chaotique à partir d'un état initial, qui est la clé du cryptosystème symétrique induit par le code. Nous avons étudié plusieurs groupes et plusieurs méthodes pour définir ces sous-ensembles chaotiques. Nous avons étudié la distance minimale des codes que nous avons conçus et montré qu'elle est légèrement plus petite que la distance minimale des codes en blocs linéaires. Cependant, nous avons, en plus, un cryptosystème symétrique associé à ces codes. Ces codes convolutifs non-commutatifs sont donc un compromis entre correction d'erreur et sécuritéAn error correcting code adds redundancy to a message in order to correct it when errors occur during transmission.Convolutional codes are powerful ones, and therefore, often used. The principle of a convolutional code is to perform a convolution product between a message and a transfer function, both defined over the group of integers. These codes do not protect the message if it is intercepted by a third party. That is why we propose in this thesis, convolutional codes with cryptographic properties defined over non-commutative groups. We first studied codes over the infinite dihedral group, which despite good performance, do not have the desired cryptographic properties. Consequently, we studied convolutional block codes over finite groups with a time-varying encoding. Every time a message needs to be encoded, the process uses a different subset of the group. These subsets are chaotically generated from an initial state. This initial state is considered as the symmetric key of the code-induced cryptosystem. We studied many groups and many methods to define these chaotic subsets. We examined the minimum distance of the codes we conceived and we showed that it is slightly smaller than the minimum distance of the linear block codes. Nevertheless, our codes have, in addition, cryptographic properties that the others do not have. These non-commutative convolutional codes are then a compromise between error correction and security
13
Côte, Maxime. "Reconnaissance de codes correcteurs d'erreurs." Phd thesis, Ecole Polytechnique X, 2010. http://pastel.archives-ouvertes.fr/pastel-00006125.
Full textAbstract:
Durant cette thèse, je me suis intéressés à la reconnaissance de codes correcteurs d'erreurs à partir d'une observation bruitée. Parmi ces codes, nous avons choisi d'étudier plus particulièrement les codes convolutifs et les turbo-codes. Le canal de transmission considéré pour nos travaux est le canal binaire symétrique. En s'appuyant sur les travaux de E. Filiol et J. Barbier, j'ai mis au point un algorithme, imaginé conjointement avec N. Sendrier. Nous avons créé une nouvelle méthode générique de reconnaissance des codes convolutifs (n; k) (k entrées et n sorties). Cette méthode améliore l'état de l'art grâce à l'utilisation exclusive d'opérations binaires d'algèbre linéaire dans l'algorithme. L'implémentation fournit de bons résultats, autant du point de vue du temps d'exécution que de la tolérance au bruit, pour tout type de code convolutifs. La seconde partie consiste en la mise au point d'une méthode de reconnaissance des turbo-codes. Cette méthode repose sur les hypothèses que nous sommes capable de retrouver le premier code convolutif à l'aide de notre méthode de reconnaissance de code convolutif et que le second code convolutif (suivant l'entrelaceur) possède une matrice génératrice systématique définie par P(D)/Q(D) (où P(D) et Q(D) sont les polynômes du codeur convolutif) de terme constant non nul. Cette dernière hypothèse forte mais réaliste nous permet de construire une méthode et un algorithme capable de retrouver à la fois l'entrelaceur et les polynômes P(D) et Q(D) du code convolutif. Cet algorithme est très rapide mais trouve ses limites lorsque le taux d'erreur croit. De plus, notre hypothèse rend impossible la reconstruction de turbo-codes poinçonnés sans modifier l'algorithme.
14
Adjudeanu, Irina. "Codes correcteurs d'erreurs LDPC structurés." Thesis, Université Laval, 2010. http://www.theses.ulaval.ca/2010/27423/27423.pdf.
Full text
15
Yaoumi, Mohamed. "Energy modeling and optimization of protograph-based LDPC codes." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2020. http://www.theses.fr/2020IMTA0224.
Full textAbstract:
Il existe différents types de codes correcteur d’erreurs (CCE), chacun offrant différents compromis entre la performance et la consommation d’énergie. Nous proposons de traiter ce problème pour les codes LDPC (Low-Density Parity Check). Dans ce travail, nous avons considéré les codes LDPC construits à partir de protographes avec un décodeur Min-Sum quantifié, pour leurs bonnes performances et leur implémentation matérielle efficace. Nous avons utilisé une méthode basée sur l’évolution de densité pour évaluer les performances à longueur finie du décodeur pour un protographe donné. Ensuite, nous avons introduit deux modèles pour estimer la consommation d’énergie du décodeur Min-Sum quantifié. A partir de ces modèles, nous avons développé une méthode d’optimisation afin de sélectionner des protographes qui minimisent la consommation d’énergie du décodeur tout en satisfaisant un critère de performance donné.Dans la seconde partie de la thèse, nous avons considéré un décodeur LDPC bruité, et nous avons supposé que le circuit introduit des défauts dans les unités de mémoire utilisées par le décodeur. Nous avons ensuite mis à jour le modèle d’énergie de la mémoire afin de prendre en compte le bruit dans le décodeur. Par conséquent, nous avons proposé une méthode alternative afin d’optimiser les paramètres du modèle et minimiser la consommation d’énergie du décodeur pour un protographe donnéThere are different types of error correction codes (CCE), each of which gives different trade-offs interms of decoding performanceand energy consumption. We propose to deal with this problem for Low-Density Parity Check (LDPC) codes. In this work, we considered LDPC codes constructed from protographs together with a quantized Min-Sum decoder, for their good performance and efficient hardware implementation. We used a method based on Density Evolution to evaluate the finite-length performance of the decoder for a given protograph.Then, we introduced two models to estimate the energy consumption of the quantized Min-Sum decoder. From these models, we developed an optimization method in order to select protographs that minimize the decoder energy consumption while satisfying a given performance criterion. The proposed optimization method was based on a genetic algorithm called differential evolution. In the second part of the thesis, we considered a faulty LDPC decoder, and we assumed that the circuit introduces some faults in the memory units used by the decoder. We then updated the memory energy model so as to take into account the noise in the decoder. Therefore, we proposed an alternate method in order to optimize the model parameters so as to minimize the decoder energy consumption for a given protograph
16
Delpeyroux, Emmanuelle. "Contribution à l'étude des codes correcteurs d'erreurs." Toulouse 3, 1996. http://www.theses.fr/1996TOU30148.
Full textAbstract:
Le cadre general concerne les corps finis, l'algebre commutative, et les applications aux codes correcteurs d'erreurs. Trois themes principaux sont developpes: les codes concatenes, les bases de grobner, et les bases normales orthonormees. Le choix d'un code correcteur est difficile et necessite des connaissances theoriques. Certaines applications actuelles, comme la transmission de la parole ou des images, demandent des codes puissants. Parmi ceux-ci se trouvent les codes concatenes. L'etude du modele algebrique de ces codes permet de considerer la concatenation de codes cycliques comme la definition d'un ideal dans une algebre abelienne. Une generalisation, aux codes abeliens modulaires, des travaux de j. M. Jensen est proposee. Concernant les bases de grobner, elles ont ete developpees par b. Buchberger. Elles trouvent une application dans le codage et le decodage des codes cycliques, et sont utilisees pour le codage systematique. Il est demontre que la matrice generatrice sous forme systematique d'un code abelien est l'unique matrice echelons reduite de ce code. Ce resultat et les proprietes de cette matrice permettent de calculer directement la base de grobner reduite et normalisee du code. Dans le cas ou le code est un code concatene abelien et semi-simple cette matrice peut etre obtenue en concatenant les matrices generatrices sous forme systematique du code interne et du code externe. Enfin, pour developper des circuits electroniques plus economiques lorsque des codes correcteurs sont utilises, de nombreux chercheurs ont etudie et construit des bases particulieres des corps finis comme les bases normales et les bases normales trace-orthonormees. Une synthese des differents resultats existants dans ce domaine, ainsi que des ameliorations de ces resultats et des demonstrations alternatives, sont proposees. Le cas plus general d'une extension abelienne, de degre fini, sur un corps commutatif est rappele
17
Lacan, Jérôme. "Contribution à l'étude des codes correcteurs d'erreurs." Toulouse 3, 1997. http://www.theses.fr/1997TOU30274.
Full textAbstract:
Dans cette these consacree aux codes correcteurs d'erreurs, le premier theme aborde concerne les codes modulaires cycliques et abeliens (ou codes a racines multiples). Il est demontre que tous les codes modulaires cycliques ainsi que certains codes modulaires abeliens sont equivalents a des sommes directes de codes produits. Cette approche permet de donner des resultats nouveaux sur la distance minimale et sur le nombre de mots de plus faible poids de certains de ces codes. Le deuxieme theme aborde concerne les codes demultiplies. Un groupe de permutations qui laisse invariants certains de ces codes est defini. Ces permutations permettent d'etablir l'equivalence entre certains de ces codes et des codes cycliques et abeliens. Elles permettent en outre d'ameliorer les performances de ces codes pour un decodage a decision ponderee. Ceci est illustre par des resultats de simulations. Enfin, bases sur le modele des codes produits, des codes abeliens dont les lignes, les colonnes et les diagonales sont des mots de codes cycliques sont caracterises. Des simulations comparatives entre les performances des decodages des codes produits et de ces codes sont presentees. Dans certains cas, celles de ces nouveaux codes sont meilleures.
18
Charaf, Akl. "Etudes de récepteurs MIMO-LDPC itératifs." Electronic Thesis or Diss., Paris, ENST, 2012. http://www.theses.fr/2012ENST0017.
Full textAbstract:
L’objectif de cette thèse est l’étude de récepteurs MIMO LDPC itératifs. Les techniques MIMO permettent d’augmenter la capacité des réseaux sans fil sans la nécessité de ressources fréquentielles additives. Associées aux schémas de modulations multiporteuses CP-OFDM, les techniques MIMO sont ainsi devenues la pierre angulaire pour les systèmes sans fil à haute efficacité spectrale. La réception optimale peut être obtenue à l’aide d’une réception conjointe (Egalisation/Décodage). Étant très complexe, la réception conjointe n’est pas envisagée et l’égalisation et le décodage sont réalisés disjointement au coût d’une dégradation significative en performances. Entre ces deux solutions, la réception itérative trouve son intérêt pour sa capacité à s’approcher des performances optimales avec une complexité réduite. La conception de récepteurs itératifs pour certaines applications, de type WiFi à titre d’exemple doit respecter la structure du code imposée par la norme. Ces codes ne sont pas optimisés pour des récepteurs itératifs. En observant l’effet du nombre d' itérations dans le processus itératif, on montre par simulation que l’ordonnancement des itérations décodage LDPC/Turbo-égalisation joue un rôle important dans la complexité et le délai du récepteur. Nous proposons de définir des ordonnancements permettant de réduire la complexité globale du récepteur. Deux approches sont proposées, une approche statique ainsi qu'une autre dynamique. Ensuite nous considérons un système multi-utilisateur avec un accès multiple par répartition spatiale. Nous étudions l’intérêt de la réception itérative dans ce contexte tenant en compte la différence de puissance signale utile/interférenceThe aim of this thesis is to address the design of iterative MIMO receivers using LDPC Error Correcting codes. MIMO techniques enable capacity increase in wireless networks with no additional frequency ressources. The associationof MIMO with multicarrier modulation techniques OFDM made them the cornerstone of emerging high rate wireless networks. Optimal reception can be achieved using joint detection and decoding at the expense of a huge complexity making it impractical. Disjoint reception is then the most used. The design of iterative receivers for some applications using LDPC codes like Wifi (IEEE 802.11n) is constrained by the standard code structure which is not optimized for such kind of receivers. By observing the effect of the number of iterations on performance and complexity we underline the interest of scheduling LDPC decoding iterations and turboequalization iterations. We propose to define schedules for the iterative receiver in order to reduce its complexity while preserving its performance. Two approaches are used : static and dynamic scheduling. The second part of this work is concerns Multiuser MIMO using Spatial Division Multiple Access. We explore and evaluate the interest of using iterative reception to cancel residual inter-user interference
19
Sendrier, Nicolas. "Codes correcteurs d'erreurs à haut pouvoir de correction." Paris 6, 1991. http://www.theses.fr/1991PA066630.
Full textAbstract:
Pour obtenir des codes a haut pouvoir de correction il est souhaitable de choisir des codes de grande longueur. Nous etudions la distance minimale de certains codes bch en longueur 255 et 511, ainsi que les proprietes de deux constructions: les codes produit et les codes concatenes. Ces techniques ont l'avantage de donner des codes de grande longueur dont le decodage a une faible complexite algorithmique. Les performances de ces codes sont etudiees a l'aide d'outils combinatoires nouveaux, les polynomes des motifs corrigibles, et se sont averees excellentes dans certains des exemples presentes
20
Urvoy, De Portzamparc Frédéric. "Sécurités algébrique et physique en cryptographie fondée sur les codes correcteurs d'erreurs." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066106/document.
Full textAbstract:
La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'artCode-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art
21
Urvoy, De Portzamparc Frédéric. "Sécurités algébrique et physique en cryptographie fondée sur les codes correcteurs d'erreurs." Electronic Thesis or Diss., Paris 6, 2015. http://www.theses.fr/2015PA066106.
Full textAbstract:
La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'artCode-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art
22
Edoukou, Frédéric Aka-Bilé. "Codes correcteurs d'erreurs construits à partir des variétés algébriques." Aix-Marseille 2, 2007. http://theses.univ-amu.fr.lama.univ-amu.fr/2007AIX22011.pdf.
Full textAbstract:
On étudie le code fonctionnel défini sur une variété algébrique X sur un corps fini, tout comme V. Goppa l'avait fait sur les courbes. La distance minimale de ce code est déterminée par le nombre de points rationnels de l'intersection de X avec toutes les hypersurfaces d'un certain degré. Dans le cas où X est une surface hermitienne non-dégénérée, A. B. S Orensen a formulé dans sa thèse (1991) une conjecture, qui résolue, donne exactement la distance minimale de ce code. Dans cette thèse nous allons répondre à cette conjecture dans le cas des surfaces quadriques. En utilisant des résultats de géométrie finie nous donnerons aussi la distribution des poids du code associé. Nous étudierons aussi des codes fonctionnels d'ordre 2 définis sur des surfaces quadriques et montrerons que pour ceux construits sur les surfaces quadriques elliptiques les paramètres en font d'eux de bons codes. Nous donnerons aussi les meilleures bornes possibles pour le nombre de points d'une section quadratique d'une variété quadrique, d'une variété hermitienne non-dégénérée en dimension 4 et proposerons une généralisation de la conjecture étudiée pour des variétés de dimension supérieureWe study the functional code defined on a projective algebraic variety X on a finite field, as this has been done by V. Goppa on algebraic curves. The minimum distance of this code is determined by computing the number of rational points of the intersection of X with all the hypersurfaces of a given degree. In the case where X is a non-degenerate hermitian surface, A. B. Sorensen has formulated a conjecture in his Ph. D thesis (1991), which should give the exact value of the minimum distance of this code. In this thesis, we give a proof of Sorensen's conjecture for quadratic surfaces. By using some results of finite geometries we give the weight distribution associated to this code. We will study also the functional code of order 2 defined on quadratic surfaces and will show that for the ones built on elliptic quadratic surfaces according to their parameters, their are good codes. We will give the best upper bounds for the number of points of quadratic section of quadric varieties, and non-degenerate hermitian variety, in projective dimension 4. Finally we will propose a generalisation of the studied conjecture for higher dimensional varieties
23
Dubreuil, Laurent. "Amélioration de l'étalement de spectre par l'utilisation de codes correcteurs d'erreurs." Limoges, 2005. https://aurore.unilim.fr/theses/nxfile/default/3964483f-5b1f-41dd-b862-6c3d029c0d41/blobholder:0/2005LIMO0041.pdf.
Full textAbstract:
Dans cette thèse, nous étudions un système de communication nommé étalement de spectre. Le principe de ce système consiste à répartir l'énergie du signal à émettre sur une bande de fréquence plus large que celle réellement nécessaire à la transmission du signal utile. Le fonctionnement de l'étalement de spectre est basé sur l'utilisation de "séquences d'étalement" ayant de bonnes propriétés de corrélation. Dans cette thèse, nous introduisons des codes correcteurs d'erreurs pour améliorer l'efficacité de l'étalement du signal. L'objectif de cette thèse est de déterminer l'efficacité de cette méthode et les critères de choix des codes correcteurs d'erreurs. Le nombre maximum d'utilisateurs dépend du choix du code correcteur d'erreur utilisé mais aussi de la séquence d'étalement utilisée. Une synthèse de l'étalement de spectre et du CDMA (Code Division Multiple Access) est présentée dans une première partie. Des limites théoriques sont données et des limites physiques sont posées. Puis deux systèmes à étalement de spectre utilisant des séquences d'étalement différentes sont présentés et comparés. Le système le plus performant, aussi bien théorique que pratique, est l'étalement de spectre "à déphasage multiple". La dernière partie présente divers codes correcteurs d'erreur et détermine celui qui maximise le nombre d'utilisateurs. Toutefois, pour un taux d'erreur binaire résiduel inférieur à 10-3 et un facteur d'étalement de 31, le nombre maximum d'utilisateurs obtenu en pratique est de 23 avec l'utilisation de code correcteurs d'erreur et de 7 sans, tandis que du point de vue théorique on en espère 45In this thesis we study a communication system named spread spectrum. The principle of this system consists in distributing the energy of the signal to transmit on a frequency band broader than what is really necessary to the transmission of the useful signal. Spread spectrum is based on using "spreading sequences" having good properties of correlation. In this thesis we introduce error correcting codes to improve the efficiency of the spreading signal. The aim of this thesis is to determine the efficiency of this method and the selection criteria of the error-correcting codes to use. The maximum number of users depends on the choice of the error-correcting code used but also on the spreading sequence used. A synthesis of the spread spectrum and CDMA (Code Division Multiple Access) are presented in a first part. Theoretical limits are given and physical limits are posed. Next two systems of spread spectrum using different spreading sequence are presented and compared. The most powerful system, theoretically as well as practically, is the spread spectrum "with multiple dephasing". The last part presents various error-correcting codes and determines which one maximizes the number of users. However, for a binary error rate residual lower than 10-3 and a spreading factor of 31 the maximum number of users obtained in practice is 23 with using error-correcting code and 7 without it, while from the theoretical point of view the expected number is 45
24
Leverrier, Anthony. "Etude théorique de la distribution quantique de clés à variables continues." Phd thesis, Paris, Télécom ParisTech, 2009. https://theses.hal.science/tel-00451021.
Full textAbstract:
Cette thèse porte sur la distribution quantique de clés, qui est une primitive cryptographique qui permet à deux correspondants éloignés, Alice et Bob, d'établir une clé secrète commune malgré la présence potentielle d'un espion. On s'intéresse notamment aux protocoles « à variables continues »' où Alice et Bob encodent l'information dans l'espace des phases. L'intérêt majeur de ces protocoles est qu'ils sont faciles à mettre en œuvre car ils ne requièrent que des composants télécom standards. La sécurité de ces protocoles repose sur les lois de la physique quantique : acquérir de l'information sur les données échangées par Alice et Bob induit nécessairement un bruit qui révèle la présence de l'espion. Une étape particulièrement délicate pour les protocoles à variables continues est la « réconciliation » durant laquelle Alice et Bob utilisent leurs résultats de mesure classiques pour se mettre d'accord sur une chaîne de bits identiques. Nous proposons d'abord un algorithme de réconciliation optimal pour le protocole initial, puis introduisons un nouveau protocole qui résout automatiquement le problème de la réconciliation grâce à l'emploi d'une modulation discrète. Parce que les protocoles à variables continues sont formellement décrits dans un espace de Hilbert de dimension infinie, prouver leur sécurité pose des problèmes mathématiques originaux. Nous nous intéressons d'abord à des symétries spécifiques de ces protocoles dans l'espace des phases. Ces symétries permettent de simplifier considérablement l'analyse de sécurité. Enfin, nous étudions l'influence des effets de tailles finies, tels que l'estimation du canal quantique, sur les performances des protocolesThis thesis is concerned with quantum key distribution (QKD), a cryptographic primitive allowing two distant parties, Alice and Bob, to establish a secret key, in spite of the presence of a potential eavesdropper, Eve. Here, we focus on continuous-variable protocols, for which the information is coded in phase-space. The main advantage of these protocols is that their implementation only requires standard telecom components. The security of QKD lies on the laws of quantum physics: an eavesdropper will necessary induce some noise on the communication, therefore revealing her presence. A particularly difficult step of continuous-variable QKD protocols is the ``reconciliation'' where Alice and Bob use their classical measurement results to agree on a common bit string. We first develop an optimal reconciliation algorithm for the initial protocol, then introduce a new protocol for which the reconciliation problem is automatically taken care of thanks to a discrete modulation. Proving the security of continuous-variable QKD protocols is a challenging problem because these protocols are formally described in an infinite dimensional Hilbert space. A solution is to use all available symmetries of the protocols. In particular, we introduce and study a class of symmetries in phase space, which is particularly relevant for continuous-variable QKD. Finally, we consider finite size effects for these protocols. We especially analyse the influence of parameter estimation on the performance of continuous-variable QDK protocols
25
Leverrier, Anthony. "Etude théorique de la distribution quantique de clés à variables continues." Phd thesis, Télécom ParisTech, 2009. http://tel.archives-ouvertes.fr/tel-00451021.
Full textAbstract:
Cette thèse porte sur la distribution quantique de clés, qui est une primitive cryptographique permettant à deux correspondants éloignés, Alice et Bob, d'établir une clé secrète commune malgré la présence potentielle d'un espion. On s'intéresse notamment aux protocoles " à variables continues " où Alice et Bob encodent l'information dans l'espace des phases. L'intérêt majeur de ces protocoles est qu'ils sont faciles à mettre en œuvre car ils ne requièrent que des composants télécom standards. La sécurité de ces protocoles repose sur les lois de la physique quantique : acquérir de l'information sur les données échangées par Alice et Bob induit nécessairement un bruit qui révèle la présence de l'espion. Une étape particulièrement délicate pour les protocoles à variables continues est la " réconciliation " durant laquelle Alice et Bob utilisent leurs résultats de mesure classiques pour se mettre d'accord sur une chaîne de bits identiques. Nous proposons d'abord un algorithme de réconciliation optimal pour le protocole initial, puis introduisons un nouveau protocole qui résout automatiquement le problème de la réconciliation grâce à l'emploi d'une modulation discrète. Parce que les protocoles à variables continues sont formellement décrits dans un espace de Hilbert de dimension infinie, prouver leur sécurité pose des problèmes mathématiques originaux. Nous nous intéressons d'abord à des symétries spécifiques de ces protocoles dans l'espace des phases. Ces symétries permettent de simplifier considérablement l'analyse de sécurité. Enfin, nous étudions l'influence des effets de tailles finies, tels que l'estimation du canal quantique, sur les performances des protocoles.
26
Abdmouleh, Ahmed. "Codes correcteurs d'erreurs NB-LDPC associés aux modulations d'ordre élevé." Thesis, Lorient, 2017. http://www.theses.fr/2017LORIS452/document.
Full textAbstract:
Cette thèse est consacrée à l'analyse de l'association de codes LDPC non-binaires (LDPC-NB) à des modulations d’ordre élevé. Cette association vise à améliorer l’efficacité spectrale pour les futurs systèmes de communication sans fil. Notre approche a consisté à tirer au maximum profit de l'association directe des symboles d’un code LDPC-NB sur un corps de Galois avec une constellation de même cardinalité. Notre première contribution concerne la diversité spatiale obtenue dans un canal de Rayleigh avec et sans effacement en faisant subir une rotation à la constellation. Nous proposons d’utiliser l'information mutuelle comme paramètre d’optimisation de l’angle de rotation, et ce pour les modulations de type « BICM » et les modulations codées. Cette étude permet de mettre en évidence les avantages de la modulation codée par rapport à la modulation BICM de l’état de l’art. Par simulation de Monte-Carlo, nous montrons que les gains de codage théoriques se retrouvent dans les systèmes pratiques. Notre deuxième contribution consiste à concevoir conjointement l'étiquetage des points de constellation et le choix des coefficients d'une équation de parité en fonction de la distance euclidienne, et non plus de la distance de Hamming. Une méthode d’optimisation est proposée. Les codes ainsi construits offrent des gains de performance de 0.2 dB et ce, sans ajout de complexitéThis thesis is devoted to the analysis of the association of non-binary LDPC codes (NB-LDPC) with high-order modulations. This association aims to improve the spectral efficiency of future wireless communication systems. Our approach tries to take maximum advantage of the straight association between NB-LDPC codes over a Galois Field with modulation constellations of the same cardinality. We first investigate the optimization of the signal space diversity technique obtained with the Rayleigh channel (with and without erasure) thanks to the rotation of the constellation. To optimize the rotation angle, the mutual information analysis is performed for both coded modulation (CM) and bit-interleaved coded modulation (BICM) schemes. The study shows the advantages of coded modulations over the state-of-the-art BCIM modulations. Using Monte Carlo simulation, we show that the theoretical gains translate into actual gains in practical systems. In the second part of the thesis, we propose to perform a joint optimization of constellation labeling and parity-check coefficient choice, based on the Euclidian distance instead of the Hamming distance. An optimization method is proposed. Using the optimized matrices, a gain of 0.2 dB in performance is obtained with no additional complexity
27
Peirani, Béatrice. "Cryptographie à base de codes correcteurs d'erreurs et générateurs aléatoires." Aix-Marseille 1, 1994. http://www.theses.fr/1994AIX11046.
Full textAbstract:
Apres avoir rappele dans un premier chapitre les principales notions de codage et cryptographie, on donne un algorithme de chiffrement qui englobe les algorithmes de cryptographie standards utilisant des codes correcteurs d'erreurs (ceux de r. J. Mceliece (mc) et s. Harari (hal)), puis un cryptosysteme aleatoire avec feedback qui utilise un automate fini pour engendrer des permutations. Dans le chapitre suivant, une nouvelle famille de codes lineaires binaires correcteurs d'erreurs, dits en degrade, est introduite ; sa distance minimale est explicite et sa distribution de poids tend vers la loi normale. Ce nouveau code est utilise dans un cryptosysteme a clef secrete et revele un meilleur taux de transmission cryptographique que celui obtenu pour le systeme hal. Il a paru interessant d'analyser le comportement asymptotique de la distribution de poids d'un code en degrade couple avec un code simplexe, par la construction (u, u+v). Le resultat obtenu, par une methode non probabiliste, montre que le passage au code (u, u+v) ne modifie pas le comportement asymptotique de la distribution de poids. Enfin, dans un dernier chapitre, on developpe une notion de generateur aleatoire en temps polynomial, basee sur la theorie des automates et des chaines de markov, en utilisant les produits croises. En introduisant la notion de batterie de tests, il est alors possible de montrer que certains generateurs bases sur les chaines de markov fournissent de bons generateurs pseudo-aleatoires en temps polynomial
28
Gennero, Marie-Claude. "Contribution à l'étude théorique et appliquée des codes correcteurs d'erreurs." Toulouse 3, 1990. http://www.theses.fr/1990TOU30243.
Full textAbstract:
Dans une première partie, nous donnons une synthèse des principaux résultats de la théorie de l'information ainsi que des méthodes de compression. Nous unifions également dans une méthode algébrique la description des codes classiques, la factorisation de polynômes ainsi que la transformée de Fourier. En seconde partie, nous présentons une chaine de logiciels que nous avons mis au point, pour être intégrée dans un système expert. Nous avons validé cette chaine sur des données comprimées (images, parole). Nous avons mis en évidence les résultats obtenus, en faisant varier les différents paramètres. Dans le dernier chapitre nous donnons des tables et des courbes utiles pour des calculs dans des corps finis
29
Dallot, Léonard. "Sécurité de protocoles cryptographiques fondés sur les codes correcteurs d'erreurs." Caen, 2010. http://www.theses.fr/2010CAEN2047.
Full textAbstract:
La cryptographie fondée sur les codes correcteurs d'erreurs est apparue en 1968, dès les premières années de la cryptographie à clef publique. L'objet de cette thèse est l'étude de la sécurité de constructions cryptographiques appartenant à cette famille. Après avoir introduit des notions de cryptographie à clef publique et de sécurité réductionniste, nous présentons une étude rigoureuse de la sécurité réductionniste de trois schémas de chiffrement fondés sur les codes correcteurs d'erreurs : le schéma de McEliece, la variante de Niederreiter et un schéma hybride proposé par N. Sendrier et B. Biswas. Le bien-fondé de cette démarche est ensuite illustré par les cryptanalyses de deux variantes du schéma de McEliece visant à réduire la taille des clefs nécessaires pour assurer la confidentialité des échanges. Nous présentons ensuite une preuve réductionniste de la sécurité d'un schéma de signature proposé en 2001 par N. Courtois, M. Finiasz et N. Sendrier. Pour y parvenir, nous montrons qu'il est nécessaire de modifier légèrement le schéma. Enfin, nous montrons que les techniques utilisées pour construire le schéma précédent peuvent être également utilisées pour construire un schéma de signature de cercles à seuil prouvé sûrCode-based cryptography appeared in 1968, in the early years of public-key cryptography. The purpose of this thesis is the study of reductionist security of cryptographic constructions that belong to this category. After introducing some notions of cryptography and reductionist security, we present a rigorous analysis of reductionist security of three code-based encryption scheme : McEliece's cryptosystem, Niederreiter's variant and a hybrid scheme proposed by N. Sendrier and B. Biswas. The legitimacy of this approach is next illustrated by the cryptanalysis of two variants of McEliece's scheme that aim at reducing the size of the keys necessary for ensure communication confidentiality. Then we present a reductionist security proof of a signature scheme proposed in 2001 by N. Courtois, M. Finiasz and N. Sendrier. In order to manage this, we show that we need to slightly modify the scheme. Finally, we show that technics used in the previous scheme can also be used to build a provably secure threshold ring signature scheme
30
Rosseel, Joachim. "DÉCODAGE DE CODES CORRECTEURS D'ERREURS ASSISTÉ PAR APPRENTISSAGE POUR L'IOT." Electronic Thesis or Diss., CY Cergy Paris Université, 2023. http://www.theses.fr/2023CYUN1260.
Full textAbstract:
Les communications sans fil, déjà très présentes dans notre société, soulèvent de nouveaux défis dans le cadre du déploiement de l'Internet des Objets (IoT) tels que le développement de nouvelles méthodes de décodage au niveau de la couche physique permettant d'assurer de bonnes performances pour la transmission de messages courts. En particulier, les codes LDPC (Low Density Parity Check) sont une famille de codes correcteurs d'erreurs très connus pour leurs excellentes performances asymptotiques lorsqu'ils sont décodés par l'algorithme de propagation de croyance (BP, pour Belief Propagation, en anglais). Cependant, la capacité de correction de l'algorithme BP se retrouve fortement dégradée pour les codes LDPC courts. Ainsi, cette thèse porte sur l'amélioration du décodage des codes LDPC courts, grâce notamment à des outils d'apprentissage automatique, tels que les réseaux de neurones.Après avoir introduit les notions et caractéristiques des codes LDPC et du décodage BP,ainsi que la modélisation du BP par un réseau de neurones récurrent (BP-Recurrent NeuralNetwork ou BP-RNN), nous développons de nouvelles méthodes d'entraînement afin de spécialiser le décodeur BP-RNN sur des motifs d'erreurs partageant des propriétés structurelles similaires. Ces approches de spécialisation sont associées à des architectures de décodage composées de plusieurs BP-RNNs spécialisés, où chaque BP-RNN est entraîné à corriger un type différent de motif d'erreurs (diversité de décodage). Nous nous intéressons ensuite au post-traitement du BP (ou du BP-RNN) avec un décodage par statistiques ordonnées (Ordered Statistics Decoding ou OSD) afin de se rapprocher de la performance du décodage par maximum de vraisemblance. Pour améliorer les performances du post-traitement, nous optimisons son entrée grâce à un neurone simple, puis nous introduisons une stratégie de décodage pour un post-traitement par OSD multiples. Il est alors montré que cette stratégie tire efficacement partie de la diversité de ses entrées, fournissant ainsi un moyen efficace de combler l'écart avec le décodage par maximum de vraisemblanceWireless communications, already very present in our society, still raise new challengesas part of the deployment of the Internet of Things (IoT) such as the development of newdecoding methods at the physical layer ensuring good performance for the transmission ofshort messages. In particular, Low Density Parity Check (LDPC) codes are a family of errorcorrecting codes well-known for their excellent asymptotic error correction performanceunder iterative Belief Propagation (BP) decoding. However, the error correcting capacity ofthe BP algorithm is severely deteriorated for short LDPC codes. Thus, this thesis focuses on improving the decoding of short LDPC codes, thanks in particular to machine learning tools such as neural networks.After introducing the notions and characteristics of LDPC codes and BP decoding, aswell as the modeling of the BP algorithm by a Recurrent Neural Network (BP-RecurrentNeural Network or BP-RNN), we develop new training methods specializing the BP-RNN ondecoding error events sharing similar structural properties. These specialization approaches are subsequently associated decoding architectures composed of several specialized BP-RNNs, where each BP-RNN is trained to decode a specific kind of error events (decoding diversity). Secondly, we are interested in the post-processing of the BP (or the BP-RNN) with an Ordered Statistics Decoding (OSD) in order to close the gap the maximum likelihood (ML) decoding performance. To improve the post-processing performance, we optimize its input thanks to a single neuron and we introduce a multiple OSD post-processing decoding strategy. We then show that this strategy effectively takes advantage of the diversity of its inputs, thus providing an effective way to close the gap with ML decoding
31
Berhault, Guillaume. "Exploration architecturale pour le décodage de codes polaires." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0193/document.
Full textAbstract:
Les applications dans le domaine des communications numériques deviennent de plus en plus complexes et diversifiées. En témoigne la nécessité de corriger les erreurs des messages transmis. Pour répondre à cette problématique, des codes correcteurs d’erreurs sont utilisés. En particulier, les Codes Polaires qui font l’objet de cette thèse. Ils ont été découverts récemment (2008) par Arıkan. Ils sont considérés comme une découverte importante dans le domaine des codes correcteurs d’erreurs. Leur aspect pratique va de paire avec la capacité à proposer une implémentation matérielle de décodeur. Le sujet de cette thèse porte sur l’exploration architecturale de décodeurs de Codes Polaires implémentant des algorithmes de décodage particuliers. Ainsi, le sujet gravite autour de deux algorithmes de décodage : un premier algorithme de décodage à décisions dures et un autre algorithme de décodage à décisions souples.Le premier algorithme de décodage, à décisions dures, traité dans cette thèse repose sur l’algorithme par annulation successive (SC) comme proposé originellement. L’analyse des implémentations de décodeurs montre que l’unité de calcul des sommes partielles est complexe. De plus,la quantité mémoire ressort de cette analyse comme étant un point limitant de l’implémentation de décodeurs de taille importante. Les recherches menées afin de palier ces problèmes montrent qu’une architecture de mise à jour des sommes partielles à base de registres à décalages permet de réduire la complexité de cette unité. Nous avons également proposé une nouvelle méthodologie permettant de revoir la conception d’une architecture de décodeur déjà existante de manière relativement simple afin de réduire le besoin en mémoire. Des synthèses en technologie ASIC et sur cibles FPGA ont été effectués pour caractériser ces contributions. Le second algorithme de décodage, à décisions souples, traité dans ce mémoire, est l’algorithme SCAN. L’étude de l’état de l’art montre que le seul autre algorithme à décisions souples implémenté est l’algorithme BP. Cependant, il nécessite une cinquantaine d’itérations pour obtenir des performances de décodages au niveau de l’algorithme SC. De plus, son besoin mémoire le rend non implémentable pour des tailles de codes élevées. L’intérêt de l’algorithme SCAN réside dans ses performances qui sont meilleures que celles de l’algorithme BP avec seulement 2 itérations.De plus, sa plus faible empreinte mémoire le rend plus pratique et permet l’implémentation de décodeurs plus grands. Nous proposons dans cette thèse une première implémentation de cetalgorithme sur cibles FPGA. Des synthèses sur cibles FPGA ont été effectuées pour pouvoir comparer le décodeur SCAN avec les décodeurs BP de l’état de l’art.Les contributions proposées dans cette thèse ont permis d’apporter une réduction de la complexité matérielle du calcul des sommes partielles ainsi que du besoin général du décodeur en éléments de mémorisation. Le décodeur SCAN peut être utilisé dans la chaîne de communication avec d’autres blocs nécessitant des entrées souples. Cela permet alors d’ouvrir le champ d’applications des Codes Polaires à ces blocsApplications in the field of digital communications are becoming increasingly complex and diversified. Hence, the need to correct the transmitted message mistakes becomes an issue to be dealt with. To address this problem, error correcting codes are used. In particular, Polar Codes that are the subject of this thesis. They have recently been discovered (2008) by Arikan. They are considered an important discovery in the field of error correcting codes. Their practicality goes hand in hand with the ability to propose a hardware implementation of a decoder. The subject of this thesis focuses on the architectural exploration of Polar Code decoders implementing particular decoding algorithms. Thus, the subject revolves around two decoding algorithms: a first decoding algorithm, returning hard decisions, and another decoding algorithm, returning soft decisions.The first decoding algorithm, treated in this thesis, is based on the hard decision algorithm called "successive cancellation" (SC) as originally proposed. Analysis of implementations of SC decoders shows that the partial sum computation unit is complex. Moreover, the memory amount from this analysis limits the implementation of large decoders. Research conducted in order to solve these problems presents an original architecture, based on shift registers, to compute the partial sums. This architecture allows to reduce the complexity and increase the maximum working frequency of this unit. We also proposed a new methodology to redesign an existing decoder architecture, relatively simply, to reduce memory requirements. ASIC and FPGA syntheses were performed to characterize these contributions.The second decoding algorithm treated in this thesis is the soft decision algorithm called SCAN. The study of the state of the art shows that the only other implemented soft decision algorithm is the BP algorithm. However, it requires about fifty iterations to obtain the decoding performances of the SC algorithm. In addition, its memory requirements make it not implementable for huge code sizes. The interest of the SCAN algorithm lies in its performances which are better than those of the BP algorithm with only two iterations. In addition, its lower memory footprint makes it more convenient and allows the implementation of larger decoders. We propose in this thesis a first implementation of this algorithm on FPGA targets. FPGA syntheses were carried out in order to compare the SCAN decoder with BP decoders in the state of the art.The contributions proposed in this thesis allowed to bring a complexity reduction of the partial sum computation unit. Moreover, the amount of memory required by an SC decoder has been decreased. At last, a SCAN decoder has been proposed and can be used in the communication field with other blocks requiring soft inputs. This then broadens the application field of Polar Codes
32
Belkasmi, Mostafa. "Contribution à l'étude des codes correcteurs multicirculants." Toulouse 3, 1992. http://www.theses.fr/1992TOU30120.
Full textAbstract:
L'utilisation des codes correcteurs d'erreurs est un moyen efficace pour ameliorer la fiabilite des donnees transmises dans un canal bruite. Bien souvent ces codes peuvent etre consideres comme des objets particuliers d'algebres: sous-espaces vectoriels, ou ideaux d'algebres;. . . Certains bons codes (codes residus quadratiques,. . . ) admettent des matrices generatrices de forme remarquables (multicirculantes). Alors quelques chercheurs (g. F. M. Beenker, p. Rabizzoni, a. Poli. . . ) se sont penches sur l'etude des codes ideaux (codes de beenker generalises) qui par demultiplication avec 2 projections donnent naissance a des codes multicirculants. Dans cette these, nous avons etudie une nouvelle famille de codes de beenker generalises, qui par demultiplication avec m projections (m entier superieur ou egal a 2) donnent naissance a des codes multicirculants. Cette these est composee de quatre chapitres. Dans le premier chapitre nous donnons des generalites sur les codes lineaires puis nous developpons des outils polynomiaux dont on aura besoin pour la suite. Dans le second chapitre nous faisons une synthese de quelques constructions des codes multicirculants. Dans le troisieme, nous faisons une autre synthese de quelques methodes de codage et de decodage qui peuvent etre appliquees aux codes multicirculants. Dans le quatrieme chapitre nous developpons deux constructions algebriques des codes de beenker generalises qui par demultiplication avec m projections, donnent naissance a des codes multicirculants. Pour aboutir a ces deux constructions nous avons suivi deux approches differentes. L'une utilisant la decomposition d'algebres et l'autre utilisant la transformee de fourier. A partir de quelques codes construits nous avons deduit quatre codes binaires qui sont parmi les meilleurs codes connus actuellement. Ils ont les parametres suivants: (22,7,8) (40,13,12), (58,19,16) et (111,37,24). Nous presentons aussi une condition suffisante a l'existence de codes multicirculants autoduaux parmi la nouvelle famille de codes
33
Tale, kalachi Herve. "Sécurité des protocoles cryptographiques fondés sur la théorie des codes correcteurs d'erreurs." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMR045/document.
Full textAbstract:
Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bitsContrary to the cryptosystems based on number theory, the security of cryptosystems based on error correcting codes appears to be resistant to the emergence of quantum computers. Another advantage of these systems is that the encryption and decryption are very fast, about five times faster for encryption, and 10 to 100 times faster for decryption compared to RSA cryptosystem. Nowadays, the interest of scientific community in code-based cryptography is highly motivated by the latest announcement of the National Institute of Standards and Technology (NIST). They initiated the Post-Quantum cryptography Project which aims to define new standards for quantum resistant cryptography and fixed the deadline for public key cryptographic algorithm submissions for November 2017. This announcement motivates to study the security of existing schemes in order to find out whether they are secure. This thesis thus presents several attacks which dismantle several code-based encryption schemes. We started by a cryptanalysis of a modified version of the Sidelnikov cryptosystem proposed by Gueye and Mboup [GM13] which is based on Reed-Muller codes. This modified scheme consists in inserting random columns in the secret generating matrix or parity check matrix. The cryptanalysis relies on the computation of the square of the public code. The particular nature of Reed-Muller which are defined by means of multivariate binary polynomials, permits to predict the values of the dimensions of the square codes and then to fully recover in polynomial time the secret positions of the random columns. Our work shows that the insertion of random columns in the Sidelnikov scheme does not bring any security improvement. The second result is an improved cryptanalysis of several variants of the GPT cryptosystem which is a rank-metric scheme based on Gabidulin codes. We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. [Gab08, GRH09, RGH11] with the goal to resist Overbeck’s structural attack [Ove08], are actually still vulnerable to that attack. We show that by applying the Frobeniusoperator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code, but with a lower length. In particular, the code obtained by this way corrects less errors than thesecret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometrictransformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existingtechniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed. To finish, we studied the security of the Faure-Loidreau encryption scheme [FL05] which is also a rank-metric scheme based on Gabidulin codes. Inspired by our precedent work and, although the structure of the scheme differs considerably from the classical setting of the GPT cryptosystem, we show that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim
34
Senigon, de Roumefort Ravan de. "Approche statistique du vieillissement des disques optiques CD-Audio, CD-R, CD-RW." Paris 6, 2011. http://www.theses.fr/2011PA066109.
Full text
35
Diab, Menouer. "Contribution à l'étude des architectures systoliques pour les codes correcteurs d'erreurs." Toulouse 3, 1992. http://www.theses.fr/1992TOU30147.
Full textAbstract:
Les domaines d'application des codes correcteurs d'erreurs vont de l'enregistrement d'information sur supports magnetiques, disques compacts, jusqu'a la transmission d'information par ordinateurs ou par satellites. L'une des caracteristiques des algorithmes de codage et de decodage, des codes reellement utilises, est qu'ils necessitent un nombre considerable d'operations de calcul dans des corps finis de caracteristique deux (i. E. Dont le cardinal est une puissance entiere de deux). Parmi les plus complexes, tant du point de vue temporelle que materielle, il y a l'operation somme-produit (un produit et une somme). Pour repondre au besoin de plus en plus croissant de transmettre ou d'enregistrer les informations avec une grande fiabilite, a des debits eleves, avec des contraintes severes sur le poids, l'encombrement et la consommation en energie electrique, une approche consiste a concevoir des circuits vlsi specialises pour le codage et le decodage. Les principaux resultats de cette these concernent la conception d'architectures systoliques pour l'operation somme-produit dans des corps finis de caracteristique deux, ainsi que pour le codage des codes cycliques. Les codeurs systoliques proposes sont ensuite adaptes au calcul des syndromes (calcul utilise dans certains decodeurs). Comparees aux multiplieurs et codeurs systoliques existants, ces architectures presentent une plus faible complexite temporelle et materielle. De plus, contrairement aux premiers, certaines des architectures proposees permettent de realiser simultanement, d'une maniere multiplexee dans le temps, plusieurs operations somme-produit ou de codage. Cette propriete est tres attractive pour la realisation de codeurs et de decodeurs pour les codes entrelaces (permettant de lutter contre les erreurs en paquet). A travers cette propriete, l'auteur propose une nouvelle approche pour ameliorer les performances d'un certain type d'architectures systoliques, qualifiees de periodiques. Comparees aux multiplieurs et codeurs vlsi proposes dans la litterature, les architectures systoliques developpees offrent l'avantage d'etre, independantes vis-a-vis des parametres, plus modulaires, plus regulieres, de permettre plus de traitements paralleles, d'eviter l'utilisation des connexions de retour et d'etre plus rapides
36
Poli, Christine. "S. E. C. C : système expert pour les codes correcteurs d'erreurs." Toulouse 3, 1995. http://www.theses.fr/1995TOU30223.
Full textAbstract:
Secc est un systeme d'aide au choix d'un systeme de protection des donnees en transmission, utilisant les codes correcteurs d'erreurs. Confrontes au probleme de la representation des connaissances incertaines et imprecises (suite aux recueil d'expertises), secc utilise la theorie des possibilites et les ensembles flous. L'incertitude liee a l'utilisation de connaissances agregees (ensembles flous donnes par plusieurs experts pour un meme concept) est integree dans secc sous la forme d'un coefficient de confiance, fonde sur l'entropie de shannon. Le moteur d'inference utilise ce coefficient pour ecarter du raisonnement les connaissances divergentes. Nous introduisons des notions de base sur un systeme de transmission, des contraintes liees au canal plus modem et au type d'information transmise, et nous formulons des performances exigees. Nous explicitons cinq strategies de protection (et les sous-strategies associees) utilisant des codes correcteurs d'erreurs. Nous avons formalise le raisonnement des experts en codes en trois niveaux de decision. Secc effectue un classement des strategies de protection possibles (puis des sous-strategies) a l'aide de regles de deduction et de regles de classement. Puis, il construit le systeme de protection adapte, de maniere recursive en utilisant des objets representant les elements de base comme un code, un decodage, un decodeur. Le systeme propose peut etre compose d'un seul code (decodage et decodeur), ou par plusieurs codes. Enfin, secc peut piloter des simulations informatiques du systeme de protection, pour evaluer l'efficacite du code
37
Ollivier, Harold. "Eléments de théorie de l'information quantique, décohérence et codes correcteurs d'erreurs." Palaiseau, Ecole polytechnique, 2004. http://www.theses.fr/2004EPXX0027.
Full text
38
Planquette, Guillaume. "Étude de certaines propriétés algébriques et spectrales des codes correcteurs d'erreurs." Rennes 1, 1996. http://www.theses.fr/1996REN10207.
Full textAbstract:
Cette these est consacree a l'etude de certaines proprietes des codes et codeurs correcteurs d'erreur. Les signaux que nous etudions sont issus de codeurs par blocs et de codeurs convolutifs. L'etude se deroule selon deux axes distincts : l'un theorique, l'autre algorithmique. Contrairement aux codes en blocs, la structure des codes convolutifs est mal connue. Nous presentons de nouvelles proprietes des codeurs convolutifs : caracterisation des codes catastrophiques, propriete de saut de rang ce qui permet finalement de reconstruire un codeur minimal permettant de generer un code donne. L'etude des proprietes se poursuit par le calcul de la correlation spectrale et de la densite spectrale de puissance (dsp) des codes convolutifs et des codes par blocs. Celui-ci montre que, sous certaines conditions, la dsp de ces signaux possede une partie discrete composee de raies harmoniques dont il faut s'affranchir car ces raies jouent le role de brouilleurs vis-a-vis des communications transitant sur les canaux adjacents. Nous nous interessons ensuite au calcul pratique de la distance minimale d'un code. On s'interesse a deux algorithmes de recherche pratique des vecteurs de poids faible dans un code a partir de sa matrice generatrice : l'algorithme de j. S. Leon et la variante de a. Canteaut et f. Chabaud. Leur complexite moyenne theorique est approchee ce qui permet d'en optimiser les parametres et de fixer le champ de leur application. Enfin nous developpons un algorithme a vocation purement traitement du signal : l'harmogramme. Ce recepteur permet de detecter une suite de raies harmoniques et d'en estimer le fondamental ; on en etablit differentes versions selon la connaissance a priori du signal a detecter.
39
Pham, Sy Lam. "Codes correcteurs d'erreurs au niveau applicatif pour les communications par satellite." Thesis, Cergy-Pontoise, 2012. http://www.theses.fr/2012CERG0574.
Full textAbstract:
L’objectif de la thèse est l’étude des codes correcteurs d’erreurs au niveau applicatif (Application Layer – Forward Error Correction, ou AL-FEC) pour les communications par satellite. Dans ce contexte, pendant les deux première années de thèse, nous avons proposé de nouvelles méthodes d’analyse, de construction et d’optimisation des codes à effacements définis par des matrices de parité à faible densité (code LDPC, pour « Low Density Parity Check » en anglais). La troisième année de la thèse a été consacrée à : (1) La suite des études portant sur de nouvelles méthodes de construction des codes LDPC non-binaires. D’une part, nous avons développé un nouvel algorithme (Scheduled-PEG) qui permet d’optimiser la construction des codes LDPC non-binaires pas rapport aux métriques de performance spécifiques à la couche application, notamment dans le cadre des systèmes de diffusion de contenu (broadcasting). D’autre part, nous avons proposé une nouvelle méthode de construction de codes à faible rendement, qui utilise l’image binaire étendue d’un code LDPC non-binaire. Ces études ont fait l’objet de deux publications dans deux conférences internationales : (a) “Scheduled-PEG construction of LDPC codes for Upper-Layer FEC”, International Workshop on Coding and Cryptography, April 2011, Paris, France. (b) “Extended Non-Binary Low-Density Parity-Check Codes over Erase Channels”, IEEE International Symposium on Wireless Communication Systems, November 2011, Aachen, Germany. (2) Une étude portant sur l’analyse asymptotique de codes cluster-LDPC non-binaires. Cette nouvelle classe de codes – introduite récemment (ISIT’2011) – se distingue par ses excellentes propriétés en termes de distance minimale. Notre étude a permis de déterminer de manière analytique la capacité de correction des codes cluster-LDPC non-binaires, aussi bien pour le décodage itératif par propagation de croyances (BP, pour « Belief Propagation ») que pour le décodage par maximum de vraisemblance (ML, pour « Maximum Likelihood »). Ces résultats seront intégrés à une publication scientifique sur les codes cluster-LDPC, en cours de rédaction, qui sera soumise à « IEEE Transactions on Information Theory », avant la fin de l’année 2011. (3) Une étude portant sur une méthode de construction des codes LDPC qui permet de réduire de manière significative le plancher d’erreur (« error floor ») du code, sans dégrader ses performances dans la région de « waterfall ». Ainsi, nous avons proposé la structuration de la matrice de parité du code, de manière à intégrer une partie irrégulière, optimisée pour la partie « waterfall », et une partie régulière, qui permet de réduire le plancher d’erreur du code. Cette étude fera l’objet d’une publication dans une conférence internationale (à déterminer), à soumettre début 2012The advent of content distribution, IPTV, video-on-demand and other similar services accelerate the demand for reliable data transmission over highly heterogeneous networks and toward terminals potentially heterogeneous too. In this context, Forward Error Correction (FEC) codes that operate at the transport or the Application Layer (AL-FEC) are used in conjunction with the FEC codes implemented at the physical layer, in order to improve the overall performance of the communication system. AL-FEC codes are aimed at recovering erased data packets and they are essential in many multicast/broadcast environments, no matter the way the information is transported, for instance using a wired or wireless link, and a terrestrial, satellite-based or hybrid infrastructure.This thesis addresses the design of Low Density Parity Check (LDPC) codes for AL-FEC applications. One the one hand, we provide an asymptotical analysis of non-binary LDPC codes over erasure channels, as well as waterfall and error-floor optimization techniques for finite-length codes. On the other hand, new concepts and coding techniques are developed in order to fully exploit the potential of non-binary LDPC codes.The first contribution of this thesis consists of the analysis and optimization of two new ensembles of LDPC codes. First, we have derived the density evolution equations for a very general ensemble of non-binary LDPC codes with rank-deficient coefficients. This allows improving the code performance, as well as designing ensembles of LDPC codes that can be punctured in an effective manner. The second approach allows the asymptotical optimization of a particular ensemble of LDPC codes, while ensuring low error-floors at finite lengths.The second contribution is the construction of finite length LDPC codes with good waterfall and error floor performance. Two approaches were investigated, according to the metric used to evaluate the code. The “Scheduled” Progressive Edge Growth (SPEG) algorithm is proposed, in order to optimize the waterfall performance of the code. Another method is proposed which consists in optimizing a specific structure of the parity check matrix. This approach gives low error-floors.The third contribution investigates a new technique of rate adaptability for non-binary LDPC codes. We propose a new method to generate “on-the-fly” incremental redundancy, which allows designing codes with flexible coding rates, in order to cope with severe channel conditions or to enable Fountain-like distribution applications.The fourth contribution focuses on a new class of LDPC codes, called non-binary cluster-LDPC codes. We derive exact equations of the density evolution for the iterative decoding and an upper bound for the maximum-likelihood decoding.Finally, we propose a practical solution to the problem of reliable communication via satellite to high-speed trains. Here, the challenge is that obstacles present along the track regularly interrupt the communication. Our solution offers optimal performance with a minimum amount of redundancy
40
Richmond, Tania. "Implantation sécurisée de protocoles cryptographiques basés sur les codes correcteurs d'erreurs." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSES048/document.
Full textAbstract:
Le premier protocole cryptographique basé sur les codes correcteurs d'erreurs a été proposé en 1978 par Robert McEliece. La cryptographie basée sur les codes est dite post-quantique car il n'existe pas à l'heure actuelle d'algorithme capable d'attaquer ce type de protocoles en temps polynomial, même en utilisant un ordinateur quantique, contrairement aux protocoles basés sur des problèmes de théorie des nombres. Toutefois, la sécurité du cryptosystème de McEliece ne repose pas uniquement sur des problèmes mathématiques. L'implantation, logicielle ou matérielle, a également un rôle très important pour sa sécurité et l'étude de celle-ci face aux attaques par canaux auxiliaires/cachés n'a débuté qu'en 2008. Des améliorations sont encore possibles. Dans cette thèse, nous proposons de nouvelles attaques sur le déchiffrement du cryptosystème de McEliece, utilisé avec les codes de Goppa classiques, ainsi que des contre-mesures correspondantes. Les attaques proposées sont des analyses de temps d'exécution ou de consommation d'énergie. Les contre-mesures associées reposent sur des propriétés mathématiques et algorithmiques. Nous montrons qu'il est essentiel de sécuriser l'algorithme de déchiffrement en le considérant dans son ensemble et non pas seulement étape par étapeThe first cryptographic protocol based on error-correcting codes was proposed in 1978 by Robert McEliece. Cryptography based on codes is called post-quantum because until now, no algorithm able to attack this kind of protocols in polynomial time, even using a quantum computer, has been proposed. This is in contrast with protocols based on number theory problems like factorization of large numbers, for which efficient Shor's algorithm can be used on quantum computers. Nevertheless, the McEliece cryptosystem security is based not only on mathematical problems. Implementation (in software or hardware) is also very important for its security. Study of side-channel attacks against the McEliece cryptosystem have begun in 2008. Improvements can still be done. In this thesis, we propose new attacks against decryption in the McEliece cryptosystem, used with classical Goppa codes, including corresponding countermeasures. Proposed attacks are based on evaluation of execution time of the algorithm or its power consumption analysis. Associate countermeasures are based on mathematical and algorithmic properties of the underlying algorithm. We show that it is necessary to secure the decryption algorithm by considering it as a whole and not only step by step
41
Cayrel, Pierre-Louis. "Construction et optimisation de cryptosystèmes basés sur les codes correcteurs d'erreurs." Limoges, 2008. https://aurore.unilim.fr/theses/nxfile/default/46aac3f7-1539-4684-bef6-9b1ae632c183/blobholder:0/2008LIMO4026.pdf.
Full textAbstract:
Dans cette thèse, on s’intéresse à l’étude de systèmes de chiffrement ainsi que de schémas de signature dont la sécurité repose sur des problèmes difficiles de théorie des codes correcteurs d’erreurs. Ces activités de recherche ont été motivées, d’une part d’un point de vue théorique par la création de nouveaux schémas de signature avec des propriétés spéciales ainsi que d’une manière de réduire la taille de clés du schéma de McEliece, et d’autre part, d’un point de vue pratique visant à utiliser des propriétés structurelles afin d’obtenir des implémentations effectives d’un schéma de signature fondé sur les codes correcteurs d’erreurs. Comme l’indique son titre, cette thèse traite de la construction et de l’optimisation des cryptosystèmes basés sur des codes correcteurs d’erreurs et plus particulièrement de cinq nouveaux protocoles. On présente ici une version sécurisée du schéma de Stern dans un environnement à faibles ressources, une nouvelle construction du schéma de Kabatianski, Krouk et Smeets, un schéma de signature basé sur l’identité prouvé sûr dans le modèle de l’oracle aléatoire, un schéma de signature de cercle à seuil et enfin une réduction de la taille de clés du schéma de McEliece à l’aide de codes alternants quasi-cycliques. En annexe, on présente un travail traitant des attaques algébriques de registre à décalage avec mémoire. On présente aussi brièvement une étude des codes cycliques sur des anneaux de matricesIn this thesis, we are interested in the study of encryption systems as well as signature schemes whose security relies on difficult problems of error-correcting codes. These research activities have been motivated, a part of a theoretical point of view by creating : new signature schemes with special properties and a way of reducing the size of the key of the McEliece scheme, and on the other hand, a practical point of view to use structural properties to obtain effective implementations of a signature scheme which is based on error-correcting codes. As its title indicates, this thesis deals with the construction and optimization of cryptosystems based on error-correcting codes and more particularly five new protocols. It presents a secure version of the Stern scheme in a low-resources environment, a new construction of the Kabatianski, Krouk and Smeets scheme, a signature scheme based on the identity proved secure in the random oracle model, a threshold ring signature scheme and a reduction of the size of the key of the McEliece scheme using quasi-cyclic alternant codes. In the annex, this work deals with algebraic attacks against linear feedback shift register with memory. It also presents a brief study of cyclic codes on rings of matrices
42
Khedher, Houda. "Effets des codes correcteurs d'erreurs sur les systèmes CDMA à taux multiples." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape8/PQDD_0004/MQ44700.pdf.
Full text
43
Finiasz, Matthieu. "Nouvelles constructions utilisant des codes correcteurs d'erreurs en cryptographie à clef publique." Palaiseau, Ecole polytechnique, 2004. http://www.theses.fr/2004EPXX0033.
Full text
44
Rochet, Raphaël. "Synthèse Automatique de Contrôleurs avec Contraintes de Sûreté de Fonctionnement." Phd thesis, Grenoble INPG, 1996. http://tel.archives-ouvertes.fr/tel-00345417.
Full textAbstract:
Cette thèse propose de nouvelles méthodes de synthèse automatique des contrôleurs internes aux circuits numériques. Elles permettent en particulier d'intégrer, directement au niveau du contrôleur, des dispositifs de détection d'erreurs ou de tolérance aux fautes. En ce qui concerne la détection d'erreurs, quatre flots de synthèse ont été implantés. Deux d'entre eux utilisent la méthode classique de duplication et comparaison, tandis que les deux autres sont basés sur la vérification d'un flot de contrôle par analyse de signature. La signature est une information permettant de caractériser la séquence parcourue d'états du contrôleur. La vérification du flot de contrôle correspond à la détection des séquences illégales d'états. En ce qui concerne la tolérance aux fautes, quatre flots ont été implantés. Deux d'entre eux utilisent la méthode classique de triplement et vote majoritaire, tandis que les deux autres sont basés sur l'utilisation d'un code correcteur d'erreurs lors du codage du contrôleur. Une erreur survenant dans le code de l'état courant peut ainsi être corrigée en utilisant les propriétés du code correcteur choisi. L'analyse des résultats de synthèse de nombreux exemples montre l'intérêt des nouvelles méthodes de détection et de tolérance proposées, et des algorithmes de synthèse implantés. Ainsi, ces méthodes et ces algorithmes permettent, entre autres, de définir de nouveaux compromis coût/sûreté de fonctionnement, en réduisant sensiblement le coût matériel de la redondance implantée. L'automatisation des traitements permet de plus de réduire le coût de conception lié à l'amélioration de la sûreté de fonctionnement des contrôleurs, en particulier lorsque des techniques plus pointues sont préférées à la redondance massive
45
Bonvard, Aurélien. "Algorithmes de détection et de reconstruction en aveugle de code correcteurs d'erreurs basés sur des informations souples." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2020. http://www.theses.fr/2020IMTA0178.
Full textAbstract:
Les dernières décennies ont connu l’essor des communications numériques. Ceci a donné lieu à la prolifération des standards de communication, ce qui demande une plus grande adaptabilité des systèmes de communication. Une manière de rendre ces systèmes plus flexibles consiste à concevoir un récepteur intelligent qui serait capable de retrouver l’ensemble des paramètres de l’émetteur. Dans ce manuscrit, nous nous intéressons à l’identification en aveugle des codes correcteurs d’erreurs. Nous proposons des méthodes originales, basées sur le calcul de distances euclidiennes entre des séquences de symboles bruités. Tout d’abord, un premier algorithme de classification permet la détection d’un code puis l’identification de la longueur de ses mots de code. Un second algorithme basé sur le nombre de collisions permet quand à lui d’identifier la longueur des mots d’informations. Ensuite, nous proposons une autre méthode utilisant cette fois les distances euclidiennes minimales pour l’identification de la longueur d’un code en bloc. Enfin, une méthode de reconstruction du code dual d’un code correcteur d’erreurs est présentéeRecent decades have seen the rise of digital communications. This has led to a proliferation of communication standards, requiring greater adaptability of communication systems. One way to make these systems more flexible is to design an intelligent receiver that would be able to retreive all the parameters of the transmitter from the received signal. In this manuscript, we are interested in the blind identification of error-correcting codes. We propose original methods based on the calculation of Euclidean distances between noisy symbol sequences. First, a classification algorithm allows the detection of a code and then the identification of its code words lenght. A second algorithm based on the number of collisions allows to identify the length of the information words. Then, we propose another method using the minimum Euclidean distances to identify block codes length. Finally, a method for reconstructing the dual code of an error-correcting code is presented
46
Calas, Yvan. "Performances des codes correcteurs d'erreur au niveau applicatif dans les réseaux." Montpellier 2, 2003. http://www.theses.fr/2003MON20166.
Full text
47
Gillot, Valérie. "La methode des sommes exponentielles a plusieurs variables pour les codes correcteurs d'erreurs." Toulon, 1993. http://www.theses.fr/1993TOUL0003.
Full textAbstract:
L'evaluation du poids des mots de certains codes correcteurs d'erreurs nous amene a evaluer certaines sommes exponentielles. Nous decrivons et etudions les proprietes d'une transformation sur les polynomes qui nous donnent des resultats sur des sommes exponentielles evaluees sur des corps finis. Tout d'abord, la borne de deligne appliquee au transforme d'un polynome a une variable nous permet d'etablir une premiere borne sur la somme exponentielle du polynome en termes de poids q-aires de ses puissances. Cette borne donne une borne theorique sur le poids des mots non-nuls de familles de codes et dans certains cas elle ameliore les bornes connues. La theorie liant polyedres de newton et sommes exponentielles, ainsi que la transformation initiale nous permettent d'obtenir une borne sur la somme exponentielle d'un polynome diagonal evaluee sur une extension quadratique, et de ce fait d'obtenir une borne sur le nombre de solutions de certaines equations diagonales
48
Jaber, Houssein. "Conception architecturale haut débit et sûre de fonctionnement pour les codes correcteurs d'erreurs." Thesis, Metz, 2009. http://www.theses.fr/2009METZ042S/document.
Full textAbstract:
Les systèmes de communication modernes exigent des débits de plus en plus élevés afin de traiter des volumes d'informations en augmentation constante. Ils doivent être flexibles pour pouvoir gérer des environnements multinormes, et évolutifs pour s'adapter aux normes futures. Pour ces systèmes, la qualité du service (QoS) doit être garantie malgré l'évolution des technologies microélectroniques qui augmente la sensibilité des circuits intégrés aux perturbations externes (impact de particules, perte de l'intégrité du signal, etc.). La tolérance aux fautes devient un critère important pour améliorer la fiabilité et par conséquence la qualité de service. Cette thèse s'inscrit dans la continuité des travaux menés au sein du laboratoire LICM concernant la conception architecturale d'une chaîne de transmission à haut débit, faible coût, et sûre de fonctionnement. Elle porte sur deux axes de recherche principaux : le premier axe porte sur les aspects rapidité et flexibilité, et en particulier sur l'étude et l'implantation d'architectures parallèles-pipelines dédiées aux codeurs convolutifs récursifs. Le principe repose sur l'optimisation des blocs calculant le reste de la division polynomiale qui constitue l'opération critique du codage. Cette approche est généralisée aux filtres récursifs RII. Les caractéristiques architecturales principales recherchées sont une grande flexibilité et une extensibilité aisée, tout en préservant la fonctionnalité ainsi qu'un bon équilibre entre quantité de ressources utilisées (et donc surface consommée) et performances obtenues (vitesse de fonctionnement) ; le deuxième axe de recherche porte sur le développement d'une méthodologie de conception de codeurs sûrs en présence de fautes, améliorant ainsi la tolérance de circuits intégrés numériques. L’approche proposée consiste à ajouter aux codeurs des blocs supplémentaires permettant la détection matérielle en ligne de l'erreur afin d'obtenir des architectures sûrs en présence des fautes. Les solutions proposées permettent d'obtenir un bon compromis entre complexité et fréquence de fonctionnement. Afin d'améliorer encore le débit du fonctionnement, nous proposons également des versions parallèles-pipelines des codeurs sûrs. Différents campagnes d'injection de fautes simples, doubles, et aléatoires ont été réalisées sur les codeurs afin d'évaluer les taux de détection d’erreurs. L'étude architectures sûrs de fonctionnement a ensuite été étendue aux décodeurs parallèles-pipeline pour les codes cycliques en blocs. L'approche choisie repose sur une légère modification des architectures parallèles-pipeline développéesNowadays, modern communication systems require higher and higher data throughputs to transmit increasing volumes of data. They must be flexible to handle multi-norms environments, and progressive to accommodate future norms. For these systems, quality of service (QoS) must be guaranteed despite the evolution of microelectronics technologies that increase the sensitivity of integrated circuits to external perturbations (impact of particles, loss of signal integrity, etc). Fault-tolerance techniques are becoming more and more an important criteria to improve the dependability and the quality of service. This thesis’work continues previous research undertaken at the LICM laboratory on the architectural design of high-speed, low-cost, and dependable transmission systems. It focuses on two principal areas of research : The first research area concerns the speed and flexibility aspects, particularly on the study and implementation of parallel-pipelined architectures dedicated to recursive convolutional encoders. The principle is based on the optimization of blocks that calculate the remainder of the polynomial division which constitute the critical operation of the encoding. This approach is generalized to recursive IIR filters. The main architectural characteristics being aimed are high flexibility and scalability, yet preserving a good trade-off between the amount of resources used (and hence, area consumption) and the obtained performance (operation speed). The second topic concerns the developing of a methodology for designing FS (fault-secure) encoders, improving the tolerance of digital integrated circuits. The proposed approach consists in adding an extra blocks to the encoders, allowing online error detection. The proposed solutions offer a good compromise between complexity and frequency operation. For even higher throughput, parallel-pipelined implementations of FS encoders were considered. Different fault injection campaigns of single, double, and random errors were applied to the encoders in order to evaluate error detection rates. The study of dependable architecture was extended to pipeline-parallel decoders for cyclic block codes. This approach is based on a slight modification of the parallel-pipeline architectures developed at LICM laboratory, introducing some redundancy in order to make it dependable
49
Jaber, Houssein. "Conception architecturale haut débit et sûre de fonctionnement pour les codes correcteurs d'erreurs." Electronic Thesis or Diss., Metz, 2009. http://www.theses.fr/2009METZ042S.
Full textAbstract:
Les systèmes de communication modernes exigent des débits de plus en plus élevés afin de traiter des volumes d'informations en augmentation constante. Ils doivent être flexibles pour pouvoir gérer des environnements multinormes, et évolutifs pour s'adapter aux normes futures. Pour ces systèmes, la qualité du service (QoS) doit être garantie malgré l'évolution des technologies microélectroniques qui augmente la sensibilité des circuits intégrés aux perturbations externes (impact de particules, perte de l'intégrité du signal, etc.). La tolérance aux fautes devient un critère important pour améliorer la fiabilité et par conséquence la qualité de service. Cette thèse s'inscrit dans la continuité des travaux menés au sein du laboratoire LICM concernant la conception architecturale d'une chaîne de transmission à haut débit, faible coût, et sûre de fonctionnement. Elle porte sur deux axes de recherche principaux : le premier axe porte sur les aspects rapidité et flexibilité, et en particulier sur l'étude et l'implantation d'architectures parallèles-pipelines dédiées aux codeurs convolutifs récursifs. Le principe repose sur l'optimisation des blocs calculant le reste de la division polynomiale qui constitue l'opération critique du codage. Cette approche est généralisée aux filtres récursifs RII. Les caractéristiques architecturales principales recherchées sont une grande flexibilité et une extensibilité aisée, tout en préservant la fonctionnalité ainsi qu'un bon équilibre entre quantité de ressources utilisées (et donc surface consommée) et performances obtenues (vitesse de fonctionnement) ; le deuxième axe de recherche porte sur le développement d'une méthodologie de conception de codeurs sûrs en présence de fautes, améliorant ainsi la tolérance de circuits intégrés numériques. L’approche proposée consiste à ajouter aux codeurs des blocs supplémentaires permettant la détection matérielle en ligne de l'erreur afin d'obtenir des architectures sûrs en présence des fautes. Les solutions proposées permettent d'obtenir un bon compromis entre complexité et fréquence de fonctionnement. Afin d'améliorer encore le débit du fonctionnement, nous proposons également des versions parallèles-pipelines des codeurs sûrs. Différents campagnes d'injection de fautes simples, doubles, et aléatoires ont été réalisées sur les codeurs afin d'évaluer les taux de détection d’erreurs. L'étude architectures sûrs de fonctionnement a ensuite été étendue aux décodeurs parallèles-pipeline pour les codes cycliques en blocs. L'approche choisie repose sur une légère modification des architectures parallèles-pipeline développéesNowadays, modern communication systems require higher and higher data throughputs to transmit increasing volumes of data. They must be flexible to handle multi-norms environments, and progressive to accommodate future norms. For these systems, quality of service (QoS) must be guaranteed despite the evolution of microelectronics technologies that increase the sensitivity of integrated circuits to external perturbations (impact of particles, loss of signal integrity, etc). Fault-tolerance techniques are becoming more and more an important criteria to improve the dependability and the quality of service. This thesis’work continues previous research undertaken at the LICM laboratory on the architectural design of high-speed, low-cost, and dependable transmission systems. It focuses on two principal areas of research : The first research area concerns the speed and flexibility aspects, particularly on the study and implementation of parallel-pipelined architectures dedicated to recursive convolutional encoders. The principle is based on the optimization of blocks that calculate the remainder of the polynomial division which constitute the critical operation of the encoding. This approach is generalized to recursive IIR filters. The main architectural characteristics being aimed are high flexibility and scalability, yet preserving a good trade-off between the amount of resources used (and hence, area consumption) and the obtained performance (operation speed). The second topic concerns the developing of a methodology for designing FS (fault-secure) encoders, improving the tolerance of digital integrated circuits. The proposed approach consists in adding an extra blocks to the encoders, allowing online error detection. The proposed solutions offer a good compromise between complexity and frequency operation. For even higher throughput, parallel-pipelined implementations of FS encoders were considered. Different fault injection campaigns of single, double, and random errors were applied to the encoders in order to evaluate error detection rates. The study of dependable architecture was extended to pipeline-parallel decoders for cyclic block codes. This approach is based on a slight modification of the parallel-pipeline architectures developed at LICM laboratory, introducing some redundancy in order to make it dependable
50
Couvreur, Alain. "Résidus de 2-formes différentielles sur les surfaces algébriques et applications aux codes correcteurs d'erreurs." Phd thesis, Université Paul Sabatier - Toulouse III, 2008. http://tel.archives-ouvertes.fr/tel-00376546.
Full textAbstract:
La théorie des codes géométriques s'est développée au début des années 80 sur l'impulsion d'un article de V.D. Goppa publié en 1981. Etant donnée une courbe algébrique projective lisse X sur un corps fini, on dispose de deux constructions de codes correcteurs d'erreurs. Une construction dite fonctionnelle qui fait intervenir certaines fonctions rationnelles sur X et une construction différentielle qui fait appel à certaines 1-formes différentielles rationnelles sur X . L'étude de ces codes construits sur des courbes a donné lieu à la publication de plusieurs centaines d'articles. Parallèlement à ces travaux, une généralisation de la construction fonctionnelle à des variétés algébriques de dimension quelconque est proposée par Y. Manin dans un article publié en 1984. On dénombre quelques dizaines de travaux publiés portant sur l'étude de tels codes. Cependant, aucun développement n'a été effectué dans le sens d'une généralisation de la construction différentielle. Dans cette thèse nous proposons une construction différentielle de codes sur des surfaces algébriques. Nous étudions ensuite les propriétés de ces codes et plus particulièrement leurs relations avec les codes fonctionnels. De façon un peu surprenante, on observe l'apparition d'une différence majeure avec le cas des courbes. En effet, si sur une courbe l'orthogonal d'un code fonctionnel est différentiel, ce fait est en général faux sur une surface. Ce résultat motive l'étude des orthogonaux de codes fonctionnels. Des formules pour l'estimation de la distance minimale de tels codes sont données en utilisant des propriétés de systèmes linéaires sur une variété. On montre également que, sous certaines conditions sur la surface, ces codes sont somme de codes différentiels et que des réponses à certains problèmes ouverts de géométrie algébrique "à la Bertini" fourniraient des informations supplémentaires sur les paramètres de ces codes.