全単射写像拡大による擬似乱数生成法
【課題】現在の暗号化の安全性は数学的な問題解決のための計算の膨大さによっているが、一方向性で保証されていたハッシュ関数の脆弱性が指摘されており、計算の容易さと一方向性を両立させる理想的な擬似乱数を生成する。
【解決手段】ビット情報を拡大し元の情報の全単射写像を作り疑似乱数化する。例えば、一つの２ビット値をもう一つの２ビット値をもとに換字と並べ替えで置換したものはこれらの組み合わせをＥＸＯＲ演算した値と共にベクトルとも云えるパターンを持つ。このベクトルを選択して並べることで原像よりも拡大された全単射写像を作ることが出来る。また、変換することなく原像の情報を取り出し二重に連結することでも、原像よりも拡大された全単射写像を作ることが出来る。
【解決手段】ビット情報を拡大し元の情報の全単射写像を作り疑似乱数化する。例えば、一つの２ビット値をもう一つの２ビット値をもとに換字と並べ替えで置換したものはこれらの組み合わせをＥＸＯＲ演算した値と共にベクトルとも云えるパターンを持つ。このベクトルを選択して並べることで原像よりも拡大された全単射写像を作ることが出来る。また、変換することなく原像の情報を取り出し二重に連結することでも、原像よりも拡大された全単射写像を作ることが出来る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は擬似乱数を生成するものであり、その一方向性から暗号化技術に関連する。
【背景技術】
【０００２】
本発明のようにビット情報を換字と並べ替えで置換することはシャノンのＳＴＮ構造と呼ばれ、古くはＤＥＳのＳボックスを作成することに用いられているものであって
【特許文献１】国際出願番号 ＰＣＴ／ＪＰ２００５／００８６４６と
【特許文献２】特願２００９−２６５２８６には会員のパスワードをネットワーク運営者に対して秘密にしたまま会員本人と認証申請者の個人的同定できることが示されており
【特許文献２】には擬似乱数発生器についての言及がされていて、その説明に本明細書と同様の図表が用いられているものの、本発明は擬似乱数生成法であって
【特許文献１】や
【特許文献２】と異なる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
現在の暗号化の安全性は素因数分解や楕円関数など効率的な解法が見つかっていない数学的な問題解答のために費やされるコンピュータ的時間量の膨大さによる一方向性で保証される。
一方、一方向性ではないかと予想されていたハッシュ関数の多くはその脆弱さが指摘され、その安全性は数学の進歩と反比例すると言える。
計算の容易さと一方向性を両立させるには理想的な擬似乱数を作ることが必要である。
【課題を解決するための手段】
【０００４】
本発明は、ビット情報を拡大し元の情報の全単射写像を作り疑似乱数化するものである。
まず最も簡単なものとして、６ビット情報を変換することなしに８ビットの全単射写像に拡大して下に示す。
２ビットを１単位として４つの変数Ａ、Ｂ、Ｃ、Ｄのそれぞれが１ビットの情報を持つこととしてＡＢ、ＣＤの２つのブロックとする。
それぞれ１ビットの情報を持つ変数ＹとＺを追加して６ビット情報とし、ＡＢ、ＣＤのブロックに付け加えられる。
ＡＢＹＺの値の４ビットとＣＤＹＺの４ビットの計８ビットをＡＢＹＺＣＤＹＺの順に並べたものが表１である。
Ｙ、Ｚ、ＡとＢ、Ｃ、Ｄの組み合わせは６４通りあって、行見出しにＹＺＡの値を、列見出しにＢＣＤの値を示す。
表１の各値はＹＺＡＢＣＤの値と一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
表２は表１の各値を１６進数で表現したものである。
【表１】
【表２】
因みにＹＺＡＢＣＤに加えて変数Ｗ、Ｘがそれぞれ１ビットの情報を持つこととして計８ビットの情報を変換することなしに１６ビットの全単射写像に拡大するには先のＡＢＹＺＣＤＹＺを２ビットずつに区切ってＡＢＷＸＹＺＷＸＣＤＷＸＹＺＷＸというように並べればよい。
つまり写像を２ビットずつに分割し分割１単位毎に２ビットを付け加えて連結することであり元の情報のビット数が増えるごとにこれをを繰り返す。
【０００５】
下の表３は変数ａ、ｂ、ｃ、ｄのそれぞれが１ビットの情報を持つこととして、それらの組み合わせをＥＸＯＲ演算したものである。
【表３】
ａ、ｂ、ｃ、ｄの各ビットを取り出し、並べ替えてＥＸＯＲ演算することによって、異なるパターンでａ、ｂ、ｃ、ｄ各値に対応する１１の変換がある。
それらをベクトルということにして１から１１の添え字をつけてベクトルＶ（１）のように表現するのだが、後でこれらを組み合わせ何度か計算するので、解りやすくするためにａ＾ｂを ｍといい、ａ＾ｃを ｏと、ａ＾ｄを ｐと、ｂ＾ｃを ｑと、ｂ＾ｄを ｒと、ｃ＾ｄを ｎということにする。
それ以外にａ＾ｂ＾ｃは ｉと、ａ＾ｂ＾ｄは ｊと、ａ＾ｃ＾ｄは ｈと、ｂ＾ｃ＾ｄは ｇといい、そしてａ＾ｂ＾ｃ＾ｄを ｓということにする。
そしてこれ以降ｍ、ｏ、ｐ、ｑ、ｒなどはそれぞれ独自のパターンについての名前とし、オペランドを変化させたときの各ベクトルの状態についてはベクトルＶ（１）からベクトルＶ（１１）などと表現することとする。
【０００６】
次にａ、ｂ、ｃ、ｄを換字と並べ替えで置換する手順について下の表４を用いて説明する。
表４の右半分は表３と同じである。
【表４】
各２ビットのレジスタ１とレジスタ２、そして作業レジスタを用意する。
その変換規則は
１．レジスタ１とレジスタ２の値をＥＸＯＲ演算してその値を作業レジスタにストアする。
２．もしレジスタ２の各ビットの値が等しければ作業レジスタの値をそのまま、もしそうでなければ作業レジスタの値を上下入れ替える。
３．レジスタ２の値をレジスタ１に移動し、作業レジスタの値をレジスタ２に移動する。
４．作業レジスタの値を出力するか、又は繰り返し実行する。
というものである。
以下、レジスタ１の値をレジスタ２でＥＸＯＲ演算しレジスタ２の各ビットの比較演算値で並べ替えを選択するという一連の操作をＸＯＲ−Ｐ（ｐｅｒｍｕｔａｔｉｏｎ）演算と言い、情報ａｂの値をレジスタ１にストアし、情報ｃｄの値をレジスタ２にストアしてＸＯＲ−Ｐ演算することを、レジスタ１情報ａｂをレジスタ２情報ｃｄでＸＯＲ−Ｐ演算すると言うことにする。
表４は００から１１までの２ビット情報を持つレジスタ１情報ａｂを同じく００から１１までの２ビット情報を持つレジスタ２情報ｃｄでＸＯＲ−Ｐ演算を繰り返した途中経過を遷移表で表したものである。
表４の１列目はレジスタ１の初期状態ａｂの値であり、２列目はレジスタ２の情報ｃｄである。
以下で説明する遷移表についても１列目はレジスタ１の初期状態のビット値であり、２列目はレジスタ２のビット値である。
表４の３列目はｅｆと名付けられていて、レジスタ１情報ａｂをレジスタ２情報ｃｄでＸＯＲ−Ｐ演算した作業レジスタの値の状態である。
それ以降はレジスタ１とレジスタ２の情報を入れ替えてＸＯＲ−Ｐ演算を実行する度の、作業レジスタの値の状態ごとにｇｈ、ｉｊ、ｋｌと名前を付けた。
ｇは表３で説明したｂ＾ｃ＾ｄと、ｈはａ＾ｃ＾ｄと、ｉはａ＾ｂ＾ｃと、ｊはａ＾ｂ＾ｄ と同じである。
しかしｅ、ｆ、ｋ、ｌはａ、ｂ、ｃ、ｄをＥＸＯＲ演算するだけでは生成されない。
そして、これらのベクトルもｅ、ｆ、ｋ、ｌはａｂ、ｃｄをオペランドとした時のそれぞれのパターン名であり、オペランドを変化させたときの各ベクトルの状態についてはベクトルＵ（１）からベクトルＵ（８）などと表現することとする。
下の表５はｅ、ｆ、ｋ、ｌの各ベクトルを順に並べたものが ａｂと ｃｄの２ビット値に対応する様子を示すもので、行見出しは ａｂの値であり列見出しは ｃｄの値である。
表５ではｅｆｋｌがａｂｃｄと一対一対応せず２対１対応していて、ｅｆｋｌの値からａｂｃｄを求められないのは後述の表１０を見れば解る。
【表５】
この変換は最大でも６回で循環するため７列目は省略する。
ＸＯＲ−Ｐ演算の順序を違えてレジスタを入れ替えてからＥＸＯＲ演算した場合、３列目と６列目の値の状態が交換されるだけであって大きな差異はない。
そこで、このＰ−ＸＯＲ演算ともいうべき方法についてこれ以降、言及することはしない。
【０００７】
さきのＹ、Ｚ、Ａ、Ｂ、Ｃ、ＤについてＸＯＲ−Ｐ演算をして６ビット情報を８ビットの全単射写像に拡大する。
ここでもＡＢ、ＣＤにＹＺが付け加えられたものとして考える。
下の表６はｉ、ｊ、ｋ、ｌの各ベクトルを順に並べたものが ａｂと ｃｄの２ビット値に対応する様子を示すもので、行見出しは ａｂの値であり列見出しは ｃｄの値である。
ｉｊｋｌがａｂｃｄと一対一対応していて、ｉｊｋｌがａｂｃｄの全単射写像であるのが解る。
【表６】
ＡＢを第１オペランドとし、ＣＤを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（５）とベクトルＵ（６）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
即ちこれらはａｂｃｄの全単射写像ｉｊｋｌであってこれらをＩＪＫＬということにする。
表１、表２で全単射写像拡大したときＡＢＹＺとＣＤＹＺを取り出して示したが、今回の全単射写像拡大にはＡＢＣＤの全単射写像ＩＪＫＬを２ビットずつに分割してＹＺを作用させＩＪＹＺとＫＬＹＺをＸＯＲ−Ｐ演算する。
ＩＪを第１オペランドとし、ＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表５で２対１対応すると説明したｅ、ｆ、ｋ、ｌのことである。
つぎにＫＬを第１オペランドとし、やはりＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（５）とベクトルＵ（６）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表６で一対一対応すると説明したｉ、ｊ、ｋ、ｌのことである。
これら８ビットを１６進数で表したのが表７である。
表７の各値はＹＺＡＢＣＤの値に一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
【表７】
【０００８】
つぎに変数Ｗ、Ｘがそれぞれ１ビットの情報を持つこととしてＷ、Ｘ、Ｙ、Ｚ、Ａ、Ｂ、Ｃ、ＤについてＸＯＲ−Ｐ演算をして８ビット情報を１６ビットの全単射写像に拡大して、この全単射写像拡大手続きが有用であることを示す。
さきのＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄについての８ビットの全単射写像をＭＮＯＰＱＲＳＴとする時、
ＭＮ、ＯＰ、ＱＲ、ＳＴのそれぞれにＷＸを作用させる。
つまり写像を２ビットずつに分割し分割１単位毎にＷＸを作用させて連結するのは変換しない表１と表２のときと同じであり、元の情報のビット数が増えるごとにこれをを繰り返すことも同じである。
ＭＮを第１オペランドとし、ＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
ＯＰを第１オペランドとし、ＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
ＱＲを第１オペランドとし、ＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表５で２対１対応すると説明したｅ、ｆ、ｋ、ｌのことである。
最後にＳＴを第１オペランドとし、やはりＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（５）とベクトルＵ（６）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表６で一対一対応すると説明したｉ、ｊ、ｋ、ｌのことである。
これら１６ビットを１６進数で表したのが表８である。
表の各値はＷＸＹＺＡＢＣＤの値に一対一対応していてＷＸＹＺＡＢＣＤの全単射写像といえる。
【表８】
【０００９】
さきに作った全単射写像を利用すれば、上記と同じように２ビットの変数を増やして２倍のビット数の全単射写像を出力できるのは当然でこれ以上の説明はしない。
つまり上記の全単射写像拡大の手続きはＮビットの変数について２の（Ｎ÷２）乗ビットの全単射写像を出力する。
また、最後の１ビットが出力されるまでＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄの値を決定することが出来ない。
しかし、最後の１ビットが出力されたとき変数全体の値が解ることになり次のビットの値を予測することができる。
さきのＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄの全単射写像についての原像復元手続きは以下の通りである。
Ｙ、Ｚ、Ａ、Ｂ、Ｃ、Ｄについての８ビットの全単射写像をＭＮＯＰＱＲＳＴとする時、
ＱＲＳＴはＫＬを第１オペランドとしＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしたベクトルＵ（５）、ベクトルＵ（６）、ベクトルＵ（７）、ベクトルＵ（８）であって
ベクトルＵ（５）、ベクトルＵ（６）即ちベクトルｉｊを第１オペランドとしベクトルＵ（７）、ベクトルＵ（８）即ちベクトルｋｌを第２オペランドとしてＸＯＲ−Ｐ演算をした遷移表が下の表９であることから
【表９】
ＱＲを第１オペランドとしＳＴを第２オペランドとしてＸＯＲ−Ｐ演算をしたベクトルＵ（１）、ベクトルＵ（２）、ベクトルＵ（３）、ベクトルＵ（４）がＫＬＹＺである。
つぎにＭＮＯＰはＩＪを第１オペランドとし、ＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）であるけれども、
ベクトルＵ（１）、ベクトルＵ（２）即ちベクトルｅｆを第１オペランドとし、ベクトルＵ（７）とベクトルＵ（８）即ちベクトルｋｌを第２オペランドとしてＸＯＲ−Ｐ演算をした遷移表が下の表１０であるのでＭＮＯＰだけからＩＪを求めることは出来ない。
【表１０】
そこでＰＯを第１オペランドとし、先に求めたＺＹを第２オペランドとしてＸＯＲ−Ｐ演算をする。
これはベクトルｌｋを第１オペランドとし、ｄｃを第２オペランドとしてＸＯＲ−Ｐ演算をしたものと同じでありベクトルＵ（２）、ベクトルＵ（１）がＩＪであることは表１１の遷移表で解る。
【表１１】
こうして求められたＩＪＫＬを表９のとおりＸＯＲ−Ｐ演算をしたベクトルＵ（１）、ベクトルＵ（２）、ベクトルＵ（３）、ベクトルＵ（４）がＡ、Ｂ、Ｃ、Ｄである。
こうして直線的に元のＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄが求まる。
【００１０】
さて最初に述べた表２の全単射拡大写像とさきの表７の全単射拡大写像の各値をそれぞれＥＸＯＲ演算したものが表１２である。
表の各値はＹＺＡＢＣＤの値に一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
【表１２】
表２の全単射拡大写像はＡＢＹＺＣＤＹＺであり、表７の全単射拡大写像ＭＮＯＰＱＲＳＴはＹＺＡＢＣＤを変換したものであって、どちらもＹＺＡＢＣＤの全単射拡大写像である。
ＡＢＹＺＣＤＹＺの値か又はＭＮＯＰＱＲＳＴの値をもとにＹＺＡＢＣＤの値を求めようとしても、表１２の値からＡＢＹＺＣＤＹＺの値とＭＮＯＰＱＲＳＴの値に分離することは出来ないのは当然である。
ＹＺＡＢＣＤの値を知らなければＡＢＹＺＣＤＹＺの値か又はＭＮＯＰＱＲＳＴの値を生成できない。
ＡＢＹＺＣＤＹＺとＭＮＯＰＱＲＳＴをＥＸＯＲ演算した表１２の各値は原像復元手続きの無いＹＺＡＢＣＤの全単射拡大写像である。
写像と原像との対応を知るためには表１２が必要で、これは表１２の各値からＹＺＡＢＣＤの値を知るには全鍵検索をしなければならないということである。
悪意のある解読者がいたとしても、解読者が予め表１２を準備することができないなら、ＹＺＡＢＣＤの値を増分するなどと予告されていて上記と同じ手続きで新しい８ビットが出力されても、その最初のビットが０か１かさえ予測することは出来ない。
ＹＺＡＢＣＤのビット数を充分大きくすることで全鍵検索が必要な表１２の大きさが増大して秘密であるべき原像の値を知るためのコンピュータ的時間量が膨大であれば、たとえアルゴリズムが全て公開されていて悪意のある解読者が全く同じ擬似乱数生成器を持っていたとしても解読者は秘密であるべき原像の値を知ることなしに同じ擬似乱数を再現することも出来ないし原像の値の変更とその増分数が分かっても未来の出力を予測することはできない。
全鍵検索をしなくては原像の値を知ることの出来ないこの全単射拡大写像は擬似乱数である。
【００１１】
表４で示される各ベクトルを使用して表１２と同じような全単射拡大写像を作ることが出来る。
例えばｉｊｋｌの代わりにｍｎｏｇを用いて、
ｍｎを第１オペランドとし、ＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＶ（１）とベクトルＶ（６）そしてベクトルＶ（２）とベクトルＵ（１）の４ビットを求める。
これらは表４でｍ、ｎ、ｏ、ｅのことである。
つぎにｏｇを第１オペランドとし、やはりＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＶ（１）とベクトルＶ（６）そしてベクトルＶ（２）とベクトルＵ（３）の４ビットを求める。
これらは表４でｍ、ｎ、ｏ、ｇのことである。
これら４ビットを連結して８ビットとする。。
このように作られる全単射拡大写像を下の表１３に示す。
【表１３】
表１３の各値と最初に述べた表２の各値をそれぞれＥＸＯＲ演算したものが表１４である。
表の各値はＹＺＡＢＣＤの値に一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
【表１４】
【発明を実施するための最良の形態】
【００１２】
本発明は通信の安全と重要情報保全に資するコンピューティングシステム全てに適応する。
【産業上の利用可能性】
【００１３】
本発明はよりコンピュータ的時間量の少ない一方向性関数を構成することができ重要情報の安全を図ることが出来る。
【実施例】
【００１４】
実施例はまだ無い。
【技術分野】
【０００１】
本発明は擬似乱数を生成するものであり、その一方向性から暗号化技術に関連する。
【背景技術】
【０００２】
本発明のようにビット情報を換字と並べ替えで置換することはシャノンのＳＴＮ構造と呼ばれ、古くはＤＥＳのＳボックスを作成することに用いられているものであって
【特許文献１】国際出願番号 ＰＣＴ／ＪＰ２００５／００８６４６と
【特許文献２】特願２００９−２６５２８６には会員のパスワードをネットワーク運営者に対して秘密にしたまま会員本人と認証申請者の個人的同定できることが示されており
【特許文献２】には擬似乱数発生器についての言及がされていて、その説明に本明細書と同様の図表が用いられているものの、本発明は擬似乱数生成法であって
【特許文献１】や
【特許文献２】と異なる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
現在の暗号化の安全性は素因数分解や楕円関数など効率的な解法が見つかっていない数学的な問題解答のために費やされるコンピュータ的時間量の膨大さによる一方向性で保証される。
一方、一方向性ではないかと予想されていたハッシュ関数の多くはその脆弱さが指摘され、その安全性は数学の進歩と反比例すると言える。
計算の容易さと一方向性を両立させるには理想的な擬似乱数を作ることが必要である。
【課題を解決するための手段】
【０００４】
本発明は、ビット情報を拡大し元の情報の全単射写像を作り疑似乱数化するものである。
まず最も簡単なものとして、６ビット情報を変換することなしに８ビットの全単射写像に拡大して下に示す。
２ビットを１単位として４つの変数Ａ、Ｂ、Ｃ、Ｄのそれぞれが１ビットの情報を持つこととしてＡＢ、ＣＤの２つのブロックとする。
それぞれ１ビットの情報を持つ変数ＹとＺを追加して６ビット情報とし、ＡＢ、ＣＤのブロックに付け加えられる。
ＡＢＹＺの値の４ビットとＣＤＹＺの４ビットの計８ビットをＡＢＹＺＣＤＹＺの順に並べたものが表１である。
Ｙ、Ｚ、ＡとＢ、Ｃ、Ｄの組み合わせは６４通りあって、行見出しにＹＺＡの値を、列見出しにＢＣＤの値を示す。
表１の各値はＹＺＡＢＣＤの値と一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
表２は表１の各値を１６進数で表現したものである。
【表１】
【表２】
因みにＹＺＡＢＣＤに加えて変数Ｗ、Ｘがそれぞれ１ビットの情報を持つこととして計８ビットの情報を変換することなしに１６ビットの全単射写像に拡大するには先のＡＢＹＺＣＤＹＺを２ビットずつに区切ってＡＢＷＸＹＺＷＸＣＤＷＸＹＺＷＸというように並べればよい。
つまり写像を２ビットずつに分割し分割１単位毎に２ビットを付け加えて連結することであり元の情報のビット数が増えるごとにこれをを繰り返す。
【０００５】
下の表３は変数ａ、ｂ、ｃ、ｄのそれぞれが１ビットの情報を持つこととして、それらの組み合わせをＥＸＯＲ演算したものである。
【表３】
ａ、ｂ、ｃ、ｄの各ビットを取り出し、並べ替えてＥＸＯＲ演算することによって、異なるパターンでａ、ｂ、ｃ、ｄ各値に対応する１１の変換がある。
それらをベクトルということにして１から１１の添え字をつけてベクトルＶ（１）のように表現するのだが、後でこれらを組み合わせ何度か計算するので、解りやすくするためにａ＾ｂを ｍといい、ａ＾ｃを ｏと、ａ＾ｄを ｐと、ｂ＾ｃを ｑと、ｂ＾ｄを ｒと、ｃ＾ｄを ｎということにする。
それ以外にａ＾ｂ＾ｃは ｉと、ａ＾ｂ＾ｄは ｊと、ａ＾ｃ＾ｄは ｈと、ｂ＾ｃ＾ｄは ｇといい、そしてａ＾ｂ＾ｃ＾ｄを ｓということにする。
そしてこれ以降ｍ、ｏ、ｐ、ｑ、ｒなどはそれぞれ独自のパターンについての名前とし、オペランドを変化させたときの各ベクトルの状態についてはベクトルＶ（１）からベクトルＶ（１１）などと表現することとする。
【０００６】
次にａ、ｂ、ｃ、ｄを換字と並べ替えで置換する手順について下の表４を用いて説明する。
表４の右半分は表３と同じである。
【表４】
各２ビットのレジスタ１とレジスタ２、そして作業レジスタを用意する。
その変換規則は
１．レジスタ１とレジスタ２の値をＥＸＯＲ演算してその値を作業レジスタにストアする。
２．もしレジスタ２の各ビットの値が等しければ作業レジスタの値をそのまま、もしそうでなければ作業レジスタの値を上下入れ替える。
３．レジスタ２の値をレジスタ１に移動し、作業レジスタの値をレジスタ２に移動する。
４．作業レジスタの値を出力するか、又は繰り返し実行する。
というものである。
以下、レジスタ１の値をレジスタ２でＥＸＯＲ演算しレジスタ２の各ビットの比較演算値で並べ替えを選択するという一連の操作をＸＯＲ−Ｐ（ｐｅｒｍｕｔａｔｉｏｎ）演算と言い、情報ａｂの値をレジスタ１にストアし、情報ｃｄの値をレジスタ２にストアしてＸＯＲ−Ｐ演算することを、レジスタ１情報ａｂをレジスタ２情報ｃｄでＸＯＲ−Ｐ演算すると言うことにする。
表４は００から１１までの２ビット情報を持つレジスタ１情報ａｂを同じく００から１１までの２ビット情報を持つレジスタ２情報ｃｄでＸＯＲ−Ｐ演算を繰り返した途中経過を遷移表で表したものである。
表４の１列目はレジスタ１の初期状態ａｂの値であり、２列目はレジスタ２の情報ｃｄである。
以下で説明する遷移表についても１列目はレジスタ１の初期状態のビット値であり、２列目はレジスタ２のビット値である。
表４の３列目はｅｆと名付けられていて、レジスタ１情報ａｂをレジスタ２情報ｃｄでＸＯＲ−Ｐ演算した作業レジスタの値の状態である。
それ以降はレジスタ１とレジスタ２の情報を入れ替えてＸＯＲ−Ｐ演算を実行する度の、作業レジスタの値の状態ごとにｇｈ、ｉｊ、ｋｌと名前を付けた。
ｇは表３で説明したｂ＾ｃ＾ｄと、ｈはａ＾ｃ＾ｄと、ｉはａ＾ｂ＾ｃと、ｊはａ＾ｂ＾ｄ と同じである。
しかしｅ、ｆ、ｋ、ｌはａ、ｂ、ｃ、ｄをＥＸＯＲ演算するだけでは生成されない。
そして、これらのベクトルもｅ、ｆ、ｋ、ｌはａｂ、ｃｄをオペランドとした時のそれぞれのパターン名であり、オペランドを変化させたときの各ベクトルの状態についてはベクトルＵ（１）からベクトルＵ（８）などと表現することとする。
下の表５はｅ、ｆ、ｋ、ｌの各ベクトルを順に並べたものが ａｂと ｃｄの２ビット値に対応する様子を示すもので、行見出しは ａｂの値であり列見出しは ｃｄの値である。
表５ではｅｆｋｌがａｂｃｄと一対一対応せず２対１対応していて、ｅｆｋｌの値からａｂｃｄを求められないのは後述の表１０を見れば解る。
【表５】
この変換は最大でも６回で循環するため７列目は省略する。
ＸＯＲ−Ｐ演算の順序を違えてレジスタを入れ替えてからＥＸＯＲ演算した場合、３列目と６列目の値の状態が交換されるだけであって大きな差異はない。
そこで、このＰ−ＸＯＲ演算ともいうべき方法についてこれ以降、言及することはしない。
【０００７】
さきのＹ、Ｚ、Ａ、Ｂ、Ｃ、ＤについてＸＯＲ−Ｐ演算をして６ビット情報を８ビットの全単射写像に拡大する。
ここでもＡＢ、ＣＤにＹＺが付け加えられたものとして考える。
下の表６はｉ、ｊ、ｋ、ｌの各ベクトルを順に並べたものが ａｂと ｃｄの２ビット値に対応する様子を示すもので、行見出しは ａｂの値であり列見出しは ｃｄの値である。
ｉｊｋｌがａｂｃｄと一対一対応していて、ｉｊｋｌがａｂｃｄの全単射写像であるのが解る。
【表６】
ＡＢを第１オペランドとし、ＣＤを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（５）とベクトルＵ（６）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
即ちこれらはａｂｃｄの全単射写像ｉｊｋｌであってこれらをＩＪＫＬということにする。
表１、表２で全単射写像拡大したときＡＢＹＺとＣＤＹＺを取り出して示したが、今回の全単射写像拡大にはＡＢＣＤの全単射写像ＩＪＫＬを２ビットずつに分割してＹＺを作用させＩＪＹＺとＫＬＹＺをＸＯＲ−Ｐ演算する。
ＩＪを第１オペランドとし、ＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表５で２対１対応すると説明したｅ、ｆ、ｋ、ｌのことである。
つぎにＫＬを第１オペランドとし、やはりＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（５）とベクトルＵ（６）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表６で一対一対応すると説明したｉ、ｊ、ｋ、ｌのことである。
これら８ビットを１６進数で表したのが表７である。
表７の各値はＹＺＡＢＣＤの値に一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
【表７】
【０００８】
つぎに変数Ｗ、Ｘがそれぞれ１ビットの情報を持つこととしてＷ、Ｘ、Ｙ、Ｚ、Ａ、Ｂ、Ｃ、ＤについてＸＯＲ−Ｐ演算をして８ビット情報を１６ビットの全単射写像に拡大して、この全単射写像拡大手続きが有用であることを示す。
さきのＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄについての８ビットの全単射写像をＭＮＯＰＱＲＳＴとする時、
ＭＮ、ＯＰ、ＱＲ、ＳＴのそれぞれにＷＸを作用させる。
つまり写像を２ビットずつに分割し分割１単位毎にＷＸを作用させて連結するのは変換しない表１と表２のときと同じであり、元の情報のビット数が増えるごとにこれをを繰り返すことも同じである。
ＭＮを第１オペランドとし、ＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
ＯＰを第１オペランドとし、ＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
ＱＲを第１オペランドとし、ＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表５で２対１対応すると説明したｅ、ｆ、ｋ、ｌのことである。
最後にＳＴを第１オペランドとし、やはりＷＸを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（５）とベクトルＵ（６）そしてベクトルＵ（７）とベクトルＵ（８）の４ビットを求める。
これらは表６で一対一対応すると説明したｉ、ｊ、ｋ、ｌのことである。
これら１６ビットを１６進数で表したのが表８である。
表の各値はＷＸＹＺＡＢＣＤの値に一対一対応していてＷＸＹＺＡＢＣＤの全単射写像といえる。
【表８】
【０００９】
さきに作った全単射写像を利用すれば、上記と同じように２ビットの変数を増やして２倍のビット数の全単射写像を出力できるのは当然でこれ以上の説明はしない。
つまり上記の全単射写像拡大の手続きはＮビットの変数について２の（Ｎ÷２）乗ビットの全単射写像を出力する。
また、最後の１ビットが出力されるまでＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄの値を決定することが出来ない。
しかし、最後の１ビットが出力されたとき変数全体の値が解ることになり次のビットの値を予測することができる。
さきのＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄの全単射写像についての原像復元手続きは以下の通りである。
Ｙ、Ｚ、Ａ、Ｂ、Ｃ、Ｄについての８ビットの全単射写像をＭＮＯＰＱＲＳＴとする時、
ＱＲＳＴはＫＬを第１オペランドとしＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしたベクトルＵ（５）、ベクトルＵ（６）、ベクトルＵ（７）、ベクトルＵ（８）であって
ベクトルＵ（５）、ベクトルＵ（６）即ちベクトルｉｊを第１オペランドとしベクトルＵ（７）、ベクトルＵ（８）即ちベクトルｋｌを第２オペランドとしてＸＯＲ−Ｐ演算をした遷移表が下の表９であることから
【表９】
ＱＲを第１オペランドとしＳＴを第２オペランドとしてＸＯＲ−Ｐ演算をしたベクトルＵ（１）、ベクトルＵ（２）、ベクトルＵ（３）、ベクトルＵ（４）がＫＬＹＺである。
つぎにＭＮＯＰはＩＪを第１オペランドとし、ＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＵ（１）とベクトルＵ（２）そしてベクトルＵ（７）とベクトルＵ（８）であるけれども、
ベクトルＵ（１）、ベクトルＵ（２）即ちベクトルｅｆを第１オペランドとし、ベクトルＵ（７）とベクトルＵ（８）即ちベクトルｋｌを第２オペランドとしてＸＯＲ−Ｐ演算をした遷移表が下の表１０であるのでＭＮＯＰだけからＩＪを求めることは出来ない。
【表１０】
そこでＰＯを第１オペランドとし、先に求めたＺＹを第２オペランドとしてＸＯＲ−Ｐ演算をする。
これはベクトルｌｋを第１オペランドとし、ｄｃを第２オペランドとしてＸＯＲ−Ｐ演算をしたものと同じでありベクトルＵ（２）、ベクトルＵ（１）がＩＪであることは表１１の遷移表で解る。
【表１１】
こうして求められたＩＪＫＬを表９のとおりＸＯＲ−Ｐ演算をしたベクトルＵ（１）、ベクトルＵ（２）、ベクトルＵ（３）、ベクトルＵ（４）がＡ、Ｂ、Ｃ、Ｄである。
こうして直線的に元のＹ、Ｚ、Ａ、Ｂ、Ｃ、Ｄが求まる。
【００１０】
さて最初に述べた表２の全単射拡大写像とさきの表７の全単射拡大写像の各値をそれぞれＥＸＯＲ演算したものが表１２である。
表の各値はＹＺＡＢＣＤの値に一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
【表１２】
表２の全単射拡大写像はＡＢＹＺＣＤＹＺであり、表７の全単射拡大写像ＭＮＯＰＱＲＳＴはＹＺＡＢＣＤを変換したものであって、どちらもＹＺＡＢＣＤの全単射拡大写像である。
ＡＢＹＺＣＤＹＺの値か又はＭＮＯＰＱＲＳＴの値をもとにＹＺＡＢＣＤの値を求めようとしても、表１２の値からＡＢＹＺＣＤＹＺの値とＭＮＯＰＱＲＳＴの値に分離することは出来ないのは当然である。
ＹＺＡＢＣＤの値を知らなければＡＢＹＺＣＤＹＺの値か又はＭＮＯＰＱＲＳＴの値を生成できない。
ＡＢＹＺＣＤＹＺとＭＮＯＰＱＲＳＴをＥＸＯＲ演算した表１２の各値は原像復元手続きの無いＹＺＡＢＣＤの全単射拡大写像である。
写像と原像との対応を知るためには表１２が必要で、これは表１２の各値からＹＺＡＢＣＤの値を知るには全鍵検索をしなければならないということである。
悪意のある解読者がいたとしても、解読者が予め表１２を準備することができないなら、ＹＺＡＢＣＤの値を増分するなどと予告されていて上記と同じ手続きで新しい８ビットが出力されても、その最初のビットが０か１かさえ予測することは出来ない。
ＹＺＡＢＣＤのビット数を充分大きくすることで全鍵検索が必要な表１２の大きさが増大して秘密であるべき原像の値を知るためのコンピュータ的時間量が膨大であれば、たとえアルゴリズムが全て公開されていて悪意のある解読者が全く同じ擬似乱数生成器を持っていたとしても解読者は秘密であるべき原像の値を知ることなしに同じ擬似乱数を再現することも出来ないし原像の値の変更とその増分数が分かっても未来の出力を予測することはできない。
全鍵検索をしなくては原像の値を知ることの出来ないこの全単射拡大写像は擬似乱数である。
【００１１】
表４で示される各ベクトルを使用して表１２と同じような全単射拡大写像を作ることが出来る。
例えばｉｊｋｌの代わりにｍｎｏｇを用いて、
ｍｎを第１オペランドとし、ＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＶ（１）とベクトルＶ（６）そしてベクトルＶ（２）とベクトルＵ（１）の４ビットを求める。
これらは表４でｍ、ｎ、ｏ、ｅのことである。
つぎにｏｇを第１オペランドとし、やはりＹＺを第２オペランドとしてＸＯＲ−Ｐ演算をしてベクトルＶ（１）とベクトルＶ（６）そしてベクトルＶ（２）とベクトルＵ（３）の４ビットを求める。
これらは表４でｍ、ｎ、ｏ、ｇのことである。
これら４ビットを連結して８ビットとする。。
このように作られる全単射拡大写像を下の表１３に示す。
【表１３】
表１３の各値と最初に述べた表２の各値をそれぞれＥＸＯＲ演算したものが表１４である。
表の各値はＹＺＡＢＣＤの値に一対一対応していてＹＺＡＢＣＤの全単射写像といえる。
【表１４】
【発明を実施するための最良の形態】
【００１２】
本発明は通信の安全と重要情報保全に資するコンピューティングシステム全てに適応する。
【産業上の利用可能性】
【００１３】
本発明はよりコンピュータ的時間量の少ない一方向性関数を構成することができ重要情報の安全を図ることが出来る。
【実施例】
【００１４】
実施例はまだ無い。
【特許請求の範囲】
【請求項１】
アルゴリズムと過去の出力が既知であれば、未来の出力を予測することが可能な古典的擬似乱数化技術に対し：
全単射写像拡大による擬似乱数生成法 では
特徴づけられることとして
原像情報の内の４ビットを取り出して最初の写像とすること、
そのあと原像情報に２ビットが残れば写像を２ビットずつに分割し分割１単位毎に原像情報から取り出した２ビットを付け加えて連結するということを繰り返すことで拡大された全単射写像を作ること、
もう一つの全単射写像を作るために原像情報の内の４ビットを取り出してＥＸＯＲと並べ替えで置換した全単射写像を最初の写像とすること、
そのあと原像情報に２ビットが残れば写像を２ビットずつに分割し分割１単位毎に分割された２ビットと原像情報から取り出した２ビットで置換した写像を付け加えて連結するということを繰り返すことでもう一つの拡大された全単射写像を作ること、
こうして作られた２つの全単射写像の各ビットをＥＸＯＲ演算して１つの拡大された全単射写像を作ること、
その拡大された全単射写像から直線的に原像を復元する方法が無いこと
がある。
【請求項１】
アルゴリズムと過去の出力が既知であれば、未来の出力を予測することが可能な古典的擬似乱数化技術に対し：
全単射写像拡大による擬似乱数生成法 では
特徴づけられることとして
原像情報の内の４ビットを取り出して最初の写像とすること、
そのあと原像情報に２ビットが残れば写像を２ビットずつに分割し分割１単位毎に原像情報から取り出した２ビットを付け加えて連結するということを繰り返すことで拡大された全単射写像を作ること、
もう一つの全単射写像を作るために原像情報の内の４ビットを取り出してＥＸＯＲと並べ替えで置換した全単射写像を最初の写像とすること、
そのあと原像情報に２ビットが残れば写像を２ビットずつに分割し分割１単位毎に分割された２ビットと原像情報から取り出した２ビットで置換した写像を付け加えて連結するということを繰り返すことでもう一つの拡大された全単射写像を作ること、
こうして作られた２つの全単射写像の各ビットをＥＸＯＲ演算して１つの拡大された全単射写像を作ること、
その拡大された全単射写像から直線的に原像を復元する方法が無いこと
がある。
【公開番号】特開２０１２−９８６５０（Ｐ２０１２−９８６５０Ａ）
【公開日】平成２４年５月２４日（２０１２．５．２４）
【国際特許分類】
【出願番号】特願２０１０−２４８２２８（Ｐ２０１０−２４８２２８）
【出願日】平成２２年１１月５日（２０１０．１１．５）
【出願人】（５０２４３４１８１）
【Ｆターム（参考）】
【公開日】平成２４年５月２４日（２０１２．５．２４）
【国際特許分類】
【出願日】平成２２年１１月５日（２０１０．１１．５）
【出願人】（５０２４３４１８１）
【Ｆターム（参考）】
[ Back to top ]