-1

我正在尝试解决 2 个小数字的 RSA。我可以计算 n、phi 和 e，但是当我必须计算 d 时总是卡住。请帮助我。例子。

        p = 3,      q = 7,
        n =  3*7 = 21,
        phi(21)= 2*6 = 12, 
        e = 5

        d = (5^-1) (mod 21) 

        or

        d * 5 = k * 12 + 1   (where k is some number)

我试图弄清楚 d * 5 = 25 = 5 * 12 + 1 的计算，但这是针对小数的，有没有其他方法可以用简单的方法计算 d

4

1 回答 1

3

下面的伪代码可以帮助你（从这个链接大量借用

// choose prime factors:
p = 3;
q = 7;

n = p * q; // =21
phi = (p-1)*(q-1); // = 12
// Choose e such that 1 < e < phi and e and n are coprime:
e = 5; 
// Compute a value for d such that (d * e) % phi = 1. 
// in other words, solve 5 * d % 12 = 1
d = 5; // since 5 * 5 = 25; modulo 12 = 1. How odd: d == e...

Public key is (e, n) => (5, 21) 
Private key is (d, n) => (5, 21) 

Testing this out on a "message" with the value of '2':
The encryption of m = 2 is 
    c = 2^5 % 21 = 32 % 21 = 11 
The decryption of c = 11 is 
    m = 11^5 % 21 = 161051 % 21 = 2

如您所见，我们在加密/解密步骤后收到了“消息”。

请注意，由于 e==d，这是（不幸的是）对称密码：如果您再次应用加密，您也会收到消息。这表明e的选择很差。这是这些玩具RSA问题的问题......

于 2013-03-12T15:16:35.217 回答