errore := function (arg)

## Riporta un messaggio di errore o informazione, senza ritornare
## Messaggio di default molto utile

local TESTO;

if Length(arg) > 0
then
TESTO := arg[1];
else
TESTO := "Very useful error message\n";
fi;
Print(TESTO, "\n");
return;

end;

# Piccola palestrina per giocare con RSA
# Funziona solo con testi composti di sole lettere maiuscole, please!!!

# ic/ci trasformano caratteri in numeri e v.v.
# A..Z -> 0..25

# findBlocklength ci dice quanti caratteri si possono impacchettare in
# un numero non più grande di n

# padString aggiunge "X"  alla fine di una stringa finché non è lunga un
# multiplo di blocklength

# findR dato n trova r invertibile modulo Phi(n)
# findRandS trova anche l'inverso -> [r, s]

# findRLP trova un esponente r che abbia periodo più piccolo di period
# -> [r, period]

# is trasforma una stringa in successione di interi, data la blocklength
# si fa il viceversa

# findS calcola s a partire da r e n

# RSAencodeIS applica  RSA una stringa, calcolandosi  la blocklength e
# facendo il padding. Emette una successione di numeri

# RSAencodeII fa tutto su successioni di numeri
# RSAdecodeII e RSAdecodeSI si spiegano da sé

# findN generates suitable n, about the size of N

Print("\n");
Print("\n");

Print("findPQ(SIZE) restituisce una lista [p, q]\n");
Print("dove p e q sono primi, e p * q è circa SIZE\n");

Print("\n");

Print("tenToB (n, B) gives B-ary digits\n");

Print("\n");

tenToB := function(n, B)

local res;

res := [];

while n > 0 do
Add(res,EuclideanRemainder(n,B)); 
n := EuclideanQuotient(n,B); 
od;

return res;

end;

findPQ := function (SIZE)
# generates suitable n = p * q, about the size of SIZE
local sq, delta, p, q;

sq := RootInt(SIZE);

delta := Random([2..sq]);

p := NextPrimeInt(Maximum([3, sq-delta]));

q := NextPrimeInt(Maximum([Int(SIZE/p), p]));

return [p, q];
end;

ic := function(c) return INT_CHAR(c) - INT_CHAR('A'); end;
ci := function(c) return CHAR_INT(c + INT_CHAR('A')); end;

findBlocklength := function (n)

local blocklength, temp;

blocklength := -1; temp := n;

repeat
      blocklength := blocklength+1;
      temp := EuclideanQuotient(temp,26);
until temp = 0;

return blocklength;

end;

padString := function(stringa, blocklength)

while EuclideanRemainder(Length(stringa), blocklength) > 0 do
      Add(stringa,'X');
od;

return stringa;

end;

errore(" ");
errore("findR([p, q]) calcola un intero r coprimo con Phi(n),");
errore("(ove n = p * q)");
errore("che si possa dunque usare come esponente per cifrare nell'RSA");
errore(" ");

findR := function(pair)
# Trova un esponente r adatto a dare RSA modulo n
local phi, r;
phi := (pair[1]-1)*(pair[2]-1);
repeat 
       r := Random([2..phi]);
until Gcd(r, phi) = 1;
return r;
end;

findRandS := function(pair)
# Come findR, ma ti dice [r, s],
# ove s è l'inverso di r modulo Phi(n)
local phi, r, s, 
      p, q, n;
p := pair[1]; q := pair[2];
n := p * q;

phi := (p - 1) * (q - 1);
repeat 
       r := Random([2..phi]);
until Gcd(r, phi) = 1;
s := GcdRepresentation(r,phi)[1];
if s < 0 then s := s + Phi(n); fi;
return [r, s];
end;

findRLP := function (n, period)
# Trova un r come sopra ma di periodo <= period
# ritorna [r, periodo di r]
local powers, r, i, res, phi;
phi := Phi(n);
repeat
	r := findR(n);
	powers := []; res := r;
	for i in [2..period] do
	    res := res * r mod phi;
	    Add (powers, res);
	od;
until 1 in powers;
return [r,Position(powers,1)+1];
end;

is := function(stringa, blocklength)
local i, j, cod, res, noofblocks;
#Assumes correct length, i.e. skips remainder tail

noofblocks := EuclideanQuotient(Length(stringa), blocklength);

## Print("Number of blocks is ", noofblocks, "\n");

res := [];

for i in [0..noofblocks-1] do
    cod := 0;
    for j in [blocklength-1,blocklength-2..0] do
	cod := cod * 26 + ic(stringa[i * blocklength + j+1]);
##	Print("Intermediate value is ", cod, "\n");
    od;
    Add(res, cod);
od;

return res;

end; #is

si := function(res, blocklength)
local stringa, i, j, cod;

## Print ( "Length is ", Length(res), "\n");

stringa := [];

for i in [1..Length(res)] do
    cod := res[i];
	for j in [1..blocklength] do
	      Add(stringa,ci(EuclideanRemainder(cod,26)));
	      cod := EuclideanQuotient(cod,26);
	od;	
od;

return stringa;

end; #si

errore(" ");
errore("findS(r, [p, q]), ove n = p * q, e r è coprimo con Phi(n),");
errore("calcola un intero s tale che r * s = 1 (mod Phi(n)),");
errore("dunque s si usa come esponente per decifrare nell'RSA.");
errore(" ");

findS := function(r, pq)
local temp, phi;

phi := (pq[1] - 1)*(pq[2] - 1);
temp := GcdRepresentation(r,phi)[1];
while temp <0 do
temp := temp + phi;
od;
return temp;
end;

