Erste Schritte mit dem SRVB-Kryptosystem

Einführung

Informationssicherheit ist ein faszinierendes Wissensgebiet, das alles von der theoretischen Informatik bis zum Software-Engineering umfassen und sogar die Psychologie des menschlichen Versagens beobachten kann.

Die Kryptographie ist heute einer der vielen anonymen technologischen Helden unseres täglichen Lebens. Soziale Netzwerke, Web-Banking, militärische Geheimdienste und alle anderen Informationssysteme, die mit sensiblen Informationen zu tun haben, verlassen sich alle stark auf Kryptografie. Kryptografie ermöglicht uns Privatsphäre, die manche als das 12. Menschenrecht betrachten.

Dieser Artikel gibt Ihnen eine Einführung in die Prinzipien hinter Public-Key-Kryptosystemen und stellt Ihnen Santana Rocha-Villas Boas (SRVB) vor, ein Kryptosystem, das vom Autor des Artikels und Prof. Daniel Santana Rocha entwickelt wurde. Während dies geschrieben wird, brauen die Autoren des Algorithmus eine Kampagne zusammen, die eine finanzielle Belohnung für jeden beinhaltet, der es schafft, den Code zu knacken. Da der Artikel die Algorithmusfunktionalität im Detail behandelt, ist dies der beste Ort, um mit der Jagd nach dem Preis zu beginnen. Weitere Informationen finden Sie auf der SRVB-Website.

Was ist ein Kryptosystem?

Kryptografie ist jede Methode, um die Interpretierbarkeit einer Nachricht zu behindern, während sie dennoch eine Möglichkeit bietet, sie zu interpretieren, solange eine bestimmte Anweisung bereitgestellt wird, die normalerweise der sogenannte „Schlüssel“ ist. Obwohl dies eine sehr weit gefasste Definition ist, die selbst die frühesten Techniken umfasst, sollte erwähnt werden, dass dies nicht alles abdeckt, was die Informationssicherheit zu bieten hat.

Der technologische Wettlauf zwischen Verschlüsselungsmethoden und Möglichkeiten, sie zu knacken, wird voraussichtlich nie einen endgültigen Gewinner haben. Von jeder neuen Generation wird erwartet, dass sie die Standards der Informationssicherheit und Kryptoanalyse anhebt, d. h. eine Reihe von Techniken zum systematischen Entschlüsseln/Brechen verschlüsselter Nachrichten, dh zum Umgehen der Sicherheit oder Verschlüsselung.

Damit ein Kryptosystem (eine bestimmte Technik der Kryptographie) von seinen Benutzern als sicher angesehen wird, muss es die Zustimmung der internationalen Expertengemeinschaft erhalten und damit öffentlich bekannt sein, was als Kerckhoffs-Prinzip bekannt ist. Doch genau diese Bedingung setzt das System der Prüfung durch die weltweite Kryptoanalyse-Community aus, die versuchen wird, Wege zu finden, um die Verschlüsselungen systematisch zu knacken.

Wie kann man einen bestimmten Verschlüsselungsprozess geheim genug machen, dass nur die vorgesehenen Agenten ihn entschlüsseln können, und gleichzeitig öffentlich genug, dass die weltweite Kryptoanalyse-Community seine Robustheit bestätigen kann? Die Antwort ist eine Komponente, die ein Schlüsselelement der Kryptologie ist: der Schlüssel. Ein Schlüssel eines Kryptosystems ist ein Parameter für entweder den Verschlüsselungs- oder den Entschlüsselungsalgorithmus oder beide. Indem die Parameter geheim gehalten werden und nicht die Algorithmusfamilie, können beide widersprüchlichen Anforderungen erfüllt werden. Vorausgesetzt, dass die Familie von Parametern groß genug ist (möglicherweise unendlich) und jede ihrer Komponenten nachweislich angemessene Eigenschaften hat, wird es Angreifern nicht möglich sein, die Parameter lediglich durch Inspektion zu bestimmen.

Schließlich muss ein Schlüssel, damit er effektiv funktioniert, leicht zu erzeugen, aber nahezu unmöglich zu erraten sein. Mit der Rechenleistung der heutigen Computer würde ein Computer weniger Zeit benötigen, um einen von Menschen generierten Schlüssel zu entschlüsseln, als jeder Mensch sich vorstellen könnte, zusätzlich zu der Tatsache, dass es ohnehin nicht kosteneffektiv ist, Schlüssel auf diese Weise zu generieren. Aus diesem Grund werden Schlüssel in der Regel von einem Algorithmus generiert.

