Notifiche
Cancella tutto

Password corretta!  

 
Giandomenico
70
207
Distintivi:

Lo scassinatore Euclide è finalmente arrivato davanti alla cassaforte della banca denominata $IsPrime$, dopo una lunga attesa per preparare il colpo. Ma per sua sfortuna, la cassaforte è protetta da una password a doppia cifratura. La password nella prima cifratura è un codice di $8$ cifre che puo' variare nell'intervallo $\bigl\{$ $2$, $3$, $...$, $9$ $\bigl\}$ mentre nella seconda cifratura le cifre variano nell'intervallo $\bigl\{$ $0$, $1$ $\bigl\}$. Euclide sa bene che la password può essere decriptata soltanto da un computer molto potente che purtroppo non è in suo possesso. 

$Schema$ $dell$'$algoritmo$ :

 

$Utente$ $\xrightarrow[ cifratura ]{}$ $\bigl($ $a_{0}$, $a_{1}$, $a_{2}$, $...$, $a_{n}$ $\bigr)$  $\xrightarrow[ cifratura ]{}$ $\bigl($ $0101010$ $\bigr)$ $\xrightarrow[ Password corretta ]{}$

$Cassaforte$

Ma per sua fortuna Euclide ha avuto una soffiata : conoscendo il proprietario della banca, sa bene che la password è una delle possibili combinazioni che variano dell'intervallo considerato, dunque basta provarle tutte e il gioco è fatto. Ma per lui è un compito molto più difficile del previsto. Arrivato ormai all' estremo delle forze, Euclide si ricorda che il proprietario era solito ad utilizzare solo cifre il cui $MCD$ sarebbe stato uguale ad $1$. Per quando riguarda la seconda cifratura, se la password fosse stata corretta avrebbe generato una stringa con il più basso valore numerico. Ricordando queste informazioni, per Euclide indovinare la doppia cifratura è un gioco da ragazzi. Basta capire come associare ad ogni numero una sequenza di bit il cui valore risulta essere il più piccolo su $8$ bit. 

Suggerimento : ( le cifre $0$ o $1$ corrispondono al resto della divisione per quale numero? )

La domanda al quesito è : Qual'è la password della prima e della seconda cifratura?

Spoiler
Soluzioni

$Password$ $prima$ $cifratura$ : $22222222$

$Password$ $seconda$ $cifratura$ $=$ $00000000$

Spoiler
Come siamo arrivati alla soluzione

Dalle informazioni ottenute dal nostro gentilissimo Euclide, possiamo dedurre alcune considerazioni particolari. Per prima cosa, la password che varia nell'intervallo considerato puo' essere una delle tante possibili combinazioni : dunque avremo su una stringa di $8$ cifre $8$ $\cdot$ $8$ $\cdot$ $8$ $\cdot$ $8$ $\cdot$ $8$ $\cdot$ $8$ $\cdot$ $8$ $\cdot$ $8$ possibili combinazioni. Il che desta ad Euclide non poco ramarrico, ma per sua fortuna si ricorda che il proprietario utilizzava nella prima cifratura tutte quelle cifre il cui $MCD$ risultava essere uguale ad $1$. Ma ciò cosa significa realmente?
Significa che i numeri, utilizzati nella password, sono a due a due $coprimi$. In formule possiamo dire che :

$\forall$$a$, $b$ $\in$ $\bigl\{$ $2$, $3$, $...$, $9$ $\bigl\}$
$MCD$$\bigl($ $a$, $b$ $\bigl)$ $=$ $Max$$\bigl($ $Div$$\bigl($ $a$ $\bigr)$ $\cap$ $Div$$\bigl($ $b$ $\bigr)$$\bigl)$ $=$ $1$.

Banalmente possiamo notare che tutte le cifre che soddisfano questa proprietà sono i $numeri$ $primi$. Ma ora il numero delle combinazioni risulta essere decisamente minore, rispetto a quello iniziale. Dunque avremo : 

$numero$ $combinazioni$ $=$ $combinazioni$ $numeri$ $primi$ $\iff$ $numero$ $combinazioni$ $=$ $4$ $\cdot$ $4$ $\cdot$ $4$ $\cdot$ $4$ $\cdot$ $4$ $\cdot$ $4$ $\cdot$ $4$ $\cdot$ $4$ $\iff$ $4^{8}$.

Ma per Euclide risultano essere ancora troppe per poter indovinare la password in maniera diretta. Come se ciò non bastasse, la seconda cifratura è una sequenza di bit il cui valore numerico risulta essere il più piccolo su $8$ bit.
Ma come sappiamo su $8$ bit il valore numerico più basso risulta essere la seguente sequenza di $bit$ : $00000000$.
Dunque domanda sorge spontanea : Come facciamo ad associare ad ogni numero primo un valore $0$ o $1$ ?
La risposta alla domanda non è molto diversa da come abbiamo risolto il quiz " $che$ $giorno$ $è$ $?$ ". Banalmente possiamo osservare dal suggerimento proposto che $0$ e $1$ sono resti della divisione per $2$ essendoci solo $2$ cifre nella seconda cifratura. Quindi ci basta risolvere una congruenza. E dato che i nostri valori nella seconda cifratura variano nell'intervallo $\bigl\{$ $0$, $1$ $\bigr\}$ dovremo risolvere una congruenza modulo $2$. In formule dovremo trovare tutti quei numeri primi tali che il resto della divisione per $2$ risulta essere uguale a $0$ per avere una stringa di bit con il più basso valore numerico :

$n$ $\equiv_{2}$ $0$ $\iff$ $2$ $|$ $n$ $-$ $0$ $\iff$ $\bigl($ $\exists$ $m$ $\in$ $\textrm{Z}$ $|$ $n$ $=$ $2m$ $+$ $0$ $\bigl)$.

Ma ciò equivale a dire che questo numero risulterà necessariamente un multiplo di $2$, ma l'unico multiplo di $2$ nell'intervallo considerato e anche nei numeri primi, è soltanto $2$. Dunque possiamo concludere che la stringa $22222222$ avrà come corrispondente nella seconda cifratura, la sequenza di bit : $00000000$.

Quota
Postato : 20 Marzo 2020 20:10
Emanuele hanno apprezzato

+10

Iscriviti su SosMatematica.it e ricevi 10 gemme oggi stesso.