Ülesanded täielikult lahendatud
-
49-tähemärgisest ASCII JSON andmestikust 68 tähemärgini ja tagasi 5 sammu
Sisend on
eyJuYW1lIjoiU3BvY2siLCJyb2xlIjoic2NpZW50aXN0IiwiYWN0aXZlIjp0cnVlfQ==ja selle all olev kasulik koormus on 49-märgine ASCII JSON{"name":"Spock","role":"scientist","active":true}. Paneelil on rida Characters 68 ja rida Bytes 68. Jõua arvuni 68 arvust 49 ilma kodeeritud sõnet loendamata — ning seejärel tagasi.-
Base64 on arvusüsteemi aluse vahetus, mitte šiffer. 64 = 26, seega kannab iga väljundmärk 6 bitti; 3 sisendbaiti kannavad 24 bitti ning 6 jagab arvu 24 ilma jäägita. See ongi kogu vorming: 3 baiti sisse, 4 märki välja, ilma jäägita.
-
49 baiti on 16 täielikku kolmikut, millele lisandub 1 ülejääv bait. Kolmikud on lihtne osa — 16 × 4 = 64 märki, millest igaüks kannab täielikku 6 bitti.
-
Üksikust baidist tekib täitepind. 8 bitti ei ole 6 kordne, seega täiendatakse seda 4 nullbitiga arvuni 12, mis moodustab 2 märki, ning 2 '='-märki lõpetavad kvarteti. 64 + 2 + 2 = 68. Iga '=' tähistab märgi positsiooni, millel polnud omaenda bitte.
-
Mõlemad paneeli read näitavad väärtust 68 ja see kattuvus ei ütle selle sõne kohta midagi. Base64 tähestik on ASCII, seega iga selle väljastatud märk on täpselt 1 bait; rida Bytes järgiks rida Characters mis tahes base64 sisendi korral.
-
Nüüd tee seda tagurpidi. 68 ÷ 4 = 17 kvartetti, 17 × 3 = 51 baidikohta, miinus 2 kohta, mida täide tunnistab tühjaks: 49. Sa taastasid just kasuliku koormuse suuruse ilma ühtegi selle baiti dekodeerimata.
Vastus
68 märki 49 baidi kohta ning '='-märgid on need, mis võimaldavad lugeda arvu 49 otse ümbriselt tagasi. See pööramine on kasulikum pool. Base64 sõne pikkus sõltub selle kasuliku koormuse pikkusest ega millestki muust, seega saad öelda täpse suuruse millelegi, mida sul pole lubatud avada — mis on tugevam väide kui ükski selle lehe detektor sisu kohta teeb. Teine pool on hind. 4 märki 3 baidi kohta ei parane kunagi, seega läheb base64 piirväärtuses maksma 4/3: 1 MiB fail saabub 1 398 104 märgina, millest 341 KiB on puhas pakend. See sõne käitub veelgi halvemini, suhtega 68/49 = 1,388, sest 2 täitemärki on fikseeritud lisatasu ning 49 baiti on liiga lühike, et seda laiali jaotada.
-
-
Juhuslikud bitid GUID/UUID v4-s ja enne kordumist loodud identifikaatorid 6 sammu
Sisend on
550e8400-e29b-41d4-a716-446655440000, mida paneel nimetab GUID/UUID v4-ks, pakkudes samas ka selle dekodeerimist Base64URL-ina. Arvuta välja, mitu selle bitti valiti tegelikult juhuslikult ning mitu sellist identifikaatorit saab luua, enne kui kordumine ei ole enam ebatõenäoline.-
Loenda esmalt kuju: 8-4-4-4-12 kuusteistkümnendsüsteemi numbrit koos 4 sidekriipsuga rühmade vahel, seega 32 + 4 = 36 märki, ning rida Bytes ühtib arvul 36, sest kuusteistkümnendsüsteemi numbrikohad ja sidekriipsud on kõik ASCII-s. Pane tähele, mida need 4 sidekriipsu väärt on. Need asuvad fikseeritud positsioonidel, seega kannavad need 0 bitti.
-
Iga kuusteistkümnendsüsteemi number on 4 bitti, seega need 32, mis arvesse lähedad, hoiavad 128 bitti. See on arv, mida tavaliselt UUID puhul mainitakse, ning selle sõne jaoks on see liiga suur.
-
Põhjuseks on 13. number ja 17. number. 13. number on 4 ja see on versiooniväli — versiooni 4 UUID on kohustatud panema sinna arvu 4, seega need 4 bitti ei olnud kunagi valik. 17. number on 'a', mis on kahendsüsteemis 1010, ja selle 2 esimest bitti on variandi märgend, fikseeritud väärtusele 10. Vormingu nimetamisele kulutatud 6 bitti jätab järele 122.
-
Ruum on seega 2122, umbes 5,32 × 1036 — mitte 3,40 × 1038, mida 128 bitti oleks andnud.
-
Kordumised järgivad pigem sünnipäevaparadoksi kui ruumi suurust. Juhuslikult n identifikaatorit valides kasvab mõne paari kattumise tõenäosus nagu n2/(2N) ning selle seadmine väärtusele 0,5 annab n = 1,177√N. Arv kasvab ruutjuurega, mistõttu 3. sammus kaotatud 6 bitti maksavad teguri 8, mitte teguri 64.
-
√N on 2,31 × 1018, seega n tulemuseks saadakse 2,7 × 1018.
Vastus
122 bitti ja 2,7 × 1018 UUID-d, enne kui mis tahes kordumise tõenäosus jõuab väärtuseni 0,5. Looduna kiirusega 109 sekundis teeb see 86 aastat ning see ongi kogu argument selle kasuks, et lasta igal masinal genereerida omaenda identifikaator ilma registri ja koordineerimiseta — mitte protokoll, vaid lihtsalt arv, mis on kättesaamiseks liiga suur. Aseta see esimese ülesande kõrvale ja see kontrast ongi see, milleks see leht on mõeldud. Base64 pakib 6 bitti igasse märki; see sõne kulutab 36 märki 122 bitile, mis on 3,4 bitti märgi kohta, seega samaväärne identifikaator mahuks 21 base64url-märki. Ülejäänud 15 ostavad loetavust, mitte informatsiooni. Ning paneeli pakutav Base64URL-dekodeerimine naaseb märgistatuna pigem binaarse kui tekstina kõige lihtsamal põhjusel: sinna polnud kunagi midagi kodeeritud, mida leida.
-
Allikad (1)
- The alphabets and padding rules the detector reasons about, normatively: S. Josefsson, "The Base16, Base32, and Base64 Data Encodings." RFC 4648, IETF, 2006.