I had a similar problem with Twofish about a decade ago. The biggest problem was that there was a definite difference in implementation, basically like starting with different IVs or maybe endian problems on different platforms. My solution was to get the C++ code and code up an exact workalike XS (Crypt::Twofish). You may need to do the same; look at RijndaelManaged's source (C#?) and get the constants it uses, then see if you can make your own private version of Crypt::Rijndael which handles it. A pure perl version would be fine too, although slow, if you're willing to take the time to decrypt legacy encrypted data, but that wouldn't work for production environment code.