Hola Gente,
 
He encontrado la formá en que trabaja, tenía un salt por eso no coincidia, al final utilizaba algo como esto:  
 Código PHP:
    public class StringEncrypter {
 
    Cipher ecipher;
 
    public StringEncrypter(String passPhrase) {
 
        // 8-bytes Salt
        byte[] salt = {
            (byte) 0xA9, (byte) 0x9B, (byte) 0xC8, (byte) 0x32,
            (byte) 0x56, (byte) 0x34, (byte) 0xE3, (byte) 0x03
        };
 
        // Iteration count
        int iterationCount = 19;
 
            KeySpec keySpec = new PBEKeySpec(passPhrase.toCharArray(), salt, iterationCount);
            SecretKey key = SecretKeyFactory.getInstance("PBEWithMD5AndDES").generateSecret(keySpec);
 
            ecipher = Cipher.getInstance(key.getAlgorithm());
 
            // Prepare the parameters to the cipthers
            AlgorithmParameterSpec paramSpec = new PBEParameterSpec(salt, iterationCount);
 
            ecipher.init(Cipher.ENCRYPT_MODE, key, paramSpec);
    }
 
    public String encrypt(String str) {
 
            // Encode the string into bytes using utf-8
            byte[] utf8 = str.getBytes("UTF8");
 
            // Encrypt
            byte[] enc = ecipher.doFinal(utf8);
 
            // Encode bytes to base64 to get a string
            return new sun.misc.BASE64Encoder().encode(enc);
 
     }
 
 } 
    
  Aunque necesito pasarlo a PHP, entiendo que escapa a sus conocimiento por lo que si a alguno ya lo ha hecho, les agradecería el comentario. 
Saludos.