-- file books\Ada\PIA10\website\RSA.txt

with Ada.Numerics.Big_Numbers.Big_Integers;
package Big renames Ada.Numerics.Big_Numbers.Big_Integers;


with Big; use Big;
package RSAdata is
	N: Big_Integer;      -- public key
	P, Q: Big_Integer;   -- N = P*Q where P and Q should be prime
	M: Big_Integer;      -- (P-1)*(Q-1)
	E: Big_Integer;      -- encryption power
	D: Big_Integer;      -- decryption power
end RSAdata;


with Big; use Big;
function GCD(X, Y: Big_Integer) return Big_Integer is
begin
	if Y = 0 then
		return X;
	else
		return GCD(Y, X rem Y);
	end if;
end GCD;


with Big; use Big;
function Mersenne(P: Integer) return Big_Integer is
begin
	return 2**P - 1;
end Mersenne;


with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Big; use Big;
with Mersenne;
procedure Get_Num(N: out Big_Integer) is
	C: Character;
	P: Integer;
	EOL: Boolean;
begin
	Look_Ahead(C, EOL);
	loop
		exit when not EOL; 
		Skip_Line;
		Look_Ahead(C, EOL); 
	end loop;
	if C = 'M' or C = 'm' then
		Get(C); Get(P);
		N := Mersenne(P);
	else
		Get(P);  N := To_Big_Integer(P);   -- sort of Get(N);
	end if;
end Get_Num;


with Ada.Text_IO; use Ada.Text_IO;
with Big; use Big;
procedure Put_Num(N: in Big_Integer) is
begin
   Put(To_String(N, 0));
end Put_Num;


with Big; use Big;
function Inverse_Mod(E, M: Big_Integer) return Big_Integer is
	-- finds D such that E*D = 1 mod M 
	-- assume E and M are relatively prime
	D: Big_Integer;
	MM: Big_Integer;

	procedure GCD_Plus(X, Y: in Big_Integer;
				 MX, MY: out Big_Integer) is
		MNext_X, MNext_Y: Big_Integer;
		Q: Big_Integer;
	begin
		if Y = 1 then
			MX := 0;
			MY := 1;
		else
			-- divide X by Y giving quotient Q 
			Q := X/Y;
			GCD_Plus(Y, X rem Y, MNext_X, MNext_Y);
			MX := MNext_Y;
			MY := MNext_X - MNext_Y*Q;
		end if;	
	end GCD_Plus;

begin

	GCD_Plus(E, M, D, MM);
	D := D mod M;
	return D;	
end Inverse_Mod;


with Big; use Big;
function Encrypt(V, E, N: Big_Integer) return Big_Integer is
	-- computes V**E mod N
	Result: Big_Integer := 1;
	Exp: Big_Integer := E;
	Term: Big_Integer := V;

begin
	loop
		if Exp mod 2 = 1 then
			Result := Result*Term mod N;		-- include a term
		end if;
		Term := Term*Term mod N;			-- keep on squaring
		Exp := Exp/2;					-- and halving
		exit when Exp = 0;
	end loop;
	return Result;
end Encrypt;

with Big; use Big;
with Encrypt;
function Decrypt(C, D, N: Big_Integer)return Big_Integer renames Encrypt;

with Ada.Text_IO; use Ada.Text_IO;
with Big; use Big;
procedure Put_Message(N: Big_Integer) is
	S: String(1..1000);
	V: Integer;
	C: Character;
	Index: Integer := 0;
	NN: Big_Integer:= N;
begin
	loop
		V := To_Integer(NN rem 53);
		if V = 0 then
			C := ' ';
		elsif V < 27 then		–- upper case
			C := Character'Val(V+64);
		else				-- lower case
			C := Character'Val(V+70);
		end if;
		
		Index := Index + 1;
		S(Index) := C;

		NN := NN/53;		
		exit when NN = 0;		
	end loop;

	for I in reverse 1 .. Index loop
		Put(S(I));
	end loop;
end Put_Message;


-- Here is an alternative version which uses recursion to avoid
-- the explicit interim storage in the array S
--		
--		Head: Big_Integer;
--		Tail: Integer;
--	begin
--		Tail := Integer_Of(N rem 53);
--		Head := N/53;
--		if Head /= 0 then
--			Put_Message(Head);
--		end if;

