Pourquoi l'encodage base64 nécessite-t-il un remplissage si la longueur de l'entrée n'est pas divisible par 3 ?

Question

A quoi sert le padding dans l'encodage base64. Voici un extrait de wikipedia :

"Un caractère de remplissage supplémentaire est attribué et peut être utilisé pour forcer la sortie codée dans un multiple entier de 4 caractères (ou de manière équivalente lorsque le texte binaire non codé n'est pas un multiple de 3 octets) ; ces caractères de remplissage doivent ensuite être éliminés lors du décodage, mais permettent toujours le calcul de la longueur effective du texte non codé, lorsque sa longueur binaire d'entrée n'est pas un multiple de 3 octets (le dernier caractère de remplissage est normalement codé de manière à ce que le dernier bloc de 6 bits qu'il représente soit mis à zéro sur ses bits les moins significatifs, deux caractères de remplissage au maximum peuvent se produire à la fin du flux codé). "

J'ai écrit un programme qui peut encoder en base64 n'importe quelle chaîne et décoder n'importe quelle chaîne encodée en base64. Quel problème le padding résout-il ?

Answer 1

Vous avez raison de conclure que le rembourrage n'est pas nécessaire. Il est toujours possible de déterminer la longueur de l'entrée sans ambiguïté à partir de la longueur de la séquence codée.

Cependant, le remplissage est utile dans les situations où les chaînes encodées en base64 sont concaténées de telle manière que les longueurs des séquences individuelles sont perdues, comme cela peut se produire, par exemple, dans un protocole de réseau très simple.

Si sans rembourrage sont concaténées, il est impossible de récupérer les données d'origine car l'information sur le nombre d'octets impairs à la fin de chaque séquence individuelle est perdue. En revanche, si l'on utilise des séquences matelassées, il n'y a pas d'ambiguïté et la séquence dans son ensemble peut être décodée correctement.

Editer : une illustration

Supposons que nous ayons un programme qui code des mots en base64, les concatène et les envoie sur un réseau. Il encode "I", "AM" et "TJM", concatène les résultats sans rembourrage et les transmet.

• I est codé en SQ ( SQ== avec remplissage)
• AM est codé en QU0 ( QU0= avec remplissage)
• TJM est codé en VEpN ( VEpN avec remplissage)

Les données transmises sont donc SQQU0VEpN . Le récepteur le décode en base64 comme suit I\x04\x14\xd1Q) au lieu de la valeur prévue IAMTJM . Le résultat est absurde car l'expéditeur a détruit les informations sur l'endroit où se termine chaque mot dans la séquence codée. Si l'expéditeur avait envoyé SQ==QU0=VEpN Au lieu de cela, le récepteur aurait pu décoder ceci comme trois séquences base64 distinctes qui se concaténeraient pour donner IAMTJM .

Pourquoi s'embêter avec le rembourrage ?

Pourquoi ne pas simplement concevoir le protocole de manière à ce que chaque mot soit précédé d'une longueur entière ? Le récepteur pourrait alors décoder le flux correctement et il n'y aurait pas besoin de remplissage.

C'est une excellente idée, à condition que nous savoir la longueur des données que nous encodons avant de commencer à les encoder. Mais que se passerait-il si, au lieu de mots, nous encodions des morceaux de vidéo provenant d'une caméra en direct ? Il se peut que nous ne connaissions pas la longueur de chaque morceau à l'avance.

Si le protocole utilisait le remplissage, il ne serait pas nécessaire de transmettre une longueur. Les données pourraient être encodées au fur et à mesure qu'elles arrivent de la caméra, chaque morceau se terminant par un tampon, et le récepteur serait en mesure de décoder le flux correctement.

Il s'agit évidemment d'un exemple très artificiel, mais il illustre peut-être la raison pour laquelle le rembourrage pourrait être utile dans certaines situations.

Answer 2

Dans le même ordre d'idées, voici un convertisseur de base arbitraire que j'ai créé pour vous. Bonne lecture ! https://convert.zamicol.com/

Qu'est-ce qu'un caractère de remplissage ?

Les caractères de remplissage permettent de satisfaire aux exigences de longueur et n'ont pas d'autre signification.

Décimale Exemple de remplissage : Compte tenu de l'exigence arbitraire selon laquelle toutes les chaînes de caractères doivent avoir une longueur de 8 caractères, le nombre 640 peut répondre à cette exigence en utilisant les 0 précédents comme caractères de remplissage puisqu'ils n'ont pas de signification, "00000640".

Encodage binaire

Le paradigme de l'octet : Pour l'encodage, l'octet est l'unité de mesure standard de facto et tout système doit se référer aux octets.

Base256 s'inscrit exactement dans le paradigme de l'octet. Un octet est égal à un caractère en base256.

Base16 Le format hexadécimal, ou hex, utilise 4 bits pour chaque caractère. Un octet peut représenter deux caractères en base16.

Base64 ne s'inscrit pas uniformément dans le paradigme de l'octet (pas plus que la base32), contrairement à la base256 et à la base16. Tous les caractères de base64 peuvent être représentés sur 6 bits, soit 2 bits de moins qu'un octet complet.

Nous pouvons représenter l'encodage base64 par rapport au paradigme de l'octet sous la forme d'une fraction : 6 bits par caractère plus de 8 bits par octet . Réduite, cette fraction est de 3 octets sur 4 caractères.

Ce ratio, 3 octets pour 4 caractères base64, est la règle à suivre lors de l'encodage base64. L'encodage Base64 ne peut promettre une mesure égale qu'avec des paquets de 3 octets, contrairement à la base16 et à la base256 où chaque octet est indépendant.

Donc pourquoi Le remplissage est-il encouragé alors que l'encodage pourrait très bien fonctionner sans les caractères de remplissage ?

