lunedì 27 aprile 2020

La crittografia


La parola crittografia deriva dal greco kryptòs “nascosto” e graphía “scrittura”, quindi tratta letteralmente delle “scritture nascoste”, ovvero dei metodi per rendere un messaggio non comprensibile a persone non autorizzate a leggerlo.

Tale messaggio si chiama crittogramma e i metodi usati per renderlo “non comprensibile” sono detti tecniche di cifratura.

Un cifrario è un algoritmo utilizzato per eseguire operazioni di cifratura (e decifratura), ovvero la procedura da seguire per rendere oscuro, non comprensibile semanticamente, il messaggio.

Le due tipologie di metodi che vengono applicati in crittografia sono la cifratura e la codifica.
La cifratura lavora sulle lettere "individuali" di un alfabeto. 
La codifica lavora ad un livello semantico più elevato (significato), come può essere una parola o una frase. 
I sistemi di cifratura possono lavorare per trasposizione, o per sostituzione, o una combinazione di entrambi: 
La trasposizione (o permutazione) mescola i caratteri di un messaggio in un nuovo ordine (es. anagramma). 
La sostituzione scambia un carattere con un altro carattere seguendo una regola specifica. 
La combinazione di trasposizione e sostituzione è chiamata cifratura composta. Quest’ultima tecnica è più sicura delle due precedenti.
La crittografia si basa su un algoritmo e su una chiave.
L’algoritmo è costituito dalle regole, seguendo una procedura passo passo, che servono a codificare e decodificare. 
La chiave, combinata con il testo “in chiaro” (non ancora crittografato), passato attraverso l'algoritmo, ci fornisce il testo “codificato”. 
In ogni moderno sistema di crittografia si deve assumere che l'algoritmo sia conosciuto dai potenziali “nemici”, quindi la sicurezza del sistema dipende solo ed esclusivamente dalla segretezza della chiave. 
In ambito informatico, è possibile distinguere tra due tipi di crittografia: la crittografia simmetrica (o a chiave privata) e la crittografia asimmetrica (o a chiave pubblica).

Negli algoritmi a chiave simmetrica, o a chiave privata, la stessa chiave, segreta, è usata sia per la cifratura che per la decifratura del messaggio. Esempi: DES, AES.
Il mittente ed il destinatario del messaggio devono conoscere entrambi la chiave segreta e quindi devono essere in possesso di un sistema sicuro per potersela scambiare senza che questa possa essere intercettata da altri. Il mittente usa questa chiave per la cifratura del messaggio mentre il destinatario la usa per decifrarlo.
Nella crittografia asimmetrica o a chiave pubblica vengono usate due chiavi diverse, una pubblica e una privata, per la cifratura e la decifratura. Esempio: RSA, PGP.
La chiave pubblica è di pubblico dominio ed è utilizzata da chiunque voglia cifrare un messaggio mentre la chiave privata è nota solo al destinatario del messaggio e viene da lui utilizzata per ottenere il testo in chiaro.
Si potrebbe pensare che la crittografia sia nata recentemente in quanto è legata alla sicurezza informatica. Invece questa particolare tecnica affonda le proprie radici in epoche lontane della storia, possiamo arrivare sino alle tribù eremitiche dell’antica Palestina. 
Oggi la crittografia è indispensabile in campo informatico. 
Contro le tecniche di hackering e di phishing in rete si devono utilizzare sistemi crittografici sempre più complessi per assicurare la sicurezza informatica. 
Vediamo ora alcuni dei cifrari che sono passati alla storia.
Il cifrario di Cesare, di tipo monoalfabetico, è uno dei più antichi. 
Ogni lettera del testo in chiaro viene sostituita nel testo cifrato dalla lettera che si trova un certo numero di posizioni dopo nell'alfabeto. 
La sostituzione avviene lettera per lettera, scorrendo il testo dall’inizio alla fine. Infatti è detto anche cifrario a sostituzione o scorrimento. Il numero di posti dello scorrimento è la chiave.
Un'evoluzione del cifrario di Cesare è il cifrario di Vigenere, di tipo polialfabetico, nel quale si considera la prima lettera del messaggio e la prima lettera della chiave. Sulla tavola di Vigenère queste due lettere si usano come coordinate cartesiane che individuano rispettivamente la riga che inizia con la prima lettera e la colonna che inizia con la seconda lettera. All’incrocio si trova la lettera da sostituire nel messaggio da cifrare. E poi si procede così per tutte le lettere successive del messaggio.
Per Shannon, il padre della teoria dell'informazione, l'unico cifrario teoricamente inviolabile, ovvero perfetto, è quello che usa una chiave segreta "usa-e-getta" (che non deve essere mai riutilizzata), casuale e lunga quanto il messaggio da cifrare. 
L'esempio perfetto è il cifrario di Vernam, che è un cifrario di Vigenere con una chiave lunga quanto il messaggio da cifrare e di tipo ‘usa e getta’ ovvero utilizzabile una sola volta. 
Questo tipo di sistema viene chiamato One Time Pad (OTP), letteralmente "taccuino monouso”.

