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 fu ideato da Kurt Gödel nel 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:

Dove è il numero primo successivo a e è la posizione dell'-esima lettera nell'alfabeto preso in considerazione.

Ad esempio:

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

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:

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

Per esempio:

CIAO = CI-AO

Usando questo metodo si può combinare una doppia cifratura polialfabetica o monoalfabetica: una prima della gödelizzazione, 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

Collegamenti esterni[modifica | modifica wikitesto]

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