Aufgaben vollständig gelöst
-
Von einem 49-Zeichen ASCII-JSON-Payload zu 68 Zeichen und zurück 5 Schritte
Die Eingabe lautet
eyJuYW1lIjoiU3BvY2siLCJyb2xlIjoic2NpZW50aXN0IiwiYWN0aXZlIjp0cnVlfQ==, und die Nutzlast darunter ist das 49-Zeichen-ASCII-JSON{"name":"Spock","role":"scientist","active":true}. Das Bedienfeld zeigt 68 für Zeichen und 68 für Bytes. Kommen Sie von der 49 auf 68, ohne die codierte Zeichenkette zu zählen — und kehren Sie dann zurück.-
Base64 ist ein Basiswechsel, keine Verschlüsselung. 64 = 26, sodass jedes Ausgabezeichen 6 Bits trägt; 3 Eingabe-Bytes tragen 24; und 6 teilt 24 exakt. Das ist das gesamte Format: 3 Bytes hinein, 4 Zeichen heraus, kein Rest.
-
49 Bytes sind 16 vollständige Tripel mit 1 verbleibenden Byte. Die Tripel sind der einfache Teil — 16 × 4 = 64 Zeichen, von denen jedes einzelne volle 6 Bits trägt.
-
Das verwaiste Byte ist die Ursache für das Padding. 8 Bits sind kein Vielfaches von 6, daher wird es mit 4 Nullbits auf 12 aufgefüllt, was 2 Zeichen entspricht, und 2 '='-Zeichen vervollständigen das Quartett. 64 + 2 + 2 = 68. Jedes '=' markiert eine Zeichenposition, die keine eigenen Bits hatte.
-
Beide Zeilen des Bedienfelds zeigen 68, und diese Übereinstimmung sagt nichts über diese Zeichenkette aus. Das Base64-Alphabet ist ASCII, sodass jedes von ihm ausgegebene Zeichen genau 1 Byte groß ist; die Zeile Bytes würde für jede beliebige Base64-Eingabe der Zeile Zeichen folgen.
-
Nun kehren Sie es um. 68 ÷ 4 = 17 Quartette, 17 × 3 = 51 Byte-Plätze, abzüglich der 2 Plätze, von denen das Padding angibt, dass sie leer sind: 49. Sie haben soeben die Größe der Nutzlast wiederhergestellt, ohne ein einziges Byte davon zu decodieren.
Antwort
68 Zeichen für 49 Bytes, und die '='-Zeichen ermöglichen es Ihnen, die 49 direkt von der Hülle abzulesen. Diese Umkehrung ist die nützliche Hälfte. Die Länge einer Base64-Zeichenkette hängt von der Länge ihrer Nutzlast ab und von sonst nichts. Sie können also die genaue Größe von etwas angeben, das Sie nicht öffnen dürfen — was eine stärkere Aussage ist, als sie jeder Detektor auf dieser Seite über den Inhalt trifft. Die andere Hälfte ist die Rechnung. 4 Zeichen pro 3 Bytes verbessern sich nie, sodass Base64 im Grenzfall 4/3 kostet: Eine 1-MiB-Datei kommt als 1.398.104 Zeichen an, 341 KiB reines Verpackungsmaterial. Diese Zeichenkette schneidet mit 68/49 = 1,388 schlechter ab, da die 2 Padding-Zeichen einen festen Aufschlag darstellen und 49 Bytes viel zu kurz sind, um diesen zu relativieren.
-
-
Zufällige Bits in einer GUID/UUID v4 und generierte Identifikatoren vor einer Wiederholung 6 Schritte
Die Eingabe lautet
550e8400-e29b-41d4-a716-446655440000, was das Bedienfeld als GUID/UUID v4 bezeichnet, während es gleichzeitig anbietet, sie als Base64URL zu decodieren. Ermitteln Sie, wie viele ihrer Bits tatsächlich zufällig gewählt wurden und wie viele solcher Bezeichner erzeugt werden können, bevor eine Wiederholung nicht mehr unwahrscheinlich ist.-
Zählen Sie zuerst die Form: 8-4-4-4-12 Hexadezimalziffern mit 4 Bindestrichen zwischen den Gruppen, also 32 + 4 = 36 Zeichen, und die Zeile Bytes stimmt bei 36 überein, da Hexadezimalziffern und Bindestriche alle ASCII sind. Beachten Sie, was diese 4 Bindestriche wert sind. Sie befinden sich an festen Positionen, tragen also 0 Bits.
-
Jede Hexadezimalziffer entspricht 4 Bits, sodass die 32 relevanten Ziffern 128 Bits enthalten. Das ist die Zahl, die gewöhnlich für eine UUID genannt wird, und für diese Zeichenkette ist sie zu hoch.
-
Ziffer 13 und Ziffer 17 sind der Grund dafür. Ziffer 13 ist 4 und bildet das Versionsfeld — eine UUID der Version 4 ist verpflichtet, dort eine 4 zu setzen, sodass diese 4 Bits nie zur Wahl standen. Ziffer 17 ist 'a', was binär 1010 entspricht, und ihre ersten 2 Bits sind das Varianten-Tag, das auf 10 festgelegt ist. 6 Bits, die für die Benennung des Formats aufgewendet werden, lassen 122 übrig.
-
Der Raum umfasst daher 2122, etwa 5,32 × 1036 — nicht die 3,40 × 1038, die 128 Bits ergeben hätten.
-
Wiederholungen folgen dem Geburtstagsproblem und nicht der Größe des Raumes. Wählt man n Bezeichner zufällig aus, wächst die Wahrscheinlichkeit, dass ein Paar übereinstimmt, wie n2/(2N); setzt man dies gleich 0,5, erhält man n = 1,177√N. Die Anzahl skaliert mit der Quadratwurzel, weshalb die in Schritt 3 verlorenen 6 Bits einen Faktor 8 und nicht einen Faktor 64 kosten.
-
√N ist 2,31 × 1018, sodass n bei 2,7 × 1018 liegt.
Antwort
122 Bits und 2,7 × 1018 UUIDs, bevor die Wahrscheinlichkeit einer Wiederholung 0,5 erreicht. Bei einer Erzeugungsrate von 109 pro Sekunde entspricht das 86 Jahren, und das ist das gesamte Argument dafür, jede Maschine ihre eigenen Bezeichner ohne Registrierungsstelle und ohne Koordinierung generieren zu lassen — kein Protokoll, sondern einfach eine Zahl, die zu groß ist, um erreicht zu werden. Stellt man dies neben das erste Problem, wird der Kontrast deutlich, um den es auf dieser Seite geht. Base64 packt 6 Bits in jedes Zeichen; diese Zeichenkette wendet 36 Zeichen für 122 Bits auf, was 3,4 Bits pro Zeichen entspricht. Derselbe Bezeichner würde also in 21 Base64URL-Zeichen passen. Die anderen 15 kaufen Lesbarkeit, keine Information. Und die vom Bedienfeld angebotene Base64URL-Decodierung wird aus dem einfachsten denkbaren Grund als binär statt als Text gekennzeichnet: Es wurde dort nie etwas codiert, das man finden könnte.
-
Quellen (1)
- The alphabets and padding rules the detector reasons about, normatively: S. Josefsson, "The Base16, Base32, and Base64 Data Encodings." RFC 4648, IETF, 2006.