RSA暗号の一般的な素数生成方法

このQ&Aのポイント
  • RSA暗号における素数生成方法について紹介します。
  • RSAでは鍵の生成に、大きな素数 p, q および (p-1)*(q-1)と互いに素となる素数eを使用します。
  • 生成には時間がかかるため、一般的にはどのようにして300桁の素数を生成するか疑問に思う方も多いです。
回答を見る
  • ベストアンサー

RSA暗号の一般的な素数生成方法

一般的なRSA暗号について質問です。 RSAでは鍵の生成に、大きな素数 p, q および (p-1)*(q-1)と互いに素となる素数eを使用します。 ただ、p, qの一般的に使用される桁数は1024bit(300桁超)であるため、素数の生成に非常に大きな時間がかかってしまいます。 e は3か65537を使用することで生成のための計算を省くことができますが… RSAで暗号鍵を生成する際に300桁もの素数を毎回計算して生成するのは時間がかかりすぎるため現実的ではないと思いますが、実際にはどのようにして300桁の素数を生成しているのでしょうか。 もしくは、計算済みの素数リストや固定の値を使用しているのでしょうか。 (後者はあり得ないとは思いますが…) 宜しくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.1

詳しくはリンクしたページを見ていただきたいのですが、2種類の方法があります。 ひとつはランダムに値をとって、確率的に素数であることを判定する方法で、もう一つはすでにある素数からそれよりも大きな別の素数を作り出す方法です。どちらの場合も乱数によって値を選ぶところがあり、暗号に使うための乱数生成器で乱数を作り出せばRSAなどに十分使える素数が作れると思います。 ちなみに、前者でなぜできるかというと、素数定理によって、十分大きな桁数の場合、ランダムに値を取ると素数になる可能性が高いことが知られています。素数でないことを判定するアルゴリズムは既にいくつかあるので、それを何度も適用することで素数である可能性が十分高い数を見つけ、それを使えます。 計算済みの素数リストや固定の値というのはDiffie-Hellman key exchangeなど素数が公開情報であっても構わない場合には使えそうですが、素数を秘密情報としないといけない場合にはまず使えないと思います。計算済みの場合だとそれが他の人に何らかの方法で知られたら安全ではなくなりますが、それを誰かが計算して与えるとしたら、渡した人は秘密にすべき素数を知っていることになると思います。また、いくつかリストがあってそこから選ぶ場合でも、長いリストを渡すことは現実的ではないと思うので、やはり鍵が取りうるパターンが限定されていて、安全とはいえないでしょう。 http://www.ipa.go.jp/security/fy14/crypto/prime_num/invest.pdf

関連するQ&A

  • RSA暗号

    どのトピックかがいまいちわからないのでこのトピックに質問を載せさせて頂きます。 いま、大学の課題でRSA暗号をパソコンで実装する という課題に取り組んでいます。 2桁以上の素数を選んで、その素数から暗号化鍵と復号化鍵を選んでアスキーコードを暗号化するという初歩的なものなので、実用性は全くありませんが… プログラムはできたのですが 暗号化鍵と復号化鍵を生成して 暗号化を行って複合化を行うと 元の平文に戻らない鍵のペアがあるらしいのです。 そういうときってあるのでしょうか?

  • RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵

    RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵eが23のとき、復 号鍵dを求める考え方の手順を教えてください。さらにこれらを使って平文2を暗号化するにはどのようにすればいいでしょうか。

  • RSAのプログラミング

     卒論でRSAをC++でプログラミングしています。  最初に選ぶ大きな素数p、qにより法鍵Nを作るとしたとき、p、qはどれくらい大きな数でなければなりませんか?  また、公開鍵は素数である必要はありますか?指数鍵もどのくらい大きな数である必要がありますか。  (p、q、公開鍵を一桁代の数字で計算すると、秘密鍵がマイナスにあるときがあったので)  また、「こんな暗号技術もC++で作ってみたら?」というのがあれば教えてください。

  • RSA暗号についてです。

    RSA暗号についてです。 秘密鍵(p,q)=(7,17)の公開鍵の求め方、解答がわかりません。 よろしくおねがいします。 この質問に補足する

  • iアプリでRSA暗号を実装したい

    今、iアプリでRSA暗号を実装しています。 しかし、p=512bit,q=512bit つまり、n=1024bitの鍵を用いるためにどうすればいいのでしょうか? 1024bitということは10進数で300桁を超えるため、困っています。 知っていましたら教えてください。

    • ベストアンサー
    • Java
  • RSA暗号について教えてください

    RSA暗号がどのようなものか、また仕組みについて教えて下さい。調べても分からなかったので、できるだけわかりやすく教えて下さい。また、RSA暗号を用いて、二桁程度の素数を二つ使って暗号の仕方、また戻し方の例を教えてください。お願いします。

  • RSA暗号の解き方

    素数 P=5 Q=11 であり、N=55となります。公開鍵e=3と定義します。一般解d=27となります。 さらに、自然数m=20となります。 (1)自然数mを公開鍵(e,N)を使って暗号Yを求めてください。 (2)さらに、秘密鍵(d,N)を使って暗号Yを復号化し、mと一致することを確認してください。

  • RSA暗号化の方法(具体的に)

    C++で、あるファイルを暗号化するプログラムを作成しようと思っています。 暗号はRSAで、と思っていますが、どのようにすればいいのか分かりません。 暗号自体のアルゴリズムは理解しているのですが、 「具体的に」どうすればいいのか教えて欲しいのです。 「文字」とか、そういう単位がなくて、単なるディスクファイル、またはメモリ上の bit列があったときに、それをどうやって暗号化するか、また復号するか。 鍵が分かったとして、bit列のどこからどこまでを1つの単位として計算するのか。 その暗号化単位は、公開鍵だけで判断できるのか。 素数で割った余りなので、1つの数字としてみたときに素数より小さい数でないと だめなことは分かります。 もしかしたら、このようなデータの暗号化は、他のアルゴリズムを 使用した方がいいのかもしれませんが、暗号について あまり詳しくないので、どうしたらいいのか分かりません。 ネットで調べた内容では、アルゴリズムは理解できても、 対象としているデータで、実際どうやるのか分かりませんでした。 よろしくお願いします。

  • 学校でRSA暗号について勉強して分からないところがありましたので質問し

    学校でRSA暗号について勉強して分からないところがありましたので質問します。 暗号文の作成者をAさん、復号者をBさんとします。 Aさんは暗号文と公開鍵{e,n}を一般に公開しますよね? 暗号文を復号化するには秘密鍵が必要ですが、Bさんはeとnしか分からない(一般の人と得られる情報が同じ)のにどうやって秘密鍵を作成するのですか?nのもとになっている2つの素数がわからないことには秘密鍵が作成できないとおもうのですが… RSA暗号はnの素因数分解が計算量的に困難だから安全なんですよね?Bさんはどうやって2つの素数を特定するのでしょうか? 教えてください。

  • RSA暗号で初めに選択2つの数について

    RSA暗号で初めに選ぶ数(p,q)で、2つの内どちらかが合成数であるとき、復号化がうまくいかない場合があります。どうして復号化がうまくいかなくのかわかりません。教えてください。