Some things I noticed when reading through your code...

Both your encryption and your decryption dictionaries have duplicate entries. Of course, only one of these (the last) will be used as the key in the hash. After seeing a couple, I wrote a script to find all duplicates. This is the output:

Plain words with multiple translations:
EXCEPT: NEH-DIH, NA-WOL-NE
HIGH: WO-TAH, EXPLOSIVE
SUPPLY: NAL-YEH-HI, SHIP
TANK: CHAY-DA-GAHI, DESTROYER

Code words with multiple translations:
AH-DEEL-TAHI: DEMOLITION, DETONATOR
ALI-KHI-HO-NE-OHA: ELEVATE, TERRACE
ALTH-AH-A-TEH: CLASS, TYPE
BIH-TSE-DIH: BEFORE, PREVIOUS
BILH: CONSIST, WITH
BOSH-KEESH: SHORT, SIDE
CHA-GEE: THE, THEY
CLO-DIH: FIELD, OUT
IL-DAY: ARRIVE, REACH
KUT: NOW, PRESENT, READY
NAHL-KIHD: CALIBER, DEGREE
NAZ-PAS: ROUND, SURROUND
NEH-DIH: BUT, EXCEPT
SHIL-LOH: EXPEDITE, IMMEDIATELY, QUICK
SHIP: MERCHANT, SUPPLY
TA-A-TAH: ALL, ENTIRE
TAH-BAHN: BEACH, SHORE
WHO-NEH: REPORT, REVEAL
WO-CHI: FLARE, ILLUMINATE
[download]

You can use Carp's croak (and carp) instead of die (and warn) to help the user of your module to find where things went awry in his code.

tr works with character ranges, not regular expressions.

Why use indexes in your foreach loops? You can use (implicit) aliases for the current element, leading to clearer and less cluttered code, eg this chunk from your encrypt sub:

my @words = split /\s+/, $str;
foreach my $word (@words) {
    $word = $CDICT{$word}, next if exists $CDICT{$word};

    my @letters = split //, $word;
    foreach (@letters) {
        next if /\d/;
        if (exists $CALPHA{$_}) {
            $_ = $CALPHA{$_}->[ rand @{$CALPHA{$_}} ];
        } else {
            croak "Letter '$_' not found in encryption dictionary";
        }
    }
    $word = join ' ' => @letters;
}
return join '  ' => @words;
[download]

— Arien