#!/usr/bin/perl

################################################
### vss.pl                                   ###
###                                          ###
### a Perl-Fu script to implement a visual   ###
### secret sharing scheme using a (n,n)      ###
### threshold.                               ###
###                                          ###
### (c) 2002 Alexander Klink, gimp@alech.de  ###
### released under the GPL v2                ###
###                                          ###
### requires the Math::MatrixBool module     ###
###                                          ###
################################################

use Gimp qw(:auto ___ N_);
use Gimp::Fu;
use Bit::Vector;
use Math::MatrixBool;

register "gimp_fu_vss",
  'Visual Secret Sharing',
  'Shares a secret between n parties, where n people can recover the secret',
  'Alexander Klink <gimp@alech.de>',
  '(c) 2002 Alexander Klink',
  "20020409",
  N_"<Toolbox>/Xtns/Perl/Visual Secret Sharing (n,n)...",
  "INDEXED",
  [
   # argument type, switch name   , a short description           , default value, extra arguments
   [PF_IMAGE  , "source"      , "Image to be shared" ],
   [PF_INT    , "n", "Number of users needed to recover the secret", 3],
  ],

  sub {
    my ($src, $k) = @_; # this is the image we get the data from
#    Gimp::set_trace(TRACE_CALL); # enable debugging information
    my $draw = gimp_image_active_drawable($src); # we take the data from the active drawable
    $width = $draw->width();
    $height = $draw->height();

    srand(); # initalize the random number generator
	     # should use a cryptographically secure random
	     # number generator one day.

    $date = `date`;
    print STDERR "Start: $date";
    $M = drawable_to_matrix($draw); # convert the image data to a boolean matrix
    $date = `date`;
    print STDERR "Converted to matrix: $date";
    @stuff = share_matrix($M, $height, $width, $k); # do the work, create k matrices
    $date = `date`;
    print STDERR "Shared matrix: $date";
    $target = matrices_to_image($stuff); # convert back to a (layered) image
    $date = `date`;
    print STDERR "End: $date";

    $target;
  };

exit main;

=pod

=head1 NAME

vss.pl - Visual Secret Sharing scheme using a (n,n) threshold

=head1 HELP

This Gimp::Fu script lets you share a black-and-white image into n parts
where k different parties can recover the secret

Assume you distribute the shares to n people, they can only
reveal the secret information if k people put their pictures
(most probably printed on transparencies) on top of each other.

No information whatsoever about the secret is contained in one
of the shares.

Reference: "Visual Cryptography" by Moni Naor and Adi Shamir.

=head1 AUTHOR

(c) 2002, 2003 Alexander Klink <gimp@alech.de>.

Released under the terms of the GNU Public License v2.

=cut

sub weight { # calculates the weight of a vector
	my $vector = shift(@_);
	my $n = $vector->Size();
	my $w = 0;

	for (my $i = 0; $i < $n; $i++) {
		$w = $w + $vector->rotate_left();
	}
	return $w;
}

sub generate_S0_S1 {   # generates starting matrices for a (k, k)-threshold visual secret sharing scheme
	my $k = shift(@_);
	my $S0 = new Math::MatrixBool($k, 2**($k-1)); # generate a 2 * 2^(k-1) matrix containing an even number of 1's in the columns
	my $S1 = new Math::MatrixBool($k, 2**($k-1)); # generate a 2 * 2^(k-1) matrix containing an odd number of 1's in the columns

	my $col_s0 = 0; # the number of columns in S0 that are already filled
	my $col_s1 = 0; # the number of columns in S1 that are already filled

	my $vector = Bit::Vector->new_Dec($k, 0); # create the k-bit 0-vector

	for (my $i = 0; $i <= 2**$k; $i++) {
		if (weight($vector) % 2 == 0) { # the vector has an even number of 1's
			insert_column($S0, $vector, $col_s0); # thus put it into the S0-matrix
			$col_s0++;
		}
		else { # the vector has an odd number of 1's
			insert_column($S1, $vector, $col_s1); # thus put it into the S1-matrix
			$col_s1++;
		}
		$vector->increment();
	}
	return ($S0, $S1);
}

sub insert_column { # insert the vector $vec as the $j-th column of the matrix $M
	my $M = shift(@_);
	my $vec = shift(@_);
	my $j = shift(@_);

	$k = $vec->Size();
	for (my $i = 0; $i < $k; $i++) {
		if ($vec->bit_test($k-$i-1) == 1) {
			$M->Bit_On($i+1, $j+1);
		}
	}
}

sub random_permutation { # Skiena 1990, see http://mathworld.wolfram.com/RandomPermutation.html
	my $n = shift(@_);
	
	for (my $i = 0; $i < $n; $i++) { # initialize with (1, 2, ... , n)
		$perm[$i] = $i+1;
	}

	for (my $i = 0; $i < $n; $i++) { # exchange the i-th entry with a random entry within the first i elements
		$rand = rand($i);
		$tmp = $perm[$rand];
		$perm[$rand] = $perm[$i];
		$perm[$i] = $tmp;
	}

	return @perm;
}

