Premiers pas avec le cryptosystème SRVB

introduction

La sécurité de l'information est un domaine de connaissances fascinant qui peut impliquer tout, de l'informatique théorique au génie logiciel, et même observer la psychologie de l'erreur humaine.

La cryptographie fait désormais partie des nombreux héros technologiques anonymes de notre quotidien. Les réseaux sociaux, les services bancaires en ligne, le renseignement militaire et tout autre système d'information traitant des informations sensibles reposent tous fortement sur la cryptographie. La cryptographie nous permet d'avoir une vie privée, que certains considèrent comme le 12e droit de l'homme.

Cet article vous donnera une introduction aux principes des cryptosystèmes à clé publique et vous présentera le Santana Rocha-Villas Boas (SRVB), un cryptosystème développé par l'auteur de l'article et le professeur Daniel Santana Rocha. Au moment d'écrire ces lignes, les auteurs de l'algorithme préparent une campagne qui comprend une récompense financière pour quiconque parvient à déchiffrer le code. Étant donné que l'article couvrira en détail la fonctionnalité de l'algorithme, c'est le meilleur endroit pour commencer la poursuite du prix. Plus d'informations sont disponibles sur le site de la SRVB.

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

La cryptographie est toute méthode pour entraver l'interprétabilité d'un message, tout en permettant de l'interpréter de manière réaliste tant qu'une instruction spécifique est fournie, qui est généralement ce qu'on appelle la "clé". Bien qu'il s'agisse d'une définition très large qui englobe même les techniques les plus anciennes, il convient de mentionner qu'elle ne couvre pas tout ce qu'il y a à la sécurité de l'information.

La course technologique entre les méthodes de cryptage et les moyens de les casser ne devrait jamais avoir de vainqueur définitif. Chaque nouvelle génération devrait élever les normes de sécurité de l'information et de cryptanalyse, qui est l'ensemble des techniques pour déchiffrer/casser systématiquement les messages cryptés, c'est-à-dire contourner la sécurité ou le cryptage.

Pour qu'un cryptosystème (technique de cryptographie donnée) soit considéré comme sûr par ses utilisateurs, il doit recevoir l'approbation de la communauté internationale d'experts, et donc être connu du public, ce qui est connu sous le nom de principe de Kerckhoffs. Pourtant, 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 casser systématiquement les cryptages.

Comment rendre un processus de chiffrement donné suffisamment secret pour que seuls les agents prévus 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 chiffrement ou de déchiffrement, ou les deux. En gardant les paramètres secrets, plutôt que la famille d'algorithmes, les deux exigences contradictoires peuvent être satisfaites. À condition que la famille de paramètres soit suffisamment grande (éventuellement infinie) et que chacun de ses composants puisse être prouvé 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 facile à produire mais presque impossible à deviner. Avec la puissance de calcul des ordinateurs d'aujourd'hui, un ordinateur aurait besoin de moins de temps pour déchiffrer une clé générée par l'homme que n'importe quel humain n'en aurait besoin pour l'imaginer, en plus du fait qu'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 sortie prévisible/reproductible à 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 consiste à transformer les algorithmes de génération de clés en cartes qui transforment une grande quantité de bits véritablement aléatoires en clés. Des bits vraiment aléatoires peuvent être acquis à partir du système d'exploitation, qui les génère à partir de l'incertitude dans l'univers. Certaines sources pourraient être le mouvement de votre souris, les latences du package réseau ou même du matériel dédié, selon l'application.

Cryptosystèmes à clé publique

Préparez-vous à être encore une fois surpris, car nous allons maintenant introduire un concept qui semble contredire 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 des paramètres secrets (clés) ont été échangés en toute sécurité, mais le problème de l'échange des paramètres sur un canal public demeure. En ce moment, nous allons introduire un concept qui résout un problème un peu plus palpable : la création d'un canal sécurisé.

