Zum Inhalt gehen

Binärrotation: Ein Data-Science-Fall für Codierungs- und Zahlentheorie

Dr. Eldar Sultanow
2022-02-17

Binärrotation spielt in der Kryptographie eine Rolle, denn wir können uns diese Rotation als algebraische Operation genauso wie einen LFSR (Abkürzung von linear feedback shift register, auf Deutsch: linear rückgekoppeltes Schieberegister) vorstellen.

Die Rotation ist vor allem dann für die Kryptographie nützlich, wenn sie mit anderen gängigen bitweisen Operationen (z. B. AND, OR, XOR, NAND, NOR) kombiniert wird. Viele symmetrische kryptografische Verfahren (Hashes, Blockchiffren usw.) nutzen diese Rotation.

Mehr dazu bietet dieser Artikel. Kryptographie ist wichtig zum Schutz der Vertraulichkeit, Geheimhaltung und Integrität von Daten. Wir sehen Möglichkeiten, bestehende Verschlüsselungsverfahren von Informationen hinsichtlich ihrer Schnelligkeit zu optimieren und darüber hinaus neue Wege für eine möglicherweise effizientere Verschlüsselung aufzuzeigen.

Eine der derzeit wichtigsten Methoden für die Kryptographie ist LFSR. Darüber hinaus findet LFSR bereits in vielen verschiedenen Zustandsautomaten Anwendung, wie beispielsweise in Haushaltsgeräten, Mobiltelefonen oder auch Autos. Allgemein wird es in der digitalen Signalverarbeitung eingesetzt, etwa im Rahmen von Direct-Sequence-Spread-Spectrum-Verfahren (DSSS) bzw. – damit verwandt – im Bereich Codemultiplexverfahren (CDMA). Durch sogenannte zusammengesetzte LFSR werden dabei serielle Schaltungen gebildet und beispielsweise im Global Positioning System (GPS) zu Navigationszwecken eingesetzt.

Der Einsatzbereich von Schieberegistern ist nahezu unbegrenzt. Auch Apple etwa hat dieses Thema aufgegriffen und bereits im Jahr 2013 ein erstes Patent für eine Einweg-Hashing-Funktion angemeldet, da die Algorithmen immer wichtiger werden.

Äquivalenzklassen optimieren die Binärrotations-basierte Codierung

Eine Möglichkeit zur Optimierung von LFSR sehen wir in einer von Grosek and Hromada eingeführten Methode zur Bestimmung von Äquivalenzklassen. Hierzu war uns zunächst eine zyklische Periodizität in unseren Daten aufgefallen, die bei allen verschiedenen „geshifteten“ Versionen eines binären Worts auftaucht. Mithilfe der Äquivalenzklassen können wir nun eine einzige repräsentative Konstante (im Paper Konstante C genannt) für alle geschifteten Versionen eines binären Worts definieren.

Damit lassen sich alle möglichen Berechnungen deutlich effizienter gestalten, indem man eine komplexe Berechnung einmal für die Urform des binären Worts berechnet und das Ergebnis im Anschluss auf alle anderen Elemente in derselben Äquivalenzklasse ableiten kann.

Aus 2L binären Wörtern für eine Länge L können wir somit die nötigen Berechnungen auf die Anzahl der Äquivalenzklassen C(L,N1(B),d) reduzieren.

Bei einer Länge von z. B. 6 Bits pro Binär-Wort, also 26 = 64, können wir die Anzahl an Rechnungen somit auf
C(6,N1,d) = 13 Konstanten reduzieren. Das verspricht eine Rechenleistungsreduktion von (13*100) ⁄ 64 = 20,31 %.

Einen anderen Zusammenhang mit der Binärrotation hat die Collatz-Vermutung, ein notorisch schwieriges Matheproblem, das bis heute ungelöst ist.

Die Collatz-Vermutung: Millionen-Dollar-Problem, das extrem einfach beschreibbar ist, aber mit momentan vorhandenen mathematischen Mitteln kaum lösbar zu sein scheint

