Numero di Gödel
# 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

