c++ - C++ での RSA 暗号化

Question

ASCII 値を使用して文字を整数に暗号化 (RSA) したいと考えています。例えば。「a」は 48 として暗号化されます。

暗号化の場合: c=pow(m,e)%nc は暗号文、m は平文、(e,n) は公開鍵です。

pow(m,e) が 67^7 のように大きい場合、intまたはlongには収まりません。しかし、doubleを使用すると、モジュラス % 演算子では使用できません。そこで、for ループを使用して暗号化用にこの関数を作成しました。

int encrypt(int m, int e, int n)
{
    int res=m, i;
    for(i=0; i<e-1;i++)
        res=(res*res)%n;
    return res;
}

67である67 ^ 7mod11で機能しましたが、実際には正しくないことがわかりました。どこで間違ったのですか？

score 5 · Accepted Answer

あなたのループ

for(i=0; i<e-1;i++)
    res=(res*res)%n;

二乗e-1倍モジュロn、つまり、モジュロを計算しm^(2^(e-1))ますn。単純なアルゴリズムでm^eモジュロを計算するには、次を使用します。n

for(i = 0; i < e-1; ++i)
    res = (res*m) % n;

代わりは。

指数が大きい場合のやや高速なアルゴリズムの場合、二乗を繰り返すことで累乗を使用できます。

res = 1;
while (e > 0) {
    if (e % 2 != 0) {
        res = (m*res) % n;
    }
    m = (m*m) % n;
    e /= 2;
}
return res;

score 0 · Accepted Answer

通常、暗号化パラメータを使用する場合、int の代わりに「big int」を使用します。まさにそのためです。

ここにいくつかの提案があります: Bigint (bigbit) ライブラリ

2 に答える 2