long/large numbers and modulus in .NET

Question

Hello,

I'm currently writing a quick custom encoding method where I take a stamp a key with a number to verify that it is a valid key.

Basically I was taking whatever number that comes out of the encoding and multiplying it by a key.

I would then multiply those numbers to the deploy to the user/customer who purchases the key. I wanted to simply use (Code % Key == 0) to verify that the key is valid, but for large values the mod function does not seem to function as expected.

Number = 468721387; Key = 12345678; Code = Number * Key;

Using the numbers above: Code % Key == 11418772

And for smaller numbers it would correctly return 0. Is there a reliable way to check divisibility for a long in .NET?

Thanks!

EDIT: Ok, tell me if I'm special and missing something...

        long a = DateTime.Now.Ticks;
        long b = 12345;
        long c = a * b;
        long d = c % b;
        d == 10001 (Bad)

and

        long a = DateTime.Now.Ticks;
        long b = 12;
        long c = a * b;
        long d = c % b;
        d == 0 (Good)

What am I doing wrong?

Answer 1

Apparently, your Code fails to fit in the int data type. Try using long instead:

long code = (long)number * key;

The (long) cast is necessary. Without the cast, the multiplication will be done in 32-bit integer form (assuming number and key variables are typed int) and the result will be casted to long which is not what you want. By casting one of the operands to long, you tell the compiler to perform the multiplication on two long numbers.

Answer 2

Integer Overflow...see my comment.

The value of the multiplication you're doing overflows the int data type and causes it to wrap (int values fall between +/-2147483647).

Pick a more appropriate data type to hold a value as large as 5786683315615386 (the result of your multiplication).

UPDATE

Your new example changes things a little.

You're using long, but now you're using System.DateTime.Ticks which on Mono (not sure about the MS platform) is returning 633909674610619350.

When you multiply that by a large number, you are now overflowing a long just like you were overflowing an int previously. At that point, you'll probably need to use a double to work with the values you want (decimal may work as well, depending on how large your multiplier gets).

Answer 3

As others have said, your problem is integer overflow. You can make this more obvious by checking "Check for arithmetic overflow/underflow" in the "Advanced Build Settings" dialog. When you do so, you'll get an OverflowException when you perform *DateTime.Now.Ticks * 12345*.

One simple solution is just to change "long" to "decimal" (or "double") in your code.

In .NET 4.0, there is a new BigInteger class.

Finally, you say you're "... writing a quick custom encoding method ...", so a simple homebrew solution may be satisfactory for your needs. However, if this is production code, you might consider more robust solutions involving cryptography or something from a third-party who specializes in software licensing.

Answer 4

The answers that say that integer overflow is the likely culprit are almost certainly correct; you can verify that by putting a "checked" block around the multiplication and seeing if it throws an exception.

But there is a much larger problem here that everyone seems to be ignoring.

The best thing to do is to take a large step back and reconsider the wisdom of this entire scheme. It appears that you are attempting to design a crypto-based security system but you are clearly not an expert on cryptographic arithmetic. That is a huge red warning flag. If you need a crypto-based security system DO NOT ATTEMPT TO ROLL YOUR OWN. There are plenty of off-the-shelf crypto systems that are built by experts, heavily tested, and readily available. Use one of them.

If you are in fact hell-bent on rolling your own crypto, getting the math right in 64 bits is the least of your worries. 64 bit integers are way too small for this crypto application. You need to be using a much larger integer size; otherwise, finding a key that matches the code is trivial.

Again, I cannot emphasize strongly enough how difficult it is to construct correct crypto-based security code that actually protects real users from real threats.