Cryptopals 39 - Implement RSA

TL;DR

Challenge 39 in Cryptopals.

Well, yeah. Implement RSA.

Been there, done that. And Perl is huge.

Anyway, there are a couple of sub-challenges that were not addressed in the post from last year.

The first is the implementation of the $e^{-1} = \text{invmod}(e, T)$ function, with the assumption that $e$ and $T$ are coprimes, i.e. $\text{GCD}(e, T) = 1$.

By Bézout’s theorem, there always exist $x$ and $y$ such that:

\[x \cdot e + y \cdot T = \text{GCD}(e, T) = 1\]

Moving on:

\[x \cdot e \cong 1 - y \cdot T \cong 1 \pmod T \\ x \cdot e \cong 1 \pmod T\]

That is $x$ is the inverse of $e$ modulo $T$.

How does this help? Well, it’s easy to find $x$, using The Extended Euclid’s Algorithm. Well, yeah, worth repeating the code here, together with invmod:

sub egcd {    # https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
   my ($X, $x, $Y, $y, $A, $B, $q) = (1, 0, 0, 1, @_);
   while ($A) {
      ($A, $B, $q) = ($B % $A, $A, int($B / $A));
      ($x, $X, $y, $Y) = ($X, $x - $q * $X, $Y, $y - $q * $Y);
   }
   return ($B, $x, $y);
} ## end sub egcd

sub invmod {
   require Math::BigInt;
   my ($A, $B) = map { Math::BigInt->new($_) } @_;
   my ($gcd, $imod) = egcd($A, $B);
   die "not coprimes!\n" unless $gcd == 1;
   return $imod % $B;
}

The other sub-challenge is about finding very big prime numbers, even using some library. What can be better than Math::Prime::Util?

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

use File::Basename 'dirname';
use lib dirname(__FILE__), dirname(__FILE__) . '/local/lib/perl5';
use Math::Prime::Util 'random_maurer_prime';

my $n_bits = shift // 2048;

my $p = random_maurer_prime($n_bits);
my $q = random_maurer_prime($n_bits);

say for $p, $q;

There’s one last little challenge that requires $e = 3$, which also means that one out of two primes given back by random_maurer_prime will have to be discarded (because if it’s congruent 1 modulo $e$, then $e$ will divide the totient value $(p - 1)(q - 1)$).

sub prime_2_mod_3 ($n_bits) {
   while ('necessary') {
      my $p = random_maurer_prime($n_bits);
      return $p if 2 == $p % 3;
   }
}

So well, from a performance perspective, this is not the best choice!

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient