(57)【要約】【課題】２次双曲線群を使用する鍵生成方法、復号方法、署名検証方法、鍵ストリーム生成方法及びそれらの装置の総称である双曲線暗号の鍵を具体的に生成する。【解決手段】双曲線暗号の鍵を生成するための２次双曲線群ＨＣの曲線パラメータを、ステップＳ１〜Ｓ５により設定する。ステップＳ１で、法ｎ＝ｐｈ（ｈ：自然数）、ｋ＝ｐｈ−１（ｐ＋１）／２の関係を満たす素数ｐ及び位数ｋを定め、ステップＳ２で、判別式Ｄ／４＝ｃ２＋４ａが素数ｐに対し平方非剰余であるように曲線パラメータａ及びｃを定め、ステップＳ３，Ｓ４で、固定元Ｐ（ｄ）を与えるパラメータｄに関しｄ（ｄ＋ｃ）−ａが素数ｐに対し平方非剰余であるように定め、ステップＳ５で、ベースポイントＰ（ｘ）を与えるパラメータｘ（ｘ≠ｄ）に関しｘ（ｘ＋ｃ）−ａが素数ｐに対し平方非剰余であるように定める。【選択図】図１（Ｂ）
2009223035.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）スカラー係数である秘密鍵を設定すると共に、有限環上で定義された整数論的関数の従属変数ｙと当該整数論的関数の独立変数ｘとの組（ｘ，ｙ）からなる集合のなす有限可換群の元を第１の公開鍵として選択するステップと、
（ｂ）前記第１の公開鍵に対して前記有限可換群において定義される加法演算を少なくとも１回施すことにより前記第１の公開鍵を前記秘密鍵でスカラー倍して第２の公開鍵を生成するステップとを有し、
前記整数論的関数は、前記有限環上で定義された２次多項式の分母と前記有限環上で定義された１次多項式の分子とからなる２次双曲線関数であり、
前記ステップ（ｂ）の加法演算において、前記有限可換群の第１及び第２の元を加算する際には、前記第１及び第２の元を解として有する１次関数と前記２次双曲線関数との共通解のうち前記第１及び第２の元を除く第３の元が定まるとき、前記第３の元と前記有限可換群の所定の固定元とを解として有する１次関数と前記２次双曲線関数との共通解のうち前記第３の元と前記所定の固定元とを除く第４の元を当該加算結果として算出する双曲線暗号の鍵生成方法において、
前記有限可換群が剰余環Ｚ／ｎＺで、前記２次双曲線関数が
【数１】
2009223035.tif 000097
である場合に、
第１のステップで、法ｎ＝ｐｈ（ｈ：自然数）である素数ｐを定め、
第２のステップで、判別式Ｄ／４＝ｃ２＋４ａが素数ｐに対し平方非剰余であるように曲線パラメータａ及びｃを定め、
第３のステップで、前記固定元Ｐ（ｄ）を与えるパラメータｄに関しｄ（ｄ＋ｃ）−ａが素数ｐに対し平方非剰余であるように定め、
第４にのステップで、ベースポイントＰ（ｘ）を与えるパラメータｘ（ｘ≠ｄ）に関しｘ（ｘ＋ｃ）−ａが素数ｐに対し平方非剰余であるように定めることを特徴とする双曲線暗号の鍵生成方法。
【請求項２】
（ａ）スカラー係数である秘密鍵を設定すると共に、有限環上で定義された整数論的関数の従属変数ｙと当該整数論的関数の独立変数ｘとの組（ｘ，ｙ）からなる集合のなす有限可換群の元を第１の公開鍵として選択するステップと、
（ｂ）前記第１の公開鍵に対して前記有限可換群において定義される加法演算を少なくとも１回施すことにより前記第１の公開鍵を前記秘密鍵でスカラー倍して第２の公開鍵を生成するステップとを有し、
前記整数論的関数は、前記有限環上で定義された２次多項式の分母と前記有限環上で定義された１次多項式の分子とからなる２次双曲線関数であり、
前記ステップ（ｂ）の加法演算において、前記有限可換群の第１及び第２の元を加算する際には、前記第１及び第２の元を解として有する１次関数と前記２次双曲線関数との共通解のうち前記第１及び第２の元を除く第３の元が定まるとき、前記第３の元と前記有限可換群の所定の固定元とを解として有する１次関数と前記２次双曲線関数との共通解のうち前記第３の元と前記所定の固定元とを除く第４の元を当該加算結果として算出する双曲線暗号の設計方法において、
前記有限可換群が剰余環Ｚ／ｎＺで、前記２次双曲線関数が
【数２】
2009223035.tif 000098
である場合に、
第１のステップで、法ｎを素数ｐ１，ｐ２の積として定め、
第２のステップで、判別式Ｄ／４＝ｃ２＋４ａが前記素数の何れに対しても平方非剰余であるように曲線パラメータａ及びｃを定め、
第３のステップで、前記固定元Ｐ（ｄ）を与える新たなパラメータｄに関しｄ（ｄ＋ｃ）−ａが前記素数の何れに対しても平方非剰余であるように定め、
第４のステップで、ベースポイントＰ（ｘ）を与えるパラメータｘ（ｘ≠ｄ）に関しｘ（ｘ＋ｃ）−ａが前記素数の何れに対しても平方非剰余であるように定めることを特徴とする双曲線暗号の鍵生成方法。
【請求項３】
（ａ）スカラー係数である秘密鍵を設定すると共に、有限環上で定義された整数論的関数の従属変数ｙと当該整数論的関数の独立変数ｘとの組（ｘ，ｙ）からなる集合のなす有限可換群の元を第１の公開鍵として選択するステップと、
（ｂ）前記第１の公開鍵に対して前記有限可換群において定義される加法演算を少なくとも１回施すことにより前記第１の公開鍵を前記秘密鍵でスカラー倍して第２の公開鍵を生成するステップとを有し、
前記整数論的関数は、前記有限環上で定義された２次多項式の分母と前記有限環上で定義された１次多項式の分子とからなる２次双曲線関数であり、
前記ステップ（ｂ）の加法演算において、前記有限可換群の第１及び第２の元を加算する際には、前記第１及び第２の元を解として有する１次関数と前記２次双曲線関数との共通解のうち前記第１及び第２の元を除く第３の元が定まるとき、前記第３の元と前記有限可換群の所定の固定元とを解として有する１次関数と前記２次双曲線関数との共通解のうち前記第３の元と前記所定の固定元とを除く第４の元を前記加算結果として算出する双曲線暗号の鍵生成方法において、
前記有限可換群が剰余環Ｚ／ｎＺで、前記２次双曲線関数が
【数３】
2009223035.tif 000099
である場合に、
前記加法演算を計算するに際し、分子の演算と分母の演算を区別することにより、法ｎに係る逆元の演算を後回しにすることを特徴とする双曲線暗号の鍵生成方法。
【請求項４】
請求項３記載の双曲線暗号の鍵生成方法において、
前記加法演算に係る関数値が特定の値に一致するか否かを判定する場合には、前記関数値の分子と前記特定の値の分母の積と前記関数値の分母と前記特定の値の分子の積とが一致することにより判定することを特徴とする双曲線暗号の鍵生成方法。
【請求項５】
請求項１又は２記載の双曲線暗号の鍵方法において、
前記有限可換群が剰余環Ｚ／ｎＺで、前記２次双曲線関数が
2009223035.tif 000100
である場合に、
第１のステップで、法ｎ＝ｐｈ（ｈ；自然数）である素数ｐ、若しくは法ｎを素数ｐ１，ｐ２の積として定め、
第２のステップで、判別式Ｄ／４＝ｃ２＋４ａが前記素数の何れか若しくは全てに対し平方剰余であるように曲線パラメータａ及びｃを定め、
第３のステップで、前記固定元Ｐ（ｄ）を与える新たなパラメータｄに関しｄ（ｄ＋ｃ）−ａが前記素数の何れに対しても平方非剰余であるように定め、
第４のステップで、ベースポイントＰ（ｘ）を与えるパラメータｘ（ｘ≠ｄ）に関しｘ（ｘ＋ｃ）−ａが前記素数の何れに対しても平方非剰余であるように定め、
前記加法演算を請求項３記載の鍵生成方法で行うことを特徴とする双曲線暗号の鍵生成方法。
【請求項６】
請求項２又は５記載の双曲線暗号の鍵生成方法において、
第１のステップで、平方剰余の相互法則により（Ｄ／ｎ）＝＋１又は（Ｄ／ｎ）＝−１を満たすＤ値で奇数であるものを集め、
第２のステップで、判別式Ｄ／４＝ｃ２＋４ａに前記Ｄ値を割り当てると共に、曲線パラメータａ及びｃを定め、
第３のステップで、適当なｘ値につきτ（ｘ）＝ｘ（ｘ＋ｃ）−ａを計算することによりτ（ｘ）が奇数であるものの中から、（τ（ｘ）／ｎ）＝＋１を満たすｘ値を集め、
第４のステップで、前記ｘ値の中から前記固定元Ｐ（ｄ）を与えるパラメータｄ、及びベースポイントＰ（ｘ）を与えるパラメータｘ（ｘ≠ｄ）を選択し、
第５のステップで、請求項２又は５記載の鍵生成方法により前記パラメータにより特定された拡張２次双曲線群若しくは拡張２次双曲線半群の位数計算を行い、
第６のステップで、前記位数計算により収集された位数から前記素数ｐ１，ｐ２を決めることにより法ｎの素因数を求める方法であって、
前記素因数によりＲＳＡ暗号の公開鍵から秘密鍵を求めることを特徴とする双曲線暗号の鍵生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、拡張された２次双曲線群の離散対数を利用した双曲線暗号の鍵生成方法に関するものである。
【背景技術】
【０００２】
１９８０年代の半ばに楕円曲線群を利用した公開鍵暗号の形成方法が提案され、近年日本において盛んに研究が行われている。楕円曲線暗号では離散対数（discrete  logarithm）問題を基礎とする。原始根ｇの指数がαであるとき値ｇαを知っても、その取り扱うビット数が大きい場合には、指数αを知ることは難しい、というものである。楕円曲線暗号は１０２４ビットのＲＳＡ暗号が形成する解読困難性を１６３ビットで達成できるとされ、携帯機器、特にＣＰＵ（中央処理装置）速度の遅いＩＣ（集積回路）カード等に搭載することが期待されている。
【０００３】
しかし、楕円曲線は幾何学的特徴が複雑であり、相当の幾何学的知識を有する者でなければ超特異楕円曲線（super-singular  elliptic  curve）等を理解することは難しく、この意味で楕円曲線群の安易な利用には限界がある。又、楕円曲線群の位数の確定もできていない。例えば、著名なHasseの不等式（１９３４）は、楕円曲線群の位数が法ｐに近い範囲にあることを証明するが、当該楕円曲線のパラメータに依存して位数が変動する。そこで実際にはその範囲にある素数を調べ、それがゼロ元（無限遠点）以外の元と掛け合わせて、ゼロ元になるかの検証を行う等の素数位数の判定を行う作業が必要になる。
【０００４】
そこで、このような不都合を解決するために、本願発明者は、平成１９年２月２０日付け提出の特許出願（特願２００７−３９７８０号、この特許出願は出願公開前の非公知状態、以下「先の特許出願」という。）において、「二次双曲線群を使用する鍵生成方法、復号方法、署名検証方法、鍵ストリーム生成方法および装置」の発明を開示し、楕円曲線暗号に替わり得る新たな暗号（本明細書では「双曲線暗号」という。）を提案した。
【０００５】
即ち、双曲線暗号とは、２次双曲線群を使用する鍵生成方法、復号方法、署名検証方法、鍵ストリーム生成方法及び装置の総称である。２次双曲線群は新たに発見された群であるので、群構造の詳細についてはまだ明らかでない部分もある。しかし、離散対数を基礎とし、群位数が一定であり、設計が容易で、且つ、秘密鍵変動等により安全性を高めることができるという性質を有するために楕円曲線群に替わり得る可能性を有している。
ここで、２次双曲線群とは、例えば
【０００６】
【数４】
2009223035.tif 000003
【０００７】
という整数論的関数ｙと直線との交点が形成する３根、ｘ１，ｘ２，ｘ３の間に定義された演算に関し、一定の制限のもとで構成される有限環上の有限可換群である。（３−１）式の分子の１次式及び分母の２次式で使用される係数（以下、「曲線パラメータ」という。）は有限環、例えば剰余環Ｚ／ｐＺの元である。又、分母は割り算ではなく剰余環Ｚ／ｐＺの逆元を意味するが、分母及び分子の共通する要素を取り除き、若しくは追加する操作で不変である性質が共通するので、簡便さを生かして割り算の表記を採用している。実際には
y=(dx＋e)(ax2＋bx＋c)−1(a,b,c,d,e,x,y∈Z/pZ)  ・・・・（３−２）
の意味である。（３−２）式は整数論的関数ｙで必ずしも実数上で定義される２次双曲線と同じではないが、２次双曲線と同様に実質的には３次関数として機能することから、本明細書では便宜上「２次双曲線」と呼ぶことにする。
【０００８】
一般に３次曲線y=(x−x1)(x−x2)(x−x3)の３根は、根と係数の関係から
x1x2x3=α  や  x1＋x2＋x3=β
の関係を有するために、点ｘ１と点ｘ２の２項演算の結果を点ｘ３とするように群演算を定義できる。しかし、３根の積や和が一定であるような簡便な関係では乗法群しか構成することはできない。これに対し、
x1x2x3=f(x1,x2)
のように複合的な関係を有するときには、離散対数の関係を築くことができる。前記（３−１）式、（３−２）式で示される直線との交点が形成する３根が、正にその構造を有している。なお、２次双曲線群における群演算（この演算記号を「＋」で表す。）は、例えばＰ＋Ｑのようにその構成要素である元同士の間で定義されるので、剰余環Ｚ／ｐＺの加算＋と混在しても間違うことはない。
【０００９】
さて、３次曲線と直線とが交わるときに、その交点を構成要素とする元同士で、群演算＋を単純に
R(x3)=P(x1)＋Q(x2)
という形で定義すると、演算操作に用いた直線の性質から、
P(x1)=Q(x2)＋R(x3)
ともなって、演算の一意性に欠けてしまう。そこで、２回目の演算を第３の固定点Ｏと前記演算結果の間で行う方法が考えられ、これにより演算操作の不可逆性と演算の一意性を同時に確保することができる。
【００１０】
即ち、１回目の半演算を
T=P(x1)*Q(x2)
とし、２回目の半演算を
R(x3)=T*O
にし、最終的な姿で群演算＋を
R(x3)=P(x1)＋Q(x2)
の形で定義する。その結果、前記群演算＋の下で固定点Ｏがゼロ元になる。任意の元Ｐと固定点Ｏとの第１の半演算が形成する直線は、その結果と固定点が形成する第２の半演算が形成する直線と一致し、最終的な演算結果は元Ｐ自身になるからである。つまり、
Ｐ＋Ｏ＝Ｐ
である。因みに、楕円曲線暗号では無限遠点を前記固定点にしている。２回の半演算でも被演算点ｘ１と点ｘ２の対称性は変わらないので、前記群演算＋の可換性は維持されている。つまり、
R(x3)=P(x1)＋Q(x2)=Q(x2)＋P(x1)
である。
【００１１】
従来の暗号化技術に関する文献としては、先の特許出願の明細書にも記載したように、例えば下記のようなものがある。
【００１２】
【特許文献１】特開２００５−２８３６７４号公報
【特許文献２】特開２０００−２２４１５７号公報
【特許文献３】特開２００３−３７４８２号公報
【特許文献４】米国特許出願公開第２００２／０９７８６８号公報（特許文献３に係る特許出願の対応米国特許出願に係る公開公報）
【特許文献５】米国特許出願公開第２００２／１１８８３０号公報（特許文献３に係る特許出願の対応米国特許出願に係る公開公報）
【特許文献６】特開２００４−１１２２７８号公報
【特許文献７】米国特許出願公開第２００６／０５９４０３号公報（特許文献６に係る特許出願の対応米国特許出願に係る公開公報）
【非特許文献１】「数論アルゴリズムと楕円暗号理論入門」，Ｎ．コブリッツ著，櫻井幸一訳，シュプリンガーフェアラーク東京（ISBN4-431-70727-1 C3041）
【非特許文献２】J.  Daemen,  C.  Clapp,  “Fast  Hashing  and  Stream  Encryption  with  PANAMA,”  Fast  Software  Encryption,  5th  International  Workshop,  FSE’98,  Proceedings,  LNCS  Vol.  1372,  Springer-Verlag,  1998.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
先の特許出願においては、未だ発明の初期段階にあったので、前記固定点Ｏとして２次双曲線の関数値＝０の点を用いてきた。自然な選択と考えられたからである。しかし、双曲線暗号の実用性が明確になり、より拡張された形での双曲線暗号を求める必要が出てきた。曲線パラメータの数等を増やし、暗号解読性を高める工夫が求められるからである。前記固定点Ｏとして任意の点ｄを選択したとき、即ち元Ｏ＝Ｏ（ｄ，ｆ（ｄ））をゼロ元としたとき、２次双曲線群がどのように拡張されどのような問題が新たに生起するのか、そしてこれをどのように解決して双曲線暗号を形成するのかが、本発明の第１の課題である。又、法ｎを素数ｐとしてきたが、これが合成数の場合にどのように拡張されどのような問題が新たに生起するのか、そしてこれをどのように解決して双曲線暗号を形成するのかが、本発明の第２の課題である。
【００１４】
先の特許出願では、前記群演算＋の非定義領域が生成する問題を「同値対（equal  pair）の問題」として捉え、これを回避するため及び群演算＋の閉鎖性を確保するために前記２次双曲線群につき（３−１）式の分母である２次関数が平方非剰余であるとの条件を付けた。同値対の問題は、割り算でゼロ割を防止する必要があることに相当する。即ち、双曲線関数値の一意性と、剰余環Ｚ／ｐＺの元０、若しくは元ｐに逆元が存在せず、従ってその点での群演算が定義できず、そのような逆元が生じる事態を回避する必要があるという必要性等から生じたものである。後記するように、前記固定点Ｏとして任意の点ｄを選択したとき、前記同値対の問題は「排他対（exclusive  pair）の問題」へと転換すること、及び双曲線関数値の一意性は最早問題ではないこと、が明らかになっている。又、法ｎが合成数の場合に単純にJacobiの記号を導入してもうまく行かず、巡回群の構造が壊れてしまうことが明らかになっている。
【００１５】
従って、今度は新たに生じた排他対の問題等を回避すること、及び群演算＋の閉鎖性を確保することを同時に達成するように２次双曲線群を構成しなければならない。更に、これらの条件を確保しつつ、２次双曲線の（３−１）式に現れる曲線パラメータを具体的に定める方法を開示して、始めて双曲線暗号の鍵生成方法が明らかになる。
【００１６】
よって、本発明の目的は、前記先の特許出願に係る発明を改善し、２次双曲線群が拡張された場合において、排他対の問題等を解決しつつ、具体的に双曲線暗号の鍵生成方法を提供することにある。
【課題を解決するための手段】
【００１７】
請求項１に係る発明は、
（ａ）スカラー係数である秘密鍵を設定すると共に、有限環上で定義された整数論的関数の従属変数ｙと当該整数論的関数の独立変数ｘとの組（ｘ，ｙ）からなる集合のなす有限可換群の元を第１の公開鍵として選択するステップと、（ｂ）前記第１の公開鍵に対して前記有限可換群において定義される加法演算を少なくとも１回施すことにより前記第１の公開鍵を前記秘密鍵でスカラー倍して第２の公開鍵を生成するステップとを有している。そして、前記整数論的関数は、前記有限環上で定義された２次多項式の分母と前記有限環上で定義された１次多項式の分子とからなる２次双曲線関数である。更に、前記ステップ（ｂ）の加法演算において、前記有限可換群の第１及び第２の元を加算する際には、前記第１及び第２の元を解として有する１次関数と前記２次双曲線関数との共通解のうち前記第１及び第２の元を除く第３の元が定まるとき、前記第３の元と前記有限可換群の所定の固定元とを解として有する１次関数と前記２次双曲線関数との共通解のうち前記第３の元と前記所定の固定元とを除く第４の元を当該加算結果として算出する双曲線暗号の鍵生成方法において、次のような手段を講じている。
前記有限可換群が剰余環Ｚ／ｎＺで、前記２次双曲線関数が
【００１８】
【数５】
2009223035.tif 000004
【００１９】
である場合に、第１のステップで、法ｎ＝ｐｈ（ｈ：自然数）である素数ｐを定め、第２のステップで、判別式Ｄ／４＝ｃ２＋４ａが素数ｐに対し平方非剰余であるように曲線パラメータａ及びｃを定め、第３のステップで、前記固定元Ｐ（ｄ）を与えるパラメータｄに関しｄ（ｄ＋ｃ）−ａが素数ｐに対し平方非剰余であるように定め、第４のステップで、ベースポイントＰ（ｘ）を与えるパラメータｘ（ｘ≠ｄ）に関しｘ（ｘ＋ｃ）−ａが素数ｐに対し平方非剰余であるように定めることを特徴とする。
【００２０】
請求項２に係る発明は、（ａ）スカラー係数である秘密鍵を設定すると共に、有限環上で定義された整数論的関数の従属変数ｙと当該整数論的関数の独立変数ｘとの組（ｘ，ｙ）からなる集合のなす有限可換群の元を第１の公開鍵として選択するステップと、（ｂ）前記第１の公開鍵に対して前記有限可換群において定義される加法演算を少なくとも１回施すことにより前記第１の公開鍵を前記秘密鍵でスカラー倍して第２の公開鍵を生成するステップとを有している。そして、前記整数論的関数は、前記有限環上で定義された２次多項式の分母と前記有限環上で定義された１次多項式の分子とからなる２次双曲線関数である。更に、前記ステップ（ｂ）の加法演算において、前記有限可換群の第１及び第２の元を加算する際には、前記第１及び第２の元を解として有する１次関数と前記２次双曲線関数との共通解のうち前記第１及び第２の元を除く第３の元が定まるとき、前記第３の元と前記有限可換群の所定の固定元とを解として有する１次関数と前記２次双曲線関数との共通解のうち前記第３の元と前記所定の固定元とを除く第４の元を当該加算結果として算出する双曲線暗号の設計方法において、次のような手段を講じている。
前記有限可換群が剰余環Ｚ／ｎＺで、前記２次双曲線関数が
【００２１】
【数６】
2009223035.tif 000005
【００２２】
である場合に、第１のステップで、法ｎを素数ｐ１，ｐ２の積として定め、第２のステップで、判別式Ｄ／４＝ｃ２＋４ａが前記素数の何れに対しても平方非剰余であるように曲線パラメータａ及びｃを定め、第３のステップで、前記固定元Ｐ（ｄ）を与える新たなパラメータｄに関しｄ（ｄ＋ｃ）−ａが前記素数の何れに対しても平方非剰余であるように定め、第４のステップで、ベースポイントＰ（ｘ）を与えるパラメータｘ（ｘ≠ｄ）に関しｘ（ｘ＋ｃ）−ａが前記素数の何れに対しても平方非剰余であるように定めることを特徴とする。
【００２３】
請求項３に係る発明は、（ａ）スカラー係数である秘密鍵を設定すると共に、有限環上で定義された整数論的関数の従属変数ｙと当該整数論的関数の独立変数ｘとの組（ｘ，ｙ）からなる集合のなす有限可換群の元を第１の公開鍵として選択するステップと、（ｂ）前記第１の公開鍵に対して前記有限可換群において定義される加法演算を少なくとも１回施すことにより前記第１の公開鍵を前記秘密鍵でスカラー倍して第２の公開鍵を生成するステップとを有している。そして、前記整数論的関数は、前記有限環上で定義された２次多項式の分母と前記有限環上で定義された１次多項式の分子とからなる２次双曲線関数である。更に、前記ステップ（ｂ）の加法演算において、前記有限可換群の第１及び第２の元を加算する際には、前記第１及び第２の元を解として有する１次関数と前記２次双曲線関数との共通解のうち前記第１及び第２の元を除く第３の元が定まるとき、前記第３の元と前記有限可換群の所定の固定元とを解として有する１次関数と前記２次双曲線関数との共通解のうち前記第３の元と前記所定の固定元とを除く第４の元を前記加算結果として算出する双曲線暗号の鍵生成方法において、次のような手段を講じている。
前記有限可換群が剰余環Ｚ／ｎＺで、前記２次双曲線関数が
【００２４】
【数７】
2009223035.tif 000006
【００２５】
である場合に、前記加法演算を計算するに際し、分子の演算と分母の演算を区別することにより、法ｎに係る逆元の演算を後回しにすることを特徴とする。
【発明の効果】
【００２６】
請求項１、２に係る発明によれば、楕円曲線暗号に比べて簡易な構成により拡張された２次双曲線群に係る離散対数を利用した暗号（双曲線暗号）の鍵を具体的に生成できる。その結果、特に位数関係が簡明なことから、整数論の初等的知識を有する者に対して離散対数に係る双曲線暗号の利用が普及すると期待される。暗号や数学の専門家に対しては、従来の暗号理論や数学理論の進歩に寄与する「道具」として利用することができる。しかも、拡張された２次双曲線群を利用する双曲線暗号は、従来と同様に、離散対数を基礎とし、群位数が一定であり、鍵生成が容易で、且つ、秘密鍵変動等により安全性を高めることができるという性質を有するために楕円曲線暗号に替わり得る可能性を有している。
【００２７】
請求項３に係る発明によれば、拡張２次双曲線群ＥＨＣ及び拡張２次双曲線半群を用いた双曲線暗号の鍵を具体的に、かつ、高速に生成できる。
【発明を実施するための最良の形態】
【００２８】
本発明を実施するための最良の形態のうち、第１の実施形態（下記の実施例１に対応）では、
【００２９】
【数８】
2009223035.tif 000007
【００３０】
という２次双曲線上の整数点につき、前記固定点Ｏとして任意の点ｄを選択し、且つ、群演算＋を定義し、新たな２次双曲線群を
ＨＣ＝｛Ｐ（ｘ）｜群演算＋；ｘ∈Ｚ／ｐＺ；x2＋cx−a≠0；(x2＋cx−a)が平方非剰余；(d(d＋c)−a)が平方非剰余｝  ・・・・（６−２）
という構成にする。ここで、（３−１）式から（６−１）式への変換は、
ｙ’＝（ａ／ｄ）ｙ、ｂ’＝−（ｅ／ｄ）、ｃ’＝（ｂ／ａ）、ａ’＝−（ｃ／ａ）
なる変換により容易に行える。そして、（６−１）式で与えられた曲線パラメータを、前記排他対の問題及び前記群演算の問題を解決しつつ、具体的に図１に示した方法により特定する。更に、この２次双曲線群ＨＣを用いてElGamal暗号（HC-Elgamal暗号）等の双曲線暗号を構成する。
【００３１】
第２の実施形態（下記の実施例２に対応）では、前記第１の実施形態に係る双曲線暗号の鍵生成方法に基づき複数の同一の群位数を有する２次双曲線群を特定し、複数のセル演算器を用いてストリーム暗号を形成し、音楽等のストリームデータを加工した後ＩＰ（インターネット・プロトコル）ネットワークを介して送受信する鍵生成装置であるストリーム暗号生成装置を開示している。
【００３２】
第３の実施形態（下記の実施例３に対応）では、法ｎを合成数とした場合の拡張２次双曲線群ＥＨＣを
【００３３】
【数９】
2009223035.tif 000008
【００３４】
という構成にした。但し、Legendreの記号を導入している。そして、拡張２次双曲線群ＥＨＣを用いた双曲線暗号の鍵生成方法を開示している。
【００３５】
第４の実施形態（下記の実施例４に対応）では、拡張２次双曲線群ＥＨＣの応用問題として、群のイメージを利用する新たな素因数分解の鍵生成方法を開示している。更に、拡張２次双曲線半群を利用する鍵生成方法も開示している。
【実施例１】
【００３６】
図１（Ａ）は、本発明の実施例１に係る双曲線暗号の鍵生成装置の概略構成を示す機能ブロック図である。
【００３７】
この双曲線暗号の鍵生成装置１０は、鍵設定部１１、曲線パラメータ設定部１２、及び鍵生成部１３を有している。
【００３８】
有限環上で定義された整数論的関数の従属変数ｙと当該整数論的関数の独立変数ｘとの組（ｘ，ｙ）からなる集合のなす有限可換群が剰余環Ｚ／ｎＺで、有限環上で定義された整数論的関数ｙが次式で表される２次双曲線関数である場合、
【００３９】
【数１０】
2009223035.tif 000009
【００４０】
曲線パラメータ設定部１２では、２次双曲線関数の曲線パラメータａ，ｂ，ｃ，ｄ，ｘを適切な値に設定して鍵設定部１１及び鍵生成部１３に供給する機能を有している。鍵設定部１１は、スカラー係数である暗号処理用の秘密鍵ｓを設定すると共に、曲線パラメータａ，ｂ，ｃ，ｄ，ｘにより定まる２次双曲線関数上のベースポイントＰ（ｘ）を第１の公開鍵として選択し、その秘密鍵ｓとベースポイントＰ（ｘ）を鍵生成部１３に供給する機能を有している。鍵生成部１３は、ベースポイントＰ（ｘ）に対して、曲線パラメータａ，ｂ，ｃ，ｄ，ｘにより定まる２次双曲線群において定義される加法演算を少なくとも１回施すことにより、ベースポイントＰ（ｘ）を秘密鍵ｓでスカラー倍して第２の公開鍵である作業鍵Ｙ（＝ｓＰ（ｘ））を生成する機能を有している。
【００４１】
これらの鍵設定部１１、曲線パラメータ設定部１２、及び鍵生成部１３の機能の全部又は一部は、ハードウェアの回路で構成され、或いは、不揮発性メモリ、光ディスク等の記憶手段に記録されたプログラム又はプログラムコードに基づき、ＣＰＵ等のプロセッサにより前記機能の全部又は一部の処理が実行される構成になっている。      
【００４２】
図１（Ｂ）は、本発明の実施例１に係る２次双曲線群の鍵生成方法を示すフローチャートである。
【００４３】
この２次双曲線群の鍵生成方法は、図１（Ａ）中の曲線パラメータ設定部１２にて処理されるものであり、ステップＳ１〜Ｓ５の処理により、整数論的関数を表す（６−１）式の曲線パラメータａ，ｂ，ｃ，ｄ，ｘが適切な値に設定される。
【００４４】
以下、図１（Ａ）及び図１（Ｂ）の内容の理解を容易にするために、最初に、２次双曲線群の前記固定点Ｏとして任意の点ｄを選択したとき、即ち元Ｏ＝Ｏ（ｄ，ｆ（ｄ））をゼロ元としたとき、先の特許出願に係る２次双曲線群がどのように拡張されどのような問題が新たに生起するのか（（I）先の特許出願との関連）、そしてこれをどのように解決して双曲線暗号を形成するのか（（II）双曲線暗号の形成方法）を順次説明する。次に、具体的に２次双曲線群を構成する方法（（III）２次双曲線群の構成方法、即ち曲線パラメータの設定方法）、及びそれを用いたHC-ElGamal暗号及びHC-ElGamal署名の構成方法（（IV）鍵設定・鍵生成方法）を開示し、併せてその数値例を掲げる。
【００４５】
（I）  先の特許出願との関連
最初に２次双曲線群の元Ｐ、Ｑ、Ｒにおいて
R(x3)=P(x1)＋Q(x2)
を計算するものとし、１回目の半演算を
T=P(x1)*Q(x2)
とし、２回目の半演算を
R(x3)=T*O
にし、最終的な姿で群演算＋を
R(x3)=P(x1)＋Q(x2)
の形で計算する。２次双曲線関数
【００４６】
【数１１】
2009223035.tif 000010
【００４７】
が成立する。更に２回目の半演算では、固定点Ｏ（ｄ）との間で
R(x3)=T*O
を計算すると、以下の式が成立する。
【００４８】
【数１２】
2009223035.tif 000011
【００４９】
と、求めることができる。
（８−６）式では、曲線パラメータｂへの依存がなく、新たにゼロ点としたｘ＝ｄのパラメータを有すること、且つ、ｄ→ｂと置き換えた式が従来の演算に一致することを示している。従って、従来の群演算で固定点をｘ＝ｂとしたことは、パラメータを増やさない利点を有していたことが判明した。最も（８−４）式に従わなければならない。
【００５０】
２次双曲線群ＨＣの前記固定点Ｏとして任意の点ｄを選択したとき、群演算の閉鎖性はどうなるのか、以下説明する。
（８−６）式から、
【００５１】
【数１３】
2009223035.tif 000012
【００５２】
であり、この場合もｄ→ｂと置き換えた式が従来の演算に一致する。従って、群演算が閉じているためには、
【００５３】
2009223035.tif 000013
【００５４】
の何れもが平方剰余であるか、何れもが平方非剰余でなければならない。２次双曲線群ＨＣでは、何れもが平方非剰余に選ばれる。平方剰余か平方非剰余かという基準でＺ／ｐＺの部分集合を分別する理由は、後記する群演算の定義域と関係している。
【００５５】
２次双曲線群ＨＣの前記固定点Ｏとして任意の点ｄを選択したとき、群演算の逆元はどうなるかを考える。
【００５６】
群逆元Ｐ（＜ｘ１＞）は、
O(d)=P(x1)＋Q(x2)
の関係から、（８−６）式でx3=dと置けば求められる。
【００５７】
【数１４】
2009223035.tif 000014
【００５８】
である。（１０−１）式の分母は、逆元の存在しない元Ｐ（ｅ）（以下、「素元」という。）が存在することを示している。
【００５９】
２次双曲線群ＨＣの前記固定点Ｏとして任意の点ｄを選択したとき、同値対（equal  pair）は、どのように変わるかを考える。
（８−１）式で、y=f(x)と置けば、以下の式になる。
【００６０】
【数１５】
2009223035.tif 000015
【００６１】
が成立する同値対のときだけ関数値が等しくなる。しかし、b≠dであるので、同値対の出現条件が異なったものになる可能性がある。ただ、演算関係（８−６）式は変わっていないので、同値対が中心元から伝播する性質に変わりないはずである。即ち、集合ＨＣの元Ｐ、Ｑ、及びＲが存在するとき、ＱとＲが同値対なら（−Ｐ）＋ＱとＲ＋Ｐも同値対のはずである。これを示すには、
【００６２】
【数１６】
2009223035.tif 000016
【００６３】
が成立することを利用する。即ち、（８−６）式によれば、（１１−３）式が成立すればその両辺も等しくなる。従って、
｛（−Ｐ）＋Ｑ｝＋｛Ｐ＋Ｒ｝＝Ｑ＋Ｒ
が成立する。この結果、前記（１１−２）式及び（１１−３）式により、ＰとＱが同値対なら、ｂ≠ｄにおいて、
【００６４】
【数１７】
2009223035.tif 000017
【００６５】
となる。従って、（１１−３）式及び（１１−４）式より、
−X1X2＋b(X1＋X2＋c)−a=0  ・・・・（１１−５）
が成立する。これは、ＱとＲが同値対なら（−Ｐ）＋ＱとＲ＋Ｐも同値対であることを示している。
【００６６】
ここで、Ｐ＋ＱとＱが同値対となる中心元が出現する条件を調べる。
「同値対の中心元」とは、Ｐ（ｘ１，ｙ１）のとき、中心元Ｑ（ｘ２，ｙ２）とＲ（ｘ３，ｙ３）につき、Ｒ＝Ｐ＋Ｑとすれば、ｘ３とｘ２との間同値対の関係（１１−２）式が、又、ｘ３とｘ２及びｘ１との間にＰを加算する関係（８−６）式が成立することなので、
【００６７】
【数１８】
2009223035.tif 000018
【００６８】
という関係式が成立し、その結果ｘ２に関する以下のような２次方程式を得ることができる。
【００６９】
2009223035.tif 000019
【００７０】
この判別式ＤＤは、
DD={−(a＋db)x1＋(ab＋ad−bcd)}2−
{(b＋d＋c)x1−(a＋db)}{(ab＋ad−dbc)x1−(bc−a)(dc−a)−abd}  ・・・（１１−８）
となり、同値対となる中心元が出現する条件を調べられる。（１１−８）式が整数解を持つためには判別式ＤＤが平方剰余でなければならず、逆に判別式ＤＤが平方非剰余なら（１１−７）式は整数解を持たず、同値対の問題も発生しないということである。（１１−８）式は、更に以下のように簡略化できる。
【００７１】
2009223035.tif 000020
【００７２】
上記計算結果を総括すると、次の（１）、（２）のことがいえる。
（１）  同値対となる中心元が出現する条件は、（１１−７）式が整数解を持つこと、即ち判別式ＤＤが平方剰余となることで、そのためには（１１−９）式からして、
【００７３】
2009223035.tif 000021
【００７４】
を平方非剰余にした場合には、(d(d＋c)−a)がゼロ元Ｐ（ｄ）であり平方非剰余であることから、(b(b＋c)−a）が平方剰余であることが要件になる。
【００７５】
（２）  逆に、同値対となる中心元の出現を防ぐには、
【００７６】
2009223035.tif 000022
【００７７】
を平方非剰余にした場合に、(b(b＋c)−a)が平方非剰余とすればよいことになる。
後記するように、同値対を排除する必要は必ずしもなく、同値対同士の演算自体は定義できる。演算を定義できないのは、逆元が存在しないときであり、こちらは必ず排除しなければならない。
【００７８】
２次双曲線群ＨＣの前記固定点Ｏとして任意の点ｄを選択したとき、どのような場合に群演算が定義できなくなるのかを考える。
【００７９】
（８−６）式で、分母が０になる点同士では演算結果を得ることはできない。従来、ｂ＝ｄの条件下では、（８−６）式の分母は同値対の（１１−１）式の分子と同じ因子（−x1x2＋b(x1＋x2＋c)−a）を有していたので、同値対を排除することは、同時に分母が０になる点同士では演算を回避する意味を有していた。しかし、b≠dの条件下ではこのような制約はないので、パラメータｂについて規制するだけでは、分母が０になる点同士での演算を回避することができない。別のいい方をすれば、群演算＋の定義域が制限されている、ということである。そこで、
−x1x2＋d(x1＋x2＋c)−a=0  ・・・・（１２−１）
の関係を有する点ｘ１とｘ２の特別な関係を「排他対（exclusive  pair）」と呼ぶことにする。明らかに排他対同士の元Ｐ（ｘ１）とＱ（ｘ２）の間での群演算＋は定義できない。
【００８０】
（１２−１）式より排他対では、
【００８１】
2009223035.tif 000023
【００８２】
の関係式が成立する。従って、排他対の出現を阻止して、群演算＋がある集合にある全ての元同士間の演算として適用できるようにするには、排他対の一方を当該集合から排除する方法が自然に考えられる。
【００８３】
２次双曲線群ＨＣの前記固定点Ｏとして任意の点ｄを選択したとき、（９−１）式からして、
集合ＨＣ＝｛Ｐ（ｘ）｜群演算＋；ｘ∈Ｚ／ｐＺ；x2＋cx−a≠0；
(x2＋cx−a)が平方非剰余；(d(d＋c)−a)が平方非剰余｝・・・・（１３−１）
若しくは、
集合ＨＣｎ＝｛Ｐ（ｘ）｜群演算＋；ｘ∈Ｚ／ｐＺ；x2＋cx−a≠0；
(x2＋cx−a)が平方剰余；(d(d＋c)−a)が平方剰余｝・・・・（１３−２）
のように選択すると、群演算の閉鎖性を満たすことができる。又、（１２−２）式からして、集合ＨＣについては分母が０になる点同士での演算を回避することができる。演算結果である元が、再び集合ＨＣの要素になるからである。この結果、集合ＨＣは群の構成要件を満たし、２次双曲線群ＨＣとして成立する。
【００８４】
しかし、集合ＨＣｎについては分母が０になる点同士での演算を回避することができない、という問題が残存している。又、（１０−２）式からして逆元を有しない素元Ｐ（ｅ）が集合ＨＣｎの要素であることから、この点でも群の構成に難点がある。即ち、集合ＨＣｎでは、上記定義における限定だけでは群演算の閉鎖性と未定義領域の解消とを両立させることができない、といえる。
【００８５】
なお、Ｐ（ｘ）はＰ（ｘ，ｙ）やＰ（ｘ，ｆ（ｘ））の省略表示で、同値対以外では特に後者の表現はしないことにする。又、「x2＋cx−a≠0」という条件はもう１つの条件「(x2＋cx−a)が平方非剰余」に含めて考えることができるが、関数（６−１）式や判別式Ｄとの関係で明示することにした。
【００８６】
（II）  双曲線暗号の形成方法
２次双曲線群ＨＣの定義が（１３−１）式で与えられたので、本実施例１の理解を容易にするために、現在までに判明している２次双曲線群ＨＣの詳細な構成について、できる限り以下に開示する。
【００８７】
さて、（１３−１）式に有るように、例えば「(x2＋cx−a)が平方非剰余」という条件は、剰余環Ｚ／ｐＺの部分集合で、且つ、ｘについての２次関数値が平方非剰余であるような集合を考える必要がある。そこで
τ(x)=x2＋cx−a  ・・・・（１４−１）
なる関数τを導入する。関数値τ（ｘ）は、２次関数値が平方非剰余であることから、剰余環Ｚ／ｐＺの原始根ρを用いて
τ(x)=ρ2m+1  ・・・・（１４−２）
のように、原始根ρの指数部を奇数とする表現で表すことができる。ここで、Ｐ＝Ｐ（ｘｎ）とした場合に、Ｑ＝ｍＰ＝Ｑ（ｘｍ）とすれば、（９−１）式から、
【００８８】
【数１９】
2009223035.tif 000024
【００８９】
と漸化式で表すことができ、次々に因子
【００９０】
2009223035.tif 000025
【００９１】
を高速に計算することが可能である。ただ、因子
【００９２】
2009223035.tif 000026
【００９３】
を高速計算できても、ｘｍ自体は式（８−６）によらなければ計算することが困難であることに注意しなければならない。
【００９４】
ここで、２次双曲線群の普遍式につき考えてみる。
ベースポイントＰ（ｘ）に対する生成群Ｑ（ｘ）の位数がｋｇ（ｋｇは生成群の最大位数ｋｑの約数）である場合に、ｘｋｇ＝ｘ０＝ｄ（ゼロ点）であるので、（１４−３）式から、
【００９５】
【数２０】
2009223035.tif 000027
【００９６】
と表示することができる。当然であるが、ゼロ元Ｐ（ｘｎ）＝Ｐ（ｄ）との加算では、部分積の各項について、
【００９７】
【数２１】
2009223035.tif 000028
【００９８】
であり、全体としても（１４−７）式が成立する。
次に、（１４−７）式のような普遍式がどのような意味を有するのか検討する。
ここで、相関係数を平方非剰余数である
【００９９】
【数２２】
2009223035.tif 000029
【０１００】
と表せる。（１４−７）式は、一般に位数ｍ＝ｋｇに対して、
【０１０１】
【数２３】
2009223035.tif 000030
【０１０２】
先ず、相関係数を、それが平方非剰余数であることを考慮して、
λmn=ρ2s(m,n)−1  ・・・・（１５−４）
と置くと、（１５−２）式より、
(2h(m,n)＋1)=（2s(m,n)−1）＋(2m＋1)＋(2n＋1)
若しくは、
h(m,n)=s(m,n)＋m＋n  ・・・・（１５−５）
となる。
【０１０３】
従って、少なくともs(m,n)≠0の場合に、指数演算の加法と２次双曲線群ＨＣの群演算＋は同型ではない。即ち、２次双曲線群ＨＣの原始根をρm=ρmのように単純に指数に置き換えることはできない、ということになる。２次双曲線群ＨＣは剰余環Ｚ／ｐＺ上の部分集合を基礎としているが、指数演算との同型が取れないために第２の演算である「積」を定義することができない。これが「２次双曲線環」とならない理由である。
（１５−３）式、（１５−４）式により、
【０１０４】
【数２４】
2009223035.tif 000031
【０１０５】
である。従って、
【０１０６】
【数２５】
2009223035.tif 000032
【０１０７】
この結果を群演算＋の方で見ると、任意の元Ｐ（ｘ）を（ｍ−１）回加算した場合に、ｍが群位数ｋｇに到達するとｋｇＰ（ｘ）＝Ｏとなることを示していて、当然の結果である。即ち、（１５−７）式は、ｋｇ回後の加算結果が全くＰ（ｘ）に依存せず、ただ位数ｋｇにのみ依存することを示している。原始根ρのべき乗の計算において、曲線パラメータに関しどのように群演算＋が定義されていても当該べき乗値の総和は変わらない、という意味があったわけである。更に、その指数がパラメータ依存である場合にも関わらず、ｈ値として、ｍ値に対応して相異なるｋｇ以下の数値が１回ずつ出現したことを示している。これは、（１５−２）式で示される原始根同士の演算（ｎ固定）において写像が全射であることを示している。ここで、相異なるｋｇ以下の数値が１回ずつ出現したことは、必ずしも異なるτ（ｘ）値がｋｇ個出現したことを意味しているわけではなく、同一値が含まれることを排除していない、と考えられる。
【０１０８】
今度は（１４−１）式で与えられる関数値τ（ｘ）の個数や性質について開示する。
この関数値τ（ｘ）が平方非剰余であることは、集合ＨＣが群の構成要件を満たすための条件の１つであった。さて、（１４−１）式から、
【０１０９】
2009223035.tif 000033
【０１１０】
(xm＋xn＋c)=0  ・・・・（１６−２）
の場合にも左辺が０になり、関数値の一意性がないことが分かる。これは、関数値を２次関数としたために生じた事態である。ここで、（１６−２）式の関係にある点を、「同根対（root  pair）」と呼ぶことにする。同根対同士では、集合ＨＣ若しくは集合ＨＣｎの条件である「(x2＋cx−a)が平方非剰余」という条件、若しくは「(x2＋cx−a)が平方剰余」という条件が同時に満たされるので、Ｐ（ｘｍ）とＰ（ｘｎ）は同時に集合ＨＣ若しくは集合ＨＣｎの元であり、特にＨＣにおけるｍＰの計算において中途で出現する。しかし、これらの条件は、演算結果が同一の群に属する元であることを意味するだけなので、演算自体に影響するものではない。この同根対については、以下の定理群が成立する。
【０１１１】
［定理１６−１］
２次双曲線群ＨＣの元ＱとＲが同根対を生成するならば、（−Ｐ）＋ＱとＲ＋Ｐも同根対を生成する。
【０１１２】
［証明］
（１１−３）式により、(x2＋x3＋c)=0ならば(X1＋X2＋c)=0である。
【０１１３】
［q.e.d］
この結果、ｍＰの計算を行うときにを計算してみると、生成される同根対は、同値対と同様に、「中心根」から伝播することが分かる。
【０１１４】
［定理１６−２］
２次双曲線群ＨＣのベースポイントＰ（ｘ１）における中心根の生成条件は、判別式ＤＤで
【０１１５】
2009223035.tif 000034
【０１１６】
が平方剰余になることである。
【０１１７】
［証明］
２次双曲線群ＨＣのベースポイントＰ（ｘ１）を用いてｍＰを計算するときに、ベースポイントＰ（ｘ１）における中心根は以下の条件を満たさなければならない。
【０１１８】
２次双曲線群ＨＣの元ＱとＲが隣り合い、且つ、同根対を生成するとき、
（１）  Ｑ（ｘ３）＝Ｒ（ｘ２）＋Ｐ（ｘ１）
（２）  ｘ３＋ｘ２＋ｃ＝０
である。従って、以下の式が成立する。
【０１１９】
【数２６】
2009223035.tif 000035
【０１２０】
これはｘ２に関する２次方程式であり、
【０１２１】
2009223035.tif 000036
【０１２２】
が成立し、ｘ２が整数解を有するためには少なくともその判別式ＤＤが平方剰余でなければならない。然るに、
【０１２３】
2009223035.tif 000037
【０１２４】
である。
【０１２５】
［q.e.d］
この結果、２次双曲線群ＨＣでは自然に（１６−３）式の条件が満たされる。即ち、
【０１２６】
2009223035.tif 000038
【０１２７】
は平方非剰余であり、P(d)=(d(d＋c)−a)はゼロ元であるので、当然平方非剰余に選ばれる。従って、同根対に対応する元同士は、双方共に２次双曲線群ＨＣに含まれる。
【０１２８】
ここで、ゼロ点ｘ＝ｄの同根対ｘ２＝−（ｄ＋ｃ）が新たなゼロ元Ｐ（−（ｄ＋ｃ））を生成するのか検討する。その同根対はゼロ点と同じτ（ｘ）値であるτ（ｄ）を有するからである。
【０１２９】
そこで、（８−６）式を用いて、
Ｐ（ｘ３）＝Ｐ（ｘ１）＋Ｐ（−（ｄ＋ｃ））
の計算を行ってみる。この結果がＰ（ｘ３）＝Ｐ（ｘ１）であれば、ゼロ元として機能していることになる。
【０１３０】
【数２７】
2009223035.tif 000039
【０１３１】
上式の最後の２項は、
【０１３２】
2009223035.tif 000040
【０１３３】
を意味している。従って、Ｐ（ｘ３）≠Ｐ（ｘ１）が示され、その結果、同根対が新たなゼロ元を生成するものではないことが示された。
【０１３４】
今度は、２次双曲線群ＨＣの全体を、図２及び図３を利用して開示する。
図２は、群演算に関する２次双曲線群の構成を示す概念図である。更に、図３は、２次双曲線群の具体的構成例であって、ｐ＝２３，ｄ＝６，ａ＝４，ｃ＝１，ｂ＝７である２次双曲線群ＨＣ（ｄ≠ｂ）の生成群Ｑ（ｘ）の構造を示す図である。
【０１３５】
図２において、左側の集合は２次双曲線群ＨＣであり、その要素が元Ｐ、Ｑ、Ｒ、Ｓにより示されている。図２の中央の集合は剰余環Ｚ／ｐＺの部分集合で、「(x2＋cx−a)が平方非剰余」という条件を満たすｘ値をその要素とする。図２の右側の集合は剰余環Ｚ／ｐＺの部分集合で、「τ(x)=x2＋cx−aが平方非剰余」という条件を満たす関数τ（ｘ）の値をその要素とする。ここで図２中、矢印で示された集合間の対応を写像として捉えて、検討してみる。
【０１３６】
２次双曲線群ＨＣと中央のｘ値の集合間において、ｇ１：ｘ１→Ｐ（ｘ１）という写像ｇ１は、Ｐ（ｘ１）＝Ｐ（ｘ２）のとき、必ずｘ１＝ｘ２であるので、単射（injective）である。又、任意の元Ｐ（ｘ１）に対して必ずｇ１（ｘ１）＝Ｐ（ｘ１）となるｘ１が存在するので、全射（surjective）である。従って、写像ｇ１は全単射（bijection）で両者の集合の個数は一致する。２次双曲線群ＨＣの位数は、
ｋ＝（ｐ−１）／２＋１
であるので、剰余環Ｚ／ｐＺの部分集合の個数も、
ｋ＝（ｐ−１）／２＋１
となる。
【０１３７】
次に、中央の剰余環Ｚ／ｐＺの部分集合と右側の剰余環Ｚ／ｐＺの平方非剰余値集合間において、ｇ２：ｘ３→τ（ｘ３）という写像ｇ２は、τ（ｘ３）＝τ（ｘ４）のとき、必ずしもｘ３＝ｘ４でないので、単射ではない。しかし、任意の元τ（ｘ３）に対して必ずｇ２（ｘ３）＝Ｐ（ｘ３）となるｘ３が存在するので、全射である。
【０１３８】
更に、同根対同士の演算、（１５−２）式についても検討すると、ｇ３：τ（ｘ１）→τ（ｘ３）（τ（ｘ２）固定）という写像ｇ３は、ｇ３：τ（ｘ５）→τ（ｘ３）（τ（ｘ２）固定）のとき必ずしもτ（ｘ３）＝τ（ｘ５）でないので、単射ではない。しかし、（１５−７）式より、任意の点τ（ｘ３）に対して必ずｇ３：τ（ｘ１）→τ（ｘ３）（τ（ｘ２）固定）となるτ（ｘ１）が存在するので、全射である。
【０１３９】
ここで、関数値τ（ｘ）の個数を計算してみる。
剰余環Ｚ／ｐＺの部分集合の個数はｋ＝（ｐ−１）／２＋１であり、その２個が１個の関数値に対応するので、少なくとも（ｐ−１）／４個の関数値を有している。しかし、残りの１個はどの関数値に対応するのか、不明である。これは関数値τ（ｘ）の重根が対応すると考られる。（１４−１）式で、
【０１４０】
【数２８】
2009223035.tif 000041
【０１４１】
になる。ここで、２次双曲線群ＨＣでは判別式Ｄは平方非剰余に選ばれる。残りの因子（−１）については、オイラーの基準が
【０１４２】
2009223035.tif 000042
【０１４３】
であり、ｐがｐ＝４ｍ＋１型の素数の場合に平方剰余、ｐ＝４ｍ＋３型の素数である場合に平方非剰余であるので、τ（ｘｍ）値は前者で平方非剰余、後者で平方剰余になる。従って、Ｚ／ｐＺの平方非剰余集合の個数を勘定すると、同根対１組に対応する（ｐ−１）／４個の関数値と、１個の重根と、合計（ｐ−１）／４＋１個の関数値を有することになる。又、ｐがｐ＝４ｍ＋３型の素数である場合には２次双曲線群ＨＣの位数は偶数になり、（１７―２）式の右辺は平方剰余になるので、この場合にはＰ（−ｃ／２）はＨＣの元ではない。このとき、平方非剰余となる関数値の数はｋ／２＝（ｐ＋１）／４個になる。以上の結果をまとめると、τ（ｘ）の位数を＃（τ（ｘ））と表した場合、
【０１４４】
【数２９】
2009223035.tif 000043
【０１４５】
となる。なお、２次双曲線群ＨＣの位数ｋを素数に選んだ場合には、ｐがｐ＝４ｍ＋１型の素数であることが知られている。
【０１４６】
以上の結果を総括すれば、剰余環Ｚ／ｐＺのｐ個の値ｘのうち、凡そその半分で２次双曲線群の元Ｐ（ｘ）を形成しており、凡そその１／４の平方非剰余値τ（ｘ）を判別に使用している、といえる。
【０１４７】
ここで、数値例を挙げておく。
演算パラメータの設定をｐ＝２３，ａ＝４，ｂ＝７，ｃ＝１，ｄ＝６とし、ｘ＝１３でτ（１３）が平方非剰余であるので、Ｐ（１３，３）を起点として（１４−３）式、（１４−７）式の計算を位数ｋ＝１２に至るまで順次行ってみる。
【０１４８】
2009223035.tif 000044
【０１４９】
の値は、１７，２１，２２，２２，２１，１７，１５，１４，１９，１９，１４，１５の順（ｍ＝１，，，１２）に出現し、その出現値は６個である。これは、ｐ＝４ｍ＋３型のとき平方非剰余となる関数値の数はｋ／２＝（ｐ＋１）／４個であることから、ｐ＝２３の場合は関数値の数は６個であることを示している。又、同根対で繰り返す構造になっている。例えば、ｘ３＝１４，ｘ４＝８においてτ（ｘ３）＝２２，τ（ｘ４）＝２２であるが、これはｘ３とｘ４が同根対であることを示している。なお、ｘ値は必ずしも平方非剰余にならない。
【０１５０】
２次双曲線群の前記固定点Ｏとして任意の点ｄを選択したとき、即ち元Ｏ＝Ｏ（ｄ，ｆ（ｄ））をゼロ元としたとき、先の特許出願に係る２次双曲線群と比較するために、具体的な数値例を掲げる。
【０１５１】
先の特許出願の図４及び図５では、ｐ＝２３，ａ＝７，ｂ＝２，ｃ＝０という２次双曲線群ＨＣを開示したが、本実施例１では、図３においてｐ＝２３，ａ＝４，ｂ＝７，ｃ＝１，ｄ＝６（ｄ≠ｂ）という２次双曲線群ＨＣを開示した。
【０１５２】
双方を比較すると、２次双曲線群ＨＣの構成が、その生成群Ｑ（ｘ）の入れ替わりを除き、全く同一であることが分かる。その理由は、２次双曲線群ＨＣの構成が位数にのみ依存して定まる、という点にある。２次双曲線群ＨＣの位数ｋは、ここでは生成群の最大位数ｋｑに一致する。最大位数ｋｑ＝１２の場合、その約数が１２，６，４，３，２，１であるので、これは各生成群の位数ｋｇになる。又、各生成群の個数は、オイラーの関数φ（ｘ）を使用して表せば、それぞれφ（１２）＝４，φ（６）＝２，φ（４）＝２，φ（３）＝２，φ（１）＝１である。これらは全く２次双曲線の曲線パラメータに依存していない。なお、生成群Ｑ（ｘ）は２次双曲線群ＨＣの元Ｐ（ｘ）を生成元として生成される群であって、群演算＋においてｍＰ（ｘ）をその要素とし、
Ｑ（ｘ）＝｛ｍＰ（ｘ）｜ｍＰ（ｘ）∈ＨＣ，１≦ｍ≦ｋｇ，ｋｇＰ（ｘ）＝Ｏ｝・・・・（１８−１）
のように定義される群であるが、明らかに巡回群の一種である。
【０１５３】
（III）  ２次双曲線群の構成方法、即ち曲線パラメータの設定方法
双曲線暗号では２次双曲線群ＨＣを利用するので、暗号化のための鍵生成において最初にする作業は暗号に利用する２次双曲線群ＨＣを特定（即ち、曲線パラメータを設定）することである。２次双曲線群ＨＣの特定は、ハードウェア回路を用いた選択・演算処理等により、或いはＣＰＵ等のプロセッサを用いた選択・演算処理等により、およそ図１（Ｂ）のステップＳ１〜Ｓ５の流れに従って行われる。
【０１５４】
図１（Ｂ）の処理が開始（スタート）すると、最初のステップＳ１において、法ｎ及び位数ｋを定める作業が行われる。
【０１５５】
このステップＳ１において、先ず、ｎ＝ｐｈ（ｈ：自然数）、ｋ＝ｐｈ−１（ｐ＋１）／２の関係を満たす素数ｐ及び位数ｋを定める。ここではｈ＝１の場合のみ取り上げ、ｈ＞１である場合は後記する。
【０１５６】
さて、ｈ＝１の場合、２次双曲線群ＨＣの位数＃（ＨＣ）＝ｋは、先の特許出願で明示したように、
＃（ＨＣ）＝（ｐ−１）／２＋１  ・・・・（１９―１）
で与えられ、２次双曲線群ＨＣの前記固定点Ｏとして任意の点ｄを選択したときも同じである。これは、「(x2＋cx−a)が平方非剰余」という条件を満たすｘ値の数が、同値対を異なる元として数えた場合に、そのまま２次双曲線群ＨＣの元の数になるからである。２次双曲線群ＨＣの位数＃（ＨＣ）がその曲線パラメータに依存せず、且つ、一定であるという事実は、楕円曲線群と比べて著しい特徴であるが、その分、剰余環Ｚ／ｐＺ上の有限集合を形成する際の「(x2＋cx−a)が平方非剰余」という条件が大変に緩いものであることを示唆している。
【０１５７】
最大群位数ｋｑについては、ｋｑ＝ｑなる素数の場合に実用性が高いことが知られている。最大群位数ｋｑが合成数である場合には、選択したベースポイントＰ（ｘ）が最大群位数ｋｑのどの約数ｋｇに対応するのかを調べる手間が必要であるが、通常の利用では最大位数ｋｑになるように選択される。然るに位数としたｋｑ＝ｑなる素数を選択すれば、ゼロ元Ｐ（ｄ）以外の何れかをベースポイントＰ（ｘ）に選択した場合は、その位数ｋｇ＝ｋｑになることが保証されているので、その手間が不要になる。このとき、
ｑ＝（ｐ−１）／２＋１  ・・・・（１９−２）
である。一般に（１９−２）式の関係を有するｐとｑの素数の組については、Germain素数若しくはSophie-Germain素数として知られている。双方の素数が奇数であることから、Germain素数でｐ＝４ｍ＋１型、Sophie-Germain素数でｐ＝４ｍ＋３型になる。２次双曲線群ＨＣはｐ＝４ｍ＋１型なので、Germain素数を使用する。
【０１５８】
素数判定法では、Henri  Lifchiz（１９９８）による汎オイラー・ラグランジュ（Euler-Lagrange）法を援用することができる。具体的には、数因子2q−1−１等を素数ｐで割り切るか否かのチェックが行われる。例えば、ｐ＝５４１，ｑ＝２７１のとき、
2q−1−1＝ｐ（３５０６７２３８２６３６６３３７４２２９５７０９２４５５４２０２２６７６９４４１７２９０７３４９６９５９３３６８２５２７３６７１６９２５１１４８９８７１９２５）
と因数分解できるので、ｐ＝５４１は素数の可能性が高いと推定され、実際に素数である。しかし、汎オイラー・ラグランジュ法は、べき乗部が１００桁以上になるとメモリの消費が大きく、通常の計算方法では難しいという欠点がある。最も、２００７年現在のSophie-Germain素数のレコードは５００００桁程度に至っている。
【０１５９】
図１（Ｂ）のステップＳ２では、パラメータａ及びｃを定める作業が行われる。２次双曲線群ＨＣでは、（１３−１）式にあるように、「x2＋cx−a≠0」という条件が課されており、これは（６−１）式の分母が０であると、その逆元が存在せず、従って群演算＋が定義できなくなるという要請からきたものである。この条件は、
【０１６０】
【数３０】
2009223035.tif 000045
【０１６１】
とも書けるので、判別式Ｄが平方非剰余であることを意味している。従って、判別式Ｄ／４＝ｃ２＋４ａが平方非剰余であるようにパラメータａ及びｃを定めなくてはならない。なお、判別式Ｄ／４と判別式Ｄを同一視することがある。これは、値４が平方数だからである。
【０１６２】
図１（Ｂ）のステップＳ３では、パラメータｂを定める作業が行われる。パラメータｂについては、ｂ≠ｄ、及び（ｂ（ｂ＋ｃ）−ａ）≠０であるように選択しなければならない。しかし、後者の条件（ｂ（ｂ＋ｃ）−ａ）≠０は、判別式Ｄが平方非剰余にしておくと、自動的に満たされる。更に、（ｂ（ｂ＋ｃ）−ａ）を平方非剰余に選択すると、同値対の出現を防止することができる。ただ、同値対の出現は群演算＋の定義域とは無関係なので、同値対の出現を防止するか否かは設計時に任意に決められる。
【０１６３】
図１（Ｂ）のステップＳ４では、パラメータｄを定める作業が行われる。パラメータｄについては、ｂ≠ｄ、及び（ｄ（ｄ＋ｃ）−ａ）が平方非剰余であるように選択しなければならない。選択されたパラメータｄに対し、Ｐ（ｄ）がゼロ元になる。
【０１６４】
図１（Ｂ）の最後のステップＳ５は、ｘ値を定める作業が行われる。ｘ値については、ｘ≠ｄ、及び（ｘ（ｘ＋ｃ）−ａ）が平方非剰余であるように選択しなければならない。選択されたｘ値に対し、Ｐ（ｘ）がベースポイントになる。
【０１６５】
以上のステップＳ１〜Ｓ５の処理により、暗号に利用する２次双曲線群ＨＣを特定（即ち、曲線パラメータを設定）することができるので、処理が終了（エンド）する。
【０１６６】
図１（Ｂ）の鍵生成方法によれば、後記するように、２次双曲線群ＨＣでは位数ｋが一定であるために、曲線パラメータやゼロ元Ｐ（ｄ）やベースポイントＰ（ｘ）を変動させても２次双曲線群ＨＣの構造が不変で、従前の計算式がそのまま利用でき、プログラム変更が最小限で済む、というメリットがある。従って、演算途中で出現するｘ値（ｘ＝ｘ１）を使って新たなベースポイントＰ（ｘ１）としたり、新たなゼロ元として採用する等の方法により、群演算＋を刻々と変動させる新しい暗号（演算変動型暗号）を容易に構成することができる。
【０１６７】
次に、少し数値を大きくして２次双曲線群ＨＣの具体的な計算を行ってみる。
ここでは、図１（Ｂ）の各ステップＳ１〜Ｓ５に従って、利用する２次双曲線群を特定する。
【０１６８】
図１（Ｂ）の最初のステップＳ１は、法ｐ及び位数ｋを定める作業であるが、大きな素数を扱うのは例題として適当ではない。そこで、数値１０万以下の素数表から（１９−２）式の関係を有するｐとｑの素数の組、Germain素数を選択するものとし、ｐ＝９７１７７，ｑ＝４８５８９として定めることにする。
【０１６９】
図１（Ｂ）のステップＳ２は、パラメータａ及びｃを定める作業である。何れかの数値は任意性があるので、ここでは最初にｃ＝１２３４５と定めることにする。そこで、判別式Ｄにつきオイラーの基準を計算する。ａ＝２３４５６あたりから数値を増加させて検討すると、
ａ＝２３４５６  ｃ＝１２３４５  Ｄ＝２２１３６  オイラーの基準Ｄ＝９７１７６
ａ＝２３４５７  ｃ＝１２３４５  Ｄ＝２２１４０  オイラーの基準Ｄ＝１
ａ＝２３４５８  ｃ＝１２３４５  Ｄ＝２２１４４  オイラーの基準Ｄ＝１
ａ＝２３４５９  ｃ＝１２３４５  Ｄ＝２２１４８  オイラーの基準Ｄ＝９７１７６
ａ＝２３４６０  ｃ＝１２３４５  Ｄ＝２２１５２  オイラーの基準Ｄ＝９７１７６
であるので、判別式Ｄが平方非剰余であるようなａ＝２３４５９を採用することができる。
【０１７０】
図１（Ｂ）のステップＳ３は、パラメータｂを定める作業である。パラメータｂについては、同値対を許容するなら任意に定めることができる。ここでは同値対を禁止するものとし、値（ｂ＊（ｂ＋ｃ）−ａ）が平方非剰余に選択するものとする。ｂ＝４５６７８あたりから数値を増加させて検討すると、
ｂ＝４５６７８  ａ＝２３４５９  ｃ＝１２３４５  （ｂ＊（ｂ＋ｃ）−ａ）＝４２８１４  オイラーの基準（ｂ＊（ｂ＋ｃ）−ａ）＝１
ｂ＝４５６７９  ａ＝２３４５９  ｃ＝１２３４５  （ｂ＊（ｂ＋ｃ）−ａ）＝４９３３９  オイラーの基準（ｂ＊（ｂ＋ｃ）−ａ）＝９７１７６
ｂ＝４５６８０  ａ＝２３４５９  ｃ＝１２３４５  （ｂ＊（ｂ＋ｃ）−ａ）＝５５８６６  オイラーの基準（ｂ＊（ｂ＋ｃ）−ａ）＝１
ｂ＝４５６８１  ａ＝２３４５９  ｃ＝１２３４５  （ｂ＊（ｂ＋ｃ）−ａ）＝６２３９５  オイラーの基準（ｂ＊（ｂ＋ｃ）−ａ）＝１
ｂ＝４５６８２  ａ＝２３４５９  ｃ＝１２３４５  （ｂ＊（ｂ＋ｃ）−ａ）＝６８９２６  オイラーの基準（ｂ＊（ｂ＋ｃ）−ａ）＝９７１７６
であるので、値（ｂ＊（ｂ＋ｃ）−ａ）が平方非剰余であるようなｂ＝４５６７９を採用することができる。
【０１７１】
図１（Ｂ）のステップＳ４は、パラメータｄを定める作業である。パラメータｄについては、ｂ≠ｄ、及び（ｄ（ｄ＋ｃ）−ａ）が平方非剰余であるように選択しなければならない。値（ｄ＊（ｄ＋ｃ）−ａ）が平方非剰余に選択するものとし、ｄ＝３４５６７あたりから数値を増加させて検討すると、
ｄ＝３４５６７  ａ＝２３４５９  ｃ＝１２３４５  （ｄ＊（ｄ＋ｃ）−ａ）＝８８２２３  オイラーの基準（ｄ＊（ｄ＋ｃ）−ａ）＝９７１７６
ｄ＝３４５６８  ａ＝２３４５９  ｃ＝１２３４５  （ｄ＊（ｄ＋ｃ）−ａ）＝７２５２６  オイラーの基準（ｄ＊（ｄ＋ｃ）−ａ）＝９７１７６
ｄ＝３４５６９  ａ＝２３４５９  ｃ＝１２３４５  （ｄ＊（ｄ＋ｃ）−ａ）＝５６８３１  オイラーの基準（ｄ＊（ｄ＋ｃ）−ａ）＝９７１７６
ｄ＝３４５７０  ａ＝２３４５９  ｃ＝１２３４５  （ｄ＊（ｄ＋ｃ）−ａ）＝４１１３８  オイラーの基準（ｄ＊（ｄ＋ｃ）−ａ）＝９７１７６
ｄ＝３４５７１  ａ＝２３４５９  ｃ＝１２３４５  （ｄ＊（ｄ＋ｃ）−ａ）＝２５４４７  オイラーの基準（ｄ＊（ｄ＋ｃ）−ａ）＝９７１７６
であるので、値（ｄ＊（ｄ＋ｃ）−ａ）が平方非剰余であるようなｄ＝３４５６８を採用することができる。
【０１７２】
図１（Ｂ）の最後のステップＳ５は、ｘ値を定める作業である。ｘ値については、ｘ≠ｄ、及び（ｘ（ｘ＋ｃ）−ａ）が平方非剰余であるように選択しなければならない。値（ｘ（ｘ＋ｃ）−ａ）が平方非剰余に選択するものとし、ｘ＝５６７８９あたりから数値を増加させて検討すると、
ｘ＝５６７８９で（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝７６４６７  オイラーの基準（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝１
ｘ＝５６７９０で（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝８０３７  オイラーの基準（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝１
ｘ＝５６７９１で（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝３６７８６  オイラーの基準（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝９７１７６
ｘ＝５６７９２で（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝６５５３７  オイラーの基準（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝９７１７６
ｘ＝５６７９３で（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝９４２９０  オイラーの基準（ｘ＊ｘ＋ｃ＊ｘ−ａ）＝１
であるので、値（ｘ＊ｘ＋ｃ＊ｘ−ａ）が平方非剰余であるようなｘ＝５６７９１を採用することができる。
【０１７３】
以上のようにして、ｐ＝９７１７７，ｑ＝４８５８９，ｃ＝１２３４５，ａ＝２３４５９，ｄ＝３４５６８，ｂ＝４５６７９，ｘ＝５６７９１と、利用する２次双曲線群ＨＣを特定することができる。
【０１７４】
（IV）  鍵設定・鍵生成方法
図１（Ａ）の鍵設定部１１及び鍵生成部１３において、２次双曲線群ＨＣを使用した鍵設定・鍵生成方法であるElGamal暗号（HC-ElGamal）の構成例を説明する。
【０１７５】
一般にElGamal暗号は、素数を法とする既約剰余群ばかりではなく、他の全ての巡回群に応用することができるといわれている。そのため、２次双曲線群ＨＣも離散対数を使う巡回群の一種なので、HC-ElGamal暗号を構成することができる。即ち、従来知られた有限体上の楕円曲線の点群、有限体上の楕円曲線のヤコビ多様体の有理点の点群、及び虚２次体上の整数環のイデアル類群に加えて、新たに有限環上の２次双曲線の点群を加えることができる。この２次双曲線群ＨＣを使用した鍵設定・鍵生成方法では、ハードウェア回路を用いた演算処理等により、或いはＣＰＵ等のプロセッサを用いた演算処理等により、以下のように実行される。
【０１７６】
最初に２次双曲線群ＨＣの位数をｋとしたとき、秘密鍵を乱数ｓ（１＜ｓ＜ｋ）とし、作業鍵Ｙ＝ｓＰを前記群演算＋により計算する。ここで、ｓＰとは群演算＋によりＰを（ｓ−１）回加算する意味である。公開鍵は点Ｙと点Ｐ（ベースポイント）、２次双曲線を特定する曲線パラメータａ、ｂ、ｃ、ｄ及び有限環Ｚ／ｐＺを特定する素数ｐであり、位数ｋは（１９−２）式で与えられる。即ち、公開鍵＝（ａ，ｂ，ｃ，ｄ，ｐ，Ｐ，Ｙ）であり、秘密鍵はｓである。離散対数の計算困難性に基づき、冒認者はＹ＝ｓＰ値が判明しても秘密鍵ｓを直接知ることはできないが、多くともｋ回計算すればｓを知ることがでる。そこで、このような計算が事実上難しいように、実際には大きな素数値ｐ及び乱数値ｓを選ばなければならない。なお、２次双曲線群ＨＣでは、ｘ値に従属して点Ｙや点Ｐが定まるので、実際にはそのｘ成分値であるＰｘやＹｘで指定する。又、ｄ値が分かっているのでＹ＝ｓＰの計算に際し、高速指数演算法を使うことができる。ここで高速指数演算法とは、
【０１７７】
【数３１】
2009223035.tif 000046
【０１７８】
と表現した場合に、元2ipを次々に計算して行くことにより全体の計算回数を少なくする方法である。
【０１７９】
送信側では、メッセージｍにつき、公開鍵を使って暗号文を作成できる。送信側では、乱数ｒ（１＜ｒ＜ｋ）を使ってＣ１＝ｒＰ，Ｃ２＝ｒＹ、及びＣ３＝ｍＣ２（ｍｏｄ  ｐ）を計算する。但し、（Ｃ２）ｘはＣ２のＸ成分値の意味である。暗号文は点Ｃ１及び点Ｃ３、若しくはそのｘ成分値の組み合わせ（（Ｃ１）ｘ，（Ｃ３）ｘ）になる。
【０１８０】
受信側では、秘密鍵ｓを使って、ｍ＝（Ｃ３）ｘ／（ｓＣ１）ｘ（ｍｏｄ  ｐ）を計算する。復号された数値ｍは隠されたメッセージであり、秘密鍵ｓを知る受信者だけが復号できる。復号に際してｓＣ１を計算するのに、前記群演算＋、及び前記高速指数演算法が使用される。
【０１８１】
ここでは、２次双曲線群ＨＣを使用したElGamal暗号（HC-ElGamal）の具体的な計算例を掲げる。
【０１８２】
先に、ｐ＝９７１７７，ｑ＝４８５８９，ｃ＝１２３４５，ａ＝２３４５９，ｄ＝３４５６８，ｂ＝４５６７９，ｘ＝５６７９１と、利用する２次双曲線群ＨＣを特定しておいた。ベースポイントＰはＰ（ｘ）＝Ｐ（５６７９１）で、ゼロ点Ｏは、Ｏ（ｄ）＝Ｏ（３４５６８）である。今秘密鍵ｓを適当にｓ＝３２１０９（１＜ｓ＜ｑ）とし、作業鍵Ｙを計算すれば、Ｙ＝ｓＰ＝Ｙ（６６６２９）と求めることができる。この段階で公開鍵（ａ，ｂ，ｃ，ｄ，ｐ，Ｐ，Ｙ）＝（２３４５９，４５６７９，１２３４５，３４５６８，９７１７７，Ｐ（５６７９１），Ｙ（６６６２９））が定まる。
【０１８３】
送信側では、メッセージｍに対し、前記公開鍵を参照して暗号文を作成する。ここではメッセージｍは、例えばｍ＝２１０９８とする。乱数ｒを適当にｒ＝４３２１０とし、Ｃ１＝ｒＰ，Ｃ２＝ｒＹ、及びＣ３＝ｍＣ２（ｍｏｄ  ｐ）を計算すれば、それぞれＣ１＝Ｃ１（２１６００）、Ｃ２＝Ｃ２（２９６５）、及びＣ３＝Ｃ３（７０７５９）となる。そこで暗号文は（（Ｃ１）ｘ，（Ｃ３）ｘ）＝（２１６００，７０７５９）になるので、これを受信側に対して送信する。
【０１８４】
前記暗号文を受信した受信側が秘密鍵ｓを保有しているのであれば、当該秘密鍵ｓを使って、ｍ＝（Ｃ３）ｘ／（ｓＣ１）ｘ（ｍｏｄ  ｐ）を計算することができる。これにより、（ｓＣ１）ｘ＝２９６５、１／（ｓＣ１）ｘ＝８８８８５、ｍ＝２１０９８を得ることができる。従って、受信側では、送信されてきたメッセージがｍ＝２１０９８である、と知ることができる。
【０１８５】
次に、図１（Ａ）の鍵設定部１１及び鍵生成部１３において、２次双曲線群ＨＣを使用した鍵設定・鍵生成方法であるElGamal署名（HC-ElGamal署名）の構成例を説明する。
【０１８６】
インターネット等では常に悪意の冒認の可能性があり、又、送信データの改ざん等の虞がある。そこで、受信したメッセージに関し、署名者の確認や受信データの真否を確認する方法としてデジタル署名が有効になっている。ここでは、楕円曲線群を利用したデジタル署名を模倣し、以下のようにHC-Elgamal署名を構成する例を説明する。
【０１８７】
先ず、前記２次双曲線群の元Ｐ（ｘ）をベースポイントとして選び、署名生成鍵をｓ（１＜ｓ＜ｋ）に、公開鍵を（ａ，ｂ，ｃ，ｄ，ｐ，Ｐ，Ｙ）とする。ここで、作業鍵Ｙ＝ｓＰである。
【０１８８】
次に、乱数ｒ（１＜ｒ＜ｋ）を生成し、ハッシュ関数ｈを使ってメッセージｍにつきハッシュ値ｈ（ｍ）を生成し、署名（Ｒ，ｔ）を生成する。但し、Ｒ＝ｒＰ及びｔ＝（ｈ（ｍ）−ｓ（Ｒ）ｘ）ｒ−１（ｍｏｄ  ｑ）である。署名者は、前記メッセージｍの他に前記署名（Ｒ，ｔ）を送信側から送信する。
【０１８９】
受信側では、メッセージｍが真に署名者からのものであるのか、改ざんされていないのかを前記署名（Ｒ，ｔ）及び公開鍵を使って確認する。受信側では、ハッシュ関数ｈを使ってメッセージｍにつきハッシュ値ｈ（ｍ）を生成し、ｈ（ｍ）Ｐ＝ｔＲ＋（Ｒ）ｘＹが成立することを確認する。前記署名（Ｒ，ｔ）は、署名生成鍵ｓを知る前記署名者のみが作成できるので、受信側では当該メッセージｍが真に署名者からのものであると確信できるのである。
【０１９０】
ここでは、２次双曲線群ＨＣを使用したElGamal署名（HC-ElGamal署名）の具体的な計算例を掲げる。
【０１９１】
先に、ｐ＝９７１７７，ｑ＝４８５８９，ｃ＝１２３４５，ａ＝２３４５９，ｄ＝３４５６８，ｂ＝４５６７９，ｘ＝５６７９１と、利用する２次双曲線群ＨＣを特定しておいた。ベースポイントＰはＰ（ｘ）＝Ｐ（５６７９１）で、ゼロ点Ｏは、Ｏ（ｄ）＝Ｏ（３４５６８）である。今署名生成鍵ｓを適当にｓ＝３９８７６  （１＜ｓ＜ｑ）とし、作業鍵Ｙを計算すれば、Ｙ＝ｓＰ＝Ｙ（１６５３７）と求めることができる。この段階で、公開鍵（ａ，ｂ，ｃ，ｄ，ｐ，Ｐ，Ｙ）＝（２３４５９，４５６７９，１２３４５，３４５６８，９７１７７，Ｐ（５６７９１），Ｙ（１６５３７））が定まる。
【０１９２】
署名者は、乱数ｒを適当に例えばｒ＝４７６５４（１＜ｒ＜ｑ）とすると、署名鍵ＲをＲ＝Ｒ（２７７５３）と計算できる。又、計算したハッシュ値ｈ（ｍ）をｈ（ｍ）＝２８７６５と置けば、他方の署名鍵ｔを計算できる。更に、ｒ−１（ｍｏｄ  ｑ）＝３９１８３、ｔ＝（ｈ（ｍ）−ｓ（Ｒ）ｘ）ｒ−１（ｍｏｄ  ｑ）＝２４８７８であるので、署名（Ｒ，ｔ）＝（Ｒ（２７７５３），２４８７８）を作成できる。そこで、署名者は、メッセージｍに当該署名（Ｒ，ｔ）を付して送信側から送信する。
【０１９３】
受信側では、受信した署名（Ｒ，ｔ）から、ｔＲ＝７５２３１を計算し、公開鍵から（Ｒ）ｘＹ＝１２２４９を計算し、それらの和（ｔＲ＋（Ｒ）ｘＹ）ｘ＝１７７８１を求める。次に、受信側は、前記メッセージｍにつきハッシュ値ｈ（ｍ）＝２８７６５を生成し、これから（ｈ（ｍ）Ｐ）ｘ＝１７７８１を計算する。このとき、（ｔＲ＋（Ｒ）ｘＹ）ｘ値と（ｈ（ｍ）Ｐ）ｘ値が一致するので、メッセージｍに付されていた署名（Ｒ，ｔ）が正当で、前記署名者からのメッセージであると、確認することができる。
【実施例２】
【０１９４】
図４は、本発明の実施例２に係る秘密鍵変動型ストリーム暗号生成装置を示す概略の構成図である。
【０１９５】
本実施例２の秘密鍵変動型ストリーム暗号生成装置２０は、図１（Ａ）の鍵設定部１１及び鍵生成部１３に相当する２次双曲線群の鍵生成装置であり、縦続接続された（ｍ＋１）個のセル演算器２１−０〜２１−ｍと、各セル演算器２１−０〜２１−ｍのセル出力Ｃ０〜Ｃｍを順次加算してストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）を送出するｍ個の加算器２２−１〜２２−ｍ等とにより構成されている。
【０１９６】
この秘密鍵変動型ストリーム暗号生成装置２０は、実施例１で示された鍵生成方法に従い特定された２次双曲線群ＨＣを利用して構成されている。一般に離散対数を基礎とする双曲線暗号の計算負担は重く、このままではストリーム暗号に適しているとはいえない。そこで、計算するビット数を減らして見かけ上の有効ビット数を増やす工夫が求められる。本実施例２の秘密鍵変動型ストリーム暗号生成装置２０では、複数のセル演算器２１−０〜２１−ｍにおいて少ないビット数での２次双曲線群演算を行わせ、そのセル出力を組み合わせることにより、擬似乱数であるストリームを生成する構成になっている。
【０１９７】
各セル演算器２１−０〜２１−ｍは、ベースポイントＰから前のセル演算器の提供する秘密鍵ｓに基づき、当該セル演算器で予め定められた群演算＋により作業鍵Ｙを演算し、当該作業鍵Ｙから攪拌関数により当該セル出力Ｃ及び次のセル演算器に引き渡す新たな秘密鍵ｓを出力する。最初のセル演算器２１−０では、初期秘密鍵としてｓ０が採用され、次回からは最終セル演算器２１−ｍの出力する秘密鍵ｓｍが使用される。従って、秘密鍵の初期値ｓ０が定められた後は、各セル演算器２１−０〜２１−ｍで採用される秘密鍵ｓ１〜ｓｍは次々に変動するので、秘密鍵ｓは１回限りの使い捨てになる。
【０１９８】
又、各セル演算器２１−０〜２１−ｍでの群演算＋は異なることから、例えベースポイントＰが同じ場合であっても、その計算された作業鍵Ｙは異なり、攪拌関数を経由した後は事実上独立したセル出力Ｃ及び事実上独立した新たな秘密鍵ｓを出力する。従って、各セル出力Ｃ０〜Ｃｍを単純に合成してストリーム出力（Ｃ０，Ｃ１，，，Ｃｍ）を構成した場合、ｍ＋１倍のビット数を有するストリーム出力のように擬似的に見えるストリームが生成される。
【０１９９】
本実施例２では、初期化のため予め各セル演算器２１−０〜２１−ｍを所定回動作させて初期状態を定めて置く必要がある。少なくともｍ回の演算を行わなければ全セル演算器２１−０〜２１−ｍが同時に演算できる状態にはならない。又、秘密鍵ｓの初期値ｓ０の秘密性を担保させるためにもｍの数倍の回数だけ演算を行い、その間のストリームを切り捨てる必要があるかも知れない。
【０２００】
本実施例２に係るストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）は、厳密な意味で乱数ではない。秘密鍵ｓが秘密であること、作業鍵Ｙは各セル演算器２１−０〜２１−ｍの群演算で計算されるが離散対数を知ることが困難であるので前記秘密鍵ｓが容易に知れないこと、新たなストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）は攪拌関数が一方向性を有するので作業鍵Ｙを遮蔽していること等の作用により、一定の規則に従って生成されているのに外部からはそのように見えない、というだけである。特に、各セル演算器２１−０〜２１−ｍの採用する群演算は、何れも位数ｋを共通にする２次双曲線群ＨＣの演算であり、曲線パラメータが異なるだけである。しかし、群演算が異なると剰余環Ｚ／ｐＺの限定方法が異なってくるために、出現する元やその順番が全く異なったものになる。従って、各セル演算器２１−０〜２１−ｍのセル出力Ｃ０〜Ｃｍを合成した場合に、合成されたストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）は見かけ上独立した出力の寄せ集めの出力になる。
【０２０１】
本実施例２に係るストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）は、各セル演算器２１−０〜２１−ｍの演算時間に依存して出力される。各セル演算器２１−０〜２１−ｍは同時に演算を行うことができるので、演算に使用されるビット数をｍ＋１倍したビット数を有するストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）が、当該演算時間で出力可能である。これはストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）の高速化を意味している。例えば、１７個のセル演算器２１−０〜２１−１６が１６ビットで演算されたとき、セル出力Ｃ０〜Ｃ１６は１５ビットになるので、２５５ビットのストリーム出力（Ｃ０，Ｃ１，・・・，Ｃ１６）がほぼセル演算器２１−０〜２１−１６の１６ビット演算の時間で一時に得られる。一般的にｎ個のセル演算器２１−０〜２１−（ｎ−１）を使用すれば、ストリーム出力（Ｃ０，Ｃ１，・・・，Ｃ（ｎ−１））をｎ倍に高速化することができる。２次双曲線群ＨＣの群演算では、逆元演算の負荷が重いことが分かっている。しかし、後記する「逆元計算後回し法」を使用すると、この演算速度を著しく改善することが可能である。
【０２０２】
各セル出力Ｃ０〜Ｃｍを単純に合成してストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）を構成した場合、そのセル出力Ｃ０〜Ｃｍが直接外部に見えるので、暗号解読性が高まる虞がある。そこで、ストリーム出力（Ｃｍ｜Ｃ０，Ｃ０｜Ｃ１，Ｃ１｜Ｃ２，・・・，Ｃｍ−１｜Ｃｍ）（演算｜はビット排他的論理和（ＥＯＲ）演算である。）のように、隣り合うセル出力Ｃ０，Ｃ１，・・・を合成して新たなストリーム出力とする等、セル出力合成やビット合成によりセル出力を隠蔽する手段が有効である。隣り合うセル出力Ｃ０，Ｃ１，・・・をビットＥＯＲ演算で合成した場合、前記１６ビット演算の場合、セル出力Ｃ０〜Ｃｍは１５ビットになるので、２５５ビットのストリーム出力（Ｃｍ｜Ｃ０，Ｃ０｜Ｃ１，・・・）が一時に得られる。一般的に、セル出力合成等により、ストリーム出力（Ｃｍ｜Ｃ０，Ｃ０｜Ｃ１，・・・）のビット数が犠牲になる（減少する）構成になることがある。
【０２０３】
本実施例２による秘密鍵変動型ストリーム暗号生成装置２０では、ｍ＋１個のセル演算器２１−０〜２１−ｍが秘密鍵ｓを介して縦続接続されているので、たまたま何れかのセル演算器で同じ秘密鍵ｓを受け渡された場合には、その後はストリーム出力（Ｃｍ｜Ｃ０，Ｃ０｜Ｃ１，・・・）が周期的に出力され、擬似乱数としての特性が失われてしまう。これを防ぐ方法としては、ｍ＋１個のセル演算器２１−０〜２１−ｍの内部状態関数として次のセル演算器へ受け渡す秘密鍵ｓを決定する方法が有る。この方法では、何れかのセル演算器で前と同じ秘密鍵ｓを受け渡された場合であっても、その後のストリームは異なるものになり、周期的な出力を避けることができる。簡単な構成例としては、秘密鍵ｓ（ｉ）＝ｆ（Ｙｘ（ｉ−１），Ｙｘ（ｉ＋１））やｓ（ｉ）＝ｆ（Ｙｘ（ｉ−１），Ｙｘ（ｉ−２））のように、前後のセル演算器の作業鍵Ｙの関数として、計算された本来の秘密鍵の全部又は一部を変更する方法が考えられる。
【０２０４】
秘密鍵ｓ値の大きさ（ｍｏｄ  ｑ）がある程度小さいか０であると、計算された暗号解読性が高まる虞が有る。そこで、秘密鍵ｓ値の上位ビットが０である等をゲートで検出し、所定のビットを立てて一定値を加算する方法が有効な場合がある。
【０２０５】
ここでは、本実施例２による秘密鍵変動型ストリーム暗号生成装置２０の具体的な構成例を掲げる。
【０２０６】
本実施例１では、
ｐ＝９７１７７，ｑ＝４８５８９，ｃ＝１２３４５，ａ＝２３４５９，ｄ＝３４５６８，ｂ＝４５６７９，ｘ＝５６７９１
と利用する２次双曲線群ＨＣを特定しておいたが、ｐ＝９７１７７であるので、これは１７ビットセル演算器２１−０・・・に相当する。そこで、１７ビットセル演算器２１−０・・・を３個（ｍ＝２）有するストリーム暗号生成装置２０を構成することにする。分かりやすい構成例なので、前記ストリーム出力（Ｃ０，Ｃ１，・・・，Ｃｍ）の被覆化や前記内部状態に依存した秘密鍵ｓの決定等の方法は採用していない。
【０２０７】
第１のセル演算器２１−０は前記２次双曲線群ＨＣを利用するものとし、作業鍵Ｙから以下のようにしてセル出力Ｃ０、及び次のセル演算器２１−１に渡す秘密鍵ｓ１を計算する。
Ｃ０＝Ｙｘ（５ビット右巡回シフト）
ｓ１＝Ｙｘ（１０ビット右巡回シフト）￥４
【０２０８】
この秘密鍵ｓ１の計算において、演算子￥は整数割り算で、４で割るのは位数ｑ以下になるようにビット数の整合を行うからである。これらの操作は前記攪拌関数に相当するが、簡単のため第２及び第３のセル演算器２１−１，２１−２でも同じ構成を採用することにする。
【０２０９】
次に、本実施例１に従い、図１（Ｂ）のフローに従って他の２個のセル演算器２１−１，２１−２を構成する。前記２次双曲線群ＨＣについては添え字０を使って、
ｐ＝９７１７７，ｑ＝４８５８９，ｃ０＝１２３４５，ａ０＝２３４５９，ｄ０＝３４５６８，ｂ０＝４５６７９，ｘ０＝５６７９１
と変更しておく。
【０２１０】
さて、ｃ１＝１２３４６、ｃ２＝１２３４７とした場合に、図１（Ｂ）のステップＳ２以下に従って計算すると、
ｐ＝９７１７７，ｑ＝４８５８９，ｃ１＝１２３４６，ａ１＝２３４５８，ｄ１＝３４５７０，ｂ１＝４５６８０，ｘ１＝５６７８０
ｐ＝９７１７７，ｑ＝４８５８９，ｃ２＝１２３４７，ａ２＝２３４６２，ｄ２＝３４５６９，ｂ２＝４５６８０，ｘ２＝５６７８１
という２つの２次双曲線群ＨＣを求めることができる。これら３つの２次双曲線群ＨＣは同じ位数ｑを有しているが、曲線パラメータが異なるために異なる群演算＋を有しており、その結果、出現する元やその順番が全く異なったものになる。
【０２１１】
楕円曲線暗号では、素数位数を得るために曲線パラメータに乱数を使用する等して素数位数判定作業を繰り返す必要があり、少なくとも同じ位数を有する曲線パラメータを複数整える作業はかなり難しい、と考えられる。しかし、前記のように、双曲線暗号では同じ位数を有する複数、若しくは多数の２次双曲線群ＨＣを確定することは容易である。楕円曲線暗号と比べて、暗号に鍵生成が簡単であるといえる。
【０２１２】
本実施例２による秘密鍵変動型ストリーム暗号生成装置２０をハードウェアで実現することは容易である。各セル演算器２１−０〜２１−ｍはコプロセッサ、若しくは専用剰余演算器又は専用べき乗剰余演算器等で実現できる。レジスタに曲線パラメータや秘密鍵ｓの初期値ｓ０を置く方式で、演算ビット数は固定であるが、共通のハードウェアで異なる２次双曲線群ＨＣを取り扱うことができる。
【０２１３】
図５（Ａ）は図４の秘密鍵変動型ストリーム暗号生成装置２０の計算例（ｍ＝２）を示す図、及び、図５（Ｂ）は図４の秘密鍵変動型ストリーム暗号生成装置２０のストリーム出力例（ｍ＝２）を示す図である。
【０２１４】
秘密鍵ｓの初期値ｓ０＝２１０９８から始めて、セル演算器２１−０のベースポイントＰ０（５６７９１）から作業鍵ＹをＹ＝ｓ０Ｐ０（５６７９１）により求めると、そのｘ成分はＹｘ＝８８３２７となる。但し、作業鍵Ｙの計算に使用された群演算＋（０）は、
ｃ０＝１２３４５，ａ０＝２３４５９，ｄ０＝３４５６８，ｂ０＝４５６７９
により特定した演算である。Ｙｘは２進数表示で１０１０１１００１０００００１１１（８８３２７）である。そこで前記攪拌関数に従いＹｘを５ビット右巡回シフトしてセル出力Ｃ０＝００１１１１０１０１１００１０００（３１４３２）を得る。又、Ｙｘを１０ビット右巡回シフトして０１０００００１１１１０１０１１０を得た後４で割る整数演算を行うと、ｓ１＝０１０００００１１１１０１０１（８４３７）が得られる。同様の処理を縦続するセル演算器２１−１及び２１−２で行うと、最初のサイクルでのセル出力
（００１１１１０１０１１００１０００）（００１１１１０１０１１１０１０１０）（０１１０１１００１１１０００１０１）
を得ることができる。即ち、１６ビットセル演算器２１−０〜２１−２の１計算時間で１７ビットＸ３＝５１ビットのストリーム出力を一時に得ることができた。
【０２１５】
この具体例では、３サイクル目（３＿３）で秘密鍵ｓ＝３９１と比較的小さな値が出現している。秘密鍵ｓ値の大きさ（ｍｏｄ  ｑ）がある程度小さいか０であると、計算された暗号解読性が高まる虞が有る。そこで、秘密鍵ｓ値の上位ビットが０である等をゲートで検出し、所定のビットを立てて一定値を加算する方法が有効な場合がある。しかし、この具体例ではそこまで考慮していない。
【０２１６】
図６は、図４の秘密鍵変動型ストリーム暗号生成装置により暗号化及び復号化を行ってデータの送受信を行う通信システムの概略の構成図である。この図６には、図４の秘密鍵変動型ストリーム暗号生成装置２０による暗号化及び復号化の方法が開示されている。
【０２１７】
図６の通信システムでは、送信側においてストリーム暗号生成装置２０−１及び排他論理和ゲート（以下「ＥＯＲゲート」という。）２３−１により生成された暗号化データＥＤ１のＩＰｖ６（IP  version  6）パケット２４−１を、ＩＰネットワーク２５を介して受信側へ送り、受信側において送られてきたＩＰｖ６パケット２４−２を受け取り、ストリーム暗号生成装置２０−２及びＥＯＲゲート２３−２により復号化する構成になっている。
【０２１８】
例えば、秘密に係る動画ファイル等の入力データＤｉｎに対し、送信側のストリーム暗号生成装置２０−１が暗号ストリームＣＳ１を供給し、両者の排他論理和がＥＯＲゲート２３−１で取られて、ＩＰｖ６パケット２４−１のデータ領域に暗号化データＥＤ１として格納される。ＩＰｖ６パケット２４−１のＩＰｖ６ヘッダには、ペイロード長等のデータの他に、その拡張ヘッダ（暗号化ヘッダ）においてストリーム暗号生成に係る同期情報ＳＩ１が格納される。同期情報ＳＩ１は、ストリーム暗号生成装置２０−１の初期化までのサイクル数、ペイロードに格納された暗号ストリームＣＳ１の開始サイクル数、終端サイクル数等であり、復号化に必要な情報である。送信者がＩＰｖ６パケット２４−１を送信し、受信者がＩＰネットワーク２５を介して当該ＩＰｖ６パケット２４−２を受信した後、ＩＰヘッダの拡張ヘッダに格納された同期情報ＳＩ２が取り出されて、受信側のストリーム暗号生成装置２０−２に提供される。又、ＩＰｖ６パケット２４−２のデータ領域から暗号化データＥＤ２が取り出された後、同期情報ＳＩ２に対応して出力された暗号ストリームＣＳ２との排他論理和がＥＯＲゲート２３−２で取られて、出力データＤｏｕｔが復元される。
【０２１９】
この暗号化及び復号化の方式では、秘密鍵ｓの初期値ｓ０は送受信側で共有されており、暗号ストリームＣＳ１も定められた順番にストリーム暗号生成装置２０−１から出力される。どのように秘密鍵ｓ０を共有するかの方法は開示されていない。通常は所定の暗号化プロトコルによるしかない。ＩＰｓｅｃ（IP  security  protocol）では「ＩＫＥ（Internet  Key  Exchange）」という暗号鍵交換のためのプロトコルが用意されている。又、本実施例２に係る方法では、仮にＩＰネットワーク２５においてＩＰｖ６パケット２４−１の一部が喪失した場合には、それ以後正しい復号化はできなくなる。この場合は、当該喪失パケットの再度の送信を要求することになる。
【０２２０】
この暗号化及び復号化方式を更に改良する手段として、ストリーム暗号生成装置２０を構成しているセル演算器２１−０〜２１−ｍに係る曲線パラメータ情報をＩＰｖ６パケット２４−１，２４−２のＩＰｖ６ヘッダ若しくはデータ領域に載せる方式が考えられる。曲線パラメータは群演算を定めるので秘密情報にすることもできるが、例え曲線パラメータが知られても秘密鍵ｓを知らない限り暗号ストリームＣＳ２を復号することはできない。この改良方式は、同じハードウェアを有するセル演算器２１−０〜２１−ｍの汎用性を確保する効果を有しており、所定の時刻毎に群演算を変化させて安全性を高める方式を採用することができる。
【実施例３】
【０２２１】
図７は、本発明の実施例３に係る拡張２次双曲線群の鍵生成方法（ｎ＝ｐ１ｐ２の場合）を示すフローチャートであり、実施例１を示す図１（Ｂ）のフローチャートに対応している。
【０２２２】
この図７のフローチャートでは、図１（Ａ）中の曲線パラメータ設定部１２において行われる曲線パラメータの設定方法が示されており、ステップＳ１１〜Ｓ１５の処理により、拡張２次双曲線群ＥＨＣにおける（６−１）式の曲線パラメータａ，ｂ，ｃ，ｄ，ｘが設定される。
【０２２３】
この図７のフローチャートを説明する前に、本実施例３における拡張２次双曲線群ＥＨＣ等の基礎技術を説明する。
【０２２４】
本実施例３では、法ｎを合成数とした場合に実施例１における２次双曲線群ＨＣを拡張して拡張２次双曲線群ＥＨＣを構成し、当該拡張２次双曲線群ＥＨＣを用いた双曲線暗号の鍵生成方法を開示し、その応用問題として新たな素因数分解の方法を開示する。
【０２２５】
実施例１における２次双曲線群ＨＣは（１３−１）式で定義され、「平方非剰余」という言葉で定義を与えた。しかし、例えば(x2＋cx−a)が平方非剰余という条件は、Legendreの記号を使うと、
【０２２６】
【数３２】
2009223035.tif 000047
【０２２７】
と表されるときの２次双曲線群ＨＣの自然な拡張は、各素因数ｐｉに付き、全く同じ条件を課すことである。
【０２２８】
【数３３】
2009223035.tif 000048
【０２２９】
ここで、Legendreの記号の拡張であるJacobiの記号を導入することが考えられる。
ｎが１より大きな奇数で、（ｍ，ｎ）＝１である整数ｍにつき、
【０２３０】
【数３４】
2009223035.tif 000049
【０２３１】
と定義し、左辺をJacobiの記号と呼び、右辺をLegendreの記号とする。ここで、右辺のLegendreの記号を確定するには、予めｎの素因数が知られていなければならない。従来のオイラーの規準は、（３１−３）式を計算する際にそのまま使える。
【０２３２】
以上の前提に立って、拡張２次双曲線群ＥＨＣを定義する。
拡張２次双曲線群ＥＨＣを、
【０２３３】
【数３５】
2009223035.tif 000050
【０２３４】
という構成にした。この定義では、Jacobiの記号を使用せず、Legendreの記号のみが使用されている。後記するように、Jacobiの記号を導入すると群の構成が維持できないことが分かっているからである。
【０２３５】
ここでは、始めに法ｎが合成数でｎ＝ｐ１ｐ２のときの拡張２次双曲線群ＥＨＣの構造を明らかにする。拡張２次双曲線群ＥＨＣの位数ｋは、（３１―２）式を満たすｘ値の個数で計算できる。素因数ｐ１，ｐ２は互いに異なり（ｐ１≠ｐ２）、独立して（３１−２）式を満たすｘ値を決められるので、それらの数同士の異なる組み合わせで生じるｘ値がその位数ｋを決める。ここでいう位数ｋとは、拡張２次双曲線群ＥＨＣの異なる元Ｐ（ｘ）の総個数であって、当該Ｐ（ｘ）をベースポイントとする生成群（巡回群）Ｑ（ｘ）の位数ｋｇ、若しくはその最大値ｋｑではない。即ち、拡張２次双曲線群ＥＨＣの位数ｋは原則として１の素因数で与えられる位数（１９−１）式の積で与えられる。
【０２３６】
【数３６】
2009223035.tif 000051
【０２３７】
２次双曲線群ＨＣではその位数ｋと生成群位数の最大値ｋｑとは一致していたが、拡張２次双曲線群ＥＨＣではこれらは一致しないことがある。
【０２３８】
生成群（巡回群）Ｑ（ｘ）の最大位数ｋｑについては、後記するように、判別式Ｄの属性に依存していることが新たに分かっています。判別式Ｄの属性が、
【０２３９】
【数３７】
2009223035.tif 000052
【０２４０】
であり、且つ、（ｋ１，ｋ２）＝１である場合には、原則として（３２−１）式で与えられる。ここでは、その巡回の周期が問題になるので、双方の素因数で共通するものがあって、（ｋ１，ｋ２）＝ｈ≠１である場合には、その「各位数の素因数同士の異なる組み合わせ」が固有の存在で、周期の対象になると考える。即ち、何れの位数に含まれるか区別ができない共通する素因数ｈを、重ねて含める組み合わせは出現しない、と考える。素因数の集合でいえば、「和集合」が該当する。これは双方の位数の最小公倍数（ＬＣＭ：Least  Common  Multiple）が最大位数ｋｑとなることを意味している。
【０２４１】
非特許文献（宮川洋、他「符号理論」、１９７３、昭晃堂、Ｐ．２０４）によれば、複数の最小多項式Ｍｉで構成される生成多項式Ｇを多項式の剰余類環（法ｘｎ−１）で考えた場合に、前記最小多項式Ｍｉの周期ｎｉの最小公倍数が、前記生成多項式Ｇの周期ｔになる旨が記載されている。巡回群の一種である拡張２次双曲線群でも同様である、と考えられる。ここでは、２次双曲線群と多項式の剰余類環の間に
法ｎ（合成数）＞法ｘｎ−１
ベースポイントＰ（ｘ）＞生成多項式Ｇ（ｘ）
生成群の最大位数（＝周期）ｋｑ＞生成多項式Ｇ（ｘ）の周期ｔ
個別の位数ｋｉ＞最小多項式Ｍｉ（ｘ）の周期ｎｉ
が、それぞれ対応している。２次双曲線群ＨＣにおける要素の方が簡素であるのは、多項式の剰余類環における演算が乗法に止まるのに対し、２次双曲線群ＨＣの群演算が離散対数の関係に立つからだと考えられる。
【０２４２】
【数３８】
2009223035.tif 000053
【０２４３】
従って、法ｎが合成数の場合には、拡張２次双曲線群ＥＨＣの位数ｋ及び生成群Ｑ（ｘ）の最大位数ｋｑは常に合成数になる。この事実は、素数位数を有する拡張２次双曲線群ＥＨＣが存在せず、その暗号等の利用も若干の制限を受けることを意味している。最大位数ｋｑを有する生成群Ｑ（ｘ）のベースポイントＰ（ｘ）を如何なる元にすべきかの規準が、未だ完全には知られていないからである。
【０２４４】
ここで数値例を掲げる。例えば、ｐ１＝１７，ｐ２＝２３，ｎ＝３９１の拡張２次双曲線群ＥＨＣの位数ｋは、ｋ１＝（ｐ１−１）／２＋１と位数ｋ２＝（ｐ２−１）／２＋１の積であり、ｋ＝ｋ１ｋ２＝１０８である。又、生成群Ｑ（ｘ）の最大位数ｋｑは、１の素因数で与えられる位数ｋ１＝（ｐ１−１）／２＋１と位数ｋ２＝（ｐ２−１）／２＋１の最小公倍数で与えられ、
ｋｑ＝ＬＣＭ（ｋ１，ｋ２）＝ＬＣＭ（９，１２）＝３６
である。
【０２４５】
次に、図７のフローチャートにて示される拡張２次双曲線群の鍵生成方法（ｎ＝ｐ１ｐ２の場合）について説明する。
整数論的関数ｙ
【０２４６】
【数３９】
2009223035.tif 000054
【０２４７】
の曲線パラメータａ，ｂ，ｃ，ｄ，ｘは、ハードウェア回路を用いた選択・演算処理等により、或いはＣＰＵ等のプロセッサを用いた選択・演算処理等により、以下のステップＳ１１〜Ｓ１５により設定される。
【０２４８】
図７の処理が開始（スタート）すると、第１のステップＳ１１において、素因数ｐ１，ｐ２及び位数ｋ等が定められる。暗号解読時の計算量を増やすためには、これらの値を大きな数値に選ばなければならない。拡張２次双曲線群ＥＨＣでは、その位数ｋは（３２−１）式で、その生成群の最大位数ｋｑは（３２−３）式で与えられるので、素因数ｐ１，ｐ２を決定することは、同時に拡張２次双曲線群ＥＨＣの位数ｋ等を指定したことになる。当該最大位数ｋｑは合成数なので、ステップＳ１５において最大位数ｋｑを有するベースポイントＰ（ｘ）を定める際に、多少の試行錯誤が必要である。ただ、通常最大位数を有するベースポイントＰ（ｘ）の個数が最も多いので、数回の試行で当該最大位数を有するベースポイントＰ（ｘ）に当たる可能性が高い、といえる。
【０２４９】
第２のステップＳ１２において、パラメータａ及びｃが定められる。実際には判別式Ｄだけに制約があるので、何れかのパラメータを任意に定めることができる。判別式
Ｄ／４＝ｃ２＋４ａ
に対し、その属性を
（Ｄ／ｐ１）＝−１；（Ｄ／ｐ２）＝−１；
であるように設定する。
【０２５０】
第３のステップＳ１３において、パラメータｂが定められる。パラメータｂは、同値対の出現を防ぐために
（（ｂ（ｂ＋ｃ）−ａ）／ｐ１）＝−１；（（ｂ（ｂ＋ｃ）−ａ）／ｐ２）＝−１
を満たすように選ばれるが、同値対を許容するならば、任意に選択することができる。従って、このステップＳ１３における前記条件を省略することができる。
【０２５１】
第４のステップＳ１４において、パラメータｄ、即ちゼロ元Ｐ（ｄ）が定められる。つまり、（（ｄ（ｄ＋ｃ）−ａ）／ｐ１）＝−１；（（ｄ（ｄ＋ｃ）−ａ）／ｐ２）＝−１；ｂ≠ｄ
であるように設定する。
【０２５２】
第５のステップＳ１５において、ｘ値、即ちベースポイントＰ（ｘ）が定められる。つまり、
（（ｘ（ｘ＋ｃ）−ａ）／ｐ１）＝−１；（（ｘ（ｘ＋ｃ）−ａ）／ｐ２）＝−１；ｘ≠ｄ
であるように設定する。
【０２５３】
ステップＳ１３，Ｓ１４，Ｓ１５はそれぞれ同じ条件であるので、それらのパラメータを１度の計算で求め、それぞれのパラメータに割り当てることができる。ただ、前記条件を満たすｘ値を任意に選択すると、最大位数ｋｑの約数を位数とする生成群Ｑ（ｘ）が出現する可能性がある。従って、最大位数ｋｑを有するベースポイントＰ（ｘ）を選択できない場合がある。
【０２５４】
前記試行錯誤の第１の方法は、最大位数ｋｑの次の大きさを有する位数ｋｔにおいて、試行するベースポイントＰ（ｘ）に対し、ｋｔＰ（ｘ）≠ＯとなるＰ（ｘ）を探すことである。即ち、ｋＰ（ｘ）＝Ｏであり、ｋｔＰ（ｘ）≠Ｏ（ｋｔ＜ｋ）であれば、当該Ｐ（ｘ）による生成群Ｑ（ｘ）の位数は、最大位数ｋｑを有する確率が高いと考えられる。このためには素因数で最小のもの（最小素因数という。）で最大位数ｋｑを割った位数を試行位数ｋｔとする。拡張２次双曲線群ＥＨＣでは、その最大位数ｋｑは（３２−３）式で与えられるので、素因数の１つが４ｍ＋３型の素数であれば、最小素因数２を有する。
【０２５５】
ここでは、前記拡張２次双曲線群ＥＨＣの計算例を使って、この方法を試してみる。最大位数ｋｑ＝２８であり、前記最小素因数２であるので、ｋｔ＝ｋｑ／２＝１４である。そこで、各素因数につき（３１−２）式を満たすｘ値を小さいほうから試すと、
ｋｔＰ（０）＝Ｏ；ｋｔＰ（２）＝Ｏ；ｋｔＰ（６）＝Ｐ（２８）≠Ｏ；
であるので、Ｐ（６）は最大位数ｋｑを有するベースポイントの可能性が高いと考えられ、実際に最大位数ｋｑを有している。しかし、双方の素因数が共に４ｍ＋１型の素数で、且つ、小さな素因数を有していない場合には、この方法は有効ではない。なお、ｋｔＰの計算では、ｋｔ値を２進展開して高速指数計算を利用することができる。
【０２５６】
前記試行錯誤の第２の方法は、分配法則の成立を確認することである。分配法則
ｍ（Ｐ＋Ｒ）＝ｍＰ＋ｍＲ
は、ＰもＲも最大位数ｋｑを有する生成群Ｑに属するときだけ完全に成立し、その他の場合には成立しないのが一般的である。特に、ｍ値を前記試行位数ｋｔに対しｋｔ≦ｍ≦ｋｑに選択すれば、不成立の蓋然性が高くなる。前記条件を満たす元Ｐ及びＲの選択では、
Ｒ（ｙ）＝ｑＰ（ｘ）；（ｑ，ｋ）＝１
であるようなｙ値を有する元Ｒを試行選択する。ベースポイントをＰ（ｘ）とする生成群Ｑ（ｘ）が最大位数ｋｑを有する場合には、前記Ｒ（ｙ）をベースポイントとする生成群Ｑ（ｙ）も最大位数ｋｑを有することが分かっているからである。
【０２５７】
拡張２次双曲線群ＥＨＣの具体的な計算例を掲げる。
図８は、本発明の実施例３に係る法ｎ＝９１、位数ｋ＝２８の拡張２次双曲線群（生成群Ｑ（ｘ））の構造を示す図である。この図８では、共通因数h=1のとき、＞位数kgを有する生成群Ｑ(x)の個数はφ(kg)個であることが開示されている。
【０２５８】
（３１−２）式で与えられるシステムで、ｒ＝７，ｓ＝１３、従ってｎ＝９１の場合、（３１−４）式で与えられる拡張２次双曲線群ＥＨＣの最大位数ｋｑは、（３２−３）式からしてｋｑ＝２８になる。判別式Ｄ／４＝ｃ２＋４ａについては、（Ｄ／ｒ）＝−１，（Ｄ／ｓ）＝−１であるようにパラメータｃ＝１，ａ＝８を決定し、τ（ｄ）／ｒ）＝−１，（τ（ｄ）／ｓ）＝−１であるようにτ（ｄ）を選択するものとし、ゼロ点をｄ＝２に選択する。又、ベースポイントの選択は、τ（ｘ）／ｒ）＝−１，（τ（ｘ）／ｓ）＝−１であるようにｘ値を選択するものとする。
【０２５９】
前記のような曲線パラメータａ，ｂ，ｃ，ｄ，ｘで特定された拡張２次双曲線群ＥＨＣは、そのベースポイントをＰ（ｘ）とするとき、生成群（部分群）Ｑ（ｘ）を生成する。即ち、
位数ｋｇ＝１の生成群：φ（１）＝１個  ｛Ｑ（２）｝
位数ｋｇ＝２の生成群：φ（２）＝１個  ｛Ｑ（２８）｝
位数ｋｇ＝４の生成群：φ（４）＝２個  ｛Ｑ（４１），Ｑ（６７）｝
位数ｋｇ＝７の生成群：φ（７）＝６個  ｛Ｑ（２３），Ｑ（３７），Ｑ（５１），Ｑ（５８），Ｑ（６５），Ｑ（７９）｝
位数ｋｇ＝１４の生成群：φ（１４）＝６個  ｛Ｑ（０），Ｑ（１４），Ｑ（４９），Ｑ（６３），Ｑ（７７），Ｑ（８４）｝
位数ｋｇ＝２８の生成群：φ（２８）＝１２個  
｛Ｑ（６），Ｑ（１１），Ｑ（１３），Ｑ（２５），Ｑ（２７），Ｑ（３２），Ｑ（３９），Ｑ（５３），Ｑ（６２），Ｑ（７６），Ｑ（８８），Ｑ（９０）｝
という構造を有する。この構造は、２次双曲線群の各位数ｋ１，ｋ２の値のみに依存して定まる。従って、これらの関係から、２次双曲線群ＨＣと同様に、ｋｇの約数ｄにつき
【０２６０】
【数４０】
2009223035.tif 000055
【０２６１】
という関係式が成立する。なお、生成群の定義は前記と同様で、
Ｑ（ｘ）＝｛ｍＰ（ｘ）｜Ｐ（ｘ）∈ＥＨＣ，ｋｇＰ（ｘ）＝Ｏ，１≦ｍ≦ｋｇ，ｋｇは最大位数ｋｑの約数｝
・・・・（３４−２）
のように定義できる。例えば、上記Ｑ（６）の場合、位数ｋｇ＝２８で、
Ｑ（６）＝｛１Ｐ＝（６，０）；２Ｐ＝（４９，７６）；３Ｐ＝（１１，３６）；４Ｐ＝（６５，３０）；５Ｐ＝（９０，３５）；６Ｐ＝（１４，５５）；
７Ｐ＝（６７，１５）；８Ｐ＝（５８，６５）；９Ｐ＝（６２，６３）；１０Ｐ＝（６３，６２）；１１Ｐ＝（３９，４３）；１２Ｐ＝（５１，９）；１３Ｐ＝（２７，４２）；１４Ｐ＝（２８，４１）；１５Ｐ＝（３２，７８）；１６Ｐ＝（２３，３７）；１７Ｐ＝（７６，４９）；１８Ｐ＝（０，６９）；１９Ｐ＝（２５，２２）；２０Ｐ＝（７９，１６）；２１Ｐ＝（４１，２８）；２２Ｐ＝（８４，１３）；２３Ｐ＝（８８，５０）；２４Ｐ＝（３７，２３）；２５Ｐ＝（１３，５６）；２６Ｐ＝（７７，４８）；２７Ｐ＝（５３，２９）；２８Ｐ＝（２，２）；｝
である。生成群Ｑ（ｘ）の総個数は、拡張２次双曲線群の位数ｋと一致する。この様子が図８に示されている。
【０２６２】
２次双曲線群ＨＣでは、位数ｋｇを有する生成群Ｑ（ｘ）の個数は、φ（ｋｇ）個で与えられていた。合成数位数の拡張２次双曲線群ＥＨＣで位数ｋｇを有する生成群Ｑ（ｘ）の個数ψ（ｋｇ）は、当該合成数位数ｋ１，ｋ２の２つの因数ｄ１，ｄ２がそれぞれｋ１，ｋ２の約数の何れかである場合に、（ｋ１，ｋ２）＝１の関係では、当該因数ｄ１，ｄ２を位数とする２次双曲線群ＨＣにおける生成群の個数φ（ｄ１），φ（ｄ２）の積和になる、と考えられる。従って、（ｋ１，ｋ２）＝１の関係が維持されている限り、各位数ｋ１，ｋ２の因数ｄ１及びｄ２を用いて、
【０２６３】
【数４１】
2009223035.tif 000056
【０２６４】
と表すことができる。（ｋ１，ｋ２）＝１では（ｄ１，ｄ２）＝１であるので、オイラー関数φの乗積的（multiplicative）性質からφ（ｄ１）φ（ｄ２）＝φ（ｄ１ｄ２）＝φ（ｋｇ）が成立し、且つ、その組み合わせが１通りだけなので、
ψ(kg)=f(kg)  ・・・・（３４−４）
が成立する。即ち、（ｋ１，ｋ２）＝１の場合、位数ｋｇを有する生成群Ｑ（ｘ）の個数は、合成数位数の拡張２次双曲線群ＥＨＣでも、素数位数の２次双曲線群ＨＣと同様の表現で求めることができる。しかし、（ｋ１，ｋ２）＝ｈ≠１のときは、その共通因数ｈにつきどのような取り扱いをすべきか明確ではない。
【０２６５】
前記具体的計算例では、各素因数のみで構成される位数ｋ１，ｋ２が共通の素因数を有しておらず、（ｋ１，ｋ２）＝１の関係にあった。これに対し位数ｋ１，ｋ２が共通の素因数を有している場合には、どのような構造を有するのかをここで明らかにする。
【０２６６】
図９は、本発明の実施例３に係る法ｎ＝３９１、位数ｋ＝１０８の拡張２次双曲線群（生成群Ｑ（ｘ））の構造を示す図である。この図９では、共通因数ｈ≠１のとき、＞位数ｋｇを有する生成群Ｑ（ｘ）の個数はψ（ｋｇ）個であることが開示されている。
【０２６７】
具体例としては、ｒ＝１７，ｓ＝２３、従ってｎ＝３９１の場合、（３２−３）式で与えられる拡張２次双曲線群ＥＨＣの位数ｋは
ｋｑ＝ＬＣＭ（ｋ１，ｋ２）＝（９，１２）＝３６
になる。判別式Ｄ／４＝ｃ２＋４ａについては、（Ｄ／ｒ）＝−１，（Ｄ／ｓ）＝−１であるようにパラメータｃ＝１，ａ＝１を決定し、τ（ｄ）／ｒ）＝−１，（τ（ｄ）／ｓ）＝−１であるようにτ（ｄ）を選択するものとし、ゼロ点をｄ＝３に選択する。又、ベースポイントの選択はτ（ｘ）／ｒ）＝−１，（τ（ｘ）／ｓ）＝−１であるようにｘ値を選択するものとする。
【０２６８】
このとき特定された拡張２次双曲線群ＥＨＣは、そのベースポイントをＰ（ｘ）とするとき、生成群（部分群）Ｑ（ｘ）を生成する。即ち、
位数ｋｇ＝１の生成群：ψ（１）＝１個  ｛Ｑ（３）｝
位数ｋｇ＝２の生成群：ψ（２）＝１個  ｛Ｑ（１０５）｝
位数ｋｇ＝３の生成群：ψ（３）＝８個  ｛Ｑ（２０），Ｑ（９５），Ｑ（１０４），Ｑ（１１２），Ｑ（１７３），Ｑ（２６５），Ｑ（３２５），Ｑ（３４２）｝
位数ｋｇ＝４の生成群：ψ（４）＝２個  ｛Ｑ（７１），Ｑ（２０７）｝
位数ｋｇ＝６の生成群：ψ（６）＝８個  ｛Ｑ（３６），Ｑ（８７），Ｑ（１５６），Ｑ（１９７），Ｑ（２０６），Ｑ（２４８），Ｑ（２７５），Ｑ（３６７）｝
位数ｋｇ＝９の生成群：ψ（９）＝１８個  ｛Ｑ（８１），Ｑ（１２７），Ｑ（１４１），Ｑ（１５０），Ｑ（１５８），Ｑ（１６４），Ｑ（１８１），Ｑ（２１０），Ｑ（２２７），Ｑ（３０２），Ｑ（３１１），Ｑ（３１９），Ｑ（３３４），Ｑ（３４８），Ｑ（３６５），Ｑ（３７１），Ｑ（３８０），Ｑ（３８８）｝
位数ｋｇ＝１２の生成群：ψ（１２）＝１６個  ｛Ｑ（２），Ｑ（１０），Ｑ（１９），Ｑ（２７），Ｑ（７８），Ｑ（８８），Ｑ（１３８），Ｑ（１６３），Ｑ（１８０），Ｑ（２４０），Ｑ（２５７），Ｑ（２９９），Ｑ（３０８），Ｑ（３０９），Ｑ（３２６），Ｑ（３７７）
位数ｋｇ＝１８の生成群：ψ（１８）＝１８個  ｛Ｑ（１３），Ｑ（２２），Ｑ（４５），Ｑ（５９），Ｑ（６４），Ｑ（８２），Ｑ（９１），Ｑ（１１０），Ｑ（１３３），Ｑ（１８３），Ｑ（２２９），Ｑ（２４３），Ｑ（２５２），Ｑ（２６６），Ｑ（２９４），Ｑ（３１２），Ｑ（３１７），Ｑ（３６３）｝
位数ｋｇ＝３６の生成群：ψ（３６）＝３６個  ｛Ｑ（２３），Ｑ（２５），Ｑ（４２），Ｑ（４８），Ｑ（５６），Ｑ（７１），Ｑ（７３），Ｑ（７９），Ｑ（９６），Ｑ（１１５），Ｑ（１２４），Ｑ（１２５），Ｑ（１４２），Ｑ（１４７），Ｑ（１６１），Ｑ（１８４），Ｑ（１９３），Ｑ（２０９），Ｑ（２１７），Ｑ（２２６），Ｑ（２３２），Ｑ（２３４），Ｑ（２４９），Ｑ（２６３），Ｑ（２７８），Ｑ（２８０），Ｑ（２８５），Ｑ（２８６），Ｑ（２９５），Ｑ（３０３），Ｑ（３３１），Ｑ（３４５），Ｑ（３５４），Ｑ（３６８），Ｑ（３７０），Ｑ（３８７）｝
である。合計１０８個の生成群ができる。この様子が図９に示されている。
【０２６９】
（ｋ１，ｋ２）＝ｈ≠１のとき、位数ｋｇを有する生成群Ｑ（ｘ）の個数ψ（ｋｇ）がどのような関係式で表現されるかは、容易に推定できない。そこで、実際に（ｋ１，ｋ２）＝ｈ≠１であるこの具体例から探ることになる。
【０２７０】
最大位数ｋｑは、ｋｑ＝ＬＣＭ（ｋ１，ｋ２）＝ＬＣＭ（９，１２）＝３６である。素因数ｈ＝３が共通の要素であるので、各生成群の位数ｋｇを与える生成群の個数ψ（ｋｇ）は前記、及び図９で開示した通りである。この数値関係を眺めると、例えば、ｋｇ＝１８の約数ｄ｜ｋｇに係る和につき
ψ(18)＋ψ(9)＋ψ(6)＋ψ(3)＋ψ(2)＋ψ(1)=18＋18＋8＋8＋1＋1=54＝3kg
が成立している。因数ｈ＝３は、前記共通の因数（ｋ１，ｋ２）＝ｈ≠１に該当する。これは、位数ｋｇ以下である生成群の個数の総和が、当該位数ｋｇの倍数に増加したことを意味している。共通の因数ｈは、２次双曲線群ＨＣの生成群の最大位数ｋｑの増加には寄与しないで、生成群の個数の総和に寄与している。これが、拡張２次双曲線群ＥＨＣで群位数ｋと生成群の最大位数ｋｑが異なる原因である。そこで、一般的に
【０２７１】
【数４２】
2009223035.tif 000057
【０２７２】
が成立していると予想される。即ち、位数ｋｇ以下の生成群Ｑ（ｘ）の個数の総和は、当該位数ｋｇの倍数、特に共通の因数ｈになる。証明はない。共通の因数ｈは、固定ではなくて、ｋｇの値に依存している。即ち、一般的には最大公約数（ＧＣＤ：Greatest  Common  Divisor）を用いてｈ＝ＧＣＤ（ｋｇ，ｋ１，ｋ２）、若しくは、単に
ｈ＝（ｋｇ，ｋ１，ｋ２）  ・・・・（３５−２）
になっている。
【０２７３】
（３５−１）式の特別の場合として、ｋｇ＝ｋｑ＝ＬＣＭ（ｋ１，ｋ２）の場合を考えると、整数論では、
ｋ１ｋ２＝ＬＣＭ（ｋ１，ｋ２）ＧＣＤ（ｋ１，ｋ２）及びＧＣＤ（ＬＣＭ（ｋ１，ｋ２），ｋ１，ｋ２）＝ＧＣＤ（ｋ１，ｋ２）
の関係が成立するので、
【０２７４】
【数４３】
2009223035.tif 000058
【０２７５】
となる。この（３５−３）式は、（３４−１）式の拡張に相当する。
整数論のメービィウス（Ｍｏｂｉｕｓ）の反転公式（inversion  formula）によれば、
【０２７６】
【数４４】
2009223035.tif 000059
【０２７７】
と、反転する公式が成立する。但し、μ（ｄ）はメービィウス関数と呼ばれるもので、値ｄの素因数でその２乗以上のものが存在するときにμ（ｄ）＝０、全部１乗である場合は、その個数をｍとしたときにμ（ｄ）＝（−１）ｍ、μ（１）＝１という性質を有している。
【０２７８】
ここで、メービィウス関数μ（ｄ）は、巡回群につき２つの意味を持つと考えられる。
第１は、値
【０２７９】
2009223035.tif 000060
【０２８０】
である場合に、値d0=p1p2…pm以外の値ｄの素因数でその２乗以上のものが排除されていることである。これは、値
2009223035.tif 000061
だけが基本周期で、それ以外の値ｄの素因数でそのべき乗部が２乗以上のものは周期に成り得ないことを示している。ｄ＝ｎである場合の基本周期d0は、この巡回群の全ての固有周期を決める基礎に成っている。別の見方をして見る。値
【０２８１】
2009223035.tif 000062
【０２８２】
である場合は、値d0=p1p2…pmとの関係として、
【０２８３】
2009223035.tif 000063
【０２８４】
であるので、
【０２８５】
2009223035.tif 000064
【０２８６】
の関係式が成立するが、これは周期ｎの下で基本周期d0に係る構造がｎ／ｄ０回繰り返される構造が存在することを意味している。
【０２８７】
第２は、基本周期d0=p1p2…pmである場合に、ｍが偶数である場合にメービィウス関数は（＋１）に、ｍが奇数である場合にメービィウス関数は（−１）になるが、これは、例えば巡回群の個数を計算するときに、重複した計算を排除する意味がある。最初にμ（ｄ）＝１と定めたことは、偶数個素因数で（＋１）に、奇数個素因数で（−１）に定めたことを意味し、周期１を有するｎ個の巡回群から、見掛け上周期ｎを有しｎ値の約数ｄを周期とする巡回群の個数を交互に差し引きして行く。交互に差し引く理由は以下の通りである。
【０２８８】
まず、基本周期d0に係る素因数を要素とする集合を考え、その集合では或る周期ｐ１とｐ２をその積周期ｐ１ｐ２の内側に配置する。このようにすると、例えば、偶数個素因数ｐ１ｐ２を有する集合の内側に奇数個素因数ｐ１若しくはｐ２が配置される構造ができ、その逆の構造も成立するので、第１に前記（＋１）若しくは（−１）の符号をそれぞれの集合に割り当てることができ、第２にある倍数の集合の内側にその約数の集合を配置できる。
【０２８９】
このとき、周期ｎのみを固有周期とする巡回群の個数φ（ｎ）を求めることを考えると、最初にメービィウス関数により基本周期d0以外の周期につき排除できる。次に、周期ｄ＝１の場合は一番外側の集合、基本周期d0に係る素因数の積集合に対応し、ｎ個ある。次にその１つ内側の集合を考えると、これは基本周期d0の約数であり、素因数が１つ少なくなっている。従って、メービィウス関数で逆の符号が割り当てられており、前記ｎ個の巡回群から、その約数を周期とする巡回群の個数を差し引くことになる。但し、その集合の内側に別の集合がある場合には、この作業を継続することにより、その約数に係る固有周期の個数のみを差し引くようにする。周期ｎを考えた場合は、その約数に係る周期ｄを有する巡回群の個数はｎ／ｄ個なので、
【０２９０】
2009223035.tif 000065
【０２９１】
により、周期ｎのみを固有周期とする巡回群の個数φ（ｎ）を求めることができる。結局、周期ｎが基本周期d0を有するときには、上式のｎ／ｄという形で基本周期d0を有する巡回群の個数の増加に寄与しているだけである。
【０２９２】
さて、（３５−１）式及び（３５−２）式と（３５−４）式を対比させ、その反転を行って（３５−５）式を求めると、
【０２９３】
【数４５】
2009223035.tif 000066
【０２９４】
と、当初の目的であった位数ｋｇを有する生成群Ｑ（ｘ）の個数ψ（ｋｇ）を明示の形で求めることができた。ここで、ｋ１＝ｋ，ｋ２＝１と置いて拡張形でない２次双曲線群ＨＣに帰着させると、（ｋｇ／ｄ，ｋ，１）＝１であることから、（３５−６）式は、
【０２９５】
【数４６】
2009223035.tif 000067
【０２９６】
に帰着する。整数論によれば、（３５−７）式の右辺はオイラーの関数φ（ｋｇ）そのものである。（３５−７）式によればψ（ｋｇ）＝φ（ｋｇ）であるので、再び（３４―４）式を確認することになった。（３５−６）式で与えられる関数ψ（ｋｇ）は、オイラーの関数の拡張形であるので、「拡張オイラーの関数（extended  totient  function）」と呼ぶことにする。２次双曲線群ＨＣでは位数ｋｇを有する生成群の個数はφ（ｋｇ）個であったが、拡張２次双曲線群ＥＨＣでは位数ｋｇを有する生成群の個数はψ（ｋｇ）個である。
【０２９７】
（３５−６）式についての直接の証明はないが、一応次のように解釈される。まず、（ｋ１，ｋ２）＝ｈ≠１のときは、その共通因数ｈは常に構成素因数の２乗以上の形で現れるので、メービィウス関数の性質から前記基本周期に影響を与えない。従って、（３５−６）式の項数が実質的に増えることはなく、当該基本周期を有する巡回群の個数ｋｇ／ｄに影響するだけである。ここで位数ｋ＝ｋ１ｋ２の構造を考えれば、
【０２９８】
2009223035.tif 000068
【０２９９】
となって、共通部分を有しない構造が、ｈ回繰り返される構造が存在すると考えられる。
基本周期を有する巡回群の個数の値ｋｇ／ｄの前記共通部分は（ｋｇ／ｄ，ｋ１，ｋ２）であるので、上記議論により当該基本周期を有する巡回群の個数は、ｋｇ／ｄから（ｋｇ／ｄ）（ｋｇ／ｄ，ｋ１，ｋ２）に増加する。
【０３００】
拡張オイラーの関数（３５−６）式の威力を理解するために、ここではより複雑な共通の因数ｈを有する拡張２次双曲線群ＥＨＣにより、具体的な試行数値例を掲げる。
ｒ＝２９，ｓ＝５９，ｎ＝１７１１で、ａ＝９，ｃ＝１，ｄ＝７に選択された場合、
位数ｋｇ＝１の生成群：ψ（１）＝１個
位数ｋｇ＝２の生成群：ψ（２）＝１個
位数ｋｇ＝３の生成群：ψ（３）＝８個
位数ｋｇ＝５の生成群：ψ（５）＝２４個
位数ｋｇ＝６の生成群：ψ（６）＝８個
位数ｋｇ＝１０の生成群：ψ（１０）＝２４個
位数ｋｇ＝１５の生成群：ψ（１５）＝１９２個
位数ｋｇ＝３０の生成群：ψ（３０）＝１９２個
であった。この拡張２次双曲線群ＥＨＣは、単独の２次双曲線群ＨＣの位数ｋ１＝１５，ｋ２＝３０で構成され、共通因数はＧＣＤ（ｋ１，ｋ２）＝１５である。最大位数ｋｑは、ｋｑ＝ＬＣＭ（ｋ１，ｋ２）＝ＬＣＭ（１５，３０）＝３０である。位数ｋｇ＝９，２５の生成群は出現しない。この理由は、これらの位数が最大位数ｋｑの約数ではないからである。
例えば、ｋｇ＝６の場合、（３５−６）式から、
【０３０１】
【数４７】
2009223035.tif 000069
【０３０２】
で、実際に試行計算で数えた生成群の個数と一致する。（３５−６）式を使えば、単独の２次双曲線群ＨＣの位数ｋ１，ｋ２で構成される拡張２次双曲線群ＥＨＣで、位数ｋｇを有する生成群の個数を予め知ることができる。
【０３０３】
拡張２次双曲線群ＥＨＣの定義においてJacobiの記号を導入すると、群の構成が維持できないことが分かっている。２次双曲線群ＨＣで問題になった群演算の定義域と閉鎖性に関し、Jacobiの記号による剰余環Ｚ／ｎＺの限定を行う場合を検討してみる。
拡張２次双曲線群ＥＨＣをJacobiの記号を使って、
【０３０４】
【数４８】
2009223035.tif 000070
【０３０５】
と定義してみる。この場合巡回群の構造が破壊されてしまうことが分かっている。
形式上、法がｐであった場合と同様に、法ｎの場合にも群演算の閉鎖性と未定義域の解消を達成することができる。即ち、Ｒ（ｘ３）＝Ｐ（ｘ１）＋Ｑ（ｘ２）という群演算を行ったとき、
【０３０６】
【数４９】
2009223035.tif 000071
【０３０７】
であるので、
【０３０８】
【数５０】
2009223035.tif 000072
【０３０９】
になる。なお、（３６−２）式の分母は、法ｎのもとでも平方剰余になっている。群演算の関係式は剰余演算と関係なく成立するからである。更に、（３６−２）式の分母が０になる未定義状態では、
【０３１０】
2009223035.tif 000073
【０３１１】
の関係が成立するので、
【０３１２】
【数５１】
2009223035.tif 000074
【０３１３】
であるので、一方の値を当該集合から排除することにより、群演算の未定義域の解消を図ることができる。
【０３１４】
しかし、Legendreの記号で（３６−３）式の実現を考えると、平方剰余数を取り扱うことになる。例えば、法ｎが合成数で素因数ｒ及びｓの積で与えられるときに、拡張２次双曲線群ＥＨＣをどのように構成すれば良いのかを検討してみる。この場合には（３６−３）式の
【０３１５】
【数５２】
2009223035.tif 000075
【０３１６】
により実現できる。この組み合わせは（３６−２）式で与えられる演算結果が、（３６−５）式、（３６−６）式に係る属性の同一性を維持するように定めてある。ここで、ゼロ元Ｐ（ｘ）（ｘ＝ｄ）もｘ値の１つであるので、ｘ値とｄ値は、τ（ｘ）＝ｘ２＋ｃｘ−ａ値とτ（ｄ）＝ｄ２＋ｃｄ−ａ値が同一の属性になるように選ばれる。これは、始めにゼロ元Ｐ（ｄ）を定めることが、（３６−５）式、（３６−６）式の何れかのシステムを選択したことを意味している。
【０３１７】
（３６−５）式、（３６−６）式の何れかのシステムを選択した場合の最大の問題点は、群演算の途中で逆元を有しない値が大量に生成されることである。法ｎ＝ｒｓの場合、ｒｓ＝０（ｍｏｄ  ｎ）であるから、素因数ｒ，ｓの倍数は全て逆元を有しない。例えば、或る数ｘの逆元（ｍｏｄ  ｎ）がｙであるとすると、ｘｙ＝１（ｍｏｄ  ｒ），ｘｙ＝１（ｍｏｄ  ｓ）の双方が成立しなければならない。しかし、数ｘが素因数ｒ，ｓの倍数であれば、少なくとも何れかが満たされない。それ故、素因数ｒ，ｓの倍数は全て逆元を有しない。又、群演算の未定義域を有し、群の構造が維持できていない。この原因は、
【０３１８】
【数５３】
2009223035.tif 000076
【０３１９】
を採用したことにより、（３６−４）式において、（３６−７）式の当該素因数に係る属性が排他対と等しくなることにある。この結果、当該素因数についてゼロ割の状態が出現する。
【０３２０】
しかし、後記するように逆元演算を最後まで実行しないで、群演算を実行する方法（逆元計算後回し法）が存在する。このとき、見掛け上群の構造が維持され、見掛け上の位数も求めることができる。数学上は、半群（semigroup）、特に単位元を有する単位半群（monoid）である。半群の観点からすると、（３６−１）式で与えた拡張２次双曲線群の定義が復活する。この半群を「拡張２次双曲線半群」と呼ぶことにする。又、分かりやすい表現として、ここでは属性の変更を受け入れた場合も含めて、広く「群のイメージ（image）」と呼ぶことにする。そこで、群のイメージの具体的な計算例を紹介する。
【０３２１】
図１０（Ａ）〜（Ｃ）は、ｒ＝１３，ｓ＝１７，ｎ＝２２１である拡張２次双曲線半群の具体例であって、各属性につき位数ｋｇを与える生成群Ｑ（ｘ）の個数を示す図である。このうち、図１０（Ａ）は位数ｋｇを与える生成群の個数（τ（ｄ））とτ（ｘ）の属性一致）を示す図、図１０（Ｂ）は位数ｋｇを与える生成群の個数（τ（ｄ））とτ（ｘ）の属性不一致）を示す図、及び、図１０（Ｃ）は判別式Ｄとτ（ｘ）の属性不一致、及びτ（ｄ）とτ（ｘ）の属性一致を示す図である。
【０３２２】
図１０（Ａ）では、各生成群の計算にあたってゼロ元の属性（τ（ｄ）／ｒ），（τ（ｄ）／ｓ）をベースポイントＰ（ｘ）と一致させている。この結果を見ると、各属性を有する生成群の個数は等しくなく、ｎ／４の値に近いというだけで、４等分されてはいない。この原因は、τ（ｘ）のように関数になっている場合、関数値の制限から取り得る値の個数に偏りが生じるからである。
【０３２３】
図１０（Ｂ）では、各生成群の計算にあたってゼロ元の属性（τ（ｄ）／ｒ），（τ（ｄ）／ｓ）をベースポイントＰ（ｘ）と一致させない場合を試みている。この場合、ゼロ元は出現しないが、逆元計算後回し法の計算方法からしてゼロ元に相当する一致を得ることができる。これによれば、位数ｋｇは上段の図の場合の２倍になっており、その個数は一致している。（３６−４）式からすれば、２回の群演算を続けて実行するとその属性は元に戻る。従って、（３７−３）式、（３７−４）式の演算を２回実行する操作を群演算と考えるとつじつまが合う。即ち、ゼロ元の属性をベースポイントＰ（ｘ）の属性と一致させない場合には、群演算が変更になるだけで、その位数は一致する。別のいい方をすれば、τ（ｘ）とτ（ｄ）の属性が一致しない拡張２次双曲線半群は、当該属性が一致する拡張２次双曲線群と同型（isomorphic）で、群演算が異なっているだけである。
【０３２４】
図１０（Ｃ）では、各生成群の計算にあたって判別式Ｄとτ（ｘ）の属性不一致、及びτ（ｄ）とτ（ｘ）の属性一致の条件下で位数ｋｇ及びその個数を求めている。これによれば、判別式Ｄの属性に依存して拡張２次双曲線半群の構造が大きく変化する。判別式Ｄはもともと２次関数の特性を決めているのであるから、当該２次関数であるτ（ｘ）やτ（ｄ）の属性よりも基本的であると考えられる。前記先の特許出願で明らかにしていたように、判別式Ｄの属性によりτ（ｘ）が平方剰余若しくは平方非剰余であるｘ値の個数は（ｐ−１）／２個若しくは（ｐ＋１）／２個になる。従って、位数ｋｇを与える生成群Ｑ（ｘ）の個数、特に最大位数ｋｑは、（３２−３）式ではなく
【０３２５】
【数５４】
2009223035.tif 000077
【０３２６】
で与えられる。この結果は重要な意味がある。即ち、判別式Ｄの属性を変更することにより拡張２次双曲線半群の構造が大きく変更でき、且つ、どのように変更されるのか予め分かっているのであるから、拡張２次双曲線半群を従来の暗号理論や数学理論の進歩に寄与する「道具」として利用することができる。本実施例４では、素因数分解の問題に対し、拡張２次双曲線半群のこの特性を使う。
【０３２７】
図１０（Ｃ）の計算例における最大位数ｋｑを（３６−８）式から確認しておく。
ｒ＝１３，ｓ＝１７で
（Ｄ／ｒ）＝−１，（Ｄ／ｓ）＝−１で、ｋｑ＝ＬＣＭ（（ｒ＋１）／２，（ｓ＋１）／２）＝ＬＣＭ（７，９）＝６３；
（Ｄ／ｒ）＝−１，（Ｄ／ｓ）＝＋１で、ｋｑ＝ＬＣＭ（（ｒ＋１）／２，（ｓ−１）／２）＝ＬＣＭ（７，８）＝５６；
（Ｄ／ｒ）＝＋１，（Ｄ／ｓ）＝−１で、ｋｑ＝ＬＣＭ（（ｒ−１）／２，（ｓ＋１）／２）＝ＬＣＭ（６，９）＝１８；
（Ｄ／ｒ）＝＋１，（Ｄ／ｓ）＝＋１で、ｋｑ＝ＬＣＭ（（ｒ−１）／２，（ｓ−１）／２）＝ＬＣＭ（６，８）＝２４；
と予想計算でき、実際に試行計算で数えた値と一致する。
【０３２８】
拡張２次双曲線半群については、未だその構造が十分に理解されておらず、その研究途上にある。
【０３２９】
ここでは、２次双曲線群ＨＣの高速計算（逆元計算後回し法）を解説する。
２次双曲線群ＨＣの計算を通常通り行うと、逆元計算の負担が重く、法ｐの大きさが大きいときには、ストリーム暗号等の応用が困難になる虞が有る。そこで、計算量を節減するために、逆元計算を最後まで行わず、最後の１回だけ逆元計算を行う方法（逆元計算後回し法）が考えらる。この方法は、分子と分母の計算を別々に行う。
群演算＋をR(x3)=P(x1)＋Q(x2)の形で計算した場合、
【０３３０】
【数５５】
2009223035.tif 000078
【０３３１】
のように表記を変更する。同様に、x1=(x11,x12)、x2=(x21,x22)とすることにする。（３７−１）式にこれを代入すると、
【０３３２】
【数５６】
2009223035.tif 000079
【０３３３】
従って、
x31=(d＋c)x11x21＋(−a)(x11x22＋x21x12)＋adx12x22  ・・・（３７−３）
x32=−x11x21＋d(x11x22＋x21x12)＋(dc−a)x12x22  ・・・・（３７−４）
と、分子と分母を峻別した形で計算可能である。なお、初期値として、x1=(x1,1)、x2=(x2,1)を使う。
【０３３４】
拡張２次双曲線半群の元は、分子である値ｘ１１と分母である値ｘ１２を用いて、Ｐ（ｘ１１，ｘ１２）若しくはｙ値を明示してＰ（ｘ１１，ｘ１２，ｙ１１，ｙ１２）のように表現できる。なお、（３６−２）式において、ｘ１＝ｄのとき、ｘ２の属性はそのまま維持されてｘ３に伝えられるので、拡張２次双曲線半群のゼロ元Ｐ（ｄ，１）は拡張２次双曲線群のゼロ元と等価である。
【０３３５】
この計算では１回の群演算に付き、剰余積を９回行う必要がある。最後の１回だけ逆元計算を行う方法で、単に位数ｋ値を知るだけなら、逆元の計算も不要である。位数ｋの計算の場合、ｍＰの計算でｍＰ（ｘ）＝Ｐ（ｄ）になる場合は、x31=d・x32となるので、ｍ＝ｋに至ったと知ることができる。又、元同士の一致は、互いに持ち寄った分子と分母の積の一致で判定できる。一般に逆元計算では、ｘ値の逆元をｘφ（ｎ）−１（ｍｏｄ  ｎ）により求める方法が通常である。しかし、ｎ値しか知らない場合に、そのφ（ｎ）値を高速計算できないのであれば、その逆元計算を高速実行できない不利がある。逆元計算後回し法は、「群のイメージ」を計算するのに有効な方法で、素因数分解の問題等で活用することができる。又、ストリーム暗号の高速計算において著しい効果を発揮する。
【実施例４】
【０３３６】
図１１は、本発明の実施例４に係る拡張２次双曲線群等を用いて法ｎ（ｎ＝ｐ１ｐ２）の素因数を求める鍵生成方法を示すフローチャートであり、実施例３を示す図７のフローチャートに対応している。
【０３３７】
この図１１のフローチャートでは、図１（Ａ）中の曲線パラメータ設定部１２において行われる曲線パラメータの設定方法（即ち、拡張２次双曲線群等を用いて法ｎ（ｎ＝ｐ１ｐ２）の素因数を求める方法）が示されており、ステップＳ２１〜Ｓ３１の処理により実行されれる。
【０３３８】
この図１１のフローチャートを説明する前に、実施例３で開示した拡張２次双曲線群ＥＨＣを利用し、ある数ｎが、２個の素因数から成る場合で（ｎ＝ｐ１ｐ２）、値ｎを知ってその素因数を求める方法（１）〜（３）を考えてみる。
【０３３９】
（１）  直接計算法
直接計算法は、素因数の値として、変数ｐ１に直接１から代入しその数を順次増やしてゆく方法である。
今、数ｎを２進数表示し、n=2L＋…とし、p2=2M＋…とすれば、p1＝2L−M＋1からp1=2L−Mまでを代入すれば、その積が値ｎに一致するか分かる。その計算量は、2L−M回の積であり、奇数だけを代入するとすれば2L−M−1回の積で足りる。従って、全体の計算量は、
【０３４０】
【数５７】
2009223035.tif 000080
【０３４１】
になる。
（２）  拡張２次双曲線群を使う方法
拡張２次双曲線群を使う方法としては、拡張２次双曲線群ＥＨＣの位数ｋを求めて、その素因数を（３１−２）式から計算する方法がある。位数ｋｑ＝ＬＣＭ（ｋ１，ｋ２）であり、この値は積ｋ１ｋ２よりも小さく、最大公約数ＧＣＤ（ｋ１，ｋ２）よりも大きく、ＧＣＤ（ｋ１，ｋ２）＝１の場合には積ｋ１ｋ２に一致する。そこで、
【０３４２】
2009223035.tif 000081
【０３４３】
の範囲にあることが知れ、位数ｋは法ｎが大きいときにはおよそｎ／４の上限値を有していることが分かる。
位数ｋｑ＝ＬＣＭ（ｋ１，ｋ２）であり、これはＭＡＸ（ｋ１，ｋ２）≦ｋであり、ｋ１ｋ２≦ｋ２なので、
√ｋ１√ｋ２≦ｋ  ・・・・（３８−４）
を意味している。（３８−３）式から、
【０３４４】
2009223035.tif 000082
【０３４５】
適当に曲線パラメータやベースポイントを定め、その位数計算を行った場合、その群演算の計算量は、直接計算法と変わりがない。しかし、通常、最大公約数に小さな素因数を有しているので、その小さな素因数は容易に拡張２次双曲線群ＥＨＣを使う方法により知ることができる。ただ、発見される素因数は最大位数ｋｑに対するもので、法ｎの素因数ではないことに注意する必要がある。直接的にｐ１やｐ２を知ることはできない。
【０３４６】
特別な場合、German素数やSophie-German素数の場合、片方の位数が素数であると、もう片方の値（ｐ±１）／２を見掛け上の位数とする群イメージが生成されることが分かっている。（３２−３）式でｋ１若しくはｋ２が素数であるために、（ｋ１，ｋ２）＝１が成立するからである。この場合、拡張２次双曲線群ＥＨＣの最大位数ｋｑの約数の１つが値（ｐ±１）／２程度であるので、√ｎ回程度の群演算でゼロ元に至るベースポイントを発見でき、その演算時間は比較的短く済む。又、求めた位数ｋｇを用いてｐ＝２ｋｇ±１と、直接法ｎの素因数を求めることができる。
【０３４７】
（３）  拡張２次双曲線群のイメージを使う方法
拡張２次双曲線群のイメージを使う方法は、拡張２次双曲線群ＥＨＣを使うのではなく、群構造が破壊されるのを承知で、平方剰余を与えるパラメータを使用し、「群のイメージ」を取り扱う方法である。この方法は、パラメータに使用する試数等を誤って採用したときに、自動的に実行される。一般的に、
（Ａ）  判別式Ｄの属性で、法ｎの素因数の何れかに係るものが平方剰余である場合は、群演算の途中でゼロ割が発生する。
（Ｂ）  τ（ｘ）は平方非剰余だがｄ値は平方剰余である場合、即ちゼロ元とベースポイントの間で属性の不一致がある場合も、群演算の途中でゼロ割が発生する。この場合には、巡回群の構造が壊れて擬似ゼロ元等のイメージが出現する。
【０３４８】
ただ、何れの場合も、逆元計算後回し法でゼロ割を回避し、拡張２次双曲線半群を構成することができる。判別式Ｄの属性変更を受け入れて、その見掛け上の群構造を調べると、法ｎの素因数に関連した様々な位数を有するイメージが出現する。そこでこのような位数を調べれば、法ｎの素因数を求める手掛かりになる。特に、（３２−３）式で法ｎの素因数を求めることができなかった場合に、（３６−８）式により法ｎの素因数を求める手掛かりを得る場合がある。
【０３４９】
前記拡張２次双曲線群ＥＨＣを使う素因数分解の方法で問題となるのは、法ｎを知って、その素因数を知らない場合に、どのようにして拡張２次双曲線群ＥＨＣを構成するのか、曲線パラメータ等を定めるのか、という問題である。例えば、（３１−２）式を満たすｘ値をどのようにして求めるべきか。
【０３５０】
ここでは、法ｎが合成数で素因数ｐ１及びｐ２の積で与えられるときに、拡張２次双曲線群ＥＨＣをどのように構成すれば良いのかを検討してみる。
この場合には、採用される曲線パラメータ等の選択のために、例えば（Ｄ，ｐｉ）＝１である値Ｄに対し、２個の合同式
【０３５１】
【数５８】
2009223035.tif 000083
【０３５２】
という条件を満たさなければならない。（３９−１）式、（３９−２）式を満たすＤ値の個数は、（Ｄ，ｎ）＝１で、且つ、原始根が存在する場合には、その属性に従って正確にφ（ｎ）／４個で、４分割されていることが分かっている。従って、ｎ値を知って当該Ｄ値が、４分割されたうち何れの集合に属しているのかを知る方法が発見できれば、（３９−１）式、（３９−２）式を満たすＤ値を判定できることになる。
【０３５３】
［定理３９−１］
法ｎ＝ｐ１ｐ２である場合に、剰余環Ｚ／ｎＺの元は、素因数ｐ１若しくはｐ２の倍数を除き、その元ｘの属性（ｘ／ｐ１）＝±１，（ｘ／ｐ２）＝±１に従って４等分割され，その個数はφ（ｎ）／４個である。
【０３５４】
［証明］
法ｎ＝ｐ１ｐ２である場合、素因数ｐ１若しくはｐ２の倍数でない元の個数はφ（ｎ）個であり、素因数ｐ１若しくはｐ２の倍数は値０を含めてｎ−φ（ｎ）個ある。さて、オイラー関数φの乗積的な性質からφ（ｎ）＝φ（ｐ１）φ（ｐ２）であり、これは素因数ｐ１若しくはｐ２の構造が法ｎの下でも生き残っていることを示している。即ち、剰余環Ｚ／ｎＺのφ（ｎ）個の元は、剰余環Ｚ／ｐ１Ｚのφ（ｐ１）個の元と剰余環Ｚ／ｐ２Ｚのφ（ｐ２）個の元との組み合わせで与えられ、その組み合わせは剰余環Ｚ／ｎＺの元に一対一で対応する。今、剰余環Ｚ／ｐ１Ｚの原始根をｒとし、剰余環Ｚ／ｐ２Ｚの原始根をｓとした場合に、剰余環Ｚ／ｎＺの元ｘは、剰余関係抜きで、
x=rhsl;(h=0,,,p1−1),(1=0,,,p2-1)  ・・・・（１）
と表される。ここで、値ｒｈは、ｈ値が偶数の場合には法ｐ１に対し平方剰余、奇数の場合には平方非剰余である。同様に、値ｓｌは、ｌ値が偶数の場合には法ｐ２に対し平方剰余、奇数の場合には平方非剰余である。そこで、
【０３５５】
【数５９】
2009223035.tif 000084
【０３５６】
と表したときに、（２）式では１個のｓｌ値に対し、その属性によらず、（ｘ／ｐ１）属性はその値が＋１と−１とで同数でそれぞれφ（ｐ１）／２個である。又、（３）式では１個のｒｈ値に対し、その属性によらず、（ｘ／ｐ２）属性はその値が＋１と−１とで同数でそれぞれφ（ｐ２）／２個である。従って、全体で考えると、ｓｌ値をどのように選んでも（ｘ／ｐ１）属性はその値が＋１と−１とで同数で、それぞれφ（ｐ２）ｘφ（ｐ１）／２個である。（ｘ／ｐ２）属性でも同様で、ｒｈ値をどのように選んでも同数で、全体でφ（ｐ１）ｘφ（ｐ２）／２個である。ここで、（２）式で１個のｓｌ値を選択する際に（ｘ／ｐ２）属性が（ｘ／ｐ２）＝＋１であるものをφ（ｐ１）／２個集めれば、（ｘ／ｐ２）＝＋１で（ｘ／ｐ１）＝±１の同数の組み合わせを得ることができる。従って、それらの属性の組に着目したとき、異なる組の個数はその半分でφ（ｐ１）ｘφ（ｐ２）／４＝φ（ｎ）／４個であり、これは属性の組み合わせ（４通り）に拘わらず同数である。
【０３５７】
［q.e.d］
最もＤ＝τ（ｘ）のように関数になっている場合、関数値の偏りから前記Ｄ値の個数は可能なｘ値に対し、およそｎ／４個にしかならない。又、残念ながらこの方法は未だ完全に確立されていない。しかし、その手掛かりは見つかっているので、以下に開示する。
（３９−１）式、（３９−２）式から、Jacobiの記号では（Ｄ／ｎ）＝＋１となる。他方、正の奇数ｍ及びｎの間で成立する平方剰余の相互法則
【０３５８】
【数６０】
2009223035.tif 000085
【０３５９】
を使うと、正の奇数であるＤ値のＪａｃｏｂｉの記号値（Ｄ／ｎ）を計算で求めることができ、その値が（＋１）である場合には、少なくとも、前記４分割された集合のうちの半分を排除できる。その分（３９−１）式、（３９−２）式を満たすＤ値の可能性が高まったわけである。ここで（３９−１）式、（３９−２）式が成立するときには、Jacobiの記号値が（＋１）でも、
X2=D(mod  n)  ・・・・（３９−４）
を満たす解は存在しない。そこで、理論上は（３９−４）式を満たす前記４分割された集合のうちの半分の残りを排除できることになる。しかし、この式の計算で可能なＸ値を全て代入して計算していたのでは、その計算量が大きく、本末転倒してしまう。（３９−３）式の計算において、ｍ値が合成数の場合には、今度はｍの素因数が知られていなければ（ｎ／ｍ）値の具体的な計算はできない。そこでｍ値として、ｐ１及びｐ２以外の素数若しくは奇数合成数であって、値の小さなものを試すことが考えられる。
【０３６０】
そこで登場するのが、以下に記載する「拡張オイラーの規準」である。オイラーの規準は、（Ｄ，ｐ）＝１である値Ｄにつき、Ｄ（ｐ−１）／２（ｍｏｄ  ｐ）を計算し、そのＤ値が法ｐに対し平方剰余数であるか、平方非剰余数であるかを判定するときに使う。単純な計算でＤ値を判別できるので、優れた方法である。
【０３６１】
ここでは、曲線パラメータ等の決定のために（３９−１）式及び（３９−２）式を満たすＤ値を求める際に、（３９−４）式の直接計算を行わない方法を検討してみる。
Jacobiの記号で（Ｄ／ｎ）＝＋１となるもう１つの場合は、２個の合同式
【０３６２】
【数６１】
2009223035.tif 000086
【０３６３】
が成立する。但し、整数ｈは、因数（ｐ１−１）及び（ｐ２−１）の共通の２のべき乗数値である。値ｎが２の素因数を幾つ持つか数えることは比較的容易である。しかし、ｎ値だけから前記整数ｈを特定することはできない。２の素因数を除外するのは、これにより値ＤのLegendre記号値が強制的に＋１になってしまうからである。２乗すると元の情報の半分が失われてしまうので、失われる前の情報を有する状態で類別を行わなければならない。従って、
【０３６４】
【数６２】
2009223035.tif 000087
【０３６５】
が成立する。この式は、値Ｄのφ（ｎ）／２ｈ＋１乗根では常に値＋１であって、値Ｄのφ（ｎ）／２ｍ乗根（ｍ＞ｈ＋１）では値＋１以外の値（例えば、「１の２ｍ乗根」（ｍｏｄ  ｎ））が出現することを示している。
最も（３９−４）式から、Ｄ値自身が平方数である場合がある。これに対し、（３−１）式及び（３９−２）式を満たすＤ値は、平方数となることはない。従って、（Ｄ，ｐｉ）＝１である値Ｄにつき、
【０３６６】
【数６３】
2009223035.tif 000088
【０３６７】
を満たさねばならず、これらの値は因数（ｐ１−１）及び（ｐ２−１）の値に依存している。
（１）  因数（ｐ１−１）／２ｈ及び（ｐ２−１）／２ｈの何れかに２の素因数が残っている場合
更に（４０−６）式、（４０−７）式を２乗して始めて両辺が一致するので、
【０３６８】
【数６４】
2009223035.tif 000089
【０３６９】
となり、（４０−５）式の場合と区別できる。この式は、値Ｄのφ（ｎ）／２ｈ乗根では常に値＋１であって、値Ｄのφ（ｎ）／２ｍ乗根（ｍ＞ｈ）では値＋１以外の値（例えば、「１の２ｍ乗根」（ｍｏｄ  ｎ））が出現することを示している。
（２）  因数（ｐ１−１）／２ｈ及び（ｐ２−１）／２ｈの何れにも２の素因数が残っていない場合
因数（ｐ１−１）／２ｈ及び（ｐ２−１）／２ｈは何れも奇数なので、
【０３７０】
【数６５】
2009223035.tif 000090
【０３７１】
となり、（３８−５）式の場合と区別できる。この式は、値Ｄのφ（ｎ）／２ｈ＋１乗根では常に値−１であって、値Ｄのφ（ｎ）／２ｍ乗根（ｍ＞ｈ＋１）では値−１以外の値（例えば、「−１の２ｍ乗根」（ｍｏｄ  ｎ））が出現することを示している。即ち、前記４分割された集合のうちの１つで、（３９−１）式、（３９−２）式を満たす集合に属するＤ値を選択できたことになる。そこで、（４０−９）式等の要件を「拡張オイラーの規準」と呼ぶことにする。（４０−９）式でｎ＝ｐ，ｈ＝０のとき、従来のオイラーの規準に一致する。即ち、拡張オイラーの規準は、
【０３７２】
【数６６】
2009223035.tif 000091
【０３７３】
をそれぞれ満たす。
（４０−９）式の計算においてφ（ｎ）の値を事前に知っている場合には、高速指数計算を利用することができる。又、φ（ｎ）値自身の高速計算アルゴリズムが確立されていれば、ｎ値を知って、（３９−１）式、（３９−２）式を満たすＤ値を選択できることになる。しかし、ビット数の大きなｎ値につきφ（ｎ）の値を高速計算できるのであれば、その素因数を求めることは容易で、拡張２次双曲線群ＥＨＣを使う意義はない。即ち、（４０−９）式は、φ（ｎ）の値を事前に知らず、且つ、法ｎの素因数を知らない場合には活用できない。又、ここでは前記４分割された集合のうちの半分の残りを分別するだけなので、（３９−３）式適用の後の使用に意義があるだけである。
【０３７４】
ここで、数値例を掲げる。
経験では、Ｄ値が５０以下の奇素数１４個のうち、少なくとも３個程度（１／４相当）は（３９−１）式、（３９−２）式を満たすＤ値であり、拡張２次双曲線群ＥＨＣの曲線パラメータの指定に利用できることが分かっている。例えば、ｐ１＝１１，ｐ２＝１３，ｎ＝１４３の場合、Ｄ＝３，７，１９，２３，４１の５個で（Ｄ／ｎ）＝＋１であり、この５個の値に対し、（４０−１０）式を適用して、べき乗値の大きい方から順に「１の２ｍ乗根」を求めてみる。
Ｄ（φ／２）＝１，１，１，１，１
Ｄ（φ／４）＝１，１２，１２，１，１２
従って、Ｄ＝７，１９，４１の３個で（３９−１）式、（３９−２）式を満たしていることが分かる。この作業でｈ＝１であることも判明する。なお、（３９−１）式、（３９−２）式を満たす値Ｄが知れても、ベースポイント等を決定するためには法ｎに関する合同式
τ（ｘ）＝ｘ２＋ｃｘ−ａ＝Ｄ（ｍｏｄ  ｎ）  ・・・・（４０−１１）
を解いて、ｘ値を求めなければならない。この作業は相当大変なので、ｘ値を始めに考える方法によって、（４０−１１）式の適用を避けることにする。
【０３７５】
次に、図１１のフローチャートにて示される拡張２次双曲線群等を用いて法ｎ（ｎ＝ｐ１ｐ２）を構成する素因数を求める鍵生成方法について説明する。
【０３７６】
最初に、拡張２次双曲線群ＥＨＣの構成を試してみる。ハードウェア回路を用いた選択・演算処理等により、或いはＣＰＵ等のプロセッサを用いた選択・演算処理等により、以下のステップＳ２１〜Ｓ３１に従い、曲線パラメータが決定される。
【０３７７】
図１１の処理が開始（スタート）すると、ステップＳ２１において、１個の（３９−１）式、（３９−２）式を満たす値Ｄで、できる限り小さな値を有するものが求められる。このとき平方剰余の相互法則の適用ができるように、Ｄ値を（Ｄ／ｎ）＝＋１を満たす奇数値で小さなものに選ぶ。一般的に、
（Ａ）  判別式Ｄの属性で、法ｎの素因数の何れかに係るものが平方剰余である場合は、群演算の途中でゼロ割が発生する。
【０３７８】
ステップＳ２２において、判別式Ｄ／４＝ｃ２＋４ａを定めるパラメータａ，ｃを定める。経験則で、（Ｄ／ｎ）＝＋１を満たす最も小さな奇素数は、（３９−１）式、（３９−２）式を満たすことが多いと分かっている。そこで、数ｎ＝１４６６１１の場合で、Ｄ＝５，７，１３，２９，３１，４１に対し、（τ（ｘ）／ｎ）＝＋１であったことから、判別式Ｄ／４＝ｃ２＋４ａにつきＤ＝５とする。次に、Ｄ／４＝ｃ２＋４ａに従い、これもできる限り小さな値を有するものをａ，ｃに指定する。なお、判別式Ｄ／４と判別式Ｄを同一視することがある。値４が平方数だからである。そこで、曲線パラメータａ，ｃにつき、ｃ＝１，ａ＝１とすることにする。
【０３７９】
ステップＳ２３において、適当なｘ値につきτ（ｘ）を計算する。ｘ＝０から小さい順に値を代入してτ（ｘ）を計算する。
【０３８０】
ステップＳ２４において、τ（ｘ）が奇数であるものの中から、（τ（ｘ）／ｎ）＝＋１を満たすｘ値を集める。即ち、τ（ｘ）が奇数である場合には、（τ（ｘ）／ｎ）の値を平方剰余の相互法則を使って求める。ここでｘ値の指定はベースポイントＰ（ｘ）を指定すること、ｄ値の指定はゼロ元Ｐ（ｄ）を指定することに、それぞれ対応している。計算では、ｘ＝２，５，８，１１，１３に対し、τ（ｘ）＝５，２９，７１，１３１，１８１の値を有し、全て奇数で、且つ、（Ｄ／ｎ）＝＋１である。（τ（ｘ）／ｎ）＝＋１である場合には、そのｘ値をレジスタ等の記憶手段に記録する。
【０３８１】
ステップＳ２５において、記録したｘ値の中から、τ（ｘ）が（３９−１）式、（３９−２）式を満たしていると予想されるものを選択する。一般的に、
（Ｂ）  τ（ｘ）は平方非剰余だがｄ値は平方剰余である場合、即ちゼロ元とベースポイントの間で属性の不一致がある場合も、群演算の途中でゼロ割が発生する。この場合には、巡回群の構造が壊れて擬似ゼロ元等のイメージが出現する。この選択が悪い場合には、中途で計算を打ち切り、他の試数をｘ値又はｄ値として採用する。
【０３８２】
ステップＳ２６，Ｓ２７において、拡張２次双曲線群等の位数計算を行う。（３６−２）式からして、拡張２次双曲線群の最大位数ｋｑはおよそｎ／４の上限値を有しているが、ｍＰ（ｘ）を計算し、ｍＰ＝Ｏとなるｍ値を計算で求めた場合に、一般的にはｍ値は最大位数ｋｑの約数ｋｇになることに注意しなければならない。しかし、一般に最大位数を与える生成群の個数が最も多いので、任意に選択しても最大位数を与えるｘ値を選択する可能性は大きい、といえる。最も正しくパラメータを選択したために最初から最大位数ｋｑを与えるベースポイントを選択していると、ｎ／４回程度の群演算を行わなければゼロ元に至らないので、その演算時間は長大なものになってしまう。なお、群イメージの計算では、逆元計算後回し法を使う。
【０３８３】
ステップＳ２８において、ｍＰ＝Ｏとなるｍ値を計算で求めた場合に、当該ｍ値をレジスタ等の記憶手段に記録しておく。一般的にはｍ値は最大位数ｋｑの約数ｋｇになるので、最大位数ｋｑの主要な因数でない可能性がある。
【０３８４】
ステップＳ２９，Ｓ３０において、群演算の回数が√ｎ回を越えた場合には、最大位数ｋｑを与えるｘ値を選択した可能性が大きいので、試行したｘ値の再選択を行う。再選択するｘ値が尽きた場合には、得られたデータを分析する。
【０３８５】
ステップＳ３１において、得られた位数ｋｇのうち特に最大のものを選択し、若しくは最小公倍数を計算する。これらから、最大位数ｋｑを確定し、（３２−３）式により素因数ｐ１，ｐ２の計算を行う。特別な場合、German素数やSophie-German素数の場合には、この計算は容易であるが、一般の場合には最大公約数なども考慮して決める。
【０３８６】
さて、未知の数ｎ＝１４６６１１が２つの素因数を有しているものとして、実際に値ｎだけからその素因数を求めてみる。
【０３８７】
計算では、ｘ＝２，５，８，１１，１３に対し、τ（ｘ）＝５，２９，７１，１３１，１８１の値を有し、全て奇数で、且つ、（Ｄ／ｎ）＝＋１であったので、（３９−１）式及び（３９−２）式の双方を満たすように拡張２次双曲線群のパラメータをｃ＝５，ａ＝１，ｂ＝１３１，ｄ＝７１；のように設定した。群演算の上限値を１０００回に設定したところ、１３回目の試行（ｘ＝４０）でようやく打ち切りでなく、位数ｋｇ＝５４２を求めることができた。この値は、素因数ｐ１＝２７１の倍数である。拡張２次双曲線群ＥＨＣを正しく構成したが、ｋｇ＞１０００であるベースポイントが連続したために、その法ｎを構成する素因数を確定するのに時間を要した。
【０３８８】
次に、拡張２次双曲線群ＥＨＣの構成が壊れるようなｘ値等の選択を試してみる。
（１）、（２）は同じであるが、（３）に付き、
＜３＞  ｘ＝０から小さい順に値を代入してτ（ｘ）を計算し、その値が奇数である場合には、（τ（ｘ）／ｎ）の値を平方剰余の相互法則を使って求める。計算では、ｘ＝３，４，９，１０，２１に対し、τ（ｘ）＝１１，１９，８９，１０９，４６１の値を有し、全て奇数で、且つ、（Ｄ／ｎ）＝−１である。（τ（ｘ）／ｎ）＝−１である場合には、そのｘ値をレジスタ等の記憶手段に記録する。
【０３８９】
＜４＞  記録したｘ値の中から、τ（ｘ）を選択する。拡張２次双曲線群ＥＨＣの最大位数ｋｑを与えるベースポイントが選択された場合、その演算時間が長大であるので√ｎ回程度の群演算でもゼロ元に至らないときには、中途で計算を打ち切る。逆にいえば、期待する位数ｋｇはｋｇ≦√ｎということになる。それ以外の群イメージで、巡回群の構造が維持されているものを探し出し、その位数ｋｇを求める。
【０３９０】
前記曲線パラメータの決定方法＜３＞及び＜４＞により、曲線パラメータをａ＝１，ｃ＝１，ｄ＝１１，ｘ＝８として決定し、拡張２次双曲線群ＥＨＣを決定できたので、これに基づき位数ｋを計算する。√ｎ≒３８３であるので、この回数を上回ってもゼロ元に至らないときは、その計算を打ち切って、次のｘ値を試す。その計算の結果、（τ（ｘ）／ｎ）＝−１であるようなｘ値に対し、
ｘ１＝５（ｘ１＊（ｘ１＋ｃ）−ａ）＝２９：  位数  ｋ＝２７０
ｘ１＝８（ｘ１＊（ｘ１＋ｃ）−ａ）＝７１：  位数  ｋ＝２７０
ｘ１＝１１（ｘ１＊（ｘ１＋ｃ）−ａ）＝１３１：  位数  ｋ＝１
ｘ１＝１３（ｘ１＊（ｘ１＋ｃ）−ａ）＝１８１：  位数  ｋ＝２７０
ｘ１＝１４（ｘ１＊（ｘ１＋ｃ）−ａ）＝２０９：  位数  ｋ＝１３５
を得ることができた。求めた位数はｋｇ＝２７０である。従って、求めた位数をｐ１＝２ｋｇ＋１に代入してｐ１＝５４１を得ることができる。法ｎ＝１４６６１１であったから、もう１個の素因数ｐ２は、ｐ２＝２７１と計算することができる。
【０３９１】
前記例題では、法ｎの素因数が互いにＧｅｒｍａｎｎ素数の関係にある、特別な場合であった。今度は、１桁増やし未知の数ｎ＝１４７４２８９が２つの素因数を有しているものとして、実際に値ｎだけからその素因数を求めてみることにする。
（１）  平方剰余の相互法則を用いた計算では、Ｄ＝５，９，１１，１７，２３に対し、全て奇数で、且つ、（Ｄ／ｎ）＝＋１であったので、最小奇素数Ｄ＝５に指定し、パラメータをａ＝１，ｃ＝１に選択した。
（２）  前記パラメータのもとでτ（ｘ）を幾つか計算し、奇数であるものを選択する。その中から（τ（ｘ）／ｎ）＝＋１であるようなｘ値を集める。平方剰余の相互法則を用いた計算では、ｘ＝２，３，５，８，９に対し、τ（ｘ）＝５，１１，２９，７１，８９で、全て奇数で、且つ、（Ｄ／ｎ）＝＋１であった。
（３）  収集したｘ値から、適当にベースポイントＰ（ｘ）及びゼロ元Ｏ＝Ｐ（ｄ）に割り当てて、位数計算を行う。
（４）  ｍＰ＝Ｏとなるｍ値を求め、√ｎ≒１２１４回の群演算でもゼロ元Ｏに当たらない場合には、その位数計算を打ち切る。
（５）  前記ｘ値を試行値とし、ｄ値としてｄ＝３とした場合、以下の結果を得ることができた。
ｎ＝１４７４２８９，ｃ＝１，ａ＝１，ｄ＝３；
ｘ＝２  打ち切り
ｘ＝３  完了：位数  ｋｇ＝１
ｘ＝５  打ち切り
ｘ＝８  打ち切り
ｘ＝９  打ち切り
この結果は、最大位数ｋｑを与えるベースポイントが連続したために、目的とした位数ｋｇ≦√ｎを得ることができなかったことを示している。
（６）  今度は判別式Ｄの属性を変更する。平方剰余の相互法則を用いた計算では、Ｄ＝３，７，１３，１５，１９に対し、全て奇数で、且つ、（Ｄ／ｎ）＝−１であったので、Ｄ＝１３に指定し、パラメータをａ＝３，ｃ＝１に選択した。
（７）  前記パラメータのもとでτ（ｘ）を幾つか計算し、奇数であるものを選択する。その中から（τ（ｘ）／ｎ）＝＋１であるようなｘ値を集める。平方剰余の相互法則を用いた計算では、ｘ＝３，４，１３，１６に対し、τ（ｘ）＝９，１７，１７９，２６９で、全て奇数で、且つ、（Ｄ／ｎ）＝＋１であった。
（８）  前記ｘ値を試行値とし、ｄ値としてｄ＝３とした場合、以下の結果を得ることができた。
ｎ＝１４７４２８９，ｃ＝１，ａ＝３，ｄ＝３；
ｘ＝３  完了：位数  ｋｇ＝１
ｘ＝４  完了：位数  ｋｇ＝５８５
ｘ＝１３  打ち切り
ｘ＝１６  打ち切り
この結果、目的とした位数ｋｇ≦√ｎを１個得ることができ、それがｋｇ＝５８５であったことを示している。
（９）  判別式Ｄ値の属性が（Ｄ／ｎ）＝−１であったので、その最大位数ｋｑは（３６−８）式で与えられる。法ｎに係る仮の素因数をｑとした場合、ｑ＝２ｋｇ±１＝１１７０±１である。そこで実際に法ｎをこのｑ値で割ってみると、ｑ＝１１７１で割り切れて、ｐ１＝１１７１，ｐ２＝１２５９と決定することができた。
【０３９２】
以上の結果を総括する。
拡張２次双曲線群ＥＨＣで適当にパラメータを定めてプロセッサで位数計算を行った結果、最大位数ｋｑを与えるベースポイントが連続したために打ち切りが続き、求める位数を有する生成群を発見できなかった。そこで、判別式Ｄ値の属性変更を行い、今度は拡張２次双曲線半群で適当にパラメータを定めて位数計算を行った結果、求める位数を有する生成群を発見でき、無事（３６−８）式により、法ｎの正しい素因数を定めることができたわけである。改めて、拡張２次双曲線半群の有効性を確認できた。
【０３９３】
ＲＳＡ暗号は、２個の素数ｐ，ｑが不明で、その積ｎ＝ｐｑのみが知られている場合に、ｎ値を知ってもその素因数であるｐ，ｑを知ることが難しいという、所謂素因数分解の数学的困難性に基礎を置いている、といわれている。φ（ｎ）よりも小さい自然数ｅで、φ（ｎ）と互いに素であるようなものを選択し、更にｄｅ＝１（ｍｏｄφ（ｎ））であるような自然数ｄを選択する。このとき、公開鍵を（ｎ，ｅ）の組、秘密鍵をｄとする公開鍵暗号化方式を構成できる。平文ｍにつき、公開鍵を使って暗号文ｃ＝ｍｅ（ｍｏｄ  ｎ）を計算し相手方に送付する。その相手方は、秘密鍵を使って前記平文をｍ＝ｃｄ（ｍｏｄ  ｎ）により復号できる。
【０３９４】
ＲＳＡ暗号は、２個の素数の積ｎ＝ｐｑを使うので、本実施例に係る拡張２次双曲線群ＥＨＣを使用する方法で、その素因数を求めることができる。素因数ｐ，ｑを知れば、φ（ｎ）＝（ｐ−１）（ｑ−１）を計算できるので、逆元計算によって公開鍵ｅから秘密鍵ｄを求めることができ、その解読も容易である。しかし、本実施例に係る方法の計算量は√ｎ回程度の群演算を必要とするので、必ずしも高速に求めることはできない。実用上は、ｌｏｇ  ｎに比例する計算量でなければならないであろう。２次双曲線群の研究は未だ始まったばかりであり、計算量を削減する余地は十分にあると考えられる。
【０３９５】
法ｎが３個以上の素因数で構成される場合は、数学理論上の興味は残っていても、暗号理論上はあまり価値のないものになると考えられる。そこで、ここでは簡単に触れておくだけにする。但し、当該複数の素因数は互いに異なるものと仮定している。
【０３９６】
法ｎが３個以上の素因数で構成される場合に、拡張２次双曲線群ＥＨＣがどのような構成になるのかある程度予想がつくが、試行数値計算で確認しながら推定するのが最善の方法と考える。（３２−３）式からして、一般の場合には生成群Ｑ（ｘ）の最大位数は、
【０３９７】
【数６７】
2009223035.tif 000092
【０３９８】
と予想される。証明はない。
ここで、試行数値計算を法ｎが３個の素因数で構成される場合を例示する。
ｒ＝７，ｓ＝１１，ｔ＝１３，ｎ＝１００１の場合で、（ｘ／ｒ）＝−１，（ｘ／ｓ）＝−１，（ｘ／ｔ）＝−１であるようなｘ値はｘ＝６，１９，２４であったので、Ｄ＝２４とするものとし、パラメータをｃ＝２，ａ＝５と選択することにする。このパラメータのもとで（τ（ｘ）／ｒ）＝−１，（τ（ｘ）／ｓ）＝−１，（τ（ｘ）／ｔ）＝−１であるようなｘ値を有する元Ｐ（ｘ）をベースポイントとしてｍＰ＝Ｏとなるようなｍ値を求める。このｍ値は生成群Ｑ（ｘ）の位数ｋｇを与えることになる。この試行計算では、ｋｇの最大値ｋｑはｋｑ＝８４であった。これは（４５−１）式で、ｎ＝３とした場合に一致する。即ち、予想値は
ｋｑ＝ＬＣＭ（ｋ１，ｋ２，ｋ３）
＝ＬＣＭ（（ｒ＋１）／２，（ｓ＋１）／２，（ｔ＋１）／２）＝ＬＣＭ（（７＋１）／２，（１１＋１）／２，（１３＋１）／２）＝ＬＣＭ（４，６，７）＝８４
であり、試行計算値と一致する。
【０３９９】
又、生成群Ｑ（ｘ）の個数はｋｇ＝８４，４２，２８，２１，１４，１２，７，６，４，３，２，１に対し、それぞれψ（ｋｇ）＝４８，３６，２４，１２，１８，８，６，６，４，２，３，１であった。
【０４００】
次に、約数ｄ｜ｋｇについての
和Σｄ｜ｋｇψ（ｄ）＝１６８，８４，５６，２１，２８，２４，７，１２，８，３，４，１
であり、これは
和Σｄ｜ｋｇψ（ｄ）＝２＊８４，２＊４２，２＊２８，１＊２１，２＊１４，２＊１２，１＊７，２＊１２，２＊４，１＊３，１＊１
と表せる。従って、
和Σｄ｜ｋｇψ（ｄ）＝ｈｋｇ（ｈ＝１  ｏｒ  ２）
が成立している。但し、ｈ＝１の場合はその位数ｋｇは共通の因数を含んでいない。ｈ＝２の場合はその位数ｋｇは共通の因数ｈ＝２を含んでいる。ここでいう共通の因数ｈとは、ｈ＝（ｋｇ，ｋ１，ｋ２）であり、位数ｋ３は関与していない。部分的な共通の因数である。複数の位数に跨る共通の因数が在る場合にどのような選択がなされているのかは、未だ知られていない。しかし、個別位数同士の対称性から
和Σｄ｜ｋｇψ（ｄ）＝ｈ１ｈ２ｈ３ｋｇ・・・・（４５−２）
ｈ１＝（ｋｇ，ｋ１，ｋ２），  ｈ２＝（ｋｇ，ｋ２，ｋ３），  ｈ３＝（ｋｇ，ｋ３，ｋ１）
が成立すると予想される。前記の例では、ｈ１＝ｈ，ｈ２＝１，ｈ３＝１である。
【０４０１】
この予想を確認するために、ｒ＝７，ｓ＝１１，ｔ＝１７，ｎ＝１３０９の場合の試行計算を検討してみる。
属性が（ｘ／ｒ）＝−１，（ｘ／ｓ）＝−１，（ｘ／ｔ）＝−１であるようなｘ値はｘ＝６，１０，２４であったので、Ｄ＝２４とするものとし、パラメータをｃ＝２，ａ＝５と選択することにする。このパラメータのもとで
（τ（ｘ）／ｒ）＝−１，（τ（ｘ）／ｓ）＝−１，（τ（ｘ）／ｔ）＝−１
であるようなｘ値を有する元Ｐ（ｘ）をベースポイントとしてｍＰ＝Ｏとなるようなｍ値を求める。このｍ値は生成群Ｑ（ｘ）の位数ｋｇを与えることになる。この試行計算ではｋｇの最大値ｋｑはｋｑ＝３６であった。予想値は
ｋｑ＝ＬＣＭ（（ｒ＋１）／２，（ｓ＋１）／２，（ｔ＋１）／２）＝ＬＣＭ（（７＋１）／２，（１１＋１）／２，（１７＋１）／２）＝ＬＣＭ（４，６，９）＝３６
で、前記試行計算値と一致した。
【０４０２】
又、生成群Ｑ（ｘ）の個数は、その試行計算ではｋｇ＝３６，１８，１２，９，６，４，３，２，１に対し、それぞれψ（ｋｇ）＝７２，５４，３２，１８，２４，４，８，３，１であった。次に、約数ｄ｜ｋｇについての和は
和Σｄ｜ｋｇψ（ｄ）＝２１６，１０８，７２，２７，３６，８，９，４，１
であり、これは
和Σｄ｜ｋｇψ（ｄ）＝６＊３６，６＊１８，６＊１２，３＊９，６＊６，２＊４，３＊３，２＊２，１＊１
である。従って、
和Σｄ｜ｋｇψ（ｄ）＝ｈｋｇ
が成立していて、ｈ＝６，６，６，３，６，２，３，２，１である。
【０４０３】
ここで、ｈ＝ｈ１ｈ２ｈ３として、ｋｇ＝３６，１８，１２，９，６，４，３，２，１に対し、ｈ値を予想値計算してみると、ｈ＝（ｋｇ，ｋ１，ｋ２）（ｋｇ，ｋ２，ｋ３）（ｋｇ，ｋ３，ｋ１）から
ｆｏｒ  ｋｇ＝３６  ｈ＝（３６，４，６）（３６，６，９）（３６，９，４）＝２＊３＊１＝６
ｆｏｒ  ｋｇ＝１８  ｈ＝（１８，４，６）（１８，６，９）（１８，９，４）＝２＊３＊１＝６
ｆｏｒ  ｋｇ＝１２  ｈ＝（１２，４，６）（１２，６，９）（１２，９，４）＝２＊３＊１＝６
ｆｏｒ  ｋｇ＝９  ｈ＝（９，４，６）（９，６，９）（９，９，４）＝１＊３＊１＝３
ｆｏｒ  ｋｇ＝６  ｈ＝（６，４，６）（６，６，９）（６，９，４）＝２＊３＊１＝６
ｆｏｒ  ｋｇ＝４  ｈ＝（４，４，６）（４，６，９）（４，９，４）＝２＊１＊１＝２
ｆｏｒ  ｋｇ＝３  ｈ＝（３，４，６）（３，６，９）（３，９，４）＝１＊３＊１＝３
ｆｏｒ  ｋｇ＝２  ｈ＝（２，４，６）（２，６，９）（２，９，４）＝２＊１＊１＝２
ｆｏｒ  ｋｇ＝１  ｈ＝（１，４，６）（１，６，９）（１，９，４）＝１＊１＊１＝１
で、やはり前記試行計算値と一致した。
【０４０４】
そこで（４５−２）式にメービウスの反転公式を適用すれば、法ｎが素因数３個を有する場合に位数ｋｇを有する生成群の個数について
【０４０５】
【数６８】
2009223035.tif 000093
【０４０６】
であり、ψ（３６）＝７２となって、試行計算で実際に数えた値に一致した。
今度は、共通の因数ｈｃ＝（ｋ１，ｋ２，ｋ３）≠１である場合にはどのように取り扱うべきか考えてみる。
【０４０７】
（４５−３）式では、ｈ＝ｈ１ｈ２ｈ３からして、ｈｃ３の形で出現することになるが、位数ｋｇは本来ｋｑ＝ＬＣＭ（ｋ１，ｋ２，ｋ３）及びその約数についてのみ和を取るので、位数ｋｇ以下の生成群Ｑ（ｘ）の個数の総和への寄与としては過重になっていると考えられる。
【０４０８】
そこで再び試行数値計算により正しい理論式を推定することにしてみる。
ｐ１＝１１，ｐ２＝１７，ｐ３＝２３の素因数を有する法ｎ＝ｐ１ｐ２ｐ３である拡張２次双曲線群で、（Ｄ／ｐｉ）＝−１であるようにパラメータ等（ａ＝１４，ｃ＝１，ｄ＝６，ｂ＝１５）を設定し、（ｘ／ｐｉ）＝−１であるようなｘ値につき生成群Ｑ（ｘ）の位数ｋｇを求める試行数値計算の結果、以下の結果を得た。
【０４０９】
即ち、生成群Ｑ（ｘ）の最大位数ｋｑについては、従来と同様に
ｋｑ＝ＬＣＭ（ｋ１，ｋ２，ｋ３）
＝ＬＣＭ（（ｐ１＋１）／２，（ｐ２＋１）／２，（ｐ３＋１）／２）＝ＬＣＭ（（１１＋１）／２，（１７＋１）／２，（２３＋１）／２）＝ＬＣＭ（６，９，１２）＝３６
であり、試行計算値と一致する。又、ｋｇ＝３６，１８，１２，９，６，４，３，２，１に対し、それぞれψ（ｋｇ）＝２１６，１６２，１０４，５４，７８，４，２６，３，１であった。次に、約数ｄ｜ｋｇについての和は
和Σｄ｜ｋｇψ（ｄ）＝６４８，３２４，２１６，８１，１０８，８，２７，４，１
であり、これは
和Σｄ｜ｋｇψ（ｄ）＝１８＊３６，１８＊１８，１８＊１２，９＊９，１８＊６，２＊４，９＊３，２＊２，１＊１
である。従って、和Σｄ｜ｋｇψ（ｄ）＝ｈｋｇが成立していて、ｈ＝１８，１８，１８，９，１８，２，９，２，１である。この結果を従来の推定理論式ｈ＝ｈ１ｈ２ｈ３と比べてみると、丁度、共通の因数ｈｃ＝（ｋｇ，ｋ１，ｋ２，ｋ３）の分だけ過重であることが分かる。従って、
ｈ＝（ｋｇ，ｋ１，ｋ２）（ｋｇ，ｋ２，ｋ３）（ｋｇ，ｋ３，ｋ１）／（ｋｇ，ｋ１，ｋ２，ｋ３）  ・・・・（４５―４）
が本来の姿（理論式）であると推定される。これによれば、（４５―３）式は本来、
【０４１０】
【数６９】
2009223035.tif 000094
【０４１１】
の一部であると考えられ、ｋ３＝１と置くと（３５−６）式へ帰着する。（４５−５）式についての直接の証明はないが、一応次のように解釈される。まず、その共通因数は常に構成素因数の２乗以上の形で現れるので、メービィウス関数の性質から前記基本周期に影響を与えない。従って、（４５−５）式の項数が実質的に増えることはなく、当該基本周期を有する巡回群の個数ｋｇ／ｄに影響するだけである。次に位数ｋ＝ｋ１ｋ２ｋ３のとき、素因数の集合を考え、ｋ１、ｋ２及びｋ３の３つの集合の重ね合わせを考える。集合ｋ１は、自らの固有部分ｋ１０と前記３つの集合の共通部分ｈ４と集合ｋ２のみとの共通部分ｈ１２と集合ｋ３のみとの共通部分ｈ３１とから構成される。集合ｋ２は、自らの固有部分ｋ２０と前記３つの集合の共通部分ｈ４と集合ｋ１のみとの共通部分ｈ１２と集合ｋ３のみとの共通部分ｈ２３とから構成される。集合ｋ３は、自らの固有部分ｋ３０と前記３つの集合の共通部分ｈ４と集合ｋ１のみとの共通部分ｈ３１と集合ｋ２のみとの共通部分ｈ２３とから構成される。このとき、
【０４１２】
2009223035.tif 000095
【０４１３】
回繰り返される構造が存在する。ここで前記巡回群の個数ｋｇ／ｄを考えれば、その共通部分につき
【０４１４】
2009223035.tif 000096
【０４１５】
と、対応付けることができる。上記議論により当該基本周期を有する巡回群の個数は、ｋｇ／ｄから（ｋｇ／ｄ）（ｋｇ／ｄ，ｋ１，ｋ２）（ｋｇ／ｄ，ｋ２，ｋ３）（ｋｇ／ｄ，ｋ３，ｋ１）／（ｋｇ／ｄ，ｋ１，ｋ２，ｋ３）に増加する。
【０４１６】
この（４５−５）式につき、別の試行計算例を掲げる。
ｐ１＝１７，ｐ２＝２３，ｐ３＝２９の素因数を有する法ｎ＝ｐ１ｐ２ｐ３である拡張２次双曲線群ＥＨＣで、（Ｄ／ｐｉ）＝−１であるようにパラメータ等（ａ＝９，ｃ＝１，ｄ＝４，ｂ＝１４）を設定し、（ｘ／ｐｉ）＝−１であるようなｘ値につき生成群Ｑ（ｘ）の位数ｋｇを求める試行数値計算の結果、以下の結果を得た。
【０４１７】
即ち、生成群Ｑ（ｘ）の最大位数ｋｑについては、従来と同様に
ｋｑ＝ＬＣＭ（ｋ１，ｋ２，ｋ３）＝ＬＣＭ（（ｐ１＋１）／２，（ｐ２＋１）／２，（ｐ３＋１）／２）
＝ＬＣＭ（（１７＋１）／２，（２３＋１）／２，（２９＋１）／２）＝ＬＣＭ（９，１２，１５）＝１８０
であり、試行計算値と一致する。又、
ｋｇ＝１８０，９０，６０，４５，３６，３０，２０，１８，１５，１２，１０，９，６，５，４，３，２，１
に対し、それぞれ
ψ（ｋｇ）＝４３２，２１６，２０８，２１６，１０８，１０４，８，５４，１０４，５２，４，５４，２６，４，２，２６，１，１
であった。次に、約数ｄ｜ｋｇについての和は、
和Σｄ｜ｋｇψ（ｄ）＝１６２０，８１０，５４０，４０５，３２４，２７０，２０，１６２，１３５，１０８，１０，８１，５４，５，４，２７，２，１
であり、これは
和Σｄ｜ｋｇψ（ｄ）＝９＊１８０，９＊９０，９＊６０，９＊４５，９＊３６，９＊３０，１＊２０，９＊１８，９＊１５，９＊１２，１＊１０，９＊９，
９＊６，１＊５，１＊４，９＊３，１＊２，１＊１
である。従って、
和Σｄ｜ｋｇψ（ｄ）＝ｈｋｇ
が成立していて、
ｈ＝９，９，９，９，９，９，１，９，９，９，１，９，９，１，１，９，１，１
である。この結果を推定理論値ｈ＝ｈ１ｈ２ｈ３と比べてみると、やはり共通の因数ｈｃ＝（ｋｇ，ｋ１，ｋ２，ｋ３）の分だけ過重で、（４５−４）式及び（４５−５）式が成立していた。そこで、一般的にも（４５−４）式及び（４５−５）式が成立していると考えられる。しかし、あくまで推定であってその証明はない。
【０４１８】
前記までは法ｎが合成数でｎ＝ｐ１ｐ２の（ｐ１≠ｐ２）ときの拡張２次双曲線群ＥＨＣを取り扱っていたが、ここでは法ｎが合成数でｎ＝ｐｈ（ｐ≠２）の場合を若干説明しておく。
【０４１９】
法ｎがｎ＝ｐｈ（ｐ≠２）の場合には、非特許文献（高木貞治「初等整数論講義」第２版、共立出版（ISBN:4-320-01001-9）Ｐ．１１２）で示される下記定理が存在する。
【０４２０】
［定理４６―１］
素数ベキ＝ｐｈ（ｐ≠２）を法とするとき、原始根ｒが存在する。即ち、ｒはそのφ（ｐｈ）乗が初めてｐｈを法として１と合同になる数で、従って
１，ｒ，ｒ２，，，ｒφ−１    ；  φ（ｐｈ）＝ｐｈ−１（ｐ−１）
が法ｐｈの既約類を代表する。
【０４２１】
［証明省略］
そこで、この原始根を利用して前記配偶の個数を議論することが考えられる。しかし、配偶という概念は法がｐのような素数のときにのみ成立する概念で、法が合成数ｎである場合には同様の議論により直接拡張することはできない。法が合成数ｎである場合には、法が素数ｐである場合を基礎にしてその拡張を図る。実際、定理３９−１では素因数ｐ１若しくはｐ２の構造が法ｎの下でも生き残っていた。なお、原始根とは法ｎの乗法群で、その位数がφ（ｎ）であるような元をいう。従って、ｎ−φ（ｎ）個の値ｎと素でない元は除外されており、これらは原始根の乗積によっては出現しない。
【０４２２】
法ｎの下での構造を理解するヒントは、オイラーの関数にある。ｎ＝ｐｈの場合に
φ（ｐｈ）＝ｐｈ−１（ｐ−１）
が成立するが、これは
φ（ｐｈ）＝ｐｈ−１φ（ｐ）
と書き直すことができる。これが意味するところは、「素因数ｐの構造がｐｈ−１回繰り返される構造が存在する」、ということである。
【０４２３】
ここで数値例を掲げる。
ｈ＝２，ｐ＝３，ｎ＝９の場合、（Ｄ／ｐ）＝＋１、例えば、ａ＝１，ｒｓ＝ａである場合には、ｎ＝９，φ（ｎ）＝６であるので、（ｒ，ｎ）≠１でない数値はｎ−φ（ｎ）＝３個で、それぞれｒ＝０，３，６である。又、従来の議論により法ｎの下での配偶を数えると４個で、具体的には（ｒ，ｓ）＝（１，１）；（８，８）；（２，５）；（４，７）である。しかし、法をｎではなくて、法ｐで考え、且つ、φ（ｎ）／φ（ｐ）回の繰り返しで構成されていると考えれば、配偶の構成も異なったものとなる。このとき配偶は（ｒ，ｓ）＝（１，１）；（２，２）の２個しかない。そして、φ（ｎ）／φ（ｐ）＝６／２＝３回繰り返される。即ち、（Ｄ／ｐ）＝＋１である場合には２個の配偶が３回繰り返す構造を有し、合計６個の配偶が出現する。
【０４２４】
（Ｄ／ｐ）＝−１、例えば、ａ＝２，ｒｓ＝ａである場合には、Ｎ＝φ（ｎ）／２＝３個で、具体的には（ｒ，ｓ）＝（１，２）；（４，５）；（７，８）である。しかし、法をｎではなくて、法ｐで考え、且つ、φ（ｎ）／φ（ｐ）回の繰り返しで構成されていると考えれば、配偶の構成も異なったものとなる。このとき配偶は（ｒ，ｓ）＝（１，２）の１個しかない。そして、φ（ｎ）／φ（ｐ）＝６／２＝３回繰り返す構造を有している。即ち、（Ｄ／ｐ）＝−１である場合には１個の配偶が３回繰り返し出現し、合計３個の配偶が出現する。
【０４２５】
次に、法ｎ＝ｐｈの下で「τ(x)=x2＋cx−aが平方剰余」という条件を満たすｘの個数Ｎを数えることにする。
【０４２６】
このとき従来の議論と同様に、判別式Ｄが法ｐの下で平方非剰余か平方剰余（Ｄ≠０）かに依存して配偶の個数が変わり、当該配偶の個数の制限を受けて「τ（ｘ）が平方剰余」という条件を満たすｘの個数Ｎが決まる。但し、当該配偶についての議論は素因数ｐを法とする場合に限り成立し、「素因数ｐの構造がｐｈ−１回繰り返される」構造を前提に計算される。即ち、「τ（ｘ）が平方剰余」という条件を満たすｘの個数Ｎは、判別式Ｄが法ｐの下で平方非剰余であれば、
Ｎ＝ｐｈ−１（（ｐ−１）／２）  ・・・・（４６−１）
に、判別式Ｄが法ｐの下で平方剰余（Ｄ≠０）であれば、
Ｎ＝ｐｈ−１（（ｐ＋１）／２）  ・・・・（４６−２）
に、それぞれなる。
【０４２７】
ここで、（ｒ，ｎ）≠１である数値ｒ（配偶の片方）をどのように取り扱うべきか説明する。
【０４２８】
（ｒ，ｎ）≠１である数値は、全て法ｐの倍数である。従って、逆元（Ｚ／ｎＺ）を有していない。逆元が存在しないのでＤ≠０の場合には、ｒｓ＝Ｄとなるような配偶を構成できない。従って、配偶ｒに係るｘ値についてτ（ｘ）は平方剰余数にならない。即ち、τ（ｘ）は平方非剰余数で、「τ（ｘ）が平方非剰余」という条件を満たすｘの個数Ｎ＿にカウントされる。これは、平方非剰余数の個数Ｎ＿が、Ｎ＿＝ｎ−Ｎであることを意味する。なお、Ｄ＝０の場合は、全て平方剰余数である。
【０４２９】
従って、法ｎがｎ＝ｐｈの場合の拡張２次双曲線群の位数ｋは、判別式Ｄが法ｐの下で平方非剰余であれば、
ｋ＝ｎ−ｐｈ−１（（ｐ−１）／２）＝ｐｈ−１（ｐ＋１）／２  ・・・・（４６−３）
に、判別式Ｄが法ｐの下で平方剰余（Ｄ≠０）であれば、拡張２次双曲線半群となって、その位数ｋは
ｋ＝ｎ−ｐｈ−１（（ｐ＋１）／２）＝ｐｈ−１（ｐ−１）／２  ・・・・（４６−４）
に、それぞれなる。又、素因数ｐ以外の構造が存在しないことから、（３２−３）式で与えられた最小公倍数の巡回周期という概念は成立せず、生成群Ｑ（ｘ）の最大位数ｋｑは拡張２次双曲線群の位数ｋと一致し、ｋｑ＝ｋになる。
【０４３０】
ここで、再び数値例を掲げる。
ｈ＝３，ｐ＝７，ｎ＝３４３の拡張２次双曲線群で（Ｄ／ｐ）＝−１の場合、Ｄ＝５，ａ＝１，ｃ＝１において生成群Ｑ（ｘ）の最大位数ｋｑは、ｋｑ＝１９６であった。前記議論によれば、τ（ｘ）が平方非剰余であるｘ値の個数
Ｎ＿＝ｎ−ｐｈ−１（（ｐ−１）／２）＝３４３−４９ｘ３＝１９６
なので、τ（ｘ）が平方非剰余であるｘ値の個数Ｎ＿は生成群Ｑ（ｘ）の最大位数ｋｑと一致した。
【０４３１】
他方、Ｄ＝９，ａ＝２，ｃ＝１において（Ｄ／ｐ）＝＋１の場合には拡張２次双曲線半群となり、生成群Ｑ（ｘ）の最大位数ｋｑはｋｑ＝１４７であった。前記議論によれば、τ（ｘ）が平方非剰余であるｘ値の個数Ｎ＿は
Ｎ＿＝ｎ−ｐｈ−１（（ｐ＋１）／２）＝３４３−４９ｘ４＝１４７
なので、τ（ｘ）が平方非剰余であるｘ値の個数Ｎ＿は生成群Ｑ（ｘ）の最大位数ｋｑと一致した。
【産業上の利用可能性】
【０４３２】
本発明の実施例１では具体的な暗号化方法としてHC-Elgamal暗号を開示し、又、具体的なデジタル署名方法として、HC-Elgamal署名を開示した。しかし、本発明の２次双曲線群等の利用はこれらに留まるものではなく、２次双曲線群等の離散対数を利用する総ての応用に拡張可能である。その場合、楕円曲線暗号等に比べて簡易な構成により２次双曲線群ＥＨＣを利用した暗号を構成でき、特に位数関係が簡明なことから、整数論の初等的知識を有する者に対して離散対数に係る暗号の利用が普及すると期待される。暗号や数学の専門家に対しては、従来の暗号理論や数学理論の進歩に寄与する「道具」として利用することができる。
【０４３３】
図１２は、楕円曲線暗号と双曲線暗号の特徴を比較した図である。
既に開示したように、双曲線暗号の数学的な根拠は離散対数を求める困難さにその根拠を置いており、これは楕円曲線暗号と同様である。しかし、楕円曲線暗号では素数位数とするために曲線パラメータを替えて素数位数判定を繰り返す作業を必要としていた。この点、当初から素数位数を指定できる双曲線暗号のほうがが有利である。又、曲線パラメータの指定も所定の関係式を満たすだけで容易に設計者の任意で選択できる。素数位数のために曲線パラメータを拘束されている楕円曲線暗号のほうが不利、といえる。
【０４３４】
公開鍵暗号やデジタル署名を同様に実現できる点で双方に差異はない。しかし、双曲線暗号では位数が一定であるので、秘密鍵変動や演算変動型暗号を構成することができる。これはストリーム暗号や１回限りの使い捨ての暗号を必要とする量子暗号通信等への利用の可能性を示唆している。最も計算の負荷を考えれば、逆元計算後回し法を使用した場合でも、暗号に係る秘密鍵等のビット数を多くすることはできない、と考えられる。
【図面の簡単な説明】
【０４３５】
【図１（Ａ）】本発明の実施例１に係る２次双曲線群の鍵生成装置の概略構成を示す機能ブロック図である。
【図１（Ｂ）】本発明の実施例１に係る２次双曲線群の鍵生成方法を示すフローチャートである。
【図２】群演算に関する２次双曲線群の構成を示す概念図である。
【図３】２次双曲線群の具体的構成例で、ｐ＝２３，ｄ＝６，ａ＝４，ｃ＝１，ｂ＝７である２次双曲線群ＨＣ（ｄ≠ｂ）の生成群Ｑ（ｘ）の構造を示す図である。
【図４】本発明の実施例２に係る秘密鍵変動型ストリーム暗号生成装置を示す概略の構成図である。
【図５（Ａ）】図４の秘密鍵変動型ストリーム暗号生成装置の計算例（ｍ＝２）を示す図である。
【図５（Ｂ）】図４の秘密鍵変動型ストリーム暗号生成装置のストリーム出力例を示す図である。
【図６】図４の秘密鍵変動型ストリーム暗号生成装置による暗号化及び復号化を行ってデータの送受信を行う通信システムの構成図である。
【図７】本発明の実施例３に係る拡張２次双曲線群の鍵生成方法（ｎ＝ｐ１ｐ２の場合）を示すフローチャートである。
【図８】本発明の実施例３に係る法ｎ＝９１、位数ｋ＝２８の拡張２次双曲線群（生成群Ｑ（ｘ））の構造を示す図である。
【図９】本発明の実施例３に係る法ｎ＝３９１、位数ｋ＝３６の拡張２次双曲線群（生成群Ｑ（ｘ））の構造を示す図である。
【図１０（Ａ）】法ｎ＝２２１，ｒ＝１３，ｓ＝１７である拡張２次双曲線半群の具体例であって、位数Ｋｇを与える生成群の個数（τ（ｄ））とτ（ｘ）の属性一致）を示す図である。
【図１０（Ｂ）】法ｎ＝２２１，ｒ＝１３，ｓ＝１７である拡張２次双曲線半群の具体例であって、位数Ｋｇを与える生成群の個数（τ（ｄ））とτ（ｘ）の属性不一致）を示す図である。
【図１０（Ｃ）】法ｎ＝２２１，ｒ＝１３，ｓ＝１７である拡張２次双曲線半群の具体例であって、判別式Ｄとτ（ｘ）の属性不一致、及びτ（ｄ）とτ（ｘ）の属性一致を示す図である。
【図１１】本発明の実施例４に係る拡張２次双曲線群等を用いて法ｎ（ｎ＝ｐ１ｐ２）の素因数を求める鍵生成方法を示すフローチャートである。
【図１２】楕円曲線暗号と双曲線暗号の特徴を比較した図である。
【符号の説明】
【０４３６】
１０      鍵生成装置
１１      鍵設定部
１２      曲線パラメータ設定部
１３      鍵生成部
２０，２０−１，２０−２      ストリーム暗号生成装置
２１−０〜２１−ｍ      セル演算器
【図１（Ａ）】
2009223035.tif 000101
【図１（Ｂ）】
2009223035.tif 000102
【図２】
2009223035.tif 000103
【図３】
2009223035.tif 000104
【図４】
2009223035.tif 000105
【図５（Ａ）】
2009223035.tif 000106
【図５（Ｂ）】
2009223035.tif 000107
【図６】
2009223035.tif 000108
【図７】
2009223035.tif 000109
【図８】
2009223035.tif 000110
【図９】
2009223035.tif 000111
【図１０（Ａ）】
2009223035.tif 000112
【図１０（Ｂ）】
2009223035.tif 000113
【図１０（Ｃ）】
2009223035.tif 000114
【図１１】
2009223035.tif 000115
【図１２】
2009223035.tif 000116