DIY Cryptography with Raku

Part 2: Base 400

See also: The Introduction | Part 1: Base 36.

The «one to one» mapping problem can be solved by adding each character several times to the base, and choosing one of the indices when we encode that character. I have chosen to do it 10 times, and this gives me a base with 400 characters:

my @base400 = (@base40 xx 10).flat;

Now we have the base 40 alphabet, ten times after each other. Alphabetical order isn't good, so I'll randomize it:

my @base400 = (@base40 xx 10).flat.pick(*);

«pick» without an argument selects one random element from the list. If we specify an integer argument, that number of elements are returned without repetition (of the indices. If we have duplicates in the list, we can get duplicates from «pick».) If we specify «*», we get the whole list, in random order.

See docs.raku.org/routine/pick for more information about «pick».

When the encoder reads an «A» in the plain text, it chooses one of the «A»'s in this list. We can print it out, with e.g. 60 characters on each line to make it fit the width of the web page, to make it clearer.

I have highlighted the «A»s  like this  to make them stand out:

> say @base400.splice(0,60).join while @base400;
SPTXJEV52S85QDER45T6!7AMM.1RA9WOULQR002B28ESJ0B9?CKGGU0RBC1
QQVP!3Q!N.9 CZ2XMI?Q366B4U? 7C!6FNZU4FBQ1 IA6SK0ON4HD6LH!Y1F
OJ81FL9W3T!88IYR39RO F6.ZWCXL791V0BF6TJYB723P0ACEF3VHTU L.3Z
ZTSP8.O7ILH55 I!T?W3QVE7XG26S?72CTYXWCM.WKJO4KIUDD1NHXDIBPHG
Y70KZ7A4KU.9NASFP5PQ!EMJKKIXJIM0DHT4UVY ?AYI5LYG9O4GGVDZC!CK
28JAE GNR1UD.P5JWQ33L6VD.OVPVG2ZZP?MWTYK5A8R4HFON!X BEL?DM8J
X5GYAL 9H9WOU0S4F?SE.1RMW8ZNHR12MBE?NN7X

A Secret Key

This actually means that the we can share the algorithm with anybody, without compromising encrypted messages. As long as the key is kept secret.

A random order key (as the one shown above) only works if both parties (sender & receiver) know it. But instead of hard coding a single key in the module, I have decided to let the user do it by running a program that sets up several keys in a separate file («lib/Cryptoish/Secret.rakumod», called the Secret File) used by the encryption library. Choosing which key to use is done by the user as a two letter base 40 value (called the key ID), giving a total of 1600 possibilities. So the file is set up with 1600 different keys, making all the combinations legal.

This Secret File (note the word «secret») should only be shared with the recipient. If the sequences are compromised, simply run «mksecret» again. And share the Secret File again. (Or have several Secret Files in reserve, at both ends.)

constant @base40 := (0 .. 9, "A" .. "Z", " ", ".", "?", "!").flat;  # [1]

sub get-base ($multiplier = 10)
{
  return (@base40 xx $multiplier).flat.pick(*);   # [2]
}

my $fh = open :w, 'lib/Cryptoish/Secret.rakumod'; # [3]

$fh.say: "use v6";                                # [3]

$fh.say: '';
$fh.say: 'unit module Cryptoish::Secret;';        # [3]
$fh.say: 'our %base;';                            # [3]

for @base40 -> $a                                 # [4]
{
  for @base40 -> $b                               # [4]
  {
    $fh.say: '%base{"' ~ $a ~ $b ~ '"} = "' ~ get-base.join ~ '";'; # [5]
  }
}
$fh.close;                                        # [6]
say "OK";

[1] The base 40 characters.

[2] We take the 40 characters, duplicates them 10 times, and return them as a string in random order.

[3] Writing to the «Cryptoish/Secret.rakumod» file.

[4] A loop iterating over every two character combination of our base 40, that is 1600 times.

[5] Setting up a random string for each of the keys.

[6] Closing the file is considered good form, though not actually required in most cases.

Then we should run the program to set up the keys:

$ raku mksecret
OK

Take a look at the generated file:

use v6;

unit module Cryptoish::Secret;
our %base;
%base{"00"} = ...

