Funzioni One-Way

Posso andarmi a calcolare facilmente un segreto conoscendo i suoi componenti, ma se di questi conosco solamente una parte diventa impossibile matematicamente andarmi a calcolare il segreto. Pensa alla questione di ECDH.

Funzioni Trapdoor

Funzioni che in teoria sono facilmente invertibili e calcolabili a patto di conoscere tutti gli elementi che compongono le operazioni coinvolte.

Matematica Modulare

Insiemi 𝐙𝑛

• Aritmetica modulare è il termine che viene utilzzato per indicare un settore della Matematica che si occupa dello studio di particolari insiemi numerici e delle operazioni definite in essi.
• Gli insiemi oggetto di studio sono sottoinsiemi finiti dei numeri interi, ciascuno definito tramite un intero positivo 𝑛 , detto modulo; è dunque naturale che essi vengano denotati con la scrittura 𝐙𝑛 .

𝐙𝑛={0,1,…,𝑛−1}

• In Informatica troviamo alcune fra le più importanti applicazioni dell'aritmetica modulare: oltre alla crittografia, la generazione di numeri pseudo-causali, le funzioni hash, i codici correttori di errore, implementazione di strutture dati, ....
• 𝐙𝑛 può essere opportunamente visto come l'insieme dei possibili resti quando si divide un numero intero per 𝑛 .

<aside> 💡 Defizioni interessante: quando $y \space mod \space n = x \space mod \space n$, si dice che x e’ congruo a x in modulo n. Alla luce di questa definizione, potremmo dire che qualsiasi intero 𝑥 fa parte di 𝐙𝑛 nel senso che o 𝑥∈{0,1,...,𝑛 − 1}, oppure 𝑥 è rappresentato quell'unico 𝑦∈{0,1,...,𝑛−1} tale che 𝑥 ≡ 𝑦 ( mod 𝑛 ).

</aside>

Operazioni modulari

Riguardo la sottrazione e il caso di dividendo negativo

• Si noti che anche la sottrazione è perfettamente definita.
• Infatti, anche se il valore 𝑥−𝑦 è negativo, il resto nella divisione per 𝑛 è comunque un numero in 𝐙𝑛.
• Se indichiamo con 𝑄 e 𝑅 rispettivamente quoziente e resto della divisione di 𝑎 per 𝑏 , deve innanzitutto valere 𝑎 = 𝑏 ⋅ 𝑄 + 𝑅
• Tuttavia l'equazione ha infinite soluzioni: ad esempio, se 𝑎 = 7 e 𝑏 = 2 potremmo correttamente scrivere 7 = 3 ⋅ 2 + 1, ma anche 7 = 3 ⋅ 1 + 4 come pure 7 = 3 ⋅ 3 − 2 e così via a piacimento.
• Per rendere unici quoziente e resto ci vuole un'ulteriore condizione e questa, come è ben noto, è che 0 ≤ 𝑅 < 𝑏