Spero di non aver sbagliato sezione ma non sapevo proprio dove aprire questo thread.
Sto studiando l'algoritmo di crittografia Knapsack (Zaino)
Ho capito tutto tranne un passaggio che mi sta facendo uscire pazzo e la cosa assurda è che probabilmente è una stupidaggine galattica.
-----------
A deve inviare il carattere "a" a B
Prima della cifratura creo la sequenza di superincreasing con la proprietà che ogni numero sia superiore della somma dei suoi precedenti. ad esempio: (2, 3, 6, 13, 27, 52)
Calcolo W come sommatoria di tutti i valori della sequenza ed ottengo: 103
Scelgo M > W ad esempio 105
Calcolo N tale che appartenga al range [1, M) e sia coprimo con M ad esempio 31.
Ricavo la chiave pubblica:
2 * 31 mod 105 = 62
3 * 31 mod 105 = 93
6 * 31 mod 105 = 81
13 * 31 mod 105 = 88
27 * 31 mod 105 = 102
52 * 31 mod 105 = 37
Chiave pubblica = (62, 93, 81, 88, 102, 37)
Adesso A riceve la chiave pubblica di B con la quale cifrare il carattere "a" che supponiamo essere 011000
Determina il sacco da inviare a B prendendo i valori corrispondenti: 93 e 81 e li somma = 174
Quindi invia 174 a B
Adesso B riceve 174 da A
Calcola l'inverso moltiplicativo di 31 ed ottiene 61
Non capisco da dove esce fuori 61.
L'inverso moltiplicativo di 31 è semplicemente 1/31, il mod utilizzato fino ad ora è 105 e non capisco da dove salti fuori questo 61.
Qualcuno saprebbe aiutarmi a capire quale passaggio viene effettuato ?
Grazie!