I spent quite a while trying to get encryption working between PHP and Perl. Here is my final solution using blowfish.

$cipher = 'blowfish';
$input = "This is a super secret message, don't let anyone read it";

$key = get_rand(56);
$iv = get_rand(8);

$cry = mcrypt_encrypt($cipher, $key, $input, MCRYPT_MODE_CBC,$iv);

print "<pre>Cipher: <b>" . strtoupper($cipher) . "</b> with a keysize of <b>$key_size</b>\n";
print "Key: $key\n";
print "IV: $iv\n";
print "Plaintext: $input\n";
print "Base64 encode: " . base64_encode($cry) . "\n";

$dec = mcrypt_decrypt($cipher, $key, $cry, MCRYPT_MODE_CBC,$iv);
$dec = rtrim($dec,chr(0)); # Remove the padding PHP adds

print "Decrypted: $dec</pre><br /><br />";

function get_rand($size) {
    #srand(73);
    for ($i=0;$i<$size;$i++) { $ret .= chr(rand(64,126)); }

    return $ret;
}

Output:

Cipher: <b>BLOWFISH</b> with a keysize of
Key: HHctIET_ohhQoNT_kmanlgN~jXLJHQUQYxGc~[CoDlAszVTgDvWp^epJ
IV: HHctIET_
Plaintext: This is a super secret message, don't let anyone read it
Base64 encode: qGrrbvkXl3ngDChiNeIVQDuniRQh5wbKZCh/oWmBwNzSw8bENwEdVBBrYcIBkBoLOQNtJacyslk=
Decrypted: This is a super secret message, don't let anyone read it</b>

use Crypt::CBC;
use MIME::Base64;

$key = 'HHctIET_ohhQoNT_kmanlgN~jXLJHQUQYxGc~[CoDlAszVTgDvWp^epJ';
$iv = 'HHctIET_';
$cipt = 'qGrrbvkXl3ngDChiNeIVQDuniRQh5wbKZCh/oWmBwNzSw8bENwEdVBBrYcIBkBoLOQNtJacyslk=';

$cipher = Crypt::CBC->new(
   -key => $key,
   -cipher => 'Blowfish',
   -iv => $iv,
   -header => 'none',
   -padding => 'null',
   -literal_key => true,
   -keysize => length($key),
);

$clt = $cipher->decrypt(decode_base64($cipt));

print "Key: $key\n";
print "IV: $iv\n";
print "Base64: $cipt\n";
print "Decrypted: $clt\n";

Output:

Key: HHctIET_ohhQoNT_kmanlgN~jXLJHQUQYxGc~[CoDlAszVTgDvWp^epJ
IV: HHctIET_
Base64: qGrrbvkXl3ngDChiNeIVQDuniRQh5wbKZCh/oWmBwNzSw8bENwEdVBBrYcIBkBoLOQNtJacyslk=
Decrypted: This is a super secret message, don't let anyone read it