2

我正在尝试实施 RSA 加密方案。它是这样的：

encrypted data = ((message)^e) % n和decrypted data = ((encrypted data)^d) % n

我试图在 c 中实现这一点。这是代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    long int num = 3255859; 
    long int encrypt =(int)pow((double) num,3) % 33;
    printf("%ld\n",encrypt);

    return 0;

}

我编译这个使用gcc -Werror -g -o encrypt encrypt.c -lm

这是我得到的输出 = -2，这显然是错误的。当我为较小的数字尝试此代码时，我得到了正确的结果。例如：

当我设置时num = 2，我得到了正确的结果，即8

我知道我要么输入错误，要么我在某处用完了边界。我确实需要使用此代码来加密像上面代码中的大数字。

你能指出我哪里出错了。

谢谢

编辑：

好的，根据@Micael Oliver 的建议，这里是修改后的代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    unsigned long long  num = 3255859; 

    long long encrypt =(long long)pow((double) num,3) % 33;

    printf("%llu\n",encrypt);

    long long decrypt =(long long)pow((double) encrypt,7) % 33;

    printf("%llu\n",decrypt);

    return 0;

}

这是此代码的输出：

Notra:Desktop Sukhvir$ gcc -Werror -g -o encrypt encrypt.c -lm
Notra:Desktop Sukhvir$ ./encrypt
18446744073709551608
18446744073709551614

这显然是错误的，因为第二个输出应该是 3255859

4

3 回答 3

2

您的代码中混合了一些无符号和有符号数字——您应该尽可能避免这种情况。此外，您正尝试%llu在有符号的 long long 上使用 -%lld在这种情况下您应该使用。

但这里还有一个更微妙的问题。在这一行：

long long encrypt =(long long)pow((double) num,3) % 33;

pow返回 a double，这不能保证您正在寻找的所有精度。当您投射到 时，您最终会丢失几位数long long。不幸的是，C 并没有为计算指数提供一个很好的选择，所以你需要自己实现一些东西或使用一个库（其他一些答案已经提出了一些建议）。

如果您想自己实现一个，可以在 Wikipedia 上找到一篇关于平方快速取幂的精彩文章：平方取幂

它们提供了一些伪代码，这些伪代码在 C 语言中应该是显而易见的。

但最后，一般而言，您的代码将受到 的大小long long或您选择的任何类型的限制。最终，对于大量数据，您应该使用其他库，或者找到更好的算法。在这种情况下，您要计算幂，然后取模——这正是模指数算法无需处理这些库即可完成的工作。您可以在此处找到 Wikipedia 文章：模幂运算

于 2013-09-29T02:17:49.253 回答
0

只要您的数字最多是您正在使用的类型的一半，您就可以执行以下操作：

(((num * num) % 33) * num) % 33

一般来说，对于任何实用的加密目的，您都需要更大的值和一个计算框架来处理 1024+ 位数。为此，您可以使用现有代码（我建议libtommath来自libtomcrypt，绝对不是GMP）或编写自己的代码。

于 2013-09-29T02:10:08.300 回答
0

一个建议是使用另一种数据类型，如 long long：

3255859^3 ==  34514116960466804779
ULLONG_MAX == 18446744073709551615  // this is the minimum guaranteed

因此， unsigned long long 可能不起作用。一般来说，改变数据类型是有限制的。您可以考虑的另一种更强大的方法是使用 GMP - free。 gmp手册 ——

-- 你也可以在这个站点下载 gmp。

代码片段：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

int main()
{
    mpz_t rop, base, exp, mod;
    mpz_init2(rop,128); 
    mpz_init2(base,128); 
    mpz_init2(exp,128); 
    mpz_init2(mod,128);
    mpz_set_ui(base, 3255859);
    mpz_set_ui(exp, 3);
    mpz_set_ui(mod, 33);
    mpz_powm_sec (rop, base, exp, mod);
    gmp_printf ("result %Zd\n", rop);    
    return 0;
}
于 2013-09-29T02:07:54.080 回答