Manchmal entsteht eine Aufgabe, um die Bezeichnerzeichenfolge vor versehentlichen Fehlern einer Person zu schützen. Zum Beispiel Zahlungskartennummer. Zu diesem Zweck wird der Zeile eine auf spezielle Weise berechnete Prüfziffer hinzugefügt. Wenn eine Person diese Nummer eingibt, können Sie eine erste Fehlerprüfung durchführen, ohne auf die Datenbank zuzugreifen. Die einfachste Möglichkeit besteht darin, den Rest der Division der Summe aller Ziffern durch 10 zu addieren. In diesem Fall ist die Verzerrung einer Ziffer (einschließlich der Kontrollziffer) leicht zu erkennen, und eine solche Linie besteht den Test nicht. Bei einigen anderen Fehlern, wie z. B. einer Prüfsumme, fehlt beispielsweise eine Permutation von zwei Stellen an bestimmten Stellen, und dies ist auch ein ziemlich häufiger Fehler.
Zum Schutz der Bankkartennummern wurde ein etwas komplexerer Algorithmus gewählt,
der Moon- Algorithmus. Eine Modifikation wurde hinzugefügt: Die an geraden Stellen stehenden Zahlen werden vor der Summierung mit 2 multipliziert (und wenn sich herausstellt, dass mehr als neun vorhanden sind, wird 9 abgezogen). Auf diese Weise können Sie zusätzlich zur Verzerrung einer Ziffer die meisten (wenn auch nicht alle) Permutationen benachbarter Ziffern erfassen.
Gibt es Algorithmen, die Permutationen benachbarter Ziffern erkennen können (zusätzlich zur Verzerrung einer einzelnen Ziffer)? Ja, sie existieren, obwohl sie aus irgendeinem Grund nicht sehr häufig sind. Dies ist
der Verhuff-Algorithmus, der auf Diedergruppen basiert, und
der Damm-Algorithmus , der auf Damm-Quasigruppen basiert. Es klingt beängstigend, aber tatsächlich gibt es nichts Kompliziertes (für diejenigen, die mit dem Konzept der "Gruppe" vertraut sind).
Jacobus Verhoeff, ein niederländischer Mathematiker und Bildhauer (eine seiner Skulpturen auf dem Foto), schlug einen Algorithmus vor, der auf
Diedergruppen basiert. Eine Diedergruppe ist eine Gruppe von Symmetrien eines regulären N-Gons, einschließlich Rotationen und axialer Symmetrien. Eine solche Gruppe ist nicht kommutativ: Wenn ein reguläres Polygon mit neu nummerierten Scheitelpunkten zuerst symmetrisch angezeigt und dann gedreht wird, ist es in den meisten Fällen nicht dasselbe, als ob Sie zuerst drehen und dann anzeigen. Und daher, wenn nacheinander die Ziffern der ursprünglichen Zeichenfolge unter Verwendung der Operation der Diedergruppe "multipliziert" werden, d.h. Durch sukzessives Anwenden der Rotations- und symmetrischen Abbildungsoperationen über das reguläre N-Gon erhalten wir Schutz gegen die meisten Permutationen. Von der Mehrheit, aber immer noch nicht von allen. Verkhuff schlug vor, diesen Algorithmus zu verbessern und vor dem Multiplizieren jeder Ziffer durch eine andere gemäß einer speziellen Tabelle zu ersetzen, abhängig von der Position der Ziffer in der Zeile. Die Tabelle wird aus einer Permutation erhalten, indem sie nacheinander auf das vorherige Ergebnis angewendet wird. Nach 8 solchen Anwendungen kehren wir zur ursprünglichen Reihenfolge zurück, sodass Sie die Tabelle 8x10 vorab erstellen und den Wert von dort übernehmen können. Einige dieser Permutationen ermöglichen es uns, alle 100% der möglichen Fehler in der Reihenfolge benachbarter Ziffern der Quellzeichenfolge zu bestimmen. Dies ist eine vollständige und korrekte Lösung für das Problem, eine Prüfziffer zu finden, die vor diesen beiden Fehlertypen schützt. Anscheinend hat Verkhuff eine erfolgreiche Permutation durch zufällige Auswahl gefunden, es gibt einige davon.
Die Frage, ob es Gruppen gibt, die es ermöglichen, Permutationen benachbarter Ziffern ohne zusätzliche Modifikationen zu finden, ist lange offen geblieben. Und bereits im 21. Jahrhundert, im Jahr 2004, hat der deutsche Mathematiker Michael Damm die Existenz solcher Gruppen nachgewiesen, die als schwach vollständig antisymmetrische Quazigruppen bezeichnet werden. Ich habe nicht vollständig herausgefunden, wie man sie baut, und diejenigen, die dies wünschen, können versuchen, dies selbst zu tun, indem
sie es veröffentlichen . Und obwohl es bei einem kurzen Blick nicht so kompliziert aussieht (es ist sogar seltsam, dass die Frage so lange offen geblieben ist), gibt es für die praktische Implementierung einen einfacheren Weg: Verwenden Sie
vorgefertigte Tabellen .
Fahren wir nun mit der nächsten und wichtigsten Frage fort: Was ist, wenn ich nicht eine Folge von Dezimalstellen, sondern eine Folge von beliebigen Zeichen, z. B. hexadezimal oder base64 oder base58, schützen muss? Das heißt, das Problem nicht im speziellen Fall des Dezimalzahlensystems zu lösen, sondern in allgemeiner Form.
Der Mondalgorithmus erstreckt sich problemlos auf diesen Fall, ist jedoch nicht so interessant, da nicht alle Permutationen benachbarter Ziffern gefunden werden. Das Verfahren zum Aufbau einer antisymmetrischen Quasigruppe beliebiger Größe ist nicht ganz klar. Für den Verhuff-Algorithmus ist eine Diedergruppe der Größe N leicht zu konstruieren, aber Sie benötigen immer noch eine Permutationstabelle, die auch unklar ist, woher sie stammt (und es ist nicht einmal klar, ob sie existiert). Dies ist das Studium der letzten Frage, und ich habe begonnen.
Das Googeln ergab nichts als getrennte Versuche und die Verwendung von "ziemlich guten" Lösungen (dh das Erkennen fast aller Permutationen) für N = 64.
Vielleicht werde ich nicht alle bewährten Wege beschreiben, um die gewünschte Permutation zu finden, die kein Ergebnis lieferte. Ich habe versucht, ein bestimmtes Problem zu lösen: eine Permutation für base64 und base58 zu finden, die Schutz gegen das Ändern der Reihenfolge benachbarter Ziffern bietet. Ich kann nur sagen, dass Versuche, eine solche Permutation durch zufällige oder sequentielle Suche mit verschiedenen Optimierungsoptionen zu finden, fehlgeschlagen sind. Aber am Ende fand ich eine allgemeine Lösung für jedes gerade n.
Die Permutation ist wie folgt:
0, N-1 .. N/2+1, 1 .. N/2
Für N = 10 wäre dies beispielsweise:
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
Diese Permutation hat eine weitere bemerkenswerte Eigenschaft: Sie hat immer eine Periode (für N> = 8) von 12, mit der Sie eine 12xN-Tabelle vorkonstruieren und von dort eine Ziffer nehmen können.
Hier ist ein Beispiel für die Implementierung der vorgeschlagenen Erweiterung des Verhuff-Algorithmus für base58 (genau genommen handelt es sich nicht um
Verkhuffs Algorithmus, sondern um dessen Verallgemeinerung). Keine vollständige Bibliothek, sondern sozusagen nur ein Dienstprogramm, ein Proof of Concept.
Den Beweis, dass diese Permutation die notwendige Eigenschaft hat und eine Periode von 12 hat, werde ich später liefern. Am Rand ist zu wenig Platz, um hier hinein zu passen.