TL;DR

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!

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