From ae9a949163f6850c7ef6a260d6d7b086a622d787 Mon Sep 17 00:00:00 2001
From: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
Date: Sun, 11 Jan 2009 23:01:10 -0500
Subject: [PATCH] pem2openpgp: implemented extended euclidean algorithm to find
 modular multiplicative inverse.  this lets us compute the value we need for
 secret key material.

---
 src/keytrans/pem2openpgp | 49 ++++++++++++++++++++++++++++++++++++----
 1 file changed, 45 insertions(+), 4 deletions(-)

diff --git a/src/keytrans/pem2openpgp b/src/keytrans/pem2openpgp
index fa92297..c74ca25 100755
--- a/src/keytrans/pem2openpgp
+++ b/src/keytrans/pem2openpgp
@@ -21,6 +21,7 @@ use strict;
 use warnings;
 use Crypt::OpenSSL::RSA;
 use Crypt::OpenSSL::Bignum;
+use Crypt::OpenSSL::Bignum::CTX;
 use Digest::SHA1;
 use MIME::Base64;
 
@@ -213,7 +214,7 @@ sub mpi_pack {
 sub simple_checksum {
   my $bytes = shift;
 
-  return unpack("%C*",$bytes) % 65536;
+  return unpack("%32W*",$bytes) % 65536;
 }
 
 # FIXME: genericize these to accept either RSA or DSA keys:
@@ -229,6 +230,46 @@ sub make_rsa_pub_key_body {
 	mpi_pack($n).
 	  mpi_pack($e);
 }
+
+# calculate the multiplicative inverse of a mod b this is euclid's
+# extended algorithm.  For more information see:
+# http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm the
+# arguments here should be Crypt::OpenSSL::Bignum objects.  $a should
+# be the larger of the two values, and the two values should be
+# coprime.
+
+sub modular_multi_inverse {
+  my $a = shift;
+  my $b = shift;
+
+  my $ctx = Crypt::OpenSSL::Bignum::CTX->new();
+  my $x = Crypt::OpenSSL::Bignum->zero();
+  my $y = Crypt::OpenSSL::Bignum->one();
+  my $lastx = Crypt::OpenSSL::Bignum->one();
+  my $lasty = Crypt::OpenSSL::Bignum->zero();
+
+  while (! $b->is_zero()) {
+    my ($quotient, $remainder) = $a->div($b, $ctx);
+
+    $a = $b;
+    $b = $remainder;
+
+    my $temp = $x;
+    $x = $lastx->sub($quotient->mul($x, $ctx));
+    $lastx = $temp;
+
+    $temp = $y;
+    $y = $lasty->sub($quotient->mul($y, $ctx));
+    $lasty = $temp;
+  }
+
+  if (!$a->is_one()) {
+    die "did this math wrong.\n";
+  }
+
+  return $lastx;
+}
+
 sub make_rsa_sec_key_body {
   my $key = shift;
   my $timestamp = shift;
@@ -239,7 +280,7 @@ sub make_rsa_sec_key_body {
   my $secret_material = mpi_pack($d).
     mpi_pack($p).
       mpi_pack($q).
-	mpi_pack($c);
+	mpi_pack(modular_multi_inverse($p, $q));
 
   # FIXME: according to Crypt::OpenSSL::RSA, $c is 1/q mod p; but
   # according to sec 5.5.3 of RFC 4880, this last argument should
@@ -254,7 +295,7 @@ sub make_rsa_sec_key_body {
 	  mpi_pack($e).
 	    pack('C', 0). # seckey material is not encrypted -- see RFC 4880 sec 5.5.3
 	      $secret_material.
-		simple_checksum($secret_material);
+		pack('n', simple_checksum($secret_material));
 }
 
 # expects an RSA key (public or private) and a timestamp
@@ -406,7 +447,7 @@ my $sig_body =
   mpi_pack($sig);
 
 print
-  make_packet($packet_types->{pubkey}, $pubkey).
+  make_packet($packet_types->{seckey}, $seckey).
   make_packet($packet_types->{uid}, $uid).
   make_packet($packet_types->{sig}, $sig_body);
 
-- 
2.25.1