Proviamo a fare un'attività pratica e costruiamo con del cartoncino un cifrario di Cesare: si costruiscono due dischi circolari, uno più grande e uno più piccolo, entrambi con un foro al centro ed entrambi suddivisi in 26 spicchi dove scrivere le 26 lettere dell'alfabeto internazionale. Nel foro introduciamo un fermacampioni. Il disco più piccolo, posto sopra, deve poter ruotare su quello più grande, posto sotto. Se lo faccio ruotare di una posizione ottengo il cifrario in chiave 1, di due posizioni in chiave 2 e così via.





NOTA 
Hackering/Hacking: metodi, tecniche e operazioni che servono a conoscere, accedere e modificare un sistema informatico, hardware e software, con utilizzo/accesso non autorizzato. 
Phishing: truffa effettuata su Internet attraverso la quale un malintenzionato cerca di ingannare la vittima convincendola a fornire informazioni personali, dati finanziari o codici di accesso, fingendosi un ente affidabile, usando mezzi per la comunicazione di tipo digitale, es. mail. 
Sniffing: intercettazione passiva dei dati che transitano in una rete informatica.

Date un'occhiata al mio video su youtube:

venerdì 3 aprile 2020

Sequenze, sottosequenze e programmazione dinamica

In questo post parleremo di sequenze numeriche, sottosequenze e programmazione dinamica.
Iniziamo a dare qualche definizione:
Una sequenza numerica è semplicemente una lista di numeri interi.


Esempio:[15,6,12,18,9,8,10,20,8,4,7]
Possiamo definire lunghezza di una sequenza o di una sottosequenza il numero dei suoi elementi.
Quella dell’esempio di partenza è quindi lunga 11 (sono 11 i numeri presenti nella lista).
Una sottosequenza è una lista che contiene una parte degli elementi della sequenza di partenza, posti nello stesso ordine. Semplicemente alcuni elementi vengono eliminati dalla lista di partenza ma, attenzione, tutti gli altri restano nella stessa posizione di partenza!
Alcuni esempi di sottosequenze della lista precedente:
[15,6,12,18,7], [9,8,10, 8,4,7]
Non è invece una sottosequenza della lista precedente la seguente:
[15,18,12,9,8,20,10,4]
perché gli elementi non compaiono nello stesso ordine di quella di partenza (es. 18 e 12 oppure 20 e 10).
Data una sequenza, è poi interessante determinare le sue sottosequenze che hanno proprietà particolari. Quelle comunemente più rilevanti sono le seguenti:

MASSIMA SOTTOSEQUENZA CRESCENTE/DECRESCENTE ovvero la sottosequenza più lunga (strettamente) crescente/decrescente.
'strettamente' significa che non ci sono elementi ripetuti
Di queste sottosequenze possono essercene anche più di una!
NB come già detto, gli elementi devono mantenere lo stesso ordine di quella di partenza! Non dobbiamo riordinarli noi!