Ein Schlüsselgenerierungsalgorithmus darf keine vorhersagbare/reproduzierbare Ausgabe als Ergebnis einer typischen Verwendung erzeugen. Da Algorithmen Verfahren ohne intelligenten Prozess ausführen, stellt sich die Frage, wie dies bewerkstelligt werden kann. Die Antwort besteht darin, Schlüsselerzeugungsalgorithmen in Karten umzuwandeln, die eine große Menge wirklich zufälliger Bits in Schlüssel umwandeln. Wirklich zufällige Bits können vom Betriebssystem erworben werden, das sie aus der Unsicherheit im Universum generiert. Einige Quellen wären je nach Anwendung Ihre Mausbewegung, Netzwerkpaketlatenzen oder sogar dedizierte Hardware.

Public-Key-Kryptosysteme

Lassen Sie sich erneut überraschen, denn wir werden jetzt ein Konzept einführen, das dem, was wir gerade gesagt haben, scheinbar widerspricht: den öffentlichen Schlüssel.

Bisher haben wir die Schaffung einer sicheren Kommunikation gesehen, nachdem geheime Parameter (Schlüssel) sicher ausgetauscht wurden, aber das Problem des Austauschs der Parameter über einen öffentlichen Kanal bleibt bestehen. Im Moment stellen wir ein Konzept vor, das ein etwas greifbareres Problem löst: die Schaffung eines sicheren Kanals.

Angenommen, Alice arbeitet mit Bob zusammen und sie möchten ihre Arbeitsinteraktionen durch Verschlüsselung schützen. Sie können sich treffen und ihre Verschlüsselungsschlüssel austauschen, indem sie sich gegenseitig ein USB-Flash-Laufwerk mit ihren Schlüsseln geben. Aber was ist, wenn sich Alice und Bob auf verschiedenen Kontinenten befinden? Wie richtet man einen sicheren Kanal ein, wo keiner existiert?

Das Versenden von Schlüsseln per E-Mail wäre keine Option, da der Konkurrent Eve den Austausch abfangen und mit seinen Schlüsseln anschließend alle verschlüsselten Daten auslesen kann. Wenn sie einen anderen digitalen Kanal hätten, über den sie diese sensiblen Daten übertragen könnten, dann bräuchten sie überhaupt keine Verschlüsselung und damit keine Schlüssel. Auch das Versenden des Schlüssels per Post könnte abgefangen werden, da zunächst sensible Informationen ausgetauscht werden müssen. Das Senden eines steganographierten Schlüssels durch Verstecken in anderen Daten wäre clever, aber nutzlos, es sei denn, der Absender ist sicher, dass der Empfänger, und nur der Empfänger, sich der Existenz einer solchen Nachricht bewusst ist und weiß, wie sie extrahiert wird. Tatsächlich ist das Wissen um die Existenz einer Nachricht zusammen mit der Beschreibung, wie der Schlüssel aus den Daten extrahiert werden kann, eine Art Schlüssel für sich, was uns wieder zum Anfang bringt.

Die Lösung besteht darin, ein Kryptosystem zu entwickeln, für das der Verschlüsselungsparameter nicht ausreicht, um die ursprüngliche Nachricht ^[1] machbar zu interpretieren, und den Parameter für sich zu behalten, der die Interpretation der Nachricht ermöglichen würde. Wir nennen diesen Parameter den privaten Schlüssel. Auf der Grundlage des privaten Schlüssels kann man durchaus einen Satz von Parametern für ein Verschlüsselungstool generieren, ohne dass diese neuen Parameter selbst in der Lage sind, den privaten Schlüssel zu enthüllen. Dieser Parametersatz kann öffentlich geteilt werden, da es nicht so wichtig ist, wer etwas verschlüsseln kann, solange nur eine Person es entschlüsseln kann. Da dieser Parametersatz für das Verschlüsselungstool öffentlich gemacht werden kann, wird er als öffentlicher Schlüssel bezeichnet.

Kryptografie, bei der sich die Verschlüsselungs- und Entschlüsselungsschlüssel unterscheiden und erstere nicht zur Ableitung der letzteren verwendet werden können, wird als asymmetrische Kryptografie bezeichnet, während symmetrische Kryptographie das ist, was wir haben, wenn diese Schlüssel gleich sind oder leicht voneinander abgeleitet werden können.

Alice sendet Bob ihren öffentlichen Schlüssel, der nur zum Verschlüsseln von Dingen verwendet werden kann, die nur sie entschlüsseln kann (mit ihrem privaten Schlüssel, den sie privat aufbewahrt), und umgekehrt sendet Bob Alice seinen öffentlichen Schlüssel, der nur zum Verschlüsseln von Dingen verwendet werden kann die er alleine entschlüsseln kann (mittels seines privaten Schlüssels, den er auch privat verwahrt). Aber wie kann man möglicherweise einen Parameter für einen Verschlüsselungsalgorithmus veröffentlichen, aus dem man nicht den genauen inversen Algorithmus ableiten kann?

