Re: str 2 int
| From: | Greg Billock | Date: | Fri, 18 Aug 2000 06:28:02 +0000 |
| Subject: | Re: str 2 int | ||
| References: | 1 | Groups: | php.general |
| Request: | Send a blank email to php-general+get-12417@lists.php.net to get a copy of this message | ||
I was looking into some crypto stuff for a current project, and while I
know that using mcrypt is the way to go for anything serious, I thought
I'd try my hand at a PHP version of Bruce Schneier's Solitaire algorithm.
(Reading _Cryptonomicon_ recently probably contributed to the insanity.)
I suppose this could be useful for sites which absolutely cannot/will not
link in mcrypt....
Anyway, I was dismayed to find that it ran some 100 times slower than
the reference perl source. Any ideas why? I tweaked on it and switched
to mostly string functions instead of regexps, but it is still some 12 times
slower. Ideas?
-Greg
For your testing pleasure......
PHP source:
<?php
// Solitaire cryptosystem: verbose version
// Ian Goldberg <ian@cypherpunks.ca>, 19980817
// adapted to PHP 2000 Greg Billock
// benchmark: encrypting and decrypting a 1k block using a fairly long
// key (over 60 characters) takes 24.875 seconds on a P/120 doing
nothing else
// meaning about 12.5 seconds/K on a P/120 - Redhat - PHP3.0.12
// not your fastest algorithm...
// the original perl algorithm takes about 1.05 seconds/K on the same
// machine.
//takes plaintext and key, produces encrypted output or decrypted output
function solcrypt($input, $key,$decrypt="") {
if ($decrypt) {
print "decrypting...";
$f = -1;
} else {
$f = 1;
}
//translate key and input to all uppercase
$key = strtoupper($key);
$key = ereg_replace("[^A-Z]","",$key);
$input = strtoupper($input);
$input = ereg_replace("[^A-Z]","",$input);
//pad $input to multiple of 5?
//while (strlen($input)%5 != 0) {
// $input .= "X";
//}
//print "with $input<P>\n";
//print "new key $key<P>\n";
$deck = makedeck();
//print $deck;
//for each letter in the key, run the setup routine
for ($i=0; $i<strlen($key); $i++) {
sce($deck,$key[$i]);
}
//print "<P>Scrambled deck: $deck<P>\n";
//now do encryption...
$output = "";
for ($i=0; $i<strlen($input); $i++) {
$cryptletter = sce($deck); //get the encryption letter to combine
with plaintext
//print "$cryptletter-";
$t = ord($input[$i])-13; //take the value of current char - 13
//print "($t)";
//print ($f * $cryptletter)."*";
$t += $f * $cryptletter; // add encryption
//print "($t)";
$t = ($t % 26) + 65; //mod 26 + 65 to turn back into letter
//print "($t)";
//print "=".chr($t)."=";
$output .= chr($t);
}
//unpad Xs from output?
//if ($decrypt) {
// $output = ereg_replace("(.*)(X*$)","\\1",$output);
//}
return $output;
}
function makedeck() {
$deck = "";
for ($i=33; $i<=86; $i++) {
$deck .= chr($i);
}
return $deck;
}
//generate the next value in the keystream. Operates on the passed
//deck
//this could be optimized with strchr calls to work faster...
function sce(&$deck,$k="") {
$decklen = strlen($deck);
//print "<P>Scrambling deck $deck with $k<BR>\n";
//original regexp code commented out......
//if joker A is at bottom, bring to top
//$deck = ereg_replace("(.*)U$","U\\1",$deck);
if ($deck[$decklen-1]=="U") {
$deck = "U".substr($deck,0,$decklen-1);
}
//swap joker A with card below it
//$deck = ereg_replace("U(.)","\\1U",$deck);
$lu = strpos($deck,"U");
$deck = substr($deck,0,$lu) . $deck[$lu+1] . "U" .
substr($deck,$lu+2);
//same with joker B, twice
//$deck = ereg_replace("(.*)V$","V\\1",$deck);
//$deck = ereg_replace("V(.)","\\1V",$deck);
//$deck = ereg_replace("(.*)V$","V\\1",$deck);
//$deck = ereg_replace("V(.)","\\1V",$deck);
if ($deck[$decklen-1]=="V") {
$deck = "V".substr($deck,0,$decklen-1);
}
$lv = strpos($deck,"V");
$deck = substr($deck,0,$lv) . $deck[$lv+1] . "V" .
substr($deck,$lv+2);
if ($deck[$decklen-1]=="V") {
$deck = "V".substr($deck,0,$decklen-1);
}
$lv = strpos($deck,"V");
$deck = substr($deck,0,$lv) . $deck[$lv+1] . "V" .
substr($deck,$lv+2);
//print "Joker swap: $deck<BR>\n";
//swap deck slices before and after jokers
//$deck = ereg_replace("(.*)([UV].*[UV])(.*)","\\3\\2\\1",$deck);
$lv = strpos($deck,"V");
$lu = strpos($deck,"U");
$f = min($lv,$lu);
$l = max($lv,$lu);
$deck = substr($deck,$l+1) . substr($deck,$f,$l-$f+1) .
substr($deck,0,$f);
//print "triple cut: $deck<BR>\n";
//count cut:
$v = deckvalue($deck,53);
//print "cutting with $v<BR>\n";
$deck = ereg_replace("(.{$v})(.*)(.)","\\2\\1\\3",$deck);
//$deck = substr($deck,$v,$decklen-1-$v+1) . substr($deck,0,$v) .
$deck[$decklen-1];
//print "Count cut: $deck<BR>\n";
//if doing key setup, do another count cut and return
if ($k) {
$v = ord($k)-64;
$deck = ereg_replace("(.{$v})(.*)(.)","\\2\\1\\3",$deck);
//print "Key cut: $deck<BR>\n";
return;
}
//if no key setup, go on
$c = deckvalue($deck, deckvalue($deck, 0));
if ($c<=52) {
return $c;
} else {
return sce($deck);
}
}
//returns the value of the $index'th card in the deck
//( the v() function)
function deckvalue($deck,$index) {
$value = ord($deck[$index])-32;
if ($value==54) {
$value = 53;
}
return $value;
}
?>
============================
Perl source: (note that this is a bit different than the original; my perl
didn't
like the -d CMD args -> $d assumption)
#!/usr/bin/perl -s
## Solitaire cryptosystem: verbose version
## Ian Goldberg <ian@cypherpunks.ca>, 19980817
## Make sure we have at least the key phrase argument
die "Usage: $0 [-d] 'key phrase' [infile ...]\n" unless $#ARGV >= 0;
## Set the multiplication factor to -1 if "-d" was specified as an
option
## (decrypt), or to 1 if not. This factor will be multiplied by the
output
## of the keystream generator and added to the input (this has the
effect
## of doing addition for encryption, and subtraction for decryption).
$d = shift;
if ($d eq '-d') {
$f = -1;
$p = shift;
} else {
$f = 1;
$p = $d;
}
#original: doesn't work
#$f = $d ? -1 : 1;
## Load the key phrase, and turn it all into uppercase
#$p = shift;
$p =~ y/a-z/A-Z/;
## Set up the deck in sorted order. chr(33) == '!' represents A of
clubs,
## chr(34) == '"' represents 2 of clubs, and so on in order until
## chr(84) == 'T' represents K of spades. chr(85) == 'U' is joker A and
## chr(86) == 'V' is joker B.
$D = pack('C*',33..86);
## For each letter in the key phrase, run the key setup routine (which
## is the same as the keystream routine, except that $k is set to the
## value of each successive letter in the key phrase).
$p =~ s/[A-Z]/$k=ord($&)-64,&e/eg;
#print "Scrambled deck $D\n";
## Stop setting up the key and switch to encrypting/decrypting mode.
$k = 0;
## Collect all of the alphabetic characters (in uppercase) from the
input
## files (or stdin if none specified) into the variable $o
while(<>) {
## Change all lowercase to uppercase
y/a-z/A-Z/;
## Remove any non-letters
y/A-Z//dc;
## Append the input to $o
$o .= $_;
}
## If we're encrypting, append X to the input until it's a multiple of 5
chars
if (!$d) {
$o.='X' while length($o)%5;
}
## This next line does the crypto:
## For each character in the input ($&), which is between 'A' and
'Z',
## find its ASCII value (ord($&)), which is in the range 65..90,
## subtract 13 (ord($&)-13), to get the range 52..77,
## add (or subtract if decrypting) the next keystream byte (the output
of
## the function &e) and take the result mod 26
((ord($&)-13+$f*&e)%26),
## to get the range 0..25,
## add 65 to get back the range 65..90, and determine the character
with
## that ASCII value (chr((ord($&)-13+$f*&e)%26+65)), which is
between
## 'A' and 'Z'. Replace the original character with this new one.
$o =~ s/./chr((ord($&)-13+$f*&e)%26+65)/eg;
## If we're decrypting, remove trailing X's from the newly found
plaintext
$o =~ s/X*$// if $d;
## Put a space after each group of 5 characters and print the result
$o =~ s/.{5}/$& /g;
print "$o\n";
## The main program ends here. The following are subroutines.
## The following subroutine gives the value of the nth card in the deck.
## n is passed in as an argument to this routine ($_[0]). The A of
clubs
## has value 1, ..., the K of spades has value 52, both jokers have
value 53.
## The top card is the 0th card, the bottom card is the 53rd card.
sub v {
## The value of most cards is just the ASCII value minus 32.
## substr($D,$_[0]) is a string beginning with the nth card in the
deck
$v=ord(substr($D,$_[0]))-32;
## Special case: both jokers (53 and 54, normally) have value 53,
## so return 53 if the value is greater than 53, and the value
otherwise.
$v>53?53:$v;
}
## The following subroutine generates the next value in the keystream.
sub e {
# print "\nScrambling deck $D with $k\n";
## If the U (joker A) is at the bottom of the deck, move it to the
top
$D =~ s/(.*)U$/U$1/;
## Swap the U (joker A) with the card below it
$D =~ s/U(.)/$1U/;
## Do the same as above, but with the V (joker B), and do it twice.
$D =~ s/(.*)V$/V$1/; $D =~ s/V(.)/$1V/;
$D =~ s/(.*)V$/V$1/; $D =~ s/V(.)/$1V/;
#print "joker swap: $D\n";
## Do the triple cut: swap the pieces before the first joker, and
## after the second joker.
$D =~ s/(.*)([UV].*[UV])(.*)/$3$2$1/;
#print "triple cut: $D\n";
## Do the count cut: find the value of the bottom card in the deck
$c=&v(53);
#print "cutting with $c\n";
## Switch that many cards from the top of the deck with all but
## the last card.
$D =~ s/(.{$c})(.*)(.)/$2$1$3/;
#print "count cut: $D\n";
## If we're doing key setup, do another count cut here, with the
## count value being the letter value of the key character (A=1,
B=2,
## etc.; this value will already have been stored in $k). After the
## second count cut, return, so that we don't happen to do the loop
## at the bottom.
if ($k) {
$D =~ s/(.{$k})(.*)(.)/$2$1$3/;
#print "key cut: $D\n";
return;
}
## Find the value of the nth card in the deck, where n is the value
## of the top card (be careful about off-by-one errors here)
$c=&v(&v(0));
## If this wasn't a joker, return its value. If it was a joker,
## just start again at the top of this subroutine.
$c>52?&e:$c;
return $c;
}