2

RSA暗号化スキームを実装しようとしています。次のようになります。

encrypted data = ((message)^e) % nとdecrypted data = ((encrypted data)^d) % n

これをcで実装しようとしました。コードは次のとおりです。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    long int num = 3255859; 
    long int encrypt =(int)pow((double) num,3) % 33;
    printf("%ld\n",encrypt);

    return 0;

}

これを使用してコンパイルしましたgcc -Werror -g -o encrypt encrypt.c -lm

これは私が得た出力 =-2であり、明らかに間違っています。小さい数値に対してこのコードを試すと、正しい結果が得られます。例：

を設定するnum = 2と、正しい結果が得られます。8

タイプキャストが間違っているか、どこかで境界が不足していることを知っています。上記のコードのような大きな数字を暗号化するには、このコードを使用する必要があります。

どこが間違っているのか指摘していただけませんか。

ありがとう

編集：

@Micael Oliver からの提案によると、変更されたコードは次のとおりです。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    unsigned long long  num = 3255859; 

    long long encrypt =(long long)pow((double) num,3) % 33;

    printf("%llu\n",encrypt);

    long long decrypt =(long long)pow((double) encrypt,7) % 33;

    printf("%llu\n",decrypt);

    return 0;

}

このコードの出力は次のとおりです。

Notra:Desktop Sukhvir$ gcc -Werror -g -o encrypt encrypt.c -lm
Notra:Desktop Sukhvir$ ./encrypt
18446744073709551608
18446744073709551614

2 番目の outpt は 3255859 である必要があるため、これは明らかに間違っています。

4

3 に答える 3

2

コードに符号なしと符号付きの数字が少し混じっています - 可能な限りこれを避けるようにしてください。%lluまた、signed long long で使用しようとしています-%lldこの場合は使用する必要があります。

しかし、ここにはもっと微妙な問題があります。この行で：

long long encrypt =(long long)pow((double) num,3) % 33;

powを返しますがdouble、探しているすべての精度が保証されるわけではありません。にキャストすると、数桁失うことになりますlong long。残念ながら、C は指数関数を計算するための優れた代替手段を提供していないため、自分で何かを実装するか、ライブラリを使用する必要があります (他の回答のいくつかはいくつかを示唆しています)。

自分で実装したい場合は、2乗による高速累乗に関する素晴らしい記事がウィキペディアで見つけることができます: 2乗による指数化

これらは、C でのコーディングで明らかな疑似コードを提供します。

しかし最後に、一般的に、コードは のサイズlong long、または選択したタイプによって制限されます。最終的に、大きな数の場合は、他のライブラリを使用するか、より良いアルゴリズムを見つける必要があります。この場合、累乗を計算してからモジュラスを取得します。これは、これらのライブラリを処理する必要なく、Modular Exponentation アルゴリズムが達成できることとまったく同じです。ここでウィキペディアの記事を見つけることができます: Modular Exponentiation

于 2013-09-29T02:17:49.253 に答える
0

1 つの提案は、long long のような別のデータ型を使用することでした。

3255859^3 ==  34514116960466804779
ULLONG_MAX == 18446744073709551615  // this is the minimum guaranteed

そのため、unsigned long long は機能しない可能性があります。一般に、データ型の変更には制限があります。考慮できるもう 1 つのより堅牢なアプローチは、GMP フリーを使用することです。 gmp マニュアル --

-- このサイトでも gmp をダウンロードできます。

コードスニペット：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

int main()
{
    mpz_t rop, base, exp, mod;
    mpz_init2(rop,128); 
    mpz_init2(base,128); 
    mpz_init2(exp,128); 
    mpz_init2(mod,128);
    mpz_set_ui(base, 3255859);
    mpz_set_ui(exp, 3);
    mpz_set_ui(mod, 33);
    mpz_powm_sec (rop, base, exp, mod);
    gmp_printf ("result %Zd\n", rop);    
    return 0;
}
于 2013-09-29T02:07:54.080 に答える
0

数値が作業中の型の最大サイズの半分である限り、次のようなことができます。

(((num * num) % 33) * num) % 33

一般に、暗号化の目的で実用的なものを使用するには、はるかに大きな値と、1024 ビット以上の数値を処理するための計算フレームワークが必要です。これには、既存のコードを使用するか ( GMPではなくからlibtommathお勧めします)、独自のコードを作成できます。libtomcrypt

于 2013-09-29T02:10:08.300 に答える