Big Numbers

Note

Big numbers are supported by

  • GNAT Community Edition 2020

  • GCC 11

  • GCC 10 (draft, no user defined literals)

Ada 2022 introduces big integers and big real types.

Big Integers

The package Ada.Numerics.Big_Numbers.Big_Integers contains a type Big_Integer and corresponding operations such as comparison (=, <, >, <=, >=), arithmetic (+, -, *, /, rem, mod, abs, **), Min, Max and Greatest_Common_Divisor. The type also has Integer_Literal and Put_Image aspects redefined, so you can use it in a natural manner.

Ada.Text_IO.Put_Line (Big_Integer'Image(2 ** 256));

115792089237316195423570985008687907853269984665640564039457584007913129639936

Tiny RSA implementation

Note

Note that you shouldn't use Big_Numbers for cryptography because it's vulnerable to timing side-channels attacks.

We can implement the RSA algorithm in a few lines of code. The main operation of RSA is (md) mod n. But you can't just write m ** d, because these are really big numbers and the result won't fit into memory. However, if you keep intermediate result mod n during the md calculation, it will work. Let's write this operation as a function:

    
    
    
        
pragma Ada_2022;

with Ada.Numerics.Big_Numbers.Big_Integers;
use  Ada.Numerics.Big_Numbers.Big_Integers;

--  Calculate M ** D mod N

function Power_Mod (M, D, N : Big_Integer) return Big_Integer;

    
        
function Power_Mod (M, D, N : Big_Integer) return Big_Integer is

   function Is_Odd (X : Big_Integer) return Boolean is
     (X mod 2 /= 0);

   Result : Big_Integer := 1;
   Exp    : Big_Integer := D;
   Mult   : Big_Integer := M mod N;
begin
   while Exp /= 0 loop
      --  Loop invariant is Power_Mod'Result = Result * Mult**Exp mod N
      if Is_Odd (Exp) then
         Result := (Result * Mult) mod N;
      end if;

      Mult := Mult ** 2 mod N;
      Exp := Exp / 2;
   end loop;

   return Result;
end Power_Mod;

Let's check this with the example from Wikipedia. In that example, the public key is (n = 3233, e = 17) and the message is m = 65. The encrypted message is me mod n = 6517 mod 3233 = 2790 = c.

Ada.Text_IO.Put_Line (Power_Mod (M => 65, D => 17, N => 3233)'Image);

2790

To decrypt it with the public key (n = 3233, d = 413), we need to calculate cd mod n = 2790413 mod 3233:

Ada.Text_IO.Put_Line (Power_Mod (M => 2790, D => 413, N => 3233)'Image);

65

So 65 is the original message m. Easy!

Here is the complete code snippet:

    
    
    
        
pragma Ada_2022;

with Ada.Text_IO;
with Ada.Numerics.Big_Numbers.Big_Integers;
use  Ada.Numerics.Big_Numbers.Big_Integers;

procedure Main is

   --  Calculate M ** D mod N

   function Power_Mod (M, D, N : Big_Integer) return Big_Integer is

      function Is_Odd (X : Big_Integer) return Boolean is
        (X mod 2 /= 0);

         Result : Big_Integer := 1;
         Exp    : Big_Integer := D;
         Mult   : Big_Integer := M mod N;
   begin
      while Exp /= 0 loop
         --  Loop invariant is Power_Mod'Result = Result * Mult**Exp mod N
         if Is_Odd (Exp) then
            Result := (Result * Mult) mod N;
         end if;

         Mult := Mult ** 2 mod N;
         Exp := Exp / 2;
      end loop;

      return Result;
   end Power_Mod;

begin
   Ada.Text_IO.Put_Line (Big_Integer'Image (2 ** 256));
   --  Encrypt:
   Ada.Text_IO.Put_Line (Power_Mod (M => 65, D => 17, N => 3233)'Image);
   --  Decrypt:
   Ada.Text_IO.Put_Line (Power_Mod (M => 2790, D => 413, N => 3233)'Image);
end Main;

Big Reals

In addition to Big_Integer, Ada 2022 provides Big Reals.

References