如何制作适用于更大 p 和 q 值的 RSA？

Question

我的项目是使用讲师亲自给出的用 C 编写的框架来实现 RSA。我对 C 不太熟悉，但能够做到。但问题是它只有在以下情况下才有效：

p<200 and q<200

当值超过该值时，它会失败。我想让 p 和 q 大于那个数字。我的代码有什么问题导致它只有在 p 和 q 小于 200 时才能工作或成功吗？

//unsigned int
uint p, q, e, d, n;

encrypt/decrypt:

时的模幂函数

uint ModPow(uint base, uint exp, uint n) {
uint h;
uint r;
int bin[32];
int i;

r=base;
i=0;

while(exp > 0)
{
    if(exp%2 == 0)
    {
        bin[i] = 0;
    }else{
        bin[i] = 1;
    }
    exp = exp/2;
    i++;
}
i--;
while(i>0)
{
    r = (r*r)%n;
    if(bin[--i]==1)
    {
        r = (r*base)%n;
    }
}
printf("r:%d n:%d\n", r,n );
return r;
}

检查 GCD(a,b) 的函数：

uint GCD(uint a, uint b) {
uint prev_a;

while(b != 0) {
    printf("GCD(%u, %u)\n", a, b);
    prev_a = a;
    a = b;
    while(prev_a >= b) prev_a -= b;
    b = prev_a;
}
printf("GCD(%u, %u)\n\n", a, b);
return a;
}

使用扩展欧几里德算法求 d

uint ModInv(uint a, uint m) {
int m0 = m, t, q;
int x0 = 0, x1 = 1;

if(m==1)
    return 0;

while(a>1)
{
    q = a/m;
    t = m;
    m = a%m, a=t;
    t=x0;
    x0=x1-q*x0;
    x1=t;
}
if(x1<0)
    x1+=m0;
return x1;
}

生成密钥，这个我用p=23，q=17

void miniRSAKeygen(uint *p, uint *q, uint *e, uint *d, uint *n) {
*p =23;
*q = 17;
*n = (*p)*(*q);
*e = 2;
unsigned long long phi = (*p-1)*(*q-1);
printf("Phi %llu\n",phi);
while(*e<phi)
{
    if(GCD(phi,*e)==1)
        break;
    else
        *e = *e + 1;
}
*d = ModInv(*e,phi);
}

Encrypt/Decrypt

uint miniRSA(uint data, uint key, uint n) {
unsigned long long result;
    result = ModPow(data,key,n); 
printf("%llu\n", result );
return result;
}

这是主要功能：

int main(int argc, char* argv[]) {
uint plain_data, encrpyted_data, decrpyted_data;
uint seed = time(NULL);
plain_data = 201;

// create random number with seed
seed = time(NULL);
InitWELLRNG512a(&seed);

// create RSA key
miniRSAKeygen(&p, &q, &e, &d, &n);
printf("0. Key generation is Success!\n ");
printf("p : %u\n q : %u\n e : %u\n d : %u\n N : %u\n\n", p, q, e, d, n);

// test RSA encryption
encrpyted_data = miniRSA(plain_data, e, n);
printf("1. plain text : %u\n", plain_data);    
printf("2. encrypted plain text : %u\n\n", encrpyted_data);

// test RSA decryption
decrpyted_data = miniRSA(encrpyted_data, d, n);
printf("3. cipher text : %u\n", encrpyted_data);
printf("4. Decrypted plain text : %u\n\n", decrpyted_data);

// print result
printf("RSA Decryption: %s\n", (decrpyted_data == plain_data) ? "SUCCESS!" : "FAILURE!");

return 0;
}

这里似乎有什么问题？提前致谢。这里的失败是当加密值不return到解密时的明文值

这是结果的例子：

failed one

success one

Answer 1

在您的系统上 uint 是 32 位无符号类型。如果p和q大于255（2⁸-1）则n=p*q大于等于2¹⁶。这意味着中间计算 r*r 可能最终大于行 r = (r*r)%n; 中的 2³² - 1。无符号整数溢出是无声的，只有低位 32 位（对于 32 位无符号类型）将被保留，这会丢失信息并导致错误答案。 r = (r*base)%n; 行中也出现了类似的问题。

解决的办法首先是不要把算术想当然。这是你作为程序员成熟的一部分。其次，您可以为中间结果使用更宽的类型来解决问题。例如，您可以创建一个简单的 mod_mul 函数：

#include  <stdint.h>

uint mod_mul(uint a, uint b, uint n) {
    uint64_t result = ((uint64_t) a) * ((uint64_t) b) % ((uint64_t) n);
    return (uint) result;
}

这是可行的，因为中间算术是用 64 位算术执行的，并且由于我们知道结果小于 2³² 最终 (uint) 转换结果为 no信息丢失。

如何制作适用于更大 p 和 q 值的 RSA？

How to make RSA that works with bigger p and q value?

c

encryption

cryptography

rsa