1

Ok this is for Base $64$ padding.

The length of Base $64$ representation of a sequence of bytes is represented by $\left\lceil \frac{4N}{3} \right\rceil$

The padding should add $M$ characters such that $$\frac{\left(\left\lceil \frac{4N}{3} \right\rceil + M \right)}{4}=0.$$

How can I prove that $M\ne 1$ for all values of $N > 0$?

I created the sequence in Excel and the sequence is $2,3,4,6,7,8,10$ which means the difference is $1-1-2$ that repeats itself. It seems that the number skipped is always $4N+1$ but how to come to this conclusion?

Hendrix
  • 1,426
Andrew Tan
  • 11
  • Welcome to MSE. Please edit and use MathJax to properly format math expressions. – Lee David Chung Lin Jul 13 '19 at 03:51
  • You mean modulo $4$ in your equation, not divided by $4$, I think. – Henno Brandsma Jul 13 '19 at 04:38
  • Huh? If $N = 3k+2$ then you do have $M \equiv 1 \pmod 4$. $\lceil \frac{4(3k+2)}3\rceil + (1 + 4j)= \lceil 4k + \frac 83\rceil + (1+ 4j) = (4k + 3) + (1 + 4j) = 4(k + j + 1) \equiv 0 \pmod 4$. What exactly are you asking. If you literally mean that $M = -\lceil \frac {4N}3\rceil$ and that $M$ not equal to $1$ welll, that's obvious because $M < 0$. – fleablood Jul 13 '19 at 06:43
  • Did you mean floor instead of ceiling? – fleablood Jul 13 '19 at 06:44

3 Answers3

3

For any $n$, we have either $n=3m$, $n=3m+1$, or $n=3m+2$. Then we just have three cases to consider:

\begin{align*} \left\lceil \frac{4n}{3} \right\rceil &= \left\lceil 4m \right\rceil = 4m \equiv 0 \pmod 4 \\ \left\lceil\frac{4n}{3} \right\rceil &= \left\lceil 4m+\frac{4}{3} \right\rceil =4m+2 \equiv 2 \pmod 4 \\ \left\lceil \frac{4n}{3} \right\rceil &= \left\lceil 4m+\frac{8}{3} \right\rceil =4m+3 \equiv 3 \pmod 4 \end{align*}

Hendrix
  • 1,426
Sambo
  • 6,243
1

Assume for a contradiction that $$\left\lceil\frac{4N}3\right\rceil\equiv1\pmod4;$$ that is, there is an integer $k$ such that $$\left\lceil\frac{4N}3\right\rceil=4k+1.$$ Equivalently, $$4k\lt\frac{4N}3\le4k+1.$$ Multiplying everything by the positive number $\frac34$, it follows that $$3k\lt N\le3k+\frac34\lt3k+1,$$ i.e., $$3k\lt N\lt3k+1.$$ This is impossible; since $3k$ is an integer, there is no integer between $3k$ and $3k+1$.

bof
  • 78,265
0

Divide your data in groups of three bytes. How many bytes are left at the end can be 0,1, or 2: if 0, then each 3 byte group becomes a 4-character base64 group; if 1, we need to characters to encode it and have two padding bytes ==, if $2$ we encode these 16 bits by 3 base64 characters (each encodes 6 bits, so can easily be done) and we add 1 = character. So the incomplete group of 1 or 2 also gets encoded as a 4 character base64 sequence, as all complete groups. We add $0, 2$ resp $1$ padding byte for the cases $N \pmod 3$ equal to $0,1$ or $2$.

So if $N$ is the message length, we have $\lfloor \frac{N}{3}\rfloor$ complete groups of $3$, covering all but the last $N \bmod 3$ bytes, the encoded message has $$4 \left(\lfloor \frac{N}{3} \rfloor + (N \bmod 3)\right)$$ bytes.

Henno Brandsma
  • 242,131