Numero di Gödel

Da Wikipedia, l'enciclopedia libera.

In logica matematica, una numerazione di Gödel è una funzione che assegna a ciascuna produzione di un linguaggio formale un unico numero naturale chiamato numero di Gödel. Il concetto venne per la prima volta utilizzato da Kurt Gödel per il suo teorema di incompletezza.

Versione originale[modifica | modifica wikitesto]

Utilizzo in crittografia[modifica | modifica wikitesto]

La cifratura secondo il metodo di Godel si basa sulla fattorizzazione secondo il seguente principio:

Messaggio = (P_1^{Pos_1})(P_2^{Pos_2})(P_{3}^{Pos_3})...(P_{n}^{Pos_n})

Dove P_n è il numero primo successivo a P_{n-1} e Pos_n è la posizione dell'n-esima lettera nell'alfabeto preso in considerazione.

Ad esempio:

ABA = (2^{1}) * (3^{2}) * (5^{1}) = 2*9*5 = 90

Per decrittare basta eseguire la scomposizione in fattori primi del numero ottenuto; gli esponenti indicano la posizione della lettera nell'alfabeto.

 90 = 2^{1} * 3^{2} * 5^{1}

Gli esponenti sono 1, 2 e 1; il messaggio è quindi A, B, A.

Il punto debole di questo algoritmo è la facilità di decrittatura, basta scomporre in fattori primi. Per aggirare il problema si può combinare una sostituzione polialfabetica per renderlo molto sicuro. Lo svantaggio è che si deve lavorare su numeri molto grandi.

Esempio:

 CIAO = 3,7 * 10^{18}

Un modo per risolvere quest'ultimo problema è dividere la stringa in tanti pezzi così da avere numeri più maneggevoli.

Per esempio:

CIAO = CI-AO

 CI = (2^3)*(3^9) = 8 * 19683 = 157464

 AO = (2^1)*(3^{15}) = 2 * 14348907 = 28697814

 CIAO = 157464.28697814

Usando questo metodo si può combinare una doppia cifratura polialfabetica o monoalfabetica: Una prima della gödelizzazione e un'altra dopo (usando come chiave i numeri ottenuti o sostituendo il numero con la posizione della lettera nell'alfabeto).

Esempio:

CIAO = 157464.28697814

Posizione 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Alfabeto cifrante M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

MESSAGGIO CIFRATO = MQSPRP.NTRUSTMP

Voci correlate[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica