introduction

La sécurité de l'information est un domaine de connaissances fascinant qui peut impliquer tout, de l'informatique théorique à l'ingénierie logicielle, et même à la psychologie de l'erreur humaine.

Crypto est désormais l'un des nombreux héros technologiques anonymes de notre vie quotidienne. Les médias sociaux, les services bancaires en ligne, le renseignement militaire et tout autre système d'information traitant des informations sensibles dépendent fortement de la cryptographie. La cryptographie nous permet d'avoir une confidentialité, ce que certains considèrent le 12e droit de l'homme .

Cet article vous donnera une introduction aux principes derrière les cryptosystèmes à clé publique et vous présentera Santana Rocha-Villas Boas (SRVB) , un cryptosystème développé par l'auteur de l'article et le professeur Daniel Santana Rocha. Au moment de la rédaction de cet article, les auteurs de l'algorithme préparent une campagne qui comprend une récompense financière pour quiconque parvient à déchiffrer le code. Comme l'article couvrira en détail les fonctionnalités de l'algorithme, c'est le meilleur endroit pour commencer votre recherche du prix. Plus d'informations sont disponibles dans le Site SRVB .

Qu'est-ce qu'un cryptosystème?

La cryptographie est toute méthode qui empêche l'interprétabilité d'un message, tout en permettant également un moyen de l'interpréter de manière viable à condition qu'une instruction spécifique soit fournie, ce que l'on appelle généralement la «clé». Bien qu'il s'agisse d'une définition très large qui englobe même les premières techniques, il convient de mentionner que cela ne couvre pas tout ce qui concerne la sécurité de l'information.

On espère que la course technologique entre les méthodes de cryptage et les moyens de les déchiffrer n'aura jamais de gagnant définitif. De plus, chaque nouvelle génération élève les normes de sécurité de l'information et de cryptanalyse, qui est l'ensemble des techniques permettant de décrypter / casser systématiquement les messages cryptés, c'est-à-dire en contournant la sécurité ou le cryptage.

Pour que les utilisateurs puissent considérer qu'un cryptosystème (compte tenu de la technique de cryptographie) est sécurisé, il doit avoir l'approbation de la communauté internationale d'experts et, par conséquent, être publiquement connu, ce que l'on appelle Principe de Kerckhoff . Cependant, cette condition même expose le système à l'examen minutieux de la communauté mondiale de la cryptanalyse, qui tentera de trouver des moyens de briser systématiquement les cryptages.

Comment pouvez-vous rendre un certain processus de chiffrement suffisamment secret pour que seuls les agents tentés puissent le déchiffrer, tout en étant suffisamment public pour que la communauté mondiale de la cryptanalyse puisse attester de sa robustesse? La réponse est un composant qui est un élément clé de la cryptologie: la clé. Une clé d'un cryptosystème est un paramètre pour les algorithmes de cryptage ou de décryptage, ou les deux. En gardant les paramètres secrets, plutôt que la famille d'algorithmes, les deux exigences contradictoires peuvent être satisfaites. Tant que la famille de paramètres est suffisamment grande (éventuellement infinie) et que chacun de ses composants peut être démontré comme ayant des propriétés adéquates, il ne sera pas possible pour les attaquants de déterminer les paramètres simplement par inspection.

Enfin, pour qu'une clé fonctionne efficacement, elle doit être produite facilement mais presque impossible à deviner. Avec la puissance de calcul des ordinateurs d'aujourd'hui, un ordinateur prendrait moins de temps pour déchiffrer une clé générée par l'homme que n'importe quel humain n'aurait jamais besoin de l'imaginer, et il n'est de toute façon pas rentable de générer des clés de cette manière. Pour cette raison, les clés ont tendance à être générées par un algorithme.

Un algorithme de génération de clé ne doit pas créer de sorties prévisibles / reproductibles à la suite d'une utilisation typique. Étant donné que les algorithmes exécutent des procédures sans aucun processus intelligent, la question est de savoir comment cela peut être fait. La réponse est de convertir les algorithmes de génération de clés en cartes qui transforment un grand nombre de bits vraiment aléatoires en clés. Des bits vraiment aléatoires peuvent être acquis à partir du système d'exploitation, ce qui les génère à partir de l'incertitude de l'univers. Certaines sources seraient le mouvement de la souris, les latences des paquets réseau ou même du matériel dédié, selon l'application.

---

Cryptosystèmes à clé publique

Préparez-vous à être surpris une fois de plus, car nous allons maintenant introduire un concept qui contredit apparemment ce que nous venons de dire: la clé publique.

Jusqu'à présent, nous avons vu la création d'une communication sécurisée après que les paramètres secrets (clés) ont été échangés en toute sécurité, mais le problème de l'échange des paramètres via un canal public demeure. À ce stade, nous allons introduire un concept qui résout un problème légèrement plus palpable: la création d'un canal sécurisé.

Disons qu'Alice travaille avec Bob et qu'ils souhaitent protéger leurs interactions professionnelles grâce au cryptage. Ils peuvent trouver et échanger leurs clés de cryptage en remettant une clé USB avec leurs clés. Mais que se passe-t-il si Alice et Bob sont situés sur des continents différents? Comment établir un canal sécurisé là où il n'y en a pas?

L'envoi de clés par e-mail ne serait pas une option, puisque son concurrent Eve peut intercepter l'échange et utiliser ses clés pour lire toutes les données cryptées ultérieurement. S'ils disposaient d'un autre canal numérique par lequel ils pouvaient transmettre ces informations sensibles, ils n'auraient pas besoin du cryptage et donc des clés en premier lieu. L'envoi de la clé par courrier physique pourrait également être intercepté, car dans un premier temps, il est nécessaire d'échanger des informations confidentielles. Envoyer un Clé stegangraphiée cachée dans d'autres données ce serait intelligent, mais inutile à moins que l'expéditeur ne soit sûr que le destinataire, et le destinataire seul, est conscient de l'existence d'un tel message et sait comment l'extraire. Il se trouve que la prise de conscience de l'existence d'un message avec la description de la façon d'extraire la clé des données est un type de clé en soi, ce qui nous ramène au point de départ.

