También encontré este código:
http://www.lacorona.com.mx/fortiz/sat/
La desventaja es que es muy muy largo y es difícil encontrar el punto al que me refiero, pero en esencia el hace esto:
http://www.lacorona.com.mx/fortiz/sat/xml.php
Código PHP:
// La cadena es la cadena ya limpia en UTF8, $pkeyid es el key en pem
openssl_sign($cadena_original, $crypttext, $pkeyid, OPENSSL_ALGO_MD5);
openssl_free_key($pkeyid);
// El sello es el resultado arrojado en base 64
$sello = base64_encode($crypttext);
Y en efecto esto tampoco me da un sello válido, me gustaría que me ayudarán con el primer código que propuse porque es mas fácil implementarlo con otros lenguajes, este solo es viable en PHP5.
Si alguien tiene alguna idea se los agradeceré.