Massimiliano (Max) Sala
CryptoWars2011: Categoria classica
ALGORITMO
Ogni squadra deve creare un algoritmo polialfabetico, eventualmente con varianti, per crittare un messaggio in chiaro.
quaderno Clusit di introduzione alla Crittografia
Il Polialfabetico Semplice
L'alfabeto da utilizzare corrisponde a quello inglese, con l'aggiunta dei simboli di punteggiatura:
a b c d e f g h i j k l m n o p q r s t u v w x y z (space) . , ; : ' ! ?
per un totale di 34 simboli. Quindi il testo da cifrare conterrà solo ed esclusivamente questi 34 simboli (senza considerare la distinzione lettere maiuscole e minuscole).
Una permutazione dell'alfabeto è un riarrangiamento dei simboli.
ESEMPIO (1)
Una semplice permutazione è shiftare i simboli dell'alfabeto di una posizione verso sinistra. Alla lettera a corrisponde la sua successiva b, a b corrisponde c e cosi via.
| a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
(space) |
. |
, |
; |
: |
' |
! |
? |
| b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
(space) |
. |
, |
; |
: |
' |
! |
? |
a |
Ogni squadra deve scegliere 5 permutazione dell'alfabeto (tutte le permutazioni sono permesse, in totale 34 fattoriale).
Il testo da cifrare viene diviso in blocchi di 5 simboli, chiamati word. La prima lettera di ogni blocco viene sostituita usando la prima permutazione, la seconda lettera del blocco viene sostituita usando la seconda permutazione, e cosi via.
ESEMPIO (2)
Le permutazioni numero 1, 3 e 5 sono la stessa e corrispondono alla shift verso sinistra di una posizione dell'alfabeto:
| a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
(space) |
. |
, |
; |
: |
' |
! |
? |
| b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
(space) |
. |
, |
; |
: |
' |
! |
? |
a |
Le permutazioni numero 2 e numero 4 corrispondono invece all'identita'(ovvero la permutazione che lascia tutto fisso).
Il testo in chiaro da crittare è il seguente:
BUONA FORTUNA A TUTTE LE SQUADRE CHE PARTECIPANO ALLA GARA.
Questo testo viene diviso in word da 5 lettere ciascuno:
BUONA|(space)FORT|UNA(space)A|(space)TUTT|E(space)LE(space)|SQUAD|RE(space)CH|E(space)PAR|TECIP|ANO(space)A|LLA(space)G|ARA.
quindi crittato diventa:
CUPNB|.FPRU|VNB(space)B|.TVTU|F(space)ME(space)|TQVAE|SE.CI|F(space)QAS|UEDIQ|BNP(space)B|MLB(SPACE)H|BRB,
Osserviamo che l'ultimo blocco non è composto da 5 lettere, in quanto il testo in chiaro non ha lunghezza multiplo di 5.
Le varianti
Ribadiamo che nel testo in chiaro non saranno presenti numeri, eventuali accenti verranno sostituiti dal simbolo apostrofo ( ' ) e non ci sarà alcuna distinzione tra lettere maiuscole e minuscole.
A ciascuna squadra è permesso applicare delle varianti al polialfabetico semplice utilizzando fino ad un massimo di 9 simboli speciali, che devono essere indicati con i numeri dall'1 al 9.
Gruppi di lettere consecutive (possono anche essere parole) vengono sostituiti tramite uno di questi simboli. All'interno di ciascun word questi simboli speciali non vengono sostituiti dalle permutazione e quindi vengono saltati (CI1AOU è una word anche se ha 6 simboli, ma solo 5 fanno parte dell'alfabeto delle permutazioni).
ESEMPIO (3)
Decidiamo che 1 corrisponde al gruppo di lettere AO.
CIAO(space)A(space)TUTTI
viene diviso in word sostituendo ad AO il numero 1, ma poi non contando tale simbolo nel raggruppamento:
CI1(space)A(space)|TUTTI
a questo punto in fase di codifica il numero 1 non subisce alcuna sostituzione.
ESEMPIO PRATICO DI CODICE (con varianti)
Riprendiamo le permutazioni citate nell'ESEMPIO (2).
Definiamo i simboli speciali:
- 1 = GLI
- 2 = RA
- 3 = RE
- 4 = "" (la stringa vuota, da non confondere con lo spazio)
- 5 = CIAO COME STAI
- 6 = PC
- 7 = GN
- 8 = ZZ
- 9 = TT
Riprendiamo il messaggio in chiaro dell'ESEMPIO (2):
BUONA FORTUNA A TUTTE LE SQUADRE CHE PARTECIPANO ALLA GARA.
Questo testo viene diviso in blocchi tenendo conto dei simboli speciali:
BUONA|(space)FORT|UNA(space)A|(space)TU9E(space)|LE(space)SQ|UAD3(space)C|HE(space)PA|RTECI|PANO(space)|ALLA(space)|GA2.
quindi crittato diventa:
CUPNB|.FPRU|VNB(space)B|.TV9E.|ME.SR|VAE3(space)D|IE.PB|RTFCJ|QAOO.|BLMA.|HA2,
Ogni squadra ha inoltre la libertà di inserire un ulteriore simbolo speciale, che deve essere indicato con il numero 0, per rappresentare un ulteriore regola a piacimento. Ad esempio, mettere 0 davanti ad un word può semplicemente indicare che tale gruppo di lettere è stato invertito (0ITTUT sta ad indicare TUTTI).
Lo zero potrà essere usato fino ad un massimo di 10 volte nel testo cifrato.
Per evitare abusi, l'uso particolare dello zero deve essere approvato dagli organizzatori. Comunque nell'ultima fase della gara (l'attacco ai testi cifrati delle varie squadre) saranno resi noti i diversi possibili significati di tale simbolo (senza dire quale squadra usa quel significato).
Esempi di 0 leciti e non leciti
ESEMPIO (4)
Con il simbolo 0 indichiamo l'inversione del word cifrato che lo segue.
Se consideriamo il messaggio crittato dell'ESEMPIO (3), possiamo scrivere il messaggio come:
CUPNB|.FPRU|VNB(space)B|.TV9E.|ME.SR|VAE3(space)D|IE.PB|RTFCJ|QAOO.|0.AMLB|HA2,
Torna a Categoria Classica
Pagina principale delle Wars!
per ulteriori informazioni e domande scrivere a
mathnow.unitn@gmail.com