Manche mathematischen Probleme sind so schwer zu lösen, dass ein Kopfgeld auf sie ausgesetzt ist. Eines dieser „Millionen-Dollar-Probleme“ ist die Collatz-Vermutung[1]: ein zahlentheoretisches Problem, das schon zahllose Forscher vor Rätsel gestellt hat. All ihre Lösungsansätze – seien es graphentheoretische, probabilistische Ansätze oder welche aus der abstrakten Algebra und Zahlentheorie – haben sich stets als unbrauchbar erwiesen. Bisher gibt es keine Lösung.

Zu beschreiben ist das Problem dagegen ganz einfach: Wir betrachten die folgende Zahlenfolge: Nimm eine Zahl n. Das nächste Zahlenfolgeglied ist n/2, falls n gerade ist, ansonsten 3n+1. Beispiel: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ….

Am Ende, nachdem wir die 1 erreicht haben, verfängt sich die Folge in einem Zyklus: 4, 2, 1. Die Vermutung besagt: Egal mit welcher Zahl ich anfange – wie groß die auch immer ist – wir landen bei der 1. Es gibt nur diesen trivialen Zyklus und keinen anderen.

Jetzt kommt der Witz: ändern wir die Zahlenfolge etwas ab, statt 3n+1 zu z. B. 3n+13, dann bekommen wir sehr wohl Zyklen: 319,485,734,367,557,842,421,638.

Probiert‘s mal aus: (319*3+13)/2 = 485, dann weiter (485*3+13)/2 = 734. So, jetzt können wir direkt wieder durch 2 teilen und haben 367, das dann wieder (367*3+13)/2 = 557….und ganz zum Schluss landen wir erneut bei 319.

Zu genau solchen Zyklen können wir eine Brücke von der Rotation von Binärzahlen aus schlagen – und die Collatz-Zahlenfolge verallgemeinern: von 3n+1 zu 3n+c. Eben im Beispiel hatten wir c = 13.

Linksrotation von Binärzahlen erzeugt Zyklen der verallgemeinerten Collatz-Folgen 3n+c

Die Binärrotation und die dahinter liegenden Zyklen können wir mithilfe von Data Science analysieren – genaueres dazu auf heise.de. Data Science ermöglicht ermöglicht das Aufdecken von Zusammenhängen zwischen Daten, die als Zahlen vorliegen. Als Beispiel wollen wir die Rotation einer Binärzahl nehmen und folgenden Sachverhalt explorativ ergründen:

Auf einer Binärzahl B der Länge L mit U Einsen[2] kann eine Linksrotation durchgeführt werden, wobei sich eine minimale Binärzahl Bmin und maximale Binärzahl Bmax ermitteln lässt. Nehmen wir zum Beispiel die Binärzahl 10110101 = 181. Das Minimum Bmin = 01011011 = 91 und das Maximum Bmax = 11011010 = 218.

Das Maximum Bmax kann durch drei Linksrotationen des Minimums Bmin erreicht werden und die Zahl R=3 bezeichnen wir als die Linksrotations-Distanz zwischen dem Minimum und Maximum. Diese Rotationsdistanz ist Untersuchungsgegenstand in dieser Aufgabe. Grundsätzlich gilt:

In unserem Beispiel bedeutet das 91 = (218×28-3) mod (255).

Wir untersuchen die Teilbarkeit:

In unserem Einführungsbeispiel stimmt diese Teilbarkeit, denn 8 teilt 5×3+1 offensichtlich. Für welche Fälle stimmt diese Teilbarkeit noch? Wie identifiziere, untersuche und visualisieren ich Zusammenhänge?

Die Länge L von Bmax und das Hamming-Gewicht U können wir auch direkt berechnen. Nehmen wir wieder das Beispiel aus der Einführung Bmax = 11011010 = 218:

Wir definieren die Funktion z, welche eine Binärzahl B mit einem Hamming-Gewicht U als Input bekommt:

wobei 0≤x1<x2<…<xU≤L-1 die mit Eins belegten Positionen (Null-basierte Indizierung) der Binärzahl B sind. Im Einführungsbeispiel haben wir z(Bmax) = z(11011010) = 319 und die fünf mit Eins belegten Positionen sind (x1,x2,x3,x4,x5) = (0,1,3,4,6). Konkret ist 319 = 3420+3321+3223+3124+3026.

