142^23%187 modulo RSA should be 65 but is 53 any idea why?

Question

As in title, 142^23%187 should be 65 not 53. It is part of RSA encrypting/decrypting algorithm.

Previous modulo operation is correct but secon one is not.

If u type 142^23%187 in wolphram alpha is correct 65 - and 65 is indeed A after decrypting.

Any ideas? Code below:

using System;
using System.Collections.Generic;

namespace RSA
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");



            AlgoritmRSA RSA = new AlgoritmRSA(11, 17, 7);
            RSA.Encrypting("A");
            RSA.Decrypting();



        }
    }
}

namespace RSA
{
    public class AlgoritmRSA
    {

        public AlgoritmRSA(int p, int q, int e) 
        {
            this.P = p;
            this.Q = q;
            this.E = e;

        }
        public int P { get; private set; }
        public int Q { get; private set; }
        public int E { get; private set; }

        List<int> J = new List<int>();
        List<double> C = new List<double>();
        List<double> NJ = new List<double>();
        List<char> ASCIIList = new List<char>();

        public void Encrypting(string message)
        {
            int n = P * Q;
            System.Console.WriteLine("N = {0}",n);

            foreach (var item in message)
            {
                J.Add(Convert.ToInt32(item));
            }

            System.Console.WriteLine("E = {0}", E);

            foreach (var item in J)
            {
                System.Console.WriteLine("J = {0}", item);
                C.Add(Math.Pow(item, E) % n);
                System.Console.WriteLine("C = {0}", C[0]);
            }

        }


        public void Decrypting()
        {
            double CC = Math.Pow(142, 23);
            double BB = CC % 187;
            System.Console.WriteLine(CC);


            int n  = P * Q;

            int K = ((P-1)*(Q-1)+1)/E;
            System.Console.WriteLine("K = {0}", K);


            foreach (var enc in C)
            {
                NJ.Add(Math.Pow(enc, K) % n);
                System.Console.WriteLine("NJ = {0}", NJ[0]);
            }

            foreach (var item in NJ)
            {
                ASCIIList.Add(Convert.ToChar(item));

            }

            System.Console.WriteLine("Encrypted Message: \n");

            foreach (var item in ASCIIList)
            {
                System.Console.WriteLine("{0}", item);
            }


        }

    }
}

You use ind and double - this will not work for your numbers! Use BigInteger or BigDecimal instead. — Robert, Nov 15 '18 at 12:29
Interesting... PowerShell is reporting the same thing: [math]::Pow(142, 23) % 187 = 53 — thepip3r, Nov 15 '18 at 20:00
Even making it a BigInt via explicit casting didn't fix it: ([bigint]([math]::Pow(142, 23))) % 187 = 53 — thepip3r, Nov 15 '18 at 20:17
@thepip3r You should cast before `Pow`, and you should not use `[Math]::Pow`, but `[bigint]::Pow` or better `[bigint]::ModPow(142, 23, 187)`. — user4003407, Nov 15 '18 at 20:19
When I use System.Numerics.BigInteger.ModPow() everything is fine and answer is correct (which I expect) - it means 65. Thanks for all help You provide me!! :) — DolaX, Nov 17 '18 at 17:26

score 0 · Answer 1 · answered Nov 15 '18 at 20:19

0

Here you are in PowerShell, works out to 65, as intended.

[bigint]::Pow(142, 23) % 187

...worrisome that the normal math function doesn't report an error and just reports incorrect information.

answered Nov 15 '18 at 20:19

thepip3r

2,855
6
32
38

2

There is no error, [Math.Pow](https://learn.microsoft.com/en-us/dotnet/api/system.math.pow?view=netframework-4.7.2#System_Math_Pow_System_Double_System_Double_) converts its arguments to double and returns a double. Since 142^23 is *way, way* too big to be exactly represented as a double you get the best double approximation which works out to 31814999504641998300455543523595688200117378088960. – President James K. Polk Nov 16 '18 at 02:25
So the math comes out wrong due to limitations in a programming function and that's not a problem? I may be misunderstanding but if I get an answer, without an error, I think most assume it has provided the correct answer. – thepip3r Nov 17 '18 at 16:06
1

There is nothing wrong with your correct answer using bigint, but your lament that Math.pow "just reports incorrect information" is misplaced. It's up to the programmer to understand the limits of floating point arithmetic. See the classic [is floating point math broken](https://stackoverflow.com/q/588004/238704) – President James K. Polk Nov 17 '18 at 16:13
Guys, thanks for all that time You spend on answers, all of them are helpfull for me! I'm not experienced programmer, I'm just lerning it. – DolaX Nov 17 '18 at 17:02

142^23%187 modulo RSA should be 65 but is 53 any idea why?

1 Answers1