/*********************************************************
*   Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
*	Codifica e decodifica con ElGamal
*   Capitolo 5.11, pagina 149.
*********************************************************/


{alfabeto=["A","B","C","D","E","F","G","H","I","J","K",
  "L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z",";",".","'"," "];
}
{da_lettera_a_numero(lettera)=local(j);
     for(j=1,30,if(alfabeto[j]==lettera,return(j-1))); 
     error("input non valido.")
}
{da_numero_a_messaggio(num,s="")= local(m,i); 
     i=floor(log(p)/log(30))-1; 
     while(i>0, s = concat(s,alfabeto[num\(30^i)+1]); num = num % (30)^i;i--); 
             \\ p \ 30 e` la divisione intera di num per 30
     s = concat(s,alfabeto[num+1]);
     return(s)
}
{da_messaggio_a_numero(w,mod,num=0)= local(l,i,j);
     l=length(w);
     i=floor(log(mod)/log(30));
     M=Vecsmall(w);  
          for(j=1,l, num = num + 
             30^(i-j)*da_lettera_a_numero(Strchr(M[j]))); 
     if(i>l, for(j=l+1,i,num = num + 
             30^(i-j)*da_lettera_a_numero(" ")));
         return(num);
}

{ isprimitiveroot(g,p) = local (flag,fact);
    fact = component(factor(p-1),1)~;
    flag=1;\
    /**** print("lunghezza dello stack per la ricerca di un generatore: ",length(fact)); ****/
    for(i=1,length(fact),flag = flag && (Mod(g,p)^((p-1)/fact[i])!=1));
    return(flag);
}

{genera_chiave_elgamal(len, p, g, a, KE, KD, flag)=
	 if (len <= 1, print("Errore: il numero di cifre di p deve essere almeno 2"); return);
	 p=2;
	 /****   print(len); ****/
     until ((isprime(p)  && (p>30)),
               p = nextprime(random(10^(len)));
     );
     /****   print("primo p = ",p);  ****/
     blocco=floor(log(p)/log(30));
     print("La lunghezza massima del blocco codificabile e': ", 
               blocco," caratteri"); 
     g = random(p-1);
	 /****   print("candidato generatore modulo p e' g= ",g); ****/   
	 flag = isprimitiveroot(g,p);
     until ( flag && (g>0),
               g = random(p-1);
               /****   print("candidato generatore modulo p e' g= ",g);  ****/   
     		   flag=isprimitiveroot(g,p);          
     );
     /****   print("generatore modulo p = ",g);  ****/   
     a = random(p-1);
     /****   print("candidata chiave privata e' a= ",a);   ****/   
     until ((gcd(a,p-1)==1),
               a = random(p-1);
               /****   print("candidata chiave privata e' a= ",a);  ****/
     );
     KE = lift(Mod(g ,p)^a);
     KD = a;
     print("[primo p, generatore g, chiave pubblica KE, chiave privata KD]:");
     return([p, g, KE, KD]);
}
{elgamal_cifra(messaggio, p, g, KE) = local(l,i,j,k);
             l=length(messaggio);
             i=floor(log(p)/log(30));
             if (l>i, print("Errore: il messaggio e' di ", l, " caratteri ma non deve essere piu' di ", i," caratteri"); return);
             k=random(p-1);
 			 print("fattore casuale di codifica e' k= ",k);
             return([lift(Mod(da_messaggio_a_numero(messaggio,p)* (Mod(KE,p)^k),p)), lift(Mod(g,p)^k)]);
}
{elgamal_decifra(segreto=vector[2], p, g, KD)  = local(u,v);
			 u = lift( Mod( segreto[2], p)^KD);
			 v = lift( Mod( bezout(u,p)[1],p));
             return(da_numero_a_messaggio(lift(Mod(segreto[1]*v,p))));
}
             
             
                   
/*  ESEMPIO
(17:46) gp > genera_chiave_elgamal(50)
50
primo p = 52879559246749699710935882865311634254730007201151
La lunghezza massima del blocco codificabile e': 33 caratteri
candidato generatore modulo p e' g= 13371777086664190086920072041526134888622707709538
lunghezza dello stack per la ricerca di un generatore: 5
candidato generatore modulo p e' g= 25696524587184476600625519886105215840250761188806
lunghezza dello stack per la ricerca di un generatore: 5
candidato generatore modulo p e' g= 2219622228689717233527159817431100712546809526639
lunghezza dello stack per la ricerca di un generatore: 5
generatore modulo p = 2219622228689717233527159817431100712546809526639
candidata chiave privata e' a= 37340468835969838656423606686122908589634698193418
candidata chiave privata e' a= 26392669921301277369858920368099165556275700682660
candidata chiave privata e' a= 16825410236564127146088893770205618355344868743777
[primo p, generatore g, chiave pubblica KE, chiave privata KD]:
%96 = [52879559246749699710935882865311634254730007201151, 2219622228689717233527159817431100712546809526639, 24659685622403251122005839442012543895417566126018, 16825410236564127146088893770205618355344868743777]
(17:46) gp > elgamal_cifra("PROVA",%96[1],%96[2],%96[3])
%97 = [5682870866672652591270528683677119389002712023091, 23722878055971669520800489377566575763850561857054]
(17:46) gp > elgamal_decifra(%97,%96[1],%96[2],%96[4])
%98 = "PROVA                            "  

 gp > genera_chiave_elgamal(100)
La lunghezza massima del blocco codificabile e': 67 caratteri
[primo p, generatore g, chiave pubblica KE, chiave privata KD]:
%101 = [6291727931850574124595998006436960043839374298281910772545404507193251999173544262981318322725317539, 373696704573068529379716953519189531075925494929286227005892359572225960554675377475124829433246424, 2108987841334390728732790457807323255045007446961962520212462637659829849179928783485250864877622303, 4018093096573533344165609627638307276037758493481641248913152794462170585762697520147102841445860767]
(17:51) gp > elgamal_cifra("LA VITA E' BELLA PERCHE' E' VARIA, I PIEDI IN TERRA, I CASTELLI IN ARIA",%101[1],%101[2],%101[3])
Errore: il messaggio e' di 71 caratteri ma non deve essere piu' di 67 caratteri
(17:53) gp > elgamal_cifra("LA VITA E' BELLA PERCHE E' VARIA I PIEDI IN TERRA",%101[1],%101[2],%101[3])
%105 = [4606915013952573938398201582207932934883888205541184678026580694892453360525565192861576717691047622, 5004436418589622991237267773295077112810605077072229134589886811148157270941893365061969645499926535]
(17:53) gp > elgamal_decifra(%105,%101[1],%101[2],%101[4])
%106 = "LA VITA E' BELLA PERCHE E' VARIA I PIEDI IN TERRA                  "

*/