疑似乱数生成器

RSA暗号化(C = M^e (mod N) ただしMは入力,出力はC )を使った疑似乱数生成を行いたいが、下記のことが分からない。

f:{0,1}^n → {0,1}^n を一方向置換とする。nビットのシード乱数 r (2進数)が与えられたとき、rをfに通して置換してnビットの乱数に変換したい。
RSA暗号化の式は自然数が入力され、自然数で出力される。シード乱数を一度10進数に直して、RSA暗号化の式に通すと大きい値となって返ってくる。これをまた2進数に直すとnビットではなく、もっと大きいビット数になって返ってきてしまう。nビットのシード乱数からnビットのまま置換するにはどのように式を使うのか？

質問者からの補足コメント

• nビットの法のNと考えているということでしょうか？
  先述の式はRSA暗号なので、法であるNは2つの大きい素数の積になるはずです。仮にnビットが小さい場合、Nも小さくなり、明らかにセキュリティに問題が出てしまいます。ですので、nビットでNはとらないのではないかと考えていたのですが、、やはりnビットで取るしかないのでしょうか？
  
  法Nを入力の大きさに関係せずに決めると仮定して、次のように計算してみたのですが、これはいかがですか？
  
  M^e (mod N) %2 →1か0
  (M^e mod N)^e (mod N) %2 →1か0
  ((M^e mod N)^e (mod N))^e (mod N) %2 →1か0
  これをn回(nビットのn)繰り返す

  No.1の回答に寄せられた補足コメントです。 補足日時：2023/01/05 21:05

No.3 回答者： stomachman 回答日時： 2023/01/06 14:39

No.2へのコメントについてです。

> 目標：暗号にも使えるような疑似乱数生成器をつくる

　そもそも、なぜ自作したいんでしょうか。もし実用するためであるなら、何ビットであろうと既存のアルゴリズムで作れますが、それだと何が不都合なんですか？

> →まずはnビットのシード乱数からn+1ビットに伸ばしたい
> →そのためにnビットのシード乱数をnビットの乱数列(シード乱数とは異なる乱数列)に置換する必要がある

　「シード乱数」なるコトバは意味がわかりませんが、もしかして「nビットの擬似乱数生成器を一つ用意しておいて、その出力値を何らかの関数でn+1ビットの数値に変換する」ってことでしょうか。だとすると、その関数が出力するn+1ビットの数値は、どうしたって高々2^n通りしかない。生成される数列には、n+1ビットで表せる数値のうちの高々半分だけしか現れず、他は決して出てこない。それは「n+1ビットの擬似乱数」ではないですね。
　また、「まずは」とおっしゃる意図も全く分かりません。仮にその「まずは」ができたとすると、それからどうするお積りなんでしょうか？

> RSA暗号化の式を用いて

　RSA暗号化は関数です。すなわち、ある平文を暗号化した結果（暗号文）が複数ある、ということはありません。さらに、これは逆関数を持つ関数ですから、異なる平文が同じ結果（暗号文）になる、ということもない。したがってnビットのあらゆる平文2^n通りを暗号化した結果（暗号文）は丁度2^n通りあります。その暗号文をn+1ビット分だけ切り取ったものは当然、2^n通り以下、すなわち、高々2^n通りです。

> nビットのシード乱数(入力)をビット数は変えずに置換したい

　「n+1ビットに伸ばしたい」という話と、「ビット数は変えずに」という話とがどう関係しているのやら、全く分かりません。

No.2 回答者： stomachman 回答日時： 2023/01/05 22:36

No.1へのコメントについて。

> nビットの法のNと考えているということでしょうか？

　何のことやら全くわかりません。日本語で書いて欲しいです。
ま、「法」という用語をご存知のようです。でしたら、「mod N」とはそのまんま「Nを法とする」って意味だということは、お分かりなんでしょうね？

> 明らかにセキュリティに問題

さっぱりわからんです。ええと、ご質問は疑似乱数生成の話ですよね？ 一体何がどう「セキュリティ」と関係するんでしょう？

> nビットでNはとらないのではないか
> nビットで取るしかないのでしょうか？

全く意味不明です。「とる」とは何のこと？

> 法Nを入力の大きさに関係せずに決める

「入力」とおっしゃるのがMのことなら、そりゃそうでしょう。
そもそも計算のたびにNを変えるなんて話はありましたっけ？

> %2

って何ですか？（もしかして「2で割ったあまり」ってことでしょうか？だとしたらそれは mod 2の計算ですが、だったらなぜ "mod 2" と書かないで"%2"？）

> これをn回(nビットのn)繰り返す

　ご質問の最初にお書きの計算とは関係ないようですが、さて、そんな計算を繰り返して、その結果が何を意味するのか、その結果をどうするつもりなのか、何より、一体何をしたいんだか、まるでわかりません。

この回答へのお礼

回答ありがとうございます。質問者さんのおっしゃることは理解できますし、補足に対する返答もおっしゃる通りです。こいつは何を言っているのだろうと思ったでしょう。分かりにくい文章で申し訳なかったです。目標なども明確に書くべきでした。

目標：暗号にも使えるような疑似乱数生成器をつくる(プログラミング言語pythonを使用して作成する)

→まずはnビットのシード乱数からn+1ビットに伸ばしたい
→そのためにnビットのシード乱数をnビットの乱数列(シード乱数とは異なる乱数列)に置換する必要がある

質問：RSA暗号化の式を用いて、nビットのシード乱数(入力)をビット数は変えずに置換したいが、この式を実際にどのように使うか決めかねている。どのように使うと「良い」疑似乱数生成器になりそうか意見が欲しい。単純にシード乱数と同じビット数で表せる数を法として出力すると、たしかにビット数を変えずに簡単に置換できるが、「良い」疑似乱数生成器は作れない。

色々な式の使い方を試して、実際にプログラムを動かして実験するので、このような式の使い方はどうか？と提案があったらしてみてください。

お礼日時：2023/01/06 12:13

No.1 回答者： stomachman 回答日時： 2023/01/05 09:39

お書きのやり方で生成される数列が擬似乱数として使い物になるのかどうか、また計算が速くできるか、という話はここでは置いといて、計算のやり方そのものについて。

　
　"mod N"の意味は「Nで割った余り」ってことですから、コタエがN以上の値になることはない。なのでNがn bitで表せるなら、出力も必ずn bitで表せます。

　例えばM^3 mod N (M＜N)を計算するのに、(M×M×M mod N) とやる代わりに((M×M mod N)×M mod N)とやっても同じで、こうするとかけ算「×M」の結果は毎回、高々2n bitで表されるわけです。
　ついでに、Mが素数ではなくて
　　M = a b
と分解できる場合には
　　M^e mod N = (a^e mod N)(b^e mod N) mod N
です。

　いずれにせよ、mod Nの世界で計算をやるのは数学的には「有限体」という代数系の計算をやっていることになり、その性質は広く利用されています。例えば符号理論。

　ちなみに、大昔に使われていた擬似乱数生成法である「線形合同法」(A, B, Nを定数として (A M + B) mod NでMの次の数を生成する。擬似乱数としての性能が悪く、廃れた。）のたいていの実装では、N=2^n にすることによって、mod Nの計算を「n桁でかけ算足し算をやり、オーバーフローした上位の桁は単に無視する。」で済ませて、mod Nの計算を不要にしていました。現在使われている擬似乱数生成法「メルセンヌ・ツイスター」の実装でも、mod Nの所には同じ手が使われています。