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