Supposons qu'Alice travaille avec Bob et qu'ils souhaitent sécuriser leurs interactions professionnelles à l'aide du cryptage. Ils peuvent se rencontrer et échanger leurs clés de cryptage en se donnant mutuellement une clé USB avec leurs clés dessus. 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, car leur concurrent Eve peut intercepter l'échange et utiliser ses clés pour lire toutes les données cryptées par la suite. S'ils disposaient d'un autre canal numérique par lequel ils pourraient transmettre ces données sensibles, ils n'auraient pas besoin de cryptage, et donc de clés, en premier lieu. L'envoi de la clé par courrier physique pourrait également être intercepté, car cela nécessite d'abord l'échange d'informations sensibles. Envoyer une clé stéganographiée en se cachant dans d'autres données serait astucieux, mais inutile à moins que l'expéditeur ne soit sûr que le destinataire, et lui seul, a connaissance de l'existence d'un tel message et sait comment l'extraire. En l'occurrence, la prise de conscience de l'existence d'un message ainsi que 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 à la case départ.

La solution est de concevoir un cryptosystème pour lequel le paramètre de cryptage n'est pas suffisant pour interpréter de manière réaliste le message d'origine ^[1] , et de garder pour soi le paramètre qui 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 chiffrement sans rendre ces nouveaux paramètres eux-mêmes capables de révéler ce qu'est la clé privée. Cet ensemble de paramètres peut être partagé publiquement, car peu importe qui peut 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, on l'appelle une clé publique.

La cryptographie où les clés de chiffrement et de déchiffrement diffèrent, et où 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 sont facilement déduites l'une de l'autre.

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 en privé) et, à l'inverse, Bob envoie à Alice sa clé publique, qui ne peut être utilisée que pour chiffrer des choses que lui seul peut déchiffrer (au moyen de sa clé privée, qu'il conserve également en privé). Mais comment peut-on éventuellement publier un paramètre pour un algorithme de chiffrement dont on ne puisse pas déduire l'algorithme inverse exact ?

La réponse se trouve dans le domaine des mathématiques qui est le plus proche de la programmation, la théorie de la complexité computationnelle. Quiconque s'est suffisamment penché sur les problèmes mathématiques a entendu parler de transformations faciles à faire dans un sens, mais difficiles à faire dans l'autre sens. En calcul, par exemple, trouver une dérivée de manuel est généralement un exercice simple, tandis que faire l'inverse (comme résoudre n'importe quel ODE ou PDE physique intégral ou manuel légèrement non trivial, par exemple) nécessite un processus plus approfondi consistant à émettre d'abord l'hypothèse de familles de fonctions qui sont garantis (ou du moins plausibles) pour contenir la ou les solutions et résoudre des problèmes inverses pour trouver des solutions à partir de ces familles.

Un exemple qui est réellement utilisé dans le cryptosystème RSA consiste à multiplier les grands nombres premiers par rapport à la factorisation du produit résultant sans déjà connaître les facteurs. Faire une multiplication est trivial, mais la factorisation vous oblige à deviner au hasard ^[2] les facteurs premiers, qui ont des centaines de chiffres. Une propriété importante de l'opération est la nécessité pour elle de bien évoluer. L'ajout de quelques chiffres à la taille des nombres premiers dans RSA se traduira par une clé qui nécessite des milliers de fois plus d'opérations pour se fissurer tout en ajoutant une petite augmentation de complexité au processus de chiffrement. Très grossièrement, le produit des nombres premiers sert au chiffrement, tandis que le couple de facteurs premiers sert au déchiffrement.

Avec tout cela à l'esprit, regardons comment fonctionne le cryptosystème SRVB.

L'algorithme sous-jacent - Regard sur SRVB

Le problème de la somme des sous-ensembles

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

Étant donné l'entier $w$ et $v_1, \cdot \cdot \cdot, v_N \in Z$ trouver la suite $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, telle que $ \sum_ {je = 1}^{N} v_i b_i = w $.

Clairement, ce problème peut être produit en choisissant au hasard N entiers, en choisissant au hasard un sous-ensemble d'entre eux et en additionnant ce sous-ensemble - ce qui est trivial.

Une recherche par force brute aurait une complexité de $ O( N * 2^N ) $, en calculant pour chaque combinaison de valeurs des $b$s. Une approche plus efficace a été donnée par Horowitz et Sahni en 1972, avec une complexité de $ O ( N * 2 ^ {N / 2} ) $. Le problème est au moins aussi difficile si nous remplaçons les $b$s et $w$ par des vecteurs d'entiers de $k$-dimensions. Le domaine où ce problème plus difficile doit être traité, cependant, doit également avoir un isomorphisme avec un anneau où une version plus facile du même problème a lieu, comme nous le verrons ci-dessous. Pour cette raison, SRVB exploite le problème de la somme des sous-ensembles dans les entiers gaussiens, où $ k = 2 $.