Die Antwort liegt in dem Bereich der Mathematik, der der Programmierung am nächsten steht, der Computational Complexity Theory. Jeder, der sich tief genug mit mathematischen Problemen beschäftigt hat, hat von Transformationen gehört, die auf eine Weise einfach zu bewerkstelligen sind, aber schwer auf die umgekehrte Weise. In der Analysis zum Beispiel ist das Finden einer Lehrbuchableitung normalerweise eine einfache Übung, während das Umgekehrte (wie zum Beispiel das Lösen eines leicht nicht trivialen Integrals oder einer physikalischen ODE oder PDE aus einem Lehrbuch) einen recherchierenderen Prozess erfordert, bei dem zuerst Funktionsfamilien hypothetisiert werden garantiert (oder zumindest plausibel) sind, die Lösung(en) zu enthalten und inverse Probleme zu lösen, um Lösungen aus diesen Familien zu finden.

Ein Beispiel, das tatsächlich im RSA-Kryptosystem verwendet wird, ist die Multiplikation großer Primzahlen im Vergleich zur Faktorisierung des resultierenden Produkts, ohne die Faktoren bereits zu kennen. Die Multiplikation ist trivial, aber beim Faktorisieren musst du zufällig ^[2] die Primfaktoren erraten, die Hunderte von Ziffern haben. Eine wichtige Eigenschaft der Operation ist die Notwendigkeit einer guten Skalierung. Das Hinzufügen einiger Ziffern zur Größe der Primzahlen in RSA führt zu einem Schlüssel, der Tausende Male mehr Operationen zum Knacken erfordert, während der Verschlüsselungsprozess nur geringfügig komplexer wird. Grob gesagt wird zum Verschlüsseln das Produkt der Primzahlen verwendet, während zum Entschlüsseln das Paar der Primzahlen verwendet wird.

Lassen Sie uns vor diesem Hintergrund einen Blick darauf werfen, wie das SRVB-Kryptosystem funktioniert.

Der zugrunde liegende Algorithmus - Ein Blick auf SRVB

Das Teilmengensummenproblem

Wie jedes andere Public-Key-Kryptosystem verlässt sich SRVB auf die Schwierigkeit, ein bestimmtes Problem zu lösen, das einfach zu produzieren ist. Im Fall von SRVB ist es das Teilsummenproblem, das wie folgt beschrieben werden kann:

Gegeben die ganzen Zahlen $w$ und $v_1, \cdot \cdot \cdot, v_N \in Z$ finde die Folge $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, so dass $ \sum_ {i = 1}^{N} v_i b_i = w $.

Natürlich kann dieses Problem dadurch erzeugt werden, dass N ganze Zahlen zufällig ausgewählt werden, zufällig eine Teilmenge davon ausgewählt wird und diese Teilmenge summiert wird – was trivial ist.

Eine Brute-Force-Suche hätte eine Komplexität von $ O( N * 2^N ) $, wobei für jede Kombination von Werten der $b$s gerechnet würde. Ein effizienterer Ansatz wurde 1972 von Horowitz und Sahni mit einer Komplexität von $ O ( N * 2 ^ {N / 2} ) $ angegeben. Das Problem ist mindestens genauso schwierig, wenn wir die $b$s und $w$ durch $k$-dimensionale Vektoren ganzer Zahlen ersetzen. Der Bereich, in dem dieses schwierigere Problem zu halten ist, muss jedoch auch einen Isomorphismus mit einem Ring haben, wo eine einfachere Version desselben Problems stattfindet, wie wir weiter unten sehen werden. Aus diesem Grund nutzt SRVB das Teilmengensummenproblem innerhalb Gaußscher Ganzzahlen aus, wobei $ k = 2 $ ist.

Es gibt einen Sonderfall, in dem dieses Problem durch die Verwendung eines gierigen Algorithmus leicht zu berechnen ist. Wenn wir eine Folge sortieren, werden Skalierungsfaktoren $ v_1, \cdot \cdot \cdot, v_N $, bei denen jede ganze Zahl in der Folge größer ist als die Summe aller vorangegangenen ganzen Zahlen ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), könnte man einen Greedy-Ansatz verwenden, um die Folge b in linearer Zeit zu finden. Eine Folge mit den beschriebenen Eigenschaften wird als übersteigende Folge bezeichnet .

Hier ist eine einfache Beschreibung der Greedy-Lösung für diesen Fall:

1. Beginnen Sie mit $ i = N $, dem aktuell beobachteten Faktor, und $ w' = w $, dem Rest von $w$