It is large; 1604 lines (and 668853 bytes on a system with Unix style newlines).

Note that the zip file with the source code does actually come with a predefined secret file, even if that is a huge security risk. Do not use the out-of-the-box file!

This module cannot be installed (by zef), as we rely on the «mksecret» program writing the Secret File to the «./lib» directory.

Encryption

unit module Cryptoish;

use Cryptoish::Secret;

constant @base40 := (0 .. 9, "A" .. "Z", " ", ".", "?", "!").flat;
constant $base    = 400;
constant $wrapper = 36;

our subset Alphabet of Str where { /^@base40+$/ };

our sub encrypt (Alphabet $key, Alphabet $text)
{
  my $idx = 0;
  my %values;
  %values{$_}.push($idx++) for %Cryptoish::Secret::base{$key}.comb;

  return $text.flip.comb.map( { %(%values).{$_}.pick * $base ** $++ } )
    .sum.base($wrapper);
}

I have added an extra twist with .base($wrapper) on the integer value, resulting in a base 36 string.

use lib "lib";

use Cryptoish;

sub MAIN (Cryptoish::Alphabet $key, Str $text)
{
  say Cryptoish::encrypt($key, $text);
}

Trying it out:

$ raku encrypt FE 'HELLO ARNE'
2UTO1IBXSQASJOXVW

$ raku encrypt FE 'HELLO ARNE'
4T255P4A15V7FHMLG

We get a different value each time we run «encrypt», as it chooses one of the ten versions of each letter at random.

Use quotes if the string contains a space character. Use single quotes (') and not double quotes (") to prevent the shell from playing havoc with «!».

The first time you run this after setting up the Secret File with «mksecret», it will take some time as the module is precompiled before the program can use it. Running it again after that first time is much faster (running in about 5% of the time when I timed it).

See docs.raku.org/language/faq#index-entry-Precompile_(FAQ) for more information about precompilation.

Random numbers as generated by a computer are not really random, but pseudorandom. In most cases the difference doesn't matter, but in cryptography it matters a lot. (See e.g. www.quora.com/Why-is-randomness-important-in-cryptography for more information.)

The (pseudo)random number generator in Raku is probably quite good, but you shouldn't bet your life on it. And I did just that. (Not my life, but at least the randomness of the encryption algorithm.) Twice. First when setting up the Secret File, and then on choosing the version of each letter when endoding them.

I'll discuss the randomness of random in Part 4: Postscript.

Decryption

our sub decrypt (Alphabet $key, Str $value)
{
  my @result;

  my $number = $value.parse-base($wrapper);
  while $number
  {
    @result.push(@(%Cryptoish::Secret::base{$key}).substr($number % $base, 1));
    $number = $number div $base; 
  }
  return @result.reverse.join;
}

The base 36 twist is handled by .parse-base($wrapper).

use lib "lib";

use Cryptoish;

sub MAIN (Cryptoish::Key $key, Str $value)
{
  say Cryptoish::decrypt($key, $value);
}

Trying it out:

$ raku decrypt FE 2UTO1IBXSQASJOXVW
HELLO ARNE

$ raku decrypt FE 4T255P4A15V7FHMLG
HELLO ARNE

Using a wrong key will give something else:

$ raku decrypt FF 2UTO1IBXSQASJOXVW
KRHGRG2L8W

And again, if we change or remove a letter the message changes.

We could add a checksum mechanism, so that we can see if the message has been tampered with. But that has an obvious benefit for an attacker, as it can be used to check that a candidate for a decoded message is valid. And that is a very bad thing.

So any additional security, as a checksum or a mechanism for signing the message, should be added on top of this encryption protocol. Essentially adding another layer of complexity. This is why I have chosen to implement all the programs as simple wrappers around procedure calls. If you want to add e.g. a checksum, you can do so in the programs without changing the procedures. Something like this, to decrypt:

use lib "lib";

use Cryptoish;

sub MAIN (Cryptoish::Key $key, Str $value)
{
  say custom-decrypt(Cryptoish::decrypt($key, $value));
}

sub custom-decrypt($string)
{
  my $decrypted = foobar($string);
  return $decrypted if $decrypted;
  die "Message has been tampered with.";
}

This file is not included in the zip file, as it doesn't work (as «foobar» isn't implemented). If you want another level of encryption (or verification), as shown here, feel free to have a go at it. Remember to implement both encryption and decryption.

