Algoritmo di ElGamal 			Ginevra Cicconi  
										        matr: 214861554

Generazione Numeri Primi

primoSuccessivo[num_] := 
      Module[{n}, 
If[EvenQ[num], n = num + 1, 
          n = num]; 
While[! PrimeQ[n], 
          n = n + 2]; 
n]

generaPrimoCasuale[n_] := 
      primoSuccessivo[Random[Integer, {(10^(n - 1)), (10^n)}]]

Generazione Generatori

testg  afferma se un numero primo s è un generatore di q, sfruttando la seguente proprietà:

testG[s_, q_] := 
      Module[{i = 1, xl = FactorInteger[q - 1], h = {}, l}, 
        h = Flatten[Take[xl, Length[xl], 1]]; l = Length[h]; 
        While[i <= l, k = (q - 1)/h[[i]]; i++; 
          If[PowerMod[s, k, q] == Mod[1, q], Return[False]]]; 
        Return[True]]

Ottenere tutti i generatori di un numero primo p

listaGeneratori mi fornisce la lista di tutti i generatori di p fino al numero len (listaGeneratori[p,p] me li fornisce tutti)

listaGeneratori[p_, len_] := 
      Module[{a = 1, lit = {}}, 
        While[a < len, If[testG[a, p], AppendTo[lit, a]]; a++]; 
        Return[lit]]

p = generaPrimoCasuale[3]

listaGeneratori[p, p]

generatori restituisce il primo generatore di p a partire dall'indice index (giunto a p-1 riparte da 1)

generatori[p_, index_] := 
      Module[{a = index, ok = False}, 
        While[a < p - 1, If[testG[a, p], ok = True; Break[]]; a++]; 
        If[ok, Return[a], generatori[p, 1]]]

gener  restituisce un generatore di p scelto a caso fra tutti i suoi generatori

gener[p_] := generatori[p, Random[Integer, {1, p - 1}]]

Generazione delle chiavi

Chiave Privata

p =  generaPrimoCasuale[12]

Chiave privata effettiva

SU = Random[Integer, {1, p - 2}]

Chiave Pubblica

g = gener[p]

Chiave pubblica effettiva

PU  =  PowerMod[g, SU, p]

Generazione di r e R

r = Random[Integer, {0, p - 2}]

R =  PowerMod[g, r, p]

Esempio di Cifratura

m = 5605451

c =  Mod[PowerMod[PU, r, p]*m, p]

Data una lista di numeri me li cifra in una nuova lista di numeri

CifraMex[mex_] := Mod[PowerMod[PU, r, p]*mex, p]

Esempio di Decifratura

m1 = Mod[c*PowerMod[PowerMod[R, SU, p], -1, p], p]

Data una lista di numeri cifrati li decifra nell'originale lista di numeri

DecifraMex[mex2_] := 
      Mod[mex2*PowerMod[PowerMod[R, SU, p], -1, p], p]

Codifica del messaggio

Funzioni di utilità

Funzioni parziali

ListaBit2Num converte un lista di bit in un numero

ListaBit2Num[lia_] := 
      Module[{len = Length[lia], s = 0, res = 0}, 
        While[s < len, res = res + lia[[len - s]]*2^s; s++]; 
        Return[res]]

ListaBit2Num[{0, 1, 0, 1}]

StringToByte mi fornisce la rappresentazione di una stringa come array di byte (array di liste di bit)

StringToByte[str_] := 
      Return[IntegerDigits[ToCharacterCode[str], 2]]

StringToByte["a!"]

ADDzero è  una funzione di utilità che gli aggiunge zeri mancanti all'inizio di un array di bit per rendere il numero pari ad N

ADDzero[le_, n_] := 
      Module[{lret = le}, While[Length[lret] < n, PrependTo[lret, 0]]; 
        Return[lret]]

ADDzero[{1, 1, 1, 1, 1}, 8]

ListaFinale inserisce gli opportuni "zeri" iniziali all'intero messaggio codificato in byte(liste di di liste di bit) e restituisce un'unica lista

ListaFinale[list_, n_] := 
      Module[{i = 1, lret = {}, ltemp = {}}, 
        While[i <= Length[list], 
          ltemp =  ADDzero[list[[i]], n]; i++; 
          lret = Flatten[{lret, ltemp}]]; Return[lret]]

ListaFinale[{{1, 0, 1}, {1, 1}}, 4]

String2Stream

String2Stream dato un messaggio sotto forma di stringa lo converte in uno stream di bit (codifica asci ==> multiplo di 8 bit)

String2Stream[str_] := ListaFinale[StringToByte[str], 8]

String2Stream["a!"]

ListaInNumeri

ListaInNumeri prende uno stream di bit e lo converte in una lista di numeri leggendo n bit alla volta partendo dalla fine

ListaInNumeri[n_, lbit_] := 
      Module[{ltemp = {}, lret = {}, f = 0, len =  Length[lbit], start, 
          res1 = 0}, 
        While[f < len, start = len - f - n + 1; If[start <= 0, start = 1]; 
          ltemp = Take[lbit, {start, len - f}]; res1 = ListaBit2Num[ltemp]; 
          lret = Flatten[{res1, lret}]; f = f + n]; Return[lret]]

ListaInNumeri[3, {0, 1, 1, 0, 1, 0, 1, 1}]

NumeriInLista

NumeriInLista data una lista di numeri la converte in un array di bit, interpretando ogni numero come se fosse ad n bit (i bit 0 in testa sono eliminati)

NumeriInLista[lis_, n_] := 
      Module[{list = ListaFinale[IntegerDigits[lis, 2], n]}, 
        While[First[list] == 0, list = Rest[list]]; 
        Return[list]]

NumeriInLista[{5, 2}, 4]

Funzioni finali

Inizializzazione

La dimensione dei blocchi in cui viene suddiviso il messaggio da cifrare dipende dalla dimensione del modulo e precisamente il messaggio viene suddiviso in blocchi ciascuno di lunghezza inferiore a Log2 p bit

numBitP = Ceiling[Log[2, p]]

dimBloccoMex = numBitP - 2

condensando le funzioni...

Cifra

Cifra[str_] := 
      FromCharacterCode[
        ListaInNumeri[8, 
          NumeriInLista[
            CifraMex[ListaInNumeri[dimBloccoMex, String2Stream[str]]], 
            numBitP]]]

Decifra

Decifra[mexcifrato_] := 
      FromCharacterCode[
        ListaInNumeri[8, 
          NumeriInLista[
            DecifraMex[
              ListaInNumeri[numBitP, 
                NumeriInLista[ToCharacterCode[mexcifrato], 8]]], 
            dimBloccoMex]]]

Esempio passo passo

mex = "che bello è tornato tutto"

nn0 = String2Stream[mex]

n0 = ListaInNumeri[dimBloccoMex, nn0]

n1 = CifraMex[n0]

mm = NumeriInLista[n1, numBitP]

k1 = ListaInNumeri[8, mm]

mexcifrato = FromCharacterCode[k1]

me1 = ToCharacterCode[mexcifrato]

me2 = NumeriInLista[me1, 8]

me3 = ListaInNumeri[numBitP, me2]

me4 = DecifraMex[me3]

m5 = NumeriInLista[me4, dimBloccoMex]

m6 = ListaInNumeri[8, m5]

FromCharacterCode[m6]

ESEMPIO FINALE PRATICO

mess=InputString[ "\n\n\t     INSERISCI UN TESTO DA CIFRARE"]

mexcifrato = Cifra[mess]

Decifra[mexcifrato]