La solution consiste à concevoir un cryptosystème pour lequel le paramètre de cryptage n'est pas suffisant pour interpréter de manière réalisable le message d'origine. ^[un] , et en gardant pour vous le paramètre qui vous permettrait d'interpréter le message. Nous appelons ce paramètre la clé privée. Sur la base de la clé privée, il est possible de générer un ensemble de paramètres pour un outil de cryptage sans que ces nouveaux paramètres révèlent ce qu'est la clé privée. Cet ensemble de paramètres peut être partagé publiquement, car il n'est pas si important de chiffrer quelque chose, tant qu'une seule personne peut le déchiffrer. Étant donné que cet ensemble de paramètres pour l'outil de chiffrement peut être rendu public, il est appelé une clé publique.

La cryptographie où les clés de cryptage et de décryptage diffèrent, et la première ne peut pas être utilisée pour déduire la seconde, est appelée cryptographie asymétrique, tandis que la cryptographie symétrique est ce que nous avons lorsque ces clés sont identiques ou facilement déduites les unes des autres. Alice envoie à Bob sa clé publique, qui ne peut être utilisée que pour chiffrer des choses qu'elle seule peut déchiffrer (avec sa clé privée, qu'elle garde privée) et, inversement, Bob envoie à Alice sa clé publique, qui ne peut être utilisée que pour chiffrer des choses que lui seul peut déchiffrer (en utilisant sa clé privée, qu'il garde également privée). Mais comment publier un paramètre pour un algorithme de chiffrement duquel l'algorithme inverse exact ne peut pas être déduit?

La réponse réside dans le domaine des mathématiques plus lié à la programmation, théorie de la complexité computationnelle . Quiconque s'est plongé suffisamment dans les problèmes de mathématiques a entendu parler de transformations faciles à faire dans un sens, mais difficiles à faire dans l'autre sens. En calcul, par exemple, trouver un dérivé d'un manuel est généralement un exercice simple, tout en faisant l'inverse (comme résoudre une partie physique ou un manuel physique légèrement non trivial ODE ou PDE , par exemple) nécessite un processus plus exploratoire de la première hypothèse de familles de fonctions qui sont garanties (ou du moins plausibles) pour contenir la (les) solution (s) et résoudre les problèmes inverses pour trouver des solutions de ces familles.

Un exemple qui est effectivement utilisé dans le Cryptosystème RSA multiplie les grands nombres premiers au lieu de factoriser le produit résultant sans connaître les facteurs. Faire la multiplication est trivial, mais l'affacturage nécessite cela au hasard ^[2] devinez les facteurs premiers, qui ont des centaines de chiffres. Une propriété importante de l'opération est la nécessité de bien évoluer. L'ajout de quelques chiffres sur la taille des nombres premiers dans RSA se traduira par une clé qui nécessite des milliers d'opérations supplémentaires pour déchiffrer et ajoute une petite augmentation de la complexité du processus de cryptage. De manière générale, le produit des nombres premiers est utilisé pour le chiffrement, tandis que la paire de facteurs premiers est utilisée pour le déchiffrement.

Avec tout cela à l'esprit, voyons comment fonctionne le système cryptographique SRVB.

L'algorithme sous-jacent: examinez SRVB

Le problème de la somme des sous-ensembles

Comme tout autre cryptosystème à clé publique, SRVB repose sur la difficulté de résoudre un problème particulier qui est facile à produire. Dans le cas de SRVB, c'est le Problème de somme de sous-ensemble , qui peut être décrite comme suit:

Dado el entero $ w $ et $ v_1, cdot cdot cdot, v_N in Z $ encuentra la secuencia $ b_1, cdot cdot cdot, b_N in {0,1} $, tel que $ sum_ {i = 1} ^ {N} v_i b_i = w $.

De toute évidence, ce problème peut se produire en sélectionnant au hasard N entiers, en choisissant au hasard un sous-ensemble d'entre eux et en résumant ce sous-ensemble, ce qui est trivial.

Une recherche par force brute aurait une complexité de $ O (N * 2 ^ N) $, calculant pour chaque combinaison de valeurs de $ b $ s. Une approche plus efficace a été donnée par Horowitz et Sahni en 1972 , avec une complexité de O (N * 2N / 2). Le problème est au moins aussi difficile si on remplace les $ b $ s et $ w $ par des vecteurs de dimensions entiers $ k $. Cependant, la portée où ce problème plus difficile doit être réalisé doit également avoir une isomorphisme avec un [ring] (https://en.wikipedia.org / wiki / Ring_ (math)) où une version plus simple du même problème est effectuée, comme nous le verrons plus loin. Pour cette raison, SRVB exploite le problème de la somme des sous-ensembles dans Entiers gaussiens , où $ k = 2 $ ..

Il existe un cas particulier où ce problème est facile à calculer en utilisant un algorithme glouton. Si nous ordonnons une séquence de facteurs d'échelle $ v_1, cdot cdot cdot, v_N $ dans laquelle chaque entier de la séquence est supérieur à la somme de tous les entiers qui l'ont précédé ($ forall i, sum_ {j = 1 } ^ {i-1} v_jséquence de grossissement excessif .

Voici une description simple de la solution gourmande pour ce cas:

1. Il commence par $ i = N $, le facteur actuellement observé, et $ w '= w $, le reste de $ w $

2. Si le facteur d'échelle actuel est trop grand pour s'adapter au reste de $ w $, cela signifie que $ v_i> w '$, définissez $ b_i = 0 $ et passez à l'étape suivante. Sinon, nous savons que le facteur d'échelle doit être dans la séquence (puisque le reste des facteurs est inférieur à $ v_i $) et nous mettons donc $ b_i = 1 $.

   plan comptable des finances personnelles

3. $ w ’ Leftarrow w’ - v_i * b_i $, $ i Leftarrow i - 1 $. Si $ i> 0 $, vuelve al paso 2.

4. Vérifiez que, maintenant $ w '== 0 $, sinon le problème a été corrompu.

Cela fonctionne parce que nous savons que tous les multiplicateurs plus petits que celui actuellement observé ne peuvent pas couvrir collectivement autant de la (sous) somme $ w '$ que le multiplicateur actuel. Donc, si la somme restante est supérieure au facteur actuel, nous savons avec certitude que tous les facteurs suivants ensemble ne peuvent pas être résumés sans l'aide du facteur actuel. D'un autre côté, puisque tous les multiplicateurs sont positifs, si le facteur courant $ v_i $ est supérieur à la somme restante $ w '$, l'ajout de tout autre facteur ferait en sorte que le résultat dépasse encore plus $ w' $.

Nous allons mettre en place une annotation pour le reste de l'article. On choisit $ v_1, cdot cdot cdot, v_n $ et $ w $ pour être les facteurs et la somme de la séquence de surincrément, tandis que $ u_1, cdot cdot cdot, u_n $ et $ y $ seront The Les paramètres publics disponibles sont fournis pour récupérer $ b_1, cdot cdot cdot, b_n $.

Avec une séquence $ u_1, cdot cdot cdot, u_n $ choisie pour ne pas être super génial, et le nombre $ y $ est disponible publiquement, pas assez d'informations sont fournies publiquement pour récupérer la séquence $ b_1, cdot cdot cdot, b_n $. Cependant, s'il existe une séquence super impressionnante $ v_1, cdot cdot cdot, v_n $ qui pourrait remplacer la séquence $ u_1, cdot cdot cdot, u_n $, cette séquence pourrait être utilisée pour résoudre le problème avec une approche gourmande.

Nous allons montrer comment cela fonctionne ci-dessous.

Utilisation de sommes de sous-ensembles dans un ancien cryptosystème

Dans 1978, Ralph Merkle et Martin Helman , ils ont imaginé un moyen d'exploiter ces deux paradigmes de sac à dos et le linéarité du fonctionnement du module pour établir la connexion entre les deux séquences décrites dans la section précédente, concevant ainsi un Cryptosystème à Clé Publique. L'idée était de transformer le sac à dos facile (celui qui est constitué du vecteur super croissant des entiers) dans le dur (celui qui n'a pas cette propriété) au moyen d'une opération linéaire (le module) avec des opérandes secrets. La transformation consiste à multiplier chaque $ v_i $ par à $ theta $ et à prendre le reste de ce produit par un $ alpha $, où $ alpha gt sum_ {i = 1} ^ N v_i $ et $ gcd ( alpha, theta) = 1 $ (deux contraintes qui seront bientôt justifiées). Le résultat, la séquence $ u_1, ldots, u_N $, n'augmente plus, et peut être considérée comme un sac à dos difficile .

Une permutation aléatoire de la séquence $ u_1, ldots, u_N $ serait donnée à la partie qui veut chiffrer et nous envoyer un message. La permutation est effectuée de sorte qu'un tiers ait du mal à deviner quelle est la séquence de super-augmentation d'origine. Les blocs de bits d'un message sont utilisés comme coefficients $ b_1, ldots, b_N $. Le chiffrement se fait en multipliant la séquence de clés avec cette séquence de coefficients, et en ajoutant les multiplications dans un résultat, que nous devons étiqueter $ et $. Seul le propriétaire de la clé privée peut transformer $ y $ en $ w $ correspondant qui serait obtenu si les mêmes blocs $ b_1, ldots, b_N $ étaient multipliés par entiers faciles (la séquence $ v_1, ldots, v_N $). Cela se fait en multipliant $ y $ par $ theta ^ {- 1} $, le multiplicatif inverse de $ theta $ module $ alpha $ (dont l'existence dépend de cette condition de $ gcd ( alpha, theta) = 1 $). En d'autres termes, $ ( theta * theta ^ {- 1}) bmod alpha = 1 $. Après cela, nous calculons $ w = (y * theta ^ {- 1}) bmod a $. La raison pour laquelle cela fonctionne est la linéarité du module , c'est-à-dire que la combinaison linéaire des résidus est égale au reste de la combinaison linéaire.

Si nous appliquons consécutivement la définition de $ u $, l'anneau de quotient et la propriété de linéarité de l'opérateur module, nous voyons la correspondance:

$ begin {align} y & = sum_ {i = 1} ^ N b_iu_i newline & = sum_ {i = 1} ^ N b_i (v_i * theta bmod alpha) newline & = sum_ { i = 1} ^ N b_i * v_i * theta bmod alpha newline & = left [ sum_ {i = 1} ^ N b_i * v_i * theta right] bmod alpha newline & = gauche [ sum_ {i = 1} ^ N b_i * v_i right] * theta bmod alpha newline & = w * theta bmod alpha end {align} $

Et ainsi le la somme facile $ w $ peut être récupéré en multipliant les deux côtés avec $ theta ^ {- 1} $ et en prenant le module avec $ alpha $. Pour ce faire, il faut connaître à la fois $ alpha $ et $ theta $ (qui permettent de calculer facilement $ theta ^ {- 1} $), qui doivent rester privées en tant que parties de la clé privée.

Une seule restriction, $ alpha gt sum_ {i = 1} ^ N v_i $, n'était pas justifiée et voici l'explication: l'égalité entre la deuxième et la troisième ligne consiste en une égalité entre types de déchets du anneau de quotient des entiers modulo $ alpha $. En d'autres termes, il ne définit l'égalité du reste des membres que lors de la division par $ alpha $, ce qui n'est pas une condition suffisante pour l'égalité des membres . En conséquence, plus d'un vecteur de valeurs $ b $ pourraient être mappés à un seul $ y $, ce qui est évité en limitant $ w $ à moins de $ alpha $ pour toute combinaison de valeurs $ b $.

Comme tout autre exemple de la vie quotidienne, la pleine connaissance de toutes les hypothèses est souvent impossible et jamais facile. Par conséquent, nous devons nous fier à l'intuition mathématique pour juger de la sécurité d'utilisation d'un système cryptographique, ce qui ne nous offre pas de réelles garanties. Six ans après sa création, le cryptosystème MH a rompu avec un attaque pour A. Shamir . Il y a eu plusieurs autres tentatives de relance de MH, dont beaucoup ont également échoué.

---

Cryptosystème Santana Rocha - Villas Boas (SRVB)

En 2016, après un brainstorming avec l'auteur de cet article sur le ^[3] Inspiré des possibilités d'un cryptosystème, Daniel Santana Rocha a eu l'idée de substituer $ theta $ et $ alpha $ aux entiers gaussiens. Pour des raisons plus techniques, cette approche conduit à une résistance contre l'attaque précitée de Shamir.

Il a également conçu un bloc de bits composé de nombreuses étapes de la combinaison linéaire précédemment décrite d'un napa dura . Dans chacun d'eux, un nouvel entier (gaussien), équivalent à un, supérieur à la somme de tous les précédents serait ajouté à la fin de la séquence, tandis que le plus petit nombre serait éliminé.

Une contrainte différente mais élégamment analogue s'applique pour $ alpha $, qui est maintenant un entier gaussien. Nous avons besoin pour $ w leq vert alpha vert ^ 2 $, où $ w $ est, encore une fois, la combinaison linéaire la plus élevée des entiers naturels dans le sac à dos facile. La raison est très difficile à formaliser, mais heureusement, elle peut être facilement devinée à partir d'une description élégante:

Imaginez un réseau carré dans le plan des nombres complexes, dont le côté est une hypoténuse d'un triangle rectangle de jambes a et b, parallèles aux axes réel et imaginaire. Un exemple d'un tel réseau est donné ci-dessous. Les entiers guassiens modulo $ alpha = a + bi $ peuvent être représentés par des points situés dans ledit réseau. Dans ce réseau, il y a $ vert alpha vert ^ 2 $ points différents. Si nous choisissons un $ alpha $ assez grand, nous pouvons adapter toutes les combinaisons linéaires du sac à dos facile. Nous définissons donc une exigence pour $ w leftarrow vert alpha vert ^ 2 $, où w est [comme décrit].

C'est la représentation graphique de l'isomorphisme $ f: Z / n rightarrow Z [i] / ( alpha) $, où $ n = 13 $ et $ alpha = a + bi = 3 + 2i $ (notez que $ n $ et $ alpha $ satisfont en fait $ n = vert alpha vert ^ 2 = a ^ 2 + b ^ 2 $ comme requis). Les points représentent les entiers gaussiens, c'est-à-dire les nombres complexes $ a + bi $, où $ a $ et $ b $ sont des entiers. Comme d'habitude, l'axe horizontal représente la partie réelle, tandis que la verticale représente la partie imaginaire. Par conséquent, déplacer un point vers la droite ou vers la gauche équivaut à ajouter respectivement +1 ou -1 à sa valeur actuelle. De même, déplacer un point vers le haut ou vers le bas équivaut à ajouter respectivement + i ou -i.

Les points rouges sont équivalents à $ 0 bmod ( alpha) $. En plus de cela, nous colorons également 4 paires de points supplémentaires.

Couleur	Équivalent à… mod α
Orange	1 $
vert	$ i $
Bleu	-1 $-i $
Violet	1 $-i $

L'isomorphisme $ f $ est défini par la transformation du $ i $ ème élément de la séquence cyclique $ (0,1,2, cdot cdot cdot, 10,11,12,0,1,2, cdot cdot cdot) $ dans le $ i $ ème élément de la séquence également cyclique de points de la figure, qui respecte les règles suivantes:

1. Commencez par le point rouge de la première rangée;
2. Suivez les flèches horizontales de droite; excepté
3. En suivant les flèches, la séquence sort du treillis, elle atteindra l'un des points non noirs. Au lieu d'aller à ce point, il saute au même point coloré (c'est-à-dire au module de point équivalent $ alpha $) dans le même carré; et finalement
4. Lorsque ce point non noir devient rouge (ce qui se produit après que toutes les autres couleurs sont passées), la séquence saute au point rouge supérieur, redémarrant ainsi le cycle;

Pour mapper au moins $ Y $ entiers naturels, prenez un carré avec l'aire $ vert alpha vert ^ 2 $ (où $ vert alpha vert = sqrt {a ^ 2 + b ^ 2} $ est par théorème de Pythagore , la mesure de votre côté) au moins aussi haut.

Notez que chaque 'saut' change le numéro de ligne $ r $ en $ r leftarrow (r + b) (mod a + b) $ si l'on compte les lignes de haut en bas, et, de manière équivalente, en $ r leftarrow ( r + a) (mod a + b) $ si on compte de bas en haut. Par conséquent, la condition nécessaire et suffisante pour que chaque ligne (et point) soit parcourue exactement une fois dans chaque cycle est que la taille des sauts soit en premier avec le nombre de lignes, ou, en d'autres termes, $ gcd (a, a + b) = pgcd (b, a + b) = 1 $. En raison des propriétés du plus grand opérateur diviseur commun, les deux sont équivalents à $ gcd (a, b) = 1 $.

Y. S. Villas Boas a noté le besoin de coprimités $ a $ et $ b $. Pour préserver le surincrément, chaque nouvel entier $ w $ ajouté à la fin de la séquence doit dépasser la somme de tous les nombres courants ($ w> sum_ {i = 1} ^ k v_i $). Vous avez observé que pour y parvenir, vos coefficients de multiplication $ b_i $ devraient être d'au moins 1, et donc chaque bit ne pourrait pas être mappé aux coefficients 0 et 1. Si les coefficients étaient 0 et 1, seul le bloc composite pour un seul satisferait le super incrément. Pour cette raison, les bits 0 et 1 ont été respectivement mappés aux coefficients de multiplication 1 et 2.

convertir l'horodatage en javascript de date

Enfin, et de manière moins triviale: à chaque étape de décodage, un nouvel entier $ v_1 $ est trouvé comme solution à l'équation $ b_1 v_1 = v_ {n + 1} - sum_ {i = 2} ^ {n} b_i v_i $, où tous les $ v_i $ et $ b_i $ sont connus par $ 1

Une dernière technicité à résoudre est le cas où la taille du message en octets n'est pas un multiple de la taille du bloc. En d'autres termes, que faire avec les octets restants possibles du dernier bloc de données pour que, une fois les blocs de données récupérés, tous les octets du contenu d'origine soient préservés, mais pas plus qu'eux? Nous l'avons résolu en répétant une fois le dernier octet du message. Cette copie est ensuite suivie d'une séquence aléatoire dans laquelle chaque composant ne doit être différent que du précédent. Par conséquent, lorsque les blocs de données sont récupérés, le dernier d'entre eux ou, dans le pire des cas, celui avant le dernier il est tronqué à la dernière répétition d'octet. ^[4]

Nous allons maintenant montrer un exemple du système cryptographique SRVB.

Nous commençons par les paramètres:

$ k = 4 $;

$ m = 4 $;

qui produit une longueur de bloc de $ l = 4 * 4 = 16 $ et une séquence super incroyable de $ k + 1 = 5 $ entiers naturels, qui est opérée —_ c'est-à-dire combinée linéairement, avec le résultat de cette combinaison linéaire , et réduit à ses k + 1 derniers éléments _— m = 4 fois;

Par souci de simplicité, soit le vecteur (super-incroyable) de $ v_i $:

(1, 2, 4, 8, 16) $

En fait, la séquence des cinq premières puissances de 2, simplement parce que c'est la séquence super impressionnante avec cinq éléments et les valeurs strictement les plus petites possibles (évitant ainsi un 0 dans la clé publique, qui céderait trivialement au 0 de son homologue correspondant)

Comme nous l'avons dit précédemment, pour $ alpha = a + bi $, les entiers $ a $ et $ b $ doivent être premiers, et selon la nouvelle restriction mentionnée, nous devons demander que $ a ^ 2 + b ^ 2 = vert alpha vert ^ 2 geq W $. Un calcul rapide produit W $ = 1 590 $. Puisque $ sqrt {1590} simeq 39.8 $, un $ alpha $ très pratique à choisir serait $ alpha = 39 + 40i $, car il est assez grand pour accueillir un isomorphisme avec un anneau d'entiers d'au moins 1590 composants, tout en satisfaisant également $ gcd (a, b) = 1 $. Aussi, il faut choisir $ theta $ tel que $ gcd (a, theta) = 1 $ ^[5] et de préférence pas trop bas, donc $ (a_1 * theta) \% alpha neq v_1 * theta $, (également pour éviter de donner des informations). $ theta = 60 $ fait le travail, produisant:

-19-1i, 1 + 38i, 3-3i, 6-6i, 12-12i $ ^[6]

Mettons-nous les mains sales, alors. Prenez le message b. Tout d'abord, nous le mappons à un tableau d'octets selon [ASCII] (https://en.wikipedia.org/wiki/ASCII#8-bit_codes) et notre convention pour tronquer les blocs de données:

Hola ApeeScape!

Puisque notre bloc de données est de 16 bits = 2 octets de long et que notre message fait 13 caractères, nous nous retrouvons avec 7 blocs de données de 2 octets chacun, où le dernier contient deux fois la représentation binaire du caractère «!». Nous allons crypter le premier bloc étape par étape. Faites très attention car les bits de chaque octet sont pris dans l'ordre de leur importance.

M $ = 01001000 01100101 $

• Première bouchée du premier octet: $ (0,0,0,1) rightarrow (1,1,1,1,2) cdot (-19-1i, 1 + 38i, 3-3i, 6-6i, 12 -12i) = 15 + 4i $
• Deuxième quartet du premier octet: $ (0,0,1,0) rightarrow (1,1,1,2,1) cdot (1 + 38i, 3-3i, 6-6i, 12-12i, 15 + 4) = 49 + 9i $
• Première bouchée du premier octet: $ (0,1,0,0) rightarrow (1,1,2,1,2) cdot (3-3i, 6-6i, 12-12i, 15 + 4i, 49 + 9i) = 106-10i $
• Segundo nibble del octet d'amorce: $ (0,1,1,0) rightarrow (1,1,2,2,1) cdot (6-6i, 12-12i, 15 + 4i, 49 + 9i, 106- 10i) = 252-2i $

Et donc nous venons de cartographier

«Il» $ Flèche droite (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) $

Le reste du message chiffré est le suivant:

'Ll' $ Flèche droite (12-12i, 21-2i, 61-3i, 185-31i, 367-59i) $

'O' $ Flèche droite (12-12i, 25 + 33i, 65 + 32i, 111 + 44i, 244 + 124i) $

'Vers' $ Flèche droite (12-12i, 9 + 10i, 46 + 12i, 149 + 5i, 277 + 31i) $

'Pt' $ Flèche droite (12-12i, 3 + 16i, 46 + 12i, 73 + 23i, 201 + 49i) $

'Al' $ Flèche droite (12-12i, 4 + 54i, 44 + 53i, 117 + 193i, 231 + 389i) $

'!!' $ Flèche droite (12-12i, 4 + 54i, 32 + 65i, 63 + 92i, 121 + 247i) $

Maintenant, pour le décryptage, nous avons $ theta ^ {- 1} = 60 ^ {- 1} = 27 + i $:

$ ($ 'He' $ Rightarrow) $ $ (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) * theta ^ {- 1} \% alpha = (16,47 , 93 223 527) $

Maintenant, vient l'algorithme glouton:

Tout d'abord, nous soustrayons chaque facteur contributif multiplié par un, car on sait qu'ils ont contribué au moins une fois au dernier, ce qui a abouti à:

• Deuxième quartet du deuxième octet:

$ T gauchearrow (527-233-93-47-16) = 148 $

$ (T geq 223) = (148 geq 223) = false Rightarrow b_1 = 0; T flèche gauche (T - 0 * 223) = 148 $

$ (T geq 93) = (148 geq 93) = true Rightarrow b_2 = 1; T flèche gauche (T - 1 * 93) = 55 $

$ (T geq 47) = 55 geq 47) = true Rightarrow b_3 = 1; T flèche gauche (T - 1 * 47) = 8 $

dans quoi sont écrits les systèmes d'exploitation

$ (T geq 16) = 8 geq 16) = false Rightarrow b_4 = 0; T flèche gauche (T - 0 * 16) = 8 $

Résultat: 0110;

Repos: 8 (ajouté au début de la séquence comme nouvel élément le plus bas);

Retirez le 527 de la fin de la séquence en cours;

• Première bouchée du deuxième octet:

$ T gauchearrow (233-93-47-16-8) = 59 $

$ (T geq 93) = (59 geq 93) = false Rightarrow b_1 = 0; T flèche gauche (T - 0 * 93) = 59 $

$ (T geq 47) = (59 geq 47) = true Rightarrow b_2 = 1; T flèche gauche (T - 1 * 47) = 12 $

$ (T geq 16) = (12 geq 16) = false Rightarrow b_3 = 0; T flèche gauche (T - 0 8 16) = 12 $

$ (T geq 8) = (12 geq 8) = true Rightarrow b_4 = 1; T flèche gauche (T - 0 * 12) = 4 $

Résultat: 0101;

Restant: 4 (ajouté au début de la séquence comme nouvel élément le plus bas);

Laissez 233 à partir de la fin de la séquence en cours;

• Deuxième quartet du premier octet:

$ T flèche gauche (93 - 47 - 16 - 8 - 4) = 18 $

$ (T geq 47) = (18 geq 47) = false Rightarrow b_1 = 0; T flèche gauche (T - 0 * 47) = 18 $

$ (T geq 16) = (18 geq 16) = true Rightarrow b_2 = 1; T flèche gauche (T - 1 * 16) = 2 $

$ (T geq 8) = (2 geq 8) = false Rightarrow b_3 = 0; T flèche gauche (T - 0 * 8) = 2 $

$ (T geq 4) = (2 geq 4) = false Rightarrow b_4 = 0; T flèche gauche (T - 0 * 4) = 2 $

Résultat: 0100;

Reste: 2 (ajouté au début de la séquence comme nouvel élément le plus bas);

Supprimez 93 à partir de la fin de la séquence en cours;

• Première bouchée du premier octet:

$ T flèche gauche (47-16-8-4-2) = 17 $

$ (T geq 16) = (17 geq 16) = true Rightarrow b_1 = 1; T flèche gauche (T - 1 * 16) = 1 $

$ (T geq 8) = (1 geq 8) = false Rightarrow b_2 = 0; T flèche gauche (T - 0 * 8) = 1 $

$ (T geq 4) = (1 geq 4) = false Rightarrow b_3 = 0; T flèche gauche (T - 0 * 4) = 1 $

$ (T geq 2) = (1 geq 4) = false Rightarrow b_4 = 0; T leftarrow (T - 0 * 2) = 1 $

Résultat: 1000;

Repos: 1 (ajouté au début de la séquence comme nouvel élément le plus bas);

principes d'unité et de variété du design

Supprimer 47 à la fin de la séquence en cours;

En conséquence, nous avons récupéré le bloc de données: «01001000 01100101» qui contient les deux premiers caractères «He», de notre message. Non seulement cela, nous avons également récupéré avec succès notre séquence super impressionnante de clé privée $ (1,2,4,8,16) $.

Les autres cartes de blocs de données vont de la même manière.

---

Comparaison avec les principaux cryptosystèmes à clé publique

SRVB c'est:

1. Entièrement gratuit et public;

2. Considérablement plus simple et plus facile à comprendre et à mettre en œuvre que ETC ^[sept] ;

3. Abondant en clés et donc pratiquement sans frais, contrairement par exemple à RSA , qui est basé sur des nombres premiers, qui sont chers .

Nous pouvons maintenant résumer les vulnérabilités les plus probables. Comme SRVB descend de MH, il est facile de soupçonner qu'il serait vulnérable à une généralisation de [l'attaque de Shamir] (https://en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem#cite_note-2), ou certains autre qui le casse.L'auteur avait des raisons de croire que ce ne serait pas le cas, cela reste à confirmer (ce qui est très typique en ce qui concerne les cryptosystèmes).

---

Suivant?

Rocha a noté quelques généralisations pour les anneaux de quotient à utiliser, ce qui peut éventuellement conduire à une augmentation de la complexité de la cryptanalyse. Nous étudierons également ces possibilités.

Obscuration algébrique linéaire

Il se trouve que, lors du développement et de la documentation de SRVB, Villas Boas a proposé une autre approche pour améliorer le concept de clé publique pour le cryptosystème de sac à dos qui ne sera pas expliquée en détail dans ce document, afin que cet article ne soit pas trop long . et fastidieux, mais en voici un coup d'œil. Si vous ne pouvez pas le comprendre, ne vous inquiétez pas, restez à l'écoute pour notre prochain article, où nous entrerons plus précisément dans les détails: voir la somme $ et $ sous-ensemble, disons, $ N $ éléments en anneau de quotient $ u_i $ (qui correspondent isomorphiquement aux entiers positifs $ v_i $ de la séquence super croissante, comme précédemment) comme une multiplication d'un vecteur ligne de ces $ u_i $ par un vecteur colonne $ B $ (pour binaire ) de zéros et de uns ^[8] .

$ y = sum_ {i = 1} ^ n u_i b_i = (u_1, cdot cdot cdot, u_n) ^ T cdot (b_1, cdot cdot cdot, b_n) $ = UB,

où $ b_i dans {0,1} $

Imaginez maintenant qu'au lieu de ce vecteur de $ u_i $, vous avez, à gauche, une matrice V de $ n $ fois $ N $ (avec $ n [9] n par n matrice R à gauche, définissant la n par N matrice P:

P = RV

L'idée est que Bob utilise P comme nouvelle clé publique. En raison du caractère aléatoire de R, le vecteur

$ Y = PB = RV B = RW $

a les informations $ w $ obscurcies par le bruit dans d'autres lignes de V.Bob calcule également à l'avance et stocke le vecteur ligne S qui satisfait:

$ R ^ T S ^ T = e_1 $

Quand Alice envoie Y à Bob, il trouve SY, car:

$ SY = S (PB) = S ((RV) B) = SRVB = {e_1} ^ T R ^ {- 1} ((RV) B) = $

(pour l'instant uniquement les définitions)

quel langage de programmation linux utilise-t-il

$ {e_1} ^ T (V B) = {e_1} ^ T W = w $

(Maintenant, en exploitant le associativité pour annuler les Rs)

puis procède comme précédemment pour extraire le vecteur de $ b_i $ de $ w $ au moyen de l'algorithme glouton.

Donc, en un mot, l'obscuration algébrique linéaire exploite l'associativité de la multiplication matricielle (le fait que nous pourrions étendre les termes puis opérer leurs composants dans un nouvel ordre, tant que nous gardons la séquence de tous les opérandes de la séquence) pour Mélangez 'linéairement' puis filtrez (respectivement dans le cryptage et le décryptage) le bruit vers / depuis $ w $. Et dans le cas limite $ n = 1 $, le système revient élégamment à l'original selon l'approche de Rocha.

La campagne SRVB: un défi enrichissant

Comme expliqué ci-dessus, selon le principe de Kerckhoff, l'expérience montre que l'antiquité d'un cryptosystème ininterrompu publiquement connu est la principale source de sa fiabilité, bien plus que toute argumentation théorique des auteurs eux-mêmes, en dehors de toute autre chose, car preuve définitive de la l'efficacité des algorithmes n'est généralement pas disponible.

Et nous avons ici la belle opportunité de mettre ces concepts en pratique pour gagner un grand prix: conscients de ce fait, nous avons lancé le campagne mentionnée , qui est essentiellement un financement participatif. pour un prix attribué automatiquement au premier à casser un message. L'argent sera converti en bitcoins dans un portefeuille donné dont la clé privée sera cryptée et publiée sur SRVB afin que quiconque puisse le décrypter puisse simplement prendre l'argent de manière anonyme, sans poser de questions.

Merci

Cet article particulier et l'ensemble du projet SRVB Crypto en général ont reçu une aide précieuse du Prof. Charles F. de Barros , professeur assistant à l '[Université fédérale de São João Del Rei] (http://www.ufsj.edu.br/). Le professeur Barros nous a présenté un examen technique du cryptosystème SRVB lui-même. Je pensais qu'il fallait soumettre avant d'oser publier, et qu'il me faudrait certainement beaucoup plus de temps pour le faire moi-même.

De plus, je voudrais également exprimer ma profonde gratitude au professeur Adnan Ademovic pour son travail extraordinairement perspicace, réfléchi et patient en tant que rédacteur en chef de cette publication. Article.

---

Glossaire

1. Cryptologie / Cryptographie: La science / pratique consistant à rendre un message presque impossible à interpréter sans un ensemble d'instructions spécifiques (dans ce contexte, la soi-disant «clé»), permettant aux agents qui partagent ces instructions de communiquer en toute sécurité même s'ils sont interceptés par des tiers;
2. Stéganographie: La science / pratique consistant à cacher un message dans un autre en ajoutant des modifications apparemment inoffensives à ce dernier;
3. Génération de clé: mappage des entrées aléatoires (attendues) sur des clés valides (aléatoires);
4. Cryptage / Encodage: Le mappage facilement calculable d'un message facilement interprétable dans un autre qui est difficile ou impossible à interpréter, en utilisant un élément (tel que spécifié au hasard) celui correspondant à la clé d'une famille d'algorithmes (selon le principe de Kerckhoffs) connue et validée publiquement;
5. Décryptage / décodage: Le mappage facilement calculable constitué de l'inverse de ce qui précède, peut également être défini par un élément (tel que spécifié au hasard, et donc inconnu et difficile à deviner par des tiers) _une fois, celui correspondant à la clé_ de a (par le même principe, généralement connu) famille d'algorithmes, qui de cette manière émet le message original lorsqu'il est saisi avec cryptage;
6. Cryptosystème: Une triade de la famille des algorithmes de codage, la famille des algorithmes de décryptage correspondants et un algorithme de génération de clé;
7. Alliés: Les agents auxquels la communication est destinée et qui sont censés agir conformément aux règles du protocole;
8. Ennemis / Tiers: Les agents avec qui la communication n'est pas prévue, mais qui essaient néanmoins d'écouter la communication et de contourner la sécurité renforcée par le cryptosystème;
9. Canal sûr: Tout protocole (procédure) de communication facile à utiliser et qui empêche en même temps des tiers d'interpréter de manière viable ce que veulent dire leurs utilisateurs.
10. Canal non sécurisé: tout canal (c'est-à-dire protocole ou procédure) qui, comme son nom l'indique, n'est pas un canal sécurisé;
11. Briser une clé: Processus de découverte d'une clé à l'aide d'informations publiques (telles qu'un message chiffré ou une clé publique) autres que la clé elle-même à découvrir et qui ne devraient pas permettre la découverte de la clé. Comme les informations qui résultent de ce processus autorisent le décryptage des messages, il s'agit d'un cas particulier de ...
12. Casser / décrypter un message: Tout moyen de déduire le contenu original d'un message crypté uniquement au moyen du message crypté lui-même et d'autres informations dont on ne pensait pas qu'elles suffiraient à la déduction du contenu original;
13. Briser un cryptosystème: Découverte d'un moyen systématique de casser tout message crypté par cette méthode sous n'importe quel paramètre de manière faisable;
14. Principe / Desideratum / Axiom / Loi de Kerckhoffs: Principe cryptologique du nom du cryptographe néerlandais. Auguste Kerckhoffs , selon lequel, pour qu'un cryptosystème soit considéré comme sécurisé, tout ce qui y est lié, à l'exception de ses clés (privées), doit être de notoriété publique;
15. Mot de passe: Paramétrage secret d'un cryptosystème qui lui permet d'être par inadvertance (et par conséquent interrompu) par des tiers tout en étant également validé par la communauté cryptanalyste (selon le principe de Kerckhoff);
16. Cryptosystème symétrique: Tout système de chiffrement dans lequel un paramètre de codage est suffisant pour en déduire facilement le paramètre de décodage et, pour cette raison, doit rester privé. On peut la reformuler en disant que les paramètres de chiffrement et de déchiffrement sont tous deux équivalents à la clé;
17. Symétrie / Clé publique du Cryptosystème: Tout cryptosystème pour lequel il existe un moyen d'exprimer les paramètres de codage qui n'est pas suffisant pour en déduire de manière faisable le paramètre correspondant pour le décodage, lui permettant d'être envoyé à des alliés via un canal non sécurisé, voire rendu public, etc. créer un environnement de canal sûr là où il n'y en avait pas;
18. Clé publique: Un composant d'un cryptosystème asymétrique qui est suffisant pour paramétrer le cryptage mais n'est pas suffisant pour en déduire de manière faisable le paramètre de décryptage, c'est-à-dire le ...
19. Clé privée: Un composant d'un cryptosystème asymétrique suffisant pour paramétrer le décryptage et doit donc rester privé et il suffit généralement également de paramétrer le cryptage;

---

^[un] Notez que les phrases ici déchiffrer ou déchiffrer ne s'appliquent pas, car avant qu'un cryptosystème donné (avec tous ses composants, y compris ses clés) soit bien défini, on ne peut pas classer une méthode donnée d'interprétation du message de cryptage d'origine comme une communication intentionnelle (décryptage) ou une attaque (décodée).

^[2] Bien qu'il existe des techniques pour améliorer ce travail de divination, il est encore beaucoup plus difficile à découvrir que de les multiplier.

^[3] La première inspiration a été de regarder le arbre de conjectures tau , un arbre infini enraciné dans le nombre 1, dont les autres nœuds sont constitués d'entiers qui se traduisent par une opération binaire d'addition, de soustraction ou de multiplication entre les nœuds précédents, éventuellement un nœud fonctionnant sur lui-même. Le but de la théorie concerne la profondeur, dans cet arbre, dans laquelle chaque entier apparaît pour la première fois. Il est apparemment difficile de trouver de grands nombres dans les branches inférieures (même si on assouplit la nécessité), mais il est immédiat de vérifier si une séquence donnée d'opérations produit effectivement un résultat donné.

^[4] Ce n'est sûrement pas l'approche la plus naturelle, mais en adoptant celle-ci, on s'assure que ce remplissage d'octets (appelé remplissage ) ...

1. Masque la taille du remplissage (différemment, par exemple, de vol de texte chiffré ) et masque la fin du message, représentant attaques en clair choisies plus difficile;
2. Améliorez la distribution des bits aussi près que possible de l'uniformité;

Si les derniers blocs de chaque message étaient connus pour être systématiquement biaisés dans une distribution loin d'être uniforme, un attaquant pourrait profiter de ce fait pour effectuer une cryptanalyse statistique, car tout échantillon donné de messages serait statistiquement plus représentatif qu'autrement. En d'autres termes, les derniers blocs sont statistiquement moins diversifiés, ils deviennent les maillons les plus faibles du message.

^[5] Ne vous y trompez pas: ce plus grand diviseur commun est gaussien, tandis que celui ci-dessus est réel.

^[6] ... ce qui n'est pas parfait, car cela révèle facilement le fait que les trois dernières composantes sont proportionnelles à 1, 2 et 4. Mais encore une fois, par souci de simplicité, nous ignorerons ce détail.

^[sept] ... qui est si complexe qu'il y en a cas notoires d'incapacité à mettre en œuvre et à maintenir des protocoles basés sur celui-ci .

^[8] Ici, nous ne prendrons pas l'approche de Rocha à un bloc de combinaisons linéaires multiples, ce qui nous permet également de permuter aléatoirement le rappel pour les rendre encore plus sombres.

^[9] Bien que pas totalement aléatoire. Sa transposition doit englober le sous-espace généré par le vecteur $ e_1 = (1,0,…, 0) $.