2
$\begingroup$

I learned modern block cipher and saw this example.

How many padding bits must be added to a message of 100 characters if 8-bit ASCII is used for encoding and the block cipher accepts blocks of 64 bits?

There was a solution, but I totally didn't understand.

Solution

Encoding 100 characters using 8-bit ASCII results in an 800-bit message. The plaintext must be divisible by 64. If |M| and |Pad| are the length of the message and the lengeth of the padding.

|M| + |Pad| = 0 mod 64 --> |Pad| = - 800 mod 64 --> 32 mod 64

What I'm curious are following questions..

  1. Why encoding 8 characters using 8-bit ASCII results in 800-bit message?
  2. What padding means?
  3. What last sentence means? (difficult to understand)
$\endgroup$
2
$\begingroup$

ASCII is a way to encode some characters (26 un-accentuated latin letters in both uppercase and lowercase, the 10 Arabic digits, space, 32 signs, 33 other typically non-printable characters, for a total of 128) into a block of 7 bits (which is enough since $2^7=128$ ).

It is customary to group bits by blocks of 8 (rather than 7) bits, called octets, or bytes. Byte tends to be the same as octet in modern computer science. In 8-bit ASCII, the supplementary bit is set to the fixed value 0.

It follows that encoding 100 characters using 8-bit ASCII results in a message of $m=8\times100=800$ bits.

When enciphering that using a block cipher in some common modes of operation (CBC, CTR, CFB, OFB…), it is necessary to group bits by blocks that can be processed by the block cipher. A 64-bit block can fit 8 characters per 8-bit ASCII. 800 is not a multiple of 64, therefore the 800 bits can not be enciphered directly.

Padding comes to the rescue: it adds $p$ extra bits (the padding bits, forming the padding), so that the total number of bits $m+p$ to be enciphered becomes a multiple of the block size $b$ and can be processed by the block cipier's mode of operation. Padding methods vary, but the most common ones will have $k\le p<k+b$ for some constant $k$, the most common methods having:

  • $k=0$ for "zero" or "no" padding
  • $k=1$ for "bit" padding
  • $k=8$ for various variants of "byte" padding

For $m=800$, $b=64$, and all three values of $k$, we'll get $p=32$, because $800+32=832$ bits fits 13 blocks of 64 bits.

The reasoning made:

$\|M\|+\|\text{Pad}\|\equiv0\pmod{64}\implies\|\text{Pad}\|=-800\bmod64=32\bmod64$

assumes $k=0$. It says that the combination of message $M$ of $\|M\|=m$ bits and $\text{Pad}$ of $\|\text{Pad}\|=p$ bits is a multiple of $b=64$. Therefore $m+p\equiv0\pmod b$. Therefore $p\equiv-m\pmod b$. Because $0\le p<b$ (which is where $k=0$ comes into play), that implies $p=-m\bmod b$.

More generally, the length of the padding is $p=k+b-1-((k+m-1)\bmod b)$ bit(s). If the question had considered a message of 96 characters ($m=768$), $p$ would be $0$ for $k=0$, and $64$ for $1\le k<8$.


Notations in modular arithmetic: for positive integer $n$ and any integers $x$ and $y$

  • the notation $y\equiv x\pmod n$ means that $x-y$ is a multiple of $n$
    This is read as y is equivalent to x, modulo n.
  • the notation $y=x\bmod n$ additionally means that $0\le y<n$
    This is read as y is equal to: x modulo n. Here, $\bmod$ is an operator. That's distinguishable by $\bmod$ not having an opening parenthesis immediately on its left; also, there is no $\equiv$ sign.
  • equivalently to the previous statement, $x\bmod n$ is the integer defined as
    • for non-negative $x$, the remainder of the Euclidean division of $x$ by $n$
    • for negative $x$, the integer $n-1-((1-x)\bmod n)$
$\endgroup$
2
$\begingroup$
  1. Why encoding 8 characters using 8-bit ASCII results in 800-bit message?

    That is not correct, 8 ASCII characters is 8-bytes times 8-bits per byte which is 64-bits.

    The question seems to be: Encoding 100 characters using 8-bit ASCII results in an 800-bit message.

    That is 100 ASCII characters is 100-bytes times 8-bits per byte is 800-bits.

  2. What padding means? Since block based encryption with a block mode such as ECB or CBC means that the input must a multiple of the block size because the data is processed one block at a time and partial blocks can not be processed.

  3. What last sentence means? (difficult to understand) Basically answered above.
    See Padding (cryptography)
    and especially: PKCS#5.

Note: ASCII is one 8-bit byte per character—only.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.