In my project I'm using the value of public exponent of 4451h. I thought it's safe and ok until I started to use one commercial RSA encryption library. If I use this exponent with this library, it throws exception.

I contacted developers of this library and got the following reply: "This feature is to prevent some attacks on RSA keys. The consequence is that the exponent value is limited to {3, 5, 17, 257 or 65537}. Deactivating this check is still being investigated, as the risks may be great."

It's the first time in my life I hear that values other than {3, 5, 17, 257 or 65537} are used to break RSA. I knew only of using 3 with improper padding being vulnerable.

Is that really so? Surely, I can use another library, but after such answer I worried about security of my solution.

There is no known weakness for any short or long public exponent for RSA, as long as the public exponent is "correct" (i.e. relatively prime to p-1 for all primes p which divide the modulus).

If you use a small exponent and you do not use any padding for encryption and you encrypt the exact same message with several distinct public keys, then your message is at risk: if e = 3, and you encrypt message m with public keys n1, n2 and n3, then you have ci = m3 mod ni for i = 1 to 3. By the Chinese Remainder Theorem, you can then rebuild m3 mod n1n2n3, which turns out to be m3 (without any modulo) because 
n1n2n3 is a greater integer. A (non modular) cube root extraction then suffices to extract m.

The weakness, here, is not the small exponent; rather, it is the use of an improper padding (namely, no padding at all) for encryption. Padding is very important for security of RSA, whether encryption or signature; if you do not use a proper padding (such as the ones described in PKCS#1), then you have many weaknesses, and the one outlined in the paragraph above is not the biggest, by far. Nevertheless, whenever someone refers to an exponent-size related weakness, he more or less directly refers to this occurrence. That's a bit of old and incorrect lore, which is sometimes inverted into a prohibition against big exponents (since it is a myth, the reverse myth is also a myth and is no more -- and no less -- substantiated); I believe this is what you observe here.

However, one can find a few reasons why a big public exponent shall be avoided:


Small public exponents promote efficiency (for public-key operations).
There are security issues about having a small private exponent; a key-recovery attack has been described when the private exponent length is no more than 29% of the public exponent length. When you want to force the private exponent to be short (e.g. to speed up private key operations), you more or less have to use a big public exponent (as big as the modulus); requiring the public exponent to be short may then be viewed as a kind of indirect countermeasure.
Some widely deployed RSA implementations choke on big RSA public exponents. E.g. the RSA code in Windows (CryptoAPI, used by Internet Explorer for HTTPS) insists on encoding the public exponent within a single 32-bit word; it cannot process a public key with a bigger public exponent.


Still, "risks may be great" looks like the generic justification ("this is a security issue" is the usual way of saying "we did not implement it but we do not want to admit any kind of laziness").
