prof.ssa Monica Sambo

1

February 27, 2011

CODICI & SEGRETILEZIONE 4prof.ssa Monica SamboLiceo "G. Veronese"

• Teorema di Wilson• Piccolo Teorema di Fermat• Definizione della funzione di Eulero• Teorema di Eulero• Applicazioni• Cifrario PLAYFAIR CIPHER LYON• CIFRA CAMPALE GERMANICA 

Ripasso della nozione di congruenza analizzata nella lezione precedente

Definizione Fissato un numero naturale n diverso dallo 0, due interi a, b si dicono congrui modulo n se n divide a ­ b cioè:

Si può dire inoltre che a e b hanno lo stesso resto nella divisione per n

1

2

34

5

6

0

0°

100

Teorema di Wilson

Esempio dimostrativo

Piccolo teorema di Fermat

Esempio dimostrativo

biiezione

n 1 2 3 4 5 6

10n 10 20 30 40 50 60

10 n mod 7 3 6 2 5 1 4

prof.ssa Monica Sambo

2

February 27, 2011

Moltiplico gli elementi della prima riga: 

Moltiplico gli elementi della seconda riga:

Ovviamente questa non è una dimostrazione!

n 1 2 3 4 5 6

10n 10 20 30 40 50 60

10 n mod 7 3 6 2 5 1 4

Il piccolo teorema di Fermat non è invertibileControesempio

341 non è un numero primo!

RSA

Definizione della funzione di EuleroDato un numero naturale n maggiore di 0, la funzione di Eulero associa ad n gli elementi che sono coprimi con n

Teorema di EuleroEstensione del piccolo teorema di Fermat

Dato un numero scritto in forma di potenza trovare quale deve essere la cifra dell'unità

calcolo il resto nella divisione per 10

3 è la cifra dell'unità

Trovare le ultime due cifre decimali del numero assegnato con l'utilizzo della funzione di Eulero 

per il T di Eulero

ESERCIZI

Trova le ultime due cifre decimali di:

Trova l'ultima cifra di:

prof.ssa Monica Sambo

3

February 27, 2011

ENIGMA

http://www.youtube.com/watch?v=XGCs3Q9Friw&feature=related

Alan Touring

http://www.youtube.com/watch?v=DnBsndE1IkA&feature=related

Enigma

http://www.simonsingh.net/The_Black_Chamber/playfaircipher.htm

Cifrario PLAYFAIR CIPHER LYON

The Playfair cipher was popularized by Wheatstone's  friend, Baron Lyon Playfair (1854)

Guerra di CrimeaMetodo di cifratura a digrammiSi utilizza una matrice 5 x 5 Ipotizziamo che a chiave sia la parola SEGRETI

S E G R T

I/J A B C D

F H K L M

N O P Q U

V W X Y Z

S E G R T

I/J A B C D

F H K L M

N O P Q U

V W X Y Z

DOMANI NELLA BATTAGLIA ATTACCO DA NORD 30 GRADI ESTLe doppie si dividono con X

DO MA NI NE  LX  LA  BA  TX AU  HD  VF  OS   KY   HC  CB  GZ  

AN OR DT RE NT AG RA DIIO QE MD TG PS BE EC IA

TA GL IA AT XT AC XC ODED RK AB DE ZG BD YB     UA

ES TXGE GZ

CHIAVE: PLAYFAIREXMHIDE THE GOLD IN THE TREE STUMP

TROVARE LA PAROLA CHIAVE:

LE SC AR PE MI ST AN XN OS TR ET XT EXHL BU OL HM OM EM LD WD RM SA TM DA TW 

LA MU CX CA NO ND AL AT XT EXAO SI DZ DF IL DI OA KA DA TW

IL PA PX PA GA LX LO ER OS XS OXNO KO KY KO KR AW AF SL RM VT AY

Sono sufficienti le prime due informazioni per trovare la soluzione!

Cifra campale germanica ADFGVX

Metodo utilizzato nella prima guerra mondialeSi usa una scacchiera 6 x 6 e si sostituisce una lettera con due o più lettere.

Scegliamo una chiave: DEUTSHLANDsi aggiungono le rimanenti lettere dell'alfabeto:DEUTSCHLANBFGIJKMOPQRVWXYZ 

A B C  D E  F  G  H  I  J 

1 2 3  4  5 6  7  8  9  0 

D4E5UTSC3H8LA1NB2F6G7I9J0KMOPQRVWXYZ

prof.ssa Monica Sambo

4

February 27, 2011

D4E5UTSC3H8LA1NB2F6G7I9J0KMOPQRVWXYZSi inserisce la stringa alfanumerica in una scacchiera 6 x 6

A D F  G  V  X 

A D 4  E 5 U T

D S C 3 H 8 L

F  A 1 N B 2 F

G  6 G 7 I  9  J

V  0 K M O P Q

X  R V W X Y Z

Si sceglie un messaggio da trasmettere: Q  U   E   S   T   O   E   U   N  S   E  G  R  E  T  OVX  AV AF  DA  AX VG  AF  AV  FF  DA AF GD XA AF AX VG 

Si sceglie una chiave colonna e si trasporta il messaggio: PANZER

Q  U   E   S   T   O   E   U   N  S   E  G  R  E  T  OVX  AV AF  DA  AX VG  AF  AV  FF  DA AF GD XA AF AX VG 

4  1 3  6  2  5 

P A N Z E R

V X A V A F

D  A A X V G

A F A V F F

D A A F G D

X  A A F A X

V G

Si leggono i messaggi per colonna partendo dalla lettera contrassegnata con 1XAFAA GAVFG AAAAA AVDAD XVFGF DXVXV FF