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 fu ideato da Kurt Gödel nel 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_{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, 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 archiviato di programmazione.it sui possibili utilizzi del Numero di Gödel per la compressione, su programmazione.it. URL consultato il 3 novembre 2021 (archiviato dall'url originale l'8 settembre 2014).

Controllo di autorità	LCCN (EN) sh85055600 · J9U (EN, HE) 987007533661505171