c++ - RSA 选择加密 key c++ 整数

Question

在我的 RSA 密码系统中，我试图选择一个与 phi(n) 相对质数的加密 key e。

phi(n) 是两个数 p-1 和 q-1 的乘积，其中 p 和 q 都是素数.这些素数是使用朴素素数测试生成的(是的，我知道它效率低下)。

当我执行我的程序时，我得到以下输出:

***** p *****
878222789

***** q *****
851559637

***** n = p x q *****
3523942633

***** phi(n) = (p-1)x(q-1) *****
1794160208

***** e *****
99

***** d *****
47835

问题是，每次我运行这个程序时，e 总是以 99 或 97 结束。它是这个输出中唯一的常数。我几乎肯定我的 GCD 算法是正确的。但它是 select_e() 中唯一的子例程。

相关函数:

void select_e(uint &e, const uint phi_n)
{ // e = encryption key
    for(int i=3;i<100;i++) {
        if(gcd(phi_n,i) == 1) {
            e = i;
            break;
            }
    }
    printf("\n***** e *****\n%u\n",e);
}

uint gcd(uint a, uint b) {
    uint temp;
    while (b!=0) {
        temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}

编辑***********************

好的，所以我在 select_e() 中添加了一个 break 语句，它导致程序为 e 输出通常为 3 或 5 的值。现在，据我了解，拙劣的解密是两个 32 位整数相乘并将值存储在另一个 32 位整数中的整数溢出的结果。因此，我修改了我的程序以生成较小的 p 和 q 并取模。这是该函数:

void generate_pq(uint &p, uint &q)
{
    srand(time(NULL));
    bool repeat = false;
    printf("\nGenerating keys...\n");

    while(!repeat) {
        p = rand()%100;
        repeat = isPrime(p);
    }
    repeat = false;
    while(!repeat) {
        q = rand()%100;
        repeat = isPrime(q);
    }
    printf("\n***** p *****\n%u\n\n***** q *****\n%u\n",p,q);
}

现在的问题是，有时，我运气好，消息被成功解密。其他时候它不起作用。这是一个拙劣的解密示例:

Generating keys...

***** p *****
79

***** q *****
49

***** n = p x q *****
3871

***** phi(n) = (p-1)x(q-1) *****
3744

***** e *****
5

***** d *****
749

Message: fdsa 

Cipher: �/�J

Decrypted Message: �a

我知道解密和加密功能有效。我分别测试了它们并检查了算法。它们不是问题的根源。如果需要，我会为后代提供它们。

Answer 1

好吧，您选择第一个可能大于二的数字。由于与数字本身相比，任何大数的素数因子的数量都非常少，因此您不能期望测试 if(gcd(phi_n,i) == 1) 多次失败。也许失败一次，也许失败两次，但我什至不想等到失败十次...

所以答案是在循环的每次迭代中随机选择一个 i 而不是简单地向上计数。

---

顺便说一句:您的输出在另一个方面很有趣:3523942633 绝对不是 878222788 和 851559636 的乘积。不知道为什么，但它看起来像是由于使用 32 位整数而被无意截断...