polyethylene

.consigliere.

User info:

Registered: Mar 2003
Posts: 117 (0.01 al dì)
Location: Ovunque
Corso: informatica
Anno: 3
Time Online: 13:31:41 [...]
Status: Offline

Post actions:

[crittografia] help!

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

.illuminato.

User info:

Registered: Sep 2002
Posts: 235 (0.03 al dì)
Location: Turate
Corso: Informatica
Anno: 4^
Time Online: 2 Days, 22:12:05: [...]
Status: Offline

Post actions:

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

Vendo Steinberger GM7TA

User info:

Registered: Jul 2002
Posts: 4400 (0.53 al dì)
Location: S. Donato Beach
Corso: TICo
Anno: Finito tutto
Time Online: 83 Days, 22:35:22 [...]
Status: Offline

Post actions:

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 |

Anche se mentre ci pensavo ti aveva già risposto Ika, ti posto comunque la mia versione!

__________________
Questo è il giardino
Dove il principe muore
Nessun sentiero
Nessun destriero
Soltanto un nome... Eterno...

polyethylene

.consigliere.

User info:

Registered: Mar 2003
Posts: 117 (0.01 al dì)
Location: Ovunque
Corso: informatica
Anno: 3
Time Online: 13:31:41 [...]
Status: Offline

Post actions:

Grazie, siete stati chiarissimi.
Mi sfuggiva il fatto del mod 26

__________________
"Per me l'uomo colto non è colui che sa quando è nato Napoleone, ma quello che sa dove andare a cercare l'informazione nell'unico momento della sua vita in cui gli serve, e in due minuti" Umberto Eco