Il existe un cas particulier où ce problème devient facile à calculer grâce à l'utilisation d'un algorithme glouton. Si nous trions 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_j < v_i $), on pourrait utiliser une approche gloutonne pour trouver la séquence b en temps linéaire. Une suite avec les propriétés décrites est appelée une suite surcroissante .

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

1. Commencez 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 tenir dans ce qui reste de $w$, c'est-à-dire $ 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 définissons $b_i = 1$.

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. Si $i > 0$, retournez à l'étape 2.

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

Cela fonctionne parce que nous savons que tous les multiplicateurs plus petits que celui actuellement observé ne peuvent pas collectivement couvrir 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 ne pourront pas s'additionner sans l'aide du facteur actuel. D'autre part, puisque tous les multiplicateurs sont positifs, si le facteur actuel $ v_i $ est supérieur à la somme restante $ w' $, l'ajout de tout autre facteur ferait que le résultat dépasserait encore plus $ w' $.

Mettons en place une notation pour le reste de l'article. Nous choisissons $ v_1, \cdot \cdot \cdot, v_n $ et $w$ comme facteurs et somme de la suite supercroissante, tandis que $ u_1, \cdot \cdot \cdot, u_n $ et $y$ seront les paramètres disponibles qui 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 de sorte qu'elle ne soit pas surcroissante, et que le nombre $y$ soit publiquement disponible, 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 suite surcroissante $ v_1, \cdot \cdot \cdot, v_n $ qui pourrait prendre la place de la suite $ u_1, \cdot \cdot \cdot, u_n $, on pourrait utiliser cette suite pour résoudre le problème avec une approche gourmande.

Ci-dessous, nous allons montrer comment cela fonctionne.

Utilisation de sommes de sous-ensembles dans un cryptosystème précédent