2. Wenn der aktuelle Skalierungsfaktor zu groß ist, um in den Rest von $w$ zu passen, dh $ v_i > w'$, setze $b_i = 0$ und fahre mit dem nächsten Schritt fort. Andernfalls wissen wir, dass der Skalierungsfaktor in der Sequenz sein muss (da der Rest der Faktoren kleiner als $v_i$ ist) und wir setzen $b_i = 1$.

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. Wenn $i > 0$, zurück zu Schritt 2.

4. Stellen Sie jetzt sicher, dass $w' == 0$, andernfalls wurde das Problem beschädigt

Dies funktioniert, weil wir wissen, dass alle Multiplikatoren, die kleiner als der aktuell beobachtete sind, zusammen nicht so viel von der (Teil-)Summe $ w' $ abdecken können wie der aktuelle Multiplikator. Wenn also die verbleibende Summe größer als der aktuelle Faktor ist, wissen wir mit Sicherheit, dass alle folgenden Faktoren zusammen ohne die Hilfe des aktuellen Faktors nicht dazu führen werden. Da andererseits alle Multiplikatoren positiv sind, wenn der aktuelle Faktor $ v_i $ größer als die verbleibende Summe $ w' $ ist, würde das Hinzufügen eines anderen Faktors dazu führen, dass das Ergebnis $ w' $ noch mehr übertrifft.

Lassen Sie uns eine Notation für den Rest des Artikels einrichten. Wir wählen $ v_1, \cdot \cdot \cdot, v_n $ und $w$ als Faktoren und Summe der supersteigenden Folge, während $ u_1, \cdot \cdot \cdot, u_n $ und $y$ die öffentlichen sind verfügbare Parameter, die bereitgestellt werden, um $ b_1, \cdot \cdot \cdot, b_n $ wiederherzustellen.

Mit einer Folge $ u_1, \cdot \cdot \cdot, u_n $, die so ausgewählt wurde, dass sie nicht superzunehmend ist, und der Zahl $y$, die öffentlich verfügbar ist, werden nicht genügend Informationen öffentlich bereitgestellt, um die Folge $ b_1, \cdot \cdot \cdot wiederherzustellen , b_n $. Wenn es jedoch eine supersteigende Folge $ v_1, \cdot \cdot \cdot, v_n $ gibt, die die Folge $ u_1, \cdot \cdot \cdot, u_n $ ersetzen könnte, könnte man diese Folge verwenden, um das Problem zu lösen eine gierige Annäherung.

Im Folgenden zeigen wir, wie das funktioniert.

Verwendung von Teilmengensummen in einem früheren Kryptosystem

1978 entwickelten Ralph Merkle und Martin Helman einen Weg, um diese beiden Rucksackparadigmen und die Linearität der Modulo-Operation auszunutzen, um die Verbindung zwischen den beiden im vorherigen Abschnitt beschriebenen Sequenzen herzustellen – und so ein Public-Key-Kryptosystem zu konzipieren. Die Idee war, den einfachen Rucksack (denjenigen, der aus dem superwachsenden Vektor ganzer Zahlen besteht) in den harten (denjenigen, dem diese Eigenschaft fehlt) durch eine lineare Operation (den Modulus) mit geheimen Operanden umzuwandeln. Die Transformation besteht darin, jedes $v_i$ mit einem $\theta$ zu multiplizieren und den Rest dieses Produkts mit einem $\alpha$ zu bilden, wobei $\alpha \gt \sum_{i=1}^N v_i$ und $\gcd (\alpha, \theta) = 1$ (zwei Nebenbedingungen, die bald gerechtfertigt werden). Das Ergebnis, die Folge $u_1, \ldots, u_N$, ist nicht mehr supersteigend und kann als harter Rucksack betrachtet werden.

Eine zufällige Permutation der Sequenz $u_1, \ldots, u_N$ würde der Partei gegeben werden, die eine Nachricht verschlüsseln und an uns senden möchte. Die Permutation wird durchgeführt, damit ein Dritter es schwerer hat, zu erraten, was die ursprüngliche superanwachsende Sequenz ist. Bitblöcke einer Nachricht werden als Koeffizienten $b_1, \ldots, b_N$ verwendet. Die Verschlüsselung erfolgt durch Multiplizieren der Schlüsselsequenz mit dieser Koeffizientensequenz und Summieren der Multiplikationen zu einem Ergebnis, das wir $y$ nennen werden. Nur der Besitzer des privaten Schlüssels kann $y$ in das entsprechende $w$ umwandeln, das erhalten würde, wenn dieselben $b_1, \ldots, b_N$-Blöcke mit den einfachen ganzen Zahlen multipliziert worden wären (die Sequenz $v_1, \ldots , v_N$). Dies geschieht durch Multiplikation von $y$ mit $\theta^{-1}$, dem multiplikativen Inversen von $\theta$ modulus $\alpha$ (dessen Existenz von der Bedingung von $\gcd(\alpha, \ theta) = 1$). Mit anderen Worten, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Danach berechnen wir $w = (y * \theta^{-1}) \bmod a$. Der Grund dafür, dass dies garantiert funktioniert, ist die Linearität von modulus , dh dass die lineare Kombination der Reste gleich dem Rest der linearen Kombination ist.

