Cryptopals 33 - Implement Diffie-Hellman

TL;DR

Challenge 33 in Cryptopals.

So… set 5 starting! This is the caveat at the beginning:

This set is significantly harder than the last set. The concepts are new, the attacks bear no resemblance to those of the previous sets, and… math.

I hope the hard part is because it’s just new stuff and… math. I like math a lot, so I hope I’ll be fine.

We start with a request to implement the Diffie-Hellman key exchange algorithm, which is genius. I’ve seen analogies based on colors (including the Wikipedia page linked before), but I think that the most convincing demonstration that exchanging keys without others knowing is the following:

Alice writes a key and puts it in a very resistant box, locked with her very resistant padlock, and sends it to Bob.
Bob adds his very resistant padlock and sends the safe back to Alice. Now the safe is locked with two padlocks.
Alice receives the double-locked safe and removes her lock, sending the safe back to Bob.
Bob receives the safe back, removes his padlock and reads the key.

At no time an observer is able to open the safe and see the key.

Alas, it does not resemble Diffie-Hellman very much, but at least can help convicing people that it’s not black magic.

OK, on with the code now:

#!/usr/bin/env perl
package DiffieHellman;
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

use Math::BigInt;
use Digest;

use constant NIST_g => Math::BigInt->new(2);
use constant NIST_p => Math::BigInt->from_hex(<<'END' =~ s{\s+}{}grmxs);
ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024
e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd
3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec
6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f
24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361
c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552
bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff
fffffffffffff
END

sub new ($package, %args) {
   my %self;
   @args{qw< g p >} = (NIST_g, NIST_p) if $args{NIST_parameters};
   for my $key (qw< g p >) {
      my $hkey = $key . '_hex';
      $self{$key} = $args{$key} ? Math::BigInt->new($args{$key})
         : $args{$hkey} ? Math::BigInt->from_hex($args{$hkey})
         : die "missing value for $key";
   }
   $self{n_hex} = my $n = length $self{p}->to_hex;
   return bless \%self, $package;
}

sub generate_key_pair ($self) {
   my $secret_key = $self->_generate_secret_key;
   my $public_key = $self->_public_key_for($secret_key);
   return (__h2o($secret_key->to_hex), __h2o($public_key->to_hex));
}

sub joint_symmetric_keys ($self, $a_secret, $b_public) {
   my $secret = $self->joint_secret($a_secret, $b_public);
   my $auth_key = Digest->new('SHA-256')->add($secret)->digest;
   my $enc_key = substr $auth_key, 0, 128 / 8, '';
   return ($enc_key, $auth_key); # two 128-bit keys
}

sub joint_secret ($self, $a_secret, $b_public) {
   my $base = Math::BigInt->from_hex(__o2h($b_public));
   my $exponent = Math::BigInt->from_hex(__o2h($a_secret));
   my $secret = __modexp($base, $exponent, $self->{p});
   return __h2o($secret->to_hex);
}

sub _public_key_for ($self, $secret_key) {
   __modexp($self->{g}, $secret_key, $self->{p});
}

sub _generate_secret_key ($self) {
   while ('necessary') {
      my $candidate_hex = join '',
         map { sprintf '%0x', int rand 16 } 1 .. $self->{n_hex};
      my $candidate = Math::BigInt->from_hex($candidate_hex);
      return $candidate if $candidate < $self->{p};
   }
}

sub __local_modexp ($base, $exponent, $modulus) {
   $base = Math::BigInt->new($base);
   my $result = 1;
   while ($exponent > 0) {
      $result = ($result * $base) % $modulus if $exponent % 2;
      $exponent /= 2;
      $base = ($base * $base) % $modulus;
   }
   return $result;
}

BEGIN {
   *__modexp = eval {
      require Math::Prime::Util;
      sub { Math::BigInt->new(Math::Prime::Util::powmod(@_)) };
   } // \&__local_modexp;
}

sub __h2o ($hex) { pack 'H*', (length($hex) % 2 ? '0' : '') . $hex }
sub __o2h ($octets) { unpack('H*', $octets) =~ s{\A 0+}{}rmxs }

sub __main (@args) {
   my ($g, $p) = @args ? @args : (NIST_g, NIST_p);
   my $dh = DiffieHellman->new(g => $g, p => $p);

   my ($a_secret, $a_public) = $dh->generate_key_pair;
   my ($b_secret, $b_public) = $dh->generate_key_pair;

   my ($enc_a, $auth_a) = $dh->joint_symmetric_keys($a_secret, $b_public);
   my ($enc_b, $auth_b) = $dh->joint_symmetric_keys($b_secret, $a_public);

   say __o2h($enc_a), "\n", unpack 'H*', $enc_b;
   say "\n";
   say __o2h($auth_a), "\n", unpack 'H*', $auth_b;

   exit 0;
}

__main(@main::ARGV) unless caller;

1;

Batteries are included, especially an implementation of exponentiation modulo a number that is capable of working with Math::BigInt. This is available as __local_modexp and it’s slow.

So, we happen to have Math::Prime::Util around, we can easily wrap its powmod function to return a Math::BigInt object back (instead of a string) and enjoy a much faster execution!

The module is written as a modulino, so it doubles down as a program that can be called directly to do some tests.

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient