CでRSAアルゴリズムのための大きな整数を操作する方法は？

Question

私はRSA暗号をC言語で実装したいと思っています。今では1バイトに収まる値を暗号化できますが、セキュリティのためには小さすぎます。とq（したがってモジュラスn = pq）、および暗号化された値のサイズは機能しません。

私は自分のコードが失敗した理由を知っていると信じて：値に暗号化される値は、（必ずしもそうではありません）nは値未満である必要があり

1. を、そして
2. n = pq実際の値を私が使用している変数の型に格納することができず、代わりにオーバーフローするため、計算した値が正しくありません。

私は大きな数字（256バイト、512バイトなどにパック）を使用してCでそれらを操作することはできますか？ライブラリ（GMPなど）を使用する必要がありますか？

Answer 1

C言語には任意精度の整数（ "bignum"）算術演算がネイティブでサポートされていないので、それを提供するライブラリを使用する必要があります（GMPが一般的です）それを処理する独自のコード。

あなたは日曜大工のパスを選択した場合、私はKはビット数をあるeach array element representing a digit in base 2^k、と、いくつかの合理的に大規模なネイティブの符号なし整数型の配列（例えばuint32_tまたはuint64_t）としてあなたの番号を表す推薦基本的なネイティブ整数で表現します。

RSAの場合、0からRSAモジュラスnまでの数値ですべての計算が行われるため、負の値の表現について心配する必要はありません。必要に応じて上限値nを利用して、特定のRSAインスタンス内のすべての値に使用される基数2を^kの数字に固定することができます。これにより、明示的に格納する必要はありませんそれは各桁の配列のそばにあります。

---

ps。 "textbook RSA"は、安全な暗号化方式ではありません。意味的に安全にするには、OAEPなどの適切なランダムなパディングスキームも含める必要があります。また、パディングされているかどうかにかかわらず、通常のRSAは、モジュラスよりも短いメッセージを暗号化し、パディングによって占有された長さを引いたものがあればそれを暗号化します。より長いメッセージを暗号化するには、hybrid encryptionを使用します。最初にランダムキーで対称暗号化方式（AES-SIVを推奨）を使用してメッセージを暗号化し、RSAで暗号化します。