\\ Pedro Patricio, 2007
/*
-- breve how-to --
Antes de mais, é necessário criar uma chave. Para tal, basta fazer
> gerachave(n)
onde o n indica o numero de bits da chave; por exemplo,
> chave=gerachave(1024)
gera uma chave com 1024 bits

Para cifrar um texto, usa-se a funcao 
> cifrar("TEXTO", chave)

Existem duas questoes: #1 o "TEXTO" nao pode ter muitos caracteres em relacao ao numero de bits da chave. #2 APENAS se admitem MAIUSCULAS no texto. Por exemplo
> texto=cifrar("OLA",chave)

se tudo correu bem, 
> decifrar(texto,chave)
mensagem numerica decifrada 797665
passando para alfanumerico...
 = "OLA"
*/



{
tamanho(n)=floor(log(n)/log(2))+1
}

{
procuraprimo(nbits)=
	primo=2;
	while(tamanho(primo)!= nbits,
		primo=nextprime(random(2^nbits))
	);
	return(primo)
}

{
gerachave(n)=
	/* parte I: encontrar os primos p e q */
	bitprimo=round(n/2);
	p=2;
	q=2;
	while(tamanho(p*q) != n,
		print("encontrando um p com  ", bitprimo, " bits..."); 
		p = procuraprimo(bitprimo);
		print("p tem ", tamanho(p), " bits.");
		print("encontrando um q com  ", n-tamanho(p)," bits..."); 
		q = procuraprimo(n - tamanho(p));
		print("q tem ", tamanho(q), " bits.");
		if(tamanho(p*q) != n,
			print("p*q tem "tamanho(p*q)" bits... vou procurar outros...")
		);
	);
	/* parte II: encontrar e primo relativo com phi(p*q) */
	phi=(p-1)*(q-1);
	print("gerando a chave publica ...");
	e=p-1;
	while( gcd(e,phi)!=1,
		e=random(phi)
	);
	/* parte III: encontrar o inverso de e mod phi */
	print("gerando a chave privada...");
	d=lift(Mod(e^(-1),phi));
	return([p*q,e,d])
}
	

{

cifrar(texto,vectorchave)=
	lista=Vecsmall(texto); 
	tamanholista=length(lista); 
	mensagem=0; 
	for(j=0,tamanholista-1,
		mensagem=mensagem+10^(2*j)*lista[tamanholista-j]
	);
	if(mensagem> vectorchave[1],
		error("ooops... o texto e' demasiado grande para a chave :-(")
	);
	print("mensagem numerica ... "mensagem);
	print("usando o expoente de encriptacao "vectorchave[2]," mod "vectorchave[1]);
	cifrado=lift(Mod(mensagem,vectorchave[1])^vectorchave[2]);
	print("a mensagem cifrada e' " cifrado);
	return(cifrado);
}	

{
decifrar(mensagem,vectorchave)=

	local(comp,decifrado,alfanum,caract, mensdesc);

	decifrado=lift(Mod(mensagem,vectorchave[1])^(vectorchave[3]));
	print("mensagem numerica decifrada "decifrado);
	print("passando para alfanumerico..."); 
	comp=floor(log(decifrado)/log(10))+1; 
	alfanum=listcreate(comp/2); 
	for (j=1,comp/2,
		caract=decifrado%10^(2); ;
		decifrado=decifrado\10^(2); 
		listput(alfanum,Strchr(caract),j);	
	); 
	\\ passar a lista para palavra	
	kill(mensdec); mensdec=""; 

	forstep(j=comp/2,1,-1,
		mensdec=concat(mensdec,alfanum[j]); 
	);
	return(mensdec);
}