(57)【要約】【課題】共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性を評価する。【解決手段】まず、セキュリティ処理に使用される共通多項式ａ（ｘ）の入力を受け付ける。次に、この共通多項式ａ（ｘ）に対し、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日の逆理を応用した誕生日攻撃アルゴリズムを用いて確認する。そして、この際、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、当該共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力する。【選択図】        図１
2004221895.tif 000002
【特許請求の範囲】
【請求項１】
可換な２つの離散対数問題の組み合わせにより実現されるセキュリティ処理の安全性を評価するセキュリティ評価装置において、
通信者間で共用され、前記セキュリティ処理に使用される整数係数の共通多項式の入力を受け付ける共通多項式入力手段と、
前記共通多項式入力手段において入力された前記共通多項式をａ（ｘ）とし、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日の逆理を応用した衝突探索アルゴリズムである誕生日攻撃アルゴリズムを用いて確認する多項式検査手段と、
前記多項式検査手段において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、前記共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力する安全性警告手段と、
を特徴とするセキュリティ評価装置。
【請求項２】
前記誕生日攻撃アルゴリズムは、
第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第１の演算結果と、
第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第２の演算結果とが一致した場合に、
ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断するアルゴリズムであること、
を特徴とする請求項１記載のセキュリティ評価装置。
【請求項３】
前記誕生日攻撃アルゴリズムは、
第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第１の演算結果と、
第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第２の演算結果とが一致し、
前記第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、前記第２の初期値とが一致することなく、
前記第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、前記第１の初期値とが一致することがなかった場合に、
ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断するアルゴリズムであること、
を特徴とする請求項１記載のセキュリティ評価装置。
【請求項４】
通信者間で共用される整数係数の共通多項式の変数を第１の整数だけ加算した該多項式の演算を行い、該加算演算結果に対し、第２の整数を指数とする指数演算を行い、さらに該指数演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合によって剰余演算した結果を、通信者間で交換することにより、秘密情報の送信を行うセキュリティ装置において、
前記共通多項式の入力を受け付ける共通多項式入力手段と、
前記共通多項式入力手段において入力された前記共通多項式をａ（ｘ）とし、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、前記イデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日の逆理を応用した衝突探索アルゴリズムである誕生日攻撃アルゴリズムを用いて確認する多項式検査手段と、
前記多項式検査手段において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、前記共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力する安全性警告手段と、
前記安全性警告手段によって前記警告情報が出力された場合、前記共通多項式の再設定を行う共通多項式設定手段と、
を有することを特徴とするセキュリティ装置。
【請求項５】
前記誕生日攻撃アルゴリズムは、
第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第１の演算結果と、
第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第２の演算結果とが一致し、
前記第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、前記第２の初期値とが一致することなく、
前記第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、前記第１の初期値とが一致することがなかった場合に、
ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断するアルゴリズムであること、
を特徴とする請求項４記載のセキュリティ装置。
【請求項６】
可換な２つの離散対数問題の組み合わせにより実現されるセキュリティ処理の安全性を評価するセキュリティ評価方法において、
通信者間で共用され、前記セキュリティ処理に使用される整数係数の共通多項式の入力を受け付ける共通多項式入力ステップと、
前記共通多項式入力ステップにおいて入力された前記共通多項式をａ（ｘ）とし、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日の逆理を応用した衝突探索アルゴリズムである誕生日攻撃アルゴリズムを用いて確認する多項式検査ステップと、
前記多項式検査ステップにおいて、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、前記共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力する安全性警告ステップと、
を特徴とするセキュリティ評価方法。
【請求項７】
前記誕生日攻撃アルゴリズムは、
第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第１の演算結果と、
第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第２の演算結果とが一致し、
前記第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、前記第２の初期値とが一致することなく、
前記第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、前記第１の初期値とが一致することがなかった場合に、
ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断するアルゴリズムであること、
を特徴とする請求項６記載のセキュリティ方法。
【請求項８】
請求項１から３の何れに記載されたセキュリティ評価装置としてコンピュータを機能させるためのセキュリティプログラム。
【請求項９】
請求項４或いは５の何れかに記載されたセキュリティ装置としてコンピュータを機能させるためのセキュリティプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、可換な２つの離散対数問題の組み合わせを利用したセキュリティ処理の安全性を評価するセキュリティ評価装置、セキュリティ装置、セキュリティ評価方法、及びセキュリティプログラムに関し、特に、通信者間で共用される共通多項式の安全性を確認することにより、セキュリティ処理の安全性を評価するセキュリティ評価装置、セキュリティ装置、セキュリティ評価方法、及びセキュリティプログラムに関する。
【０００２】
【従来の技術】
従来、離散対数問題の整数論的な問題の困難性に基づく暗号プリミティブとしてＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式が提唱されてきた。
まず、この従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式による鍵配送手順について説明する。なお、以下の説明において、甲乙間は、安全でない通信回線によって結ばれているものとする。
鍵の配送を行う場合、甲は、まず、擬似乱数生成装置を用いてあるＮ以下の整数ａを定め、このａを通信回線を介して乙に送信する。次に、甲は、擬似乱数生成装置を用いてある整数ｓを定めた後、整数演算装置を用いてｂ＝ａｓｍｏｄＮを計算し、整数ｓを秘密に保ったまま、計算したｂを乙に送信する。
これに対し、乙は、擬似乱数生成装置を用いてある整数ｔを定めた後、整数演算装置を用いてｃ＝ａｔｍｏｄＮを計算し、整数ｓを秘密に保ったまま、計算したｃを甲に送信する。また、乙は、整数演算装置を用い、甲から送信されたｂから、鍵ｋ＝ｂｔｍｏｄＮを求める。
【０００３】
一方、甲は、整数演算装置を用い、乙から送信されたｃから、鍵ｋ＝ｃｓｍｏｄＮを求める。
ここで、乙が求めた鍵ｋは、ｋ＝ｂｔｍｏｄＮ＝ａｓｔｍｏｄＮとなり、甲が求めた鍵ｋ＝ｃｓｍｏｄＮ＝ａｓｔｍｏｄＮと一致することになる。これにより、甲乙間で、共通鍵ｋの配送が行われたことになる。
しかし、従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式では、ｂ及びｃの計算に必要な四則演算の回数が、秘密パラメータであるｓ、ｔの大きさに依存して増大してしまい、秘密パラメータｓ、ｔを大きくした場合、鍵配送時、暗号・復号時における計算量が増大し、実用面での利便性に問題があるという課題があった。一方、秘密パラメータｓ、ｔの値が十分大きくない場合、高速指数計算法等の攻撃アルゴリズムを用いることにより、第三者が比較的容易にｋを計算できることが知られており、この場合、安全性に問題が生じるという課題もあった。特に、電子商取引やモバイルバンキング等が一般的になりつつある昨今、携帯電話やＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）カード等に代表される、メモリサイズや処理能力に制限のある実装環境においても高速に動作する暗号プリミティブの実現が期待されていた。
このような中、発明者は、可換な２つの離散対数問題の組み合わせを利用した暗号プリミティブを発案し（非特許文献１参照。）、その承継人により、その特許出願が行われている（特願２００２−２４０６５７）。
【０００４】
以下に、この可換な２つの離散対数問題の組み合わせを利用した暗号プリミティブについて説明する。
この方法によって共通鍵ｋ（ｘ）の配送を行う場合、例えばまず、甲は、整数係数の多項式である共通多項式ａ（ｘ）を生成し、生成した共通多項式ａ（ｘ）を乙に送信する。
次に、甲は、整数組ｓ＝（ｓ１，ｓ２）を定め、この整数組ｓ＝（ｓ１，ｓ２）及び共通多項式ａ（ｘ）を用い、共通多項式ａ（ｘ）の変数をｓ１だけ加算した該多項式の演算結果に対し、ｓ２を指数とする指数演算を行い、該演算結果をイデアル集合Ｉによって剰余演算する（ｂ（ｘ）＝ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）。そして、この演算結果である多項式ｂ（ｘ）は、例えば、整数組ｓ＝（ｓ１，ｓ２）が秘密に保たれた状態で、乙に送信される。なお、イデアル集合Ｉとは、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合を意味する。
【０００５】
一方、乙は、整数組ｔ＝（ｔ１，ｔ２）を定め、この整数組ｔ＝（ｔ１，ｔ２）、及び甲から送信された共通多項式ａ（ｘ）を用い、上記と同様な演算を行い（ｃ（ｘ）＝ａ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）、この演算結果である多項式ｃ（ｘ）を、整数組ｔ＝（ｔ１，ｔ２）を秘密に保った状態で、甲に送信する。
乙から多項式ｃ（ｘ）が送信された甲は、この多項式ｃ（ｘ）と、保持している整数組ｓ＝（ｓ１，ｓ２）を用い、上記と同様な演算によって共通鍵を算出する（ｋ（ｘ）＝ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）。
一方、甲から多項式ｂ（ｘ）が送信された乙は、この多項式ｂ（ｘ）と、保持している整数組ｔ＝（ｔ１，ｔ２）を用い、上記と同様な演算によって共通鍵を算出する（ｋ（ｘ）＝ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）。
【０００６】
ここで、以上の演算のうち、多項式の変数を所定の整数分だけ加算した該多項式の演算（ａ（ｘ＋ｓ１），ｃ（ｘ＋ｓ１），ａ（ｘ＋ｔ１），ｂ（ｘ＋ｔ１））は、ａ（ｘ＋ｓ）＝Σｎ＝０ｄｅｇａ（１／ｎ！）（∂ｎａ（ｘ））ｓｎという一般式を用いて行うことが可能であることが知られている。この一般式が示す通り、この演算に必要な四則演算の回数は、秘密パラメータ（ｓ１やｔ１）の大きさに依存しない。したがって、秘密パラメータ（ｓ１やｔ１）の大きさを大きくした場合であっても、鍵配送時において、この演算に起因した四則演算の回数が増大することはなく、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、大幅に利便性が向上する。
また、この方法では、多項式の変数を所定の整数分だけ加算した該多項式の演算作用素からなる第１の離散対数問題と、整数指数演算作用素からなる第２の離散対数問題とからなる、可換な離散対数問題を交換することにより、共通鍵ｋ（ｘ）の配送を行うため、指数演算作用素のみによって構成される離散対数問題を交換することによって共通鍵の配送を行っていた従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、第三者がこの共通鍵の解読を行うことが大幅に困難となり、結果、共通鍵に対する安全性が大幅に向上する。
【０００７】
【非特許文献１】
山本  剛，内山  成憲，”Ａ  ｋｅｙ  ａｇｒｅｅｍｅｎｔ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ａ  ｒｉｎｇ  ｗｉｔｈ  ｍｕｔｕａｌｌｙ  ｃｏｍｍｕｔａｔｉｖｅ  ａｃｔｉｏｎｓ  ｏｆ  ｓｅｍｉ−ｇｒｏｕｐｓ”  ，「電子情報通信学会技術研究報告」，社団法人  電子情報通信学会，２００２年１１月７日発行，信学技報  Ｖｏｌ．１０２  Ｎｏ．４３６，Ｐ１５−Ｐ２０
【０００８】
【発明が解決しようとする課題】
しかし、この暗号プリミティブにおいて、攻撃者がａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）を発見した場合（ｐは素数を、ｒは自然数を意味し、上述のイデアル集合Ｉに対し、ｐｒ∈Ｉという関係が成立しているものとする。）、この暗号に対する安全性が低下してしまうという課題がある。以下にその詳細を述べる。
攻撃者にとって、上述の共通多項式ａ（ｘ）と、多項式ｂ（ｘ）＝ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩとを取得することは比較的容易であり、これらから秘密パラメータである整数組（ｓ１，ｓ２）を求めることができれば、この鍵共有方式や公開鍵暗号方式を攻撃することができる。しかし、上述のように、これらから整数組（ｓ１，ｓ２）を求めることは一般に大変困難であり、通常、その安全性に問題はない。
ところが、攻撃者がａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）を発見できた場合、この攻撃者は、ｂ’（ｘ）＝ｂ（ｘ＋ｍ−ｎ）−ｂ（ｘ）ｍｏｄＩの演算を行うことが可能となり、この式の右辺にｂ（ｘ）＝ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩを代入すると、ｂ’（ｘ）＝ａ（ｘ＋ｓ１＋（ｍ−ｎ））ｓ２−ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩとなり、さらに、ｘ＝ｎ−ｓ１とおくと、ｂ’（ｎ−ｓ１）＝ａ（ｎ＋（ｍ−ｎ））ｓ２−ａ（ｎ）ｓ２ｍｏｄＩとなる。また、ここで、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒという関係が成立しているため、ａ（ｎ）ｓ２＝ａ（ｍ）ｓ２ｍｏｄ  ｐｒ＝ａ（ｎ＋（ｍ−ｎ））ｓ２ｍｏｄ  ｐｒという関係も成立する。したがって、これらの関係とｐｒ∈Ｉにより、ｂ’（ｎ−ｓ１）＝０ｍｏｄ  ｐｒという関係も求めることができる。
【０００９】
この関係においてｕ＝ｎ−ｓ１とおくとｂ’（ｕ）＝０ｍｏｄ  ｐｒとなるが、このｂ’（ｕ）＝０ｍｏｄ  ｐｒを満たすｕの一般解は、ｕ１＋ｕ２ｐ＋ｕ３ｐ２＋…＋ｕｒｐｒ−１となることが知られており、この解は、公知のアルゴリズムを用いて比較的容易に求めることができる。つまり、ｂ’（ｕ）＝  ｂ’（ｕ１）ｍｏｄ  ｐであるためｂ’（ｕ）＝０ｍｏｄ  ｐを全数検索によって解くことによってｕ１を求めることができ、ｂ’（ｕ）＝  ｂ’（ｕ１＋ｕ２ｐ）ｍｏｄ  ｐ２であるため、ｕ１がわかれば、ｂ’（ｕ）＝０ｍｏｄ  ｐ２を全数検索によって解くことができてｕ２が求まる。この関係はその後のｕ３，ｕ４，ｕ５，…を求める場合についても同様である。したがって、この解の集合Ｕ＝［ｕ∈Ｚ／ｐｒＺ｜ｂ’（ｕ）＝０ｍｏｄ  ｐｒ］を求めることは比較的容易である。
次に、この求められた解の集合Ｕの元ｕすべてについて、総当りで、β０（ｘ）＝ｂ（ｘ＋ｕ−ｎ）ｍｏｄＩとおき、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムを用いることで、β０（ｘ）＝ａ（ｘ）ｓｍｏｄＩとなる自然数ｓを探索する。
【００１０】
Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムは、ｆ（ｘ）Ｗ０＝ｇ（ｘ）であるときに、ｆ（ｘ）ｗ＝ｇ（ｘ）となるｗを見つけるアルゴリズムであり、このアルゴリズムにおいて
【数１】
2004221895.tif 000003
と仮定した場合（ｐは十分小さな素数，ｎは自然数）、このｗの値を容易に求めることができる。つまり、ｗの一般解は、
【数２】
2004221895.tif 000004
のように表されるため、これをｆ（ｘ）ｗ＝ｇ（ｘ）に代入すると
【数３】
2004221895.tif 000005
となり、その両辺をｐｎ−１乗すると
【数４】
2004221895.tif 000006
を得る。ここで、上記の仮定を適用すると、
【数５】
2004221895.tif 000007
が得られ、その式において総当りでｗ０を求める。次に、ｇ（ｘ）＝ｆ（ｘ）ｗの両辺に
【数６】
2004221895.tif 000008
をかけると
【数７】
2004221895.tif 000009
が得られ、上記の仮定を適用すると、
【数８】
2004221895.tif 000010
が得られる。さらに、その両辺をｐｎ−２乗すると
【数９】
2004221895.tif 000011
が得られ、上記の仮定を適用することにより
【数１０】
2004221895.tif 000012
が得られる。そして、この式において総当りでｗ１を求める。その後も同様にｗ２，ｗ３，ｗ４・・を順次求めていき、最終的に解ｗを求めることができる。
【００１１】
このＰｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムによって求められた自然数ｗは、β０（ｘ）＝ｂ（ｘ＋ｕ−ｎ）ｍｏｄＩでｂ（ｘ＋ｕ−ｎ）＝ｂ（ｘ−ｓ１）ｍｏｄＩであるため、ｂ（ｘ−ｓ１）＝ａ（ｘ）ｗｍｏｄＩを満たし、さらには、ｂ（ｘ）＝ａ（ｘ＋ｓ１）ｗｍｏｄＩをも満たすように思われる。ところが、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムでは、
【数１１】
2004221895.tif 000013
という仮定を前提として解を求めているため、このような仮定が成立していない場合には、ｂ（ｘ）＝ａ（ｘ＋ｓ１）ｗｍｏｄＩは成立しない。
従って、このような（ｓ１，ｗ）の組み合わせが、必ずｂ（ｘ）＝ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩを満たすとは言い切れないが、少なくとも、このような（ｓ１，ｗ）の組み合わせを求めることにより、ｂ（ｘ）＝ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩを満たす整数組（ｓ１，ｓ２）の検索範囲を限定することは可能である。つまり、このように求められた（ｓ１，ｗ）の集合の元を、ａ（ｘ＋ｓ１）ｗ−ｂ（ｘ）ｍｏｄＩに順次代入していき、その演算結果が０となるか否かを判断し、ａ（ｘ＋ｓ１）ｗ−ｂ（ｘ）ｍｏｄＩ＝０となったときに、その（ｓ１，ｗ）を秘密パラメータである（ｓ１，ｓ２）として決定することはできる。
結局、攻撃者がａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）を発見できた場合、この攻撃者は、集合Ｚ／ｐｒＺの部分集合Ｕ＝［ｕ∈Ｚ／ｐｒＺ｜ｂ’（ｕ）＝０ｍｏｄ  ｐｒ］のみについて、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズム等を用いた検索を行うことにより、全数検索よりも容易に秘密パラメータ（ｓ１，ｓ２）を見つけ出すことができてしまう。
【００１２】
この発明はこのような点に鑑みてなされたものであり、設定された共通多項式ａ（ｘ）に対し、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を効率良く検査し、共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性を評価することが可能なセキュリティ評価装置を提供することを目的とする。
また、この発明の他の目的は、設定された共通多項式ａ（ｘ）に対し、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を効率良く検査し、共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性低下を抑制することが可能なセキュリティ装置を提供することである。
さらに、この発明の他の目的は、設定された共通多項式ａ（ｘ）に対し、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を効率良く検査し、共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性を評価することが可能なセキュリティ評価方法を提供することである。
また、この発明の他の目的は、設定された共通多項式ａ（ｘ）に対し、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を効率良く検査し、共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性を評価することが可能な機能をコンピュータに実行させるためのセキュリティプログラムを提供することである。
【００１３】
【課題を解決するための手段】
この発明では上記課題を解決するために、まず、通信者間で共用され、セキュリティ処理に使用される整数係数の共通多項式ａ（ｘ）の入力を受け付ける。次に、この共通多項式ａ（ｘ）に対し、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日の逆理を応用した衝突探索アルゴリズムである誕生日攻撃アルゴリズムを用いて確認する。そして、この際、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、当該共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力する。
この警告情報の出力により、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在し、前述のように、この共通多項式ａ（ｎ）を用い、可換な２つの離散対数問題の組み合わせることによって実現されるセキュリティ処理の安全性が低下していることを知ることができる。
【００１４】
【発明の実施の形態】
以下、この発明の実施の形態を図面を参照して説明する。
ここでは、まず、この形態の概略について説明を行い、その後、その詳細について説明を行っていく。
図１は、この形態におけるセキュリティ評価装置１の概略構成を例示した概念図である。
図１に例示するように、この例のセキュリティ装置１は、通信者間で共用され、セキュリティ処理に使用される整数係数の共通多項式５の入力を受け付ける共通多項式入力手段２、共通多項式入力手段２において入力された共通多項式をａ（ｘ）とし、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日の逆理を応用した衝突探索アルゴリズムである誕生日攻撃アルゴリズムを用いて確認する多項式検査手段３、及び多項式検査手段において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報６を出力する安全性警告手段４を有している。
【００１５】
なお、ここで、「イデアル」という用語の意味に関し、可換環Ｒの部分集合Ｉ１がイデアルであるとは、任意のｘ，ｙ∈Ｉ１についてｘ＋ｙ∈Ｉ１が成り立ち、かつ任意のｘ∈Ｒとｙ∈Ｉ１についてｘｙ∈Ｉ１が成り立つことをいう。また、上述のイデアル集合の具体例としては、例えば、整数係数の多項式がなす環のイデアルであって、δを任意の多項式ｇ（ｘ）に対して多項式ｇ（ｘ）−ｇ（ｘ−１）を対応させる作用素とし、ｄｅｇｆ（ｘ）をｆ（ｘ）の次数とした場合における、［ｆ（ｘ），  δｆ（ｘ），δ２ｆ（ｘ），…，δｄｅｇｆ（ｘ）ｆ（ｘ）］  によって生成される集合が挙げられる。
【００１６】
このセキュリティ装置１においてセキュリティ処理の安全性を評価する場合、まず、可換な２つの離散対数問題の組み合わせることによって実現されるセキュリティ処理（例えば、上述の非特許文献１参照）に利用される共通多項式５（共通多項式ａ（ｘ））を共通多項式入力手段２に入力する。入力された共通多項式ａ（ｘ）は、多項式検査手段３に送られ、そこで誕生日攻撃アルゴリズム（例えば、「Ｐａｕｌ  Ｃ．ｖａｎ  Ｏｏｒｓｃｈｏｔ，  Ｍｉｃｈａｅｌ  Ｊ．Ｗｉｅｎｅｒ，  ”Ｐａｒａｌｌｅｌ  Ｃｏｌｌｉｓｉｏｎ  Ｓｅａｒｃｈ  ｗｉｔｈ  Ｃｒｙｐｔａｎａｌｙｔｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ，”  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ，  ｖｏｌ．１２，ｐｐ．１−２８，１９９９．」参照。）を用い、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在の確認が行われる（ｐは任意の素数、ｒは自然数、（ｎ，ｍ）は整数組、Ｉはイデアル集合をそれぞれ意味し、ｐｒ∈Ｉの関係を満たす。）。ここで、この例での誕生日攻撃アルゴリズムとは、第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第１の演算結果と、第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第２の演算結果とが一致し、第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、第２の初期値とが一致することなく、第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、第１の初期値とが一致することがなかった場合に、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断するアルゴリズムである。なお、この誕生日攻撃アルゴリズムの詳細については後述する。
【００１７】
この多項式検査手段３における処理により、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断された場合、その判断結果は、安全性警告手段４に送られ、安全性警告手段４は、この共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報６を出力する。
この警告情報６により、設定した共通多項式ａ（ｘ）に、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在し、この共通多項式ａ（ｎ）を用い、可換な２つの離散対数問題の組み合わせることによって実現されるセキュリティ処理の安全性が低下していることを知ることができる。
また、この例では、誕生日攻撃アルゴリズムを用いて、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を確認するため、このａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を効率良く検査することができる。
次に、この形態の詳細について説明する。
【００１８】
図２は、セキュリティ評価装置１０のハードウェア構成を例示したブロック図である。
図２に例示するように、セキュリティ評価装置１０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：中央処理装置）１１、主記憶装置１２、外部記憶装置１３、入出力装置１４、記録媒体読書き装置１５、及びバス１６を有している。
ＣＰＵ１１は、例えば、制御装置と演算装置を有するＣＩＳＣ（Ｃｏｍｐｌｅｘ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）方式、或いはＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）方式の中央処理装置であり、図示していない発信器から供給されるクロック信号に同期し、主記憶装置１２に格納されたオペレーティングシステム、アプリケーションプログラム等の各種プログラムの実行を行い、周辺機器の制御、必要データの呼び出し、呼び出したデータの演算・加工、演算・加工後のデータのメモリへの格納、周辺機器への出力等の各種処理を行う。
【００１９】
主記憶装置１２は、例えば、ＣＰＵ１１が直接データを読み書きできる記憶装置である。主記憶装置１２には、例えば、オペレーティングシステム、アプリケーションプログラム、データ、周辺機器を制御するドライバ等が読み込まれ、ＣＰＵ１１は、この主記憶装置２２に読み込まれたオペレーティングシステム等を実行することにより、一連の処理を行う。主記憶装置１２には、例えば、半導体メモリ等の高速処理可能な記憶素子を用い、この主記憶装置１２内の物理アドレスは、ページング方式、セグメンテーション方式等の方法により、外部記憶装置１３の仮想アドレス空間に対応付けられる。
外部記憶装置１３は、例えば、磁性体が蒸着された薄い円盤を高速回転させ、この磁性体を磁気ヘッドによって磁化することでデータの記録を行うハードディスク装置等である。
入出力装置１４は、コンピュータに指示やデータを受け付け、コンピュータで処理されたデータを取り出す為の装置である。
記録媒体読書き装置１５は、例えば、フレキシブルディスク等への情報の読書き、コンパクト・ディスク等からの情報の読み出し等を行う装置である。
バス１６は、例えば、データバス、アドレスバス、コントロールバス等によって構成され、ＣＰＵ１１、主記憶装置１２、外部記憶装置１３、入出力装置１４、及び記録媒体読書き装置１５のデータ、アドレス情報、制御情報の受け渡しを行う。
【００２０】
図３の（ａ）は、図２に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ評価装置１０の処理機能を例示した機能ブロック図である。
図３の（ａ）に例示するように、この例のセキュリティ評価装置１０は、通信者間で共用され、セキュリティ処理に使用される整数係数の共通多項式の入力を受け付ける共通多項式入力手段１０ａ、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日攻撃アルゴリズムを用いて確認する多項式検査手段１０ｂ、多項式検査手段１０ｂにおいて、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力する安全性警告手段１０ｃ、誕生日攻撃アルゴリズムの処理に必要な多項式検査データを記憶する記憶手段１０ｄ、及びセキュリティ評価装置１０全体を制御する制御手段１０ｅを処理機能として有している。そして、これらの共通多項式入力手段１０ａ、多項式検査手段１０ｂ、安全性警告手段１０ｃ及び記憶手段１０ｄは、制御手段１０ｅを介し、情報の提供或いは受け取りが可能なように構成されている。
【００２１】
図３の（ｂ）は、多項式検査手段１０ｂの機能構成を例示した機能ブロック図である。
図３の（ｂ）に例示するように、多項式検査手段１０ｂは、初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り繰り返す関数演算手段１０ｂａ、第１の初期値に対し、関数演算手段１０ｂａによる演算を行った結果、所定の出力条件に達した第１の演算結果と、第２の初期値に対し、関数演算手段１０ｂａによる演算を行った結果、所定の出力条件に達した第２の演算結果と、が一致するか否かを判断する演算結果一致判断手段１０ｂｂ、第１の初期値に対して行われた関数演算手段１０ｂａによる演算結果の少なくとも１つが、第２の初期値と一致するか否かを判断する初期値一致判断手段１０ｂｃ、及び、演算結果一致判断手段１０ｂｂにおいて、第１の演算結果と第２の演算結果とが一致すると判断され、なおかつ、初期値一致判断手段１０ｂｃにおいて、第１の演算結果と第２の初期値とが一致しないと判断された場合に、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断する整数組存在判断手段１０ｂｄを有している。そして、これらの関数演算手段１０ｂａ、演算結果一致判断手段１０ｂｂ、初期値一致判断手段１０ｂｃ及び整数組存在判断手段１０ｂｄの連携により、この例の誕生日攻撃アルゴリズムの処理が実行される。
【００２２】
図４は、記憶手段１０ｄに記憶される多項式検査データ２０のデータ構成を例示した概念図である。
図４に例示するように、多項式検査データ２０は、アドレスコード２１及び記憶データ２２を有している。この例の記憶手段１０ｄは、複数の独立した記憶領域を有しており、アドレスコード２１は、この各記憶領域の先頭アドレスと一対一に対応するコードを、記憶データ２２は、各記憶領域に記憶されるデータを、それぞれ意味している。この例の場合、アドレスコード２１として、「０」「１」「２」・・・「Ｎ−１」が割り当てられており、記憶データ２２として、「ｉｎｖａｌｉｄ」が各記憶領域に記憶されている。
【００２３】
次に、この例におけるセキュリティ評価装置１０の処理の前提となる誕生日攻撃アルゴリズムの説明を行う。
図５は、この処理に用いられる誕生日攻撃アルゴリズムを説明するための概念図である。
前述のように、この例の誕生日攻撃アルゴリズムでは、第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第１の演算結果と、第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第２の演算結果とが一致し、第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、第２の初期値とが一致することなく、第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、第１の初期値とが一致することがなかった場合に、ａ（ｎ）＝ａ（ｍ）ｍｏｄｐｒを満たす整数組（ｎ，ｍ）が存在すると判断する。以下、この内容を、図５を用いて概念的に説明する。
【００２４】
まず、第１の初期値をｃ１、第２の初期値をｃ２とした場合について説明する。
初めに、第１の初期値であるｃ１を、素数ｐごとに、Ｚ／ｐｒＺからＺ／ｐｒＺへの関数として関数ａ（ｘ）ｍｏｄ  ｐｒに代入する。次に、その演算結果であるｃ１’を、さらに関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、次の演算結果ｃ１’’を得る。そして、その後も、このｃ１’’を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、次の演算結果ｃ１’’’を得るといった処理を繰り返していき、最終的にその演算結果ｃ３が所定の出力条件３０に達したものとする。
一方、同様に、第２の初期値であるｃ２を、関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、その演算結果を関数ａ（ｘ）ｍｏｄ  ｐｒに代入するといった処理を繰り返していった結果、ある時点での演算結果が衝突点３１に達したものとする。なお、ここで衝突点３１とは、異なる初期値（図５では、初期値ｃ１、ｃ２）からスタートし、上述のように演算結果を順次関数ａ（ｘ）ｍｏｄ  ｐｒに代入していった場合に、それぞれの演算結果が一致する点をいう。
【００２５】
この場合、この衝突点３１に達した以降において、各演算結果を関数ａ（ｘ）ｍｏｄ  ｐｒに代入していった演算結果は、ｃ１を初期値とした演算結果と一致することになり、最終的には、出力条件３０を満たした演算結果ｃ３に達することになる。これは、各演算結果を代入する関数は、すべてａ（ｘ）ｍｏｄ  ｐｒであるため、一端演算結果が一致すると、その後の演算結果（ａ（ｘ）ｍｏｄ  ｐｒに代入した演算結果）も当然一致することになるからである。
この性質より、異なる初期値から同様な演算を行っていき、出力条件３０を満たした演算結果が一致していた場合、これらの演算途中において、原則、衝突点が生じていたことを判断することができる。なお、「原則」とあるのは、図５に例示した第１の初期値をｃ４とし、第２の初期値をｃ５とした場合のように、出力条件３０を満たした演算結果ｃ６が一致していた場合であっても、この場合は、初期値ｃ４から始めた演算の結果の一つが、初期値ｃ５自体と一致しているだけであって、演算結果同士が一致しているわけではなく、衝突点は生じていないといえるからである。
【００２６】
従って、異なる初期値から同様な演算を行っていき、出力条件３０を満たした演算結果が一致しているか否か、ある初期値から始めた演算の結果の一つが、他の初期値自体と一致していないかを確認することによって、衝突点の有無を判定することができる。そして、この衝突点３１が生じていた場合、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断することができる。つまり、図５のように衝突点３１が生じていた場合、この衝突点３１の１つ前の演算結果ｃ１’’’’とｃ２’は、互いに異なる値であるが、それぞれをａ（ｘ）ｍｏｄ  ｐｒに代入することによって同一の値（衝突点３１）となる。そして、この場合、（ｎ，ｍ）を（ｃ１’’’’、ｃ２’）とおくとａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒの関係も満たすことになるからである。
一方、図５に例示するように、初期値をｃ７とした場合には、最終的に出力条件３０を満たす演算結果ｃ８へと達するものの、衝突点は生じておらず、このような場合には、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒの関係も満たさないと判断することができる。
また、初期値をｃ９とした場合には、演算結果の一部が再びもとの演算結果と一致し（結合点３２）、演算結果がループ状に巡回することになる。この場合、演算結果は永遠に出力条件に達することはないため、各演算結果を関数ａ（ｘ）ｍｏｄ  ｐｒに代入する回数を制限しなければ、永遠に処理が終了しないことになる。従って、実際上、このアルゴリズムでは、この各演算結果を関数ａ（ｘ）ｍｏｄ  ｐｒに代入する回数を制限しなければならない。
【００２７】
次に、この例におけるセキュリティ評価装置１０の処理動作について説明する。
図６から図８は、この形態におけるセキュリティ評価装置１０の処理動作を説明するためのフローチャートである。以下、このフローチャートを用いて、この形態におけるセキュリティ評価装置１０の処理動作を説明していく。なお、以下のフローチャートにおいて、Ｎ、Ｍ、Ｓは、予め定められた０でない自然数の定数であり、Ｐは｛２，３，５，７，・・・，ｐ０｝の素数からなる有限集合である。また、ｃ、ｋ、ｓ、ｊは、初期値を０とする変数であり、ｐはｐ∈Ｐの関係を満たすとし、そのようなすべてのｐ∈Ｐについて以下のステップを実行する。
【００２８】
ステップＳ０：
このステップでは、関数演算手段１０ｂａにおいて、ｐｒ∈Ｉを満たす自然数ｒを求める。
具体的には、ｈ（ｘ）∈Ｉとなる多項式と、ある整数ｖを設定し、自然数Ｒで、ｐＲが整数ｈ（ｖ）を割り切り、ｐＲ＋１が整数ｈ（ｖ）を割り切らないものを計算する。ｐｒ∈Ｉとｐｒ＝０ｍｏｄＩとは自明に同値の命題であるため、所定の自然数Ｒ以下の自然数ｒについて、順次ｐｒ＝０ｍｏｄＩとなるか否かを判定することで、ｐｒ∈Ｉを満たす自然数ｒを求める。
なお、整数ｖと多項式ｈ（ｘ）は、例えば、ランダムに生成される。そして、ｈ（ｘ）∈Ｉをランダムに生成する方法としては、例えば、まず、ランダムな多項式ｈ０（ｘ）を生成し、イデアルＩによるｈ０（ｘ）の剰余ｈ１（ｘ）を求め、ｈ（ｘ）＝ｈ０（ｘ）−ｈ１（ｘ）と置く方法がある。
以上のような処理により、ｐｒ∈Ｉを満たす自然数ｒが求まった場合、ステップＳ１に進む。なお、自然数ｒは小さければ小さいほど効率的で望ましいが、ｐｒ∈Ｉを満たすものであれば、機能上問題はない。
【００２９】
ステップＳ１：
このステップでは、共通多項式入力手段１０ａにおいて、共通多項式ａ（ｘ）の入力を受け付ける。この共通多項式ａ（ｘ）は、前述した可換な２つの離散対数問題の組み合わせることによって実現されるセキュリティ処理に使用される共通多項式ａ（ｘ）であり、このように入力された共通多項式ａ（ｘ）は、制御手段１０ｅを介して多項式検査手段１０ｂに送られる。
ステップＳ２：
このステップでは、関数演算手段１０ｂａにおいて、変数ｃに０を代入する。ここで、変数ｃは、図５で説明した初期値を格納する変数である。
【００３０】
ステップＳ３：
このステップでは、関数演算手段１０ｂａにおいて、記憶手段１０ｄにおける多項式検査データ２０のアドレスコード０〜Ｎ−１全ての記憶領域に「ｉｎｖａｌｉｄ」を代入し、それぞれの記憶データ２２を全て「ｉｎｖａｌｉｄ」とする。
ステップＳ４：
このステップでは、関数演算手段１０ｂａにおいて、ｃ＞Ｍか否かを判断する。ここで、Ｍとは、前述した初期値の最大値を意味し、ここで、ｃ＞Ｍでなかった場合ステップＳ５に進み、ｃ＞Ｍであった場合、処理を終了する。
【００３１】
ステップＳ５：
このステップでは、関数演算手段１０ｂａにおいて、変数ｋにｃを代入する。なお、ここで、変数ｋは、前述した関数ａ（ｘ）ｍｏｄ  ｐｒに代入する値を格納する変数であり、ここで、初期値となる値であるｃの値をこの変数ｋに代入するのは、順次、各演算結果を関数ａ（ｘ）ｍｏｄ  ｐｒに代入していく場合に、初期値であるｃの値を保存しておくためである。
ステップＳ６：
このステップでは、関数演算手段１０ｂａにおいて、変数ｓにＳを代入する。ここで、変数ｓは減算カウンタのカウンタ値を意味し、Ｓはこの減算カウンタの最大値（初期値）を意味する。なお、この減算カウンタは、初期値或いは各演算結果に関数ａ（ｘ）ｍｏｄ  ｐｒを代入した回数をカウントするものであり、前述の図５に例示したｃ９を初期値とした場合のように、演算結果がループ状に巡回し、いつまでたっても処理が終了しないという事態に備え、初期値或いは各演算結果に関数ａ（ｘ）ｍｏｄ  ｐｒを代入する回数を制限するために使用するものである。
【００３２】
ステップＳ７：
このステップでは、関数演算手段１０ｂａにおいて、ｋ’＝ａ（ｋ）ｍｏｄ  ｐｒを計算する。つまり、変数ｋの値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入する。
ステップＳ８：
このステップでは、関数演算手段１０ｂａにおいて、変数ｓを１減じる。つまり減算カウンタを１つカウントする。
ステップＳ９：
このステップでは、関数演算手段１０ｂａにおいて、ｓ＝０であるか否かを判断する。つまり、減算カウンタの値が０となり、初期値或いは各演算結果に関数ａ（ｘ）ｍｏｄ  ｐｒを代入した回数が規定値（Ｓの値）に達したか否かを判断する。ここで、ｓ＝０であった場合、ステップＳ１５に進み、現在の初期値についての検証はこれ以上行わない。一方、ｓ＝０でなかった場合には、ステップＳ１０に進む。
【００３３】
ステップＳ１０：
このステップでは、関数演算手段１０ｂａにおいて、ｋ’≦ｃか否かを判断する。
ある演算結果に関数ａ（ｘ）ｍｏｄ  ｐｒを代入した演算結果ｋ’が、それに対応する初期値ｃよりも小さかった場合、その演算結果ｋ’は、既に検証済みの何れかの初期値と一致し、その後の検証は既に終了している検証結果と同一となる。これは、このフローチャートの処理では、初期値ｃの値を０から１ずつ増加させていき（ステップＳ１５参照）、各初期値ｃに対する検証を行っていくからである。したがって、このような重複した検証処理を排除し、処理の効率を高めるため、このステップでは、ｋ’≦ｃか否かを判断し、その後の処理を選択する。具体的には、ｋ’≦ｃであった場合にはステップＳ１５に進み、現在の初期値についての検証はこれ以上行わない。一方、ｋ’≦ｃでなかった場合にはステップＳ１１に進む。
【００３４】
ステップＳ１１：
このステップでは、関数演算手段１０ｂａにおいて、ｋ’≧Ｎであるか否かを判断する。ここでｋ’≧Ｎであるとは、前述の図５における出力条件３０を満たしていないことを意味する。そして、ｋ’≧Ｎであった場合、ステップＳ１２に進み、ｋ’≧Ｎでなかった場合には、出力条件３０を満たしたものとしてステップＳ１３に進む。
ステップＳ１２：
このステップでは、関数演算手段１０ｂａにおいて、ｋにｋ’を代入する。つまり、関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果である演算結果ｋ’を、次に関数ａ（ｘ）ｍｏｄ  ｐｒに代入する対象ｋとする。その後、ステップＳ７に進む。
【００３５】
ステップＳ１３：
このステップでは、演算結果一致判断手段１０ｂｂにおいて、ｋ’＜Ｎであり、かつ記憶手段１０ｄに記憶されている多項式検査データ２０におけるアドレスコードｋ’に対応する記憶データ２２の値が「ｉｎｖａｌｉｄ」であるか否かを判断する。つまり、出力条件を満たした演算結果が、それ以前に出力条件を満たした演算結果と一致したか否かを判断する。ここで、対応する記憶データ２２の値が「ｉｎｖａｌｉｄ」であった場合、まだ一致する演算結果がないものとしてステップＳ１４に進む。一方、対応する記憶データ２２の値が「ｉｎｖａｌｉｄ」でなかった場合、一致する演算結果があるとしてステップＳ１６に進む。
【００３６】
ステップＳ１４：
このステップでは、演算結果一致判断手段１０ｂｂにおいて、記憶手段１０ｄに記憶されている多項式検査データ２０におけるアドレスコードｋ’に対応する記憶領域にｃを格納する。つまり、このアドレスコードｋ’に対応する記憶データ２２を、演算結果が出力条件を満たした初期値ｃとする。
ステップＳ１５：
このステップでは、関数演算手段１０ｂａにおいて、変数ｃに１を加算し、次の初期値での検証を開始するため、ステップＳ４に進む。
【００３７】
ステップＳ１６：
このステップでは、初期値一致判断手段１０ｂｃにおいて、変数ｊにアドレスコードｋ’の記憶データ２２の値を代入する。つまり、変数ｊに演算結果が出力条件を満たした初期値を代入する。これは、図５に例示した第１の初期値をｃ４とし、第２の初期値をｃ５とした場合のように、出力条件３０を満たした演算結果ｃ６が一致していた場合であっても、この場合は、初期値ｃ４から始めた演算の結果の一つが、初期値ｃ５自体と一致しているだけであって、演算結果同士が一致しているわけではなく、衝突点が生じていないため、このような状況を検出結果から排除する処理を行うためである。つまり、このステップでは、ステップＳ１７以下の処理において、ある初期値から始めた演算の結果の一つが、他の初期値自体と一致しているか否かを判断する処理を行うための変数代入処理を行う。
【００３８】
ステップＳ１７：
このステップでは、初期値一致判断手段１０ｂｃにおいて、ｊ’＝ａ（ｊ）ｍｏｄ  ｐｒを計算する。ある初期値から始めた演算の結果の一つが、他の初期値自体と一致しているか否かを判断するためである。
ステップＳ１８：
このステップでは、整数組存在判断手段１０ｂｄにおいて、ｊ’＝ｋ’であるか否かを判断する。ある初期値から始めた演算の結果の一つが、他の初期値自体と一致することなく、当該判断処理が終了したか否かを判断する。ここで、ｊ’＝ｋ’であった場合、ある初期値から始めた演算の結果の一つが、他の初期値自体と一致していなかったものとして、ステップＳ１９に進む。一方、ｊ’＝ｋ’でなかった場合、ある初期値から始めた演算の結果の一つが、他の初期値自体と一致していたとして、ステップＳ２０に進む。
【００３９】
ステップＳ１９：
このステップでは、安全性警告手段１０ｃにおいて、暗号の安全性低下の可能性を警告し、処理を終了する。つまり、上述の検査においてａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認されたとして、その旨の情報が、多項式検査手段１０ｂから安全性警告手段１０ｃに送られ、安全性警告手段１０ｃは、この共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力して処理を終了する。
【００４０】
ステップＳ２０：
このステップでは、初期値一致判断手段１０ｂｃにおいて、ｊ’＝ｃであるか否かを判断する。つまり、ある初期値から始めた演算の結果の一つであるｊ’が、他の初期値ｃ自体と一致したか否かを判断する。ここで、ｊ’＝ｃであった場合、ある初期値から始めた演算の結果の一つが、他の初期値自体と一致したとして、ステップＳ２１に進む、一方、ｊ’＝ｃでなかった場合、ステップＳ２２に進む。
【００４１】
ステップＳ２１：
このステップでは、関数演算手段１０ｂａにおいて、変数ｃに１を加算し、次の初期値での検証を開始するため、ステップＳ４に進む。
ステップＳ２２：
このステップでは、初期値一致判断手段１０ｂｃにおいて、ｊ’＝ｊの値を代入し、ステップＳ１６に進む。つまり、ステップＳ１７での関数ａ（ｘ）ｍｏｄｐｒの演算結果を、関数ａ（ｘ）ｍｏｄ  ｐｒに代入する対象とする。
【００４２】
このように、この形態では、共通多項式入力手段１０ａにおいて、通信者間で共用され、セキュリティ処理に使用される整数係数の共通多項式の入力を受け付け、多項式検査手段１０ｂにおいて、共通多項式入力手段１０ａにおいて入力された共通多項式をａ（ｘ）とし、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日攻撃アルゴリズムを用いて確認し、安全性警告手段１０ｃにおいて、多項式検査手段１０ａでａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力することとした。そのため、  この警告情報により、設定した共通多項式ａ（ｘ）に、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在し、この共通多項式ａ（ｎ）を用い、可換な２つの離散対数問題の組み合わせることによって実現されるセキュリティ処理の安全性が低下していることを知ることができる。
【００４３】
また、この例では、誕生日攻撃アルゴリズムを用いて、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を確認するため、このａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を効率良く検査することができる。
さらに、この警告情報が出力された場合に共通多項式ａ（ｘ）の再設定を行う構成とすることにより、通信者間で共用される整数係数の共通多項式の変数を第１の整数だけ加算した該多項式の演算を行い、該加算演算結果に対し、第２の整数を指数とする指数演算を行い、さらに該指数演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合によって剰余演算した結果を、通信者間で交換することにより、秘密情報の送信を行うセキュリティ装置（例えば、特願２００２−２４０６５７参照。）における安全性低下を抑制することが可能となる。
【００４４】
次に、上述したセキュリティ評価装置の使用例について説明する。
図９は、このセキュリティ評価装置の使用例であるセキュリティシステム５０の構成を例示した概念図である。
図９に例示するように、セキュリティシステム５０は、セキュリティ装置６０、７０によって構成されており、このセキュリティ装置６０、７０間で共通鍵の配送を行う。この例の場合、セキュリティ装置６０は、第１の離散対数問題を構成することとなる、第１の半群が作用する第１の集合の演算を行う演算手段６１、６２、及び第２の離散対数問題を構成することとなる、第２の半群が作用する第２の集合の演算を行う演算手段６３、６４、前述したセキュリティ評価装置６５、及び安全性警告手段によって警告情報が出力された場合、共通多項式の再設定を行う共通多項式設定手段６６を備えている。また、セキュリティ装置７０は、第１の離散対数問題を構成することとなる、第１の半群が作用する第１の集合の演算を行う演算手段７１、７２、及び第２の離散対数問題を構成することとなる、第２の半群が作用する第２の集合の演算を行う演算手段７３、７４を備えている。なお、ここで半群とは、例えば、空でない集合と、この集合上の結合法則を満たす演算の組をいう。
【００４５】
また、この例では、演算手段６１、６３における演算内容に関し、第１の集合に対する作用と、第２の集合に対する作用とは、交換可能であり、かつ、第１の集合に対する計算量及び前記第２の集合に対する計算量のいずれか一方の計算量は、他方の計算量よりも小さくなるように構成される。具体的には、例えば、演算手段６１は、整数係数の多項式の変数を第１の整数だけ加算した該多項式の演算を行う手段となっており、演算手段６３は、演算手段６１によって行われた演算の結果に対し、第２の整数を指数とする指数演算を行い、その演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合、によって剰余演算する手段となっている。この点、演算手段６２、６４、演算手段７１、７３、及び演算手段７２、７４の組についても同様である。
【００４６】
この例におけるセキュリティシステム５０において共通鍵ｋ（ｘ）の配送を行う場合、例えば、まず、セキュリティ装置５０は、共通多項式設定手段６６において、整数係数の多項式である共通多項式ａ（ｘ）を生成する。生成された共通多項式ａ（ｘ）は、セキュリティ評価装置６５に送られ、そこで上述した処理によって、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が、誕生日攻撃アルゴリズムを用いて確認され、ここで、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、この共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報が出力される。このように出力された警告情報は共通多項式設定手段６６に送られ、この警告情報を受けた共通多項式設定手段６６は共通多項式ａ（ｘ）の再設定を行い、同様に、セキュリティ評価装置６５において、この共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性が評価される。
【００４７】
一方、セキュリティ評価装置６５で共通多項式ａ（ｘ）を検査し、警告情報が出力されなかった場合には、当該共通多項式ａ（ｘ）は、セキュリティ装置７０に送信される。そして、例えば次に、セキュリティ装置６０は、整数組ｓ＝（ｓ１，ｓ２）を定め、この整数組ｓ＝（ｓ１，ｓ２）及び共通多項式ａ（ｘ）を用い、演算手段６１によって、共通多項式ａ（ｘ）の変数を第１の整数であるｓ１だけ加算した該多項式の演算を行い、演算手段６３によって、演算手段６１によって行われた演算の結果に対し、第２の整数であるｓ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算する（ｂ（ｘ）＝ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）。この演算結果である多項式ｂ（ｘ）は、例えば、整数組ｓ＝（ｓ１，ｓ２）が秘密に保たれた状態で、セキュリティ装置７０に送信される。
【００４８】
一方、セキュリティ装置７０は、例えば、整数組ｔ＝（ｔ１，ｔ２）を定め、この整数組ｔ＝（ｔ１，ｔ２）、及びセキュリティ装置６０から送信された共通多項式ａ（ｘ）を用い、演算手段７１によって、共通多項式ａ（ｘ）の変数を第１の整数であるｔ１だけ加算した該多項式の演算を行い、演算手段７３によって、演算手段７１によって行われた演算の結果に対し、第２の整数であるｔ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算する（ｃ（ｘ）＝ａ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）。この演算結果である多項式ｃ（ｘ）は、例えば、整数組ｔ＝（ｔ１，ｔ２）が秘密に保たれた状態で、セキュリティ装置６０に送信される。
セキュリティ装置７０から多項式ｃ（ｘ）が送信されたセキュリティ装置６０は、例えば、演算手段６２によって、多項式ｃ（ｘ）の変数を第１の整数であるｓ１だけ加算した該多項式の演算を行い、演算手段６４によって、演算手段６２によって行われた演算の結果に対し、第２の整数であるｓ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算し（ｋ（ｘ）＝ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）、共通鍵ｋ（ｘ）を求める。
【００４９】
一方、セキュリティ装置６０から多項式ｂ（ｘ）が送信されたセキュリティ装置７０は、例えば、演算手段７２によって、多項式ｂ（ｘ）の変数を第１の整数であるｔ１だけ加算した該多項式の演算を行い、演算手段７４によって、演算手段７２によって行われた演算の結果に対し、第２の整数であるｔ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算し（ｋ（ｘ）＝ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）、共通鍵ｋ（ｘ）を求める。
ここで、以上の演算手段６１、６２、７１、７２における第１の離散対数問題の演算（ａ（ｘ＋ｓ１）やａ（ｘ＋ｔ１）の演算等）は、ａ（ｘ＋ｓ）＝Σｎ＝０ｄｅｇａ（１／ｎ！）（∂ｎａ（ｘ））ｓｎという一般式を用いて行うことが可能であることが知られている。この一般式が示す通り、この演算に必要な四則演算の回数は、秘密パラメータ（ｓ１やｔ１）の大きさに依存しない。したがって、秘密パラメータ（ｓ１やｔ１）の大きさを大きくした場合であっても、鍵配送時において、この第１の離散対数問題に起因した四則演算の回数が増大することはなく、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、大幅に利便性が向上する。
【００５０】
また、この例では、第１の離散対数問題と、第２の離散対数問題と、を組み合わせることにより、共通鍵ｋ（ｘ）の配送を行うため、単一の離散対数問題を交換することによって共通鍵の配送を行っていた従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、第三者がこの共通鍵の計算を行うことが大幅に困難となり、結果、共通鍵に対する安全性が大幅に向上する。
さらに、この例では、共通多項式設定手段６６で設定した共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性をセキュリティ評価装置６５で検証し、そこで警告情報が出力されなかった場合にのみ、この共通多項式ａ（ｘ）を共通鍵ｋ（ｘ）の配送に用いることとしたため、共通鍵ｋ（ｘ）配送時における安全性がさらに向上する。
【００５１】
図１０は、このセキュリティ評価装置の別の使用例であるセキュリティシステム１１０の構成を例示した概念図である。
図７に例示するように、セキュリティシステム１００は、セキュリティ装置１１０、１２０によって構成されており、セキュリティ装置１１０が公開した公開鍵を用い、セキュリティ装置１２０において平文の暗号化を行い、さらにセキュリティ装置１１０において、その暗号を復号する。この例の場合、セキュリティ装置１１０は、第１の離散対数問題を構成することとなる、第１の半群が作用する第１の集合の演算を行う演算手段１１１、１１２及び第２の離散対数問題を構成することとなる、第２の半群が作用する第２の集合の演算を行う演算手段１１３、１１４、前述したセキュリティ評価装置１１５、及び共通多項式設定手段１１６を備えている。また、セキュリティ装置１２０は、第１の離散対数問題を構成することとなる、第１の半群が作用する第１の集合の演算を行う演算手段１２１、１２２、及び第２の離散対数問題を構成することとなる、第２の半群が作用する第２の集合の演算を行う演算手段１２３、１２４を備えている。
【００５２】
また、この例でも、演算手段１１１、１１３における演算内容に関し、第１の集合に対する作用と、第２の集合に対する作用とは、交換可能であり、かつ、前記第１の集合に対する計算量及び前記第２の集合に対する計算量のいずれか一方の計算量は、他方の計算量よりも小さくなるように構成される。この点、演算手段１１２、１１４、演算手段１２１、１２３及び演算手段１２２、１２４の組についても同様である。
この例におけるセキュリティシステム１００において、セキュリティ装置１１０において公開鍵暗号方式による暗号化を行い、セキュリティ装置１２０においてその復号を行う場合、例えば、まず、セキュリティ装置１１０は、共通多項式設定手段１１６において、整数係数の多項式である共通多項式ａ（ｘ）を生成する。生成された共通多項式ａ（ｘ）は、セキュリティ評価装置１１５に送られ、そこで上述した処理によって、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が、誕生日攻撃アルゴリズムを用いて確認され、ここで、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、この共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報が出力される。このように出力された警告情報は共通多項式設定手段１１６に送られ、この警告情報を受けた共通多項式設定手段１１６は共通多項式ａ（ｘ）の再設定を行い、同様に、セキュリティ評価装置１１５において、この共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性が評価される。
【００５３】
一方、セキュリティ評価装置１１５で共通多項式ａ（ｘ）を検査し、警告情報が出力されなかった場合には、当該共通多項式ａ（ｘ）は、セキュリティ装置１２０に送信される。そして、次に、セキュリティ装置１１０は、秘密鍵となる整数組ｓ＝（ｓ１，ｓ２）を定め、この整数組ｓ＝（ｓ１，ｓ２）及び共通多項式ａ（ｘ）を用い、演算手段１１１によって、共通多項式ａ（ｘ）の変数を第１の整数であるｓ１だけ加算した該多項式の演算を行い、演算手段１１３によって、演算手段１１１によって行われた演算の結果に対し、第２の整数であるｓ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算する（ｂ（ｘ）＝ａ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）。この演算結果である多項式ｂ（ｘ）は、例えば、整数組ｓ＝（ｓ１，ｓ２）が秘密に保たれた状態で、公開鍵としてセキュリティ装置１２０に送信される。
【００５４】
一方、暗号化する平文Ｍが、Ｍ∈［０，１］ｌである場合、セキュリティ装置１２０は、例えば、整数組ｔ＝（ｔ１，ｔ２）を定め、セキュリティ装置１１０から送信された多項式ｂ（ｘ）とこの整数組ｔ＝（ｔ１，ｔ２）とを用い、演算手段１２１によって、多項式ｂ（ｘ）の変数を第１の整数であるｔ１だけ加算した該多項式の演算を行い、演算手段１２３によって、演算手段１２１によって行われた演算の結果に対し、第２の整数であるｔ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算する（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）。その後、この演算結果に対し、ハッシュ関数Ｈ（演算結果の値域が十分大きい集合となることが好ましく、この値域が、例えば、２８０項以上程度の元からなる集合であるものがより好ましい）を作用させ、Ｈ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）∈［０，１］ｌを得る。そして、このＨ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）と平文Ｍとの排他的論理和（Ｈ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）（＋）Ｍ）を暗号文として演算する。なお、図１０及びこの例の説明において、「Ａ（＋）Ｂ」は、ＡとＢとの排他的論理和を意味するものとする。また、セキュリティ装置１２０は、整数組ｔ＝（ｔ１，ｔ２）、及びセキュリティ装置１１０から送信された共通多項式ａ（ｘ）を用い、演算手段１２２によって、共通多項式ａ（ｘ）の変数を第１の整数であるｔ１だけ加算した該多項式の演算を行い、演算手段１２４によって、演算手段１２２によって行われた演算の結果に対し、第２の整数であるｔ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算する（ｃ（ｘ）＝ａ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）。その後、このように演算されたＨ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）（＋）Ｍと、ｃ（ｘ）とは、例えば、整数組ｔ＝（ｔ１，ｔ２）が秘密に保たれた状態で、暗号文Ｃ＝（ｃ（ｘ），Ｈ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）（＋）Ｍ）として、セキュリティ装置１１０に送信される。
【００５５】
暗号文Ｃ＝（ｃ（ｘ），Ｈ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）（＋）Ｍ）が送信されたセキュリティ装置１１０は、例えば、演算手段１１２によって、このｃ（ｘ）の変数をｓ１だけ加算した該多項式の演算を行い、演算手段１１４によって、この演算の結果に対し、ｓ２を指数とする指数演算を行い、該演算結果を、前述のイデアル集合Ｉ、によって剰余演算する。そして、この演算結果に対し、セキュリティ装置１２０で用いたものと同じハッシュ関数Ｈを作用させ、Ｈ（ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）∈［０，１］ｌを得る。その後、このように得られたＨ（ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）と、暗号文ＣのＨ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）（＋）Ｍとの排他的論理和を演算する（Ｈ（ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）（＋）（Ｈ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）（＋）Ｍ））。ここで、前述した第１の実施の形態の場合と同様、ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩの演算結果と、ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩの演算結果とは同一となっているため、これらに対して同一のハッシュ関数を作用させた結果であるＨ（ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）及びＨ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩも同一となっている。そのため、Ｈ（ｃ（ｘ＋ｓ１）ｓ２ｍｏｄＩ）（＋）（Ｈ（ｂ（ｘ＋ｔ１）ｔ２ｍｏｄＩ）（＋）Ｍ）の演算結果はＭとなり、これにより、平文Ｍが復号されたことになる。
【００５６】
ここで図９の使用例で説明した通り、以上の演算手段１１１、１１２、１２１、１２２における第１の離散対数問題の演算（ａ（ｘ＋ｓ１）やａ（ｘ＋ｔ１）の演算等）は、ａ（ｘ＋ｓ）＝Σｎ＝０ｄｅｇａ（１／ｎ！）（∂ｎａ（ｘ））ｓｎという一般式を用いて行うことが可能であることが知られている。この一般式が示す通り、この演算に必要な四則演算の回数は、秘密パラメータ（ｓ１やｔ１）の大きさに依存しない。したがって、秘密パラメータ（ｓ１やｔ１）の大きさを大きくした場合であっても、暗号化或いは復号の際、この第１の離散対数問題に起因した四則演算の回数が増大することはなく、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００５７】
また、この例では、第１の離散対数問題と、第２の離散対数問題と、を組み合わせることにより、暗号化及び復号を行うため、単一の離散対数問題を用いて暗号化及び復号を行っていた従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式に比べ、暗号に対する安全性が大幅に向上する。
さらに、この例では、共通多項式設定手段６６で設定した共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性をセキュリティ評価装置６５で検証し、そこで警告情報が出力されなかった場合にのみ、この共通多項式ａ（ｘ）を暗号処理に用いることとしたため、暗号化された平文の送信時における安全性がさらに向上する。
【００５８】
また、図１１は、このセキュリティ評価装置の別の使用例であるセキュリティシステム１３０の構成を例示した概念図である。
セキュリティシステム１３０は、ネットワーク１７０で通信可能なように結ばれたセキュリティ装置１５０、１６０及び上述したセキュリティ評価装置１４０によって構成されており、セキュリティ装置１５０、１６０間において、図９に例示したような共通鍵の配送、或いは図１０に例示したような公開鍵暗号方式による暗号処理が行われる。ただし、図９や図１０に例示した使用例と相違するのは、セキュリティ評価装置１４０が、セキュリティ装置１５０、１６０と独立して構成されている点である。従って、共通鍵配送処理或いは公開鍵暗号方式による暗号処理の際、セキュリティ装置１５０又は１６０は、生成した共通多項式ａ（ｘ）を、ネットワーク１７０を介してセキュリティ評価装置１４０に送信し、そこで前述した安全性の評価を行い、それに対し、警告信号がセキュリティ評価装置１４０からネットワーク１７０を介し、セキュリティ装置１５０又は１６０に返送されてきた場合、共通多項式ａ（ｘ）の再設定を行うこととなる。
【００５９】
また、セキュリティ評価装置１４０で共通多項式ａ（ｘ）の設定も行い、前述した処理により安全性が確認された共通多項式ａ（ｘ）をセキュリティ１５０、１６０にネットワーク１７０を介して送信し、セキュリティ１５０、１６０において、この送信された共通多項式ａ（ｘ）を使用する構成としてもよい。
なお、この発明は上述の実施の形態に限定されるものではない。例えば、この形態では、第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第１の演算結果と、第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していくことにより、所定の出力条件に達した第２の演算結果とが一致し、第１の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、第２の初期値とが一致することなく、第２の初期値を関数ａ（ｘ）ｍｏｄ  ｐｒに代入し、或いは、該関数ａ（ｘ）ｍｏｄ  ｐｒの演算結果を、さらに該関数ａ（ｘ）ｍｏｄ  ｐｒに代入する処理を１回以上繰り返していった演算結果と、第１の初期値とが一致することがなかった場合に、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断することとしたが、この第１の演算結果と第２の演算結果の一致のみで、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断してもよい。この場合、多項式検査手段１０ｂは、関数演算手段１０ｂａ、演算結果一致判断手段１０ｂｂ、及び、演算結果一致判断手段１０ｂｂにおいて、第１の演算結果と第２の演算結果とが一致すると判断され場合に、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）が存在すると判断する整数組存在判断手段１０ｂｄによって構成され、誕生日攻撃アルゴリズムは、関数演算手段１０ｂａ、演算結果一致判断手段１０ｂｂ、及び整数組存在判断手段１０ｂｄの連携によって実行されることとなる。なお、この場合、図５に例示した第１の初期値をｃ４とし、第２の初期値をｃ５とした場合のように、初期値ｃ４から始めた演算の結果の一つが、初期値ｃ５自体と一致しているだけであって、演算結果同士が一致しているわけではなく、衝突点は生じていない場合も、安全性低下の警告信号が出力されることとなる。
【００６０】
また、本形態では、コンピュータ上で所定のプログラムを実行させることにより、本形態におけるセキュリティ評価装置及びセキュリティ装置を構成することとしたが、これらの処理内容の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
さらに、上述のように、上記の処理機能は、コンピュータによって実現することができる。この場合、セキュリティ評価装置又はセキュリティ装置が有すべき機能の処理内容はプログラムによって記述され、このプログラムをコンピュータで実行することにより、上記処理機能をコンピュータ上で実現することができる。
【００６１】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ＤＶＤ−ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｒｅｃｏｒｄａｂｌｅ）／ＲＷ（ＲｅＷｒｉｔａｂｌｅ）等を、光磁気記録媒体として、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｃ）等を用いることができる。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）型のサービスによって、上述の処理を実行する構成としてもよい。
なお、上記におけるプログラムとは、電子計算機に対する指令であって、一の結果を得ることができるように組合されたものをいい、その他電子計算機による処理の用に供する情報であってプログラムに準ずるものをも含むものとする。
【００６３】
【発明の効果】
以上説明したようにこの発明では、共通多項式入力手段において、通信者間で共用され、セキュリティ処理に使用される整数係数の共通多項式の入力を受け付け、多項式検査手段において、共通多項式入力手段において入力された共通多項式をａ（ｘ）とし、任意の素数をｐとし、自然数をｒとし、整数組を（ｎ，ｍ）とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を所定の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合をＩとし、ｐｒ∈Ｉとなる場合において、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を、誕生日攻撃アルゴリズムを用いて確認し、安全性警告手段において、多項式検査手段でａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在が確認された場合、共通多項式ａ（ｘ）を用いたセキュリティ処理は安全性が低いことを示す警告情報を出力することとした。そのため、設定された共通多項式ａ（ｘ）に対し、ａ（ｎ）＝ａ（ｍ）ｍｏｄ  ｐｒを満たす整数組（ｎ，ｍ）の存在を効率良く検査し、共通多項式ａ（ｘ）を用いたセキュリティ処理の安全性を評価することが可能となる。
【図面の簡単な説明】
【図１】セキュリティ評価装置の概略構成を例示した概念図。
【図２】セキュリティ評価装置のハードウェア構成を例示したブロック図。
【図３】（ａ）は、セキュリティ評価装置の処理機能を例示した機能ブロック図。（ｂ）は、多項式検査手段１０ｂの機能構成を例示した機能ブロック図。
【図４】記憶手段に記憶される多項式検査データのデータ構成を例示した概念図。
【図５】誕生日攻撃アルゴリズムを説明するための概念図。
【図６】セキュリティ評価装置の処理動作を説明するためのフローチャート。
【図７】セキュリティ評価装置の処理動作を説明するためのフローチャート。
【図８】セキュリティ評価装置の処理動作を説明するためのフローチャート。
【図９】セキュリティ評価装置の使用例であるセキュリティシステムの構成を例示した概念図。
【図１０】セキュリティ評価装置の使用例であるセキュリティシステムの構成を例示した概念図。
【図１１】セキュリティ評価装置の使用例であるセキュリティシステムの構成を例示した概念図。
【符号の説明】
１、１０、６５、１１５、１４０  セキュリティ評価装置
２、１０ａ  共通多項式入力手段
３、１０ｂ  多項式検査手段
４、１０ｃ  安全性警告手段
６０、７０、１１０、１２０、１５０、１６０  セキュリティ装置
【図１】
2004221895.tif 000014
【図２】
2004221895.tif 000015
【図３】
2004221895.tif 000016
【図４】
2004221895.tif 000017
【図５】
2004221895.tif 000018
【図６】
2004221895.tif 000019
【図７】
2004221895.tif 000020
【図８】
2004221895.tif 000021
【図９】
2004221895.tif 000022
【図１０】
2004221895.tif 000023
【図１１】
2004221895.tif 000024