- ベストアンサー
RSAのアルゴリズムについて教えてください
RSAのアルゴリズムを http://www.maitou.gr.jp/rsa/rsa10.php で勉強中です。 このHPにある 『全ての数はなんと11 乗又は 21 乗すると自分自身に戻っているでしょう！ このように、２つの素数（ P, Q とします）をかけた数を法とする世界では、 全ての数が自分自身に戻るべき乗数が必ず存在します。そして、これが何乗 なのかは、最初の２つの素数( P , Q ) によって決まります』 という部分について、理屈が分かりません。。。 この部分の理屈について教えていただけませんか？ または、解説してあるHPや本を教えて頂けませんか？ よろしくお願いします。
- fugafugahogehoge
- お礼率57% (161/281)
- ネットワーク
- 回答数3
- ありがとう数4
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
スマートなやりかた (笑) 重要な定理は, Fermat の定理と中国剰余定理 (Chinese Reminder Theorem, CRT) の 2つ. これらだけで OK. CRT から「法33 の剰余系」は「法3 の剰余系」と「法11 の剰余系」の対で表すことができます. なので, そこの表の全ての数値に対し「3 でわった余りと 11 でわった余りの対」を書き込んでみてください. Fermat の定理を念頭におけば規則性が見えてくると思います.
お礼
ありがとうございます。 Fermat の定理と中国剰余定理ですね。 調べてみます。
- ymmasayan
- ベストアンサー率30% (2593/8599)
これは(ｎ^11)/33の余りと(ｎ^21)/33の余りががどちらもｎと等しいといっているのですが この部分の理解は出来ていますか。 あとは確かめてみるだけですね。 スマートにやるか力仕事でやるかは自由です。
お礼
スマートなやり方で考えてみます。
関連するQ&A
- RSAアルゴリズムの8つのパラメータに関して
RSA暗号の勉強をしています。 RSAアルゴリズムには、下記の8つのパラメータがあるという事を知りました。 ・Dパラメータ ・DPパラメータ ・DQパラメータ ・Exponentパラメータ ・InverseQパラメータ ・Modulusパラメータ ・Pパラメータ ・Qパラメータ http://msdn2.microsoft.com/ja-JP/library/fh3dd3wt.aspx このうち、P,Q,Modulas,Exponent,Dに関しては、通常のRSAの説明に 現れる物であろうと予想がつくのですが、残りの3つ 「DP」「DQ」「InverseQ」が何を意味しているのか分かりません。 これらをキーワードとして検索してみましたが、説明が記載されている ものがありませんでした。 ご存知の方が見えましたらお教えください。
- ベストアンサー
- ネットワーク
- RSAのプログラミング
卒論でRSAをC++でプログラミングしています。 最初に選ぶ大きな素数ｐ、ｑにより法鍵Nを作るとしたとき、ｐ、ｑはどれくらい大きな数でなければなりませんか？ また、公開鍵は素数である必要はありますか？指数鍵もどのくらい大きな数である必要がありますか。 （ｐ、ｑ、公開鍵を一桁代の数字で計算すると、秘密鍵がマイナスにあるときがあったので） また、「こんな暗号技術もC++で作ってみたら？」というのがあれば教えてください。
- 締切済み
- ネットワーク
- RSA暗号で初めに選択２つの数について
RSA暗号で初めに選ぶ数（p,q）で、２つの内どちらかが合成数であるとき、復号化がうまくいかない場合があります。どうして復号化がうまくいかなくのかわかりません。教えてください。
- ベストアンサー
- 数学・算数
- RSA暗号の一般的な素数生成方法
一般的なRSA暗号について質問です。 RSAでは鍵の生成に、大きな素数 p, q および (p-1)*(q-1)と互いに素となる素数eを使用します。 ただ、p, qの一般的に使用される桁数は1024bit（300桁超）であるため、素数の生成に非常に大きな時間がかかってしまいます。 e は3か65537を使用することで生成のための計算を省くことができますが… RSAで暗号鍵を生成する際に300桁もの素数を毎回計算して生成するのは時間がかかりすぎるため現実的ではないと思いますが、実際にはどのようにして300桁の素数を生成しているのでしょうか。 もしくは、計算済みの素数リストや固定の値を使用しているのでしょうか。 （後者はあり得ないとは思いますが…） 宜しくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- RSAのeの実際値について
RSAの公開指数eは固定値(主に65537)でもセキュリティ的な問題は 発生しないとの事ですが、それはなぜでしょうか？ 要は、eから2つの素数pとqを推測する事が難しいので、eが固定値 でも問題ないと言うことでしょうか？ よろしくお願いします。
- ベストアンサー
- ネットワーク
- RSAのCプログラム
何かC言語で書かれたRSAの一連の流れを示したものはありますか？Googleでプログラムを探しているのですがどうしてもみつかりません。プログラムとして、単純なものでよいです。ある平文に対して、はじめに２つの素数を見つけ(p,q)、鍵を生成し、暗号化をして、それを復号するというような一連の流れをC言語で見てみたいのでプログラムがありましたら教えてください。お願いします。
- ベストアンサー
- ネットワーク
- iアプリでRSA暗号を実装したい
今、iアプリでRSA暗号を実装しています。 しかし、p=512bit,q=512bit つまり、n=1024bitの鍵を用いるためにどうすればいいのでしょうか？ 1024bitということは10進数で300桁を超えるため、困っています。 知っていましたら教えてください。
- ベストアンサー
- Java
- RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵
RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵eが23のとき、復 号鍵dを求める考え方の手順を教えてください。さらにこれらを使って平文2を暗号化するにはどのようにすればいいでしょうか。
- ベストアンサー
- ネットワーク
- RSA暗号の中国剰余定理についておしえてください.
RSA暗号の中国剰余定理についておしえてください． N=77 = 7×11, p1=7, p2=11 d1 = d mod (p1-1) = 43 mod (7-1) = 1 d2 = d mod (p2-1) = 43 mod (11-1) = 3 m1 = c^d1 mod p1 = 48^1 mod 7 = 6 m2 = c^d2 mod p2 = 48^3 mod 11 = 4^3 mod 11 = 9 連立方程式 m = 6 mod 7 m = 9 mod 11 となり p1=7とp2=11は共に素数であるので互いに素 q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2 /// q2=p1-^1 mod p2 = 7^-1mod 11=8 //// これを用いて m=(m1×p2×q1 + m2×p1×q2) mod p1p2 = (6×11×2 + 9×7×8) mod 77 = (132+504) mod 77 = 20 平文 m = 20 とあるのですが，q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2と q2=p1^-1 mod p2 = 7^-1mod 11=8の部分でどうして2と8になるのかがわかりません．1時間くらい悩んでいるのですが見当がつきません．教えて下さい．＞＜
- 締切済み
- その他([技術者向] コンピューター)
お礼
ありがとうございます。 教えて頂いたホームページ読んでみます。