Perché la codifica base64 richiede il riempimento se la lunghezza dell’input non è divisibile per 3?

Qual è lo scopo del riempimento nella codifica base64. Quello che segue è l’estratto di wikipedia:

“Viene assegnato un carattere pad aggiuntivo che può essere utilizzato per forzare l’output codificato in un multiplo intero di 4 caratteri (o equivalentemente quando il testo binario non codificato non è un multiplo di 3 byte), questi caratteri di riempimento devono essere eliminati durante la decodifica ma Permetti comunque il calcolo della lunghezza effettiva del testo non codificato, quando la sua lunghezza binaria di input non sarebbe un multiplo di 3 byte (l’ultimo carattere non pad è normalmente codificato in modo che l’ultimo blocco a 6 bit che rappresenta sia zero -aggiunta sui suoi bit meno significativi, al massimo due caratteri pad possono verificarsi alla fine del stream codificato). ”

Ho scritto un programma che potrebbe codificare in base64 qualsiasi stringa e decodificare qualsiasi stringa codificata in base64. Che problema risolve il riempimento?

La conclusione che il riempimento non è necessario è giusto. È sempre ansible determinare la lunghezza dell’input in modo non ambiguo dalla lunghezza della sequenza codificata.

Tuttavia, il riempimento è utile in situazioni in cui le stringhe codificate in base 64 sono concatenate in modo tale che le lunghezze delle singole sequenze vengano perse, come potrebbe accadere, ad esempio, in un protocollo di rete molto semplice.

Se le stringhe non imbottite sono concatenate, è imansible recuperare i dati originali perché le informazioni sul numero di byte dispari alla fine di ogni singola sequenza vengono perse. Tuttavia, se vengono utilizzate sequenze riempite, non c’è ambiguità e la sequenza nel suo complesso può essere decodificata correttamente.

Modifica: Un’illustrazione

Supponiamo di avere un programma che base64 codifica le parole, le concatena e le invia su una rete. Codifica “I”, “AM” e “TJM”, riunisce insieme i risultati senza riempimento e li trasmette.

  • I codifica su SQ ( SQ== con padding)
  • AM codifica su QU0 ( QU0= con padding)
  • TJM codifica su VEpN ( VEpN con padding)

Quindi i dati trasmessi sono SQQU0VEpN . Il ricevitore base64 decodifica questo come I\x04\x14\xd1Q) invece del previsto IAMTJM . Il risultato è privo di senso perché il mittente ha distrutto informazioni su dove termina ogni parola nella sequenza codificata. Se invece il mittente avesse inviato SQ==QU0=VEpN , il ricevitore avrebbe potuto decodificarlo come tre sequenze separate di base64 che si sarebbero concatenate per fornire IAMTJM .

Perché preoccuparsi di Padding?

Perché non progettare il protocollo solo per prefissare ogni parola con una lunghezza intera? Quindi il ricevitore poteva decodificare correttamente il stream e non ci sarebbe stato bisogno di imbottiture.

Questa è una grande idea, purché conosciamo la lunghezza dei dati che codifichiamo prima di iniziare a codificarli. Ma cosa succede se, invece di parole, codifichiamo pezzi di video da una telecamera live? Potremmo non sapere la lunghezza di ogni blocco in anticipo.

Se il protocollo utilizzato riempimento, non ci sarebbe alcuna necessità di trasmettere una lunghezza a tutti. I dati potrebbero essere codificati appena entrati dalla telecamera, ogni blocco terminato con padding e il ricevitore sarebbe in grado di decodificare il stream correttamente.

Ovviamente questo è un esempio molto elaborato, ma forse illustra perché il padding potrebbe essere utile in alcune situazioni.

Cosa sono i caratteri di riempimento?

I caratteri di riempimento aiutano a soddisfare i requisiti di lunghezza e non portano alcun significato.