Wenden wir nacheinander die Definition von $u$, dem Quotientenring, und der Linearitätseigenschaft des Moduloperators an, sehen wir die Entsprechung:

$ \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 & = \ left[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

Und so kann die einfache Summe $w$ wiederhergestellt werden, indem man beide Seiten mit $\theta^{-1}$ multipliziert und den Modulus mit $\alpha$ nimmt. Dazu muss man sowohl $\alpha$ als auch $\theta$ kennen (womit man leicht $\theta^{-1}$ berechnen kann), die als Teile des privaten Schlüssels geheim zu halten sind.

Eine einzige Bedingung, $\alpha \gt \sum_{i=1}^N v_i$, wurde ungerechtfertigt gelassen und hier die Erklärung dafür: Die Gleichheit zwischen der zweiten und dritten Zeile besteht aus einer Gleichheit zwischen Restklassen des Quotienten Ring aus ganzen Zahlen modulo $\alpha$. Mit anderen Worten, es gibt nur die Gleichheit des Rests der Mitglieder an, wenn es durch $\alpha$ dividiert wird, was keine ausreichende Bedingung für die Gleichheit der Mitglieder selbst ist . Dadurch könnten mehr als ein Vektor von $b$-Werten auf ein einzelnes $y$ abgebildet werden, was verhindert wird, indem die maximal mögliche Teilsumme (also die Summe aller Pakete $v_i$) auf $w_{max}$ begrenzt wird für jede Kombination von $b$-Werten kleiner als $\alpha$ sein.

Genau wie in jedem anderen Fall des täglichen Lebens ist die vollständige Kenntnis aller Hypothesen oft unmöglich und nie einfach. Infolgedessen müssen wir uns bei der Beurteilung, ob ein Kryptosystem sicher zu verwenden ist, auf mathematische Intuition verlassen, was uns keine wirklichen Garantien bietet. Sechs Jahre nach seiner Gründung wurde das MH-Kryptosystem durch einen Angriff von A. Shamir gebrochen. Es gab mehrere weitere Versuche, MH wiederzubeleben, von denen viele ebenfalls fehlschlugen.

Das Santana Rocha - Villas Boas (SRVB) Kryptosystem

Im Jahr 2016, nach einigen Brainstormings mit dem Autor dieses Artikels über unterschiedlich inspirierte ^[3] Möglichkeiten eines Kryptosystems, hatte Daniel Santana Rocha die Idee, $\theta$ und $\alpha$ durch Gaußsche ganze Zahlen zu ersetzen. Aus eher technischen Gründen führt dieser Ansatz zum Widerstand gegen den oben erwähnten Shamir-Angriff.

Er konzipierte auch einen Bitblock, der aus vielen Schritten der zuvor beschriebenen linearen Kombination eines harten Rucksacks besteht. In jeder von ihnen würde am Ende der Sequenz eine neue (Gaußsche) ganze Zahl, die eins entspricht und höher als die Summe aller vorherigen ist, hinzugefügt, während die aktuell kleinste ausgelassen würde.

Eine andere und doch elegant analoge Beschränkung gilt für $\alpha$, das jetzt eine Gaußsche ganze Zahl ist. Wir benötigen $w_{max} \leq \vert\alpha\vert^2$. Der Grund ist sehr schwer zu formalisieren, aber glücklicherweise lässt er sich leicht aus einer eleganten Beschreibung erschließen:

Stellen Sie sich ein quadratisches Gitter in der Ebene komplexer Zahlen vor, dessen Seite eine Hypotenuse eines rechtwinkligen Dreiecks der Katheten a und b ist, parallel zu den reellen und imaginären Achsen. Ein Beispiel eines solchen Gitters ist unten angegeben. Guassische ganze Zahlen modulo $\alpha = a + bi$ können durch Punkte dargestellt werden, die sich innerhalb eines solchen Gitters befinden. Innerhalb eines solchen Gitters gibt es $\vert\alpha\vert^2$ verschiedene Punkte. Wenn wir $\alpha$ groß genug wählen, können wir alle linearen Kombinationen des einfachen Tornisters anpassen.

Dies ist die grafische Darstellung des Isomorphismus $f : Z/n \rightarrow Z[i]/(\alpha)$, wobei $n = 13$ und $\alpha = a + bi = 3 + 2i$ (man beachte, dass $ n$ und $\alpha$ erfüllen tatsächlich $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ wie gefordert). Die Punkte stellen die Gaußschen ganzen Zahlen dar, dh die komplexen Zahlen $a + bi$, wobei $a$ und $b$ ganze Zahlen sind. Wie üblich stellt die horizontale Achse den Realteil dar, während die vertikale Achse den Imaginärteil darstellt. Das Bewegen um einen Punkt nach rechts oder links entspricht also dem Hinzufügen von +1 bzw. -1 zu seinem aktuellen Wert. Ebenso entspricht das Bewegen um einen Punkt nach oben oder unten dem Hinzufügen von +i bzw. -i.

Die roten Punkte sind die Äquivalente zu $0 \bmod(\alpha)$. Außerdem haben wir noch 4 weitere Punktpaare eingefärbt.

Der Isomorphismus $f$ ist definiert durch die Transformation des $i$ten Elements der zyklischen Folge $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ in das $i$te Element der ebenfalls zyklischen Punktfolge in der Abbildung, die sich an folgende Regeln hält:

1. Es beginnt mit dem roten Punkt der ersten Reihe;
2. Es folgt den horizontalen Pfeilen nach rechts; außer dass
3. Wenn man den Pfeilen folgt, führt die Sequenz aus dem Gitter heraus, sie würde einen der nicht schwarzen Punkte erreichen. Anstatt zu diesem Punkt zu gehen, springt es zu demselben farbigen Punkt (dh dem äquivalenten Punkt modulo $\alpha$) innerhalb desselben Quadrats; und schlussendlich
4. Wenn dieser nicht-schwarze Punkt rot ist (was passiert, nachdem alle anderen Farben durchlaufen wurden), springt die Sequenz zum obersten roten Punkt, wodurch der Zyklus neu gestartet wird;

Um mindestens $Y$ natürliche ganze Zahlen abzubilden, muss man ein Quadrat mit der Fläche $\vert\alpha\vert^2$ nehmen (wobei $\vert\alpha\vert = \sqrt{a^2 + b^2} $ ist nach dem Satz des Pythagoras das Maß seiner Seite) mindestens genauso hoch.

Beachten Sie, dass jeder „Sprung“ die Zeilennummer $r$ zu $r \leftarrow (r + b)(mod a + b)$ ändert, wenn man die Zeilen von oben nach unten zählt, und äquivalent zu $r \leftarrow (r + a)(mod a + b)$ wenn man von unten nach oben zählt. Daher ist die notwendige und hinreichende Bedingung dafür, dass jede Zeile (und jeder Punkt) in jedem Zyklus genau einmal durchlaufen wird, dass die Größe der Sprünge teilerfremd ist mit der Anzahl der Zeilen, oder mit anderen Worten $gcd(a,a + b) = ggT(b,a + b) = 1$. Aufgrund der Eigenschaften des Operators des größten gemeinsamen Teilers sind beide äquivalent zu $gcd(a,b) = 1$.

YS Villas Boas bemerkte die Notwendigkeit der Koprimalität von $a$ und $b$. Um die Übersteigerung zu erhalten, muss jede neue ganze Zahl $w$, die am Ende der Sequenz hinzugefügt wird, die Summe aller aktuellen übertreffen ($w > \sum_{i=1}^k v_i$). Er bemerkte, dass dazu ihre Multiplikationskoeffizienten $b_i$ mindestens 1 sein müssten und somit nicht jedes Bit in die Koeffizienten 0 und 1 abgebildet werden könnte. Wenn die Koeffizienten 0 und 1 wären, nur der Block nur aus Einsen zusammengesetzt würde der Übersteigerung genügen. Aus diesem Grund wurden die Bits 0 und 1 dann jeweils auf die Multiplikationskoeffizienten 1 und 2 abgebildet.

Schließlich und weniger trivial: Bei jedem Schritt der Dekodierung ist eine neue ganze Zahl $v_1$ als Lösung der Gleichung $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} zu finden b_i v_i$, wobei alle $v_i$ und $b_i$ für $1 < i \leq n$ bekannt sind. Da wir auch $b_1$ nicht kennen, haben wir am Ende ein System mit einer Gleichung und zwei Variablen, was uns einen Freiheitsgrad lässt. Um dies zu korrigieren, müssen wir einen positiven Wert (der Einfachheit halber 1) arbitrieren, der immer $b_1$ zugewiesen wird, wodurch die Mehrdeutigkeit beseitigt wird. Da der erste Koeffizient auf 1 festgelegt ist, müssen unsere Folgen von ganzen Zahlen also $n + 1$ Elemente lang sein, um $n$ Bits in jedem Schritt zu codieren.

