borisz,
This was the approach I was working on when I saw your post. Can you tell me what I am doing wrong?

#!/usr/bin/perl
use strict;
use warnings;
use Digest::MD5;
use Math::BaseCalc;

my $md5_b64 = Digest::MD5->new;
$md5_b64->add( 'foo bar' );

my $md5_hex = Digest::MD5->new;
$md5_hex->add( 'foo bar' );

my $b64_digest   = $md5_b64->b64digest;
my $hex_digest   = $md5_hex->hexdigest;

my $base_64 = new Math::BaseCalc (
    digits => [ 'A' .. 'Z', 'a' .. 'z', 0 .. 9, '+' , '/' ]
);
my $base_16 = new Math::BaseCalc (
    digits => [ 0 .. 9, 'a' .. 'f' ]
);

my $b64_string   = $base_16->to_base( $base_64->from_base( $b64_digest
+ ) );

print "Base 64   : $b64_digest\n";
print "Hex       : $hex_digest\n\n";
__END__
Base 64   : MntvB0NYESObxH4VRDUycw
Hex       : 327b6f07435811239bc47e1544353273

Converted : 327b6f074358120000000000000000000
[download]

It doesn't seem to work correctly? L~R

Update: After talking with tye in the CB, he seems to think that Math::BaseCalc expects the number being converted to fit into a double as well as an endian problem. He suggested using Math::Fleximal instead and I stumbled on to converting from b64 -> b16 to correct for the endian problem encountered going the other way.

#!/usr/bin/perl
use strict;
use warnings;
use Digest::MD5;
use Math::Fleximal;

my $md5_b64 = Digest::MD5->new;
$md5_b64->add( 'foo bar' );

my $md5_hex = Digest::MD5->new;
$md5_hex->add( 'foo bar' );

my $b64_digest = $md5_b64->b64digest;
my $hex_digest = $md5_hex->hexdigest;

my $b16_string = Math::Fleximal->new (
    $b64_digest , [ 'A'..'Z', 'a'..'z', '0'..'9', '+', '/']
    )->change_flex ( [ 0..9, 'a'..'f' ] )->to_str()
;

print "Base 64   : $b64_digest\n";
print "Hex       : $hex_digest\n\n";
print "Converted : ", substr($b16_string, 0, 32), "\n";
__END__
Base 64   : MntvB0NYESObxH4VRDUycw
Hex       : 327b6f07435811239bc47e1544353273

Converted : 327b6f07435811239bc47e1544353273
[download]

You probably want to look into the endian problem further instead of just relying on it working from b64 -> b16 though.