c++ - 非常に大きな整数を処理するC++

Question

私は暗号化/復号化にRSAアルゴリズムを使用しています。ファイルを復号化するには、かなり大きな値を処理する必要があります。より具体的には、

P = C^d % n
  = 62^65 % 133

さて、それは本当に悪い計算をしている唯一の計算です。Matt McCutchenのBigIntegerライブラリを使用してみましたが、リンク中に次のような多くのコンパイラエラーが発生します。

encryption.o(.text+0x187):encryption.cpp: undefined reference to `BigInteger::BigInteger(int)'

encryption.o(.text+0x302):encryption.cpp: undefined reference to `operator<<(std::ostream&, BigInteger const&)'

encryption.o(.text$_ZNK10BigIntegermlERKS_[BigInteger::operator*(BigInteger const&) const]+0x63):encryption.cpp: undefined reference to `BigInteger::multiply(BigInteger const&, BigInteger const&)'

そのため、RSAアルゴリズムから出力される非常に大きな整数を処理するための最善の方法は何でしょうか。

変数をdoublelongとして宣言する可能性があると聞いたので、...

long long decryptedCharacter;

しかし、格納できる整数の大きさは正確にはわかりません。

たとえば、devC++を使用して次のプログラムをコンパイルして実行しようとしています。

#include iostream

#include "bigint\BigIntegerLibrary.hh"

using namespace std;

int main()
{
    BigInteger a = 65536;
    cout << (a * a * a * a * a * a * a * a);
    return 0;
}

それから私はそれらのエラーを受け取ります。

デレク、私はBigIntegerLibrary.hhファイルを含めることで、コンパイラーが使用する必要なすべてのファイルを調べてコンパイルするだろうと思いました。

リンクエラーを解決するには、上記のプログラムをどのようにコンパイルしてみればよいですか？

score 13 · Accepted Answer

Tomek さん、BigInteger コードに正しくリンクしていないようです。新しいライブラリを探すのではなく、この問題を解決する必要があると思います。私はソースを見て、BigInteger::BigInteger(int)最も明確に定義されています. 一見すると、他の人も同様であることがわかります。

発生しているリンクエラーは、BigInteger ソースのコンパイルを怠っているか、リンク時に結果のオブジェクトファイルを含めることを怠っていることを意味します。BigInteger ソースは「cpp」ではなく「cc」拡張子を使用することに注意してください。これらのファイルもコンパイルしていることを確認してください。

score 12 · Accepted Answer

gmpを使用することをお勧めします。これは、任意の長い整数を処理でき、適切な C++ バインディングを備えています。

現在のハードウェア/ソフトウェアのロングロングは64ビットであるため、unsignedは(2**64)-1 == 18446744073709551615までの数値を処理できます。これは、RSAで処理する必要がある数値よりもかなり小さいです。

score 3 · Accepted Answer

RSAを学校の課題などとして実装していない場合は、crypto++ライブラリhttp://www.cryptopp.comを参照することをお勧めします。

暗号のものをひどく実装するのはとても簡単です。

score 3 · Accepted Answer

long longのサイズを確認するには、次のことを試してください。

#include <stdio.h>

int main(void) {
    printf("%d\n", sizeof(long long));

    return 0;
}

私のマシンでは8を返します。これは、2^64の値を格納できる8バイトを意味します。

score 3 · Accepted Answer

RSA の実装を保護するには、大きな数だけではありません。単純な RSA 実装は、サイドチャネル、特にタイミングを介して個人情報を漏洩する傾向があります (簡単に言えば、計算時間は処理されたデータに依存するため、攻撃者は秘密鍵ビットの一部、場合によってはすべてを回復できます)。優れた RSA 実装では、対策が実装されています。

また、べき乗剰余以外にも、パディングビジネス全体があり、概念的には難しくありませんが、すべての I/O および解析コードと同様に、微妙なバグの余地があります。書くのが最も簡単なコードは、他の誰かによってすでに書かれているコードです。

もう 1 つのポイントは、RSA コードを起動して実行すると、「使用したい秘密鍵が RAM ではなくスマートカードにある場合」など、拡張機能やその他の状況を想定し始める可能性があることです。一部の既存の RSA 実装は、実際にはそれを処理できる API です。Microsoft の世界では、Windows に統合されているCryptoAPIを検索します。また、Firefox ブラウザーが SSL に使用するNSSも参照してください。

要約すると、大きな整数から RSA 準拠の実装を構築することはできますが、これを正しく行うのは通常のように思われるよりも難しいため、既存の RSA 実装を使用することをお勧めします。

score 3 · Accepted Answer

RSA の場合、bignum ライブラリが必要です。数値が大きすぎて、64 ビットの長さに収まりません。私は大学の同僚に、RSA を実装する任務を与えられ、独自の bignum ライブラリを構築したことがあります。

たまたま、Python には bignum ライブラリがあります。bignum ハンドラーの作成は、コンピューターサイエンスの課題に収まるほど小さいですが、重要なタスクにするのに十分な落とし穴があります。彼の解決策は、Python ライブラリを使用してテストデータを生成し、bignum ライブラリを検証することでした。

他の bignum ライブラリを取得できるはずです。

または、Python でプロトタイプを実装してみて、十分に高速かどうかを確認してください。

score 3 · Accepted Answer

これが私のアプローチです。これは、必要なスペースを削減する二乗+モジュラー指数を使用した高速指数を組み合わせています。

long long mod_exp (long long n, long long e, long long mod)
{
  if(e == 1)
  {
       return (n % mod);
  }
  else
  {
      if((e % 2) == 1)
      {
          long long temp = mod_exp(n, (e-1)/2, mod);
          return ((n * temp * temp) % mod);
      }
      else
      {
          long long temp = mod_exp(n, e/2, mod);
          return ((temp*temp) % mod); 
      }
  }
}

score 2 · Accepted Answer

GMPライブラリを試してみたいと思います。これは堅牢で、十分にテストされており、このタイプのコードによく使用されます。

score 2 · Accepted Answer

Openssl には、使用できるBignumタイプもあります。私はそれを使用しましたが、うまく機能します。必要に応じて、C++ や Objective-C などの oo 言語で簡単にラップできます。

https://www.openssl.org/docs/crypto/bn.html

また、ご存じない場合は、この形式 x^y % z の方程式の答えを見つけるには、累乗剰余と呼ばれるアルゴリズムを調べてください。ほとんどの crypto または bignum ライブラリには、この計算専用の関数があります。

score 1 · Accepted Answer

long intは通常64ビットであり、これほど大きな整数を処理するにはおそらく十分ではありません。おそらく、ある種のbigintライブラリが必要になります。

StackOverflowに関するこの質問も参照してください

score 1 · Accepted Answer

コンパイラのドキュメントを確認してください。一部のコンパイラには、サイズを指定する__int64などのタイプが定義されています。多分あなたはそれらのいくつかを利用できるようにしています。

score 1 · Accepted Answer

注意: __int64 と long long は非標準の拡張機能です。どちらも、すべての C++ コンパイラでサポートされるとは限りません。C++ は C89 をベースにしています (98 年に登場したため、C99 をベースにすることはできませんでした)。

(C は C99 以降、'long long' をサポートしています)

ところで、64 ビット整数がこの問題を解決するとは思いません。

score 1 · Accepted Answer

LibTomCryptライブラリを暗号化のニーズに使用して、多くの成功を収めてきました。高速で無駄がなく、ポータブルです。RSA を実行することも、必要に応じて計算を処理することもできます。

score 0 · Accepted Answer

biginteger ライブラリの使用に問題があるという事実は、それが悪いアプローチであるという意味ではありません。

long long を使用することは、間違いなく悪いアプローチです。

他の人が言ったように、すでにbigintegerライブラリを使用することはおそらく良いアプローチですが、これらのエラーを解決するために、言及されたライブラリを使用する方法の詳細を投稿する必要があります.

score 0 · Accepted Answer

0

RSA の実装を書いたとき、私は GMP を使用しました。

于 2009-05-18T19:26:45.103 に答える

c++ - 非常に大きな整数を処理するC++

15 に答える 15

Related

Reference