-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 に答える