2
$\begingroup$

Each mobile SIM card has a four-digit number ($b_1$,$b_2$,$b_3$,$b_4$) called PIN code. Each digit $0 \le b_i \le 9$ (for i = 1, 2, 3, 4) is generated using a random 16-bit sequence as follows: $b_i=(r_{4i-3} + r_{4i-2} .2 + r_{4i-1}.2^2 + r_{4i}.2^3)\pmod {10} $. How we can calculate the antropy of PIN code? I know the entropy relation but I have no view.

$\endgroup$
1
  • 1
    $\begingroup$ Clearly HW, What have you tried? $\endgroup$
    – kelalaka
    Commented Nov 14, 2021 at 15:50

2 Answers 2

1
$\begingroup$

I'm calling here $B_1, B_2, B_3, B_4$ the four random variables representing the four digits (I do not like to call a variable $p$). It seems a good idea to compute the entropy of only $1$ digits, and then because the four digits are independently chosen, we could multiply this number by $4$. Let $q_i= \mathbb{P}(B_1 = i)$ for any $i \in\{0, \dots, 9\}$. $$H(B_1)= -\sum_{i=0}^9 q_i\log(q_i)$$.

You can notice for $0\leq j \leq 5$, $q_j =\frac{2}{16}$, and for $6\leq j\leq9$, $q_j= \frac{1}{16}$. Then, because $\log_2(\frac{2}{16})= (1-4)$, and $\log_2(\frac{1}{16})= (-4)$. \begin{align} H(B_1)&= -\left(6\cdot \frac{2}{16}(1-4) + 4\cdot \frac{1}{16}(-4)\right) \\ &=\frac{9+4}{4}= \frac{13}{4} = 3.25 \end{align}

After multiplying by $4$, because there is $4$ digits (as I've said before), we obtain $13$ bits of entropy.

$\endgroup$
11
  • $\begingroup$ Just looking at this. Are you convinced that $p_i$ is smooth and continuous? There are no gaps? And are they IID; they come from a formula... $\endgroup$
    – Paul Uszak
    Commented Nov 14, 2021 at 13:26
  • $\begingroup$ I've deleted one sentence does it make more sense for you? $\endgroup$
    – Ievgeni
    Commented Nov 14, 2021 at 13:32
  • 2
    $\begingroup$ Oh I'm not criticising. I'm suspicious of the formulation of $p_i$. I am of all constructs that have implications for the security services. Four truly random digits have H = 13.3 bits ($\log_2(10) \times 4$). Seed $r$ is 16 bits. 16 > 13.3, so why not directly use $r$ and rejection sample down? It whiffs. $\endgroup$
    – Paul Uszak
    Commented Nov 14, 2021 at 14:18
  • $\begingroup$ Nobody generates such probabilistic random pins. HW. $\endgroup$
    – kelalaka
    Commented Nov 14, 2021 at 15:54
  • 1
    $\begingroup$ Since this is homework, I will let it to the OP to fix a slight error. $\endgroup$
    – fgrieu
    Commented Nov 14, 2021 at 16:48
0
$\begingroup$

For $0 \le b_i \le 5$, $p_i=\frac{2}{16}$ and for $6 \le b_i \le 9$, $p_i=\frac{1}{16}$. Then we calculate the logarithm values, which are respectively equal to $\log_2(\frac{2}{16})=(1-4)$ and $\log_2(\frac{1}{16})=(-4)$. Now, according to the entropy relation, \begin{align} \ H(b_1) &= -\ \sum_{i=0}^{9} p_i \log_2(p_i ), \end{align} we will have:

\begin{align} \ H(b_1) &= \ -(6 \cdot \frac{2}{16}(1-4) + 4 \cdot \frac{1}{16}(-4))=3.25, \end{align} which is the entopy of one digit. As there are four independent digits, multiply the value by 4 and we get 13 bits of entropy.

$\endgroup$
2
  • 1
    $\begingroup$ Watch the sign, and the exclusion of indices $j$ with zero probability. It's $H(b_1)=\displaystyle\sum_{j=0\ldots9\text{ and }p_j>0}p_j \log_2(1/p_j)$ or equivalently $H(b_1)=-\displaystyle\sum_{j=0\ldots9\text{ and }p_j>0}p_j \log_2(1/p_j)$. $\endgroup$
    – fgrieu
    Commented Nov 15, 2021 at 19:52
  • 1
    $\begingroup$ @fgrieu on the right, do you mean $\log_2(p_j)$? This comment shouts: delete me if I'm correct. $\endgroup$
    – kelalaka
    Commented Nov 15, 2021 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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