/*********************************************************
*   Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
*	Codifica e decodifica con RSA
*   Capitolo 5.9 pag. 128 e
*   Capitolo 9.6.2 pag. 271 
*********************************************************/
 


{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(n)/log(30))-1; 
     while(i>0, s = concat(s,alfabeto[num\(30^i)+1]); num = num % (30)^i;i--); 
             \\ n \ 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);
}
{genera_chiave_rsa(len,p,q,n,e,d)=
	 if (len <= 1, print("Errore: il numero di cifre di n deve essere almeno 2"); return);
	 p=2;q=2;
	 print(len);
	 print(len\2+ 2*floor(sqrt(len)));
	 print(len\2 - floor(sqrt(len)));
     until (((isprime(p) && isprime(q))),
               p = nextprime(random(10^(len\2+ 2*floor(sqrt(len))))); 
               q = nextprime(random(10^(len\2 - floor(sqrt(len))))); 
     );
     n = p*q; phin = (p-1)*(q-1);
     e = random(phin);
     while(gcd(e,phin)!=1,e=e+1);
     d = lift(Mod(e,phin)^(-1));
     blocco=floor(log(n)/log(30));
     print("La lunghezza massima del blocco codificabile e': ", 
               blocco," caratteri");
     return([n,e,d]);
}
{rsa_cifra(messaggio, n, e) = local(l,i,j);
             l=length(messaggio);
             i=floor(log(n)/log(30));
             if (l>i, print("Errore: il messaggio e' di ", l, " caratteri ma non deve essere piu' di ", i," caratteri"); return);
             lift(Mod(da_messaggio_a_numero(messaggio,n),n)^e);
}
{rsa_decifra(segreto, n, d)  = 
             da_numero_a_messaggio(lift(Mod(segreto,n)^d));
}
             
             
                   
/*  ESEMPIO
genera_chiave_rsa(100)
La lunghezza massima del blocco e': 69 caratteri
%144 = [12060264452559942700098788007730655692673584053441309338727306637752487121122557574606423774344513477197, 9973986523701691273536077223196826950101830421286308369194901980858760367069649073680806500488610442553, 391738269573768390792972889622782071075553018719778520040018577878985107081825093913832255125673742917]
? rsa_cifra("SALACABULA; MAGICABULA; BIBIDI; BOBIDI; BU; FA LA MAGIA",%144[1],%144[2])
%148 = 223457737783392628977118202888587856457804427440789455872805918845425823087475598108583164147359836337
? rsa_decifra(223457737783392628977118202888587856457804427440789455872805918845425823087475598108583164147359836337,%144[1],%144[3])
%149 = "SALACABULA; MAGICABULA; BIBIDI; BOBIDI; BU; FA LA MAGIA              "
? rsa_cifra("SALACABULA; MAGICABULA; BIBIDI; BOBIDI; BU; FA LA MAGIA TUTTO QUEL CHE VUOI TU",%144[1],%144[2])
Errore: il messaggio e' di 78 caratteri ma non deve essere piu' di 69 caratteri
  */