errore(" ");
errore("RSAencode(TESTO, r, n), ove r è coprimo con Phi(n),");
errore("cifra il TESTO (solo lettere maiuscole non accentate)");
errore("usando RSA in una successione di numeri compresi fra 0 e n");
errore(" ");



RSAencodeIS := function (stringa, r, n)
# da stringa di lettere a lista di numeri
local res, x, blocklength, temp;

blocklength := findBlocklength(n);

## Print("Blocklength is ", blocklength, "\n");

#Print(blocklength);

stringa := padString(stringa, blocklength);

res := is(stringa, blocklength);

res := List(res, x -> PowerMod(x,r,n));

return res;

end;

RSAencode := RSAencodeIS;

RSAencodeII := function (res, r, n)
# da stringa di lettere a lista di numeri
local blocklength, temp;

blocklength := -1; temp := n;

repeat
      blocklength := blocklength+1;
      temp := EuclideanQuotient(temp,26);
until temp = 0;

## Print("Blocklength is ", blocklength, "\n");

#Print(blocklength);

#while EuclideanRemainder(Length(stringa), blocklength) > 0 do
#      Add(stringa,'X');
#od;

#res := is(stringa, blocklength);

res := List(res, x -> PowerMod(x,r,n));

return res;

end;

RSAdecodeII := function (res, s, n)
# da lista di numeri a lista di numeri
local x;

return List(res, x -> PowerMod(x,s,n));

end;

errore(" ");
errore("RSAdecode(SUC_NUM, s, n), ove s è coprimo con Phi(n),");
errore("decifra la successione di  numeri compresi fra 0 e n SUC_NUM");
errore("(ottenuta mediante RSA, usando r e n)");
errore("ricavando il testo originale. Qui s è tale che");
errore("r * s = 1 (mod Phi(n))");
errore(" ");


RSAdecodeSI := function (res, s, n)
# da lista di numeri a stringa di lettere
local stringa, noofblocks, i, j, cod, x, blocklength, temp;

blocklength := -1; temp := n;

repeat
      blocklength := blocklength+1;
      temp := EuclideanQuotient(temp,26);
until temp = 0;

Print("Blocklength is ", blocklength, "\n");

noofblocks := Length(res);

res := List(res, x -> PowerMod(x,s,n));

stringa := si(res, blocklength);

return stringa;

end;

RSAdecode := RSAdecodeSI;

tryAndDecodeSmallPeriod := function (res, r, n)
# assumes r has small period, and try and decode by encoding

local text, blocklength, iteration, i, DELAY;

DELAY := 100000000;

blocklength := findBlocklength(n);

for iteration in [1..100] do

text := si(res, blocklength);

Print("Encoding (iteration #", iteration, ")... ", 
		text, "\n");

for i in [1..DELAY] do od;

res := RSAencodeII (res, r, n);

od;

end;

findPeriodOfExponent := function (r, n)
# Dumb method, there should be something better in GAP

local i, temp;

temp := 1;

for i in [1..n] do
if i mod 100000 = 0 then Print("Trying ",  i, "\n"); fi;
temp := temp * r mod Phi(n);
if temp = 1 then return i; fi;
od;

end;

findPeriodOfExponentFaster := function (r, n)
# Dumb method, there should be something better in GAP

local p, factors, candidateInt, phi, phiphi;

phi := Phi(n);
phiphi := Phi(phi);

factors := FactorsInt(phiphi);
## Set(factors);

candidateInt := phiphi;

for p in factors do
Print(p, ", ", candidateInt, "\n");
if PowerMod(r, candidateInt/p, phi) = 1 
then
candidateInt := candidateInt/p;
fi;
od;
return candidateInt;
end;

baseTwo := function(n)
local res;
res := [];
while n > 0 do
Add(res, EuclideanRemainder(n, 2));
n := EuclideanQuotient(n, 2);
od;
return res;
end;

detailedPower := function(b, e, n)
local expo, factors, x, c, alreadyprinted;

expo := baseTwo(e);
factors := [];
c := b;
for x in expo do
Add(factors, c);
c := PowerMod(c, 2, n);
od;
for x in [1..Length(factors)] do
Print(b, "^", 2^(x-1), " = ", factors[x], " (mod ", n, ")\n");
od;
Print(e, " = ");
alreadyprinted := false;
for x in [1..Length(expo)] do
if expo[x] = 1 then
if alreadyprinted then
Print(" + ");
fi;
Print(2^(x-1));
alreadyprinted := true;
fi;
od;
Print("\n");
Print(b, "^", e, " = ");
alreadyprinted := false;
for x in [1..Length(expo)] do
if expo[x] = 1 then
if alreadyprinted then
Print(" * ");
fi;
Print(factors[x]);
alreadyprinted := true;
fi;
od;
Print (" = ", PowerMod(b, e, n), " (mod ", n, ")\n");
return;
end;

RSAprepare := function(N, numProducts)
local tmp, p, q, n, r, s;
repeat
tmp := findPQ(N);
p := tmp[1]; q := tmp[2]; n := p * q;
r := findR([p,q]); s := findS(r, [p,q]);
tmp := baseTwo(s);
until ((Length(tmp) - 1 + Sum(tmp) - 1) = numProducts);
return [p,q,r,s];
end;

Print ("# findPQ := function (SIZE)\n");
Print ("# findR := function([p,q])\n");
Print ("# findS := function(r,[p,q])\n");
Print ("# RSAencode := function (stringa, r, n)\n");
Print ("# RSAdecode := function(successione_di_numeri, s, n)\n");
Print ("# is(stringa, blocklength); si(seqofno, blocklength);\n");
Print ("# baseTwo:= function(number);\n"); 
Print ("# detailedPower := function(base, exponent,modulo);\n");
Print ("# RSAprepare := function(N, numProducts);\n");