--		if Tail = 0 then 
--			Put(' ');
--		elsif Tail < 27 then	–- upper case
--			Put(Character'Val(Tail+64));
--		else				-- lower case
--			Put(Character'Val(Tail+70));
--		end if;
--	end Put_Message;


with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Big; use Big;
with Encrypt, Decrypt;
with GCD;
with Get_Num;
with Inverse_Mod;
with Put_Message;
with Put_Num;
with RSAdata; use RSAdata;
procedure RSA is
	
	Coded       : Big_Integer;
	Decoded     : Big_Integer;
	Letter      : Character;
	Letter_Code : Integer;
	Max_Letters : Integer;
	Message     : Big_Integer;
	Numeric     : Boolean := True;

	function Get_Letter return Integer is
		Letter: Character;
	begin
		Get(Letter);
		if Letter = ' ' then
			return 0;
		end if;
		if Letter >='A' and Letter <= 'Z' then
			return Character'Pos(Letter) - 64;
		elsif Letter >='a' and letter <= 'z' then
			return Character'Pos(Letter) - 70;
		else 
			return 99;
		end if;
	end Get_Letter;

	function Do_Max_Letters return Integer is
		Max: Integer := 0;
		Message: Big_Integer:= 1;
	begin
		loop
			Message:= Message * 53;
			exit when Message >= N;   -- N is the public key
			Max := Max + 1;
		end loop;
		return Max;
	end Do_Max_Letters;

		
begin
<<Restart>>
	Put_Line("Welcome to the RSA cryptography system");
	Put_Line("Enter values for the two primes P and Q");
	Put("P = "); Get_Num(P);
	Put("Confirms P = "); Put_Num(P); New_Line;
	Put("Q = "); Get_Num(Q);
	Put("Confirms Q = "); Put_Num(Q); New_Line;
	N := P*Q;
	Put("N, the public key is = "); Put_Num(N); New_Line;
	Max_Letters := Do_Max_letters;
	M := (P-1)*(Q-1);	
	Put("M = (P-1)*(Q-1) is = "); Put_Num(M); New_Line;

	Put_Line("Enter value for the encoding key E");
	-- check E is relatively prime to M and ask for new E if not
	loop
		Put("E = "); Get_Num(E);
		Put("Confirms E = "); Put_Num(E); New_Line;
		exit when GCD(M, E) = 1;	-- exit if relatively prime
		Put("Sorry, E is not relatively prime to M = "); Put_Num(M); 
		Put_Line("  Please supply a new E");
	end loop;

	Put_Line("Computed D = "); 

	D := Inverse_Mod(E, M);

	Put_Num(D); New_Line;
	
loop
	
	Put_Line("Now ready to encrypt your message");
	loop
		Put("Do you want to supply a numeric or alpha message?");
		Put(" Answer N or A "); Get(Letter);
		if Letter = 'N' or Letter = 'n' then 
			Numeric := True;
			Put("Preparing for a numeric message not exceeding "); 
			Put_Num(N); New_Line;
			exit;
		elsif Letter = 'A' or Letter = 'a' then
			Numeric := False;
			Put("Preparing for a text message with max length "); 
			Put(Max_Letters, 0); New_Line;
			Put_Line("Include spaces and letters only");
			exit;
		else
			Put_Line("was not A or N; try again");
		end if;
	end loop;

	if Numeric then
		Put_Line("Message is "); Get_Num(Message);

		exit when Message = 0;		-- Zero

		Coded := Encrypt(Message, E, N);

		Put("The encrypted message is "); Put_Num(Coded); New_Line;
		Put("Now ready to decrypt your message"); Skip_Line(2);

		Decoded := Decrypt(Coded, D, N);

		Put("The decrypted message is "); Put_Num(Decoded); 
		New_Line(2);
	else	-- this is the alpha case
		Put_Line("Message is "); Skip_Line;

		Message := 0;   -- all spaces
		
		-- now get first alphabetic letter
		loop
			Letter_Code := Get_Letter;
			exit when Letter_Code > 0;
		end loop;
		exit when Letter_Code = 99;

		Message := To_Big_Integer(Letter_Code);
		for I in 2 .. Max_Letters loop
			Letter_Code := Get_Letter;
			exit when Letter_Code = 99;
			Message := Message * 53 + To_Big_Integer(Letter_Code);
		end loop;
		Skip_Line;
		Coded := Encrypt(Message, E, N);

		Put("The encrypted message is "); 
		Message := Coded;
		
		Put_Message(Message);

		New_Line;

		
		Put("Now ready to decrypt your message"); Skip_Line(2);

		Decoded := Decrypt(Coded, D, N);
		Message := Decoded;

		Put("The decrypted message is ");  New_Line(2);
		Put_Message(Message);
		New_Line(2);
		
	end if;
end loop;

	Put_Line("Bye bye");

	goto Restart;

end RSA;