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 :wikipedia:`RSA algorithm <RSA_(cryptosystem)> 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:

    
    
        
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 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