Per una sequenza di n elementi esiste un numero di distinte sottosequenze pari all'n-ma potenza di 2. L'algoritmo che permette di risolvere problemi con sequenze e sottosequenze ha una complessità esponenziale.

In informatica la programmazione dinamica è una tecnica di progettazione di algoritmi basata sulla divisione del problema in sottoproblemi e sull'utilizzo di sottostrutture ottimali (es. grafo, matrice…).
Il processo di risoluzione prevede 3 passi:
1. suddividere il problema in sottoproblemi più piccoli;
2. risolvere questi problemi in modo ottimale, utilizzando in modo ricorsivo questo processo a tre passi;
3. usare queste soluzioni ottimali per costruire una soluzione ottimale al problema originale.
La programmazione dinamica si usa quindi nei casi in cui esista una definizione ricorsiva del problema.
L’algoritmo che ne deriva genera un programma di complessità esponenziale a causa del calcolo ripetuto sugli stessi sottoinsiemi di dati da parte delle diverse chiamate ricorsive.
A questo punto sorgono spontanee le seguenti domande: cosa significa algoritmo? E cosa significa ricorsione?
Un algoritmo è un procedimento o programma che risolve un determinato problema attraverso un numero finito di istruzioni elementari, chiare e non ambigue.
Un algoritmo ricorsivo è un algoritmo espresso in termini di se stesso (es. una funzione che richiama se stessa più volte nella sua implementazione).

Questo tipo di argomento non è semplicissimo ma sono sicura che sulle sequenze e sottosequenze numeriche tutti gli amanti della matematica, anche i più piccini, possano sbizzarrirsi nella risoluzione di problemi.
Spero invece di aver stimolato la curiosità dei più grandi con i concetti di algoritmo, ricorsione e programmazione dinamica!

Date un'occhiata al mio video su youtube:

Esercizi con sequenze e sottosequenze

Proviamo a risolvere qualche semplice esercizio su sequenze e sottosequenze.
Nel video del mio canale youtube troverete alcuni semplici problemi svolti su una lavagna interattiva:
https://youtu.be/ErA3LdxSgH4

Dopo aver studiato la teoria e aver visto il video con la mia spiegazione su esercizi semplici, vi consiglio di esercitarvi un pò da soli.

In particolare potrete trovare molti problemi da risolvere sul sito delle Olimpiadi di Problem Solving, ai link sotto riportati.
Per la scuola primaria:
https://www.olimpiadiproblemsolving.it/web/archivio-prove-primaria.php
Per la scuola secondaria di primo grado:
https://www.olimpiadiproblemsolving.it/web/archivio-prove-sec-primo-grado.php
Per la scuola secondaria di secondo grado:
https://www.olimpiadiproblemsolving.it/web/archivio-prove-sec-secondo-grado.php

E' sufficiente che all'interno delle prove dei diversi anni andiate a cercare i problemi sulle sottosequenze.
Buon lavoro!

mercoledì 1 aprile 2020

Esercizi con i grafi


Dopo aver parlato della teoria dei grafi, siamo adesso pronti a risolvere qualche semplice esercizio.
Nel video del mio canale youtube troverete alcuni semplici esercizi svolti su una lavagna interattiva:
https://youtu.be/JmIEAVjg4-M

Dopo aver studiato la teoria e aver visto il video con la mia spiegazione su esercizi semplici, vi consiglio di esercitarvi un pò da soli.

In particolare potrete trovare molti problemi da risolvere sul sito delle Olimpiadi di Problem Solving, ai link sotto riportati.
Per la scuola primaria:
https://www.olimpiadiproblemsolving.it/web/archivio-prove-primaria.php
Per la scuola secondaria di primo grado:
https://www.olimpiadiproblemsolving.it/web/archivio-prove-sec-primo-grado.php
Per la scuola secondaria di secondo grado:
https://www.olimpiadiproblemsolving.it/web/archivio-prove-sec-secondo-grado.php

E' sufficiente che all'interno delle prove dei diversi anni andiate a cercare i problemi sui grafi.
Buon lavoro!