Big numbers are supported by
GNAT Community Edition 2020
GCC 10 (draft, no user defined literals)
Ada 2022 introduces big integers and big real types.
Big_Integer and corresponding operations such as comparison
Greatest_Common_Divisor. The type also has
Put_Image aspects redefined, so you can use it in a natural
Ada.Text_IO.Put_Line (Big_Integer'Image(2 ** 256));
Tiny RSA implementation
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
m ** d, because these are really big numbers and the result
won't fit into memory. However, if you keep intermediate result
n during the md calculation, it will work. Let's write this operation
as a function:
-- 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);
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 is the original message m. Easy!
Here is the complete code snippet:
In addition to
Big_Integer, Ada 2022 provides Big Reals.