Si la longueur d'un flux est inconnue ou s'il peut être utile de savoir exactement quand un flux de données se termine, utilisez le remplissage. Les caractères de remplissage indiquent explicitement que ces espaces supplémentaires doivent être vides et éliminent toute ambiguïté. Même si la longueur est inconnue, vous saurez où se termine votre flux de données.

À titre de contre-exemple, certaines normes telles que JOSE n'autorisent pas les caractères de remplissage. Dans ce cas, s'il manque quelque chose, une signature cryptographique ne fonctionnera pas ou d'autres caractères non base64 seront manquants (comme le "."). Bien que les hypothèses sur la longueur ne soient pas faites, le remplissage n'est pas nécessaire car s'il y a quelque chose d'incorrect, cela ne fonctionnera tout simplement pas.

Et c'est exactement ce que la base64 Le RFC dit,

Dans certaines circonstances, l'utilisation du remplissage ("=") dans les données codées en base n'est pas nécessaire ou n'est pas utilisée. Dans le cas général, lorsqu'il n'est pas possible de faire des hypothèses sur la taille des données transportées ne peut être supposée, le remplissage est nécessaire pour pour obtenir des données décodées correctes.

[...]

Le pas de remplissage en base 64 [...] s'il est incorrectement mal implémentée, conduit à des altérations non significatives des données encodées. Par exemple, si l'entrée n'est que d'un octet pour un codage en base 64, tous les six bits du premier symbole sont utilisés, mais seulement les deux premiers deux premiers bits du symbole suivant. Ces bits de remplissage DOIVENT être mis à zéro par les codeurs conformes, ce qui est décrit dans les descriptions sur le remplissage ci-dessous. Si cette propriété n'est pas respectée, il n'y a pas de représentation canonique des données codées en base, et plusieurs chaînes codées en base peuvent être décodées. peuvent être décodées dans les mêmes données binaires. Si cette (et d'autres discutées dans ce document), un codage canonique est garanti. est garanti.

Le padding nous permet de décoder l'encodage base64 avec la promesse de ne pas perdre de bits. Sans padding, il n'y a plus de reconnaissance explicite de la mesure en paquets de trois octets. Sans padding, il se peut que vous ne puissiez pas garantir la reproduction exacte de l'encodage original sans informations supplémentaires provenant généralement d'un autre endroit de votre pile, comme TCP, les sommes de contrôle ou d'autres méthodes.

L'alternative aux systèmes de conversion par seau comme base64 est la suivante conversion des radix qui n'a pas de taille de godet arbitraire et qui, pour les lecteurs de gauche à droite, est rembourré à gauche. Les "division itérative par radix". est généralement utilisée pour les conversions de radix.

Exemples

Voici l'exemple du formulaire RFC 4648 ( https://www.rfc-editor.org/rfc/rfc4648#section-8 )

Chaque caractère à l'intérieur de la fonction "BASE64" utilise un octet (base256). Nous le traduisons ensuite en 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)

Voici un encodeur avec lequel vous pouvez jouer : http://www.motobit.com/util/base64-decoder-encoder.asp

Answer 3

Il n'y a pas beaucoup d'avantages à en tirer à l'heure actuelle. Il s'agit donc de se demander ce que le original historique a pu être.

Le codage Base64 apparaît pour la première fois dans RFC 1421 datant de 1993. Ce RFC est en fait axé sur le cryptage du courrier électronique, et base64 est décrit dans une petite section 4.3.2.4 .

Ce RFC n'explique pas la raison d'être de ce rembourrage. La phrase suivante est celle qui se rapproche le plus d'une mention de l'objectif initial :

Un quantum d'encodage complet est toujours effectué à la fin d'un message.

Elle ne suggère pas la concaténation (la meilleure réponse ici), ni la facilité de mise en œuvre en tant qu'objectif explicite du remplissage. Toutefois, si l'on considère l'ensemble de la description, il n'est pas déraisonnable de supposer que le but était d'aider le décodeur à lire l'entrée en unités de 32 bits ( "quanta ). Cela ne présente aucun intérêt aujourd'hui, mais en 1993, un code C non sécurisé aurait très probablement tiré parti de cette propriété.

Answer 4

Avec le padding, une chaîne base64 a toujours une longueur qui est un multiple de 4 (si ce n'est pas le cas, la chaîne a été corrompue à coup sûr) et le code peut donc facilement traiter cette chaîne dans une boucle qui traite 4 caractères à la fois (en convertissant toujours 4 caractères d'entrée en trois octets de sortie ou moins). Le remplissage facilite donc la vérification de la cohérence ( length % 4 != 0 ==> erreur n'est pas possible avec le remplissage) et rend le traitement plus simple et plus efficace.

Je sais ce que les gens vont penser : même sans padding, je peux traiter tous les morceaux de 4 octets dans une boucle et ajouter un traitement spécial pour les 1 à 3 derniers octets, s'ils existent. Il ne s'agit que de quelques lignes de code supplémentaires et la différence de vitesse sera trop minime pour être mesurée. C'est probablement vrai, mais vous pensez en termes de C (ou de langages supérieurs) et d'une unité centrale puissante avec beaucoup de mémoire vive. Qu'en est-il si vous devez décoder base64 au niveau matériel, en utilisant un simple DSP, dont la puissance de traitement est très limitée, qui n'a pas de mémoire vive et qui doit écrire le code dans un micro-assemblage très limité ? Et si vous ne pouvez pas utiliser de code du tout et que tout doit être fait avec des transistors empilés les uns sur les autres (une implémentation matérielle câblée) ? Avec le rembourrage, c'est beaucoup plus simple que sans.

Answer 5

Le padding remplit la longueur de sortie à un multiple de quatre octets d'une manière définie.