Cryptopals 33 - Implement Diffie-Hellman


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

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;

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


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!

Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!