Was ist das Besondere an in der Kryptographie?

12

Im kleinen Verschlüsselungsalgorithmus :

Verschiedene Vielfache einer magischen Konstante werden verwendet, um einfache Angriffe aufgrund der Symmetrie der Runden zu verhindern. Die magische Konstante 2654435769 oder 9E3779B9 16 wird zu , wobei ϕ der goldene Schnitt ist .232/ϕ

Welche Eigenschaften hat , die es in diesem Zusammenhang nützlich machen?232/ϕ

MS Dousti
quelle
1
Möglicherweise relevant: en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
Charles

Antworten:

11

AFAIK, solche "magischen" Werte haben die folgenden zwei Eigenschaften:

  1. Sie sind irgendwie einzigartig und sehen zufällig aus.
  2. Sie können wiederholt an algebraischen Operationen teilnehmen. dh selbst nach mehrmaliger Anwendung einer bestimmten Operation (z. B. Multiplikation oder Exponentiation) kann der "magische" Wert immer noch neue Werte erzeugen.

Möglicherweise finden Sie einen ähnlichen Fall im MD5 . Betrachten Sie die folgende Zeile:

k[i] := floor(abs(sin(i + 1)) × (2 pow 32))

Hier sin(i + 1)sollen magische Werte erzeugt werden; die einzigartig sind, zufällig aussehen und für viele funktionieren können i. (Tatsächlich ireicht in 0..63).

Bearbeiten: Lesen Sie die Originalarbeit auf TEA , versteht man, dass die Antwort von "Steven Stadnicki" richtig ist. Beachten Sie, dass die magische Konstante der Name Delta ist:

In jeder Runde wird ein anderes Vielfaches von Delta verwendet, sodass sich kein Bit des Vielfachen häufig ändert. Wir vermuten, dass der Algorithmus nicht sehr empfindlich auf den Wert von Delta reagiert und wir müssen lediglich einen schlechten Wert vermeiden. Es ist anzumerken, dass sich Delta als ungerade mit Kürzung oder nächster Rundung herausstellt, so dass keine zusätzlichen Vorkehrungen erforderlich sind, um sicherzustellen, dass sich alle Ziffern der Summe ändern.

Da nur 32 Vielfache von Delta verwendet werden (eines pro Runde), ist es nicht ungewöhnlich, dass der Algorithmus für ein bestimmtes Delta nicht sehr empfindlich ist. (Weitere Informationen finden Sie in der Antwort von Steven Stadnicki.)

Edit 2: übrigens MD4 verwendet Quadratwurzeln 2 (0x5a827999) und 3 (0x6ed9eba1) als "magische" Konstanten in ihrer Tätigkeit. Abschnitt 5.4.4 des Buches Netzwerksicherheit: Private Kommunikation in einer öffentlichen Welt erklärt dies gut:

Um zu zeigen, dass die Designer nicht absichtlich einen teuflischen Wert für die Konstante gewählt haben, basiert die Konstante auf der Quadratwurzel von 2.

Diese Erklärung entspricht dem unten in einem Kommentar von Gilles gemachten Punkt.

MS Dousti
quelle
Klingt vernünftig. Hätte dann 2 ^ 32 / pi oder 2 ^ 32 / sqrt (2) genauso gut funktioniert?
@Tim: Ich denke schon, aber es ist wichtig, die neuen magischen Zahlen im Kontext der internen Operationen von TEA zu überprüfen.
MS Dousti
5
Ein Grund, eine mathematische Konstante wie 2 ^ 32 / phi anstelle eines zufällig generierten Werts mit akzeptablen Eigenschaften zu wählen, ist die Annahme, dass dies kein Wert ist, der für zusätzliche nicht offenbarte Eigenschaften ausgewählt wurde - ein Backdoor-Wert .
Gilles 'SO- hör auf böse zu sein'
2
@ Gilles, aus diesem Grund werden sie sogar "nothing up my sleeve number" genannt, siehe en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
Henno Brandsma
12

φnφφ{nφ}{nα}α

Cπ=232/π=1367130551(355Cπ)mod232=41157Cφ=232/φ=2654435769n|(nCφ)mod232|216n=28657XnXn+kk232

Steven Stadnicki
quelle
1
Sadeq: 'mod 1' bezieht sich auf den Bruchteil der Vielfachen - in diesem Fall wären dies [.62, .24, .85, .47, .09, .71, .33, .94, .56,. 18]. Gleichverteilung im Grenzwert bedeutet, dass jedes Teilintervall [a, b] von [0, 1] den erwarteten Anteil (ba) dieser Werte enthält; Während sich herausstellt, dass die gebrochenen Teile der Vielfachen einer irrationalen Zahl gleichmäßig auf [0, 1] verteilt sind, nähern sich diejenigen des Goldenen Schnitts dieser geraden Verteilung schneller an als jede andere Zahl; Sie „verklumpen“ nicht auf dem Einheitsintervall.
Steven Stadnicki
8
π113π{(n+113)π}{nπ}
8
Das ist eine sehr nette Eigenschaft des Goldenen Schnitts
Suresh Venkat
2
Danke für die tolle Beschreibung. Es war wirklich toll! Haben Sie Kommentare zu k[i], wie in MD5 definiert? (Siehe meine Antwort oben.)
MS Dousti
2
Sünde(nx)xeinichΣeinichk[ich]=0