Unbreakable?

I have combined an algorithm (base 40; which basically is a one to one mapping) with a secret key (400 characters long). If you send relatively short messages (and I am beeing relatively vague on purpose, so that I cannot be arrested on this claim), and use a new key for each one, you are essentially using a One-time pad - and you have unbreakable encryption.

How many different permuations (distinct keys) do we have?

We have 400 characters, so it they were unique we'd get 400! (that is 400 * 399 * .. * 1) permutations. That is a very large number, with 869 digits.

> say [*](1..400);           # -> 640...
> say ( [*](1..400) ).chars  # 869

But that number is way too high, as we have ten instances of e.g. the character «A», and it doesn't matter if we swap e.g. the third and seventh «A». We have 10! possible permutations of the letter «A»s if we take them on their own, so if we divide the first number by this we have removed the internal «A» permutions from the equation.

We have 40 distinct characters, so we'll do that for all 40, giving the answer: 400! / (10! ** 40)

> say [*](1..400) / ( [*](1..10) * 40);           # -> 260...
> say ([*](1..400) / ( [*](1..10) * 40) ).chars;  # -> 607

So the number of distinct keys is a number with 607 digits. That is also a very large number. For comparison, the total number of atoms in the observable universe is a number with about 80 digits.

Keeping the Keys Secret

If you communicate with several different people, it is a security risk to share all the keys with everybody. Let us consider a set up with three users; A, B and C:

