#!/usr/bin/perl -w
########################################
# Exploring the Web of Trust with GnuPG
# by Ralf Hüls <R.Huels@ping.de>
#
# This program recursively searches the web of signators for a given key in
# your GnuPG keyring. It produces a list of signators and signators'
# signators by levels of remoteness. It creates Unix style shell scripts
# that retrieve missing keys from keyservers (I don't use automatic key
# retrieval). It also produces graph data output that can be used with
# Graphviz from AT&T and Lucent Bell Labs.
#
# Usage: graph <key> <depth>
#
#        <key> is a key-ID (e.g. 4931A04F)
#        <depth> is a number.
#
# Output:
# levels.txt     - List of signators
# graph.dot      - Input for "dot" in the Graphviz package 
# getkeys-<n>.sh - Retrieve missing keys for level <n> 
#
# Needs:
# GnuPG 1.0.4 (http://www.gnupg.org/)
# Perl 5      (http://www.perl.com/)
#
# For graph visualization, use:
# Graphviz    (http://www.research.att.com/sw/tools/graphviz/)
#
# 
# (c) 17-11-2000 by Ralf Hüls <R.Huels@ping.de> 
#     03-03-2002 Minor bugfix for Perl 5.6
#
# This program is a dirty hack, use it at your own risk ;-)
# Non-commercial use and distribution of this program is permitted.
# If you modify this program to create something useful or
# interesting, I'd like to hear about it.
#
# Ralf Hüls <R.Huels@ping.de> 
# http://www.teleute.ping.de/
# DSA key: E131C5A4 
# RSA key: 4931A04F 
# 
########################################
# Change this to your favorite Keyserver
my $keyserver="wwwkeys.de.pgp.net";
#my $keyserver=certserver.pgp.com;
########################################

use strict;

my $top;
my $depth;
my @known;
my @unknown;
my $key;
my %data;
my %graph;
my %mail;
my %level;
my $i;
my $a;
my $b;
my $edge;
my $nodeformat;

my @color=qw{green red blue magenta black gray};

die "\nUsage: graph <key> <depth>\n\n<key> is a key-ID (e.g. 4931A04F)\n<depth> is a number.\n"
unless (scalar(@ARGV)==2);


$top=$ARGV[0];
$depth=$ARGV[1];
$level{$top}=0;

$nodeformat='[shape=box,';

print "0 $top\n";
$known[0]{$top}++;

getkeys($top,1);


open G,">graph.dot";
print G "digraph G {\n";

foreach (keys %graph)
  {
    $a=substr($_,0,8);
    $b=substr($_,8,8);
    $edge=$level{$a};
    if ($level{$b} > $level{$a}) {$edge=$level{$b}};
    if ($graph{$_} == 1)
      {
	print G "\"$a\" -> \"$b\" [color=$color[$edge]];\n";
	print G "\"$a\" $nodeformat color=$color[$level{$a}]];\n";
	print G "\"$b\" $nodeformat color=$color[$level{$b}]];\n";
      }

    if ($graph{$_} == 2)
      {
	print G "\"$a\" -> \"$b\" [dir=\"both\" color=$color[$edge]];\n";

	print G "\"$a\" $nodeformat color=$color[$level{$a}]];\n";
	print G "\"$b\" $nodeformat color=$color[$level{$b}]];\n";
      }

  }

print G "}\n";
close G;


open G ,">levels.txt" or die "$!\n";;
for ($i=0;$i<=$depth;$i++)
  {
    foreach $key (keys %{$known[$i]})
      {
	if (defined($known[$i]{$key}))
	  {
	    print G "$i $key $data{$key}"; 
	  }
      }    
    foreach $key (keys %{$unknown[$i]})
      {
	if (defined($unknown[$i]{$key}))
	  {
	    print G "$i $key ???\n"; 
	  }
      }    
    print G "\n";

    open F,">getkeys-$i.sh" or die "$!\n";;
    print F "#!/bin/sh\n";
    foreach $key (keys %{$unknown[$i]})
      {
	if (defined($unknown[$i]{$key}))
	  {
	    print F "gpg --allow-non-selfsigned-uid --keyserver $keyserver --recv-keys $key\n";
	  }
      }
    
    close F;
  }
close G;

##########################################

sub getkeys{

  my $sig;
  my $d=0;
  my @output;
  
  
  $d=$_[1];
  
  open(S,"gpg --check-sigs $_[0]|") or die "$!"; 
  @output=<S>;
  close S;


  foreach (@output)
    {
      if (/^sig\!/)
	{      
	  $sig=substr($_,11,8);
	  $data{$sig}=substr($_,32);

	  unless ( ($sig eq $_[0]) || ($graph{"$sig$_[0]"}))
	    {
	      $graph{"$sig$_[0]"}=1;
	      if ($graph{"$_[0]$sig"})
		{
		  $graph{"$sig$_[0]"}=2;
		  $graph{"$_[0]$sig"}=3;
		}
	    }
	  unless (defined($level{$sig}) && $level{$sig}<=$d)
	    {
	      if (defined($level{$sig}))
		  {
		    undef  ($known[$level{$sig}]{$sig});
		  }
	      $level{$sig}=$d;
	      $known[$d]{$sig}++;
	      if ($d<$depth)
		{
		  getkeys($sig,$d+1);
		}
	    }
	}
      if (/^sig\?/)
	{      
	  $sig=substr($_,11,8);
	  $data{$sig}=substr($_,32);
	  unless ($graph{"$sig$_[0]"})
	    {
	      $graph{"$sig$_[0]"}=1;
	      if ($graph{"$_[0]$sig"})
		{
		  $graph{"$sig$_[0]"}=2;
		  $graph{"$_[0]$sig"}=3;
		}
	    }
	  unless (defined($level{$sig}) && $level{$sig}<=$d)
	    {
	      if (defined($level{$sig}) )
		  {
		    undef  ($known[$level{$sig}]{$sig});
		  }
	      $level{$sig}=$d;
	      $unknown[$d]{$sig}++;
	    }
	}
    }
  
}