[crittografia] help!
Clicca QUI per vedere il messaggio nel forum |
| polyethylene |
Crittosistema di Hill, dagli appunti della Pagnoni, seconda lezione
Non ho capito perchè l'inversa di:
|3 3|
|2 5|
risulta essere:
|15 17|
|20 9|
qualcuno mi può spiegare ?:?
grazie |
| Ika |
Allora per calcolare l'inversa devi prima di tutto calcolare il determinante della matrice di partenza ..
Nel nostro caso è 15-6= 9 .
Dopodiche calcoli la matrice trasposta .. che essendo una due per due si calcola semplicemente invertendo di posizione gli elementi agli estremi ... e dividendo ogni elemento per i determinante trovato prima
Diventa quindi
| 5/9 -2/9 |
| -1/3 1/3 |
Ah, mi stavo dimenticando che devi mettere segno negativo agli elementi che si trovano in posizione dispari.
Ora devi trasformare questi numeri in modulo 26 perchè il crittosistema di Hill si basa sull'aritmetica modulo 26.
Nell'anello delle classi di resto modulo 26 non esistono i numeri negativi nè tantomeno le frazioni !
Dunque devi cercare gli inversi dei numeri 3 e 9.
a è l'inverso di b se a *b =1.
Quindi l'inverso di 9 è 3 e l'inverso di 3 è ovviamente 9.
A questo punto fai delle semplici moltiplicazioni
5 * 3 = 15
-2 * 3 = -6 che è congruo a 20 mod 26
-1 * 9 = -9 congruo 17 mod 26
1*9 = 9
e hai la matrice dei lucidi
| 15 17 |
| 20 9 |
Ciao ciao |
| LazerPhEa |
code:
Allora: tieni presente che tutti i calcoli li devi fare mudulo 26, perchè si assume che il testo da crittare sia scritto in inglese, il cui alfabeto è di 26 lettere.
Detto questo, l'inversa di una matrice M viene calcolata come:
M^-1 = [1/Det(M)] x N
Dove:
Det(M) indica il determinante della matrice M
N è la matrice dei complementi algebrici di M trasposta.
Dall' espressione di M^-1 si deduce che C.N.S. per l'esistenza dell'inversa è Det(M) <> 0 ( i.e., il determinante deve essere non nullo, essendo al denominatore dell'espressione).
Si calcola il determinante come: (5*3) + (-(3*2)) = 15 - 6 = 9 <>0.
Esiste quindi M^-1.
Si ricava la matrice dei complementi algebrici:
| 5 -2 |
|-3 3 |
Si riducono gli elementi della matrice modulo 26; 5 e 3 non richiedono ulteriori computazioni, mentre -2 e -3 devono essere ridotti.
Tenendo presente che l'opposto di un numero n è quel numero che sommato ad n da l'elemento neutro per la somma, -2 è quel numero che sommato a 2 da 0mod26
Quindi 2+24 = 0mod26 (infatti 2+24=26 che è congruente a 0, in aritmetica modulo 26)
Stesso ragionamento per -3, che risulta essere 23mod26
Ora si traspone la matrice, che diventa:
N = |5 23|
|24 3 |
Gli elementi di N devono perciò essere moltiplicati per 1/9 (cioè 1/Det(M)).
Ancora una volta si deve ridurre 1/9 modulo 26, tenendo presente che l'inverso di un numero n è quel numero che moltiplicato per n da l'elemento neutro per la moltiplicazione, si cerca un numero m T.C 9*m = 1mod26.
In questo caso m=3, infatti 9*3=26+1= 1mod26.
Quindi M^-1 = |5*3 23*3|
|24*3 3*3 |
Ancora: 5*3 = 15 e 3*3=9 sono a posto, mentre 23*3 = 69 e 24*3 = 72 devono essere ridotti mod26.
69 = 17 + 2*26 = 17mod26
72 = 20 + 2*26 = 17mod26
Infine M^-1 = |15 17|
|20 9 |
:D
Anche se mentre ci pensavo ti aveva già risposto Ika, ti posto comunque la mia versione! ;) |
| polyethylene |
Grazie, siete stati chiarissimi.
Mi sfuggiva il fatto del mod 26 :-D |
|
|
|