Esempio decimale di riempimento: Dato il requisito arbitrario che tutte le stringhe siano lunghe 8 caratteri, il numero 640 può soddisfare questo requisito utilizzando gli 0 precedenti come caratteri di riempimento poiché non hanno alcun significato, “00000640”.

Codifica binaria

Il paradigma dei byte: il byte è l’unità di misura standard de facto e qualsiasi schema di codifica deve essere riferito ai byte.

Base256 si adatta esattamente a questo paradigma. Un byte è uguale a un carattere in base256.

Base16 , esadecimale o esadecimale, utilizza 4 bit per ogni carattere. Un byte può rappresentare due caratteri base16.

Base64 non si adatta uniformsmente al paradigma del byte, diversamente da base256 e base16. Tutti i caratteri base64 possono essere rappresentati in 6 bit, 2 bit in meno di un byte intero.

Possiamo rappresentare la codifica base64 rispetto al paradigma del byte come una frazione: 6 bit per carattere su 8 bit per byte . Ridotta questa frazione è di 3 byte su 4 caratteri.

Questo rapporto, 3 byte per ogni 4 caratteri base64, è la regola che vogliamo seguire durante la codifica base64. La codifica Base64 può promettere anche misurazioni con bundle a 3 byte, a differenza di base16 e base256 in cui ogni byte può stare in piedi da solo.

Quindi, perché il padding è incoraggiato anche se la codifica potrebbe funzionare senza i caratteri di riempimento? I personaggi del padding comunicano esplicitamente che quei punti extra dovrebbero essere vuoti e esclude qualsiasi ambiguità o bug potenzialmente sgradevoli. Il riempimento ci consente di decodificare la codifica base64 con la promise di non perdere i bit. Senza padding non c’è più il riconoscimento esplicito della misurazione in bundle a tre byte e non possiamo più garantire una riproduzione esatta della codifica originale senza ulteriori informazioni.

Esempi

Ecco il modulo di esempio RFC 4648 ( http://tools.ietf.org/html/rfc4648#section-8 )

Ogni carattere all’interno della funzione “BASE64” utilizza un byte (base256). Quindi lo traduciamo in base64.

 BASE64("") = "" (No bytes used. 0%3=0.) BASE64("f") = "Zg==" (One byte used. 1%3=1.) BASE64("fo") = "Zm8=" (Two bytes. 2%3=2.) BASE64("foo") = "Zm9v" (Three bytes. 3%3=0.) BASE64("foob") = "Zm9vYg==" (Four bytes. 4%3=1.) BASE64("fooba") = "Zm9vYmE=" (Five bytes. 5%3=2.) BASE64("foobar") = "Zm9vYmFy" (Six bytes. 6%3=0.) 

Ecco un encoder che puoi giocare con: http://www.motobit.com/util/base64-decoder-encoder.asp

Questa è solo una mia teoria, e non posso fornire alcuna fonte, ma penso che i caratteri padding servano solo a rendere alcune implementazioni dell’algoritmo di decodifica un po ‘più semplice. In particolare, se l’algoritmo inserisce la stringa codificata in qualcosa di simile a int[] il valore finale a volte sarà troppo lungo.

Se il padding è già presente nell’input, non è necessario fare altro: l’algoritmo può solo leggere e decodificare l’input.

Se l’algoritmo non è in grado di assumere il padding per essere presente, tuttavia, e utilizza la struttura dati int[] -like, quindi è necessario eseguire manualmente il rilievo dell’intero intero prima della decodifica, o eseguire un ulteriore contabilità sulla lunghezza originale dell’input.

Personalmente, non penso che il padding sia più funzionale a qualsiasi scopo, ma quando CPU e RAM non erano così abbondanti come ora potrebbe essere importante questa leggera ottimizzazione. Dubito che fosse importante … anche se … una buona implementazione avrebbe comunque dovuto fare qualcosa di sensato quando l’input nutrito veniva troncato in modo casuale, e che, IMO, avrebbe dato la possibilità di elaborare input non imbottiti senza costi aggiuntivi.