Numero di Gödel

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.

Utilizzo in crittografia

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 è un numero primo e Pos è la posizione della lettera nell'alfabeto.

Ad esempio:

ABA = (2¹) * (3²) * (5¹) = 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¹ * 3² * 5¹

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¹⁸

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⁹) = 8 * 19683 = 157464

AO = (2¹) * (3¹⁵) = 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

Collegamenti esterni

• Articolo di programmazione.it sui possibili utilizzi del Numero di Gödel per la compressione

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