Corso di Didattica 1 – Modulo di Programmazione

Crittografia e crittanalisi

Contenuti

  • Prima parte: come un agente segreto!
  • Seconda parte: rudimenti di crittografia e di crittanalisi
  • Terza parte: che si programmi!
  • Quarta parte: proviamo a strutturare un percorso

Prima parte: come un agente segreto!

Messaggi segreti 1

Divisi a gruppi, dovrete rivestire i panni di un gruppo di agenti segreti che vogliono scambiarsi messaggi scritti in modo che il loro contenuto non sia comprensibile nel caso in cui questi venissero intercettati.

  1. Pensate a un modo per camuffare una o più frasi, indicando il testo del messaggio che volete camuffare come testo in chiaro, e il testo camuffato come testo cifrato.
  2. Oltre al testo cifrato in sé, quali sono le informazioni necessarie conoscere per poter ricostruire il testo in chiaro?
  3. Perché chi non conosce queste informazioni non è in grado di ricostruire il testo in chiaro?

Messaggi segreti 2

Provate a pensare a un modo per costruire il testo cifrato che rispetti le regole seguenti:

  1. il messaggio cifrato dovrà essere composto solo da lettere dell’alfabeto e da numeri;
  2. a ogni lettera del messaggio originale deve corrispondere una e una sola lettera nel messaggio cifrato;
  3. non si può camuffare il messaggio invertendo l’ordine di lettere o parole al suo interno;
  4. non è possibile eliminare le lettere di una parola.

Messaggi segreti 2

Useremo il termine chiave per indicare le informazioni necessarie per ricostruire il testo in chiaro a partire da quello cifrato.

  1. Anche in questo caso, descrivete qui sotto che procedimento è necessario applicare al testo in chiaro per ottenere il testo cifrato.
  2. Qual è la chiave che permette di ricostruire il testo in chiaro a partire dal testo cifrato? Perché chi non la conosce non è in grado di ricostruire il testo in chiaro?
  3. Modalità docente: qual è la differenza tra i due esercizi svolti finora?

Messaggi segreti 3

C'è (almeno un) un modo semplice di trovare un modo per creare il testo cifrato rispettando le regole che ci siamo dati e usando come chiave un numero intero. Riuscite a trovarlo?

Modalità docente: è possibile che alcune delle attività precedenti non siano necessarie? Se sì, di quali attività si tratta e perché non risulterebbero necessarie?

Seconda parte: rudimenti di crittografia e di crittanalisi

Crittografia

kryptos (nascosto) + graphia (scrittura)

È una pratica antica: Plutarco descrive la scitala lacedemonica come in uso fin dal IX secolo a.C.

Il cifrario Atbash

Viene fatto risalire al libro di Geremia

La prima lettera dell'alfabeto è sostituita con l'ultima, la seconda con la penultima e così via.

chiaro A B C D E F G H I L M N O P Q R S T U V Z
cifrato Z V U T S R Q P O N M L I H G F E D C B A

Tecnicamente: cifrario a sostituzione monoalfabetica

Il cifrario di Cesare

Ogni lettera è sostituita con quella che si trova dopo un certo numero di posizioni nell'alfabeto... o anche prima

Chiave: di quanto bisogna spostarsi

chiaro A B C D E F G H I L M N O P Q R S T U V Z
cifrato D E F G H I L M N O P Q R S T U V Z A B C

In generale

Si tratta di cifrari a sostituzione (ogni lettera viene sostituita con un altra lettera) monoalfabetica (la regola che mi dice come sostituire le lettere non cambia mai)

Forma più generale: cifrario a permutazione, in cui in corrispondenza di ogni lettera dell'alfabeto è necessario specificare con che cosa questa vada sostituita.

Chiave: l'intera permutazione

Crittanalisi di base

Frequenze delle lettere in un testo scritto in lingua italiana

Cerchiamo la lettera più frequente nel testo cifrato, e andiamo per tentativi: sarà una E, o una A, ...

Un computer può aiutarci parecchio

Provate a svolgere una serie di semplici esercizi di crittanalisi.

Complichiamo le cose

Cambiamo la regola di sostituzione man mano che consideriamo lettere diverse (cifrario a sostituzione polialfabetica)

Per esempio: il cifrario di Vigenère.

chiaro A R R I V A N O I R I N F O R Z I
verme V E R M E V E R M E V E R M E V E
cifrato V V I U Z V R F U V D R W A W U M

Terza parte: che si programmi!

Provate a implementare delle funzioni che implementino gli algoritmi di crittografia descritti.

Se c'è tempo, provate anche ad affrontare il problema della crittanalisi basata sulle frequenze delle lettere.

Ma prima... memento! Abbiamo visto solo la base delle tecniche di crittografia e di crittanalisi.

Quarta parte: proviamo a strutturare un percorso

Obiettivi formativi

  • Conoscenze
  • Abilità
  • Competenze

Conoscenze

  • strutture dati di tipo insieme e dizionario
  • algoritmi di cifratura e decifratura legati al cifrario di Cesare
  • caratteristiche rilevanti di un sistema di cifratura
  • tecnica di crittanalisi basata sulla frequenza delle lettere

Abilità

  • saper codificare in python gli algoritmi per la cifratura e la decifratura legati al cifrario di Cesare
  • saper progettare possibili algoritmi per la crittanalisi del cifrario di Cesare
  • saper implementare gli algoritmi al punto precedente in python

Competenze

  • riconosere le debolezze intrinseche nei cifrari a sostituzione
  • saper trasferire il concetto di criticità della sicurezza delle informazioni a situazioni della vita quotidiana

Snodi concettuali 1

  • comprendere che per cifrare e decifrare è necessario conoscere la chiave
  • comprendere che ogni chiave dà luogo a un diverso alfabeto cifrante
  • realizzare che è possibile astrarre le operazioni di sostituzione delle lettere ragionando in termini di numeri
  • capire l'utilità dell'aritmetica modulo 26 quando si effettua la cifratura e la decifratura con il cifrario di Cesare
  • realizzare che cifratura e decifratura sono una l'operazione inversa dell'altra
  • comprendere che nell'attacco a forza bruta del cifrario di Cesare vi è un numero possibile di chiavi pari al numero di lettere dell'alfabeto

Snodi concettuali 2

  • comprendere che nell'analisi frequenziale bisogna costruire le coppie di lettere più frequenti nei testi in chiaro e cifrato...
  • ...e che le distanze tra gli elementi di queste coppie rappresentano delle possibili chiavi utilizzate...
  • ...e dunque che bisogna procedere per tentativi
  • comprendere che un dizionario facilita il calcolo delle frequenze di parole
  • realizzare che è necessario avere a disposizione un insieme contenente le parole della lingua italiana per verificare se un tentativo di decrittazione è andato a buon fine
  • comprendere che l'efficacia della tecnica frequenziale dipende dalla lunghezza del testo analizzato, ma anche dal tipo di testo