Cannot understand Block Cipher example

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)

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.

$\|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)$
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.