Eine letzte zu lösende technische Besonderheit ist der Fall, in dem die Größe der Nachricht in Bytes kein Vielfaches der Blockgröße ist. Mit anderen Worten, was ist mit den möglicherweise verbleibenden Bytes des letzten Datenblocks zu tun, damit nach der Wiederherstellung der Datenblöcke alle Bytes des ursprünglichen Inhalts erhalten bleiben, aber nicht mehr als sie? Wir haben das gelöst, indem wir das letzte Byte der Nachricht einmal wiederholt haben. Auf diese Kopie folgt dann eine zufällige Sequenz, bei der jede Komponente nur anders als die vorherige sein muss. Beim Abrufen der Datenblöcke wird also der letzte oder schlimmstenfalls der vorletzte in der letzten Byte-Wiederholung abgeschnitten. ^[4]

Lassen Sie uns nun ein Beispiel des SRVB-Kryptosystems zeigen.

Wir beginnen mit den Parametern:

$ k = 4 $;

$m = 4$;

was eine Blocklänge von $l = 4 * 4 = 16$ ergibt, und eine supersteigende Folge von $k + 1 = 5$ natürlichen ganzen Zahlen, die mit dem Ergebnis dieser Linearkombination verknüpft, dh linear kombiniert, und verknüpft wird auf seine letzten $k + 1$ Elemente reduziert —$m = 4$ mal;