Auf gleiche Weise erhalten wir z(Bmin) = 842. Beide Zahlen, die 319 und die 842 gehören dem Zyklus 3n+13 an, der durch die folgende Funktion entsteht:

Der Parameter c ergibt sich aus der Differenz c = 2L-3U und ist damit in unserem Fall 13. Die periodische Sequenz ist schließlich 319,485,734,367,557,842,421,638. Die zu untersuchende Teilbarkeit L|U×R+1 scheint immer für solche periodischen Sequenzen gegeben zu sein.

So scheint die zu untersuchende Teilbarkeit immer für solche periodischen Sequenzen gegeben zu sein. Diese Sequenzen lassen sich in Python schnell als Panda-Dataframe erzeugen (siehe Abbildung 1).

Abbildung 1: DataFrame mit generierten Zyklen. Unser Beispiel aus dem Text ist hervorgehoben.

Den Differenzquotienten berechnet man mit DataFrame.diff(). Die Funktion diff berechnet die Differenz eines DataFrame-Elements zum Element in der vorherigen Zeile des DataFrames. Im vorliegenden Fall nutzt man diese Funktion, um die Differenzen aufeinanderfolgender Bmin-Werte (∆Bmin) und Bmax-Werte (∆Bmax) zu ermitteln. Ordnet man nun dem ∆Bmin das entsprechende ∆Bmax einer jeden Zeile des DataFrames zu, entstehen zwei Diagramme (s. Abbildung 2). Auf der linken Seite sind die Daten sortiert nach der Rotationsdistanz r und auf der rechten Seite nach der Differenz Bmax – Bmin.

Abbildung 2: Die Verteilung rotierender Binärzahlen aus zwei unterschiedlichen Perspektiven.

Kryptographie und Zahlentheorie sind tatsächlich auch interessant, um mit Data Science angegangen zu werden. Python verfügt über dafür geeignete Mittel, wie algebraische Funktionen, Bitoperationen und vieles mehr. Wir haben einen Zusammenhang zwischen der Binärrotation und Kryptographie sowie zu dem bis dato ungelösten Collatz-Problem hergestellt.

Im Artikel „Rotating Binaries“ habe ich das Verhalten rotierender Binärzahlen gemeinsam mit Co-Autoren ausführlicher beschrieben. Der Artikel ist in der wissenschaftlichen Publikation AppliedMath erschienen und online frei verfügbar.

Sie haben Fragen oder Anregungen? Dann freue ich mich, von Ihnen zu hören. Melden Sie sich sehr gern auch bei mir, wenn Sie Spaß an Mathematik haben und sie praktisch einsetzen möchten.

[1] S. W. Williams. “Million Buck Problems”. In: National Association of Mathematicians Newsletter 31.2 (2000), pp. 1–3.

[2] Die Anzahl U der Einsen in einer Binärzahl nennt man auch Hamming-Gewicht.

Autor

Dr. Eldar Sultanow

Enterprise Architecture
Dr. Eldar Sultanow ist als Architekt tätig. Er hat langjährige Praxiserfahrung in der Softwareindustrie, insbesondere in den Bereichen JEE, Electronic/Mobile Commerce, Track-&-Trace und Auto-ID im Pharmabereich. In einem zwischenstaatlichen Projekt hat er eine Plattform mit konzipiert, an der internationale Finanzinstitute angeschlossen sind. Aktuell ist Eldar Sultanow als technischer Chefdesigner in einem der größten öffentlichen IT-Verfahren aktiv, das hunderttausende Transaktionen pro Tag mit einem Jahresvolumen von über 25 Milliarden EUR vollzieht.

    Weitere Blogposts

    Daten & Künstliche Intelligenz

    First 100 Days of a Chief Data Officer

    Ingo Finck
    3 Aug. 2022
    Daten & Künstliche Intelligenz, Sustainability

    Wie klimaresilient sind unsere Städte – müssen wir umdenken?

    Markus Pütz
    27 Juli 2022
    Daten & Künstliche Intelligenz, Transformation & Innovation

    Digital (T)win – Welche konkreten Anwendungsfälle und Mehrwerte stecken hinter dem Buzzword wirklich?

    Svenja Dreger
    21 Juli 2022