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

```

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

Enable tabbed editor view for this editor

Use the dark theme

-g

-O0

-gnata

-gnatW8

-gnatwa

-gnatyg0-s

-gnatyM50

-gnatyM80

-gnato

-gnato0

-gnato11

-gnato21

-gnato22

-gnato23

-gnateE

-gnatX

```

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:

```

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

Enable tabbed editor view for this editor

Use the dark theme

-g

-O0

-gnata

-gnatW8

-gnatwa

-gnatyg0-s

-gnatyM50

-gnatyM80

-gnato

-gnato0

-gnato11

-gnato21

-gnato22

-gnato23

-gnateE

-gnatX

```

## Big Reals

In addition to `Big_Integer`, Ada 2022 provides Big Reals.