înregistrare Logare
Puncte:2
Mohammadsadeq Borjiyan avatar Crypto

Entropia codului PIN SIM

drapel at
Mohammadsadeq Borjiyan

Fiecare cartelă SIM mobilă are un număr din patru cifre ($b_1$,$b_2$,$b_3$,$b_4$) numit cod PIN. Fiecare cifră $0 \le b_i \le 9$ (pentru i = 1, 2, 3, 4) este generată folosind o secvență aleatorie de 16 biți, după cum urmează: $b_i=(r_{4i-3} + r_{4i-2} .2 + r_{4i-1}.2^2 + r_{4i}.2^3)\pmod {10} $. Cum putem calcula antropia codului PIN? Cunosc relația de entropie, dar nu am nicio viziune.

154
0 + 0
kelalaka avatar
drapel in
kelalaka
În mod clar HW, ce ai încercat?
1
Răspunde
Puncte:1
Ievgeni avatar Crypto
drapel cn
Ievgeni

Sun aici $B_1, B_2, B_3, B_4$ cele patru variabile aleatoare reprezentând cele patru cifre (nu îmi place să numesc o variabilă $p$). Pare o idee bună să calculați entropia numai $1$ cifre și apoi, deoarece cele patru cifre sunt alese independent, am putea înmulți acest număr cu $4$. Lăsa $q_i= \mathbb{P}(B_1 = i)$ pentru orice $i \in\{0, \dots, 9\}$. $$H(B_1)= -\sum_{i=0}^9 q_i\log(q_i)$$.

Puteți observa pt $0\leq j \leq 5$, $q_j =\frac{2}{16}$, si pentru $6\leq j\leq9$, $q_j= \frac{1}{16}$. Apoi, pentru că $\log_2(\frac{2}{16})= (1-4)$, și $\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}

După înmulțirea cu $4$, pentru că există $4$ cifre (cum am spus mai înainte), obținem $13$ biți de entropie.

0 + 0
Paul Uszak avatar
drapel cn
Paul Uszak
Doar uitându-mă la asta. Sunteți convins că $p_i$ este neted și continuu? Nu sunt goluri? Și sunt IID; vin dintr-o formula...
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
Am șters o propoziție are mai mult sens pentru tine?
0
Răspunde
Paul Uszak avatar
drapel cn
Paul Uszak
Oh, nu critic. Sunt suspicios de formularea lui $p_i$. Sunt din toate constructele care au implicații pentru serviciile de securitate. Patru cifre cu adevărat aleatorii au H = 13,3 biți ($\log_2(10) \times 4$). Sămânța $r$ este de 16 biți. 16 > 13.3, deci de ce să nu folosiți direct $r$ și eșantionul de respingere în jos? Pufă.
2
Răspunde
kelalaka avatar
drapel in
kelalaka
Nimeni nu generează astfel de pinuri probabilistice aleatorii. HW.
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Deoarece aceasta este temă pentru acasă, o voi lăsa la OP pentru a remedia o ușoară eroare.
1
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
am corectat eroarea...
0
Răspunde
kelalaka avatar
drapel in
kelalaka
Totuși, există o greșeală de la clasa întâi de numere raționale.
0
Răspunde
Mohammadsadeq Borjiyan avatar
drapel at
Mohammadsadeq Borjiyan
Dragă Paul Uszak, vă mulțumesc pentru considerație. Da, această schemă în comparație cu un număr aleatoriu de patru cifre este nerezonabilă, dar scopul a fost compararea entropiei a două modele.
0
Răspunde
Mohammadsadeq Borjiyan avatar
drapel at
Mohammadsadeq Borjiyan
Dragă Levgeni, am fost foarte recunoscător că iei în considerare problema mea.
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Pentru comparație: un PIN de 10 cifre uniform aleatoriu are â13,2877 biți de entropie, iar generarea PIN-ului prin reducerea valorii de 16 biți modulo 10000 produce â13,2835 biți de entropie.
0
Răspunde
Paul Uszak avatar
drapel cn
Paul Uszak
Repet: aceste valori sunt distribuite independent? Dacă nu, entropia va fi (mult) mai mică. Este necesar ceva Python.
0
Răspunde
Puncte:0
Mohammadsadeq Borjiyan avatar Crypto
drapel at
Mohammadsadeq Borjiyan

Pentru $0 \le b_i \le 5$, $p_i=\frac{2}{16}$ si pentru $6 \le b_i \le 9$, $p_i=\frac{1}{16}$. Apoi calculăm valorile logaritmului, care sunt, respectiv, egale cu $\log_2(\frac{2}{16})=(1-4)$ și $\log_2(\frac{1}{16})=(-4)$. Acum, conform relației de entropie, \begin{align} \ H(b_1) &= -\ \sum_{i=0}^{9} p_i \log_2(p_i ), \end{align} noi vom avea:

\begin{align} \ H(b_1) &= \ -(6 \cdot \frac{2}{16}(1-4) + 4 \cdot \frac{1}{16}(-4))=3,25, \end{align} care este entopia unei cifre. Deoarece există patru cifre independente, înmulțiți valoarea cu 4 și obținem 13 biți de entropie.

0 + 0
fgrieu avatar
drapel ng
fgrieu
Urmăriți semnul și excluderea indicilor $j$ cu probabilitate zero. Este $H(b_1)=\displaystyle\sum_{j=0\ldots9\text{ și }p_j>0}p_j \log_2(1/p_j)$ sau echivalent $H(b_1)=-\displaystyle\sum_{j =0\ldots9\text{ și }p_j>0}p_j \log_2(1/p_j)$.
1
Răspunde
kelalaka avatar
drapel in
kelalaka
@fgrieu pe dreapta, vrei să spui $\log_2(p_j)$? Acest comentariu strigă: șterge-mă dacă am dreptate.
1
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.