C#: RSA implementation not working with large keys

Question

I'm trying to implement RSA Encryption in C#. I have it working with small keys such as this:

    public static int n = 33;
    public static int e = 7;
    public static int d = 3;

    static void Main(string[] args)
    {
        int A = 9;
        int enc = (int)(Math.Pow(A, e) % n);
        int dec = (int)(Math.Pow(enc, d) % n);
        Console.WriteLine(A);
        Console.WriteLine(enc);
        Console.WriteLine(dec);
    }

This outputs:

9
15
9

I can't understand why it doesn't work with larger keys. If I give these key values:

    public static int n = 3233;
    public static int e = 17;
    public static int d = 2753;

It outputs:

9
1971
-2147483648

According to Wikipedia (and checked with an RSA calculator from a university's website), n=3233 e=17 d=2753 is a valid RSA key set.

Can someone explain why I'm not getting the expected output?

Please note that there are [classes](http://msdn.microsoft.com/en-us/library/system.security.cryptography.rsacryptoserviceprovider.aspx) in the .NET Framework handling RSA encryption/decryption for you. Don't implement any homebrewn security, it's way to easy to get wrong. — nvoigt, May 02 '13 at 06:33

score 1 · Answer 1 · edited May 23 '17 at 11:43

Your integers are overflowing. Change your code to this:

static void Main(string[] args)
        {
            checked
            {
                int A = 9;
                int enc = (int)(Math.Pow(A, e) % n);
                int dec = (int)(Math.Pow(enc, d) % n);
                Console.WriteLine(A);
                Console.WriteLine(enc);
                Console.WriteLine(dec);
            }
        }

and you will see it throw an error. There is a maximum value that 32 bit integers can hold. Even if you switched A to an unsigned long (UInt64) the double in the Math.Pow operations will overflow. You will probably have to build your own power and mod function to handle these large numbers.

EDIT: found this SO post: Encrypt and decrypt a string

score 0 · Answer 2 · edited May 23 '17 at 11:57

first: try to avoid your own crypto implementations ...

if you just want to know how sthe stuff works or if this is an assignment:

as you might know integer types like int / long have a fixed length of 32 / 64 bit

your variables simply overflow ...

RSA calculations usually depend on numbers that are way bigger ...

The Biginteger Class will help you with arbitrary sized integer calcualtions ...

but be aware that the naive way of writing stuff like

C = X ^ E mod N

brings a little problem here ... assume X is the clear text ... E is some exponent ... even with relatively small numbers the intermediate result of X ^ E would be way too big ... you need to take some properties of modular arithmetic into account ... you can split X ^ E into multiple operations and may apply the modulo reduction to all of them (which reduces the size of the numbers) whithout changing the result ... one approach for this is the square and multiply algorithm ... but you don't have to implement that by yourself ... BigInteger contains the ModPow Function ...

if you want to see a BigInteger based RSA implementation take a look here
in the example you will also find the RSACryptoServiceProvider ... if you need RSA calculations, this should be your first choice ...

C#: RSA implementation not working with large keys

2 Answers2