Informatica; esercitazioni varie svolte prof. Moriani

2018/19

ESERCIZI RSA CALCOLO

ALGORITMO RSA

• COSTRUIRE LA CHIAVE
• CIFRATURA DI UN MESSAGGIO IN CHIARO

ES. IN AULA:

• GENERAZIONE COPPIA DI CHIAVI

DATI IN INGRESSO

• p = 3 q = 11 c = 7
• CALCOLARE m
• m = p * q = 3 * 11 = 33
• p - 1 = 3 - 1 = 2
• q - 1 = 11 - 1 = 10
• (p - 1) (q - 1) = 2 * 10 = 20
• CALCOLARE d
• SUPPONIAMO CHE d VALGA ... E POI PROVO CHE È GIUSTO!
• SUPPONGO d = 3

^ed = 7 * 3 = 1 MODULO 20

21/20 = 1 RESTO 1 SEQUE 21 CONGRUO 1 MODULO 20

Segue d = 3

MEMO:

• A₁ = B MODULO N
• A = B + fn m
• A = B + q m
• A = B_m e q DEVE ESSERE UN N° INTERO

es. in aula (continua da prima)

• p = 3, q = 11, e = 7, d = 3, m = 33

- Cifratura - Decifratura

• m = 15
• Cifro m con chiave cifrata
• c = messaggio cifrato
• c = m^e (modulo m) = 15⁷ (modulo 33) = 27

- Decifrare c per ottenere m

• m = c^d (modulo m) = 27³ (modulo 33) = 15

es. in aula codifica RSA

• o: p, q e i: f m: = 13
• m : p, q : r^1,1 = 77
• (p - 1)(q - 4) = 6 * 10 = 60

• Calcolare d tne che d * e congruo 1 modulo ((p - 4) * (q - 4))
• d * 1 congru 1 modulo 60
• d * x = 1 + 60q
• t.d : 1 + 60q
• t.d : 60q
• t.d : 1
• t.d : 1: -9 ⇔ q deve venire intero
• 60
• Se d: 5 allora q : 5

Esercizi Algebra Booleana

1. Operatori:

• NOT - Complemento della variabile [0 - 1; 1 - 0]
• AND - Risultato vero [1] se sono vere entrambe le variabili
• OR - Risultato vero se è vera almeno una delle variabili
• XOR - Risultato vero se, e solo se, è vera solo una delle variabili
• XNOR [EQV] - Risultato vero solo se le due variabili sono uguali
• NAND - È vero solo se è falso l’AND tra le due variabili
• NOR - È vero solo se è falso l’OR tra le due variabili

es 1: W = NOT ((X OR Y) AND Z AND (Y OR Z))

es 2: W = (X XOR Y) AND Z EQU (NOT (X) AND Y)

23₁₀ ⇒ ...?

• 23 : 2 = 11 RESTO 1
• 11 : 2 = 5 RESTO 1
• 5 : 2 = 2 RESTO 1
• 2 : 2 = 1 RESTO 0
• 1 : 2 = 0 RESTO 1

23₁₀ = 10111₂

10111₂ = 16 + 4 + 2 + 1 = 23

118₁₀ ⇒ ...?

• 118 : 2 = 59 RESTO 0
• 59 : 2 = 29 RESTO 1
• 29 : 2 = 14 RESTO 1
• 14 : 2 = 7 RESTO 0
• 7 : 2 = 3 RESTO 1
• 3 : 2 = 1 RESTO 1
• 1 : 2 = 0 RESTO 1

118₁₀ = 1110110₂

1110110₂ = 64 + 32 + 8 + 4 + 2 = 118

83₁₀ ⇒ ...?

• 83 : 2 = 41 RESTO 1
• 41 : 2 = 20 RESTO 1
• 20 : 2 = 10 RESTO 0
• 10 : 2 = 5 RESTO 0
• 5 : 2 = 2 RESTO 1
• 2 : 2 = 1 RESTO 0
• 1 : 2 = 0 RESTO 1

83₁₀ = 1010011₂

1010011₂ = 64 + 16 + 2 + 1 = 83