Esercizi su classi di resto, funzione di Eulero, applicazioni crittografiche

1. Calcolare:$ \let\Implica\Longrightarrow \newcommand\N{\mathbb N} \newcommand\Z{\mathbb Z} \newcommand\modbin{\mathbin {\rm mod}} \def\U{\mathscr U} \let\phi\varphi $
   • $\phi(77)$;
   • $\phi(100)$;
   • $\phi(1000)$;
   • $\phi(2^3 3^3 5^2)$ (basta indicare questo numero, per esempio, scrivendolo come prodotto di potenze di numeri primi);
   • il numero degli interi positivi minori di $60$ che siano coprimi con $60$;
   • il numero degli interi positivi dispari minori di $60$ che non siano multipli né di $3$ né di $5$.
2. Calcolare:
   • $8^{60}\modbin 77$;
   • $8^{120}\modbin 77$;
   • $2^{\phi(645624669619)}\modbin 645624669619$;
   • $6^{12}\modbin 13$;
   • $6^{13}\modbin 13$;
   • $6^{17}\modbin 17$;
   • $6^{31}\modbin 31$;
   • $17^{41}+39^{80}\modbin 100$;
3. Stabilire se la funzione di Eulero (dall'insieme dei numeri interi positivi in se stesso) è o non è iniettiva. Vale a dire: esistono interi positivi $a$ e $b$ tali che $a\ne b$ ma $\phi(a)=\phi(b)$?
4. Esistono interi positivi $a$ tali che $\phi(a)=3$?
5. Quali delle seguenti classi di resto sono invertibili?:
   • $[14]_{77}$;
   • $[2]_{77}$;
   • $[12345678]_{12345679}$;
   • $[5]_{17}$;
   • $[102]_{1788}$;
   • $[321]_{4567}$ (suggerimento: $4567$ è primo);
   Di alcune di queste (tutte tranne l'ultima, a meno di non aver fatto la conoscenza con l'algoritmo euclideo), trovare l'inversa.
6. Utilizzando RSA, Alice manda a Bob il numero (riservatissimo, ma noi lo conosciamo lo stesso) della sua cabina: 12. La chiave pubblica di Bob è $(91,5)$.
   • Come cifrerà Alice il suo numero? Vale a dire: quale numero (messaggio cifrato) invierà Alice a Bob?
   • La chiave privata di Bob è 17. Come decifrerà Bob il messaggio di Alice? Riuscirà Bob a recuperare il numero della cabina di Alice?
   • A quanto pare c'è un errore. Dove? Correggere l'errore e ripetere la decifrazione del messaggio.
   • Spiegare perché la chiave pubblica $(91,5)$ di Bob non è per nulla idonea a garantire alcuna riservatezza.
7. Alice e Bob usano il protocollo di Diffie-Hellman (descritto nella presentazione proiettata nel quarto incontro) per concordare una chiave. Il primo utilizzato è $17$, i numeri segreti usati da Alice e Bob sono (nell'ordine) $7$ e $6$. Alice sceglie di iniziare la procedura ponendo $a=10$.
   • Quale sarà la chiave concordata?
   • Descrivere ogni passo della procedura, specificando tutti i numeri trasmessi.
   NB: I calcoli sono molto semplici da effettuare, se svolti in modo accorto. Può essere utile osservare in partenza che $10\equiv_{17}-7$.
8. Questa volta Alice manda un messaggio a Bob usando la crittografia senza chiavi condivise (il riferimento è sempre alla solita presentazione). Il primo prefissato è $23$, il messaggio è $8$, i numeri segreti di Alice e Bob sono, nell'ordine, $5$ e $13$. Svolgere tutti i passaggi di cifratura e decifrazione (da parte di Alice e di Bob) sino alla ricezione del messaggio da parte di Bob. Un suggerimento: $13\cdot 17=221\equiv_{22}1$.

Home