(57)【要約】【課題】従来Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムと呼ばれる方法を利用した楕円暗号解読法が適用できなかった楕円曲線（楕円暗号）に対してもＷｅｉｌｄｅｓｃｅｎｔアルゴリズムを適用できるようにする。【解決手段】楕円暗号パラメータとその公開鍵の暗号安全性強度評価を行う楕円暗号安全性強度評価装置であって、所定の楕円暗号パラメータとその公開鍵とを入力する入力手段４０１と、楕円暗号パラメータとその公開鍵とを超楕円暗号パラメータとその公開鍵とに変換する計算手段４０４と、超楕円暗号パラメータとその公開鍵とを高次代数曲線暗号パラメータとその公開鍵とに変換する計算手段４０５と、高次代数曲線暗号パラメータとその公開鍵とに基づき、秘密鍵を計算する計算手段４０６と、計算結果を出力する出力手段４０７とを備えたことを特徴とする。【選択図】        図３
2004226706.tif 000002
【特許請求の範囲】
【請求項１】
楕円暗号パラメータの暗号安全性強度評価を行う楕円暗号安全性強度評価方法であって、
所定の楕円暗号パラメータを入力する入力工程と、
上記入力工程により入力された所定の楕円暗号パラメータに対する公開鍵をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に計算させる第１の計算工程と、
上記入力工程により入力された所定の楕円暗号パラメータと上記第１の計算工程により計算された公開鍵とを、超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換し、変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを記憶装置に記憶する第１の変換工程と、
上記第１の変換工程により変換され、記憶装置に記憶された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換し、変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とを上記記憶装置に記憶する第２の変換工程と、
上記第２の変換工程により変換され、記憶装置に記憶された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づいて、上記入力工程により入力された所定の楕円暗号パラメータに対する秘密鍵を上記ＣＰＵに計算させる第２の計算工程と、
上記第２の計算工程により計算された結果を出力する出力工程と
を備えたことを特徴とする楕円暗号安全性強度評価方法。
【請求項２】
楕円暗号パラメータの暗号安全性強度評価を行う楕円暗号安全性強度評価装置であって、
所定の楕円暗号パラメータを入力する入力部と、
上記入力部により入力された所定の楕円暗号パラメータに対する公開鍵を計算する第１の計算部と、
上記入力部により入力された所定の楕円暗号パラメータと上記第１の計算部により計算された公開鍵とを、超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換する第１の変換部と、
上記第１の変換部により変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換する第２の変換部と、
上記第２の変換部により変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づいて、上記入力部により入力された所定の楕円暗号パラメータに対する秘密鍵を計算する第２の計算部と、
上記第２の計算部により計算された結果を出力する出力部と
を備えたことを特徴とする楕円暗号安全性強度評価装置。
【請求項３】
楕円暗号パラメータと上記楕円暗号パラメータの公開鍵の暗号安全性強度評価を行う楕円暗号安全性強度評価方法であって、
所定の楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを入力する入力工程と、
上記入力工程により入力された楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換し、変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを記憶装置に記憶する第１の変換工程と、
上記第１の変換工程により変換され、記憶装置に記憶された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換し、変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とを上記記憶装置に記憶する第２の変換工程と、
上記第２の変換工程により変換され、記憶装置に記憶された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づき、秘密鍵をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に計算させる計算工程と、
上記計算工程により計算された結果を出力する出力工程と
を備えたことを特徴とする楕円暗号安全性強度評価方法。
【請求項４】
楕円暗号パラメータと上記楕円暗号パラメータの公開鍵の暗号安全性強度評価を行う楕円暗号安全性強度評価装置であって、
所定の楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを入力する入力部と、
上記入力部により入力された楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換する第１の変換部と、
上記第１の変換部により変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換する第２の変換部と、
上記第２の変換部により変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づき、秘密鍵を計算する計算部と、
上記計算部により計算された結果を出力する出力部と
を備えたことを特徴とする楕円暗号安全性強度評価装置。
【請求項５】
上記所定の楕円暗号パラメータは、楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）とから定まる楕円暗号パラメータ（ｃ１１，ｃ１２，ｃ１３，ｚ１１，ｔ１１）であり、
上記所定の楕円暗号パラメータの公開鍵は、上記楕円曲線Ｃ１を満たす点Ｐ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）である場合に、
上記第１の変換工程は、
式（Ｉ）：（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２−１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３と、式（ＩＩ）：（Ｕ−２）α２＋４α＋Ｕ＋２＝０との両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）（但し、ｕは平方剰余）を計算する第３の計算工程と、
上記第３の計算工程により計算された値Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）に対して、変数Ｚ３とＴ３との方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３と、上記方程式Ｃ３を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵とを計算する計算する第４の計算工程と、
上記第３の計算工程により計算された値Ｕを用いて、Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する第５の計算工程と、
上記第５の計算工程により計算された値ｓ１とｓ２と、上記第３の計算工程により計算された値Δ，Ｕとを用いて、変数Ｚ３，Ｔ３の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する第６の計算工程と、
上記第６の計算工程により計算された方程式Ｃ４に基づいて定まる超楕円暗号の超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵を計算する第７の計算工程と
を有することを特徴とする請求項１記載の楕円暗号安全性強度評価方法。
【請求項６】
上記所定の楕円暗号パラメータは、楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）とから定まる楕円暗号パラメータ（ｃ１１，ｃ１２，ｃ１３，ｚ１１，ｔ１１）であり、
上記所定の楕円暗号パラメータの公開鍵は、上記楕円曲線Ｃ１を満たす点Ｐ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）である場合に、
上記第１の変換部は、
式（Ｉ）：（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２  −１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３と、式（ＩＩ）：（Ｕ−２）α２＋４α＋Ｕ＋２＝０との両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）（但し、ｕは平方剰余）を計算する第３の計算部と、
上記第３の計算部により計算された値Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）に対して、変数Ｚ３とＴ３との方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３と、上記方程式Ｃ３を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵とを計算する計算する第４の計算部と、上記第３の計算部により計算された値Ｕを用いて、Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する第５の計算部と、
上記第５の計算部により計算された値ｓ１とｓ２と、上記第３の計算部により計算された値Δ，Ｕとを用いて、変数Ｚ３，Ｔ３の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する第６の計算部と、
上記第６の計算部により計算された方程式Ｃ４に基づいて定まる超楕円暗号の超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵を計算する第７の計算部と
を有することを特徴とする請求項２記載の楕円暗号安全性強度評価装置。
【請求項７】
上記所定の楕円暗号パラメータは、楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）とから定まる楕円暗号パラメータ（ｃ１１，ｃ１２，ｃ１３，ｚ１１，ｔ１１）であり、
上記所定の楕円暗号パラメータの公開鍵は、上記楕円曲線Ｃ１を満たす点Ｐ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）である場合に、
上記第１の変換工程は、
式（Ｉ）：（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２  −１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３と、式（ＩＩ）：（Ｕ−２）α２＋４α＋Ｕ＋２＝０との両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）（但し、ｕは平方剰余）を計算する第３の計算工程と、
上記第３の計算工程により計算された値Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）に対して、変数Ｚ３とＴ３との方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３と、上記方程式Ｃ３を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵とを計算する計算する第４の計算工程と、
上記第３の計算工程により計算された値Ｕを用いて、Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する第５の計算工程と、
上記第５の計算工程により計算された値ｓ１とｓ２と、上記第３の計算工程により計算された値Δ，Ｕとを用いて、変数Ｚ３，Ｔ３の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する第６の計算工程と、
上記第６の計算工程により計算された方程式Ｃ４に基づいて定まる超楕円暗号の超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵を計算する第７の計算工程と
を有することを特徴とする請求項３記載の楕円暗号安全性強度評価方法。
【請求項８】
上記所定の楕円暗号パラメータは、楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）とから定まる楕円暗号パラメータ（ｃ１１，ｃ１２，ｃ１３，ｚ１１，ｔ１１）であり、
上記所定の楕円暗号パラメータの公開鍵は、上記楕円曲線Ｃ１を満たす点Ｐ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）である場合に、
上記第１の変換部は、
式（Ｉ）：（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２  −１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３と、式（ＩＩ）：（Ｕ−２）α２＋４α＋Ｕ＋２＝０との両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）（但し、ｕは平方剰余）を計算する第３の計算部と、
上記第３の計算部により計算された値Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）に対して、変数Ｚ３とＴ３との方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３と、上記方程式Ｃ３を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵とを計算する計算する第４の計算部と、上記第３の計算部により計算された値Ｕを用いて、Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する第５の計算部と、
上記第５の計算部により計算された値ｓ１とｓ２と、上記第３の計算部により計算された値Δ，Ｕとを用いて、変数Ｚ３，Ｔ３の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する第６の計算部と、
上記第６の計算部により計算された方程式Ｃ４に基づいて定まる超楕円暗号の超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵を計算する第７の計算部と
を有することを特徴とする請求項４記載の楕円暗号安全性強度評価装置。
【請求項９】
楕円暗号パラメータの暗号安全性強度評価を行う処理をコンピュータに実行させるためのプログラムであって、
所定の楕円暗号パラメータを入力する入力処理と、
上記入力処理により入力された所定の楕円暗号パラメータに対する公開鍵をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に計算させる第１の計算処理と、
上記入力処理により入力された所定の楕円暗号パラメータと上記第１の計算処理により計算された公開鍵とを、超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換し、変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを記憶装置に記憶する第１の変換処理と、
上記第１の変換処理により変換され、記憶装置に記憶された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換し、変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とを上記記憶装置に記憶する第２の変換処理と、
上記第２の変換処理により変換され、記憶装置に記憶された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づいて、上記入力処理により入力された所定の楕円暗号パラメータに対する秘密鍵を上記ＣＰＵに計算させる第２の計算処理と、
上記第２の計算処理により計算された結果を出力する出力処理と
をコンピュータに実行させるためのプログラム。
【請求項１０】
楕円暗号パラメータの暗号安全性強度評価を行う処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
所定の楕円暗号パラメータを入力する入力処理と、
上記入力処理により入力された所定の楕円暗号パラメータに対する公開鍵をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に計算させる第１の計算処理と、
上記入力処理により入力された所定の楕円暗号パラメータと上記第１の計算処理により計算された公開鍵とを、超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換し、変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを記憶装置に記憶する第１の変換処理と、
上記第１の変換処理により変換され、記憶装置に記憶された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換し、変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とを上記記憶装置に記憶する第２の変換処理と、
上記第２の変換処理により変換され、記憶装置に記憶された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づいて、上記入力処理により入力された所定の楕円暗号パラメータに対する秘密鍵を上記ＣＰＵに計算させる第２の計算処理と、
上記第２の計算処理により計算された結果を出力する出力処理と
をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
本発明は、従来安全性強度評価が困難であった楕円暗号パラメータ（及びその公開鍵）の安全性強度評価を行う方法、及びその方法を用いた演算装置に関する。
【０００２】
【従来の技術】
従来技術として、楕円曲線間の同種写像を用いて、楕円曲線離散対数問題を別の楕円曲線離散対数問題に変換する方法が述べられている（非特許文献１参照）。
また、楕円曲線上の加法及び超楕円曲線ヤコビアンの加法の算法について、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムに必要とされる一般の（平面）代数曲線ヤコビアンの加法の算法が実現可能であるとした記載が示されている。（非特許文献２参照）
また、非特許文献３には、埋め込み写像についての記載がある。しかし、その論文においては、暗号応用は全く意識されていない。
また、一般には、種数が小さい超楕円曲線ヤコビアン離散対数問題を効率的に解くアルゴリズムは見つかっていないが、ある特別な超楕円曲線ヤコビアン離散対数問題を効率的に解くアルゴリズム（解読アルゴリズム）として、種数１，標数２の場合のある特定の楕円曲線に対して、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムが有効な楕円暗号が示されている。（例えば、非特許文献７参照）
【０００３】
【非特許文献１】
Ｓ．Ｄ．Ｇａｌｂｒａｉｔｈ，Ｆ．Ｈｅｓｓ，Ｎ．Ｐ．Ｓｍａｒｔ，”Ｅｘｔｅｎｄｉｎｇ  ｔｈｅ  ＧＨＳ  Ｗｅｉｌ  Ｄｅｓｃｅｎｔ  Ａｔｔａｃｋ”、プレプリント、ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／
【非特許文献２】
Ｅ．Ｊ．Ｖｏｌｃｈｅｃｋ，  ”Ｃｏｍｐｕｔｉｎｇ  ｉｎ  ｔｈｅＪａｃｏｂｉａｎ  ｏｆ  ａ  Ｐｌａｎｅ  Ａｌｇｅｂｒａｉｃ  Ｃｕｒｖｅ”ＵＣＬＡ  Ｄｅｐｔ．  ｏｆ  Ｍａｔｈｅｍａｔｉｃｓ  ａｎｄ  Ｃｅｎｔｅｒ  ｆｏｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ａｒｔ
【非特許文献３】
Ｐ．Ｒ．Ｂｅｎｄｉｎｇ，”Ｃｕｒｖｅｓ  ｏｆ  ｇｅｎｕｓ  ２  ｗｉｔｈ  √２  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ”，ｈｔｔｐ：／／ｗｗｗ．ｍａｔｈ．ｕｉｕｃ．ｅｄｕ／Ａｌｇｅｂｒａｉｃ−Ｎｕｍｂｅｒ−Ｔｈｅｏｒｙ／
【非特許文献４】
Ｍ．Ｍａｕｒｅｒ，Ａ．Ｍｅｎｅｚｅｓ，Ｅ．Ｔｅｓｋｅ，”Ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅ  Ｗｅｉｌ  Ｄｅｓｃｅｎｔ  Ａｔｔａｃｋ  ｏｎ  ｔｈｅ  ＥＣＤＬＰ  ｏｖｅｒ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ  Ｔｗｏ  Ｆｉｎｉｔｅ  Ｆｉｅｌｄｓ  ｏｆ  Ｃｏｍｐｏｓｉｔｅ  Ｄｅｇｒｅｅ”、Ｄｅｐｔ．  ｏｆ  Ｃｏｍｂｉｎａｔｏｒｉｃｓ  ａｎｄ  Ｏｐｔｉｍｉｚａｔｉｏｎ，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｗａｔｅｒｌｏｏ、ＡＭＳ  ＳｐｅｃｉａｌＳｅｓｓｉｏｎ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ  ２００１
【非特許文献５】
Ａ．Ｍｅｎｅｚｅｓ，Ｍ．Ｑｕ，”Ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅＷｅｉｌ  Ｄｅｓｃｅｎｔ  Ａｔｔａｃｋ  ｏｆ  Ｇａｕｄｒｙ，  Ｈｅｓｓａｎｄ  Ｓｍａｒｔ”、Ｄｅｐｔ．  ｏｆ  Ｃｏｍｂｉｎａｔｏｒｉｃｓ  ａｎｄ  Ｏｐｔｉｍｉｚａｔｉｏｎ，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｗａｔｅｒｌｏｏ，Ｃａｎａｄａ、Ｃｒｙｐｔｏｇｒａｐｈｅｒ’    Ｔｒａｃｋ  ａｔ  ＲＳＡ  Ｃｏｎｆｅｒｅｎｃｅ  ２００１
【非特許文献６】
Ｓ．Ｄ．Ｇａｌｂａｒａｉｔｈ，Ｆ．Ｈｅｓｓ，Ｎ．Ｐ．Ｓｍａｒｔ”Ｅｘｔｅｎｄｉｎｇ  ｔｈｅ  ＧＨＳ  Ｗｅｉｌ  Ｄｅｓｃｅｎｔ  Ａｔｔａｃｋ”、Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｂｒｉｓｔｏｌ、Ｕｎｉｔｅｄ  Ｋｉｎｇｄｏｍ
【非特許文献７】
Ａ．Ｍｅｎｅｚｅｓ，Ｍ．Ｑｕ，”Ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅＷｅｉｌ  Ｄｅｓｃｅｎｔ  Ａｔｔａｃｋ  ｏｆ  Ｇａｕｄｒｙ，  Ｈｅｓｓａｎｄ  Ｓｍａｒｔ”Ｃｒｙｐｔｏｇｒａｐｈｅｒ’    Ｔｒａｃｋ  ａｔ  ＲＳＡ  Ｃｏｎｆｅｒｅｎｃｅ  ２００１
【０００４】
【発明が解決しようとする課題】
従来の楕円暗号に対するＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムは、一般には、その同種類の中に、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムが有効な楕円曲線Ｃ２を見つけ出すことができない楕円曲線Ｃ１が存在した。よって、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムが有効でない楕円曲線Ｃ１が多く存在した。このことは、楕円暗号パラメータ（及びその公開鍵）の安全性強度を評価する方法、及び演算方法がまだ不十分であることを示しており、現在、暗号解読法を拡充した、より正確な暗号安全性強度評価方法、及び評価演算装置が求められていた。特に、より多くの楕円曲線に対して有効なＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムを利用した解読方法、乃至演算装置の発明が必要とされていた。
【０００５】
近年の高度情報通信技術の実用化に伴い、楕円暗号を含む公開鍵暗号も既に実用化段階に入っているが、その安全性は理論的仮定に拠っており、絶対的なものでない。また、暗号の安全性強度評価は、暗号解読を遂行することによって行われることが多く、暗号解読技術の進展は暗号の安全性強度を評価する上で、必要不可欠のものとなっている。
【０００６】
本発明は従来のＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムをより広いクラスの楕円暗号に適用可能にすることで、安全性強度評価法の向上を図ることを目的とする。
【０００７】
本発明の目的は、従来のＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムを利用した解読法が適用できなかった楕円曲線（楕円暗号）に対してもＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムを適用できるようにし、より正確な楕円暗号安全性強度評価方法、及び評価演算方法を提供することにある。
【０００８】
【課題を解決するための手段】
この発明の楕円暗号安全性強度評価方法は、楕円暗号パラメータの暗号安全性強度評価を行う楕円暗号安全性強度評価方法であって、
所定の楕円暗号パラメータを入力する入力工程と、
上記入力工程により入力された所定の楕円暗号パラメータに対する公開鍵をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に計算させる第１の計算工程と、
上記入力工程により入力された所定の楕円暗号パラメータと上記第１の計算工程により計算された公開鍵とを、超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換し、変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを記憶装置に記憶する第１の変換工程と、
上記第１の変換工程により変換され、記憶装置に記憶された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換し、変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とを上記記憶装置に記憶する第２の変換工程と、
上記第２の変換工程により変換され、記憶装置に記憶された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づいて、上記入力工程により入力された所定の楕円暗号パラメータに対する秘密鍵を上記ＣＰＵに計算させる第２の計算工程と、
上記第２の計算工程により計算された結果を出力する出力工程と
を備えたことを特徴とする。
【０００９】
【発明の実施の形態】
実施の形態１．
まず、公開鍵暗号、離散対数問題および超楕円暗号について簡単に説明する。公開鍵暗号通信においては、利用者ごとに秘密鍵ｘと公開鍵ｙの組が用意され、秘密鍵ｘは、各利用者が秘密に保持しておく。公開鍵ｙは利用者自身以外の一般に公開する。利用者Ｂが利用者Ａに秘密にデータを送りたい時は、利用者Ｂは利用者Ａに対応する公開鍵ｙを用いてデータを暗号化する。この暗号文は、秘密鍵ｘを知る利用者Ａにしか復号できない。
離散対数問題とは代数群Ｇ（加法が定義されているものとする）の２つの要素ｇ１，ｇ２に対して、ｇ１＝ｍｇ２を満たすようなｍを求める問題である。代数群Ｇの要素の数が大きい場合、多くの離散対数問題を解くことは、計算量的に非常に困難になることが知られている。この事実を利用して公開鍵暗号を設計することができる。
離散対数型公開鍵暗号は多く、代数群Ｇを定める式とｇ２を公開鍵暗号パラメータとし、ｇ１をその公開鍵、ｍをその秘密鍵とする。
有限体ＧＦ（ｑｎ）（ｑは素数ｐのべき乗）上の種数ｇの超楕円曲線Ｃとは、ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）（ｈ（ｘ），ｆ（ｘ）はそれぞれＧＦ（ｑｎ）係数の高々ｇ次及び、２ｇ＋１次多項式。かつ、ｆ（ｘ）は最高次の係数が１）と表される方程式である。また、Ｃのヤコビ多様体（ヤコビアン）の有理点集合には加法が定義され、群となる。特に、種数ｇが１の時の超楕円曲線を楕円曲線といい、その場合は、楕円曲線自体に加法が定義されている。これらの群を利用した公開鍵暗号を超楕円暗号（ｇ＝１の時は、楕円暗号）という。
つまり、楕円暗号の場合には、方程式ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）の係数とその上の点（ｘ０，ｙ０）が楕円暗号パラメータとなり、楕円曲線上の加算に従って計算される（ｘ１，ｙ１）（（ｘ１，ｙ１）は、（ｘ１，ｙ１）＝ｍ・（ｘ０，ｙ０）を満たす）がその公開鍵、ｍがその秘密鍵となる。
また、種数ｇの超楕円暗号、または高次代数曲線暗号の場合は、方程式ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）、または方程式ｇ（ｘ，ｙ）＝０の係数がその暗号パラメータの一部であることは同様であるが、その他に、暗号パラメータとして、その曲線のヤコビアン上の点（その曲線上の因子類）Ｄ１が必要であり、ヤコビアン上の加算に従って計算されるＤ２（Ｄ２は、Ｄ２＝ｍ・Ｄ１を満たす）がその公開鍵、ｍがその秘密鍵となる。
以上から、超楕円曲線ヤコビアン群の離散対数問題（超楕円曲線ヤコビアン離散対数問題）を効率的に解くアルゴリズムは、超楕円暗号を解読するアルゴリズムになる。一般には、種数が小さい超楕円曲線ヤコビアン離散対数問題を効率的に解くアルゴリズムは見つかっていないが、ある特別な超楕円曲線ヤコビアン離散対数問題を効率的に解くアルゴリズム（解読アルゴリズム）として、例えば、種数１，標数２の場合のある特定の楕円曲線に対して、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムが有効であることが示されている（非特許文献７）。しかし、一般の場合にその解読法が有効な超楕円暗号はまだ決定されていない。
【００１０】
図１は、実施の形態１における楕円暗号安全性強度評価装置の外観を示す図である。
図１において、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）表示装置４１、キーボード（Ｋ／Ｂ）４２、マウス４３、コンパクトディスク装置（ＣＤＤ）８６、プリンタ装置８７、スキャナ装置８８は、パーソナルコンピュータ（ＰＣ）３３にケーブルで接続されている。
【００１１】
図２は、実施の形態１における楕円暗号安全性強度評価装置のハードウェア構成図である。
図２において、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３７は、バス３８を介してＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３９、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）４０、ＣＲＴ表示装置４１、Ｋ／Ｂ４２、マウス４３、通信ボード４４、ＦＤＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）４５、磁気ディスク装置４６、ＣＤＤ８６、プリンタ装置８７、スキャナ装置８８と接続されている。通信ボード４４は、インターネット３０に接続されている。
ここで、通信ボード４４は、インターネット３０に限らず、ＬＡＮ（ローカルエリアネットワーク）、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されていても構わない。
磁気ディスク装置４６には、オペレーティングシステム（ＯＳ）４７、ウィンドウシステム４８、プログラム群４９、ファイル群５０が記憶されている。プログラム群４９は、ＣＰＵ３７、ＯＳ４７、ウィンドウシステム４８により実行される。
【００１２】
図３は、本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
図において、楕円暗号安全性強度評価装置の一例である演算装置は、入力手段４０１、記憶手段４０２、有限体計算手段４０３、計算手段４０４，４０５，４０６、出力手段４０７、装置全体を制御する制御手段４０８を備えている。
本装置は、拡大体上定められた楕円暗号パラメータ、及びその公開鍵の暗号安全性強度評価を行う。言いかえれば、楕円暗号安全性強度評価装置は、楕円暗号パラメータと上記楕円暗号パラメータの公開鍵との暗号安全性強度評価を行う。まず、楕円曲線Ｃ１の定義式Ｔ２＝Ｚ３＋ｃ１Ｚ２＋ｃ２Ｚ＋ｃ３（ｃｉはＧＦ（ｑｎ）の元）とＣ１上の２点Ｐ１１＝（ｚ１１，ｔ１１），Ｐ１２＝ｄ・Ｐ１１＝（ｚ１２，ｔ１２）（ｚ１１，ｚ１２，ｔ１１，ｔ１２∈ＧＦ（ｑｎ））が入力手段４０１に入力される。ｄは任意の定数である。言いかえれば、入力装置は、拡大体上定められた楕円暗号パラメータ、及びその公開鍵を入力する。すなわち、入力部の一例として入力手段４０１は、所定の楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを入力する。ここでは、Ｃ１とＰ１１とが楕円暗号パラメータの一例である。Ｐ１２が公開鍵の一例である。
この装置では、楕円曲線離散対数ｄ０が計算される。まず、計算手段４０４において、種数ｇ超楕円曲線Ｃ２：Ｔ２＝Ｚ２ｇ＋１＋ｃ１Ｚ２ｇ＋．．．＋ｃ２ｇ＋１（ｃｉはＧＦ（ｑｎ）の元）と、Ｃ１からＣ２のヤコビアンへの準同型写像φによる２点Ｐ１１，Ｐ１２の準同型像φ（Ｐ１１）＝Ｄ１１＝（ｕ１１，ｖ１１），φ（Ｐ１２）＝Ｄ１２＝（ｕ１２，ｖ１２）（ｕ１１，ｕ１２，ｖ１１，ｖ１２∈ＧＦ（ｑｎ）［Ｚ］，ｕｉｊは次数ｇ、ｖｉｊは次数ｇ−１以下で最高次係数は１，ｉ，ｊ＝１，２）が計算される。各計算は有限体計算手段４０３（ここでは、例えば、ＣＰＵ３７）を用いて計算される。計算されたＣ２，Ｄ１１，Ｄ１２は、記憶手段４０２（ここでは、例えば、ＲＡＭ４０）に記憶される。言いかえれば、演算装置は、その楕円暗号パラメータ、及びその公開鍵を、超楕円暗号パラメータ、及びその公開鍵に変換する。すなわち、第１の変換部の一例として、計算手段４０４は、上記入力部により入力された楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換する。ここでは、Ｃ２，Ｄ１１が超楕円暗号パラメータ、Ｄ１２が超楕円暗号パラメータの公開鍵の一例となる。ここで、準同型像φとは、例えば、ある値Ｑ１，Ｑ２が存在するとき、φ（Ｑ１＋Ｑ２）＝φ（Ｑ１）＋φ（Ｑ２）が成り立つφをいう。すなわち、公開鍵と秘密鍵との関係を一定に保てる関係になる。
次に、計算手段４０５において、Ｃ２からＷｅｉｌ  ｄｅｓｃｅｎｔで得られる曲線Ｃ３：ｇ（Ｘ，Ｙ）＝０とＤ２ｊ＝Ｎｏｒｍ［Ｃ３Ｋ／Ｃ３］・Ｃｏｎｏｒｍ［Ｃ３Ｋ／Ｃ２］（Ｄ１ｊ）（ｊ＝１，２，但し、Ｋ＝ＧＦ（ｑｎ））が計算される。ここで、ｇ（ｘ，ｙ）は関数を表わす。また、Ｄ２ｊ＝Ｎｏｒｍ［Ｃ３Ｋ／Ｃ３］・Ｃｏｎｏｒｍ［Ｃ３Ｋ／Ｃ２］（Ｄ１ｊ）は曲線Ｃ２上の因子Ｄ１ｊを曲線Ｃ３Ｋ上の因子に写像し、次にこの曲線Ｃ３Ｋ上の因子を曲線Ｃ３上の因子Ｄ２ｊに写像することを示す。同様に、各計算は有限体計算手段４０３を用いて計算される。計算されたＣ３，Ｄ２１，Ｄ２２は記憶手段４０２に記憶される。言いかえれば、演算装置は、その超楕円暗号パラメータ、及びその公開鍵を高次代数曲線暗号パラメータ、及びその公開鍵に変換する。すなわち、第２の変換部の一例として、計算手段４０５は、上記第１の変換部により変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換する。ここでは、Ｃ３，Ｄ２１が高次代数曲線暗号パラメータ、Ｄ２２が高次代数曲線暗号パラメータの公開鍵の一例となる。
次に、計算手段４０６において、高種数代数曲線ヤコビアン離散対数アルゴリズムを用いて、Ｄ２２＝ｄ０・Ｄ２１となるｄ０が計算され、Ｐ１２＝ｄ０・Ｐ１１となることが確認される。同様に、各計算は有限体計算手段４０３を用いて計算される。計算されたｄ０は記憶手段４０２に記憶される。言いかえれば、演算装置は、その高次代数曲線暗号パラメータ、及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する。そして、入力された楕円暗号パラメータ及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する。すなわち、計算部の一例として、計算手段４０６は、上記第２の変換部により変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づき、秘密鍵を計算する。ここでは、ｄ０が高次代数曲線暗号パラメータの公開鍵に対する秘密鍵であり、同様に、入力手段４０１において入力された楕円暗号パラメータの公開鍵に対する秘密鍵となり得る。
最後に、上記Ｐ１２＝ｄ０・Ｐ１１が確認されると、“安全でない”が出力され、確認されなければ“安全である”が出力される。言いかえれば、出力部の一例として、出力手段４０７は、上記第２の計算部により計算された結果を出力する。すなわち、上記Ｐ１２＝ｄ０・Ｐ１１が確認されると入力手段４０１において入力された楕円暗号パラメータ（ｃｉにより決まるＣ１とＣ１を満たす点Ｐ１１）では、暗号が解読されてしまうことを意味する。ここで、結果の一例として、Ｐ１２＝ｄ０・Ｐ１１の計算式、“安全でない”、“安全である”の文字情報等が挙げられるがこれに限るものではない。入力手段４０１において入力された楕円暗号パラメータと楕円暗号パラメータの公開鍵とが“安全でない”か“安全である”かが判断できる情報であれば構わない。
制御装置の一例として、制御手段４０８は、上記各構成を制御する。
【００１３】
以上のように、一旦、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムが適用しやすい種数ｇ超楕円暗号に変換してから、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムにより解読できる高次代数曲線暗号に変換することにより、従来Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムによる効率的解読法が知られていなかった楕円曲線離散対数問題に対して効率的解読法を得ることが可能になる。
【００１４】
図４は、本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）方法を示したフローチャートである。
図において、まず、楕円曲線Ｃ１の定義式Ｔ２＝Ｚ３＋ｃ１Ｚ２＋ｃ２Ｚ＋ｃ３（ｃｉはＧＦ（ｑｎ）の元）とＣ１上の２点Ｐ１１＝（ｚ１１，ｔ１１），Ｐ１２＝ｄ・Ｐ１１＝（ｚ１２，ｔ１２）（ｚ１１，ｚ１２，ｔ１１，ｔ１２∈ＧＦ（ｑｎ））が入力される。
Ｓ（ステップ）３０１は、種数ｇ超楕円曲線Ｃ２：Ｔ２＝Ｚ２ｇ＋１＋ｃ１Ｚ２ｇ＋．．．＋ｃ２ｇ＋１（ｃｉはＧＦ（ｑｎ）の元）と、Ｃ１からＣ２のヤコビアンへの準同型写像φによる２点Ｐ１１，Ｐ１２の準同型像φ（Ｐ１１）＝Ｄ１１＝（ｕ１１，ｖ１１），φ（Ｐ１２）＝Ｄ１２＝（ｕ１２，ｖ１２）（ｕ１１，ｕ１２，ｖ１１，ｖ１２∈ＧＦ（ｑｎ）［Ｚ］，ｕｉｊは次数ｇ、ｖｉｊは次数ｇ−１以下で最高次係数は１，ｉ，ｊ＝１，２）を計算するステップである。
Ｓ３０２は、Ｃ２からＷｅｉｌ  ｄｅｓｃｅｎｔで得られる曲線Ｃ３：ｇ（Ｘ，Ｙ）＝０とＤ２ｊ＝Ｎｏｒｍ［Ｃ３Ｋ／Ｃ３］・Ｃｏｎｏｒｍ［Ｃ３Ｋ／Ｃ２］（Ｄ１ｊ）（ｊ＝１，２，但し、Ｋ＝ＧＦ（ｑｎ））を計算するステップである。
Ｓ３０３は、高種数代数曲線ヤコビアン離散対数アルゴリズムを用いて、Ｄ２２＝ｄ０・Ｄ２１となるｄ０を計算し、Ｐ１２＝ｄ０・Ｐ１１となることを確認するステップであり、確認されると“安全でない”が出力され、確認されなければ“安全である”が出力される。
【００１５】
次に動作を説明する。楕円離散対数問題の種数ｇ超楕円曲線ヤコビアン離散対数問題への変換を含むＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムによる楕円曲線離散対数問題解読法を図３に基づいて説明する。楕円曲線Ｃ１の定義式Ｔ２＝Ｚ３＋ｃ１Ｚ２＋ｃ２Ｚ＋ｃ３を表す配列（ｃ１，ｃ２，ｃ３）（但し、ｃｉはＧＦ（ｑｎ）の元）と２点Ｐ１１，Ｐ１２を表す配列（ｚ１，ｔ１，ｚ２，ｔ２）がまず入力される。各ステップにおける演算は全て有限体ＧＦ（ｐ）上の多項式の演算を含む有限体ＧＦ（ｐ）上の演算となる。
この方法の演算は、従来Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムによる効率的解読法が知られていなかった楕円曲線離散対数問題に対して効率的解読法を得ることを可能にする。
【００１６】
以上のように、本実施の形態における楕円暗号パラメータの暗号安全性強度評価を行う方法は、拡大体上定められた楕円暗号パラメータと上記楕円暗号パラメータの公開鍵との暗号安全性強度評価を行う方法、すなわち、楕円暗号安全性強度評価方法であって、
所定の楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを入力する入力工程と、
その楕円暗号パラメータ、及びその公開鍵を、超楕円暗号パラメータ、及びその公開鍵に変換する方法を有することと、すなわち、上記入力工程により入力された楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換し、変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを記憶装置に記憶する第１の変換工程と、
その超楕円暗号パラメータ、及びその公開鍵を高次代数曲線暗号パラメータ、及びその公開鍵に変換する方法を有することと、すなわち、上記第１の変換工程により変換され、記憶装置に記憶された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換し、変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とを上記記憶装置に記憶する第２の変換工程と、
その高次代数曲線暗号パラメータ、及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する方法を有することと、すなわち、上記第２の変換工程により変換され、記憶装置に記憶された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づき、秘密鍵をＣＰＵに計算させる計算工程と、
それらの方法を制御する方法を用いることにより、入力された楕円暗号パラメータ、及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する方法を有する、すなわち、上記計算工程により計算された結果を出力する出力工程とを備えたことを特徴とする拡大体上定められた楕円暗号パラメータの暗号安全性強度評価を行う方法である。
【００１７】
本実施の形態においては、一般に、楕円曲線離散対数問題を種数ｇの超楕円曲線ヤコビアン離散対数問題に変換して、楕円暗号を解読することが中心的なアイデアとなっている。
【００１８】
実施の形態２．
実施の形態２では、上記実施の形態１（図４）の入力部前処理として、公開鍵生成演算装置を挿入することで、公開鍵を除いた楕円暗号パラメータ自体の安全性強度評価演算装置を得ることができるようにした。
図５は、本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
図において、楕円暗号安全性強度評価装置の一例である演算装置は、入力手段８０１、公開鍵生成演算装置の一例である計算手段８０２、記憶手段４０２、有限体計算手段４０３、計算手段４０４，４０５，４０６、出力手段４０７、装置全体を制御する制御手段４０８を備えている。
演算装置は、拡大体上定められた楕円暗号パラメータの暗号安全性強度評価を行う。言いかえれば、楕円暗号安全性強度評価装置は、楕円暗号パラメータの暗号安全性強度評価を行う。
まず、楕円曲線Ｃ１の定義式Ｔ２＝Ｚ３＋ｃ１Ｚ２＋ｃ２Ｚ＋ｃ３（ｃｉはＧＦ（ｑｎ）の元）とＣ１上の点Ｐ１１＝（ｚ１１，ｔ１１）（ｚ１１，ｔ１１∈ＧＦ（ｑｎ））が入力手段８０１に入力される。言いかえれば、入力装置は、拡大体上定められた楕円暗号パラメータを入力とする。すなわち、入力部の一例として、入力手段４０１は、所定の楕円暗号パラメータを入力する。ここでは、ｃｉとＰ１１が楕円暗号パラメータの一例である。
計算手段８０２は、Ｃ１上のランダム点Ｐ１２＝ｄ・Ｐ１１＝（ｚ１２，ｔ１２）（ｚ１２，ｔ１２∈ＧＦ（ｑｎ））を生成する。言いかえれば、演算装置は、その楕円暗号パラメータに関する公開鍵を計算する。すなわち、第１の計算部の一例として、計算手段８０２は、上記入力部により入力された所定の楕円暗号パラメータに対する公開鍵Ｐ１２を計算する。ここでは、Ｐ１２が公開鍵の一例である。この装置では、楕円曲線離散対数ｄ０が計算される。まず、計算手段４０４において、種数ｇ超楕円曲線Ｃ２：Ｔ２＝Ｚ２ｇ＋１＋ｃ１Ｚ２ｇ＋．．．＋ｃ２ｇ＋１（ｃｉはＧＦ（ｑｎ）の元）と、Ｃ１からＣ２のヤコビアンへの準同型写像φによる２点Ｐ１１，Ｐ１２の準同型像φ（Ｐ１１）＝Ｄ１１＝（ｕ１１，ｖ１１），φ（Ｐ１２）＝Ｄ１２＝（ｕ１２，ｖ１２）（ｕ１１，ｕ１２，ｖ１１，ｖ１２∈ＧＦ（ｑｎ）［Ｚ］，ｕｉｊは次数ｇ、ｖｉｊは次数ｇ−１以下で最高次係数は１，ｉ，ｊ＝１，２）が計算される。各計算は有限体計算手段４０３（ここでは、例えば、ＣＰＵ３７）を用いて計算される。計算されたＣ２，Ｄ１１，Ｄ１２は、記憶手段４０２（ここでは、例えば、ＲＡＭ４０）に記憶される。言いかえれば、演算装置は、その楕円暗号パラメータ、及びその公開鍵を、超楕円暗号パラメータ、及びその公開鍵に変換する。すなわち、第１の変換部の一例として、計算手段４０４は、上記入力部により入力された所定の楕円暗号パラメータと上記第１の計算部により計算された公開鍵とを、超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換する。ここでは、実施の形態１と同様に、Ｃ２，Ｄ１１が超楕円暗号パラメータ、Ｄ１２が超楕円暗号パラメータの公開鍵の一例である。
次に、計算手段４０５において、Ｃ２からＷｅｉｌ  ｄｅｓｃｅｎｔで得られる曲線Ｃ３：ｇ（Ｘ，Ｙ）＝０とＤ２ｊ＝Ｎｏｒｍ［Ｃ３Ｋ／Ｃ３］・Ｃｏｎｏｒｍ［Ｃ３Ｋ／Ｃ２］（Ｄ１ｊ）（ｊ＝１，２，但し、Ｋ＝ＧＦ（ｑｎ））が計算される。同様に、各計算は有限体計算手段４０３を用いて計算される。計算されたＣ３，Ｄ２１，Ｄ２２は記憶手段４０２に記憶される。言いかえれば、演算装置は、その超楕円暗号パラメータ、及びその公開鍵を高次代数曲線暗号パラメータ、及びその公開鍵に変換する。すなわち、第２の変換部の一例として、計算手段４０５は、上記第１の変換部により変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換する。ここでは、実施の形態１と同様に、Ｃ３，Ｄ２１が高次代数曲線暗号パラメータ、Ｄ２２が高次代数曲線暗号パラメータの公開鍵の一例である。
次に、計算手段４０６において、高種数代数曲線ヤコビアン離散対数アルゴリズムを用いて、Ｄ２２＝ｄ０・Ｄ２１となるｄ０が計算され、Ｐ１２＝ｄ０・Ｐ１１となることが確認される。同様に、各計算は有限体計算手段４０３を用いて計算される。計算されたｄ０は記憶手段４０２に記憶される。言いかえれば、演算装置は、その高次代数曲線暗号パラメータ、及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する。そして、演算装置は、入力された楕円暗号パラメータ、及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する。すなわち、第２の計算部の一例として、計算手段４０６は、上記第２の変換部により変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づいて、上記入力部により入力された所定の楕円暗号パラメータに対する秘密鍵を計算する。ここでは、実施の形態１と同様に、ｄ０が高次代数曲線暗号パラメータの公開鍵に対する秘密鍵であり、入力部により入力された所定の楕円暗号パラメータに対する秘密鍵となり得る。
最後に、上記Ｐ１２＝ｄ０・Ｐ１１が確認されると、“安全でない”が出力され、確認されなければ“安全である”が出力される。言いかえれば、出力部の一例として、出力手段４０７は、上記第２の計算部により計算された結果を出力する。すなわち、上記Ｐ１２＝ｄ０・Ｐ１１が確認されると、入力手段４０１において入力された楕円暗号パラメータ（ｃｉにより決まる式Ｃ１とＣ１を満たす点Ｐ１１）では、暗号が解読されてしまうことを意味する。
ここで、結果の一例として、Ｐ１２＝ｄ０・Ｐ１１の計算式、“安全でない”、“安全である”の文字情報等が挙げられるがこれに限るものではない。入力手段４０１において入力された楕円暗号パラメータが“安全でない”か“安全である”かが判断できる情報であれば構わない。
制御装置の一例として、制御手段４０８は、上記各構成を制御する。
【００１９】
図６は、本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）方法を示したフローチャートである。
Ｓ７０１において、まず、楕円曲線Ｃ１の定義式Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃ１ｉはＧＦ（ｑｎ）の元）とＣ１上の点Ｐ１１＝（ｚ１１，ｔ１１）（ｚ１１，ｔ１１∈ＧＦ（ｑｎ））が入力される。
Ｓ７０２において、Ｃ１上のランダム点Ｐ１２＝ｄ・Ｐ１１＝（ｚ１２，ｔ１２）（ｚ１２，ｔ１２∈ＧＦ（ｑｎ））を生成する。
次に、図４におけるＳ３０１へと繋がり、Ｓ３０２、Ｓ３０３において、高種数代数曲線ヤコビアン離散対数アルゴリズムを用いて、Ｄ２２＝ｄ０・Ｄ２１となるｄ０を計算し、Ｐ１２＝ｄ０・Ｐ１１となることが確認されると“安全でない”が出力され、確認されなければ“安全である”が出力される。
【００２０】
以上のように、本実施の形態における楕円暗号パラメータの暗号安全性強度評価を行う方法は、拡大体上定められた楕円暗号パラメータの暗号安全性強度評価を行う方法、すなわち、楕円暗号安全性強度評価方法であって、
拡大体上定められた楕円暗号パラメータを入力とし、すなわち、所定の楕円暗号パラメータを入力する入力工程と、
その楕円暗号パラメータに関する公開鍵を計算する方法を有することと、すなわち、上記入力工程により入力された所定の楕円暗号パラメータに対する公開鍵をＣＰＵに計算させる第１の計算工程と、
その楕円暗号パラメータ、及びその公開鍵を、超楕円暗号パラメータ、及びその公開鍵に変換する方法を有することと、すなわち、上記入力工程により入力された所定の楕円暗号パラメータと上記第１の計算工程により計算された公開鍵とを、超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換し、変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを記憶装置に記憶する第１の変換工程と、
その超楕円暗号パラメータ、及びその公開鍵を高次代数曲線暗号パラメータ、及びその公開鍵に変換する方法を有することと、すなわち、上記第１の変換工程により変換され、記憶装置に記憶された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換し、変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とを上記記憶装置に記憶する第２の変換工程と、
その高次代数曲線暗号パラメータ、及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する方法を有することと、それら方法を制御する方法を用いることにより、入力された楕円暗号パラメータ、及びその公開鍵から定まる公開鍵暗号（離散対数問題）の秘密鍵を導出する方法を有することと、すなわち、上記第２の変換工程により変換され、記憶装置に記憶された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づいて、上記入力工程により入力された所定の楕円暗号パラメータに対する秘密鍵を上記ＣＰＵに計算させる第２の計算工程と、
上記第２の計算工程により計算された結果を出力する出力工程と
を備えたことを特徴とする拡大体上定められた楕円暗号パラメータの暗号安全性強度評価を行う方法である。
【００２１】
以上のように、公開鍵生成演算装置は、入力部前処理として、拡大体上定められた楕円暗号パラメータの公開鍵を生成することで、公開鍵を除いた楕円暗号パラメータ自体の安全性強度評価をおこなうことができる。
【００２２】
実施の形態３．
例えば、標数が２でない楕円曲線に対しては、楕円曲線離散対数問題の種数２超楕円曲線ヤコビアン離散対数問題への具体的な変換が導出できる。その変換法を利用して、その種数２曲線に対するＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムを楕円曲線離散対数問題に適用可能にすることによって、従来Ｗｅｉｌ  ｄｅｓｃｅｎｔ  アルゴリズムによる効率的解読法が知られていなかった楕円曲線離散対数問題に対して効率的解読法、及びそれを実行する演算装置を得ることができる。
【００２３】
図７、図８（図７と図８で１図を構成する。）は、本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
図において、楕円暗号安全性強度評価装置の一例である演算装置は、入力手段６０１（入力部の一例である）、計算手段６２０（第１の変換部の一例である）、計算手段６３０（第２の変換部の一例である）、計算手段６１１（計算部の一例である）、記憶手段６０２（記憶装置の一例である）、有限体計算手段６０３（ＣＰＵの一例である）、出力手段６１２（出力部の一例である）、装置全体を制御する制御手段７００を備えている。計算手段６２０は、計算手段６０４，６０５，６０６，６０８，６０９，６１０を有している。計算手段６３０は、計算手段６０７，６１３を有している。
【００２４】
楕円暗号安全性強度評価装置の一例である本装置は、拡大体上定められた（但し、例えば、有限体の標数≠２）楕円暗号パラメータと上記楕円暗号パラメータの暗号安全性強度評価を行う。
楕円曲線Ｃ１の定義式Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃ１ｉはＧＦ（ｑｎ）の元）の係数ｃ１ｉとＣ１上の２点Ｐ１１＝（ｚ１１，ｔ１１），Ｐ１２＝ｄ・Ｐ１１＝（ｚ１２，ｔ１２）（ｚ１１，ｚ１２，ｔ１１，ｔ１２∈ＧＦ（ｑｎ））が入力手段６０１に入力される。言いかえれば、入力部は、所定の楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを入力する。ここでは、ｃ１ｉとＰ１１が所定の楕円暗号パラメータ、Ｐ１２が所定の楕円暗号パラメータの公開鍵の一例となる。
この装置では、楕円曲線離散対数ｄ０が計算される。
まず、計算手段６０４において、Ｃ１と同種な曲線Ｃ２とその同種写像でＰ１１，Ｐ１２を写した２点Ｐ２１，Ｐ２２が計算される。各計算は有限体計算手段６０３を用いて計算される。計算されたＣ２，Ｐ２１，Ｐ２２は記憶手段６０２に記憶される。ここで、同種写像とは、楕円曲線間の有理式で定義された準同型写像であって、零写像でない写像をいう。
次に、計算手段６０５において、方程式（Ｉ），（ＩＩ）を満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）＊（但し、ｕは平方剰余）が計算され、更に楕円曲線Ｃ３とその曲線上の点Ｐ３１，Ｐ３２が計算される。各計算は有限体計算手段６０３を用いて計算される。計算されたΔ，Ｕ，α，ｕ，ｒ，Ｗ，Ｐ３１，Ｐ３２は記憶手段６０２に記憶される。言いかえると、演算装置は、その楕円暗号パラメータ、及びその公開鍵が楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）から定まる楕円暗号パラメータ（ｃ１１，ｃ１２，ｃ１３，ｚ１１，ｔ１１）、及びＣ１を満たすＰ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）の時に，
（Ｉ）：（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２−１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３、
（ＩＩ）：（Ｕ−２）α２＋４α＋Ｕ＋２＝０
両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）＊（但し，ｕは平方剰余）を計算する。そして、演算装置は、上記Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）＊に対して，変数Ｚ３，Ｔ３の方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３とその方程式を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵を計算する。すなわち、上記所定の楕円暗号パラメータは、楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）とから定まる楕円暗号パラメータ（ｃ１１，ｃ１２，ｃ１３，ｚ１１，ｔ１１）であり、上記所定の楕円暗号パラメータの公開鍵は、上記楕円曲線Ｃ１を満たす点Ｐ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）である場合に、第３の計算部は、式（Ｉ）：（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２−１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３と、式（ＩＩ）：（Ｕ−２）α２＋４α＋Ｕ＋２＝０との両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）（但し、ｕは平方剰余）を計算する。そして、第４の計算部は、上記第３の計算部により計算された値Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）に対して、変数Ｚ３とＴ３との方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３と、上記方程式Ｃ３を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵とを計算する。
次に、計算手段６０６において、種数２超楕円曲線Ｃ４が計算される。各計算は有限体計算手段６０３を用いて計算される。計算されたＣ４は記憶手段６０２に記憶される。言いかえると、演算装置は、Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する。そして、演算装置は、変数Ｚ４，Ｔ４の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する。すなわち、第５の計算部は、上記第３の計算部により計算された値Ｕを用いて、Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する。そして、第６の計算部は、上記第５の計算部により計算された値ｓ１とｓ２と、上記第３の計算部により計算された値Δ，Ｕとを用いて、変数Ｚ３，Ｔ３の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する。
次に、計算手段６０７において、Ｃ４からＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムを用いて曲線Ｃ５が計算される。各計算は有限体計算手段６０３を用いて計算される。計算されたＣ５は記憶手段６０２に記憶される。
次に、計算手段６０８において、Ｃ５の種数が４以上で、かつある程度小さいかが判定される（現在は４以上１０ぐらい以下であることが推奨されている）。各計算は有限体計算手段６０３を用いて計算される。もし、Ｃ５の種数が４以上でないか、または、ある程度小さくなければ（現在は４より小さいか１０より大きいことが推奨されている）、計算手段６０４に処理が引き渡される。
ｃ５の種類が４以上で、ある程度小さければ、計算手段６０９において、第一座標（Ｚ３座標）がＧＦ（ｑｎ）内で平方剰余になるＣ３上の点Ｐ４１，Ｐ４２が計算され、その値から決まるｚ５ｉｊ，ｔ５ｉｊ（ｉ，ｊ＝１，２）が計算される。各計算は有限体計算手段６０３を用いて計算される。計算されたＰ４１，Ｐ４２，ｚ５ｉｊ，ｔ５ｉｊ（ｉ，ｊ＝１，２）は記憶手段６０２に記憶される。
次に、計算手段６１０において、Ｃ４の因子類Ｄ４ｊ（ｊ＝１，２）が計算される。各計算は有限体計算手段６０３を用いて計算される。計算されたＤ４ｊ（ｊ＝１，２）は記憶手段６０２に記憶される。
言いかえれば、演算装置は、Ｃ４から定まる超楕円暗号の超楕円暗号パラメータ、及びその公開鍵を計算する。すなわち、第７の計算部は、上記第６の計算部により計算された方程式Ｃ４に基づいて定まる超楕円暗号の超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵を計算する。ここでは、計算手段６０６において計算されたＣ４と計算手段６１０において計算されたＤ４１とが超楕円暗号パラメータ、計算手段６１０において計算されたＤ４２が超楕円暗号パラメータの公開鍵の一例となる。すなわち、第１の変換部の一例としての計算手段６０４，６０５，６０６，６０９，６１０は、上記入力部により入力された楕円暗号パラメータと上記所定の楕円暗号パラメータの公開鍵とを超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とに変換する。
次に、計算手段６１３において、Ｃ４の因子類Ｄ４ｊ（ｊ＝１，２）とそれから計算されるＣ５の因子類Ｄ５ｊ（ｊ＝１，２）が計算される。各計算は有限体計算手段６０３を用いて計算される。計算されたＤ５ｊ（ｊ＝１，２）は記憶手段６０２に記憶される。すなわち、第２の変換部の一例としての計算手段６０７，６１３は、上記第１の変換部により変換された超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵とを高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに変換する。ここでは、計算手段６０７において計算されたＣ５と計算手段６１３において計算されたＤ５１とが高次代数曲線暗号パラメータ、計算手段６１３において計算されたＤ５２が高次代数曲線暗号パラメータの公開鍵の一例となる。
次に、計算手段６１１において、高種数代数曲線ヤコビアン離散対数アルゴリズムを用いて、Ｄ５２＝ｄ０・Ｄ５１となるｄ０が計算され、Ｐ１２＝ｄ０・Ｐ１１となることが確認される。各計算は有限体計算手段６０３を用いて計算される。計算されたｄ０は記憶手段６０２に記憶される。すなわち、計算部の一例としての計算手段６１１は、上記第２の変換部により変換された高次代数曲線暗号パラメータと上記高次代数曲線暗号パラメータの公開鍵とに基づき、秘密鍵を計算する。
最後に、上記Ｐ１２＝ｄ０・Ｐ１１が確認されると、“安全でない”が出力され、確認されなければ“安全である”が出力される。言いかえれば、出力部の一例としての出力手段６１２は、上記計算部により計算された結果を出力する。
以上のように、一旦、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムが適用しやすい超楕円暗号に変換してから、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムにより解読できる高次代数曲線暗号に変換することにより、例えば、標数が２でない楕円曲線に対しては、楕円曲線離散対数問題の種数２超楕円曲線ヤコビアン離散対数問題への具体的な変換が導出できる。
【００２５】
図９は本実施の形態による、楕円曲線離散対数問題を解く（楕円暗号を解読する）方法を示したフローチャートである。
図において、まず楕円曲線Ｃ１の定義式Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃ１ｉはＧＦ（ｑｎ）の元）とＣ１上の２点Ｐ１１＝（ｚ１１，ｔ１１），Ｐ１２＝ｄ・Ｐ１１＝（ｚ１２，ｔ１２）（ｚ１１，ｚ１２，ｔ１１，ｔ１２∈ＧＦ（ｑｎ））が入力される。
Ｓ５０１はＣ１と同種な曲線Ｃ２とその同種写像でＰ１１，Ｐ１２を写した２点Ｐ２１，Ｐ２２を計算するステップである。
Ｓ５０２は方程式（Ｉ），（ＩＩ）を満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）＊（但し、ｕは平方剰余）を計算し、更に楕円曲線Ｃ３とその曲線上の点Ｐ３１，Ｐ３２を計算するステップである。
Ｓ５０３は種数２超楕円曲線Ｃ４を計算するステップである。
Ｓ５０４はＣ４からＷｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムを用いて曲線Ｃ５を計算するステップである。
Ｓ５０５はＣ５の種数が４以上で、かつある程度小さいかを判定するステップ（現在は４以上１０ぐらい以下であることが推奨されている）である。
Ｓ５０６は第一座標（Ｚ３座標）がＧＦ（ｑｎ）内で平方剰余になるＣ３上の点Ｐ４１，Ｐ４２を計算し、その値から決まるｚ５ｉｊ，ｔ５ｉｊ（ｉ，ｊ＝１，２）を計算するステップである。
Ｓ５０７はＣ４の因子類Ｄ４ｊ（ｊ＝１，２）とそれから計算されるＣ５の因子類Ｄ５ｊ（ｊ＝１，２）を計算するステップである。
Ｓ５０８は高種数代数曲線ヤコビアン離散対数アルゴリズムを用いて、Ｄ５２＝ｄ０・Ｄ５１となるｄ０を計算し、Ｐ１２＝ｄ０・Ｐ１１となることを確認するステップであり、確認されると“安全でない”が出力され、確認されなければ“安全である”が出力される。
【００２６】
次に動作を説明する。Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムによる楕円曲線離散対数問題解読法を図９に基づいて説明する。楕円曲線Ｃ１の定義式Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３を表す配列（ｃ１１，ｃ１２，ｃ１３）（但し、ｃ１ｉはＧＦ（ｑｎ）の元）と２点Ｐ１１，Ｐ１２を表す配列（ｚ１１，ｔ１１，ｚ１２，ｔ１２）がまず入力される。各ステップにおける演算は全て有限体ＧＦ（ｐ）上の多項式の演算を含む有限体ＧＦ（ｐ）上の演算となる。
この方法の演算は、従来Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムによる効率的解読法が知られていなかった楕円曲線離散対数問題に対して効率的解読法を得ることを可能にする。
【００２７】
以上のように、本実施の形態における楕円暗号安全性強度評価方法は、拡大体上定められた（但し、例えば、有限体の標数≠２）楕円暗号パラメータの暗号安全性強度評価を行う方法であって、
その楕円暗号パラメータ、及びその公開鍵を、超楕円暗号パラメータ、及びその公開鍵に変換する方法が、その楕円暗号パラメータ、及びその公開鍵が、楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃ１ｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）から定まる楕円暗号パラメータ（ｃ１１，ｃ１２  ，ｃ１３，ｚ１１，ｔ１１）、及びＣ１を満たすＰ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）の時に、
すなわち、上記所定の楕円暗号パラメータは、楕円曲線Ｃ１：Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１  ２Ｚ１＋ｃ１３（ｃｉはＧＦ（ｑｎ）の元）とＣ１を満たすＰ１１＝（ｚ１１，ｔ１１）とから定まる楕円暗号パラメータ（ｃ１１，ｃ１２，ｃ１３，ｚ１１，ｔ１１）であり、
上記所定の楕円暗号パラメータの公開鍵は、上記楕円曲線Ｃ１を満たす点Ｐ１２＝（ｚ１２，ｔ１２）から定まる公開鍵（ｚ１２，ｔ１２）である場合に、
（Ｉ）（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２  −１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３、
（ＩＩ）（Ｕ−２）α２＋４α＋Ｕ＋２＝０
両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）＊（但し、ｕは平方剰余）を計算する方法を有することと、すなわち、式（Ｉ）：（Δ（α＋１）／Ｕ）（Ｚ３＋１）［−３２（４（Ｕ−３）α＋Ｕ２−Ｕ−４）（Ｚ３２−６Ｚ３＋１）＋（Ｕ−２）２（（Ｕ２−１２）α−２（Ｕ＋２））Ｗ（Ｚ３２＋１）＋２（（Ｕ４−４Ｕ３−８Ｕ２  −１６Ｕ＋１４４）α−２（Ｕ３＋６Ｕ２−２０Ｕ−２４））ＷＺ３］＝（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３と、式（ＩＩ）：（Ｕ−２）α２＋４α＋Ｕ＋２＝０との両式をＧＦ（ｑｎ）係数のＺ３を変数とする多項式として満たすΔ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）（但し、ｕは平方剰余）を計算する第３の計算工程と、
上記Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）＊に対して、変数Ｚ３，Ｔ３の方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３とその方程式を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵を計算する方法を有することと、すなわち、上記第３の計算工程により計算された値Δ，Ｕ，α，ｕ，ｒ∈ＧＦ（ｑｎ），Ｗ∈ＧＦ（ｑｎ）に対して、変数Ｚ３とＴ３との方程式Ｃ３：Ｔ３２＝（（ｕＺ３＋ｒ）３＋ｃ２１（ｕＺ３＋ｒ）２＋ｃ２２（ｕＺ３＋ｒ）＋ｃ２３）／ｕ３と、上記方程式Ｃ３を満たすパラメータＰ３１＝（ｕｚ２１＋ｒ，ｔ２１／（ｕ３／２））＝（ｚ３１，ｔ３１）により定まる楕円暗号パラメータとＰ３２＝（ｕｚ２２＋ｒ，ｔ２２／（ｕ３／２））＝（ｚ３２，ｔ３２）により定まる公開鍵とを計算する計算する第４の計算工程と、
Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する方法を有することと、すなわち、上記第３の計算工程により計算された値Ｕを用いて、Ｖ＝２として、ｓ１＝−［（Ｗ（Ｕ−Ｖ）（Ｕ＋Ｖ）＋４（Ｖ２＋４））／４Ｕ］，ｓ２＝Ｗを計算する第５の計算工程と、
変数Ｚ３，Ｔ３の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する方法を有することと、すなわち、上記第５の計算工程により計算された値ｓ１とｓ２と、上記第３の計算工程により計算された値Δ，Ｕとを用いて、変数Ｚ３，Ｔ３の方程式Ｃ４：Ｔ４２＝Δ（Ｚ４２＋ＵＺ４＋Ｖ）［Ｚ４４−ｓ１Ｚ４３＋（−（ｓ１Ｕ＋８）／Ｖ＋ｓ２）Ｚ４２＋（（２Ｕｓ２＋４ｓ１）／Ｖ）Ｚ４＋（Ｕ２ｓ２＋４ｓ１Ｕ＋１６）／Ｖ２］を計算する第６の計算工程と、
Ｃ４から定まる超楕円暗号の超楕円暗号パラメータ、及びその公開鍵を計算する方法を有すること、すなわち、上記第６の計算工程により計算された方程式Ｃ４に基づいて定まる超楕円暗号の超楕円暗号パラメータと上記超楕円暗号パラメータの公開鍵を計算する第７の計算工程と、
を備えたことにより実現される拡大体上定められた（但し、例えば、有限体の標数≠２）楕円暗号パラメータの暗号安全性強度評価を行う方法である。
【００２８】
実施の形態４．
上記実施の形態５（図７、図８（図７と図８で１図を構成する。））の入力部前処理として、公開鍵生成方法を挿入することで、楕円暗号パラメータ安全性強度評価方法を得ることができる。
図１０、図１１（図１０と図１１で１図を構成する。）は、本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
図において、楕円暗号安全性強度評価装置の一例である演算装置は、入力手段８０１、公開鍵生成演算装置の一例である計算手段８０２（第１の計算部の一例である）、計算手段６２０（第１の変換部の一例である）、計算手段６３０（第２の変換部の一例である）、計算手段６１１（第２の計算部の一例である）、記憶手段６０２（記憶装置の一例である）、有限体計算手段６０３（ＣＰＵの一例である）、出力手段６１２（出力部の一例である）、装置全体を制御する制御手段７００を備えている。計算手段６２０は、計算手段６０４，６０５，６０６，６０８，６０９，６１０を有している。計算手段６３０は、計算手段６０７，６１３を有している。
演算装置は、拡大体上定められた楕円暗号パラメータの暗号安全性強度評価を行う。言いかえれば、楕円暗号安全性強度評価装置は、楕円暗号パラメータの暗号安全性強度評価を行う。
まず、楕円曲線Ｃ１の定義式Ｔ１２＝Ｚ１３＋ｃ１１Ｚ１２＋ｃ１２Ｚ１＋ｃ１３（ｃ１ｉはＧＦ（ｑｎ）の元）とＣ１上の点Ｐ１１＝（ｚ１１，ｔ１１）（ｚ１１，ｚ１２∈ＧＦ（ｑｎ））が入力手段８０１に入力される。言いかえれば、入力装置は、拡大体上定められた楕円暗号パラメータを入力とする。すなわち、入力部の一例として、入力手段４０１は、所定の楕円暗号パラメータを入力する。ここでは、ｃ１ｉとＰ１１が楕円暗号パラメータの一例である。
計算手段８０２は、Ｃ１上のランダム点Ｐ１２＝ｄ・Ｐ１１＝（ｚ１２，ｔ１２）（ｚ１２，ｔ１２∈ＧＦ（ｑｎ））を生成する。言いかえれば、演算装置は、その楕円暗号パラメータに関する公開鍵を計算する。すなわち、第１の計算部の一例として、計算手段８０２は、上記入力部により入力された所定の楕円暗号パラメータに対する公開鍵Ｐ１２を計算する。ここでは、Ｐ１２が公開鍵の一例である。
以降の構成は、実施の形態３と同様である。
すなわち、上記Ｐ１２＝ｄ０・Ｐ１１が確認されると、入力手段４０１において入力された楕円暗号パラメータ（ｃｉにより決まる式Ｃ１とＣ１を満たす点Ｐ１１）では、暗号が解読されてしまうことを意味する。
【００２９】
以上のように、公開鍵生成演算装置は、入力部前処理として、拡大体上定められた楕円暗号パラメータの公開鍵を生成することで、実施の形態３とは異なり公開鍵を除いた楕円暗号パラメータ自体の安全性強度評価をおこなうことができる。
また、一旦、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムが適用しやすい超楕円暗号に変換してから、Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムにより解読できる超楕円暗号に変換することにより、例えば、標数が２でない楕円曲線に対しては、楕円曲線離散対数問題の種数２超楕円曲線ヤコビアン離散対数問題への具体的な変換が導出できる。
【００３０】
以上の説明において、各実施の形態の説明において「〜部」或いは「〜手段」として説明したものは、一部或いはすべてコンピュータで動作可能なプログラムにより構成することができる。これらのプログラムは、例えば、Ｃ言語により作成することができる。或いは、ＨＴＭＬやＳＧＭＬやＸＭＬを用いても構わない。或いは、ＪＡＶＡ（登録商標）を用いて画面表示を行っても構わない。
また、各実施の形態の説明において「〜部」或いは「〜手段」として説明したものは、ＲＯＭ３９に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェア或いは、ハードウェア或いは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。
また、上記各実施の形態を実施させるプログラムは、また、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体による記録装置を用いても構わない。
また、出力部は、ＣＲＴ表示装置、その他の表示装置、プリンタ装置等の出力装置を用いても構わない。
【００３１】
【発明の効果】
以上のように、本発明による演算方法は、従来Ｗｅｉｌ  ｄｅｓｃｅｎｔアルゴリズムによる効率的解読法が知られていなかった楕円曲線離散対数問題に対して効率的解読法を得ることを可能にし、多量の楕円暗号を解読することを可能にし、楕円暗号安全性強度評価方法の正確性を向上させる。
【図面の簡単な説明】
【図１】実施の形態１における楕円暗号安全性強度評価装置の外観を示す図である。
【図２】実施の形態１における楕円暗号安全性強度評価装置のハードウェア構成図である。
【図３】本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
【図４】本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）方法を示したフローチャートである。
【図５】本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
【図６】本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）方法を示したフローチャートである。
【図７】本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
【図８】図７の続きの図である。
【図９】本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）方法を示したフローチャートである。
【図１０】本実施の形態による楕円曲線離散対数問題を解く（楕円暗号を解読する）演算装置を示した図である。
【図１１】図１０の続きの図である。
【符号の説明】
３０  インターネット、３３  ＰＣ、３７  ＣＰＵ、３８  バス、３９  ＲＯＭ、４０  ＲＡＭ、４１  ＣＲＴ表示装置、４２  Ｋ／Ｂ、４３  マウス、４４通信ボード、４５  ＦＤＤ、４６  磁気ディスク装置、４７  ＯＳ、４８  ウィンドウシステム、４９  プログラム群、５０  ファイル群、８６  ＣＤＤ、８７  プリンタ装置、８８  スキャナ装置、４０１  入力手段、４０２  記憶手段、４０３  有限体計算手段、４０４，４０５，４０６  計算手段、４０７  出力手段、４０８  制御手段、６０１  入力手段、６２０  計算手段、６３０  計算手段、６０２  記憶手段、６０３  有限体計算手段、６０４，６０５，６０６，６０７，６０８，６０９，６１０，６１１  計算手段、６１２  出力手段、６１３  計算手段、６２０  計算手段、７００  制御手段、８０１  入力手段、８０２  計算手段。
【図１】
2004226706.tif 000003
【図２】
2004226706.tif 000004
【図３】
2004226706.tif 000005
【図４】
2004226706.tif 000006
【図５】
2004226706.tif 000007
【図６】
2004226706.tif 000008
【図７】
2004226706.tif 000009
【図８】
2004226706.tif 000010
【図９】
2004226706.tif 000011
【図１０】
2004226706.tif 000012
【図１１】
2004226706.tif 000013