Der Einfachheit halber sei folgendes der (superwachsende) Vektor von $v_i$:

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

Allerdings die Folge der ersten fünf Potenzen von 2, eben weil dies die supersteigende Folge mit fünf Elementen und den kleinstmöglichen streng positiven Werten ist (womit eine 0 im öffentlichen Schlüssel vermieden wird, die trivialerweise die entsprechende 0 ihres Gegenstücks verraten würde ).

Wie wir bereits gesagt haben, müssen für $\alpha = a + bi$ die ganzen Zahlen $a$ und $b$ teilerfremd sein, und gemäß der neuen Einschränkung, die wir erwähnt haben, müssen wir verlangen, dass $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Eine schnelle Rechnung ergibt $W = 1590$. Da $\sqrt{1590} \simeq 39,8$ ist, wäre ein sehr bequemes zu wählendes $\alpha$ $\alpha = 39 + 40i$, denn es ist gerade groß genug, um einen Isomorphismus mit einem Ring aus ganzen Zahlen mit at aufzunehmen mindestens 1590 Komponenten und erfüllt gleichzeitig $gcd(a,b)=1$. Außerdem müssen wir ein $\theta$ so wählen, dass $gcd(a,\theta)=1$ ^[5] und vorzugsweise nicht zu niedrig ist, sodass $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (auch um Informationen nicht preiszugeben). $\theta = 60$ erledigt die Arbeit und ergibt:

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

Dann machen wir uns die Hände schmutzig. Nehmen Sie die Nachricht Hello Toptal! . Zuerst bilden wir es gemäß ASCII und unserer Konvention zum Abschneiden von Datenblöcken in ein Array von Bytes ab:

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

Da unser Datenblock 16 Bit = 2 Byte lang ist und unsere Nachricht 13 Zeichen hat, erhalten wir am Ende 7 Datenblöcke zu je 2 Byte, wobei der letzte die zweifache Bitdarstellung des Zeichens '!' . Lassen Sie uns Schritt für Schritt den ersten Block verschlüsseln. Achten Sie genau darauf, da die Bits jedes Bytes in der Reihenfolge ihrer Bedeutung genommen werden.

$m=01001000 01100101$

• Erstes Halbbyte des ersten Bytes: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Zweites Halbbyte des ersten Bytes: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Erstes Halbbyte des zweiten Bytes: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Zweites Halbbyte des zweiten Bytes: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

Und so haben wir gerade abgebildet

„Er“ $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

Der Rest der verschlüsselten Nachricht lautet wie folgt:

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

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

„Nach“ $\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)$

”!!” $\Rightarrow(12-12i,4+54i,32+65i,63+92i,121+247i)$

Für die Entschlüsselung haben wir nun $\theta^{-1}=60^{-1}=27+i$:

$($”Er” $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93.223.527)$

Jetzt kommt der Greedy-Algorithmus:

Zuerst subtrahieren wir jeden beitragenden Faktor multipliziert mit eins, da bekannt ist, dass sie mindestens einmal zum letzten beigetragen haben, was ergibt:

• Zweites Nibble des zweiten Bytes:

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

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

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

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

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

Ergebnis: 0110;

Rest: 8 (am Anfang der Sequenz als neues unterstes Element hinzugefügt);

Lassen Sie 527 aus dem Finale der aktuellen Sequenz fallen;

• Erstes Nibble des zweiten Bytes:

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

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

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

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

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

Ergebnis: 0101;

Rest: 4 (am Anfang der Sequenz als neues unterstes Element hinzugefügt);

Lassen Sie 233 aus dem Finale der aktuellen Sequenz fallen;