sub random_permutation_matrix { # generate a random permutation matrix
	my $n = shift(@_);

	@perm = random_permutation($n);

	my $M = new Math::MatrixBool($n, $n); # a n x n matrix

	for (my $i = 0; $i < $n; $i++) {
		$M->Bit_On($i+1, $perm[$i]); # set the entry according to the permutation
	}

	return $M;
}

sub generate_random_elem_from_C0_C1 { # generate a random permutation of columns in a starting matrix
				      # and thus random elements from C0 and C1
	my $k = shift(@_);

	my ($T0, $T1) = generate_S0_S1($k); # generate the starting matrices

	my $P = random_permutation_matrix(2**($k-1)); # generate two 2^(k-1) permutation matrices
	my $Q = random_permutation_matrix(2**($k-1));

	my $S0 = $T0 * $P; # permute the matrices
	my $S1 = $T1 * $Q;

	return ($S0, $S1);
}

sub drawable_to_matrix { # convert a GIMP drawable to a binary matrix
	my $draw = shift(@_);

	my $width = $draw->width();
	my $height = $draw->height();

	my $M = new Math::MatrixBool($height, $width);

	for (my $y = 0; $y < $height; $y++) {
		for (my $x = 0; $x < $width; $x++) {
			my @pixel = $draw->get_pixel($x, $y);
			if ($pixel[0] == 1) { # this is a black pixel
				$M->Bit_On($y+1, $x+1);
			}
		}
	}

	return $M;
}

sub share_matrix { # share a matrix containing image data among k
		   # users, return k matrices of the appropriate size
	my ($A, $h, $w, $k) = @_;

	my ($C0, $C1) = generate_random_elem_from_C0_C1($k);

	my $r = 2**(int(($k-1)/2));       # the scaling factors for the
	my $s = 2**(int($k/2));   	  # the matrices.

	for (my $i = 0; $i < $k; $i++) {
		$B[$i] = new Math::MatrixBool($h*$r, $w*$s); # a hr x ws matrix
	}

	for (my $y = 1; $y <= $h; $y++) {
		for (my $x = 1; $x <= $w; $x++) {
			$P = random_permutation_matrix(2**($k-1));
			$Q = random_permutation_matrix(2**($k-1));
			$C0 = $C0 * $P; # permute
			$C1 = $C1 * $Q; # C0 and C1
			if ($A->bit_test($y, $x)) {
				for (my $i = 0; $i < $k; $i++) {
					set_share($i, $B[$i], $x, $y, $r, $s, $C1); # serve a black pixel share
				}
			}
			else {
				for (my $i = 0; $i < $k; $i++) {
					set_share($i, $B[$i], $x, $y, $r, $s, $C0); # serve a white pixel share
				}
			}
		}
	}

	return $B;
}

sub set_share { # set a s x r part of the given matrix starting at (x, y) with the contents of the i-th row of $C
	my ($i, $M, $x, $y, $s, $r, $C) = @_;

	($w, $h) = $M->Dim();

	my $kstart = ($x-1) * $r + 1;
	my $lstart = ($y-1) * $s + 1;
	my $row = $i+1;

	for (my $l = $lstart; $l < $lstart + $s; $l++) {
		for (my $k = $kstart; $k < $kstart + $r; $k++) {
			my $column = ($k-$kstart) + ($l-$lstart)*$s + 1;
			if ($C->bit_test($row, $column)) {
				$M->Bit_On($l, $k);
			}
		}
	}
}

sub matrices_to_image { # convert k binary matrices to an image with k transparent layers
	my $B = @_;
	my $k = $#B + 1;
	my ($height, $width) = $B[0]->Dim();

        my $target = new Image($width, $height, RGB);
        $blackpixel[0] = 0;
        $blackpixel[1] = 0;
        $blackpixel[2] = 0;
        $blackpixel[3] = 255;
	
	for (my $i=0; $i < $k; $i++) { # create k layers and fill them with the data from the matrices
		$idisplay = $i+1;
		gimp_progress_init("Processing share $idisplay/$k...", -1);
		$layer[$i] = $target->layer_new($width, $height, RGBA_IMAGE, "Share $idisplay", 100, NORMAL_MODE);
		$layer[$i]->add_layer(-1);
		$target->set_active_layer($layer[$i]);
		$drawable[$i] = gimp_image_active_drawable($target);
		gimp_edit_clear($drawable[$i]);
		for (my $y = 0; $y < $height; $y++) {
			if ($y % 10 == 0) {
				gimp_progress_update($y/$height);
			}
			for (my $x = 0; $x < $width; $x++) {
				if ($B[$i]->bit_test($y+1, $x+1)) {
					$drawable[$i]->set_pixel($x, $y, \@blackpixel);
				}
			}
		}
	}
	return $target;
}