En 1978, Ralph Merkle et Martin Helman ont imaginé un moyen d'exploiter ces deux paradigmes de sac à dos et la linéarité de l'opération de 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 constitué du vecteur surcroissant d'entiers) en dur (celui dépourvu de cette propriété) au moyen d'une opération linéaire (le module) à opérandes secrets. La transformation consiste à multiplier chaque $v_i$ par un $\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'est plus supercroissant et peut être considéré comme un sac à dos rigide .

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 faite pour qu'un tiers ait plus de mal à deviner quelle est la séquence supercroissante 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 par cette séquence de coefficients, et en additionnant les multiplications en un résultat, que nous appellerons $y$. Seul le propriétaire de la clé privée peut transformer $y$ en le $w$ correspondant qui serait obtenu si ces mêmes blocs $b_1, \ldots, b_N$ avaient été multipliés par les entiers simples (la séquence $v_1, \ldots , v_N$). Cela se fait en multipliant $y$ par $\theta^{-1}$, l'inverse multiplicatif de $\theta$ module $\alpha$ (dont l'existence dépend de cette condition de $\gcd(\alpha, \ thêta) = 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 est garanti de fonctionner est la linéarité du module , c'est-à-dire que la combinaison linéaire des restes est égale au reste de la combinaison linéaire.

Si nous appliquons consécutivement la définition de $u$, l'anneau 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 la somme facile $w$ peut être récupérée 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 être gardées privées en tant que parties de la clé privée.

Une seule contrainte, $\alpha \gt \sum_{i=1}^N v_i$, n'a pas été justifiée et en voici l'explication : l'égalité entre les deuxième et troisième lignes consiste en une égalité entre les classes résiduelles du quotient anneau d'entiers modulo $\alpha$. En d'autres termes, il indique uniquement l'égalité du reste des membres lorsqu'ils sont divisés par $\alpha$, ce qui n'est pas une condition suffisante pour l'égalité des membres eux-mêmes . En conséquence, plus d'un vecteur de valeurs $b$ pourrait être mappé dans un seul $y$, ce qui est empêché en limitant la sous-somme maximale possible (c'est-à-dire la somme de toutes les parcelles $v_i$) $w_{max}$ à être inférieur à $\alpha$ pour toute combinaison de valeurs $b$.

Comme tout autre exemple de la vie quotidienne, la connaissance complète de toutes les hypothèses est souvent impossible et jamais facile. En conséquence, nous devons nous fier à l'intuition mathématique pour juger si un cryptosystème est sûr à utiliser, ce qui ne nous fournit aucune garantie réelle. Six ans après sa création, le cryptosystème MH a été brisé par une attaque d'A. Shamir. Il y a eu plusieurs autres tentatives pour relancer MH, dont beaucoup ont également échoué.

Le cryptosystème Santana Rocha - Villas Boas (SRVB)

En 2016, après quelques brainstorms avec l'auteur de cet article sur les possibilités différemment inspirées ^[3] d'un cryptosystème, Daniel Santana Rocha a eu l'idée de substituer $\theta$ et $\alpha$ par des entiers gaussiens. Pour des raisons plus techniques, cette approche conduit à la résistance contre l'attaque Shamir susmentionnée.

Il a également conçu un bloc de bits composé de nombreuses étapes de la combinaison linéaire décrite précédemment d'un sac à dos rigide . 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 actuellement serait supprimé.

Une contrainte différente et pourtant élégamment analogue s'applique pour $\alpha$, qui est maintenant un entier gaussien. Nous avons besoin de $w_{max} \leq \vert\alpha\vert^2$. La raison est très difficile à formaliser, mais heureusement, elle peut être facilement devinée à partir d'une description élégante :

Imaginez un treillis carré dans le plan des nombres complexes, dont le côté est une hypoténuse d'un triangle rectangle de catheti a et b, parallèle 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 à l'intérieur d'un tel réseau. A l'intérieur d'un tel réseau, il y a $\vert\alpha\vert^2$ points distincts. Si nous choisissons un $\alpha$ suffisamment grand, nous pouvons ajuster toutes les combinaisons linéaires du sac à dos facile.

Ceci 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 bien $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. Ainsi, déplacer un point vers la droite ou la gauche équivaut à ajouter +1 ou -1 à sa valeur actuelle, respectivement. De même, déplacer un point vers le haut ou vers le bas correspond à l'ajout de +i ou -i, respectivement.

Les points rouges sont ces équivalents à $0 \bmod(\alpha)$. En dehors de ceux-ci, nous avons également colorié 4 autres paires de points.

L'isomorphisme $f$ est défini par la transformation du $i$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$ième élément de la séquence également cyclique de points de la figure, qui respecte les règles suivantes :

1. Il part du point rouge de la première ligne ;
2. Il suit les flèches droites horizontales ; excepté
3. Lorsque le fait de suivre les flèches mène la séquence à l'extérieur du réseau, elle atteindrait l'un des points non noirs. Au lieu d'aller à ce point, il saute au même point coloré (c'est-à-dire, le point équivalent modulo $\alpha$) à l'intérieur du même carré ; et enfin
4. Lorsque ce point non noir se trouve être rouge (ce qui se produit après que toutes les autres couleurs ont été traversées), la séquence saute au point rouge le plus haut, réinitialisant ainsi le cycle;

Pour mapper au moins $Y$ entiers naturels, il faut prendre un carré d'aire $\vert\alpha\vert^2$ (où $\vert\alpha\vert = \sqrt{a^2 + b^2} $ est, par le théorème de Pythagore, la mesure de son côté) au moins aussi élevé.

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 parcouru exactement une fois sur chaque cycle est que la taille des sauts soit première 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 de l'opérateur du plus grand diviseur commun, les deux sont équivalents à $gcd(a,b) = 1$.

YS Villas Boas a remarqué le besoin de coprimalité de $a$ et $b$. Afin de préserver le surcroissance, chaque nouvel entier $w$ ajouté à la fin de la séquence doit dépasser la somme de tous les entiers courants ($w > \sum_{i=1}^k v_i$). Il a observé que pour y parvenir, leurs coefficients multiplicateurs $b_i$ devraient être au moins 1, et donc, chaque bit ne pourrait pas être mappé dans les coefficients 0 et 1. Si les coefficients étaient 0 et 1, seul le bloc composé uniquement de uns satisferait le surcroissance. Pour cette raison, les bits 0 et 1 ont ensuite été mappés respectivement sur les coefficients multiplicateurs 1 et 2.

Enfin, et de manière moins triviale : lors de chaque étape du décodage, un nouvel entier $v_1$ est à trouver comme solution de 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 pour $1 < i \leq n$. Comme nous ne connaissons pas non plus $b_1$, nous nous retrouvons avec un système à une équation et deux variables, ce qui nous laisse un degré de liberté. Pour corriger cela, nous devons arbitrer une valeur positive (pour des raisons de simplicité, 1) pour qu'elle soit toujours affectée à $b_1$, éliminant ainsi l'ambiguïté. Ainsi, puisque le premier coefficient est fixé à 1, pour coder $n$ bits à chaque étape, nos séquences d'entiers doivent être longues de $n + 1$ éléments.

Un dernier point technique à résoudre est le cas où la taille en octets du message n'est pas un multiple de la taille du bloc. Autrement dit, que faire des éventuels octets restants 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 conservés, mais pas plus qu'eux ? Nous avons résolu cela en répétant une fois le dernier octet du message. Cette copie est alors suivie d'une séquence aléatoire sur laquelle chaque composant n'a qu'à être différent du précédent. Ainsi, lorsque les blocs de données sont récupérés, le dernier d'entre eux ou, dans le pire des cas, l'avant-dernier est tronqué dans la dernière répétition d'octets. ^[4]

Montrons maintenant un exemple du cryptosystème SRVB.

On commence par les paramètres :

$k = 4$ ;

$m = 4$ ;

ce qui donne une longueur de bloc de $l = 4 * 4 = 16$, et une suite supercroissante de $k + 1 = 5$ entiers naturels, qui est opérée— c'est-à -dire combinée linéairement, ajoutée au résultat de cette combinaison linéaire, et réduit à ses derniers $k + 1$ éléments —$m = 4$ fois ;

Par souci de simplicité, considérons le vecteur (surcroissant) suivant de $v_i$ :

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

En effet, la suite des cinq premières puissances de 2, justement parce que c'est la suite surcroissante à cinq éléments et les plus petites valeurs strictement positives possibles (évitant ainsi un 0 dans la clé publique, ce qui donnerait trivialement le correspondant 0 de son homologue ).

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

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

Mettons-nous les mains dans le cambouis, alors. Prenez le message Hello Toptal! . D'abord, nous le mappons dans un tableau d'octets selon ASCII et notre convention pour tronquer les blocs de données :

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

Puisque notre bloc de données est long de 16 bits = 2 octets et que notre message comporte 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 en bits du caractère '!' . Chiffrez 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$

• Premier quartet 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$
• Premier quartet du deuxième octet : $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Deuxième quartet du deuxième octet : $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

Et ainsi, nous venons de cartographier

"Il" $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

Le reste du message crypté est le suivant :

« ll » $\Rightarrow(12-12i,21-2i,61-3i,185-31i,367-59i)$

« o » $\Rightarrow(12-12i,25+33i,65+32i,111+44i,244+124i)$

« Vers » $\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

« pt » $\Rightarrow(12-12i,3+16i,46+12i,73+23i,201+49i)$

"al" $\Rightarrow(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échiffrement, nous avons $\theta^{-1}=60^{-1}=27+i$ :

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

Maintenant, vient l'algorithme gourmand :

Tout d'abord, nous soustrayons chaque facteur contributif multiplié par un, car ils sont connus pour avoir contribué au moins une fois pour le dernier, ce qui donne :

• Deuxième quartet du deuxième octet :

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

$(T \geq 223) = (148 \geq 223) = faux \Rightarrow b_1=0 ; T \leftarrow (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = vrai \Rightarrow b_2 = 1 ; T \leftarrow (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = vrai \Rightarrow b_3 = 1 ; T \leftarrow (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = faux \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 16) = 8$

Résultat : 0110 ;

Reste : 8 (ajouté au début de la séquence en tant que nouvel élément le plus bas) ;

Déposez 527 de la finale de la séquence actuelle ;

• Premier quartet du deuxième octet :

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

$(T \geq 93) = (59 \geq 93) = faux \Rightarrow b_1 = 0 ; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = vrai \Rightarrow b_2 = 1 ; T \leftarrow (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = faux \Rightarrow b_3 = 0 ; T \leftarrow (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = vrai \Rightarrow b_4 = 1 ; T \leftarrow (T - 0 * 12) = 4$

Résultat : 0101 ;

Reste : 4 (ajouté au début de la séquence en tant que nouvel élément le plus bas) ;

Drop 233 de la finale de la séquence actuelle ;

• Deuxième quartet du premier octet :

$T \leftarrow (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = faux \Rightarrow b_1 = 0 ; T \leftarrow (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = vrai \Rightarrow b_2 = 1 ; T \leftarrow (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = faux \Rightarrow b_3 = 0 ; T \leftarrow (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = faux \Rightarrow b_4 = 0 ; T \leftarrow (T - 0 * 4) = 2$

Résultat : 0100 ;

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

Drop 93 de la finale de la séquence actuelle ;

• Premier quartet du premier octet :

$T \leftarrow (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = vrai \Rightarrow b_1 = 1 ; T \leftarrow (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = faux \Rightarrow b_2 = 0 ; T \leftarrow (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = faux \Rightarrow b_3 = 0 ; T \leftarrow (T - 0 * 4) = 1$

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

Résultat : 1 000 ;

Reste : 1 (ajouté au début de la séquence en tant que nouvel élément le plus bas) ;

Drop 47 de la finale de la séquence actuelle ;

Du coup, nous avons récupéré le bloc de données : « 01001000 01100101 » contenant les deux premiers caractères « He », de notre message. Non seulement cela, nous avons également récupéré correctement notre séquence de superaugmentation de clé privée $(1,2,4,8,16)$.

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

Comparaison avec les principaux cryptosystèmes à clé publique

SRVB c'est :

1. Totalement gratuit et public ;

2. Considérablement plus simple et plus facile à comprendre et à mettre en œuvre que l'ECC ^[7] ;

3. Abondant en clés et donc quasiment sans coût, contrairement par exemple au RSA qui s'appuie sur des nombres premiers, qui sont chers.

Nous pouvons déjà résumer les vulnérabilités les plus probables. Étant donné que SRVB descend de MH, il est facile de soupçonner qu'il serait vulnérable à une généralisation de l'attaque de Shamir, ou à une autre qui la brise. Bien que l'auteur ait eu des raisons de croire que ce ne serait pas le cas, aucune confirmation n'a encore été faite (ce qui est très typique lorsqu'il s'agit de cryptosystèmes).

Et après?

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

L'obscurcissement algébrique linéaire

En l'occurrence, lors du développement et de la documentation de SRVB, Villas Boas a proposé une autre approche pour améliorer le concept de système de chiffrement à clé publique à dos qui ne sera pas expliquée en détail ici, afin que cet article ne devienne pas trop long. et fastidieux, mais en voici un survol. Si vous ne parvenez pas à le saisir, ne vous inquiétez pas, restez à l'écoute pour la sortie de notre prochain article, dans lequel nous entrerons plus en détail dans les détails : Voir la somme du sous-ensemble $y$, de, disons, $N$ éléments de l'anneau quotient $u_i$ (qui correspondent isomorphiquement aux entiers positifs $v_i$ de la suite super croissante, comme précédemment) comme une multiplication d'un vecteur ligne de ces $u_i$ par un vecteur colonne $B$ ( pour le 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 \in {0,1}$

Maintenant, imaginons qu'au lieu de ce vecteur de $u_i$, vous ayez, à gauche, une matrice V $n$ par $N$ (avec $n < N$), ayant les $v_i$ (les entiers du supercroissant séquence) vecteur comme (sans perte de généralité) sa première ligne et toutes les autres entrées remplies de bruit. Notez que, maintenant, multiplier V par le même vecteur de bits B vous donne un vecteur colonne W qui a $w$ comme première entrée et du bruit dans les autres. Maintenant, prenez cette matrice V et multipliez-la par une matrice aléatoire ^[9] n par n R sur la gauche, définissant la matrice n par N P :

P = VD

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 l'information $w$ masquée par le bruit dans d'autres lignes de V. Bob calcule également à l'avance et stocke le vecteur ligne S qui satisfait :

$R^TS^T = e_1$

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

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

(jusqu'à présent uniquement les définitions)

${e_1}^T (VB)={e_1}^TW = w$

(Maintenant, exploiter l'associativité pour annuler les R)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

Acknowledgments

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

Glossaire

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.