• Zweites Nibble des ersten Bytes:

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

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

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

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

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

Ergebnis: 0100;

Rest: 2 (am Anfang der Sequenz als neues unterstes Element hinzugefügt);

Lassen Sie 93 aus dem Finale der aktuellen Sequenz fallen;

• Erstes Nibble des ersten Bytes:

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

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

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

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

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

Ergebnis: 1000;

Rest: 1 (am Anfang der Sequenz als neues unterstes Element hinzugefügt);

Drop 47 aus dem Finale der aktuellen Sequenz;

Als Ergebnis haben wir den Datenblock „01001000 01100101“ wiederhergestellt, der die ersten beiden Zeichen „He“ unserer Nachricht enthält. Nicht nur das, wir haben auch unsere Superincreasing-Sequenz $(1,2,4,8,16)$ unseres privaten Schlüssels korrekt abgerufen.

Die anderen Datenblockkarten gehen auf die gleiche Weise.

Vergleich mit den wichtigsten Public-Key-Kryptosystemen

SRVB ist:

1. Völlig kostenlos und öffentlich;

2. Wesentlich einfacher und leichter zu verstehen und zu implementieren als ECC ^[7] ;

3. Reichlich an Schlüsseln und damit praktisch kostenlos, im Gegensatz beispielsweise zu RSA, das auf Primzahlen setzt, die teuer sind.

Wir können bereits die wahrscheinlichsten Schwachstellen zusammenfassen. Da SRVB von MH abstammt, ist es leicht zu vermuten, dass es anfällig für eine Verallgemeinerung des Shamir-Angriffs oder eines anderen Angriffs wäre, der ihn bricht. Obwohl der Autor Grund zu der Annahme hatte, dass dies nicht der Fall sein würde, wurde dies bisher nicht bestätigt (was sehr typisch ist, wenn es um Kryptosysteme geht).

Was kommt als nächstes?

Rocha beobachtete einige Verallgemeinerungen für die zu verwendenden Quotientenringe, die möglicherweise zu einer Erhöhung der Komplexität der Kryptoanalyse führen können. Auch diese Möglichkeiten werden wir untersuchen.

Die lineare algebraische Verschleierung

Zufälligerweise hat Villas Boas während der Entwicklung und Dokumentation von SRVB einen weiteren Ansatz zur Verbesserung des Konzepts des Knapsack-Public-Key-Kryptosystems entwickelt, der hier nicht im Detail erläutert wird, damit dieser Artikel nicht zu lang wird und ermüdend, aber hier ist ein Überfliegen davon. Wenn es Ihnen nicht gelingt, es zu begreifen, machen Sie sich keine Sorgen, warten Sie einfach auf die Veröffentlichung unseres nächsten Artikels, in dem wir ausführlicher auf die Details eingehen werden: Siehe die Teilmengensumme $y$, der, sagen wir, $N$ Quotientenringelemente $u_i$ (die wie zuvor isomorph den positiven ganzen Zahlen $v_i$ der supersteigenden Folge entsprechen) als Multiplikation eines Zeilenvektors dieser $u_i$ mit einem Spaltenvektor $B$ ( für binär) von Nullen und Einsen ^[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,

wo $b_i \in {0,1}$

Stellen Sie sich nun vor, dass Sie anstelle dieses Vektors von $u_i$ auf der linken Seite eine Matrix V von $n$ mal $N$ (mit $n < N$) haben, die die $v_i$ (die ganzen Zahlen aus der Superincreasing Sequenz) Vektor als (ohne Verlust der Allgemeinheit) seine erste Zeile und alle anderen Einträge mit Rauschen aufgefüllt. Beachten Sie, dass Sie jetzt durch Multiplizieren von V mit demselben Bitvektor B einen Spaltenvektor W erhalten, der $w$ als ersten Eintrag und Rauschen in den anderen hat. Nehmen Sie nun diese V-Matrix und multiplizieren Sie sie mit einer zufälligen ^[9] n-mal-n-Matrix R auf der linken Seite, wodurch die n-mal-N-Matrix P definiert wird:

P = RV

Die Idee ist, dass Bob P als seinen neuen öffentlichen Schlüssel verwendet. Wegen der Zufälligkeit von R, dem Vektor

$Y = PB = RVB = RW$

hat die Information $w$ durch das Rauschen in anderen Zeilen von V verdeckt. Bob berechnet ebenfalls im Voraus und speichert den Zeilenvektor S, der erfüllt:

$R^TS^T = e_1$

Wenn Alice Y an Bob sendet, findet er nur SY, weil:

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

(bisher nur Definitionen)

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

(Jetzt die Assoziativität ausnutzen, um die Rs aufzuheben)

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.

Danksagungen

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.

Glossar

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) $.