A can decide to use the key with ID "CW" to communicate with B, and the key with ID "KJ" with C. And then distribute the key to the recipient only. B and C must then manually edit their Secret File with the new key. They choose to use the same key ID, for sanity reasons. Then C decides to communicate with B, and chooses his "CW" key (which is different from A's). Giving that key to C causes a key collision. We can fix this by renaming the key ID when receiving them, but that can cause a mess. Especially if decryption fails, and the receiver and sender must figure out what went wrong. They cannot just say the key ID to figure out that they use the same key, but must resend the entire key itself - which is an obvious security disaster.

The solution to this problem is to add support for more than one Secret File, and deciding which one to use (other than the default) by a new command line option. Then A can simply set up one Secret File for communication with B, and another one with C.

The changes in the code are shown  like this . I'll start with the scripts, as they only require minor changes:

use lib "lib";

use Cryptoish;

sub MAIN (Str $key, Str $text, :$secret)
{
  say Cryptoish::encrypt($key, $text, :$secret);
}

use lib "lib";

use Cryptoish;

sub MAIN (Cryptoish::Alphabet $key, Str $value, :$secret)
{
  say Cryptoish::decrypt($key, $value, :$secret);
}

We can specify the Secret File to use (instead of the default one) with the optional named argument «--secret». But we need the changes in the module before we can use it.

unit module Cryptoish::Secret;  # [1]
our %base;                      # [3]

our sub get-secret($key) is export { return %base{$key}; } # [2]

%base{"00"} = ...

[1] The name of the module, as specified on this line, must match the file name. So the additional Secret Files will have their own module and file names.

[2] I want the programs to be able to use the same code to access the keys, regardless of which module we loaded the keys from. We can write a wrapper function to access the key, and import that function into the program (as set up by «is export»).

[3] The «%base» variable is now private («my» instead of «our»), as we use the procedure to access it from outside the module.

We can take a look at an alternate Secret File, with the module name in the code as well as the file name:

unit module Cryptoish::Secret::axiom;

Then we'll modify «mksecret» so that it can get an optional file name (module name) to write to:

unit sub MAIN ($name = "");  # [1]

if $name.chars
{
  die "Illegal name \"$name\" (use 2-10 characters; a..z 0..9)"
    unless $name ~~ /^<[a..z 0..9]> ** 2..10 $/;  # [2]
}

constant @base40 := (0 .. 9, "A" .. "Z", " ", ".", "?", "!").flat;

sub get-base
{
  return (@base40 xx 10).flat.pick(*);
}

my $file = $name ?? "lib/Cryptoish/Secret/$name.rakumod"
                 !! 'lib/Cryptoish/Secret.rakumod';  # [3]

my $fh = open :w, $file;

$fh.say: "use v6;";

$fh.say: '';
$fh.print: 'unit module Cryptoish::Secret';
$fh.print: "::$name" if $name; # [4]
$fh.say: ';';
$fh.say: 'my %base;';
$fh.say: '';
$fh.say: 'our sub get-secret($key) is export { return %base{$key}; }';  # [5]
$fh.say: '';

for @base40 -> $a
{
  for @base40 -> $b
  {
    $fh.say: '%base{"' ~ $a ~ $b ~ '"} = "' ~ get-base.join ~ '";';
  }
}

$fh.close;

say "Written file $file";  # [6]

[1] An optional file- and module name to write to.

[2] The name, if given, must be from 2 to 10 characters long (both included) and can only consist of digit (0-9) and lower case letters (a-z).

[3] The name of the file.

[4] Add the alternate module name, if used.

[5] The accessor function, used to get the data.

[6] Include the file name in the message.

The «axiom» file hinted at above can be generated like this:

$ raku mksecret axiom
Written file lib/Cryptoish/Secret/axiom.rakumod

It is recommended to generate the default Secret File as well (by running «mksecret» without the optional argument), so that the module has a fall back. But on the other hand, not having a fallback ensures that the Secret File must be specified explicitly each time (and thus reducing the risk of using the default file too often).

The changes to the main module are tricker. We used «use» to load the Secret File module, but that doesn't work now as «use» loads the module at compile time. And the name is first available after we have parsed the arguments, when we run the program.

The «require» keyword also loads modules, but at runtime. We have an additional complication as we have the module name as a variable. «require» (and «use») do not like variables, so we have to use the ::($variable) string prefix syntax to turn a string into a variable name (or in this case, a module name) at runtime.

See my Raku Colonoscopy article for more information about the ::($variable) syntax. Scroll down to the section with that name, almost at the end.

See docs.raku.org/language/modules#use for more information about «use».

See docs.raku.org/language/modules#require for more information about «require».

sub load-it ($secret = "")
{
  my $name = $secret ?? "Cryptoish::Secret::$secret" !! "Cryptoish::Secret";
  require ::($name) '&get-secret';
  return &get-secret;
}

our sub encrypt (Alphabet $key, Alphabet $text, :$secret)
{
  my &get-secret = load-it($secret);

  my $idx = 0;
  my %values;
  %values{$_}.push($++) for &get-secret($key).comb;

  return $text.flip.comb.map( { %(%values).{$_}.pick * $base ** $++ } )
    .sum.base($wrapper);
}

our sub decrypt (Alphabet $key, Str $value, :$secret)
{
  my &get-secret = load-it($secret);
  
  my $result = "";

  my $number = $value.parse-base($wrapper);
  while $number
  {
    $result ~= @( &get-secret($key) ).substr($number % $base, 1);
    $number = $number div $base; 
  }
  return $result.flip;
}

The global «use» line has gone, and the procedures use the «load-it» wrapper function to load the correct module (the Secret File) and get a pointer to the «get-secret» function at runtime. «require» (and «use») are lexically scoped, so we have to resort to the trick of returning a pointer to the procedure, as it would only have been available inside «load-it» otherwise. When we prepend a function with «&» we get a reference to it (and as «&» is a sigil, we have a variable) instead of calling it. Executing a function in a variable is done by appending parens, either empty (e.g. &come-here()) or around one or more arguments (e.g. &go-to("me")).

I used a procedure (load-it) as the alternative was to add the code in the procedure body everywhere. A macro (see docs.raku.org/syntax/macros) would have been perfect, but they are experimental.

Now A, B and C can exchange complete Secret Files with each other, but different files for different persons so that they cannot use it to decrypt information not meant for them.

«A» sends the Secret File «axiom» to «B», and they use it when communicating. «A» sends the «naxos» Secret File to «C», and they use it when communicating. Finally «C» sends the Secret File «lance» to «B», and they use it when communicating.

The person generating the Secret File chooses the name, but should ensure that the chosen name is ok for the recipient (not taken already). It may also be useful to choose a name that makes sense for the given relationship.

Part 3: Changing Keys

See the next part; Part 3: Changing Keys.