简化模块化幂运算C ++ [英] Simplify modular exponentiation C++

问题描述

我正在尝试为RSA加密系统编写解密功能，对于非常很小的数字，一切似乎都工作正常，但是有时输出不正确(我认为原因是可能是浮点错误或某种堆栈溢出.

I am attempting to write the decryption function for an RSA encryption system, everything seemed to be working fine for very small numbers, however sometimes the output just isn't correct (I think that the cause may be a floating point error or some kind of stack overflow).

导致我出现问题的过程可以简化为(11 ^ 23)mod 187，但是如果有人希望看到它，我将提供完整的代码.我知道答案应该是88，因为这是西蒙·辛格(Simon Singh)博士在密码本"附录J中使用的示例(我也使用Wolfram Alpha进行了检查).但是，我得到的结果为149.但是，数字较小时，它与Wolfram Alpha一致.

The process which is causing me problems can be simplified to (11^23) mod 187 but I will include the full code in case anybody wants to see it. I know that the answer should be 88 as it is the example used in Appendix J of "The Code Book" by Dr Simon Singh (I also checked using Wolfram Alpha). However, I get the result of 149. However, with smaller numbers, it agrees with Wolfram Alpha.

我的想法是，我需要使用以下知识来简化模幂运算:

My thoughts are that I need to simplify the modular exponentiation using the knowledge that:

a ^ b = a ^ c * a ^ d [其中c + d = b]

a^b = a^c * a^d [ where c + d = b ]

但是，我仍然不能100％地确定这是否是这个问题，这是我有史以来的第一次堆栈溢出吗?(我仍然不是100％知道那是什么意思).在没有人问我之前，这不是什么功课，如果这个问题看起来微不足道，我感到抱歉.如果所有人都认为这样做太难了，那么我愿意使用gmp.h，但是如果我完全诚实的话，我宁愿不使用gmp.h.我的代码如下(上半部分是计算私钥，我认为这与我遇到的问题无关，但是为了防止我错了，我已经将其包括在内)，我真的希望你们能提供帮助，谢谢提前很多.

However, I'm still not 100% sure if this is this problem, is this my first ever stack-overflow? (I'm still not 100% sure what that means). Before anybody has a go at me, no this isn't any kind of homework and I'm sorry if this question seems trivial. I am open to using gmp.h if everyone thinks that this would be too difficult to do but I would rather not if I'm entirely honest. My code is below (the first half is to calculate the private key, which I believe is irrelevant to the problem I'm having but I've included it just in case I am wrong), I really hope you guys can help, thank you very much in advance.

#include <iostream>
#include <math.h>

using namespace std;

unsigned int modinv(unsigned int u, unsigned int v)
{
    unsigned int inv, u1, u3, v1, v3, t1, t3, q;
    int iter;

    u1 = 1;
    u3 = u;
    v1 = 0;
    v3 = v;

    iter = 1;

    while (v3 != 0)
    {

        q = u3 / v3;
        t3 = u3 % v3;
        t1 = u1 + q * v1;

        u1 = v1; v1 = t1; u3 = v3; v3 = t3;
        iter = -iter;
    }

    if (u3 != 1)
        return 0;
    if (iter < 0)
        inv = v - u1;
    else
        inv = u1;
    return inv;
}

int main()
{ long unsigned int p = 17;
long unsigned int q = 11;
long unsigned int phi = (p-1)*(q-1);
long unsigned int e = 7;
long unsigned int c = 11;
long unsigned int n = p*q;
long unsigned int d = modinv (e,phi);
    {
         cout << fmod (pow (c, d), n);
    }
    return 0;
}

推荐答案

11 ^ 23约为2 ^ 80.仅最大2 ^ 53的整数可以精确地表示为双浮点数.因此fmod(pow(c，d)，n))返回一个近似值.这不适用于密码学.

11^23 is approximately 2^80. Only integers up to 2^53 can be represented exactly as double floating-point numbers. Hence fmod(pow(c, d), n)) returns an approximate value. That is not suitable in cryptography.

已添加您可以使用重复平方来进行模幂运算.查看Wikipedia上有关平方求幂"的文章

ADDED You can do modular exponentiation using repeated squaring. Check Wikipedia's article about "Exponentiation by squaring"

这篇关于简化模块化幂运算C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！