simple algorithm wont produce correct answer

Question

i need use the rsa encryption algorithm which is a pretty simple algorithm. i have tested the answers using the calculator on windows by entering in the formula and an online rsa calculator and they both returned the correct value but when i write the code to do it it brings back the wrong answer.

            double c = Math.Pow(p, e) % n;

this formula works perfect if i enter it into the calculator on windows so the formula isnt the problem. i think it might be something to do with the % being used on a double but to use math.pow it needs to be a double and if i convert it to a long int 64 after then mod n it comes back with an overflow error message. if i use int 32 it says its too big for int 32.

the values for p, e and n are entered by the user.

Answer 1

Use BigInteger.

It is specifically designed for working in this context.  Several of the methods (i.e. ModPow) literally doing everything you want.

Answer 2

p and e are integers right?

What are the range of values for p and e that you want this to work for?  Obviously Pow(p,e) can be an enormously large value that might not have a representation as an integer with a modest number of bits.

I think you should use one of the techniques on this page:  http://en.wikipedia.org/wiki/Modular_exponentiation

Maybe this one:  (what follows is lifted directly from Wikipedia)

The following is an example in pseudocode based on Applied Cryptography by Bruce Schneier[1] The inputs base, exponent, and modulus correspond to b, e, and m in the equations given above.

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent & 1) equals 1:
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

Answer 3

yes all 3 are integers its ment to be for an rsa encription function so the power can be high. the example that needs to be worked out is 44^49mod1517 this should = 1069 but instead with the code i have at the moment it = 1047 since its kinda close im guessing its a problem that numbers are being rounded or something. i get an overflow if i try to use a int64 .

ive tried looking at the bigintegers but i cant use them ive tried using system.numerics but it doesnt know what it is. im using visual studio 2010.

i coded it a little different so i could run it in debug to see what was happening and when it does 44^49 it gives the same answer as in the calculator but a small bit shorter. like the answer is in e notation which i dont understand but its a huge long number in the calculator  3.3820587525965804518360474476833e+80. in visual studio it tells me its much shorter than that i cant copy and paste but its like 3.38205875259658045e+80 in visual studio no idea if that makes a difference but thats whats goin on

Answer 4

Are you sure your project targets the .NET framework 4?  That is required to use BigInteger.  If this is not an academic project, System.Security.Cryptography contains a full-featured set of encryption classes that you can use for production code.

Answer 5

unfortunately its for a project so i have to do it the hard way. i dont know what the story with the .net is i looked in add or remove programs and .net  framework 4 client profile .net  framework 4 extended and .net  framework 4 multi-targeting pack installed. im using windows xp sp3.

Answer 6

Go with the built-in Cryptography classes. You don't need to reinvent the wheel - unless this is an academic project, like InLocoAbsentia mentioned, in which case you should probably ask your professor for guidance.

---

Check out My Blog. Now updated to actually work!

Answer 7

yes all 3 are integers its ment to be for an rsa encription function so the power can be high. the example that needs to be worked out is 44^49mod1517 this should = 1069 but instead with the code i have at the moment it = 1047 since its kinda close im guessing its a problem that numbers are being rounded or something. i get an overflow if i try to use a int64 .

ive tried looking at the bigintegers but i cant use them ive tried using system.numerics but it doesnt know what it is. im using visual studio 2010.

i coded it a little different so i could run it in debug to see what was happening and when it does 44^49 it gives the same answer as in the calculator but a small bit shorter. like the answer is in e notation which i dont understand but its a huge long number in the calculator  3.3820587525965804518360474476833e+80. in visual studio it tells me its much shorter than that i cant copy and paste but its like 3.38205875259658045e+80 in visual studio no idea if that makes a difference but thats whats goin on

It's very important that you don't use floating point numbers (like double or float) to do modular arithmetic for cryptography.  Notice that number is about 3 times 10 to the 80th power.   But there's no way that a 64 bit number is going to give you all 80 significant decimal digits.  That would require a number with at least 268 bits of mantissa to represent accurately enough to get the MOD result accurate to the nearest integer.  After all, the least significant bits are still important for your answer, and so are the most significant bits.  Actually all bits are important to get the right answer, that's why cryptography uses modular arithmetic.

Fortunately, if you calculate the answer incrementally, you don't need all of those bits at once.  So you can still compute the result using that algorithm that makes use of modest sized int or long (32 - 64 bits) variables and takes several steps to compute, but you cannot compute this in one shot by putting that large value into a float or double floating point variable (with only 32-64 bits).

Here's a poser for you:  The population of the Earth is 6.84e+9.  Is the population of the world ODD or EVEN?    

This number is not 6,840,000,000 (the answer would be EVEN, if this were true).  It's more like 6,84?,???,???.  The other digits are not known.  I didn't express them accurately in my 6.84e+9 figure.  You could make them up (fill them with zeroes arbitrarily)  But you could also fill them 1's (6,841,111,111) and the answer is still 6.84e+9.  That's just how scientific notation (a.k.a. floating point notation) works.  The unspecified digits are just that:  unspecified.  If I could specify more digits, I would have to say: 6.8411111111e+9.  or 6.840000000e+9 It takes space for me to type all those 1s or 0's and just like that, it takes bits for the computer to represent them.  But if I only ever give you 2 digits after the decimal place, you'll never know what those other digits are to tell me if it is an odd or even number.  So the correct answer is YOU CAN'T TELL.

A floating point number is broken into a matissa and exponent.  The mantissa gives the significant digits (the 6.84), and the exponent gives the power (the e+9 part.)  A 64 bit floating point number (double) uses 53 bits of mantissa giving you about 15 significant decimal digits (log(2^53)/log(10)).  Nowhere close to the the 80 or so significant decimal digits that you would need to do your modular arithmetic on a number as big as 3.8e+80.