Site hosted by Angelfire.com: Build your free website today!
 .   .   .   C   i   p   h   e   r   t   e   x   t   .   .   .

.   .   .   C   i   p   h   e   r   t   e   x   t   .   .   .

.   .   .   C   i   p   h   e   r   t   e   x   t   .   .   .

 

Presentazione

 

Algoritmi di cifratura

Cifratura a blocchi
Cifrari Monoalfabetici
Shifting cypher
Substitution cypher
Affine cypher
Cifrari Polialfabetici
Vigenère cipher
Permutation cipher

Cifratura DES

Cifrtura a catena
One-Time-Pad
Periodic Stream Cipher
Approfondimento
DES: Feistel cypher
DES-CBC
   DES-PCBC
  DES-ECB
  DES-CTR
  DES-CFB
  DES-ITL
DES in cascata
 
Privatezza, autenticita', integrita'
Public Key
Firma digitale
RSA
DSA
Funzioni di Hash
Shared Key
kerberos
Diffie & Hellman
Shamir Protocol
  Station to Station Protocol
Otway-Rees

Certificazione di identita'

 
Mutua Identificazione: protocolli di Needham-Shroeder
NSPK a 3 messaggi
NSPK a 7 messaggi
Certificazione da parte di un garante terzo
Certification Authorities
 
 

Riassunto di algebra modulare

e-mail

 

 

 

 

 

 

 

 

Riassunto di algebra modulare

Vengono riportate di seguito alcune delle regole base dell'algebra modulare, la cui conoscenza e' richiesta per la comprensione di alcune delle operazioni e delle definizioni impiegate nelle pagine di questo sito. Questo riassunto tuttavia puo' solo servire di richiamo per chi possiede gia' la conoscenza degli argomenti trattati o comunque delle buone basi, ma non e' consigliato come testo per lo studio di tali argomenti.


 

 

Numeri primi

Sono tutti quei numeri divisibili solo per 1 e per se stessi. Indicati con p.

Tutti gli altri numeri interi (composti) sono derivabili dai numeri primi come prodotto. (Th. Fond. aritmetica).

 

Numeri coprimi
 

Due numeri sono coprimi se il massimo comun divisore(MCD) tra loro e’ 1.

Nota:

0 non e’ primo e non e’ coprimo con nulla.


Modulo


A mod m = r significa che Km + r = a

Nota:

amod0 = a

0mod0 = 0

0modm = 0


Regola cerchio:

 


ES)

3mod7 = 3 (3<7)

-1mod7 = 6 (Per regola cerchio)

7mod3 = 1


 

 

 

Congruenza


 

[a mod m] e' congruente a  [b mod m] se entrambi danno il medesimo risultato.

ES)

13mod3 = 1

22mod3 = 1

 Sono congruenti.

 

MCD: Algoritmo di Euclide


MCD(a,b) = MOD(b mod a, a) . Applicare in modo ricorsivo.


ES)

MCD(12,18) = MCD(18mod12, 12) = MCD(6, 12) = MCD(12mod6, 6) = MCD(0, 6) = 6.

 

Cardinalita’


L’insieme Zn (completo) comprende tutti I numeri dell’insieme da 0 (n-1).

L’insieme Zn* (ridotto) comprende solo i numeri coprimi con n di Zn completo.

 

La cardinalita’ di un insieme si indica con |Zn|

La cardinalita’ dell’insieme Zn* s indica con |Zn*| oppure con φ(n), detta funzione toziente.

 

La cardinalita’ dell’insieme Zn e’ n.

La cardinalita’ dell’insieme Zp e’ p.

La cardinalita’ dell’insieme Zp* e’ (p-1) = φ(p).


Esprimendo n come prodotto di numeri primi (n=p*q),

φ(n) = (p-1)(q-1).


ES)

M=21 = 7*3

φ(M) = 6*2=12


φ(m) = П(i da 1 a m) (P(i) ^ h(i) – P(i)^h(i-1))


ES)

φ(60) = [60= 2^2 * 3 * 5] = (3-1)(5-1)(2^2 - 2^1).


 

Logaritmo


(a^x) mod m = b significa che x = log DIGa (b). [Log digitale: prendere solo intero di risultato, senza approssimazioni]


 

Square & Multiply


Per calcolare il mod di un numero elevato a potenza, si utilizza il metodo Square & Multiply:

Si codifica l’esponente in binario.

Si pone la cifra in binario in verticale dal most al less sign. Byte.

Ad ogni riga:

  • se c’e’ 1, si eleva al quadrato il numero risultante dalla riga superiore (se e’ la prima e’ 1) e lo si molti plica per la base.

  • Se c’e’ 0, si eleva solo al quadrato.

ES)

Calcolare :(7^11) mod 26 = ?

 

11 bin = 1011

1

[(1^2)*7]mod 26 = 7

0

(7*7)mod 26 = 23

1

(23^2)*7mod26= 11

1

(11^2)*7 mod26 = 15


Risposta: (7^11)mod26= 15


 

Inversione


Se (x*a) mod m = 1 , allora x= a-1

x esiste se e solo se a e' perpendicolare ad m.

Se m =p, a-1 esiste sempre.
 

 

Calcolo dell'inverso: Metodo di Lagrange (Metodo generale)

a-1 = a^[φ(m)-1] mod m.


 

Calcolo dell'inverso: piccolo teorema di Fermat (Solo se m=p)

a-1 = a p-2

ES)

m=p=3

a=7


7 -1 (mod 3) = 7 (3 – 2) (mod 3) = 7 (mod 3) = 1


Verifica: (7*1) mod 3 =1. [ok]


 

ES2)

m=p=15=3*5

a=7

φ(15) = 2*4 = 8

a-1 = a ^ [φ(15)-1]= a^ 7 mod 15 = 7^7 mod 15 = 13

Verifica: (13*7) mod 15 = 1. [ok]


 

Elementi generatori


In un insieme Zp, gli elementi generatori A sono quelli appartenenti a Zp* tali che, detti i B gli elementi di Zp*, valga:

B= A^i , dove 0<=i<=p-2

Numero elementi generaltori = Funz.toziente(p-1).


 

Es)

m=p=5

A=2

|Z5|=5 |Z5*|=p-1=4

 

2^0 mod 5=1

2^1 mod 5 =2

2^2 mod 5=4

2^3 mod 5=3

 

Torna a inizio pagina