(57)【特許請求の範囲】
【請求項１】
非対称ないくつかの暗号鍵を生成するためのシステムであって、該いくつかの暗号鍵は、ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmとｍ個の公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）とを含んでおり、
プロセッサと、
前記プロセッサに接続されたメモリユニットとを備え、
前記プロセッサは、
１より大きい整数である機密保護パラメータｋを選択して前記メモリユニットに格納し、
１より大きい整数であるｍ個の基数ｇ1，ｇ2，…ｇmを選択して前記メモリユニットに格納し、
ｐ1およびｐ2がｐ1≡３ｍｏｄ４およびｐ2≡３ｍｏｄ４であり、前記基数の１つがｐ1およびｐ2に関して異なるルジャンドル記号を有するように、前記メモリユニットに格納されている前記基数に基づいて少なくとも２つの素因数ｐ1，ｐ2，…ｐfを選択して前記メモリユニットに格納し、
前記メモリユニットに格納されている前記素因数の積に等しい公開値としてモジュロｎを決定して前記メモリユニットに格納し、
前記メモリユニットに格納されている前記基数およびｎに基づいて、Ｇi≡ｇi2ｍｏｄ  ｎである前記公開値Ｇiを、ｉ＝１からｉ＝ｍまで計算して前記メモリユニットに格納し、
前記メモリユニットに格納されているｋ、ｎおよびＧiに基づいて、方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎまたは方程式Ｇi≡Ｑivｍｏｄ  ｎ（ここで、公開指数ｖはｖ＝２kである）のいずれかを解くことによって、ｉ＝１からｉ＝ｍまでについての秘密値Ｑiを計算して前記メモリユニットに格納する
ように構成されている、システム。
【請求項２】
３ｍｏｄ４に合同のｅ≧０である前記モジュロｎの素因数の数（ｆ−ｅ）が２より大きいものであり、３ｍｏｄ４に合同の２≦ｊ≦ｍについてのこれらの素因数ｐj+1が、
前記プロセッサが、前記素因数ｐ1，ｐ2，…ｐjに関するｇjのＰｒｏｆｉｌｅj（ｇj）を計算して前記メモリユニットに格納することであって、ｆ個の素因数ｐ1，ｐ2，…ｐfに関するｇiのＰｒｏｆｉｌｅf（ｇi）は、素因数あたり１ビットのｆビットのシーケンスであり、第１ビットは一方の論理値に等しく、後続の各ビットは、ｐ1および次の素因数に関してｇiが同じルジャンドル記号を有する場合は前記一方の論理値に等しく、ｐ1および次の素因数に関してｇiが異なるルジャンドル記号を有する場合は他方の論理値に等しいものであることと、
前記メモリユニットに格納されているプロファイル（Ｐｒｏｆｉｌｅj（ｇj））の全ビットが前記一方の論理値である場合には、前記プロセッサが、ｐ1およびｐj+1に関してｇjが異なるルジャンドル記号を有するように素因数ｐj+1を選択して前記メモリユニットに格納し、さもなければ、前記プロセッサが、ｊ−１個の基数ｇ1，ｇ2，…ｇj-1およびそのすべての乗法の組み合わせの中で、Ｐｒｏｆｉｌｅj（ｇ）＝Ｐｒｏｆｉｌｅj（ｇj）となるようにｇという数を選択し、Ｐｒｏｆｉｌｅj+1（ｇj）≠Ｐｒｏｆｉｌｅj+1（ｇ）となるようにｐj+1を選択してｐj+1を前記メモリユニットに格納することと
によって反復的に決定されるものであり、ここで、前記プロセッサは、ｆ−ｅ≦ｍのときに、ｆ−ｅ≦ｉ≦ｍであってＰｒｏｆｉｌｅf-e-1（ｇi）の全ビットが前記一方の論理値となり、前記基数ｇiのすべてがｐ1およびｐf-eに関して異なるルジャンドル記号を有するように、３ｍｏｄ４に合同の最後の素因数ｐf-eを選択して前記メモリユニットに格納する、請求項１に記載のシステム。
【請求項３】
１ｍｏｄ４（４を法にして１）に合同の、前記モジュロｎの素因数の数ｅが少なくとも１に等しいものであり、
前記プロセッサが、
ｐについてｇ1からｇmまでの基数ｇiのルジャンドル記号が＋１に等しくなるように、候補素因数ｐを選択することと、
ｐ−１が２t+1によって除算可能ではなく２tによって除算可能となるように、整数ｔを計算することと、
ｓ＝（ｐ−１＋２t）／２t+1となるように整数ｓを計算することと、
ｈがモジュロｐの整数環についての非平方剰余であり、ｂ≡ｈp-1/2tｍｏｄ  ｐとなる整数ｂを計算することと、
ｉ＝１からｍまでについてｍ個の整数ｒi≡ｇi2sｍｏｄ  ｐを計算することと、
整数ｕをｕ＝０に初期化することと、
ｉが１に初期化されているときには、以下の手順、すなわち、
整数ｗをｗ＝０に初期化することと、
ｒi＝±ｇiであって、ｉ＜ｍであれば、ｉの値を増加し、ｉの新たな値について手順をｉ＜ｍの間続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れ、
ｒi≠±ｇiであれば、
整数ｊｊを１に初期化することと、
ｉｉが１に初期化されているときには、以下の手順、すなわち、
ｘ≡ｗ2／ｇi2ｍｏｄ  ｐとなるｘを計算することと、
ｙ≡［ｘ2］(t-ii-1)を計算することと、
ｙ＝＋１であれば、そのときの値ｉｉで前記手順を終了し、
ｙ＝−１であれば、ｊｊ＝２iiとなる値ｊｊを割当て、古い値にｂjjモジュロｐを乗算したものに等しい新たな値をｗに割当て、
ｉｉ＜ｔ−２については、前記ｉｉの値を増加し、新たな反復を続行し、
ｉｉ＝ｔ−２については、ｊｊ＝２t-uまで前記ｕの値を更新し、
ｔ−ｕ＜ｋであれば、モジュロｎの因数としての候補素因数ｐを拒絶し、
ｔ−ｕ＞ｋであって、ｉ＜ｍであれば、前記ｉの値を増加し、値ｉの新たな値について一連の手順を続行し、ｉ＝ｍであれば、候補素因数ｐを前記モジュロｎの因数として受け入れることと
を反復的に実行することによって各素因数が決定されるものである、請求項１に記載のシステム。
【請求項４】
ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmのｆ．ｍ個の秘密構成要素Ｑi,jを計算するために、各組（ｉ，ｊ）について以下の手順、すなわち、
前記プロセッサが、
ｐjが３ｍｏｄ４に合同の場合には、１に等しい整数ｔを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項３に従うｔについて得られた値に整数ｔを決定することと、
ｐjが３ｍｏｄ４に合同の場合には、０に等しい整数ｕを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項３に従うｔについて得られた値に整数ｕを決定することと、
ｓ＝（ｐ−１＋２t）／２t+1である、整数ｚ≡Ｇisｍｏｄ  ｐjを計算することと、
ｕ＝０であれば、ｚｚがｚに等しいか、または、ｚｚが単位の２ii-t２ii番目の原始根のそれぞれによってｚの積（ｍｏｄ  ｐj）に等しくなり、ｉｉが１からｍｉｎ（ｋ，ｔ）の範囲となるようにすべての数ｚｚを考慮し、ｕ＞０であれば、ｚｚが、単位の２k２k番目の根のそれぞれによってｚａの（ｍｏｄ  ｐj）に等しくなるように、すべての数ｚｚを考慮することと、ここで、ｚａは、請求項３に従うｗについて得られた値であり、
そのようなそれぞれの数ｚｚについて、ｉの値について前記方程式Ｇi＝Ｑivｍｏｄ  ｎを用いた場合には、Ｑi,jがｚｚに等しいことを考慮して前記構成要素Ｑi,jについての値を得て、ｉの値についてＧi．Ｑiv≡１ｍｏｄ  ｎを使用する場合には、ｚｚのモジュロｐjのｚｚの逆数に等しいことを考慮して前記構成要素Ｑi,jについての値を得ることと
を実行するものである、請求項３に記載のシステム。
【請求項５】
非対称ないくつかの暗号鍵を生成するための命令を記憶しているコンピュータ読み取り可能な記録媒体であって、該いくつかの暗号鍵は、ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmとｍ個の公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）とを含んでおり、前記媒体は、プロセッサに対して、
１より大きい整数である機密保護パラメータｋを選択してメモリユニットに格納することと、
１より大きい整数であるｍ個の基数ｇ1，ｇ2，…ｇmを選択して前記メモリユニットに格納することと、
ｐ1およびｐ2がｐ1≡３ｍｏｄ４およびｐ2≡３ｍｏｄ４であり、前記基数の１つがｐ1およびｐ2に関して異なるルジャンドル記号を有するように、前記メモリユニットに格納されている前記基数に基づいて少なくとも２つの素因数ｐ1，ｐ2，…ｐfを選択して前記メモリユニットに格納することと、
前記メモリユニットに格納されている前記素因数の積に等しい公開値としてモジュロｎを決定して前記メモリユニットに格納することと、
前記メモリユニットに格納されている前記基数およびｎに基づいて、Ｇi≡ｇi2ｍｏｄ  ｎである前記公開値Ｇiを、ｉ＝１からｉ＝ｍまで計算して前記メモリユニットに格納することと、
前記メモリユニットに格納されているｋ、ｎおよびＧiに基づいて、方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎまたは方程式Ｇi≡Ｑivｍｏｄ  ｎ（ここで、公開指数ｖはｖ＝２kである）のいずれかを解くことによって、ｉ＝１からｉ＝ｍまでについての秘密値Ｑiを計算して前記メモリユニットに格納することと
を実行させるものである、コンピュータ読み取り可能な記録媒体。
【請求項６】
３ｍｏｄ４に合同のｅ≧０である前記モジュロｎの素因数の数（ｆ−ｅ）が２より大きいものであり、３ｍｏｄ４に合同の２≦ｊ≦ｍについてのこれらの素因数ｐj+1が、
前記プロセッサが、前記素因数ｐ1，ｐ2，…ｐjに関するｇjのＰｒｏｆｉｌｅj（ｇj）を計算して前記メモリユニットに格納することであって、ｆ個の素因数ｐ1，ｐ2，…ｐfに関するｇiのＰｒｏｆｉｌｅf（ｇi）は、素因数あたり１ビットのｆビットのシーケンスであり、第１ビットは一方の論理値に等しく、後続の各ビットは、ｐ1および次の素因数に関してｇiが同じルジャンドル記号を有する場合は前記一方の論理値に等しく、ｐ1および次の素因数に関してｇiが異なるルジャンドル記号を有する場合は他方の論理値に等しいものであることと、
前記メモリユニットに格納されているプロファイル（Ｐｒｏｆｉｌｅj（ｇj））の全ビットが前記一方の論理値である場合には、前記プロセッサが、ｐ1およびｐj+1に関してｇjが異なるルジャンドル記号を有するように素因数ｐj+1を選択して前記メモリユニットに格納し、さもなければ、前記プロセッサが、ｊ−１個の基数ｇ1，ｇ2，…ｇj-1およびそのすべての乗法の組み合わせの中で、Ｐｒｏｆｉｌｅj（ｇ）＝Ｐｒｏｆｉｌｅj（ｇj）となるようにｇという数を選択し、Ｐｒｏｆｉｌｅj+1（ｇj）≠Ｐｒｏｆｉｌｅj+1（ｇ）となるようにｐj+1を選択してｐj+1を前記メモリユニットに格納することと
によって反復的に決定されるものであり、ここで、前記プロセッサは、ｆ−ｅ≦ｍのときに、ｆ−ｅ≦ｉ≦ｍであってＰｒｏｆｉｌｅf-e-1（ｇi）の全ビットが前記一方の論理値となり、前記基数ｇiのすべてがｐ1およびｐf-eに関して異なるルジャンドル記号を有するように、３ｍｏｄ４に合同の最後の素因数ｐf-eを選択して前記メモリユニットに格納する、請求項５に記載のコンピュータ読み取り可能な記録媒体。
【請求項７】
１ｍｏｄ４に合同であり、前記モジュロｎの素因数の数ｅが少なくとも１に等しいものであり、
前記プロセッサが、
ｐについてｇ1からｇmまでの基数ｇiのルジャンドル記号が＋１に等しくなるように、候補素因数ｐを選択することと、
ｐ−１が２t+1によって除算可能ではなく２tによって除算可能であるように、整数ｔを計算することと、
ｓ＝（ｐ−１＋２t）／２t+1となるように整数ｓを計算することと、
ｈがモジュロｐの整数環についての非平方剰余であり、ｂ≡ｈp-1/2tｍｏｄ  ｐとなる整数ｂを計算することと、
ｉ＝１からｍまでについてｍ個の整数ｒi≡ｇi2sｍｏｄ  ｐを計算することと、
整数ｕをｕ＝０に初期化することと、
ｉが１に初期化されているときには、以下の手順、すなわち、
整数ｗをｗ＝０に初期化することと、
ｒi＝±ｇiであって、ｉ＜ｍであれば、ｉの値を増加し、ｉの新たな値について手順をｉ＜ｍの間続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れ、
ｒi≠±ｇiであれば、
整数ｊｊを１に初期化することと、
ｉｉが１に初期化されているときには、以下の手順、すなわち、
ｘ≡ｗ2／ｇi2ｍｏｄ  ｐとなるｘを計算することと、
ｙ≡［ｘ2］(t-ii-1)を計算することと、
ｙ＝＋１であれば、そのときの値ｉｉで前記手順を終了し、
ｙ＝−１であれば、ｊｊ＝２iiとなる値ｊｊを割当て、古い値にｂjjモジュロｐを乗算したものに等しい新たな値をｗに割当て、
ｉｉ＜ｔ−２については、前記ｉｉの値を増加し、新たな反復を続行し、
ｉｉ＝ｔ−２については、ｊｊ＝２t-uまで前記ｕの値を更新し、
ｔ−ｕ＜ｋであれば、前記モジュロｎの因数としての前記候補素因数ｐを拒絶し、
ｔ−ｕ＞ｋであって、ｉ＜ｍであれば、前記ｉの値を増加し、値ｉの新たな値について一連の手順をｉ＜ｍとなるまで続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れること
を反復的に実行することによって各素因数が決定されるものである、請求項５に記載のコンピュータ読み取り可能な記録媒体。
【請求項８】
秘密値Ｑ1，Ｑ2，…Ｑmのｆ．ｍ個の秘密構成要素Ｑi,jを計算するために、各組（ｉ，ｊ）について以下の手順、すなわち、
前記プロセッサが、
ｐjが３ｍｏｄ４に合同の場合には、１に等しい整数ｔを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項７に従うｔについて得られた値に整数ｔを決定することと、
ｐjが３ｍｏｄ４に合同の場合には、０に等しい整数ｕを決定し、ｐjが１ｍｏｄ４に合同の場合には、請求項７に従うｔについて得られた値に整数ｕを決定することと、
ｓ＝（ｐ−１＋２t）／２t+1である、整数ｚ≡Ｇisｍｏｄ  ｐjを計算することと、
ｕ＝０であれば、ｚｚがｚに等しいか、または、ｚｚが単位の２ii-t２ii番目の原始根のそれぞれによってｚの積（ｍｏｄ  ｐj）に等しくなり、ｉｉが１からｍｉｎ（ｋ，ｔ）の範囲となるようにすべての数ｚｚを考慮し、ｕ＞０であれば、ｚｚが、単位の２k２k番目の根のそれぞれによってｚａの（ｍｏｄ  ｐj）に等しくなるように、すべての数ｚｚを考慮することと、ここで、ｚａは、請求項７に従うｗについて得られた値であり、
そのようなそれぞれの数ｚｚについて、ｉの値について前記方程式Ｇi＝Ｑivｍｏｄ  ｎを用いた場合には、Ｑi,jがｚｚに等しいことを考慮して前記構成要素Ｑi,jについての値を得て、ｉの値についてＧi．Ｑiv≡１ｍｏｄ  ｎを使用する場合には、ｚｚのモジュロｐｊのｚｚの逆数に等しいことを考慮して前記構成要素Ｑi,jについての値を得ることと
を実行するものである、請求項７に記載のコンピュータ読み取り可能な記録媒体。
【請求項９】
非対称ないくつかの暗号鍵を生成するための方法であって、該いくつかの暗号鍵は、ｍ個の秘密値Ｑ1，Ｑ2，…Ｑmとｍ個の公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）とを含んでおり、プロセッサに対して、
１より大きい整数である機密保護パラメータｋを選択してメモリユニットに格納することと、
１より大きい整数であるｍ個の基数ｇ1，ｇ2，…ｇmを選択して前記メモリユニットに格納することと、
ｐ1およびｐ2がｐ1≡３ｍｏｄ４およびｐ2≡３ｍｏｄ４であり、前記基数の１つがｐ1およびｐ2に関して異なるルジャンドル記号を有するように、前記メモリユニットに格納されている前記基数に基づいて少なくとも２つの素因数ｐ1，ｐ2，…ｐfを選択して前記メモリユニットに格納することと、
前記メモリユニットに格納されている前記素因数の積に等しい公開値としてモジュロｎを決定して前記メモリユニットに格納することと、
前記メモリユニットに格納されている前記基数およびｎに基づいて、Ｇi≡ｇi2ｍｏｄ  ｎである前記公開値Ｇiを、ｉ＝１からｉ＝ｍまで計算して前記メモリユニットに格納することと、
前記メモリユニットに格納されているｋ、ｎおよびＧiに基づいて、方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎまたは方程式Ｇi≡Ｑivｍｏｄ  ｎ（ここで、公開指数ｖはｖ＝２kである）のいずれかを解くことによって、ｉ＝１からｉ＝ｍまでについての秘密値Ｑiを計算して前記メモリユニットに格納することと
を実行させるものである方法。
【請求項１０】
３ｍｏｄ４に合同であり、ｅ≧０である前記モジュロｎの素因数の数（ｆ−ｅ）が２より大きいものであり、３ｍｏｄ４に合同であり、２≦ｊ≦ｍについてのこれらの素因数ｐj+1が、
前記プロセッサが、前記素因数ｐ1，ｐ2，…ｐjに関するｇjのＰｒｏｆｉｌｅj（ｇj）を計算して前記メモリユニットに格納することであって、ｆ個の素因数ｐ1，ｐ2，…ｐfに関するｇiのＰｒｏｆｉｌｅf（ｇi）は、素因数あたり１ビットのｆビットのシーケンスであり、第１ビットは一方の論理値に等しく、後続の各ビットは、ｐ1および次の素因数に関してｇiが同じルジャンドル記号を有する場合は前記一方の論理値に等しく、ｐ1および次の素因数に関してｇiが異なるルジャンドル記号を有する場合は他方の論理値に等しいものであることと、
前記メモリユニットに格納されているプロファイル（Ｐｒｏｆｉｌｅj（ｇj））の全ビットが前記一方の論理値である場合には、前記プロセッサが、ｐ1およびｐj+1に関してｇjが異なるルジャンドル記号を有するように素因数ｐj+1を選択して前記メモリユニットに格納し、さもなければ、前記プロセッサが、ｊ−１個の基数ｇ1，ｇ2，…ｇj-1およびそのすべての乗法の組み合わせの中で、Ｐｒｏｆｉｌｅj（ｇ）＝Ｐｒｏｆｉｌｅj（ｇj）となるようにｇという数を選択し、Ｐｒｏｆｉｌｅj+1（ｇj）≠Ｐｒｏｆｉｌｅj+1（ｇ）となるようにｐj+1を選択してｐj+1を前記メモリユニットに格納することと
によって反復的に決定されるものであり、ここで、前記プロセッサは、ｆ−ｅ≦ｍのときに、ｆ−ｅ≦ｉ≦ｍであってＰｒｏｆｉｌｅf-e-1（ｇi）の全ビットが前記一方の論理値となり、前記基数ｇiのすべてがｐ1およびｐf-eに関して異なるルジャンドル記号を有するように、３ｍｏｄ４に合同の最後の素因数ｐf-eを選択して前記メモリユニットに格納する、請求項９に記載の方法。
【請求項１１】
１ｍｏｄ４（４を法にして１）に合同であり、前記モジュロｎの素因数である数ｅが少なくとも１に等しいものであり、
前記プロセッサが、
ｐについてｇ1からｇmまでの基数ｇiのルジャンドル記号が＋１に等しくなるように、候補素因数ｐを選択することと、
ｐ−１が２t+1によって除算可能ではなく２tによって除算可能であるように、整数ｔを計算することと、
ｓ＝（ｐ−１＋２t）／２t+1となるように整数ｓを計算することと、
ｈがモジュロｐの整数環についての非平方剰余であり、ｂ≡ｈp-1/2tｍｏｄ  ｐとなる整数ｂを計算することと、
ｉ＝１からｍまでについて整数ｒi≡ｇi2sｍｏｄ  ｐとなるｍを計算することと、
整数ｕをｕ＝０に初期化することと、
ｉが１に初期化されているときには、以下の手順、すなわち、
整数ｗをｗ＝０に初期化することと、
ｒi＝±ｇiであって、ｉ＜ｍであれば、ｉの値を増加し、ｉの新たな値について手順をｉ＜ｍの間続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れ、
ｒi≠±ｇiである場合には、
整数ｊｊを１に初期化することと、
ｉｉが１に初期化されているときには、以下の手順、すなわち、
ｘ≡ｗ2／ｇi2ｍｏｄ  ｐとなるｘを計算することと、
ｙ≡［ｘ2］(t-ii-1)を計算することと、
ｙ＝＋１であれば、そのときの値ｉｉで前記手順を終了し、
ｙ＝−１であれば、ｊｊ＝２iiとなる値ｊｊを割当て、古い値にｂjjモジュロｐを乗算したものに等しい新たな値をｗに割当て、
ｉｉ＜ｔ−２については、前記ｉｉの値を増加し、新たな反復を続行し、
ｉｉ＝ｔ−２については、ｊｊ＝２t-uまで前記ｕの値を更新し、
ｔ−ｕ＜ｋであれば、前記モジュロｎの因数としての前記候補素因数ｐを拒絶し、
ｔ−ｕ＞ｋであって、ｉ＜ｍであれば、前記ｉの値を増加し、値ｉの新たな値について一連の手順をｉ＜ｍとなるまで続行し、ｉ＝ｍであれば、候補素因数ｐをモジュロｎの因数として受け入れること
を反復的に実行することによって各素因数が決定されるものである、請求項９に記載の方法。
【請求項１２】
秘密値Ｑ1，Ｑ2，…Ｑmのｆ．ｍ個の秘密構成要素Ｑi,jを計算するために、各組（ｉ，ｊ）について以下の手順、すなわち、
前記プロセッサが、
ｐjが３ｍｏｄ４に合同であれば、１に等しい整数ｔを決定し、ｐjが１ｍｏｄ４に合同であれば、請求項１１に従うｔについて得られた値に整数ｔを決定することと、
ｐjが３ｍｏｄ４に合同であれば、０に等しい整数ｕを決定し、ｐjが１ｍｏｄ４に合同であれば、請求項１１に従うｔについて得られた値に整数ｕを決定することと、
ｓ＝（ｐ−１＋２t）／２t+1である、整数ｚ≡Ｇisｍｏｄ  ｐjを計算することと、
ｕ＝０であれば、ｚｚがｚに等しいか、または、ｚｚが単位の２ii-t２ii番目の原始根のそれぞれによってｚの積（ｍｏｄ  ｐj）に等しくなり、ｉｉが１からｍｉｎ（ｋ，ｔ）の範囲となるようにすべての数ｚｚを考慮し、ｕ＞０であれば、ｚｚが、単位の２k２k番目の根のそれぞれによってｚａの（ｍｏｄ  ｐj）に等しくなるように、すべての数ｚｚを考慮することと、ここで、ｚａは、請求項１１に従うｗについて得られた値であり、
そのようなそれぞれの数ｚｚについて、ｉの値について前記方程式Ｇi＝Ｑivｍｏｄ  ｎを用いた場合には、Ｑi,jがｚｚに等しいことを考慮して前記構成要素Ｑi,jについての値を得て、ｉの値についてＧi．Ｑiv≡１ｍｏｄ  ｎを使用する場合には、ｚｚのモジュロｐｊのｚｚの逆数に等しいことを考慮して前記構成要素Ｑi,jについての値を得ることと
を実行するものである、請求項１１に記載の方法。
【発明の詳細な説明】
【０００１】
本発明は、エンティティの真正性（authenticity）および／またはメッセ−ジの完全性（integrity）および／または真正性を証明するように設計されている方法、システムおよびデバイスの技術分野に関する。
【０００２】
発明者がLouis−GuillouおよびJean−Jacques Quisquaterである特許ＥＰ第０３１１４７０Ｂ１号公報がこのような方法を説明する。これ以降、彼らの研究を、用語「ＧＱ特許」または「ＧＱ方法」によって引用するものとする。これ以降、表現「ＧＱ２」または「ＱＧ２発明」あるいは「ＧＱ２技術」を、フランステレコム（France Telecom）とＴＤＦと企業Mathrizkとによって、本出願と同日に登録され、発明者がLouis GuillouおよびJean−Jacques  Quisquaterである係属出願の対象であるＧＱ技術の新しい開発を記述するために使用するものとする。これらの係属中の出願の特徴的な特色は、以下の説明の中で必要なときに想起する。
【０００３】
ＧＱ方法に従って、「信頼される当局（trusted authority）」として知られているエンティティは、「証人(witness)」と呼ばれているエンティティ（entity）に対しアイデンティティ(identity)を割り当て、それのＲＳＡ符号を計算する。顧客イズ化したプロセスでは、信頼される当局は、証人にアイデンティティおよび符号を与える。その後に証人は以下を宣言する。つまり、「ここに私のアイデンティティがある。私は、そのＲＳＡ符号を知っている。」証人は、事実を明らかにすることなく、自分が自らのアイデンティティのＲＳＡを知っていることを証明する。ＲＳＡ公開識別鍵（RSA public identification key）は、信頼される当局により配布されるが、「監査官（controller）」として知られるエンティティが、その知識を得ずに、ＲＳＡ符号が宣言されたアイデンティティに一致することを確かめる。ＧＱ方法を使用する機構は、「知識の移管（without transfer of knowledge）」を行わずに起こる。ＧＱ方法に従って、証人は、信頼される当局がそれを使って大多数のアイデンティティに署名するＲＳＡ秘密鍵（RSA private key）を知らない。
【０００４】
前記ＧＱ技術はＲＳＡ技術を利用している。しかしながら、ＲＳＡ技術は真に係数ｎの因数分解に依存しているが、ＲＳＡ技術を実現しているデジタル符号の多様な規格に対するいわゆる倍数的に増加する攻撃（multiplicative attacks）においてみられるように、この依存は等価でなく実際にはそれとはかなり異なっている。
【０００５】
ＧＱ２技術の目標は２つの部分を有する。つまり、第１に、ＲＳＡ技術の性能特徴を改善すること、第２にＲＳＡ技術に固有の問題を回避することである。ＧＱ２秘密鍵を知っていることは、係数ｎの因数分解を知っていることに等価である。三つ組のＧＱ２に対する攻撃は、係数ｎの因数分解につながる。このときには等価性がある。ＧＱ２技術を用いると、署名をするあるいは自己認証するエンティティにとっての、および、監査するエンティティにとっての作業量は削減される。機密保護と性能の両方の点での因数分解の問題をさらにうまく使用することにより、ＧＱ２技術はＲＳＡ技術の欠点を回避する。
【０００６】
ＧＱ方法は、５１２ビット以上を備える数のモジュロ計算を実現する。これらの計算は、約２16＋１乗まで累乗されたのと実質的に同じ大きさを有する数に関する。現在では、特に、銀行カ−ドの分野における既存のマイクロエレクトロニクス・インフラストラクチャは、演算コプロセッサを使用しないで一体式の自己プログラム可能なマイクロプロセッサを利用する。ＧＱ方法などの方法に関係する複数の演算アプリケ−ションに関する作業量は、一定の場合には、顧客が購入物を支払うために銀行カ−ドを使用するには不利であることを判明する計算時間に通じている。ここでは、支払カ−ドの安全性を高めるため、銀行当局が、特に解決が困難な問題を引き起こしたことを想起することができる。実際、２つの明らかに矛盾する問題を解決しなければならない。つまり、一方では、各カ−ドのますます長いかつ識別可能な鍵を使用することにより安全性を高めつつ、他方では、作業量がユ−ザに対して過剰な計算時間に通じることを妨げるのである。この問題は、既存のインフラストラクチャおよび既存のマイクロプロセッサ構成要素を考慮に入れることも必要となるため、特に急を要する。
【０００７】
ＧＱ２技術は、安全性を高めつつ、この問題に対する解決策を提供する。
【０００８】
ＧＱ２技術は、特殊な特性を有する素因数を実現する。これらの素因数を作り出すには多様な既存の技法がある。本発明の目的とは、このような素因数の組織的な生産のための方法である。それは、特にＧＱ２技術の実施によりこれらの因数から作り出すことができるアプリケ−ションにも関する。これらの特殊な素因数およびそれらを得るための方法が、Ｑ２技術の分野を超えて適用可能であることをいま強調しなければならない。
【０００９】
本発明は、コントロ−ラエンティティに以下を証明するように作られた方法（ＧＱ２方法）に適用できる。
エンティティの真正性、および／または、
このエンティティに関連付けられたメッセ−ジＭの完全性
【００１０】
この証明は、以下のパラメ−タまたはその派生物のすべてまたは一部によって確立される。
ｆ個の素因数ｐ1，ｐ2，…ｐf（ｆは２に等しいまたは大きい）の積により構成されている公開モジュラス(public modulus)ｎと、
公開指数(public exponent)ｖと、
ｍ個の別個の整数基数(integer base number)ｇ1，ｇ2，…ｇm（ｍは、１以上）。
【００１１】
基数ｇiは、２つの等式（１）と（２）である
ｘ2≡ｇiｍｏｄ  ｎおよびｘ2≡−ｇiｍｏｄ  ｎ
が、モジュロｎの整数環(the ring of integers modulo n)においてｘについて解くことができないほどであり、等式（３）
ｘv≡ｇi2ｍｏｄ  ｎ
は、モジュロｎの整数環においてｘについて解くことができるほどである。
【００１２】
本発明に従った方法は、等式（１）、（２）および（３）が満たされるような方法でｆ個の素因数ｐ1,，ｐ2,，…ｐf．を作り出すために使用される。本発明に従った方法は、最初に、
ｍ個の基数ｇ1，，ｇ2，，…ｇm，と、
係数ｎのサイズと、
ｆ個の素因数ｐ1，，ｐ2，，…ｐfのサイズと
を選ぶステップを含んでなる。
【００１３】
該方法は、公開指数ｖが、ｖ＝２kの形を持つ場合に関し、ここで、ｋは１より大きい機密保護パラメ−タ(security parameter)である。機密保護パラメ−タｋは、素数としても選択される。指数ｖのこの特殊な値は、ＧＱ２技術の必須な特色の１つである。
【００１４】
好ましくはｍ個の基数  ｇ1,，ｇ2,，…ｇmは、第１の整数の間で少なくとも部分的に選択される。また好ましくは、機密保護パラメ−タｋは、小さい整数、特に１００以下である。有利には、係数ｎのサイズは、数百ビットより大きい。また有利には、ｆ個の素因数ｐ1，，ｐ2，，…ｐfは、因数の数ｆで除算された係数ｎのサイズに近いサイズである。
【００１５】
本発明の特徴に従った主要な特徴に従い、ｆ個の素因数ｐ1，，ｐ2，，…ｐfは、明記されていない方法では選択されない。ｆ個の素因数ｐ1，，ｐ2，，…ｐfの内、それらの一定数ｅが、モジュロ４の１に一致するように選択される。素因数のこのｅは、ゼロであってよい。ｅがゼロである場合には、係数ｎは、これ以降、基本係数と呼ばれる。ｅ＞０である場合には、係数ｎは、これ以降、結合係数と呼ばれる。ｆ−ｅ個のそれ以外の素因数は、モジュロ４の３に一致するように選択される。素因数のこのｆ−ｅは、少なくとも２に等しい。
【００１６】
（モジュロ４の３に一致するｆ−ｅ個の素因数の選択）
モジュロ４の３に一致するｆ−ｅ個の素因数ｐ1，，ｐ2，，…ｐf-eを繰り出すためには、以下のステップを実施する。
モジュロ４の３に一致する第１素因数ｐ1を選択してから、
第２の素因数ｐ2を、ｐ2が基数ｇ1に関してｐ1に相補的（conplementary）となるように選択する。
【００１７】
因数ｐi+1を選択するためには、２つの場合を区別する上で以下の手順を使用する。
（１）ｉ＞ｍの場合には、
ｉ＞ｍであるならば、モジュロ４の３に一致する因数ｐi+1を選択する。
（２）ｉ≦ｍの場合には、
ｉ≦ｍであるならば、ｉ個の第１素因数ｐiに関してｇiのプロファイル（Ｐｒｏｆｉｌｅi（ｇi））を計算する。
Ｐｒｏｆｉｌｅi（ｇi）が平坦(flat)である場合には、因数ｐi+1を、ｐi+1がｇiに関してｐ1に相補的となるように選択する。
それ以外の場合には、ｉ−１個の基数ｇ1，ｇ2，…ｇi-1  およびそのすべての乗法の組み合わせの中で、これ以降ｇと呼ばれる数を、Ｐｒｏｆｉｌｅi（ｇ）＝Ｐｒｏｆｉｌｅi（ｇi）となるように選択し、したがってｐi+1を、Ｐｒｏｆｉｌｅi+1（ｇi）  ≠  Ｐｒｏｆｉｌｅi+1（ｇ）となるように選択する。
【００１８】
用語「相補的（conplementary）」、「プロファイル(profile)」、「平坦なプロファイル(flat profile)」は、本明細書の記述において定義される意味を有する。
【００１９】
最後の素因数ｐf-eを選択するためには、３つの場合区別する上で、以下の手順を使用する。
（１）ｆ−ｅ−１  ＞  ｍである場合
ｆ−ｅ−１＞ｍである場合、ｐf-eを、モジュロ４の３に一致して選択する。
（２）ｆ−ｅ−１＝ｍである場合
ｆ−ｅ−１＝ｍである場合、Ｐｒｏｆｉｌｅf-e-1（ｇm）を、ｐ1からｐf-e-1,というｆ−ｅ−１個の第１素因子に関して計算する。
もし、Ｐｒｏｆｉｌｅf-e-1（ｇm）が平坦である場合には、ｐf-e-1を、それがｇmに関してｐ1に相補的となるように選択する。
それ以外の場合には、以下に規定されている手順に従う。
ｇ1からｇm-1というｍ−１個の基数およびすべてのその乗法の組み合わせの中で、これ以降ｇと呼ばれる数をＰｒｏｆｉｌｅi（ｇ）＝Ｐｒｏｆｉｌｅi（ｇi）となるように選択し、そして、ｐf-eをＰｒｏｆｉｌｅf-e（ｇ）  ≠  Ｐｒｏｆｉｌｅf-e（ｇm）となるように選択する。
（３）ｆ−ｅ−１＜ｍである場合
ｆ−ｅ−１＜ｍである場合には、ｐf-eが、以下の２つの条件を満たすと選択される。
（３．１）  第１条件
Ｐｒｏｆｉｌｅf-e-1（ｇf-e-1）が、ｐ1からｐf-e-1のｆ−ｅ−１個の第１素因数に関して計算される。その場合に２つの場合が考えられる。これらの２つの場合のどちらかに応じて、第１条件が異なる。
もし、Ｐｒｏｆｉｌｅf-e-1（ｇf-e-1）が平坦である場合には、ｐf-eを、それがｇf-e-1に関してｐ1に相補的であるという第１条件を満たすように選択する。それ以外の場合には、ｇ1からｇm-1というｆ−ｅ−１個の基数およびそのすべての乗法組み合わせの中では、これ以降ｇと呼ばれる数を、Ｐｒｏｆｉｌｅi（ｇ）＝Ｐｒｏｆｉｌｅf-e-1（ｇf-e-1）  となるように選択してから、それがＰｒｏｆｉｌｅf-e（ｇ）  ≠  Ｐｒｏｆｉｌｅf-e（ｇm）（第２場合に従った第１条件）となるという条件を満たすように、ｐf-eを選択する。
（３．２）第２条件
ｇf-eからｇmというすべての最後の基数の間で、プロファイルＰｒｏｆｉｌｅf-e-1（ｇi）が平坦であるそれらの数を選択してから、ｐf-eを、それがこのようにして選択された基数のそれぞれに関してｐ1に相補的であるという条件（第２条件）を満たすように選択する。
【００２０】
（モジュロ４の１に一致するｅ個の素因数の選択）
モジュロ４の１に一致するｅ個の素因数を作り出すためには、以下の２つの連続試験にさらされる上で、ｐf-eからｐfのそれぞれの素因数候補ｐを評価する。
（１）第１試験
ルジャンドル記号を、候補素因数ｐに関してｇ1からｇmまでそれぞれの基数ｇiに関してして計算する。
ルジャンドル記号が−１に等しい場合には、候補ｐを拒絶し、
ルジャンドル記号が＋１に等しい場合には、候補ｐの評価を続く基数に移る際に続行し、そして、最後の基数が考慮に入れられると、第２試験へと通過する。
（２）第２試験
整数ｔを、ｐ−１が２t+1によってではなく２tによって除算可能であるように計算し、そして、整数ｓを、ｓ＝（ｐ−１＋２t）／２t+1となるように計算する。
鍵<ｓ，ｐ>は、結果ｒを得るためにそれぞれの公開値Ｇi+1適用される。
ｒ≡Ｇisｍｏｄ ｐ
もし、ｒがｇi または−ｇiに等しい場合には、第２試験を以下の公開値Ｇi+1に移る際に続行する。
もし、ｒがｇi または−ｇiとは異なる場合には、因数ｕを、１からｔ−２の範囲までＣＧ（ｐ）の添数ｉｉに指定される以下のアルゴリズムを適用する上で計算する。該アルゴリズムは２つの変数を実行する。つまり、ｒによって初期化されるｗと、ＣＧ（ｐ）の非平方剰余に鍵<（ｐ−１）／２t，ｐ>を適用することによって得られる数ｂだけではなく、２から２t-2の範囲の値を想定したｊｊ＝２iiとである。該アルゴリズムは、必要な限り何回でも以下のシ−ケンスを繰り返す。
ステップ１では、ｗ2／Ｇi（ｍｏｄ  ｐ）を計算する。
ステップ２では、結果を２t-ii-1乗まで累乗する。２つの場合を考慮すべきである。
第１場合
＋１が得られる場合には、以下の公開値Ｇi+1への通過があり、第２試験をこの公開値に関して実行する。
第２場合
−１が得られる場合には、ｊｊ＝２iiを計算されてから、ｗをｗ．ｂjj（ｍｏｄ  ｐ）によって置換する。そして、アルゴリズムを添数ｉｉを有する以下の値に関して続行する。
該アルゴリズムの最後では、変数ｊｊ内の値を、関係ｊｊ＝２t-u によって整数ｕを計算するために使用し、そして、表記ｔ−ｕを計算する。２つの場合が生じる。
ｔ−ｕ＜ｋの場合には、候補ｐを拒絶する。
ｔ−ｕ＞ｋの場合、以下の公開値Ｇi+1に移り、第２試験で続行される際に候補ｐの評価を続行する。
候補ｐは、第２試験の最後にｍ個の公開値Ｇiに関して、それが拒絶されなかった場合に、モジュロ４の１に一致する素因数として受け入れられる。
【００２１】
（ＧＱ２の公開値および秘密値に対する適用）
本発明は、上記に説明された方法を適用し、それを可能にする方法（ＧＱ２）にも関し、特別な特性を有するｆ個の素因数ｐ1，，ｐ2，，…ｐfを作り出すことを想起することができる。上記に説明された方法の適用のための方法は、コントロ−ラエンティティに対して、以下を証明するように設計される。
エンティティの真正性、および／または、
このエンティティに関連付けられたメッセ−ジＭの完全性であり、
この証明を、以下のパラメ−タまたはこれらのパラメ−タの派生物のすべてまたは一部によって確立する。
ｍ組の秘密値Ｑ1，Ｑ2，…Ｑmおよび公開値Ｇ1，Ｇ2，…Ｇm（ｍは、１以上）と、
前記素因数ｆｐ1，ｐ2，…ｐf（ｆは２以上）の積によって構成される公開モジュラスｎと、
公開指数ｖと、
前記係数と前記指数と前記値とは、以下の型の関係によってリンクされる。
Ｇi．Ｑiv≡１．ｍｏｄ ｎ、または、Ｇi≡Ｑiv ｍｏｄ ｎ ．
前記指数ｖは、ｖ＝２kであり、ここで、ｋは、１より大きい機密保護パラメ−タである。
前記公開値Ｇiは、ｆ個の素因数ｐ1，ｐ2，…ｐfより小さい基数ｇiの平方根ｇi2である。基数ｇiは、以下の２つの等式
ｘ2  ≡  ｇi ｍｏｄ ｎ、および、ｘ2  ≡  −ｇi ｍｏｄ ｎ
が、モジュロｎの整数環においてｘについて解くことができず、以下の等式
ｘv  ≡  ｇi2  ｍｏｄ ｎ
が、モジュロｎの整数環においてｘについて解くことができる。
前記方法は、以下のステップで証人と呼ばれるエンティティを実行する。前記証人エンティティは、ｆ個の素因数ｐiおよび／または該素因数のチャイニ−ズの剰余（Chinese remainder）のおよび／または公開モジュラスｎのパラメ−タおよび／またはｍ個の秘密値Ｑiおよび／または該秘密値Ｑiおよび公開指数ｖのｆ．ｍ個の構成要素Ｑi,j（Ｑi,j  ≡  Ｑi ｍｏｄ ｐj）を有する。
証人は、整数モジュロｎの環内のコミットメントＲを計算する。各コミットメントは、
Ｒ≡ｒv ｍｏｄ  ｎの型の演算を実行することによって、ここで、ｒは、０＜ｒ＜ｎとなるようにランダムな因数である。
あるいは、
Ｒi≡ｒivｍｏｄ ｐiの型の演算を実行することによって、ここで、ｒiは、０＜ｒi＜ｐiとなるように素数ｐiに関連付けられたランダムな値であり、各ｒiはランダムな因数｛ｒ1，ｒ2，…ｒf｝の集合体に属し、そして、チャイニ−ズの剰余の方法を適用することのどちらかによって計算される。
証人は、１以上のチャレンジｄを受け取る。それぞれのチャレンジｄは、これ以降初歩チャレンジと呼ばれるｍ個の整数ｄiを備える。証人は、各チャレンジｄに基づき、応答  Ｄを、
Ｄ≡ｒ．Ｑ1d1．Ｑ2d2．…Ｑmdmｍｏｄ ｎの型の演算を実行することによって、
あるいは、
Ｄi≡ｒi．Ｑi,1d1．Ｑi,2d2．…Ｑi,mdmｍｏｄ ｐiの型の演算を実行し、そして、チャイニ−ズの剰余方法（Chinese remainders method、孫氏剰余としても知られている）を適用することによって計算する。
【００２２】
方法は、コミットメントＲがあるため、チャレンジｄがあるほど多くの応答Ｄがあるほどであり、Ｒ，ｄ，Ｄ  のそれぞれのグル−プは三つ組の参照された  ｛Ｒ，ｄ，Ｄ｝を形成する。
【００２３】
好ましくは、上述したように秘密値Ｑ1，Ｑ2，…Ｑmおよび公開値Ｇ1，Ｇ2，…Ｇmの組を実現するために、方法は、チャイニ−ズの剰余の素因数ｐ1，ｐ2，…ｐfおよび／またはパラメ−タ、基数ｇ1，ｇ2，…ｇmおよび／または公開値Ｇ1，Ｇ2，…Ｇmを使用して、以下のどちらかを計算する。
Ｇiのモジュロｎのｋ番目の平方根を抽出することによって、またはＧiのモジュロｎのｋ番目の平方根の逆数を取ることによって秘密値Ｑ1，Ｑ2，…Ｑmか、  あるいは、Ｑi,j ≡Ｑi（ｍｏｄ  ｐj）となるように、秘密値Ｑ1，Ｑ2，…Ｑmのｆ．ｍ個の秘密構成要素Ｑi,jか
のどちらかを計算する。
【００２４】
さらに特定すると、秘密値Ｑ1，Ｑ2，…Ｑm  のｆ．ｍ個の秘密構成要素Ｑi,jを計算するために、
鍵<ｓ，ｐj>を、ｚ  ≡  Ｇis（ｍｏｄ ｐj）となるようにｚを計算するために適用し、
値ｔとｕを使用する。
【００２５】
値ｔおよびｕは、ｐjを、モジュロ４の１に一致するときにここに示されるように計算する。値ｔおよびｕは、それぞれ１（ｔ＝１）および０（ｕ＝０）であると解釈され、ここではｐjは、モジュロ４の３に一致する。
もし、値ｕがゼロである場合には、以下となるようにすべての数ｚｚを考える。
ｚｚがｚに等しい、または、
ｚｚが単位の２ii-t２ii番目の原始根のそれぞれによってｚの積（ｍｏｄ  ｐj）に等しく、ｉｉが１からｍｉｎ（ｋ，ｔ）の範囲である。
【００２６】
ｕが正である場合には、ｚｚが単位の２k  ２k番目の累乗根のそれぞれによってｚａの積（ｍｏｄ  ｐj）に等しくなり、ｚａが前述されたアルゴリズムの最後で変数ｗの値を指定するように、すべての数ｚｚを考えることができる。
【００２７】
構成要素Ｑi,jの少なくとも１つの値をそれから推論する。それは、等式Ｇi  ≡  Ｑivｍｏｄ ｎを使用するときにｚｚに等しいか、またはさもなければ、それは等式Ｇi．Ｑiv≡１．ｍｏｄ ｎを使用するときにｚｚのモジュロｐｊのｚｚ逆数に等しい。
【００２８】
（説明）
ＧＱ技術の目標を想起することができる。つまり、それは、エンティティのデジタル符号だけではなく、エンティティおよび関連付けられたメッセ−ジの動的な認証でもある。
【００２９】
ＧＱ技術の標準的なバ−ジョンは、ＲＳＡ技術を利用する。しかしながら、ＲＳＡ技術は真に因数分解に依存しているが、この依存は等価ではなく、ＲＳＡ技術を実現する多様なデジタル符号規格に対する倍数的に増加する攻撃として知られる攻撃から見られるように、それとはかなり異なっている。
【００３０】
ＧＱ２技術という状況では、本発明のこの部分は、さらに特に、動的な認証およびデジタル符号に備えるように作られるＧＱ２鍵の集合の生産に関する。ＧＱ２技術は、ＲＳＡ技術を使用しない。目標は２つの部分を持つ目標である。つまり、第１に、ＲＳＡ技術に関して性能を改善すること、および第２にＲＳＡ技術に固有な問題を防止することである。ＧＱ２秘密鍵は、係数ｎの因数分解である。ＧＱ２の三つ組に対する任意の攻撃は係数ｎの因数分解に相当する。つまり、この時点では等価性がある。ＧＱ２技術を使用すると、署名をする、あるいは認証されるエンティティにとって、および監査（コントロ−ル）するエンティティの両方にとって作業量は削減される。機密保護および性能という両方の点での因数分解の問題の改善された使用を通して、ＧＱ２技術はＲＳＡ技術に匹敵する。
【００３１】
ＧＱ２技術は、例えば、基数と呼ばれ、ｇｉと参照される、ｍ個の小さい整数（ｍ≧１）１より大きい１以上の小さい整数を使用する。そして、公開認証鍵<ｖ，ｎ>を以下のように選択する。公開認証指数（public velification exponent）ｖは  ２kであり、この場合ｋは、（ｋ≧２）より大きい、小さい整数である。公開モジュラスｎは、例えば、ｐ1  …ｐfのｐjによって参照されるｆ個の素因数（ｆ≧２）である、基数より大きい少なくとも２つの素因数の積である。ｆ個の素因数は、公開モジュラスｎが、ｇ1からｇmへのｍ個の基数のそれぞれに関して以下の特性を有する。
第１に、（数１）および（数２）は、整数モジュロｎの環においてｘについて解くことができない。つまり、ｇiおよび−ｇiは２つの非平方剰余(non−quadratic residues)（ｍｏｄ ｎ）である。
【数１】
0004772189.tif 000002
【数２】
0004772189.tif 000003
第２に、（数３）は、モジュロｎの整数モジュロｎの環においてｘについて解くことができる。
【数３】
0004772189.tif 000004
これ以降、これらの特性もＧＱ２原則と呼ばれる。
【００３２】
公開認証鍵<ｖ，ｎ>は、ｍ≧１である場合のｇ1からｇmという基数に従って固定されるため、それぞれの基数ｇiが、公開値Ｇiおよび秘密値ＱIを備える値ＧＱ２の組を決定する。つまり、ｍ組の参照されたＧ1Ｑ1からＧmＱmを与える。公開値Ｇiは基数ｇIの平方でありＧi＝ｇi2を与える。秘密値Ｑiは、等式（３）に対する解の１つであるか、それ以外の場合にはこのような解の逆数（ｍｏｄ  ｎ）である。
【００３３】
係数ｎがｆ個の素因数に分解されるように、整数モジュロｎの環は、ＣＧ（ｐ1）からＣＧ（ｐf）までのｆ個のガロア体（Galois field）に分解される。ここでは、ＣＧ（ｐj）内に（数１）、（数２）および（数３）の投射がある。
【数４】
0004772189.tif 000005
【数５】
0004772189.tif 000006
【数６】
0004772189.tif 000007
【００３４】
各秘密値Ｑiは、１つの素因数あたり１個の、ｆ個の秘密構成要素によって一意に表される。つまり、Ｑi,j≡Ｑi（ｍｏｄ  ｐj）である。各秘密構成要素Ｑi,jは、等式（数６）に対する解であるか、それ以外の場合には、このような解の逆数（ｍｏｄ  ｐj）である。各等式（数６）に対するすべての考えられる解が計算された後に、チャイニ−ズの剰余の技法が、等式（数３）に対するすべての考えられる解を得るために、このような解のＱi,1からＱi,f：Ｑi＝チャイニ−ズの剰余（Ｑi,1，Ｑi,2，…Ｑi,f）  のｆ個の構成要素に基づいて、秘密値Ｑiごとにすべての考えられる値をセットアップする。
【００３５】
以下はチャイニ−ズの剰余の技法（Chinese remainders technique）である。つまり、０＜ａ＜ｂとなるように、相互に素数ａおよびｂである２つの正の整数、および０からａ−１、および０からｂ−１までの２つの構成要素ＸaおよびＸbを存在させる。Ｘ＝チャイニ−ズの剰余（Ｘa，Ｘb）、つまりＸa≡Ｘ（ｍｏｄ ａ）およびＸb≡Ｘ（ｍｏｄ ｂ）となるように、０からａ．ｂ−１という単一数Ｘを求めることが必要とされる。以下がチャイニ−ズの剰余パラメ−タである。つまり、α≡｛ｂ（ｍｏｄ ａ）｝-1（ｍｏｄ ａ）である。以下はチャイニ−ズの剰余演算である。つまり、ε≡ Ｘb（ｍｏｄ ａ）、δ＝ Ｘa-ε、δが負である場合には、δをδ＋ａと、γ≡α  ．δ（ｍｏｄ  ａ）と、Ｘ＝γ．ｂ＋Ｘbとに置換する。
【００３６】
素因子が最小のｐ1から最大のｐfへと昇順で並べられるとき、チャイニ−ズの剰余パラメ−タは以下（ｆ−１、つまり素因数の内の少なくとも１つがある）である場合がある。第１のチャイニ−ズの剰余パラメ−タは、α≡｛ｐ2（ｍｏｄ ｐ1）｝-1（ｍｏｄ  ｐ1）である。第２のチャイニ−ズの剰余パラメ−タは、β≡｛ｐ1．ｐ2（ｍｏｄ  ｐ3）｝-1（ｍｏｄ  ｐ3）である。ｉ番目のチャイニ−ズの剰余パラメ−タは、λ≡｛ｐ1．ｐ2．…ｐi-1（ｍｏｄ  ｐi）｝-1（ｍｏｄ  ｐi）のようになる。最後に、ｆ−１個のチャイニ−ズの剰余演算では、第１結果（ｍｏｄ ｐ2 × ｐ1）が第１パラメ−タで得られ、そして、第２結果（ｍｏｄｐ1．ｐ2 × ｐ3）が第２パラメ−タで得られ、結果（ｍｏｄ ｐ1．…ｐf(1 × ｐf）、つまり（ｍｏｄ  ｎ）まで等々である。
【００３７】
本発明の目的とは、考えられるすべての集合の中での任意のＧＱ２鍵の集合のランダムな生成のための方法である。すなわち、
すべての考えられるＧＱ２係数の中での任意の係数、つまりｍ個の基数ｇIごとに、等式（数１）および（数２）がモジュロｎの整数環のｘの中で解決できないが、等式（数３）がそれらの内の１つを有することを保証する係数のランダムな生成と、
等式（数６）のそれぞれにすべての考えられる解決策を計算することである。チャイニ−ズの剰余技法によりすべての考えられるｈｔ等式の中で等式（数３）に対するｘ内の任意の解を得るために、Ｑi,1からＱi,fのｆ個の構成要素の各集合から秘密値Ｑiを得ることを可能にする。
Ｑi＝チャイニ−ズの剰余（Ｑi,1，Ｑi,2，…Ｑi,f）
【００３８】
問題を把握し、それから問題に与えられるべき解、つまり本発明を理解するために、最初にＧＱ２技術の原理の適用可能性を分析するものとする。「ＣＧ（ｐ）の平方まで累乗される」関数を研究し、「ＣＧ（ｐ）の平方剰余の平方根を取る」ために、ガロア体ＣＧ（ｐ）内での階数の概念を思い出すことによって始めよう。それから、私達は、等式（数４）と（数５）と（数６）とに対するＣＧ（ｐ）内のｘでの解の存在および数を分析するものとする。
【００３９】
（ＣＧ（ｐ）内の元（element）の階数（Rank））
奇数の素数ｐおよびｐより小さい正の素数ａを取ってみよう。その後に  ｛Ｘ｝を定義してみよう。
【数７】
0004772189.tif 000008
添数ｉ＋ｐの項を計算し、フェルマの定理（Fermat's theorem）を使用してみる。ここで、
【数８】
0004772189.tif 000009
である。
【００４０】
その結果、シ−ケンス｛Ｘ｝の期間は、ｐ−１またはｐ−１の割り算器である。この期間はａの値に依存する。定義によって、この期間は「ａ（ｍｏｄ  ｐ）の階数」と呼ばれる。それは、シ−ケンス｛Ｘ｝内の単位の出現の添数である。
ここで、
【数９】
0004772189.tif 000010
である。
【００４１】
例えば、（ｐ−１）／２が奇数の素数ｐ'であるとき、ガロア体ＣＧ（ｐ）は、階数１が指定される単一元を備える。つまり、それは１であり、階数２が指定された単一元である。それは−１、階数ｐ'のｐ'−１元、階数２．ｐ'、つまり階数  ｐ−１のｐ'−１元である。
【００４２】
その階数がｐ−１であるＣＧ（ｐ）の元は、原始元、あるいはまた、ＣＧ（ｐ）の生成器と呼ばれる。名前は、ＣＧ（ｐ）内のその連続する累乗、つまり１からｐ−１まで進む添数の｛Ｘ｝シ−ケンスの項が、ＣＧ（ｐ）のすべての非零元の順列を形成するという事実による。
【００４３】
ＣＧ（ｐ）の原始元ｙに従って、ｉおよびｐ−１の関数として元ｙi（ｍｏｄ ｐ）の階数を評価してみる。ｉがｐ−１が指定される素数であるとき、それはｐ−１である。ｉがｐ−１を割ると、それは（ｐ−１）／iである。すべての場合で、それは（ｐ−１）／ｐｇｃｄ（ｐ−１，ｉ）である。
【００４４】
オイラ−関数（Euler function）はψで参照される。定義により、ｎが正の整数であるため、ψ（ｎ）はｎが指定される素数であるｎより小さい正の整数の数である。したがって、体ＣＧ（ｐ）には、ψ（ｐ(１）個の原始元がある。
【００４５】
例証によって、ここにＲＳＡ技術の基礎がある。公開モジュラスｎは、ｆ≧２がであるｐ1からｐfのｆ個の素数の積であり、その結果、素因数ｐjごとに、公開指数ｖは、ｐj−１である素数である。鍵<ｖ，ｐj>は、ＣＧ（ｐj）の元の階数と準拠する。それが、それらを並べ替える逆置換は、ｐj−１がｖ．ｓj−１を割るように、鍵<ｓj，ｐj>を用いて得られる。
【００４６】
（ＣＧ（ｐ）内の累乗および平方根）
元ｘおよびｐ−ｘは、ＣＧ（ｐ）内に同じ平方を有する。鍵<２，ｐ>は、ｐ−１が偶数値であるため、ＣＧ（ｐ）を並べ替えない。素数ｐごとに、以下のように整数ｔを定義しよう。ｐ−１は、２t+1によってではなく２tによって除算可能であり、つまりｐは、２t＋１（ｍｏｄ  ２t+1）に一致している。例えば、  ｐが３（ｍｏｄ  ４）に一致するときｔ＝１である。ｐが５（ｍｏｄ  ８）に一致するときｔ＝２である。ｐが９（ｍｏｄ  １６）に一致するときｔ＝３である。ｐが１７（ｍｏｄ  ３２）に一致するときｔ＝４である、等々。それぞれの奇数の素数は、１つのおよび唯一のカテゴリに見られる。つまり、ｐはｔ番目のカテゴリ内で見られる。実際に、かなり多数の連続する素数を考える場合には、あらゆる２の内のほぼ１が第１カテゴリで見つかり、４の内の１が第２カテゴリで見つかり、８の内の１が第３カテゴリで見つかり、１６の内の１が第４カテゴリで見つかる、等々。要約すると、平均して２tの内の１つがｔ番目のカテゴリに見つけられる。
【００４７】
引数の階数のパリティに従って関数の動作、「ＣＧ（ｐ）の平方まで累乗する」を考えてみよう。
唯一の固定された元がある。それが１である。奇数パリティ階数の他の任意の元の平方は、同じ回数を有する別の元である。その結果、鍵<２，ｐ>がすべてのその（ｐ−１）／２t奇数パリティ階数元を並べ替える。順列サイクルの数は、（ｐ−１）／２tの因数分解に依存する。例えば、（ｐ−１）／２tが素数ｐ'であるときには、ｐ'−１個の元を備える大きな順列サイクルがある。
任意の奇数パリティ階数元の平方は、その階数が２によって除算される別の元である。その結果、奇数パリティ奇数元は、（ｐ−１）／２t個の分岐上で分散される。奇数パリティ階数が指定される各非零元は２t−１個の元、つまり４によってではなく、２によって除算可能な階数の元、それからｔ≧２の場合には８によってではなく４によって除算可能な階数の２個の元、およびｔ≧３の場合には１６によってではなく８によて除算可能な階数の４個の元、およびｔ≧４の場合には３２によってではなく１６によって除算可能な階数の８個の元等々、を備える長さｔの分岐を生み出す。各分岐の２t-1個の末尾は非平方剰余である。つまり、その階数は２tによって除算可能である。
【００４８】
図１Ａから図２Ｂは、体のｐ−１個の非零元のそれぞれがその場所を見つける指向型グラフによって関数「ＣＧ（ｐ）の平方まで累乗する」を図解する。非平方剰余は白であり、平方剰余は黒である。平方剰余の中、奇数パリティ階数元は円の中にある。
【００４９】
これらの図は、それぞれ以下を示す。
図１Ａは、ｐが３（ｍｏｄ  ４）に一致する場合を示す。
図１Ｂは、ｐが５（ｍｏｄ  ８）に一致する場合を示す。
図２Ａは、ｐが９（ｍｏｄ  １６）に一致する場合を示す。
図２Ｂは、ｐが１７（ｍｏｄ  ３２）に一致する場合を示す。
【００５０】
今回は、ａがＣＧ（ｐ）の平方剰余であることが既知であるので、等式ｘ2  ≡ ａ（ｍｏｄ  ｐ）に従って、ｘについての解を計算する方法、つまり「ＣＧ（ｐ）内で平方根を取る」方法を見てみよう。言うまでもなく、同じ結果を得る複数の方法がある。つまり、読者は、有利なことに「Graduate Texts in Mathematics」, vol.138 (ＧＴＭ１３８)だけではなく、１９９３年にBerlin，Springer出版のHenri Cohenの「A Coursein Computational  Algebraic Number Theory」の３１〜３６頁も参照することができる。
【００５１】
鍵<ｓ，ｐ>を確立するために整数ｓ＝（ｐ−１＋２t）／２t+1を計算してみよう。つまりｐが３（ｍｏｄ  ４）に一致するときには、<（ｐ＋１）／４，ｐ>である。ｐが５（ｍｏｄ  ８）に一致するときには、<（ｐ＋３）／８，ｐ>である。ｐが９（ｍｏｄ  １６）であるときには<（ｐ＋７）／１６，ｐ>である。ｐが１７（ｍｏｄ  ３２）であるときには<（ｐ＋１５）／３２，ｐ>である、等々。
鍵<ｓ，ｐ>は、任意の奇数パリティ階数元の奇数階数平方根を与える。実際に、ＣＧ（ｐ）では、ｒ2／ａは累乗（２．（ｐ−１＋２t）／２ t+1）−１  ＝（ｐ−１）／２t乗まで累乗されるａに等しい。その結果、ａがサイクル（cycle）にあるとき、鍵<ｓ，ｐ>が、ａを、ｗと呼ばれる解へと変換する。他の解はｐ−ｗである。
一般的には、鍵<ｓ，ｐ>は、任意の平方剰余ａをｒと呼ばれる解の第１近似へと変換する。以下は、平方根ａまでの近似のステップごとの改善の方法の大まかな略図が続く２個の鍵ポイントである。
第１に、ａは平方剰余であるため、鍵<２t-1，ｐ>は、確かにｒ2／ａを１へと変換する。
第２に、私達が、ｙと命名されるＣＧ（ｐ）の非平方剰余を知っていると仮定することができる。鍵<（ｐ−１）／２t，ｐ>は、ｙをｂと呼ばれる元へと変換する。これが、−１の根２t-1番目である。実際に、ｙ(p-1)/2  ≡  −１（ｍｏｄ  ｐ）である。その結果、ＣＧ（ｐ）では、単位の２tの２t番目の根の乗法群は、１から２tまの指数のｂ乗の乗法群に同形である。
ａの平方根に近づくためには、ｒ2／ａを２t-2（ｍｏｄ  ｐ）乗まで累乗しよう。その結果は＋１または−１である。新しい近似は、結果が＋１である場合にはｒのままであるか、さもなければ結果−１である場合には、それはｂ．ｒ（ｍｏｄ  ｐ）になる。その結果、鍵<２t-2，ｐ>は、確かに新規近似を１に変換する。必要とされる値に近づき続けることが可能である。次の段階では、必要な場合に、ｂ2（ｍｏｄ  ｐ）等で乗算することにより、調整が行われるだろう。
【００５２】
以下のアルゴリズムは、前記に定義された整数ｒおよびｂからａの平方根に達するために連続近似を行う。それは、以下の２つの変数を使用する。つまり、連続近似を表すためにｒによって初期化されるｗ、および２から２t-2の２乗の間の値を想定するｊｊである。
【００５３】
１からｔ−２までの範囲のｉの場合には、以下のシ−ケンスを反復する。
ｗ2／ａ（ｍｏｄ  ｐ）を計算してから、結果を２t-i-1（ｍｏｄ  ｐ）乗まで累乗する。つまり、＋１または−１が得られるべきである。−１が得られると、  ｊｊ＝２iを計算し、そして、ｗをｗ．ｂjj（ｍｏｄ  ｐ）で置換する。＋１が得られるときには何もしない。
【００５４】
計算の最後では、ｗおよびｐ−ｗはＣＧ（ｐ）内のａの２つの平方根である。さらに、私達は、ＣＧ（ｐ）内の階数ａが２t+1／ｊｊによってではなく、２t／ｊｊによって除算可能であることを学ぶ。この観察の関連性は、以下に理解されるだろう。
【００５５】
（ＣＧ（ｐ）内でのＧＱ２技術の原理の分析）
１より大きい２つの整数ｇとｋおよびｇより大きい素数ｐを取ってみよう。等式（数４），（数５）および（数６）内でのＣＧ（ｐ）のｘの中の解の存在および数を分析してみよう。
【００５６】
ガロア体ＣＧ（ｐ）においては、ｔの値に応じて、つまりｐ−１を除算する２の累乗に従って、さまざまな場合を区別してみよう。ｐ−１が２t+1によってではなく、２tによって除算可能である、つまりｐが２t＋１（ｍｏｄ  ２t+1）に一致していることを想起することができる。過去の分析は、私達に、大まかな解だけではなく問題に関するかなり正確な考えも与えてくれる。
【００５７】
ｔ＝１のとき、ｐは３（ｍｏｄ  ４）に一致している。ｐに関するｇおよび−ｇというルジャンドル記号は異なる。つまり、ＣＧ（ｐ）の任意の平方剰余はＣＧ（ｐ）内に２つの平方根を有する。つまり、一方は平方剰余であり、他方は非平方剰余である。第１に、２つの等式（数４）または（数５）の一方はＣＧ（ｐ）内のｘの中に２つの解を有し、他方は何も有さない。第２に、等式（数６）には、ｋの値が何であれ、ＣＧ（ｐ）のｘの中に２つの解を有する。
【００５８】
ｔ＝２のとき、ｐは５（ｍｏｄ  ８）に一致している。２つの場合は、ｐに関するｇのルジャンドル記号に応じて発生する。記号が−１に等しいとき、ｇおよび−ｇは、ともにＣＧ（ｐ）の非平方剰余である。３つの等式（数４）と（数５）と（数６）とは、ＣＧ（ｐ）のｘの中に解を有していない。記号が＋１に等しいとき、ｇおよび−ｇはＣＧ（ｐ）の２つの平方剰余であり、各等式（数４）および（数５）はＣＧ（ｐ）内のｘの中に２つの解を有する。さらに、ＣＧ（ｐ）内のｇ2の階数は、ｋの値が何であれ、等式（数６）にはＣＧ（ｐ）内のｘの中に４つの解があり、その内の１つだけが奇数パリティ階数を有することを暗示する奇数パリティ値である。
【００５９】
図３は、ｋ＝６およびｐが５（ｍｏｄ  ８）に一致し、ｔ＝２を示す等式（数６）に対する解を図解する。５（ｍｏｄ  ８）に等しいｐに関する２のルジャンドル記号は、−１．２(p-1)/4（ｍｏｄ  ｐ）に等しく、そして、−１という平方根に等しい。したがって、私達は、以下を有する。
【数１０】
0004772189.tif 000011
【数１１】
0004772189.tif 000012
【００６０】
ｔ＝３のとき、ｐは９（ｍｏｄ  １６）に等しい。Ｐに関するｇのルジャンドル記号を考慮してみよう、記号が−１に等しいとき、ｇおよび−ｇはＣＧ（ｐ）の２つの非平方剰余である。つまり、３つの等式（数４）、（数５）、（数６）は、ＣＧ（ｐ）のｘの中に解がない。記号が＋１に等しいとき、ｇおよび−ｇはＣＧ（ｐ）の２つの平常剰余である。つまり、各等式（数４）および（数５）にはＣＧ（ｐ）内ｘの中に２つの解がある。ｘについての等式（数６）に対する解の存在はＣＧ（ｐ）内のｇ2の階数に依存する。この階数は、奇数パリティ値であるか、または４によってではなく２によって除算可能である。ＣＧ（ｐ）のｇ2の階数が４によってではなく２によって除算可能であるとき、等式（数６）には、ｋ＝２の場合、ＣＧ（ｐ）内のｘについて４つの解がある。つまり、それはｋ≧３を超えることはできない。ＣＧ（ｐ）内のｇ2の階数が奇数パリティ値であるとき、等式（数６）はｋ＝２の場合ＣＧ（ｐ）内のｘの中に４つの解を有し、ｋ≧３の場合には８つの解を有する。両方の場合とも、唯一の値は奇数パリティ値である。
【００６１】
ｔ＝４のとき、ｐは１７（ｍｏｄ  ３２）に一致している。Ｐに関してｇのルジャンドル記号を考えてみよう。記号が−１に等しいとき、ｇおよび−ｇはＣＧ（ｐ）の２つの非平方剰余である。つまり、３つの等式（数４）、（数５）、（数６）は、ＣＧ（ｐ）内のｘについて解がない。記号が＋１に等しいとき、ｇおよび−ｇはＣＧ（ｐ）の２つの平方剰である。各等式（数４）および（数５）はＣＧ（ｐ）内のｘの中に２つの解を有する。等式（数６）に対するｘについて解の存在は、ＣＧ（ｐ）内のｇ2の階数に依存する。この階数は、奇数パリティ値であるか、または８によってではなく、２または４によって除算可能である。ＣＧ（ｐ）内のｇ2の階数が８によってではなく２によって除算可能である場合には、等式（数６）は、ｋ＝２の場合、ＣＧ（ｐ）内のｘについて４つの解を有する。つまり、それはｋ≧３を超えることはできない。ＣＧ（ｐ）内のｇ2の階数が４によってではなく２によって除算可能であるとき、等式（数６）は、ｋ＝２の場合ＣＧ（ｐ）内のｘについて４つの解、またはｋ＝３の場合８つの解を有する。それは、ｋ≧４の場合にはまったく解を有さない。ＣＧ（ｐ）内のｇ2の階数が奇数パリティ値であるとき、等式（数６）は、ｋ＝２の場合ＣＧ（ｐ）内のｘの中で４つの解を、ｋ≧３の場合８つの解を、およびｋ≧４のときには１６個の解を有する。３つすべての場合において、唯一の値は奇数パリティ値である。
【００６２】
ｐが１（ｍｏｄ  ４）に一致している場合を、以下のように要約できるように等々である。
【００６３】
ｐが１（ｍｏｄ  ４）に等しいとき、ｐに関するｇのルジャンドル記号を考えてみよう。記号が−１に等しいとき、ｇおよび−ｇはＣＧ（ｐ）の２つの非平方剰余である。つまり、３つの等式（数４）、（数５）、（数６）は、ＣＧ（ｐ）のｘについて解がない。記号が＋１に等しいとき、ｇおよび−ｇは、ＣＧ（ｐ）の２つの平方剰余である。各等式（数４）および（数５）は、ＣＧ（ｐ）のｘについて２つの解を有する。整数ｕを定義してみよう。ＣＧ（ｐ）内のｇ2の階数は、２u+1によってではなく、２uによって除算可能である。ｕ  の値は０からｔ−２の考えられるｔ−１値の中にある。等式（数６）に対するＣＧ（ｐ）のｘの中の解の存在および数は、ｋ、ｔおよびｕの値に依存する。ｕが正であり、ｋがｔ−ｕより大きい場合には、等式（数６）は、ＣＧ（ｐ）のｘについて解を有していない。ｕがゼロであり、ｋがｔより大きいとき、等式（数６）はＣＧ（ｐ）のｘについて２t個の解を有する。ｋがｔ−ｕより小さいとき、等式（数６）は、ＣＧ（ｐ）内のｘの中に２k個の解を有する。
【００６４】
（整数係数の環内でのＧＱ２原理の適用可能性）
等式（数１）および（数２）がそれぞれモジュロｎの整数環のｘの中で解を有さないためには、ｐ1からｐf，という素因数ｐの少なくとも１つにとって、等式（数４）および（数５）がそれぞれＣＧ（ｐ）内のｘに解を有さないことが必要であり十分である。
【００６５】
等式（数３）がモジュロｎの整数環のｘの中で解を有するためには、ｐ1からｐf，という素因数ｐのそれぞれにとって、等式（数６）がＣＧ（ｐ）内のｘに解を有さなければならないことが必要であり、十分である。
【００６６】
等式（数３）は、１（ｍｏｄ  ４）に一致する素因数ｐが、可能な限りはやく基数ｇの１つに関してｇ1からｇmになるのを禁止する。つまり、ｐに関するｇというルジャンドル記号が−１に等しいか、あるいはさもなければｐに関するｇというルジャンドル記号は以下の条件付きで＋１に等しい。つまり、ｕが正であり、ｔ−ｋより大きい。１（ｍｏｄ  ４）に等しい素因数ｐが考えられる可能性があるためには、ここに前述された２つの整数ｔおよびｕに従って、ｇ1からｇmの基数ｇのそれぞれに対する次の２つの条件の内の１つを満たすことが必要である。Ｇ＝ｇ2の階数は、ｋの値が何であれ、ＣＧ（ｐ）内の奇数パリティ階数である、つまりｕ＝０である。または、さもなければＧ＝ｇ2の階数はＣＧ（ｐ）内の奇数パリティ階数値、つまりｕ＞０であり、それがｕ＋ｋ≦ｔという条件を満たす。
【００６７】
１（ｍｏｄ ４）に一致する素因数の積は、ＧＱ２技術のすべての原理を満たすことはできない。各ＧＱ２係数は、基数ｇごとに、これらの因数の一方に関するｇのルジャンドル記号が、他方に関するｇのルジャンドル記号と異なるように、３（ｍｏｄ  ４）に一致している少なくとも２個の素因数を有さなければならない。すべての素因数が３（ｍｏｄ  ４）に一致しているとき、ＧＱ２係数は基本(basic)であるといわれる。３（ｍｏｄ  ４）に一致している少なくとも２つの素因数に加えて、係数は、１（ｍｏｄ  ４）に一致している１以上の素因数を含み、係数ＧＱ２は  結合されていると言われる。
【００６８】
（係数ＧＱ２の体系的な構築）
最初に、係数ｎに関して規定されなければならない全体的な制約を固定する必要がある。つまり、１のときの最上位ビットの数（少なくとも１つ、言うまでもなく、典型的には１６ビットまたは３２ビット）、素因数の数ｆと１（ｍｏｄ  ４）に一致しなければならない素因数の数ｅ（おそらくゼロ）だけではなく、ビット単位で表されるサイズ（例えば、５１２ビットまたは１０２４ビット）、その他の素因数、すなわちｆ−ｅ因数、少なくとも２つが３（ｍｏｄ  ４）に一致していなければならない。係数ｎは、類似したサイズのｆ個の素因数の積となる。ｅ＝０のとき、基本係数ＧＱ２が得られる。ｅ＞０のとき、結合係数ＧＱ２が得られる。基本係数は、すべて３（ｍｏｄ  ４）に等しい素因数の積である。したがって、結合係数ＧＱ２は、１（ｍｏｄ  ４）に一致している１以上のその他の素因数によって乗算される基本係数ＧＱ２の積として出現する。最初に、３（ｍｏｄ  ４）に一致している素因数が作成される。そして、ｅ＞０であると、１（ｍｏｄ  ４）に一致している素因数が作成される。
【００６９】
係数の構築の効力のため、それが素数値であるかどうかを突き止めようとする前に各候補を選択するのが確かによいであろう。
【００７０】
ｇ1  ｇ2  …によって参照されるとき、基数は、典型的には第１素数、つまり２、３、５、７．．．の中で見つけられる。逆の表示がない場合には、ｍ個の基数はｍ個の第１素数である。つまり、ｇ1＝２、ｇ2＝３、ｇ3＝５、ｇ4＝７、…。しかしながら、以下の点を注記しなければならない。５（ｍｏｄ  ８）に一致する係数が予想される場合には２は回避しなければならない。公開鍵<３，ｎ>をＲＳＡ公開認証鍵として使用しなければならない場合には、３は回避しなければならない。
【００７１】
（３（ｍｏｄ  ４）に一致するｆ−ｅ個の素因数の選択）
第２因数に基づき、プログラムは、因数ごとに１つの基数を要求、使用する。３（ｍｏｄ  ４）に一致する最後の因数を選択するためには、プログラムは、他の基数があるかどうか、すなわちｍがｆ−ｅに等しい、またはそれより大きいかどうかを突き止め、それからこれが当てはまる場合には、ｇf-eからｇmという最後の基数を要求し、考慮に入れる。３（ｍｏｄ  ４）と一致する最後の基数の選択を形式化するために、私達はプロファイルという概念を導入した。プロファイルは、ｇより大きく、３（ｍｏｄ  ４）に一致する素因数の集合に関して整数ｇを特徴付ける。
整数ｇに２つの素因数に関して同じルジャンドル記号が付く場合には、素因数は、ｇに関して等価であるといわれる。さもないと、それらはｇに関して相補的である。
プロファイル（ｇ）によって参照され、ｆ個の素因数ｐ1  ｐ2  …ｐfに関する整数ｇのプロファイルは、素因数あたり１ビットのｆ個のビットのシ−ケンスである。第１ビットは１に等しい。それぞれの続くビットは、次に因数がｇに関してｐ1に等価であるのか、または相補的であるのかに応じて１または０に等しい。
プロファイルのすべてのビットが１に等しいとき、プロファイルは平坦であると言われる。このような場合には、ｇに関するすべてのルジャンドル記号は＋１に等しいか、さもなければ−１に等しい。ｇのプロファイルが平坦ではないとき、等式（数１）および（数２）は、モジュロｎの整数環のｘの中で解くことはできない。
定義によって、３（ｍｏｄ  ４）に一致する単一素数に関するｇのプロファイルはつねに平坦である。この拡張は、３（ｍｏｄ  ４）に一致する素因数の選択のアルゴリズムを汎用化するために使用される。
【００７２】
２つの基数ｇ1とｇ2のプロファイルが異なるとき、それは３（ｍｏｄ  ４）に一致する少なくとも３つの素因数を暗示し、２つの秘密値Ｑ1とＱ2の情報が、係数ｎの２つの異なる分解の情報を引き出す。基数が小さい素数であるとき、プログラムは、ｆ−ｅ−１個の基本素数の２f-e-1−１個の乗法の組み合わせのプロファイルがすべて異なることを保証する。それらは、すべての考えられる値を取る。プロファイルという概念は、１（ｍｏｄ  ４）に一致する素因数まで拡張しない。
【００７３】
３（ｍｏｄ  ４）に一致する第１素因数ｐ1は、各候補が他の特定の制約なしに３（ｍｏｄ  ４）に一致しなければならない。
【００７４】
第１基数ｇ1が考慮に入れられている３（ｍｏｄ  ４）に一致する第２素因数ｐ2は、各候補がｇ1に関してｐ1に相補的でなければならない。
【００７５】
第２基数ｇ2が考慮に入れられている３（ｍｏｄ  ４）に一致する第３素因数ｐ3は、２つの第１素因数ｐ1およびｐ2に関するｇ2のプロファイルに従って、２つの場合が発生する。Ｐｒｏｆｉｌｅ2（ｇ2）が平坦であるとき、各候補はｇ2に関してｐ1に相補的でなければならない。さもなければ、Ｐｒｏｆｉｌｅ2（ｇ1）＝Ｐｒｏｆｉｌｅ2（ｇ2）を有する。そして、各候補は、Ｐｒｏｆｉｌｅ3（ｇ1）≠Ｐｒｏｆｉｌｅ3（ｇ2）を保証しなければならない。
【００７６】
基数ｇiが考慮に入れられている３（ｍｏｄ  ４）に一致するｉ番目の素因数ｐi+1の選択は、ｉ個の第１素因数ｐ1，ｐ2，…ｐiに関するｇiのプロファイルに従って、２つの場合が発生する。Ｐｒｏｆｉｌｅi（ｇi）が平坦であるとき、各候補はｇiに関してｐ1に対し相補的でなければならない。さもなければ、ｉ−１番目の基数ｇ1，ｇ2，…ｇi-1およびその乗法の組み合わせｇ1．ｇ2，…，ｇ1．ｇ2．…ｇi-1、つまり、すべての中で２i-1−１個の整数の中では、Ｐｒｏｆｉｌｅi（ｇi）＝Ｐｒｏｆｉｌｅi（ｇ）であるように、１つおよび唯一の整数ｇがある。そして、各候補は、Ｐｒｏｆｉｌｅi+1（ｇi）≠Ｐｒｏｆｉｌｅi+1（ｇ）を保証しなければならない。
【００７７】
基数ｇf-e-1およびｇf-eからｇmというそれ以外の基数が考慮に入れられている３（ｍｏｄ  ４）に一致する最後の素因数ｐf-eは、基数ｇf-e-1のための制約が前述されたように考慮に入れられる。さらに、ｍがｆ−ｅに等しい、またはそれより大きいとき、各候補はｆ−ｅ個の素因数に関してｇf-eからｇmという最後の基数の非平坦プロファイルに備えなければならない。各候補は、Ｐｒｏｆｉｌｅf-e-1（ｇi）が平坦であるｇ iのすべての値に関してｐ1に相補的でなければならない。
【００７８】
要約すると、３（ｍｏｄ  ４）に一致する素因数は、互いの関数として選択される。
【００７９】
０からｆ−ｅ−１の範囲のｉの場合には、３（ｍｏｄ  ４）に一致するｉ＋１番目の素因数を選択するには、候補ｐi+1は、無事に以下の試験に合格しなければならない。
ｉ＞ｍまたはｉ＝０の場合には、候補ｐi+1にはそれ以外の制約はない。したがって、それは受け入れられている。
０＜ｉ≦ｍの場合には、候補ｐi+1はｉ番目の基数ｇiを考慮に入れなければならない。ｐ1からｐiのｉ個の素因数に関する基数ｇIのプロファイルＰｒｏｆｉｌｅi（ｇi）を計算する。結果に応じて、以下の２つの場合の内の１つおよび１つだけが発生することができる。
プロファイルが平坦である場合には、候補ｐi+1は、ｇiに関してｐ1に相補的でなければならない。さもなければ、それは拒絶されなければならない。
さもなければ、ｉ−１個の基数およびすべてのその乗法組み合わせの中で、Ｐｒｏｆｉｌｅi（ｇ）＝Ｐｒｏｆｉｌｅi（ｇi）となるようにｇと呼ばれる１つのおよび唯一の数がある。そして、候補ｐi+1は、Ｐｒｏｆｉｌｅi+1（ｇ）  ≠  Ｐｒｏｆｉｌｅi+1（ｇi）となるようでなければならない。さもなければ、それは拒絶されなければならない。
ｉ＋１＝ｆ−ｅであり、ｉ＜ｍの場合、つまりまだ考慮に入れられていない、基数ｇf-eからｇmが残るときには、３（ｍｏｄ  ４）に一致する最後の素因数を選択するために、候補ｐf-eはそれらを考慮に入れなければならない。これらの基数の中で、そのプロファイルＰｒｏｆｉｌｅf-e-1（ｇi）が平坦であるそれらの数が選択される。候補ｐf-eは、このようにして選択された基数のそれぞれに関してｐ1に相補的でなければならない。さもなければ、それらは拒絶されなければならない。
【００８０】
候補は、それが無事に適切な試験を受けたため受け入れられる。
【００８１】
（１（ｍｏｄ  ４）に一致するｅ個の素因数の選択）
許容できるためには、１（ｍｏｄ  ４）に一致する各候補ｐは、ｇ1からｇmという各基数に関して以下の条件を満たさなければならない。
ｐに関する各基数ｇiのルジャンドル記号を評価してみよう。もし、記号が−１に等しい場合には、候補ｐを拒絶し、別の候補に移動しよう。記号が＋１に等しい場合には、候補の評価を続行しよう。整数２が基数として使用される場合には、５（ｍｏｄ  ８）に一致するすべての候補が削除されなければならない。基数２は５（ｍｏｄ  ８）に一致する係数とは相容れない。
鍵<ｓ，ｐ>を確立するために、整数ｓ＝（ｐ−１＋２t）／２t+1を計算しよう。結果ｒを得るために、各公開値Ｇiに鍵<ｓ，ｐ>を適用しよう。
もし、ｒがｇiまたは−ｇiに等しい場合には、ｕ＝０である。この場合およびこの場合だけ、Ｇiはサイクル内にある。自明な場合を注記することができる。つまり、Ｇiは、ｐが５（ｍｏｄ  ８）に一致し、ｐに関するｇiというルジャンドル記号が＋１に等しいならばサイクル内にある。Ｇi＝４が、この場合では不可能であることを想起することができる。
もし、ｒがｇiにも−ｇiにも等しくない場合には、ｕ＞０である。鍵<（ｐ−１）／２t，ｐ>が、あらゆる非平方剰余ｙを、単位の２t番目の根であるｂに変換することを注記しなければならない。以下のアルゴリズムは、２つの整数変数を使用することにより、ｒおよびｂからｕを計算する。つまり、ｒによって初期化されたｗおよび２から２t-2の値を取るｊｊである。
１からｔ−２の範囲のｉの場合には、以下のシ−ケンスを繰り返す。
ｗ2／Ｇi（ｍｏｄ  ｐj）を計算してから、累乗２t-i-1（ｍｏｄ  ｐj）まで結果を累乗する。つまり、私達は、＋１または−１を得なければならない。−１が得られたら、ｊｊ＝２iを計算し、それからｗ．ｂjj（ｍｏｄ  ｐj）で  ｗ  を置換する。＋１が得られたら何も行わない。
【００８２】
計算の最後に、変数ｗは、値ｇiまたは−ｇiを有する。さらに、ＣＧ（ｐj）  内のＧi  の階数が、２t+1／ｊｊによってではなく、  ２t／ｊｊによって除算可能である、つまり、ｊｊがｊｊ＝２t-uによるｕの値を決定することを知っている。ｖがｊｊより大きいとき、つまりｋ＞ｔ−ｕであるときには、候補を拒絶し、別の候補に移動する。ｖがｊｊより小さい、または等しいとき、つまりｋ≦ｔ−ｕには、候補の評価を続行する。
【００８３】
ｆ個の素因数が作成されると、公開モジュラスｎは、ｆ個の素因数ｐ1，ｐ2，…ｐfの積である。符号なし整数ｎは、バイナリシ−ケンスによって表すことができる。つまり、このシ−ケンスは、ビットのサイズに関して、および１での連続最上位ビットの数に関してプログラムの始めに課された制約に準拠している。素因数の選択は、ｍ個の基数ｇ1，ｇ2，…ｇm  のそれぞれに関しての係数ｎの以下の特性に備える。さらに、等式（数１）および（数２）は、モジュロｎの整数環のｘの中に解を有さない。第２に、等式（数３）は、モジュロｎの整数環のｘの中に解を有する。
【００８４】
要約すると、１（ｍｏｄ  ４）に一致する素因数は、互いとは無関係に選ばれる。３（ｍｏｄ  ４）に一致する因数は徐々に基数を考慮に入れるが、１（ｍｏｄ  ４）に一致する各素因数は基数のそれぞれによって規定されているすべての制約を考慮に入れなければならない。ｐf-eからｐfまでの１（ｍｏｄ  ４）に一致する各素因数、つまりｐは、２つのステップで以下の試験を無事に受けるべきであった。
１）ステップ（１）は、ｇ1からｇmへｍ個の基数のそれぞれに連続して実行される。
候補ｐに関する現在の基数ｇのルジャンドル記号が計算される。以下の２つの場合の内の１つおよび１つだけが発生する。つまり、記号が−１に等しい場合には、候補は拒絶される。さもなければ（記号が＋１に等しい）、試験は、ステップ（１）の後の基本数ｇに移る際に続行される。
候補がすべてのｍ個の基数に関して許容できるときには、演算はステップ（２）に移る。
２）ステップ（２）は、Ｇ1からＧmまでｍ個の公開値のそれぞれに連続して実行される。
整数ｔは、ｐ−１が２t+1によってではなく、２tによって除算可能であるように計算され、それから鍵<ｓ，ｐ>をセットアップするために、整数ｓ＝（ｐ−１＋２t）／２t+1である。鍵<ｓ，ｐ>は、結果ｒ、つまり、
【数１２】
0004772189.tif 000013
を得るために、現在の公開値Ｇ＝ｇ2に適用される。結果に応じて、以下の状態の１つおよび１つだけが発生する。
ａ）ｒがｇまたは−ｇに等しい場合には、ｕ＝０である。候補の試験はステップ（２）で以下の公開値Ｇに移る際に続行される。
ｂ）さもなければ、正の数ｕが、２つの変数を実現する以下のアルゴリズムを適用する際に、１からｔ−２の値の１つを取って計算される。つまり、２から２t-2という範囲の値を取るｊｊおよびＣＧ（ｐ）の非平方剰余に鍵<（ｐ−１）／２t，ｐ>を適用することによって得られる整数ｂだけではなく、ｒによって初期化されるｗである。
１からｔ−２の添数ｉｉの場合、以下の演算が繰り返される。
ｗ2／Ｇ（ｍｏｄ  ｐ）を計算してから、鍵<２t-ii-1，ｐ>が、＋１または−１を得るために結果に適用される（さもなければ、候補が素因数ではないという証拠がある）。−１が得られる場合には、ｊｊ＝２iiが計算されてから、ｃ≡ｂjj（ｍｏｄ  ｐ）を計算し、ｗをｗ．ｃ（ｍｏｄ  ｐ）によって置換し、そして、次の添数ｉｉへの通過がある。＋１が得られると、次の添数ｉｉへの通過がある。
アルゴリズムの最後では、変数ｊｊの値が、関係性ｊｊ＝２t-uによってｕを定義する。変数ｗ  の値はＧの平方根、つまりｇまたは−ｇである（さもなければ、候補が素因数ではないという証拠がある）。２つの場合が発生する。
ｔ−ｕ＜ｋの場合には、候補ｐは、Ｇが発生する分岐が十分に長くないために拒絶される。
（ｔ−ｕ≧ｋ）の場合には、候補の評価は、ステップ（２）の後に次の公開値  Ｇに移動する上で続行される。
候補がすべてのｍ個の公開値にとって許容できるときには、それは１（ｍｏｄ  ４）と一致する素因数として受け入れられる。
【００８５】
（関連付けられる値の計算）
秘密構成要素を得るために、一般的な場合を取り上げる前に、まず２つの最も簡略かつ最新の場合での等式（数６）に対するすべての解を計算しよう。
【００８６】
３（ｍｏｄ  ４）に一致する各素因数ｐjに対しては、鍵<（ｐj＋１）／４，ｐj>は任意の平方剰余の平方剰余根を与える。このことから、等式（数６）に対する解を計算するための方法を推論する。つまり、
ｓj  ≡（（ｐj＋１）／４）k（ｍｏｄ（ｐj−１）／２）であれば、Ｑi,j  ≡  Ｇisj（ｍｏｄ  ｐj）であり、
または、さもなければ、むしろこのような解の逆数（ｍｏｄ  ｐj）である。
ｓj  ≡（ｐj−１）／２−（（ｐj＋１）／４）k（ｍｏｄ（ｐj−１）／２）であれば、Ｑi,j  ≡  Ｇisj（ｍｏｄ  ｐj）である。
【００８７】
ＣＧ（ｐj）においては、その場合、単位の２つのおよび２つだけの平方根がある。つまり、＋１と−１である。したがって、等式（数６）に対するｘ内の２つの解がある。つまり、２つの数Ｑi,jおよびｐj−Ｑi,jは、同じ平方Ｇi（ｍｏｄ ｐj）である。
【００８８】
５（ｍｏｄ  ８）に一致する各素因数ｐjに対しては、鍵<（ｐj＋１）／４，ｐj>は、任意の奇数パリティ階数元の奇数パリティ階数平方根を与える。このことから、等式（数６）に対する解を推論する。つまり、
ｓj  ≡（（ｐj＋３）／８）k（ｍｏｄ（ｐj−１）／４）であれば、Ｑi,j  ≡  Ｇisj（ｍｏｄ  ｐj）であり、
または、さもなければ、むしろこのような解の逆数（ｍｏｄ  ｐj）である。
ｓj  ≡（ｐj−１）／４−（（ｐj＋３）／８）k（ｍｏｄ（ｐj−１）／４）であれば、Ｑi,j  ≡  Ｇisj（ｍｏｄ  ｐj）である。
ＣＧ（ｐj）においては、単位の４つおよび４つだけの第４根がある。したがって、等式（数６）に対するｘの中に４つの解がある。２(pj-1)/4（ｍｏｄ  ｐj）が、５（ｍｏｄ  ８）に一致するｐに関する２のルジャンドル記号が−１に等しいため、−１という平方根であることを注記しよう。Ｑi,jが解である場合には、−１という平方根によるＱi,jの積（ｍｏｄ  ｐj）だけではなく、ｐj−Ｑi,jも別の解である。
【００８９】
２t＋１（ｍｏｄ２t+1）に一致する素因数ｐjに対しては、鍵<（ｐj−１＋２t）／２t+1，ｐj>は、任意の奇数パリティ次数元の奇数パリティ平方根を与える。したがって、等式（数６）に対する解を計算することが可能である。
最初に、整数ｓj≡（（ｐj−１＋２t）／２t+1）k（ｍｏｄ（ｐj−１）／２t）を計算して、鍵<ｓj，ｐj>をセットアップしよう。
鍵<（ｐj−１＋２t）／２t+1，ｐj>が、Ｇiをｇiまたは−ｇiに変換するとき、Ｇiの階数はＣＧ（ｐj）（ｕ＝０）内の奇数パリティ値である。それから、鍵<ｓj，ｐj>は、Ｇiを数ｚへと変換する。これは、等式（数６）に対する奇数パリティ階数解である。ｔおよびｋの値に従って、依然として１以上の分岐上にｍｉｎ（２k−１，２t−１）のその他の解がある。ｚ2の分岐は別の解を運ぶ。これがｐj−ｚである。ｔ≧２のとき、ｚ4の分岐には２つのそれ以外の解がある。それは、−１の２つの平方根のそれぞれ、つまり単位の２つの原始第４元のそれぞれによるｚの積である。いま、ｙがＣＧ（ｐj）の非平方剰余である場合には、  ｙ(pj-1)/4（ｍｏｄ  ｐj）は、−１の平方根である。一般的には、１からｍｉｎ（ｋ，ｔ）の各値を取るｉの場合には、ｚの２i番目の累乗の分岐が２i-1個の解を生じさせる。これらは、単位の２i-1個の原始２i番目の元のそれぞれによるｚの（ｍｏｄ  ｐj）である。いまｙがＣＧ（ｐj）の非平方剰余である場合には、累乗（ｐj−１）／２iに対するｙは、私達がｃと呼ぶ単位の２i番目の原始根である。単位の２i-1番目から２i番目の原始根は、ｃの奇数パリティ累乗である。つまり累乗２i−１（ｍｏｄ  ｐj）までのｃ，ｃ3（ｍｏｄ  ｐj），ｃ5（ｍｏｄ  ｐj），…ｃである。
鍵<（ｐj−１＋２t）／２t+1，ｐj>が、ｇiでもなく−ｇiでもないＧiを整数  ｒに変換するとき、Ｇiの階数はＣＧ（ｐj）（ｕ＞０）内の奇数パリティ値である。その場合には、Ｇiが適切にかなり冗長な分岐、つまりｔ≧ｋ＋ｕに置かれる場合、Ｇiが位置している分岐上に２k個の解がある。２k番目の根を計算するために解ｚまでの連続結果の平方根を計算するには、前述された平方根計算アルゴリズムｋを階数分反復することで十分である。この計算は、言うまでもなく、２k番目の根に直接的に近づいてから、解ｚを達成するために単一演算で２k番目の根の近似を調整するために最適化することができる。すべてのそれ以外の解を得るために、まず第１に、ｙがＣＧ（ｐj）の非平方剰余である場合には、（ｐj−１）／２k乗までのｙが、ｄと呼ばれる単位の原始２k番目の根であることを注記することができる。単位２kの２k番目の根は、ｄの連続累乗である。つまり、２k−１（ｍｏｄ  ｐj）乗までのｄ，ｄ2（ｍｏｄ  ｐj），ｄ3（ｍｏｄ  ｐj），…ｄ、２k（ｍｏｄ  ｐj）乗までのｄは１に等しい。Ｇiが位置している分岐上の２k個の解は、これらの根のそれぞれのｚの積（ｍｏｄ  ｐj）である。
【００９０】
要約すると、ｋ，ｔおよびｕが既知の状態で素因数ｐの構成要素および基数ｇを計算するには、以下の手順を使用する。
１）鍵<ｓ，ｐ>をセットアップするために、整数を計算する。ｓ≡（（ｐ−１＋２t）／２t+1）k（ｍｏｄ（ｐ−１）／２t）。そして、鍵<ｓ，ｐ>を、ｚ≡Ｇs(mod  ｐ）を得るために、Ｇに適用する。Ｕの値に従って、ステップ（２）または（３）への通過がある。
２）ｕ＝０である場合には、ｚは等式（数６）に対する奇数パリティ解である。依然として、１以上の分岐上に、非常に正確にはｍｉｎ（ｋ，ｔ）の他の分岐上に、ｍｉｎ（２k−１，２t−１）のその他の奇数パリティ階数解がある。１からｍｉｎ（ｋ，ｔ）の範囲のｉの場合には、ｚの２i番目の累乗の分岐が２i-1  の解を有する。これらは、単位２i-1  の２i番目の原始元のそれぞれによるｚの（ｍｏｄ  ｐ）である。等式（数６）に対する総称的な解は、ｚｚによって示される。演算はステップ（４）に移動する。
３）ｕ＞０の場合には、等式（数６）に対するすべての解は、奇数パリティ解である。それらの内の２kがあり、それらはすべてＧが位置している分岐内にある。実際には、ｔ−ｕ≧ｋである。解を計算するには、以下のアルゴリズムが２つの変数を実行する。つまり、鍵<（ｐ−１）／２t，ｐ>をＣＧ（ｐ）の非平方剰余に適用することによって得られる整数ｂだけではなく、２から２t-2の範囲の値を想定するｊｊおよびｚによって初期化されるｗである。
以下のシ−ケンスはｋ階数回繰り返される。
１からｔ−２の範囲の添数ｉｉの場合には、以下の演算が繰り返される。つまり、ｗ2／Ｇ（ｍｏｄ  ｐ）を計算し、そして、鍵<２t-ii-1，ｐ>を、＋１または−１を得るために結果に適用する（さもなければ、ｐが素数であるという証拠がある）。−１が得られると、ｊｊ＝２ii を計算し、そして、ｃ≡ｂjj（ｍｏｄ  ｐ）を計算してから、ｗをｗ．ｃ（ｍｏｄ  ｐ）によって置換し、次の添数ｉｉへの通過がある。＋１が得られると、次の添数ｉｉへの通過がある。
アルゴリズムの最後では、変数ｗが値ｚａを有する。Ｇが位置する分岐上の  ２k  の解は、単位の２k番目の根のそれぞれによるｚａの（ｍｏｄ  ｐ）である。等式（数６）に対する総称的な解は、ｚｚによって表される。演算はステップ（４）に移る。
４）ｚｚが既知である状態で、構成要素値は、そこから推論される。つまり、それは、等式Ｇ≡Ｑv（ｍｏｄ  ｎ）が使用されるときにモジュロｐのｚｚの逆数であり、等式Ｇ．Ｑv≡１（ｍｏｄ  ｎ）が使用されるとき、ｚｚである。
（注記）  秘密構成要素および秘密値を得るには多様な方法がある。ｆ個の構成要素、つまり指定された基数に対してｆ個の構成要素が既知である場合には、対応する秘密値を計算するために、チャイニ−ズの剰余技法が使用される。指定された公開値Ｇ  および係数ｎの場合に、複数の考えられる秘密値Ｑを有することが可能である。ｎが３（ｍｏｄ４）に一致する２つの素因数の積であるときには、それらの内の４つがある。３（ｍｏｄ  ４）に一致する３つの素因数ではそれらの内の８つがある。３（ｍｏｄ  ４）に一致する２つの素因数および５（ｍｏｄ  ８）に一致する１つの素因数ではそれらの内の１６がある。これらの複数の値の賢明な使用は、ＧＱ２を使用するチップカ−ドの電気的な消費の分析による攻撃を複雑にする可能性がある。
【００９１】
このようにして、ｔが増加するので、および増加するとき、プログラムは、ますます珍しい場合に関して複雑になる。実際に、素数は以下のように平均して分散される。つまり、２つの内の１つの場合、ｔ＝１、４つの内の１つ、ｔ＝２、および８つの内の１つの場合、ｔ＝３等々である。さらに、ｍ個の基数のための制約が立候補をますます許容できないものとする。どのような場合であっても、結合された係数は、決定的にＧＱ２技術の部分を形成する。つまり、ＧＱ２係数の型は、決して動的認証およびデジタル符号プロトコルに影響を及ぼさない。
【００９２】
図４は、素因数ｐが９（ｍｏｄ  １６）に一致する、つまりｋ≧３だけではなく、ｔ＝３、ｕ＝０でもあるサイクル内のＧi＝ｇi2  を図解する。
【数１３】
0004772189.tif 000014
【数１４】
0004772189.tif 000015
【数１５】
0004772189.tif 000016
に注意する。
【００９３】
図５は、素因数ｐが６５（ｍｏｄ  １２８）に一致する、つまりｋ＝４および
ｕ＝２だけではなく、ｔ＝６でもある分岐上のＧi＝ｇi2を図解する。
【００９４】
ここでは、ｖ＝６４，ｍ＝３を示し、３つの基数ｇ1＝３，ｇ2＝５、ｇ3＝７を示すｋ＝６、および、２つが３（ｍｏｄ  ４）に一致し、１つが５（ｍｏｄ  ８）に一致する３つの素因数が指定される係数であるｆ＝３である鍵ＧＱ２の第１の集合がある。ｇ＝２が５（ｍｏｄ  ８）に一致する素因数とは相容れないことを注意しなければならない。
【表１】
0004772189.tif 000017
【００９５】
以下は、５（ｍｏｄ  ８）に一致するｐ3に関係する構成要素のそれ以外に考えられる値である。
【００９６】
以下は、ＣＧ（ｐ3）内の−１の平方根である。つまり、ｃ＝２(p3-1)/4（ｍｏｄ  ｐ3）＝
【表２】
0004772189.tif 000018
【００９７】
以下は、ｋ＝９、つまりｖ＝  ５１２、ｍ＝２、つまり２つの基数  ｇ1＝２  およびｇ2＝３、および３（ｍｏｄ  ４）に一致する３つの素因数のある係数を示すｆ＝３のある鍵ＧＱ２の第２集合である。
【表３】
0004772189.tif 000019
【００９８】
本発明は、ＧＱ鍵の集合、つまり係数ｎおよび指数ｖが２kに等しい、それぞれ公開値Ｇと秘密値Ｑの組の生産のための方法を説明してきた。鍵のこれらの集合は、エンティティの真正性、および／または説明されたようにメッセ−ジの完全性および／または真正性を証明するように作られる方法を実現するために使用される。フランステレコム、TDFおよびMath RiZK社によって同日に提出され、その発明者がLouis  GuillouおよびJean−Jacques  Quisquaterである係属出願において、エンティティの真正性、および／またはメッセ−ジの完全性および／または真正性を証明するように設計された方法、システムおよびデバイスの特徴的な特色が主張された。これらの２つの出願は、引用することにより本明細書の一部をなすものとする。
【図１】
0004772189.tif 000020
【図２】
0004772189.tif 000021
【図３】
0004772189.tif 000022
【図４】
0004772189.tif 000023
【図５】
0004772189.tif 000024