PowerMod function working for small integers bur not for large ones

Question

Here is the PowerMod function I implemented using ttmath BigInt library:

#include <iostream>
#include <ttmath/ttmath.h>

using namespace std;

template <typename Integer>
Integer iPowerMod(Integer & n,Integer & p,Integer & b)
{
    if (n>b) {n.Div(b,n);}
    Integer iOut="1";
    Integer iOutk=n;
    Integer pref="1";
    Integer ptemp=p;
    Integer factor="2";
    while (ptemp!=0)
    {
         while ((factor*pref)<=ptemp)
        {
            iOutk.Mul(iOutk);
            if (iOutk>b) {iOutk.Div(b,iOutk);}
            pref.Mul(2);
        }
        iOut.Mul(iOutk);
        if (iOut>b) {iOut.Div(b,iOut);}
        iOutk=n;
        ptemp-=pref;
        pref="1";
    }
    return iOut;
}

int main()
{
    ttmath::UInt<100> n,p,b;
    n="52526321452369856214521";
    p="731779601467";
    b="40420472400259202128651";
    cout << iPowerMod(n,p,b);
    return 0;
}

This is working for small (4-5 digits) integers, but not for large ones. As I am trying to build an encryption app using the RSA algorithm, I need it to work with large integers. I am using Mathematica 10.2 Kernel for verification. But, I've been unable to find the flaw. It'd be great if anyone could help. :)

Is this an exercise, or do you actually intend to protect secrets with this app? If the latter, *don't write your own crypto*. There are far too many ways to get it wrong (see the latest vulnerability in OpenSSL for evidence - and that is a library that is written by people who really understand crypto). — Martin Bonner supports Monica, Mar 02 '16 at 11:42
@MartinBooner This is just an exercise. Sort of fun, if you will. And I am really curious as to why this isn't working with big integers. I've got the rest of the program somewhere else. It's working nice for smaller numbers. But, I need it to work with larger ones. The PowerMod is what is creating the problem. That is why I only put this in the question. — MathIsNice1729, Mar 02 '16 at 11:47
Fun is fine! I just get nervous in case people think they can do it properly (and writing the crypto is the *easy* bit of security engineering). — Martin Bonner supports Monica, Mar 02 '16 at 11:56
.What exactly doesn't work? What is the output of your `main()`? — Rudy Velthuis, Mar 02 '16 at 12:00
@RudyVelthuis The output differs from the output given by Mathematica by a large amount. I was checking them for smaller integers and it was okay. But, they don't seem to work with larger ones. — MathIsNice1729, Mar 02 '16 at 12:02
OK. Not an answer, but take a look here: // http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n . — Rudy Velthuis, Mar 02 '16 at 12:05
@RudyVelthuis Yeah, my method is similar just that I've implemented some tricks to speed up the process and used a BigInt library to facilitate the calculation involving large numbers. I just couldn't find a way that it could help me in. — MathIsNice1729, Mar 02 '16 at 12:09
The code I posted works fine with BigIntegers (I use it in my own BigInteger library) and can not be optimized with any tricks anymore. It is very much optimized. So perhaps you should first try to get it right (producing the correct result) and then start optimizing? — Rudy Velthuis, Mar 02 '16 at 12:18
Anyway, what does Mathematica think the result should be, and what do you get? — Rudy Velthuis, Mar 02 '16 at 12:20
@RudyVelthuis When I `cout`ed the `iOut` and `iOutk` numbers after each completion of the nested `while` loop, it seems like the problem is either the `Mul` or the `Div` function. Do you think I should consider changing the library? — MathIsNice1729, Mar 02 '16 at 16:18
I just tried in Java, using java.math.BigInteger as well as in Delphi, using my own BigInteger, and I get the same result: `39811619560416273798458`. That should be yours too. — Rudy Velthuis, Mar 02 '16 at 16:31
I would consider debugging my code until I get the right result. — Rudy Velthuis, Mar 02 '16 at 16:32
FWIW, I just translated your code to Delphi, and got the same result as my code and as Java, but using the BigInteger equivalent of `a = a % b` instead of something like `Div()`. **Perhaps, instead of doing things like `a.Div(b, a)`, you should do: `a.Div(b, c); a = c;` every time you do a `Div()`. it could be that `a` is overwritten with the quotient *after* the remainder is set**. — Rudy Velthuis, Mar 02 '16 at 16:54
@RudyVelthuis Thanks. It worked. Now, I got the correct results. — MathIsNice1729, Mar 02 '16 at 17:08

score 0 · Answer 1 · answered Mar 02 '16 at 11:52

0

I bet the problem is your frequent use of:

  i.Div(b,i)

Which (if I have read correctly) is supposed to calculate:

  i /= b

and

  i %= b;

At the same time.

That probably works for values that fit in a single 32-bit word, but it's going to go horribly wrong for multi-word values.

I would look for a library with some documentation.

answered Mar 02 '16 at 11:52

Martin Bonner supports Monica

28,528
3
51
88

Thanks. I'm willing to rewrite all of it if needed. I just wanna make it work. – MathIsNice1729 Mar 02 '16 at 11:59
1

It is not going to be horribly wrong for multi-word values at all. I bet most BigInteger implementations have a function like that. The ones I know work fine. – Rudy Velthuis Mar 02 '16 at 12:04
1

@RudyVelthuis: The (home-grown) one I used at my previous job would not have coped fine. – Martin Bonner supports Monica Mar 02 '16 at 12:10
I too was skeptical about the use of Div as there should've been a dedicated congruent function. – MathIsNice1729 Mar 02 '16 at 12:11
1

Any serious BigInteger library would cope fine. I assume that `ttmath` should be able to cope too. FWIW, I also have [a homegrown one](http://rvelthuis.de/programs/bigintegers.html), and it certainly has no problems with (what is called there) `DivMod` on very large integers. – Rudy Velthuis Mar 02 '16 at 12:14
1

@SayantanSantra: Did you take a look at the link I put in my comment? The `modpow()` described there works fine, – Rudy Velthuis Mar 02 '16 at 12:16
@RudyVelthuis Can you please tell me how I can install your library on my PC and use it? I feel like giving it a try. – MathIsNice1729 Mar 02 '16 at 14:28
2

My code is in Delphi, a language mainly incompatible with C++. I doubt you will be able to use it, unless you have Embarcadero C++Builder, which can read Object Pascal files. – Rudy Velthuis Mar 02 '16 at 16:06
1

Why don't you try to install [gmp](https://gmplib.org/) and use that? No nice operator overloading, etc. but an entirely thorough library. – Rudy Velthuis Mar 02 '16 at 16:09
@RudyVelthuis Okay. I'll try to debug it the way it is. Then, I'll try GMP. – MathIsNice1729 Mar 02 '16 at 16:34

PowerMod function working for small integers bur not for large ones

1 Answers1