• 締切済み

modの計算方法について

下記ホームページで紹介されているmodの計算方法について教えてください。 http://c4t.jp/introduction/cryptography/cryptography04.html (1)「素数」を法とする世界では、Xn mod 素数＝X という、元の数字と答え（X）が共に同じとなる「n」の値を「素数」から計算することができます。というのがありますが、例をあげて説明していただけないでしょうか？ (2)RSA暗号の概要で暗号分456はどのように計算するのでしょうか？ よろしくお願いします。

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

公開鍵暗号系だと, 数論とか代数的構造とかを抑えとかないとつらいかなぁ.... (1) p を素数とすると, Fermat の定理から x ≡ 0 (mod p) でなければ x^(p-1) ≡ 1 (mod p) です. このことを使えば簡単でしょう. (2) パラメータが足らないので計算できません.

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ＭＯＤ２５（２５を法とする剰余）の計算

    エクセルでＭＯＤ２５（２５を法とする剰余）の計算をします。 （記号）３∧ｎで３のｎ乗をあらわすものとする。 （したいこと）ｍｏｄ（３、25），３∧２=9、３∧３=２７、―――、３∧２０、―――、３∧２４に対して、 ｍｏｄ（３、25）～ｍｏｄ（３∧２４、25）までの値を求めたいのですが、～ｍｏｄ（３∧２0、25）以降の値がおおきすぎてエラーとなります。どうすればいいのでしょうか。

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

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

  • modを使用した平方根の求め方

    解き方が解からない問題があります。 どれだけ考えても解き方がわからないので、どなたかわかる方教えてください。 【解き方が解からない問題】 大きな素数の積n=pqが与えられた時、nを素因数分解するのは非常に難しい。 整数ｍと整数ｙ(<ｍ)が与えられた時y=ｘ2(xの二乗) mod mなる整数解xが存在すれば、yは mod mで平方剰余であるという。 xを mod mでのyの平方根という。 mが素数7の時、 12(1の二乗の事です。二乗の書き方がわからなくて・・・)≡1 (mod 7) 、 22(2の二乗) ≡ 4 (mod 7) 32(3の二乗)≡2 (mod 7) 、 42(4の二乗) ≡ 2 (mod 7) 52(5の二乗)≡4 (mod 7) 、 62(6の二乗) ≡ 1 (mod 7) となるので、1、2、4が平方剰余で、各平方剰余には２個の平方根がある。 mが二つの素数の積の場合、４個の平方根がある。 ここまでが参考書に載ってる説明です。 ここから私がわからない問題です。 102(10の二乗) mod 77＝23 n = 77 の素因数7と11から素因数の知識を利用してZのmod nでの平方根Sを計算する。 S2(Sの二乗) ≡ 23 mod 7 S2(Sの二乗) ≡ 23 mod 11 上の２つを解いて、mod 77での４つの平方根10、32、45、67を得る。 この２つの式から、何をどうやって計算して、４つの平方根10、32、45、67が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。

  • 可換な指数関数

    　RSA暗号で使われるh(x,y) = x^y mod n という指数関数が入れ替え可能な(h(h(x,y1),y2) = h(h(x,y2),y1))一方向アキュムレータだととある記事に書いてあったので、それに従って以下のような関数ｆを例に計算してみましたが、f(f(f(x,3),5),7) != f(f(f(x,5),7),3) でした。可換ではないように見えるのですが、どこが間違っているのか教えて下さい。 n = 47 * 59 (47 = 2 * 23 + 1, 59 = 2 * 29 + 1) 　f(x,y) = x^y mod n 　よろしくお願いします。 　

  • 多倍長演算での累乗

    ElGamal暗号のプログラムをjavaで書いているのですが、累乗の計算で困っています。 RSA暗号で出てくる「a^b mod p」の場合はBigIntegerを使うと「a.modPow(b,p)」ですよね。 しかし今回使う式は「a*(b^p-x-1) mod p」といったような式です。 ということで a.miltiply.b.pow(p.subtract(x).subtract(x)).mod(p) としたんですが、コンパイルしてエラーが出たので調べたところ、指数部分はint型でないとpow()が使えないことを知りました。 しかし、この式の指数部分が1024ビットなので32ビットのint型には変換できません。 int型以外の値で累乗するにはどうしたらいいのでしょうか？

  • 原始根をつかって合同式を解く計算過程について

    2が11の原始根で有る事をつかって3X^3 ≡ 2(mod 11)を解きたいのですが計算途中でつまずいてしまいます。 φ(11) = 10 2^10 = 1(mod 11) ind_2 (3X^3) ≡ ind_2 2 = 1(mod 11) ind_2 (3X^3) ≡ ind_2 3 + ind_2 X^3 ≡ 8 + 3 * ind_2 X (mod 11) 8+3*ind_2 X ≡ 2(mod 11) ここまでわかったのですがここから先の計算がわかりません。どうやれば X ≡　n1, n2, n3 ,.... (mod 11)の形に持っていけるのでしょうか？

  • a mod b = x、c mod d = x

    a mod b = x c mod d = x (a,b,c,dは正の整数) という式が与えられ aとbとdの数値が決定している場合に cの値を求める事は可能でしょうか？ ただしこのとき 計算途中にxの値を使わずcの値を求めたいのです。(瞬間的にでもメモリ(レジスタ含む)にその数値を書きたくない為) 例えば 49999 % 800 = 399 c mod 1560 = 399 この場合cは50319や51879等あると思いますが49999に近い値が望ましいです。 不可能な場合でも理由をご回答頂ければ幸いです。 宜しくお願いいたします。

  • 素数判定アルゴリズム内の剰余計算

    今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか？

  • NSAによる電文の解読？

    NSAがアシュロン（阿修羅の兄弟か？）とかいうシステムで世界中の市民の通信を傍受しているようです。 しかし、RSA方式の公開鍵暗号で暗号化してある私の電文はさすがのNSAも解読でいきないですよね？ RSAで暗号化した私の電文を解読するには、桁数の大きな素数を発見する必要があって、そのためには最高速のスーパーコンピューターを使っても何年もの計算時間が必要なんですよね？ 上記の理解が正しいかどうか教えてください。 なぜ、NSAの傍受で通信のコンテクストがバレルと騒いでいるのか理解できません。

  • RSA暗号化の方法（具体的に）

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

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する