複素数及び行列による強化ＲＳＡ系暗号
【課題】離散対数問題に難読性の根拠を置く暗号の強度を向上させる。また、ＲＳＡ暗号の鍵を高速に作成する。
【解決手段】同じ因数が重複して含まれる合成数を法としても１と合同になる一般化されたフェルマーの小定理を導出し、これを利用する。また、因数に関する関係式を用いて、最大公約数からも秘密鍵と公開鍵の逆数の関係にある２数を計算する。 また、離散対数問題の強度の向上については、複素数、または行列の離散対数問題を利用する。
【解決手段】同じ因数が重複して含まれる合成数を法としても１と合同になる一般化されたフェルマーの小定理を導出し、これを利用する。また、因数に関する関係式を用いて、最大公約数からも秘密鍵と公開鍵の逆数の関係にある２数を計算する。 また、離散対数問題の強度の向上については、複素数、または行列の離散対数問題を利用する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術分野に属する。
【背景技術】
【０００２】
自然数に関する離散対数問題及び素因数分解の非容易性に難読性の根拠を置く暗号技術を背景とする。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
離散対数問題を強化する。また、ＲＳＡ暗号に関しては、鍵を高速に作成する。
【課題を解決するための手段】
【０００４】
ＲＳＡに利用可能な鍵を高速に作成するには、幾つかの方法があり、特許も多く出願されている。
本発明では、以下の二つの方法を提案する。一つ目は、フェルマーの小定理から逆数を求める方法である。
一般的に知られているフェルマーの小定理による逆数計算は、ＲＳＡ暗号が復号可能であることの原理そのものである。それは、Ｐ、Ｑが互いに相異なる２素数であるとき、Ｐ，Ｑのいずれとも互いに素である自然数Ａにより、Ａ（Ｐ−１）（Ｑ−１）≡１（ｍｏｄ ＰＱ）というものである。そこで、（Ｐ−１）（Ｑ−１）を適当な２数に因数分解すれば、ＰＱを法として互いに逆数の関係にある２数を得ることができる。Ｐ単体では、Ａ（Ｐ−１）≡１（ｍｏｄ Ｐ）である。
数学的に、ｒを整数として、Ａｒ≡Ｂ（ｍｏｄ Ｐ）、Ａｒ≡Ｂ（ｍｏｄ Ｑ）のとき、Ａｒ≡Ｂ（ｍｏｄ ＰＱ）である。これも、ＲＳＡが復号可能であることの原理なのだが、もし、ＱをＰに置き換え、法の値をＰ２とすると、フェルマーの小定理では、法の値がＰ２だからといって、単純にＡ（Ｐ−１）（Ｐ−１）≡１（ｍｏｄ Ｐ２）とはならない。たとえば、７２≡１（ｍｏｄ ３）だが、７２≡４（ｍｏｄ ９）であり、また、７４≡７（ｍｏｄ ９）である。素数の整数乗を法とするケースでフェルマーの小定理と同様一般的に１と合同にするのに、単純に異なる素数の組み合わせによる合成数を法とする場合と同じように扱うことでそれを実現することはできない。
そこで、これを解決するために、ｎを自然数として、Ｐｎを法として必ずＡを１と合同にする、一般化されたフェルマーの小定理を導出する必要がある。
と元のフェルマーの小定理に戻る。この結果は、フェルマーの小定理により、任意の整数ｘを用い、Ａ（Ｐ−１）＝Ｐｘ＋１とした上で、この式の両辺をＰ（ｎ−１）乗して右辺を多項式に展開すると、定数１以外の係数が全てＰｎを法としてゼロと合同になることによって示される。
が得られる。従って、書類「特許請求の範囲」に掲げた式
【数１】
のように一般化しても、法の値に含まれる因数の全ての組み合わせについて左辺は１と合同になることになるので、この式はＲＳＡが復号可能であることの原理と同様の理由により、法の値と互いに素である任意の一つの数から、その逆数にあたるもう一つの数を導き出す。
【０００５】
二つ目は、ユークリッドの互除法などの方法を用い、最大公約数から秘密鍵を作成する方法である。
ある２数Ａ、Ｂがあるとして、ＡＢ＋１について考える。このＡＢ＋１を、ＡＢ＋１＝｛（Ａ−１）＋１｝｛（Ｂ＋１）−１｝＋１と書き換え、Ａ−１とＢ＋１の最大公約数を求めてそれをｒとすると、Ａ−１＝ｒａ、Ｂ＋１＝ｒｂとしたとき、ＡＢ＋１＝（ｒａ＋１）（ｒｂ−１）＋１≡１・−１＋１≡０（ｍｏｄ ｒ）となり、ＡＢ＋１はｒを因数に持つことになる。
本発明におけるこの鍵作成法は、この原理を利用したものである。
今、２素数Ｐ、Ｑを考え、ある整数をｇとして、（Ｐｇ−１）と（Ｑｇ−１）の最大公約数を求める。これをｓとし、ｓで（Ｐｇ−１）を割った商をｘ、（Ｑｇ−１）を割った商をｙとする。
すると、（Ｐｇ−１）（Ｑｇ−１）＋１は、（Ｐｇ−１）（Ｑｇ−１）＋１＝ｘｙｓ２＋１となる。
ここで、これらとは別に、２つの自然数ｊ、ｋを用意し、ｊ、ｋ、ｘ、ｙ、ｓ、ｓの６個の数字から幾つかを取り出して掛け合わせてＡとし、残りも掛け合わせてＢとする。ｘ、ｙ、ｓの累乗については、ｊ、ｋにｘ、ｙ、ｓが単数又は複数、因数として含まれる場合と同じにみなす。
このＡ、Ｂについて、先の方法でＡ−１とＢ＋１における最大公約数ｒを求め、これが１の場合は再度別の組み合わせ、または別のｊ、ｋを用意してｒを求めなおし、１でない、有効な値であるｒによって、ＡＢ＋１＝ｊｋｘｙｓ２＋１＝ｊｋ（Ｐｇ−１）（Ｑｇ−１）＋１＝ｒｔと因数分解する。
こうして求められたｒ、ｔにより、ｎを任意の自然数として、ｒｎ≡Ｒ（ｍｏｄ（Ｐｇ−１）（Ｑｇ−１））、ｔｎ≡Ｔ（ｍｏｄ （Ｐｇ−１）（Ｑｇ−１））を求めると、
（ｒｔ）ｎ≡（ｊｋｘｙｓ２＋１）ｎ≡（ｊｋ（Ｐｇ−１）（Ｑｇ−１）＋１）ｎ≡１（ｍｏｄ（Ｐｇ−１）（Ｑｇ−１））となり、どんなｎを選んでも、Ｒ、Ｔは（Ｐｇ−１）（Ｑｇ−１）を法として逆数の関係にある２数となるので、任意に選んだｎにより、自由に秘密鍵と公開鍵を作成することができる。
この方法の利点は、秘密鍵と公開鍵の互いに逆数の関係にある２数を、離散対数問題を用い、任意のｊ、ｋ、ｎによって作成する、という点である。同じ法の値でも、ｊ、ｋ、ｎによっていくらでも異なる組み合わせを作り出すことができる。つまり、この「自由度」が、鍵の安全性を高める効果を持つ、と考えられる。
また、この方法では、Ｐの自然数乗といった周期を持つ行列用の鍵を容易に作成できる。
【０００６】
複素数を用いる暗号は、以下の計算に理論上の根拠を置く。
Ａを、ａ、ｂを整数として、Ａ＝ａ＋ｂｉとなる複素数とする。もう一つの複素数をＢとして、その値をα＋βｉとすると、ＡＢ＝（ａα−ｂβ）＋（ａβ＋ｂα）ｉとなる。
複素数の時計代数は、実部、虚部それぞれに計算されるので、複素数の離散対数では、乗算のほかに、加減算が組み合わされた複雑な計算になることになる。
この性質が、複素数を用いた離散対数問題を、自然数のみによるものよりも強度の高いものとする効果をもっている、と考えられる。
複素数の場合のフェルマーの小定理は、次のようになる。
素数ｐを法として、ａ、ｂ、｜Ａ｜２が全てｐと互いに素であるとき、フェルマーの小定理により、Ａｐ≡ａｐ＋（ｉｂ）ｐ（ｍｏｄ ｐ）である。ｉ４＝１なので、ｐを４で割った余りが１のときは、Ａｐ≡Ａ（ｍｏｄ ｐ）となるが、ｐを４で割った余りが３のときは、Ａｐ≡ａ−ｉｂ（ｍｏｄ ｐ）である。
そこで、ｐ２を周期と見ると、ｐを４で割った剰余の値によらず、Ａｐ２≡Ａ（ｍｏｄ ｐ）である。ここで、｜Ａ｜２がｐと互いに素なので、Ａにはｐを法として逆数が存在する。従って、Ａ（ｐ２−１）≡１（ｍｏｄ ｐ）となる。これが、複素数の場合のフェルマーの小定理である。
ただし、２素数Ｐ、Ｑの合成数によりＰＱを法とする場合には、ｓｔ≡１（ｍｏｄ（Ｐ−１）（Ｑ−１））となるｓｔが、（Ｐ−１）、（Ｑ−１）が共に偶数であることにより４を因数に持っため、Ｐ、Ｑの値によらず、Ａｓｔ≡Ａ（ｍｏｄ ＰＱ）となるので、従来のＲＳＡ暗号と同じように計算できる。
【０００７】
一方、行列を用いる方法については、以下のような行列によるモデュラ代数方程式の解法に基づく。
最初に、下記のような、モデュラ連立方程式を考える。
この連立方程式を解くには、次のようにする。
まず、行列（この行列をＡとする）とベクトルの積の形に式を書き換える。
【数２】
次に、１１を法としてＡと合同な整数逆行列を、フェルマーの小定理により求める。
Ａの行列式の値は｜Ａ｜＝４７で、これは法の値と互いに素である。
従って、フェルマーの小定理により、１１を法として４７−１と合同な整数を求めることができる。その値は、４７−１≡４７（１１−１）−１≡４７９≡４（ｍｏｄ １１）である。従って、
となる。
この逆行列を
【数２】
の両辺に左から掛けることにより、解
が得られる。
この計算に基づき、行列のモデュラは定義される。厳密な定義は、請求項４の演算規則２である。
そして、この行列のモデュラにより、行列の離散対数問題を考えることができる。行列の離散対数問題は、自然数を一次の正方行列とみなすことが可能であることから、旧来の自然数のみに関する離散対数問題よりもさらに高度で解きにくいものであろう、ということが予想される。実際、実数には対数に対してその逆関数（一般にｌｏｇで表される）が存在するが、行列ではそれが存在しない。複素数による離散対数問題よりもさらに高度な離散対数問題が、行列の離散対数問題である。
行列における一般的なフェルマーの小定理（ただし、実施例で挙げるような特殊なケースが存在する）は、Ｅｎをｎ次の単位行列、行列Ａｎを、全ての要素が整数で、ｐを法として逆行列が存在するｎ次の正方行列としたとき、いくつかのサンプルによる実験結果から、
であろう、と予想している。この式において、ｎが１のときは、従来の自然数に関するフェルマーの小定理に戻る。ただし、ｎが１のときはＡ１そのものがｐと互いに素であることが条件であるのに対し、ｎが２以上の場合については、Ａｎの各要素とではなく、Ａｎの各要素が組み合わされて作られる数値とｐが互いに素であることが求められ、その条件は複雑で、また、ｎによって異なる。
この行列のフェルマーの小定理を利用することにより、行列のＲＳＡ暗号を作ることができる。
参考として、要素が複素数である場合については、コンピューターを使った実験結果として、法の素数Ｐが４を法として１と合同になるときは整数のみを要素とする場合と同じ結果になるが、法の素数Ｐが４を法として３と合同となるケースについては、まだ明確なことはわかっていない。また、２素数の積を法とするケースについては、これら２素数が４を法として共に１と合同になる場合と、それぞれが１、３と合同になるケースは、要素が全て実整数の場合のフェルマーの小定理と同じ結果になるが、２素数が共に４を法として３と合同になるケースについては、明確なことはわかっていない。
【発明の効果】
【０００８】
暗号文の安全性を高めることができる。また、請求項１および２については、計算能力の高くないハードウェア上でも、鍵を高速に作成することができる。
【発明を実施するための最良の形態】
【０００９】
携帯電話のような計算能力の弱い端末も含めた、さまざまな種類の端末が混在するネットワーク上での利用が有効である。
【実施例】
【００１０】
請求項１に基づく鍵の作例を示す。
ｐ＝７（＝２×３＋１）、ｑ＝１１（＝２×５＋１）とし、これらの積であるｐｑ＝７７と１３を公開鍵とし、これらに対する秘密鍵である１３の逆数ｔを、次のように求める。
１３−１≡１３｛２（３−１）（５−１）−１｝≡１３１５≡３７＝ｔ （ｍｏｄ （７−１）（１１−１）＝６０）
この計算では、ｐ−１とｑ−１を、２とその他の予めフェルマーテストなどの方法にかけて見つけた素数により生成する。ここでは、必須の２以外の素数として３及び５を選び、それらから７、１１を２つの素数としている。これら３、５により、（７−１）（１１−１）は容易に因数分解されて２×３×２×５となる。３と５を予め探しておくことにより、あとから（ｐ−１）、（ｑ−１）を因数分解することなく、容易に６０を法として逆数を計算することができる。
実際、この鍵を用い、６を暗号化したい元の数値として実験してみると、６１３≡６２（ｍｏｄ ７７）であり、これを秘密鍵３７を用いて復号化すると、６２３７≡６（ｍｏｄ ７７）となって元の数値が復元される。
【００１１】
請求項１に基づく２乗鍵の作例を示す。ここでいう２乗鍵とは、素数の２乗を周期とする暗号化を行う場合の鍵である。
一般的に、ａ、ｂ、ｃ、ｄ、α、β、γを全て整数とし、ｄ＝αβ＋γ且つａ≡α（ｍｏｄｄ）、ｂ≡β（ｍｏｄ ｄ）、ｃ≡γ（ｍｏｄ ｄ）であるとき、ａｂ＋ｃ≡αβ＋γ＝ｄ≡０（ｍｏｄ ｄ）より、任意の整数をｘとして、ａｂ＋ｃ＝ｄｘとなる。つまり、この関係式を利用することで、加減乗算が組み合わされた数値の因数に関する関係式を得ることができる。
を得ることができる。こうしてｐともう一つの素数を作成することにより、公開鍵の法の値と、秘密鍵と公開鍵における互いに逆数同士の２数を得ることができる。
今、ｐ１＝２×２＋１＝５、ｐ２＝２×２×３＋１＝１３、ｔを任意の整数としてΠｎＰｎ＋１＝２（５×１３×ｔ＋５×９＋１３×４）＋１とすると、５×９≡６（ｍｏｄ １３）、１３×４≡２（ｍｏｄ ５）より、ΠｎＰｎ＋１≡２×６＋１（ｍｏｄ １３）、ΠｎＰｎ＋１≡２×２＋１（ｍｏｄ ５）となる。つまり、任意のｔについて、ΠｎＰｎ＋１は５と１３を因数に持つようになる。
れる。９７は素数なので、これにより、Ｐ１＝２、Ｐ２＝９７という２素数が得られたことになる。また、このときｐ＝２×２×９７＋１＝３８９となり、公開鍵の作成に必要な法の値のための、求める一つ目の素数が得られたことになる。
もう一つの素数ｑは、簡単のため、ｑ＝２×３×６１＋１＝３６７とする。
これらのｐ、ｑにより、ｐ２−１＝２３×３×５×１３×９７＝１５１３２０、ｑ２−１＝３６７２−１＝２５×３×２３×６１＝１３４６８８、（ｐ２−１）（ｑ２−１）＝２８×３２×５×１３×２３×６１×９７となるので、ｐ２−１、ｑ２−１のいずれとも互いに素な整数３７０５７８９８０３をとると、
により、３７０５７８９８０３の逆数１３０８２３８７２６７が計算できる。
【００１２】
請求項２に基づく３乗鍵の作例を示す。
３次の正方行列では、法となる素数の３乗が周期となるため、
【００１１】
で定義したところの３乗鍵が必要になる。
二つの素数Ｐ、Ｑを、Ｐ＝７、Ｑ＝１１にとり、Ｐ３−１とＱ３−１の最大公約数ｓをユークリッドの互除法により求める。この場合、ｓ＝３８である。また、７３−１をｓで割った商ｘは９、１１３−１をｓで割った商ｙは３５である。
次に、２整数ｊ、ｋを、それぞれｊ＝３６２０、ｋ＝８９２５にとり、２数Ａ＝ｊｓ２とＢ＝ｋｘｙを作り、Ａ−１とＢ＋１の最大公約数ｒを、同じくユークリッドの互除法により求めると、ｒ＝２９となる。従って、ｊｋｘｙｓ２＋１＝（Ｐ３−１）（Ｑ３−１）＋１＝２９×５０６７５３２５２０６９となる。このｒと対を成すもう一つの約数をｔ（＝５０６７５３２５２０６９）とする。
ｎを適当に定め、ここではｎ＝７５とすると、（Ｐ３−１）（Ｑ３−１）を法として、ｒｎ≡２４３８９＝Ｒ（ｍｏｄ ４５４８６０）、ｔｎ≡３２６７８９＝Ｔ（ｍｏｄ ４５４８６０）が得られる。この２数Ｒ、Ｔが、求める秘密鍵と公開鍵の２数である。
実際、この２数を用い、行列Ａを
として暗号化してみると、
となり、次にｔを用いて復号化すると、
となって元に戻る。
【００１３】
請求項３に基づく複素数を用いた暗号化の例を示す。
先に作成したＰ＝７、Ｑ＝１１、ｓ＝１３、ｓ−１≡３７（ｍｏｄ ６０）を利用する。Ａ＝２３＋４１ｉとすると、Ａ１３≡７６＋４７ｉ＝Ｂ（ｍｏｄ ７７）であり、Ｂ３７≡２３＋４１ｉ（ｍｏｄ ７７）で元に戻る。
【００１４】
請求項４に基づく行列を用いた暗号化の例を示す。
ケーリー・ハミルトンの等式による漸化式を解いた結果からの計算及びコンピューターを使った実験により、２次の整数正方行列Ａのｍ行ｎ列目の要素をａｍｎ、法とする素数をｐとして、（ａ１１＋ａ２２）／２と｛（ａ１１−ａ２２）２＋４ｂｃ｝（１／２）／２が共に整数で、且つ少なくともいずれか一方がｐと互いに素であるとき、Ａ（ｐ−１）≡Ｅ（ｍｏｄ ｐ）となることがわかっている。これが、先に挙げた「特殊なケース」である。
たとえば、
とすると、先に作成した鍵、ＰＱ＝７７、ｓ＝１３、ｓ−１≡３７（ｍｏｄ ６０）により、
であり、次に復号化すると
となり元のＡに戻る。
２乗鍵を使う場合については、先に
【００１１】
において作成した値を使用した例を示す。
行列Ａを
とし、これを法の値１４２７６３（＝３８９×３６７）、ｓ＝３７０５７８９８０３を用いて暗号化すると、
となり、これを更に秘密鍵の値ｔ＝１３０８２３８７２６７を用いて復号化すると、
となり元のＡに戻る。
因みに、Ａの（Ｐ−１）（Ｑ−１）（＝３８８×３６６＝１４２００８）乗を計算しても、
となり、この行列が、法の素数の１乗を周期とはしていないことがわかる。
【００１５】
請求項５に基づく、複素数を用いる場合のディフィー・ヘルマン鍵共有法の作例を示す。
複素数ＡをＡ＝１３＋２０ｉ、共有される法の値の素数ＰをＰ＝２３とし、受信者の秘密鍵を１８、送信者の秘密鍵を２１とすると、受信者の公開鍵ＢはＢ＝１４＋２ｉ（≡Ａ１８（ｍｏｄ２３））、送信者の公開鍵ＣはＣ＝４＋７ｉ（≡Ａ２１（ｍｏｄ ２３））となる。
これより、共有される秘密の複素数Ｄは、Ｂ２１≡Ｃ１８≡Ａ２１×１８≡２＋２１ｉ＝Ｄ （ｍｏｄ ２３）となる。ただし、エルガマル暗号の場合には逆数が必要であるため、このＤの値のよ
【００１６】
請求項５に基づく、行列を用いる場合のディフィー・ヘルマン鍵共有法の実施例を示す。
４次の正方行列Ａを
とし、法の値ＰをＰ＝２３、受信者の秘密鍵を３８、送信者の秘密鍵を５２とすると、受信者の公開鍵Ｂ、送信者の公開鍵Ｃは、それぞれ
となる。
これらの公開鍵を更に送受信者間で共有し、互いに相手の公開鍵を自分の秘密鍵乗することで、
となる行列Ｄを共有できる。エルガマル暗号においても、共通の行列の共有は同じ原理・方法による。ただし、エルガマル暗号では、共有される行列Ｄが、法の値に対して逆行列を求めることのできる行列であることが必要となる。
【産業上の利用可能性】
【００１７】
インターネットによる通信などの産業分野において、セキュリティー効果の向上が期待できる。
【技術分野】
【０００１】
本発明は、暗号技術分野に属する。
【背景技術】
【０００２】
自然数に関する離散対数問題及び素因数分解の非容易性に難読性の根拠を置く暗号技術を背景とする。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
離散対数問題を強化する。また、ＲＳＡ暗号に関しては、鍵を高速に作成する。
【課題を解決するための手段】
【０００４】
ＲＳＡに利用可能な鍵を高速に作成するには、幾つかの方法があり、特許も多く出願されている。
本発明では、以下の二つの方法を提案する。一つ目は、フェルマーの小定理から逆数を求める方法である。
一般的に知られているフェルマーの小定理による逆数計算は、ＲＳＡ暗号が復号可能であることの原理そのものである。それは、Ｐ、Ｑが互いに相異なる２素数であるとき、Ｐ，Ｑのいずれとも互いに素である自然数Ａにより、Ａ（Ｐ−１）（Ｑ−１）≡１（ｍｏｄ ＰＱ）というものである。そこで、（Ｐ−１）（Ｑ−１）を適当な２数に因数分解すれば、ＰＱを法として互いに逆数の関係にある２数を得ることができる。Ｐ単体では、Ａ（Ｐ−１）≡１（ｍｏｄ Ｐ）である。
数学的に、ｒを整数として、Ａｒ≡Ｂ（ｍｏｄ Ｐ）、Ａｒ≡Ｂ（ｍｏｄ Ｑ）のとき、Ａｒ≡Ｂ（ｍｏｄ ＰＱ）である。これも、ＲＳＡが復号可能であることの原理なのだが、もし、ＱをＰに置き換え、法の値をＰ２とすると、フェルマーの小定理では、法の値がＰ２だからといって、単純にＡ（Ｐ−１）（Ｐ−１）≡１（ｍｏｄ Ｐ２）とはならない。たとえば、７２≡１（ｍｏｄ ３）だが、７２≡４（ｍｏｄ ９）であり、また、７４≡７（ｍｏｄ ９）である。素数の整数乗を法とするケースでフェルマーの小定理と同様一般的に１と合同にするのに、単純に異なる素数の組み合わせによる合成数を法とする場合と同じように扱うことでそれを実現することはできない。
そこで、これを解決するために、ｎを自然数として、Ｐｎを法として必ずＡを１と合同にする、一般化されたフェルマーの小定理を導出する必要がある。
と元のフェルマーの小定理に戻る。この結果は、フェルマーの小定理により、任意の整数ｘを用い、Ａ（Ｐ−１）＝Ｐｘ＋１とした上で、この式の両辺をＰ（ｎ−１）乗して右辺を多項式に展開すると、定数１以外の係数が全てＰｎを法としてゼロと合同になることによって示される。
が得られる。従って、書類「特許請求の範囲」に掲げた式
【数１】
のように一般化しても、法の値に含まれる因数の全ての組み合わせについて左辺は１と合同になることになるので、この式はＲＳＡが復号可能であることの原理と同様の理由により、法の値と互いに素である任意の一つの数から、その逆数にあたるもう一つの数を導き出す。
【０００５】
二つ目は、ユークリッドの互除法などの方法を用い、最大公約数から秘密鍵を作成する方法である。
ある２数Ａ、Ｂがあるとして、ＡＢ＋１について考える。このＡＢ＋１を、ＡＢ＋１＝｛（Ａ−１）＋１｝｛（Ｂ＋１）−１｝＋１と書き換え、Ａ−１とＢ＋１の最大公約数を求めてそれをｒとすると、Ａ−１＝ｒａ、Ｂ＋１＝ｒｂとしたとき、ＡＢ＋１＝（ｒａ＋１）（ｒｂ−１）＋１≡１・−１＋１≡０（ｍｏｄ ｒ）となり、ＡＢ＋１はｒを因数に持つことになる。
本発明におけるこの鍵作成法は、この原理を利用したものである。
今、２素数Ｐ、Ｑを考え、ある整数をｇとして、（Ｐｇ−１）と（Ｑｇ−１）の最大公約数を求める。これをｓとし、ｓで（Ｐｇ−１）を割った商をｘ、（Ｑｇ−１）を割った商をｙとする。
すると、（Ｐｇ−１）（Ｑｇ−１）＋１は、（Ｐｇ−１）（Ｑｇ−１）＋１＝ｘｙｓ２＋１となる。
ここで、これらとは別に、２つの自然数ｊ、ｋを用意し、ｊ、ｋ、ｘ、ｙ、ｓ、ｓの６個の数字から幾つかを取り出して掛け合わせてＡとし、残りも掛け合わせてＢとする。ｘ、ｙ、ｓの累乗については、ｊ、ｋにｘ、ｙ、ｓが単数又は複数、因数として含まれる場合と同じにみなす。
このＡ、Ｂについて、先の方法でＡ−１とＢ＋１における最大公約数ｒを求め、これが１の場合は再度別の組み合わせ、または別のｊ、ｋを用意してｒを求めなおし、１でない、有効な値であるｒによって、ＡＢ＋１＝ｊｋｘｙｓ２＋１＝ｊｋ（Ｐｇ−１）（Ｑｇ−１）＋１＝ｒｔと因数分解する。
こうして求められたｒ、ｔにより、ｎを任意の自然数として、ｒｎ≡Ｒ（ｍｏｄ（Ｐｇ−１）（Ｑｇ−１））、ｔｎ≡Ｔ（ｍｏｄ （Ｐｇ−１）（Ｑｇ−１））を求めると、
（ｒｔ）ｎ≡（ｊｋｘｙｓ２＋１）ｎ≡（ｊｋ（Ｐｇ−１）（Ｑｇ−１）＋１）ｎ≡１（ｍｏｄ（Ｐｇ−１）（Ｑｇ−１））となり、どんなｎを選んでも、Ｒ、Ｔは（Ｐｇ−１）（Ｑｇ−１）を法として逆数の関係にある２数となるので、任意に選んだｎにより、自由に秘密鍵と公開鍵を作成することができる。
この方法の利点は、秘密鍵と公開鍵の互いに逆数の関係にある２数を、離散対数問題を用い、任意のｊ、ｋ、ｎによって作成する、という点である。同じ法の値でも、ｊ、ｋ、ｎによっていくらでも異なる組み合わせを作り出すことができる。つまり、この「自由度」が、鍵の安全性を高める効果を持つ、と考えられる。
また、この方法では、Ｐの自然数乗といった周期を持つ行列用の鍵を容易に作成できる。
【０００６】
複素数を用いる暗号は、以下の計算に理論上の根拠を置く。
Ａを、ａ、ｂを整数として、Ａ＝ａ＋ｂｉとなる複素数とする。もう一つの複素数をＢとして、その値をα＋βｉとすると、ＡＢ＝（ａα−ｂβ）＋（ａβ＋ｂα）ｉとなる。
複素数の時計代数は、実部、虚部それぞれに計算されるので、複素数の離散対数では、乗算のほかに、加減算が組み合わされた複雑な計算になることになる。
この性質が、複素数を用いた離散対数問題を、自然数のみによるものよりも強度の高いものとする効果をもっている、と考えられる。
複素数の場合のフェルマーの小定理は、次のようになる。
素数ｐを法として、ａ、ｂ、｜Ａ｜２が全てｐと互いに素であるとき、フェルマーの小定理により、Ａｐ≡ａｐ＋（ｉｂ）ｐ（ｍｏｄ ｐ）である。ｉ４＝１なので、ｐを４で割った余りが１のときは、Ａｐ≡Ａ（ｍｏｄ ｐ）となるが、ｐを４で割った余りが３のときは、Ａｐ≡ａ−ｉｂ（ｍｏｄ ｐ）である。
そこで、ｐ２を周期と見ると、ｐを４で割った剰余の値によらず、Ａｐ２≡Ａ（ｍｏｄ ｐ）である。ここで、｜Ａ｜２がｐと互いに素なので、Ａにはｐを法として逆数が存在する。従って、Ａ（ｐ２−１）≡１（ｍｏｄ ｐ）となる。これが、複素数の場合のフェルマーの小定理である。
ただし、２素数Ｐ、Ｑの合成数によりＰＱを法とする場合には、ｓｔ≡１（ｍｏｄ（Ｐ−１）（Ｑ−１））となるｓｔが、（Ｐ−１）、（Ｑ−１）が共に偶数であることにより４を因数に持っため、Ｐ、Ｑの値によらず、Ａｓｔ≡Ａ（ｍｏｄ ＰＱ）となるので、従来のＲＳＡ暗号と同じように計算できる。
【０００７】
一方、行列を用いる方法については、以下のような行列によるモデュラ代数方程式の解法に基づく。
最初に、下記のような、モデュラ連立方程式を考える。
この連立方程式を解くには、次のようにする。
まず、行列（この行列をＡとする）とベクトルの積の形に式を書き換える。
【数２】
次に、１１を法としてＡと合同な整数逆行列を、フェルマーの小定理により求める。
Ａの行列式の値は｜Ａ｜＝４７で、これは法の値と互いに素である。
従って、フェルマーの小定理により、１１を法として４７−１と合同な整数を求めることができる。その値は、４７−１≡４７（１１−１）−１≡４７９≡４（ｍｏｄ １１）である。従って、
となる。
この逆行列を
【数２】
の両辺に左から掛けることにより、解
が得られる。
この計算に基づき、行列のモデュラは定義される。厳密な定義は、請求項４の演算規則２である。
そして、この行列のモデュラにより、行列の離散対数問題を考えることができる。行列の離散対数問題は、自然数を一次の正方行列とみなすことが可能であることから、旧来の自然数のみに関する離散対数問題よりもさらに高度で解きにくいものであろう、ということが予想される。実際、実数には対数に対してその逆関数（一般にｌｏｇで表される）が存在するが、行列ではそれが存在しない。複素数による離散対数問題よりもさらに高度な離散対数問題が、行列の離散対数問題である。
行列における一般的なフェルマーの小定理（ただし、実施例で挙げるような特殊なケースが存在する）は、Ｅｎをｎ次の単位行列、行列Ａｎを、全ての要素が整数で、ｐを法として逆行列が存在するｎ次の正方行列としたとき、いくつかのサンプルによる実験結果から、
であろう、と予想している。この式において、ｎが１のときは、従来の自然数に関するフェルマーの小定理に戻る。ただし、ｎが１のときはＡ１そのものがｐと互いに素であることが条件であるのに対し、ｎが２以上の場合については、Ａｎの各要素とではなく、Ａｎの各要素が組み合わされて作られる数値とｐが互いに素であることが求められ、その条件は複雑で、また、ｎによって異なる。
この行列のフェルマーの小定理を利用することにより、行列のＲＳＡ暗号を作ることができる。
参考として、要素が複素数である場合については、コンピューターを使った実験結果として、法の素数Ｐが４を法として１と合同になるときは整数のみを要素とする場合と同じ結果になるが、法の素数Ｐが４を法として３と合同となるケースについては、まだ明確なことはわかっていない。また、２素数の積を法とするケースについては、これら２素数が４を法として共に１と合同になる場合と、それぞれが１、３と合同になるケースは、要素が全て実整数の場合のフェルマーの小定理と同じ結果になるが、２素数が共に４を法として３と合同になるケースについては、明確なことはわかっていない。
【発明の効果】
【０００８】
暗号文の安全性を高めることができる。また、請求項１および２については、計算能力の高くないハードウェア上でも、鍵を高速に作成することができる。
【発明を実施するための最良の形態】
【０００９】
携帯電話のような計算能力の弱い端末も含めた、さまざまな種類の端末が混在するネットワーク上での利用が有効である。
【実施例】
【００１０】
請求項１に基づく鍵の作例を示す。
ｐ＝７（＝２×３＋１）、ｑ＝１１（＝２×５＋１）とし、これらの積であるｐｑ＝７７と１３を公開鍵とし、これらに対する秘密鍵である１３の逆数ｔを、次のように求める。
１３−１≡１３｛２（３−１）（５−１）−１｝≡１３１５≡３７＝ｔ （ｍｏｄ （７−１）（１１−１）＝６０）
この計算では、ｐ−１とｑ−１を、２とその他の予めフェルマーテストなどの方法にかけて見つけた素数により生成する。ここでは、必須の２以外の素数として３及び５を選び、それらから７、１１を２つの素数としている。これら３、５により、（７−１）（１１−１）は容易に因数分解されて２×３×２×５となる。３と５を予め探しておくことにより、あとから（ｐ−１）、（ｑ−１）を因数分解することなく、容易に６０を法として逆数を計算することができる。
実際、この鍵を用い、６を暗号化したい元の数値として実験してみると、６１３≡６２（ｍｏｄ ７７）であり、これを秘密鍵３７を用いて復号化すると、６２３７≡６（ｍｏｄ ７７）となって元の数値が復元される。
【００１１】
請求項１に基づく２乗鍵の作例を示す。ここでいう２乗鍵とは、素数の２乗を周期とする暗号化を行う場合の鍵である。
一般的に、ａ、ｂ、ｃ、ｄ、α、β、γを全て整数とし、ｄ＝αβ＋γ且つａ≡α（ｍｏｄｄ）、ｂ≡β（ｍｏｄ ｄ）、ｃ≡γ（ｍｏｄ ｄ）であるとき、ａｂ＋ｃ≡αβ＋γ＝ｄ≡０（ｍｏｄ ｄ）より、任意の整数をｘとして、ａｂ＋ｃ＝ｄｘとなる。つまり、この関係式を利用することで、加減乗算が組み合わされた数値の因数に関する関係式を得ることができる。
を得ることができる。こうしてｐともう一つの素数を作成することにより、公開鍵の法の値と、秘密鍵と公開鍵における互いに逆数同士の２数を得ることができる。
今、ｐ１＝２×２＋１＝５、ｐ２＝２×２×３＋１＝１３、ｔを任意の整数としてΠｎＰｎ＋１＝２（５×１３×ｔ＋５×９＋１３×４）＋１とすると、５×９≡６（ｍｏｄ １３）、１３×４≡２（ｍｏｄ ５）より、ΠｎＰｎ＋１≡２×６＋１（ｍｏｄ １３）、ΠｎＰｎ＋１≡２×２＋１（ｍｏｄ ５）となる。つまり、任意のｔについて、ΠｎＰｎ＋１は５と１３を因数に持つようになる。
れる。９７は素数なので、これにより、Ｐ１＝２、Ｐ２＝９７という２素数が得られたことになる。また、このときｐ＝２×２×９７＋１＝３８９となり、公開鍵の作成に必要な法の値のための、求める一つ目の素数が得られたことになる。
もう一つの素数ｑは、簡単のため、ｑ＝２×３×６１＋１＝３６７とする。
これらのｐ、ｑにより、ｐ２−１＝２３×３×５×１３×９７＝１５１３２０、ｑ２−１＝３６７２−１＝２５×３×２３×６１＝１３４６８８、（ｐ２−１）（ｑ２−１）＝２８×３２×５×１３×２３×６１×９７となるので、ｐ２−１、ｑ２−１のいずれとも互いに素な整数３７０５７８９８０３をとると、
により、３７０５７８９８０３の逆数１３０８２３８７２６７が計算できる。
【００１２】
請求項２に基づく３乗鍵の作例を示す。
３次の正方行列では、法となる素数の３乗が周期となるため、
【００１１】
で定義したところの３乗鍵が必要になる。
二つの素数Ｐ、Ｑを、Ｐ＝７、Ｑ＝１１にとり、Ｐ３−１とＱ３−１の最大公約数ｓをユークリッドの互除法により求める。この場合、ｓ＝３８である。また、７３−１をｓで割った商ｘは９、１１３−１をｓで割った商ｙは３５である。
次に、２整数ｊ、ｋを、それぞれｊ＝３６２０、ｋ＝８９２５にとり、２数Ａ＝ｊｓ２とＢ＝ｋｘｙを作り、Ａ−１とＢ＋１の最大公約数ｒを、同じくユークリッドの互除法により求めると、ｒ＝２９となる。従って、ｊｋｘｙｓ２＋１＝（Ｐ３−１）（Ｑ３−１）＋１＝２９×５０６７５３２５２０６９となる。このｒと対を成すもう一つの約数をｔ（＝５０６７５３２５２０６９）とする。
ｎを適当に定め、ここではｎ＝７５とすると、（Ｐ３−１）（Ｑ３−１）を法として、ｒｎ≡２４３８９＝Ｒ（ｍｏｄ ４５４８６０）、ｔｎ≡３２６７８９＝Ｔ（ｍｏｄ ４５４８６０）が得られる。この２数Ｒ、Ｔが、求める秘密鍵と公開鍵の２数である。
実際、この２数を用い、行列Ａを
として暗号化してみると、
となり、次にｔを用いて復号化すると、
となって元に戻る。
【００１３】
請求項３に基づく複素数を用いた暗号化の例を示す。
先に作成したＰ＝７、Ｑ＝１１、ｓ＝１３、ｓ−１≡３７（ｍｏｄ ６０）を利用する。Ａ＝２３＋４１ｉとすると、Ａ１３≡７６＋４７ｉ＝Ｂ（ｍｏｄ ７７）であり、Ｂ３７≡２３＋４１ｉ（ｍｏｄ ７７）で元に戻る。
【００１４】
請求項４に基づく行列を用いた暗号化の例を示す。
ケーリー・ハミルトンの等式による漸化式を解いた結果からの計算及びコンピューターを使った実験により、２次の整数正方行列Ａのｍ行ｎ列目の要素をａｍｎ、法とする素数をｐとして、（ａ１１＋ａ２２）／２と｛（ａ１１−ａ２２）２＋４ｂｃ｝（１／２）／２が共に整数で、且つ少なくともいずれか一方がｐと互いに素であるとき、Ａ（ｐ−１）≡Ｅ（ｍｏｄ ｐ）となることがわかっている。これが、先に挙げた「特殊なケース」である。
たとえば、
とすると、先に作成した鍵、ＰＱ＝７７、ｓ＝１３、ｓ−１≡３７（ｍｏｄ ６０）により、
であり、次に復号化すると
となり元のＡに戻る。
２乗鍵を使う場合については、先に
【００１１】
において作成した値を使用した例を示す。
行列Ａを
とし、これを法の値１４２７６３（＝３８９×３６７）、ｓ＝３７０５７８９８０３を用いて暗号化すると、
となり、これを更に秘密鍵の値ｔ＝１３０８２３８７２６７を用いて復号化すると、
となり元のＡに戻る。
因みに、Ａの（Ｐ−１）（Ｑ−１）（＝３８８×３６６＝１４２００８）乗を計算しても、
となり、この行列が、法の素数の１乗を周期とはしていないことがわかる。
【００１５】
請求項５に基づく、複素数を用いる場合のディフィー・ヘルマン鍵共有法の作例を示す。
複素数ＡをＡ＝１３＋２０ｉ、共有される法の値の素数ＰをＰ＝２３とし、受信者の秘密鍵を１８、送信者の秘密鍵を２１とすると、受信者の公開鍵ＢはＢ＝１４＋２ｉ（≡Ａ１８（ｍｏｄ２３））、送信者の公開鍵ＣはＣ＝４＋７ｉ（≡Ａ２１（ｍｏｄ ２３））となる。
これより、共有される秘密の複素数Ｄは、Ｂ２１≡Ｃ１８≡Ａ２１×１８≡２＋２１ｉ＝Ｄ （ｍｏｄ ２３）となる。ただし、エルガマル暗号の場合には逆数が必要であるため、このＤの値のよ
【００１６】
請求項５に基づく、行列を用いる場合のディフィー・ヘルマン鍵共有法の実施例を示す。
４次の正方行列Ａを
とし、法の値ＰをＰ＝２３、受信者の秘密鍵を３８、送信者の秘密鍵を５２とすると、受信者の公開鍵Ｂ、送信者の公開鍵Ｃは、それぞれ
となる。
これらの公開鍵を更に送受信者間で共有し、互いに相手の公開鍵を自分の秘密鍵乗することで、
となる行列Ｄを共有できる。エルガマル暗号においても、共通の行列の共有は同じ原理・方法による。ただし、エルガマル暗号では、共有される行列Ｄが、法の値に対して逆行列を求めることのできる行列であることが必要となる。
【産業上の利用可能性】
【００１７】
インターネットによる通信などの産業分野において、セキュリティー効果の向上が期待できる。
【特許請求の範囲】
【請求項１】
Ｐ、Ｑを互いに相異なる２素数、ｐ１、ｐ２、・・・、ｐｎを互いに相異なるｎ個の素数、ａ１、
によりＬの逆数を計算するＲＳＡ暗号用鍵作成法。
【請求項２】
Ｐ、Ｑを互いに相異なる２素数、ｇを任意の自然数とし、（Ｐｇ−１）（Ｑｇ−１）＝ｘｙｓ２とする。ｓは、（Ｐｇ−１）と（Ｑｇ−１）の最大公約数、ｘ、ｙは（Ｐｇ−１）と（Ｑｇ−１）それぞれにおけるｓ以外の因数である。
任意の二つの自然数ｊ、ｋにより（二つ以上の場合については、それらが二組に分けられて事前に掛け合わされてｊ、ｋとなっているとみなし、また、ｘ、ｙ、ｓが、ｊ、ｋのそれぞれに単数または複数、因数として含まれる場合もあるものとする）、ｊ、ｋ、ｘ、ｙ、ｓを任意の組み合わせで二組に分け、それぞれの組においてこれらを掛け合わせて２数ａ、ｂを得、（ａ−１）と（ｂ＋１）の最大公約数を求めることにより、（Ｐｇ−１）（Ｑｇ−１）＋１の因数の一つｒを得、さらにｒで（Ｐｇ−１）（Ｑｇ−１）＋１を割ってもう一つの（Ｐｇ−１）（Ｑｇ−１）＋１の因数ｔを得る。
このｒ、ｔに対し、更にｎを任意の自然数として、ｒｎ≡Ｒ（ｍｏｄ （Ｐｇ−１）（Ｑｇ−１））、ｔｎ≡Ｔ（ｍｏｄ （Ｐｇ−１）（Ｑｇ−１））を計算することにより、秘密鍵と公開鍵の、累乗を作るための互いに逆数関係ある２数Ｒ、Ｔを得る、ＲＳＡ暗号用鍵作成法。
【請求項３】
ａ、ｂを、ｋ、α、βを全て整数として、ａ≡α（ｍｏｄ ｋ）、ｂ≡β（ｍｏｄ ｋ）を満たす整数とし、Ａを、Ａ＝ａ＋ｂｉ（ｉは虚数単位）である複素数とするとき、Ａはｋを法としてα＋βｉと合同である（Ａ≡α＋βｉ（ｍｏｄ ｋ））と定義する。この演算規則を、「演算規則１」とする。
この演算規則１に基づき、ｂ≠０のとき、Ｐ、Ｑを、ａ、ｂのいずれとも互いに素な互いに相異なる２素数とし、ｓｔ≡１（ｍｏｄ （Ｐ−１）（Ｑ−１））となる整数ｓ、ｔにより、Ａｓ≡Ｂ（ｍｏｄ ＰＱ）によるＢを暗号文とし、Ｂｔ≡Ａ（ｍｏｄ ＰＱ）で復号化することにより、暗号化及び復号化を行う、ｓ、ＰＱを公開鍵とし、ｔを秘密鍵とする改良型複素数ＲＳＡ暗号。
【請求項４】
Ａを２次以上の正方行列とする。Ａのｍ行ｎ列目の要素をａｍｎ（ａｍｎは整数、純虚数、または複素数）とし、ａｍｎが純虚数又は複素数の場合には請求項３の演算規則１に基づき、整数ｋを法として、ａｍｎ≡ｂｍｎ（ｍｏｄ ｋ）となるｂｍｎをｍ行ｎ列目の要素とする行列をＢとする。これを、ｋを法としてＡはＢと合同である（Ａ≡Ｂ（ｍｏｄ ｋ））と定義する。この演算規則を「演算規則２」とする。
個々の要素が整数、純虚数、複素数のいずれかである正方行列Ａが、互いに相異なる２素数をＰ、Ｑ、任意の整数をｒとして、この演算規則２に基づき、Ａ｛（Ｐｒ−１）（Ｑｒ−１）＋１｝≡Ａ（ｍｏｄ ＰＱ）を満たすとき、ｓｔ≡１（ｍｏｄ （Ｐｒ−１）（Ｑｒ−１））となるｓ、ｔにより、Ａｓ≡Ｂ（ｍｏｄ ＰＱ）によるＢを暗号文とし、Ｂｔ≡Ａ（ｍｏｄ ＰＱ）により復号化を行う、ｓ、ＰＱを公開鍵とし、ｔを秘密鍵とする、改良型行列ＲＳＡ暗号。
【請求項４】
送信者の秘密の整数をｓ、受信者の秘密の整数をｔ、送信者と受信者の間で共有される、虚部がゼロでない複素数または任意の２次以上の正方行列（個々の要素は、整数、純虚数、複素数のいずれか）をＡ、同様に送信者と受信者の間で共有される法の値（素数・合成数を問わない）をｋ、請求項３の演算規則１及び請求項４の演算規則２により計算される、送信者の公開鍵をＢ（≡Ａｓ（ｍｏｄ ｋ））、受信者の公開鍵をＣ（≡Ａｔ（ｍｏｄ ｋ））とし、送信者はＣｓ≡Ｄ（ｍｏｄ ｋ）を、受信者はＢｔ≡Ｄ（ｍｏｄ ｋ）を計算することにより、受信者と送信者の間で共通の秘密の値Ｄを共有するようにしたディフィー・ヘルマン鍵共有法及びエルガマル暗号。
【請求項１】
Ｐ、Ｑを互いに相異なる２素数、ｐ１、ｐ２、・・・、ｐｎを互いに相異なるｎ個の素数、ａ１、
によりＬの逆数を計算するＲＳＡ暗号用鍵作成法。
【請求項２】
Ｐ、Ｑを互いに相異なる２素数、ｇを任意の自然数とし、（Ｐｇ−１）（Ｑｇ−１）＝ｘｙｓ２とする。ｓは、（Ｐｇ−１）と（Ｑｇ−１）の最大公約数、ｘ、ｙは（Ｐｇ−１）と（Ｑｇ−１）それぞれにおけるｓ以外の因数である。
任意の二つの自然数ｊ、ｋにより（二つ以上の場合については、それらが二組に分けられて事前に掛け合わされてｊ、ｋとなっているとみなし、また、ｘ、ｙ、ｓが、ｊ、ｋのそれぞれに単数または複数、因数として含まれる場合もあるものとする）、ｊ、ｋ、ｘ、ｙ、ｓを任意の組み合わせで二組に分け、それぞれの組においてこれらを掛け合わせて２数ａ、ｂを得、（ａ−１）と（ｂ＋１）の最大公約数を求めることにより、（Ｐｇ−１）（Ｑｇ−１）＋１の因数の一つｒを得、さらにｒで（Ｐｇ−１）（Ｑｇ−１）＋１を割ってもう一つの（Ｐｇ−１）（Ｑｇ−１）＋１の因数ｔを得る。
このｒ、ｔに対し、更にｎを任意の自然数として、ｒｎ≡Ｒ（ｍｏｄ （Ｐｇ−１）（Ｑｇ−１））、ｔｎ≡Ｔ（ｍｏｄ （Ｐｇ−１）（Ｑｇ−１））を計算することにより、秘密鍵と公開鍵の、累乗を作るための互いに逆数関係ある２数Ｒ、Ｔを得る、ＲＳＡ暗号用鍵作成法。
【請求項３】
ａ、ｂを、ｋ、α、βを全て整数として、ａ≡α（ｍｏｄ ｋ）、ｂ≡β（ｍｏｄ ｋ）を満たす整数とし、Ａを、Ａ＝ａ＋ｂｉ（ｉは虚数単位）である複素数とするとき、Ａはｋを法としてα＋βｉと合同である（Ａ≡α＋βｉ（ｍｏｄ ｋ））と定義する。この演算規則を、「演算規則１」とする。
この演算規則１に基づき、ｂ≠０のとき、Ｐ、Ｑを、ａ、ｂのいずれとも互いに素な互いに相異なる２素数とし、ｓｔ≡１（ｍｏｄ （Ｐ−１）（Ｑ−１））となる整数ｓ、ｔにより、Ａｓ≡Ｂ（ｍｏｄ ＰＱ）によるＢを暗号文とし、Ｂｔ≡Ａ（ｍｏｄ ＰＱ）で復号化することにより、暗号化及び復号化を行う、ｓ、ＰＱを公開鍵とし、ｔを秘密鍵とする改良型複素数ＲＳＡ暗号。
【請求項４】
Ａを２次以上の正方行列とする。Ａのｍ行ｎ列目の要素をａｍｎ（ａｍｎは整数、純虚数、または複素数）とし、ａｍｎが純虚数又は複素数の場合には請求項３の演算規則１に基づき、整数ｋを法として、ａｍｎ≡ｂｍｎ（ｍｏｄ ｋ）となるｂｍｎをｍ行ｎ列目の要素とする行列をＢとする。これを、ｋを法としてＡはＢと合同である（Ａ≡Ｂ（ｍｏｄ ｋ））と定義する。この演算規則を「演算規則２」とする。
個々の要素が整数、純虚数、複素数のいずれかである正方行列Ａが、互いに相異なる２素数をＰ、Ｑ、任意の整数をｒとして、この演算規則２に基づき、Ａ｛（Ｐｒ−１）（Ｑｒ−１）＋１｝≡Ａ（ｍｏｄ ＰＱ）を満たすとき、ｓｔ≡１（ｍｏｄ （Ｐｒ−１）（Ｑｒ−１））となるｓ、ｔにより、Ａｓ≡Ｂ（ｍｏｄ ＰＱ）によるＢを暗号文とし、Ｂｔ≡Ａ（ｍｏｄ ＰＱ）により復号化を行う、ｓ、ＰＱを公開鍵とし、ｔを秘密鍵とする、改良型行列ＲＳＡ暗号。
【請求項４】
送信者の秘密の整数をｓ、受信者の秘密の整数をｔ、送信者と受信者の間で共有される、虚部がゼロでない複素数または任意の２次以上の正方行列（個々の要素は、整数、純虚数、複素数のいずれか）をＡ、同様に送信者と受信者の間で共有される法の値（素数・合成数を問わない）をｋ、請求項３の演算規則１及び請求項４の演算規則２により計算される、送信者の公開鍵をＢ（≡Ａｓ（ｍｏｄ ｋ））、受信者の公開鍵をＣ（≡Ａｔ（ｍｏｄ ｋ））とし、送信者はＣｓ≡Ｄ（ｍｏｄ ｋ）を、受信者はＢｔ≡Ｄ（ｍｏｄ ｋ）を計算することにより、受信者と送信者の間で共通の秘密の値Ｄを共有するようにしたディフィー・ヘルマン鍵共有法及びエルガマル暗号。
【公開番号】特開２００７−５２３８６（Ｐ２００７−５２３８６Ａ）
【公開日】平成１９年３月１日（２００７．３．１）
【国際特許分類】
【出願番号】特願２００５−２６５９８９（Ｐ２００５−２６５９８９）
【出願日】平成１７年８月１７日（２００５．８．１７）
【出願人】（５０１３９９７０６）
【Ｆターム（参考）】
【公開日】平成１９年３月１日（２００７．３．１）
【国際特許分類】
【出願日】平成１７年８月１７日（２００５．８．１７）
【出願人】（５０１３９９７０６）
【Ｆターム（参考）】
[ Back to top ]