(57)【特許請求の範囲】
【請求項１】
素数ｐを標数とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、
電子計算機で、前記平文データと前記暗号化鍵とを乗算して暗号データの元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成させる、または前記暗号データと前記復号化鍵とを乗算して平文データの元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成させる暗号化／復号化プログラムにおいて、
km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを特定する第１のステップと、
前記の２つの元Ａ，Ｂを、前記正整数ｋを用いて素数ｐを標数とする拡大次数kmの拡大体Fpkmにおける２つの元として乗算を行う第２のステップと、
この乗算の結果を用いて部分体である前記拡大次数ｍの拡大体Fpmの元における乗算の結果を求める第３のステップと
を有することを特徴とする暗号化／復号化プログラム。
【請求項２】
０≦ｉ≦m-1、０≦ｊ≦k-1とし、
<ｘ>がｘのmod(km+1)をとるものとして、
前記第２のステップは、
０≦ｔ≦k-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求めるステップと、
０≦ｉ≦kmで、それぞれ０＝q[<i>]とするステップと、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めるステップと、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて、０≦ｔ≦k-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込むステップと
を有することを特徴とする請求項１記載の暗号化／復号化プログラム。
【請求項３】
前記第３のステップは、
０≦ｉ≦m-1で、かつ１≦ｔ≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むステップと、
０≦ｉ≦m-1で、kq[<0>]-q[<pi>]＝ciをそれぞれ求めるステップと
を有することを特徴とする請求項２記載の暗号化／復号化プログラム。
【請求項４】
k=2k'の場合に、
F2k'm+1でｐが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'とし、
０≦ｉ≦m-1、０≦ｊ≦2k'-1とし、
<ｘ>がｘのmod(2k'm+1)をとるものとして、
前記第２のステップは、
０≦ｔ≦k'-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めるステップと、
０≦ｉ≦2k'mで、それぞれ０＝q[<i>]とするステップと、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めるステップと、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて、０≦ｔ≦k'-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込むとともに、q[<pi-(pjK[t])>]にＭをそれぞれ足し込むステップと
を有することを特徴とする請求項１記載の暗号化／復号化プログラム。
【請求項５】
前記第３のステップは、
０≦ｉ≦m-1で、かつ１≦ｔ≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込むステップと、
０≦ｉ≦m-1で、-q[<pi>]＝ciをそれぞれ求めるステップと
を有することを特徴とする請求項４記載の暗号化／復号化プログラム。
【請求項６】
素数ｐを標数とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、
前記平文データと前記暗号化鍵とを乗算させて元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成することにより暗号化する、または前記暗号データと前記復号化鍵とを乗算させて元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成することにより復号化する演算器を備えた暗号化／復号化装置において、
前記元をそれぞれ記憶する第１の記憶部と、
前記拡大次数ｍを記憶する第２の記憶部と、
km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを前記演算器による演算に基づいて特定して記憶する第３の記憶部と、
前記の２つの元Ａ，Ｂを、前記正整数ｋを用いて素数ｐを標数とする拡大次数kmの拡大体Fpkmにおける２つの元として前記演算器で乗算した結果を記憶する第４の記憶部と、
前記拡大次数kmの拡大体Fpkmの元の乗算結果を用いて前記演算器で所定の演算を行って、部分体である前記拡大次数ｍの拡大体Fpmの元における乗算の結果を求めて記憶する第５の記憶部と
を有することを特徴とする暗号化／復号化装置。
【請求項７】
０≦ｉ≦m-1、０≦ｊ≦k-1とし、
<ｘ>がｘのmod(km+1)をとるものとして、
前記第４の記憶部は、
０≦ｔ≦k-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
０≦ｉ≦kmで、それぞれ０＝q[<i>]として記憶する記憶部と、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めて記憶する記憶部と、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて記憶する記憶部と、
０≦ｔ≦k-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項６記載の暗号化／復号化装置。
【請求項８】
前記第５の記憶部は、
０≦ｉ≦m-1で、かつ１≦ｔ≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
０≦ｉ≦m-1で、kq[<0>]-q[<pi>]＝ciをそれぞれ求めて記憶する記憶部と
を有することを特徴とする請求項７記載の暗号化／復号化装置。
【請求項９】
k=2k'の場合に、
F2k'm+1でｐが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'として、この正整数k'を記憶する記憶部を有し、
０≦ｉ≦m-1、０≦ｊ≦2k'-1とし、
<ｘ>がｘのmod(2k'm+1)をとるものとして、
前記第４の記憶部は、
０≦ｔ≦k'-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
０≦ｉ≦2k'mで、それぞれ０＝q[<i>]として記憶する記憶部と、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めて記憶する記憶部と、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて記憶する記憶部と、
０≦ｔ≦k'-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込し込んで記憶するとともに、q[<pi-(pjK[t])>]にＭをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項６記載の暗号化／復号化装置。
【請求項１０】
前記第５の記憶部は、
０≦ｉ≦m-1で、かつ１≦ｔ≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
０≦ｉ≦m-1で、-q[<pi>]＝ciをそれぞれ求めて記憶する記憶部と
を有することを特徴とする請求項９記載の暗号化／復号化装置。
【請求項１１】
素数ｐを標数とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を乗算して元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成する演算器を備えた拡大体の乗算装置において、
前記元をそれぞれ記憶する第１の記憶部と、
前記拡大次数ｍを記憶する第２の記憶部と、
km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを前記演算器による演算に基づいて特定して記憶する第３の記憶部と、
前記の２つの元Ａ，Ｂを、前記正整数ｋを用いて素数ｐを標数とする拡大次数kmの拡大体Fpkmにおける２つの元として前記演算器で乗算した結果を記憶する第４の記憶部と、
前記拡大次数kmの拡大体Fpkmの元の乗算結果を用いて前記演算器で所定の演算を行って、部分体である前記拡大次数ｍの拡大体Fpmの元における乗算の結果を求めて記憶する第５の記憶部と
を有することを特徴とする拡大体の乗算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化／復号化プログラム、暗号化／復号化装置、及び暗号化または復号化における乗算処理を実行する拡大体の乗算装置に関する。
【背景技術】
【０００２】
従来、インターネットなどの電気通信回線を利用した情報通信において、送受信されるデータの秘匿性を保持するために、データの暗号化が行われている。すなわち、平文データを送信する送信者は、平文データに暗号化処理を施して暗号データを生成し、この暗号データを受信者に送信している。一方、暗号データを受信した受信者は、暗号データに復号化処理を施して平文データを生成することにより、平文データを受け取ることができる。【０００３】
このような暗号化及び復号化の方法として、昨今では公開鍵暗号と呼ばれる方法が用いられている。公開鍵暗号では、公開鍵と秘密鍵があらかじめ設定され、所定の平文データを送信する送信者に公開鍵を開示しており、送信者は公開鍵を用いて平文データを暗号化することにより暗号データを生成し、受信者に送信している。受信者は、暗号データを受信すると、秘密鍵を用いて暗号データを復号化して平文データを生成している。【０００４】
ここで、平文データを暗号化する場合には、平文データを暗号化に用いる公開鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長平文データを生成し、各単位長平文データと公開鍵を用いて乗算処理を行うことにより単位長暗号データを生成し、所定数の単位長暗号データで構成された暗号データを生成している。【０００５】
一方、暗号データを復号化する場合には、暗号データを復号化に用いる秘密鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長暗号データを生成し、各単位長暗号データと秘密鍵を用いて乗算処理を行うことにより単位長平文データを生成し、所定数の単位長平文データで構成された平文データを生成している。【０００６】
このような公開鍵暗号には様々な方式が提案されており、Rivest Shamir Adleman（ＲＳＡ）暗号、楕円曲線暗号、ElGamal暗号などが知られている。【０００７】
昨今、パーソナルコンピュータなどの電子計算機の性能向上にともなって、各種の暗号方法で暗号化された暗号データが解読されるおそれが高まっている。すなわち、暗号データは、秘密鍵さえ分かれば解読できることから、電子計算機によって手当たり次第に秘密鍵を生成して復号化を試みることにより、時間はかかるものの解読されるおそれがあった。【０００８】
そこで、各暗号方法では、安全性を高めるために公開鍵及び秘密鍵の鍵長を長くすることが行われている。すなわち、公開鍵及び秘密鍵の鍵長を長くすると、解読に用いる秘密鍵の数が飛躍的に増大し、現実的な時間内での解読を不可能とすることができるからである。そのため、現在では、ＲＳＡ暗号では１０２４ビット以上、楕円曲線暗号では１６０ビット以上、ElGamal暗号では１０２４ビット以上の鍵長が求められている。【０００９】
しかしながら、公開鍵及び秘密鍵の鍵長を長くした場合には、公開鍵を用いた乗算処理による暗号化、及び秘密鍵を用いた乗算処理による復号化に多大な時間を要することとなっていた。この場合、処理時間の短縮のためには、乗算処理の演算速度が高速な演算手段が必要となることにより、安全性を高めるためのコストが増大することとなっていた。【００１０】
一方で、現実的には、電気通信回線中を流れているデータにおいては重要度が様々に異なっており、利用価値が高いために高度の秘匿性が必要なデータから、利用価値が低いために秘匿性を必要としないデータまでが存在している。【００１１】
したがって、何れのデータに対しても同等の安全性で暗号化する必要はなく、高い安全性が要求されるデータには長い鍵長の公開鍵及び秘密鍵を用い、高い安全性が要求されないデータには短い鍵長の公開鍵及び秘密鍵が用いられている。【００１２】
また、パーソナルコンピュータなどのような高速な演算処理の実行が可能な装置では、できるだけ長い鍵長の公開鍵及び秘密鍵による暗号化が利用されており、携帯電話機やＩＣカードなどのような演算処理能力の乏しい装置では、比較的短い鍵長の公開鍵及び秘密鍵による暗号化が利用され、保証され得る安全性の範囲内でデータの送受信が行われている。【００１３】
特に、パーソナルコンピュータなどの電子計算機では、複数種類の鍵長の公開鍵及び秘密鍵が利用可能となっており、送信するデータに応じた安全性、あるいは送信先の装置における乗算処理の処理能力などに応じて鍵長を変えて暗号化することも行われており、鍵長に汎用性を持たせることが提案されている（例えば、特許文献１参照。）。
【特許文献１】特開２００１−０５１８３２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、通常、鍵長の決定にともなって、乗算処理などの演算処理に必要となる拡大体が、所定の拡大体に特定されてしまうために、鍵長に汎用性を持たせた場合には、鍵長ごとの拡大体をあらかじめ準備しておかなければならなかった。したがって、鍵長の汎用性を高めようとすればするほど、鍵長に対応した拡大体を記憶しておくためのより大きな記憶領域が必要となっていた。【００１５】
したがって、現実的には、準備できる記憶領域の大きさの制限から、鍵長は３〜５種類程度しか準備されておらず、必ずしも十分な汎用性が提供できてはいなかった。そのため、準備された鍵長の公開鍵及び秘密鍵では安全性が十分に保証できない状態となった場合に、安全性をさらに高めることはできなかった。【００１６】
しかも、従来の暗号化または復号化における乗算処理では、多項式積の計算の後に多項式剰余算の計算が必要であって、多項式積の計算が終了するまでは多項式剰余算の計算を開始することができなかった。したがって、このような乗算処理を演算回路を構成して実行する場合には、演算回路の並列化が困難であって、処理速度の高速化を図りにくいという問題もあった。【００１７】
本発明者らは、このような現状に鑑み、任意な鍵長を選択可能としながら高速に乗算処理を実行可能とすることにより、利便性の高い暗号化及び復号化のシステムを構築可能とするために研究を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１８】
本発明の暗号化／復号化プログラムでは、素数ｐを標数とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、電子計算機で、平文データと暗号化鍵とを乗算して暗号データの元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成させる、または暗号データと復号化鍵とを乗算して平文データの元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成させる暗号化／復号化プログラムにおいて、km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを特定する第１のステップと、２つの元Ａ，Ｂを、正整数ｋを用いて素数ｐを標数とする拡大次数kmの拡大体Fpkmにおける２つの元として乗算を行う第２のステップと、この乗算の結果を用いて部分体である拡大次数ｍの拡大体Fpmの元における乗算の結果を求める第３のステップとを有することとした。【００１９】
さらに、本発明の暗号化／復号化プログラムでは、
０≦ｉ≦m-1、０≦ｊ≦k-1とし、
<ｘ>がｘのmod(km+1)をとるものとして、
第２のステップが、
０≦ｔ≦k-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求めるステップと、
０≦ｉ≦kmで、それぞれ０＝q[<i>]とするステップと、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めるステップと、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて、０≦ｔ≦k-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込むステップと
を有することにも特徴を有するものであり、
第３のステップが、
０≦ｉ≦m-1で、かつ１≦ｔ≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むステップと、
０≦ｉ≦m-1で、kq[<0>]-q[<pi>]＝ciをそれぞれ求めるステップと
を有することにも特徴を有するものである。【００２０】
さらに、本発明の暗号化／復号化プログラムでは、
k=2k'の場合に、
F2k'm+1でｐが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'とし、
０≦ｉ≦m-1、０≦ｊ≦2k'-1とし、
<ｘ>がｘのmod(2k'm+1)をとるものとして、
第２のステップが、
０≦ｔ≦k'-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めるステップと、
０≦ｉ≦2k'mで、それぞれ０＝q[<i>]とするステップと、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めるステップと、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて、０≦ｔ≦k'-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込むとともに、q[<pi-(pjK[t])>]にＭをそれぞれ足し込むステップと
を有することにも特徴を有し、
第３のステップが、
０≦ｉ≦m-1で、かつ１≦ｔ≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込むステップと、
０≦ｉ≦m-1で、-q[<pi>]＝ciをそれぞれ求めるステップと
を有することにも特徴を有するものである。【００２１】
また、本発明の暗号化／復号化装置では、素数ｐを標数とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、平文データと暗号化鍵とを乗算させて元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成することにより暗号化する、または暗号データと復号化鍵とを乗算させて元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成することにより復号化する演算器を備えた暗号化／復号化装置において、元をそれぞれ記憶する第１の記憶部と、拡大次数ｍを記憶する第２の記憶部と、km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを演算器による演算に基づいて特定して記憶する第３の記憶部と、２つの元Ａ，Ｂを、正整数ｋを用いて素数ｐを標数とする拡大次数kmの拡大体Fpkmにおける２つの元として演算器で乗算した結果を記憶する第４の記憶部と、拡大次数kmの拡大体Fpkmの元の乗算結果を用いて演算器で所定の演算を行って、部分体である拡大次数ｍの拡大体Fpmの元における乗算の結果を求めて記憶する第５の記憶部とを有することとした。【００２２】
さらに、本発明の暗号化／復号化装置では、
０≦ｉ≦m-1、０≦ｊ≦k-1とし、
<ｘ>がｘのmod(km+1)をとるものとして、
第４の記憶部が、
０≦ｔ≦k-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
０≦ｉ≦kmで、それぞれ０＝q[<i>]として記憶する記憶部と、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めて記憶する記憶部と、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて記憶する記憶部と、
０≦ｔ≦k-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込んで記憶する記憶部と
を有することにも特徴を有し、
第５の記憶部が、
０≦ｉ≦m-1で、かつ１≦ｔ≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
０≦ｉ≦m-1で、kq[<0>]-q[<pi>]＝ciをそれぞれ求めて記憶する記憶部と
を有することにも特徴を有するものである。【００２３】
さらに、本発明の暗号化／復号化装置では、
k=2k'の場合に、
F2k'm+1でｐが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'として、この正整数k'を記憶する記憶部を有し、
０≦ｉ≦m-1、０≦ｊ≦2k'-1とし、
<ｘ>がｘのmod(2k'm+1)をとるものとして、
第４の記憶部が、
０≦ｔ≦k'-1で、<pmt>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
０≦ｉ≦2k'mで、それぞれ０＝q[<i>]として記憶する記憶部と、
０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めて記憶する記憶部と、
０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて記憶する記憶部と、
０≦ｔ≦k'-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込し込んで記憶するとともに、q[<pi-(pjK[t])>]にＭをそれぞれ足し込んで記憶する記憶部と
を有することにも特徴を有し、
第５の記憶部が、
０≦ｉ≦m-1で、かつ１≦ｔ≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
０≦ｉ≦m-1で、-q[<pi>]＝ciをそれぞれ求めて記憶する記憶部と
を有することにも特徴を有するものである。【００２４】
また、本発明の乗算装置では、素数ｐを標数とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を乗算して元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成する演算器を備えた拡大体の乗算装置において、元をそれぞれ記憶する第１の記憶部と、拡大次数ｍを記憶する第２の記憶部と、km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを演算器による演算に基づいて特定して記憶する第３の記憶部と、２つの元Ａ，Ｂを、正整数ｋを用いて素数ｐを標数とする拡大次数kmの拡大体Fpkmにおける２つの元として演算器で乗算した結果を記憶する第４の記憶部と、拡大次数kmの拡大体Fpkmの元の乗算結果を用いて演算器で所定の演算を行って、部分体である拡大次数ｍの拡大体Fpmの元における乗算の結果を求めて記憶する第５の記憶部とを有することとした。
【発明の効果】
【００２５】
本発明では、素数ｐを標数とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を乗算して元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成する際に、km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを用いて、素数ｐを標数とする拡大次数kmの拡大体Fpkmを定義体として想定して演算を行うことにより、拡大次数ｍを任意の整数とすることができる。【００２６】
すなわち、任意の拡大次数ｍを用いても、km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを用いた拡大次数kmの拡大体によって、演算に必要な拡大体を極めて容易に準備できるので、拡大次数ｍごとに対応した拡大体を準備する必要がなく、拡大次数ｍを無制限に選択することができる。【００２７】
この拡大次数ｍは、暗号化及び復号化における鍵長であって、鍵長を任意に選択することができるので、必要に応じて暗号データの安全性を任意に選択可能とすることができる。特に、安全性を高めたければ拡大次数ｍをできるだけ大きくするだけでよく、暗号データの解読行為に対して極めて容易に対応できる。【００２８】
しかも、拡大次数kmの拡大体を定義体として用いることにより、乗算を、所定の元の加算または減算と、乗算との繰り返しに分解して演算することができ、並列処理化が容易であって、高速演算を可能とすることができる。【００２９】
さらに、ｋ＝2k'となるk'を用いた場合には、所定の元の加算または減算と、乗算との繰り返し回数を削減できることにより、演算のさらなる高速化を図ることができる。
【図面の簡単な説明】
【００３０】
【図１】本発明に係る暗号化／復号化装置のブロック図である。
【図２】本発明に係る暗号化／復号化プログラムにおけるフローチャートである。
【図３】本発明に係る暗号化／復号化プログラムにおけるフローチャートである。
【図４】他の実施形態のフローチャートである。
【図５】既約多項式を求めるフローチャートである。
【符号の説明】
【００３１】
10  演算器
20  不揮発性記憶部
30  揮発性記憶部
40  データ入出力部
50  データバス
【発明を実施するための最良の形態】
【００３２】
本発明の暗号化／復号化プログラム、暗号化／復号化装置、及び拡大体の乗算装置では、素数ｐを標数とする拡大体を定義体とし、拡大次数ｍの拡大体Fpmの２つの元Ａ＝{a0,a1,a2,・・・，am-1}、Ｂ＝{b0,b1,b2,・・・，bm-1}を乗算して元Ｃ＝{c0,c1,c2,・・・，cm-1}を生成する際に、拡大次数ｍに対応し、km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを用いて素数ｐを標数とする拡大次数kmの拡大体Fpkmを新たな定義体として乗算を行い、この乗算の結果を用いて部分体である拡大次数ｍの拡大体Fpmの元における乗算の結果を求めている。【００３３】
すなわち、任意の拡大次数ｍに対応して、km+1が素数であって、Fkm+1でｐが原始元となる正整数ｋを用いることにより、素数ｐを標数とする拡大次数ｍの拡大体Fpmを部分体とする拡大次数kmの拡大体Fpkmを定義体として用いることができ、拡大次数ｍ及び標数ｐを任意としても２つの元Ａ、Ｂの乗算を行うことができる。【００３４】
ここで、拡大次数ｍは、暗号化及び復号化における鍵長に当たり、任意の拡大次数ｍが選択できるということは、鍵長を任意に選択できることを示しており、必要に応じて適宜の鍵長として暗号データを生成することができる。【００３５】
したがって、状況に応じて鍵長を選択することにより、暗号データの安全性と、暗号化及び復号化の演算の負荷をバランスさせながら適宜の鍵長とした暗号データを生成できる。【００３６】
例えば、標数ｐ＝2500−863の500ビットの素数を用いた場合には、下表に示すように、拡大次数ｍ、パラメータとなる正整数ｋ、鍵長の組み合わせを選択できる。
【表１】
0004836208.tif 000002
【００３７】
ここで、鍵長が短くなる組み合わせを用いれば、暗号化及び復号化の演算速度を向上させることができ、鍵長が長くなる組み合わせを用いれば、解読困難な暗号化データを生成して安全性を向上させることができる。【００３８】
特に、拡大次数ｍは、任意な正整数とすることができ、いくらでも大きくすることもできる。また、標数ｐも任意の素数とすることができる。【００３９】
なお、暗号化に必要となる鍵は、Diffie−Hellman鍵交換アルゴリズムを用いて受け渡すことにより、安全に受け渡すことができる。【００４０】
すなわち、アリスとボブが鍵交換を行う場合、まず、アリスからボブに鍵データとしてｇ，Ａ＝ga∈Ｆpmを送信している。【００４１】
ボブは、Ａを受信すると、Ｃ＝Ab＝gab∈Ｆpmを計算して、Ｂ＝gb∈Ｆpmを計算し、Ｂ＝gbをアリスに送信している。【００４２】
アリスは、Ｂを受信してＣ＝Ba＝gab∈Ｆpmを計算することにより、アリスとボブとを接続するネットワーク上に鍵gabを流すことなく共有することができる。【００４３】
なお、ＩＣカードにおける認証用データに用いる鍵の場合には、ＩＣカードの作成時にあらかじめＩＣカードに鍵データを記憶させておくことにより、ネットワーク上に鍵を流すことなく共有することができる。【００４４】
あるいは、一般的な公開鍵暗号の場合であれば、ボブがアリスから所要のデータを受け取る際に、ボブは予め公開鍵を公開しておく。【００４５】
例えば、Elgamal暗号の場合であれば、ボブは秘密鍵ｓを用いて、ｇ，Ｂ＝gs∈Ｆpmを計算して公開しておく。【００４６】
メッセージＭを送信するアリスは、ボブの公開鍵データｇ，Ｂをダウンロードして、メッセージＭに対して、
C1＝Ｍ×Ｂt、  C2＝gt
を計算することにより暗号化を行っている。ここで、ｔは乱数である。【００４７】
また、C1の演算を行うに当たり、後述する本発明の暗号化／復号化プログラム、暗号化／復号化装置、あるいは拡大体の乗算装置を用いている。【００４８】
アリスは、C1、C2をボブに送信し、ボブは、受信したC1、C2を用いて、C1/C2sを演算することによりメッセージＭの復号化を行っている。すなわち、
C1/C2s＝ＭＢt/gts＝Ｍgts/gts。【００４９】
この復号化においても、後述する本発明の暗号化／復号化プログラム、暗号化／復号化装置、あるいは拡大体の乗算装置を用いている。【００５０】
このようにメッセージＭの復号化は、ｓを秘密にもつボブのみが行える計算であり、対称鍵暗号のようにある一つのパスワードを互いに共有する必要がなく、かつ安全性が確保される長さの鍵を使用することで高い信頼性を有することができる。【００５１】
図１は、本実施形態の暗号化／復号化装置のブロック図である。なお、この暗号化／復号化装置は拡大体の乗算装置でもある。【００５２】
暗号化／復号化装置は、ＣＰＵ（中央演算装置）などの演算器10と、この演算器10が実行するプログラムなどを記憶した不揮発性記憶部20と、プログラムの実行にともなって必要となるデータを一時的に格納する揮発性記憶部30とを備えている。不揮発性記憶部20は、いわゆるＲＯＭ（Read Only Memory）あるいはハードディスクなどの不揮発性の記憶手段で構成し、揮発性記憶部30はいわゆるＲＡＭ（Random Access Memory）で構成している。【００５３】
特に、揮発性記憶部30は、複数のレジスタを備えており、それぞれのレジスタで所要のデータを記憶している。【００５４】
不揮発性記憶部20には、本実施形態の暗号化／復号化プログラムを記憶しており、この暗号化／復号化プログラムを起動させることにより、必要に応じて暗号化／復号化プログラムを揮発性記憶部30に展開して、暗号化あるいは復号化の演算を行っている。【００５５】
さらに、暗号化／復号化装置にはデータ入出力部40を設けており、このデータ入力部40を介して任意の拡大次数ｍの値を入力可能とし、入力された拡大次数ｍの値に基づいて暗号化を実行可能としている。あるいは、拡大次数ｍの値だけでなく、標数ｐの値を変更可能とすることもできる。【００５６】
また、データ入出力部40では、公開鍵となる鍵データの出力や、暗号化されたデータの入出力などを行っている。図１中、50はデータバスである。【００５７】
演算器10では、必要に応じて、揮発性記憶部30に記憶されている所要の鍵データ、標数ｐの値、拡大次数ｍなどを不揮発性記憶部20に記憶させてもよい。【００５８】
暗号化／復号化装置あるいは拡大体の乗算装置は、このように暗号化／復号化プログラムを実行する電子計算機などの装置に限定するものではなく、暗号化／復号化プログラムに相当する演算を実行する演算回路を備えた演算用デバイスとして、演算処理の高速化を図ることもできる。【００５９】
以下において、暗号化あるいは復号化における２つの元の乗算について説明する。【００６０】
まず、第１実施形態として、以下の条件下における元Ａと元Ｂの積の演算について説明する。ここで、この積の演算が暗号化である場合には、元Ａと元Ｂのいずれか一方が暗号化鍵であって、他方が暗号化鍵の鍵長ごとに分断された単位長平文データであり、積の演算が復号化である場合には、元Ａと元Ｂのいずれか一方が復号化鍵であって、他方が復号化鍵の鍵長ごとに分断された単位長暗号データである。【００６１】
・素数ｐを標数とする拡大体を定義体とする。
・拡大次数ｍに対し、km+1が素数であって、Fkm+1でｐが原始元となる適当な正整数ｋ。
・０≦ｉ≦ｍ−１、０≦ｊ≦ｋ−１。
・<ｘ>がｘのmod(km+1)をとるものとする。
・ωを１の原始km+1乗根とする。
・{a0,a1,a2,・・・，am-1}を拡大次数ｍの拡大体Fpmの元Ａ
【数１】
0004836208.tif 000003
・{b0,b1,b2,・・・，bm-1}を拡大次数ｍの拡大体Fpmの元Ｂ
【数２】
0004836208.tif 000004
【００６２】
なお、任意の正整数ｍに対して、km+1が素数となる正整数ｋが少なくともｋ＜ｍの範囲に存在していることは一般的に証明済みの事実であり、正整数ｋを特定する専用プログラムを用いて容易に見つけ出すことができる。【００６３】
通常、元Ａと元Ｂの積Ｃ＝ＡＢは、ＣＶＭＡ（Cyclic Vector Multiplication Algorithm）で計算されるが、部分体における演算の閉性から元Ａと元Ｂの積Ｃも部分体Fpmの元なることから、積Ｃのベクトル表現においても、基底ベクトルω'とω”のベクトル係数が等しくなる。【００６４】
ここで、表記の便宜上、
【数３】
0004836208.tif 000005
及び、
【数４】
0004836208.tif 000006
である。【００６５】
したがって、求める必要があるのは０≦ｉ≦m-1でのω'の各係数ciのみであり、
【数５】
0004836208.tif 000007
として、係数ciは、図２に示すフローチャートに基づく暗号化／復号化プログラムにより、パーソナルコンピュータなどの電子計算機での演算によって求めることができる。【００６６】
ただし、この場合、直接、8p|m(p-1)となる拡大体を構成することはできない。そこで、8p|m(p-1)となる拡大体を構成する場合には、拡大次数ｍの偶数因数部分mEと奇数因数部分mOとに分けて（ｍ＝mE・mO）、それぞれを逐次拡大体に分けて拡大することにより、8p|m(p-1)となる拡大体にも対応可能とすることができる。なお、場合によっては後述する第２実施形態を組み合わせて用いることが必要となることもある。【００６７】
暗号化の場合には、まず、電子計算機では拡大次数ｍを設定する（ステップＳ１）。なお、復号化の場合には、電子計算機は、秘密鍵または公開鍵の鍵長から拡大次数ｍを特定することもできる。【００６８】
次いで、電子計算機は、設定された拡大次数ｍに基づいて、km+1が素数であって、Fkm+1でｐが原始元となる適当な正整数ｋを専用プログラムを用いて特定する（ステップＳ２）。なお、前述したように、ｋ＜ｍの範囲でkm+1が素数となる正整数ｋは少なくとも１つは特定でき、電子計算機は、比較的短時間で正整数ｋの特定処理を終了することができる。【００６９】
次いで、電子計算機は、０≦ｔ≦k-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求め（ステップＳ３）、さらに、０≦ｉ≦kmで、それぞれ０＝q[<i>]とする（ステップＳ４）。【００７０】
次いで、電子計算機は、０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求め（ステップＳ５）、その後、０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて、０≦ｔ≦k-1でq[<pi+(pjK[t])>]へのＭの足し込みをそれぞれ行う（ステップＳ６）。【００７１】
その後、電子計算機は、拡大次数ｍの拡大体Fpmではなく、拡大次数kmの拡大体を定義体として用いていることによる処理として、０≦ｉ≦m-1で、かつ１≦ｔ≦k-1で、q[<pi>]へのq[<(piK[t])>]の足し込みをそれぞれ行って（ステップＳ７）、最後に、０≦ｉ≦m-1で、kq[<0>]-q[<pi>]＝ciを求めている（ステップＳ８）。【００７２】
このように、ciは、拡大次数kmの拡大体Fpkmにおける所定の元の加算または減算と、乗算との繰り返しに分解して演算を行うことができ、並列処理化が容易であって、高速演算を可能とすることができる。【００７３】
特に、演算の負荷が小さいことにより、携帯電話機やＩＣカードなどの演算機能の乏しい装置でも容易に乗算処理を実行でき、しかも公開鍵及び秘密鍵の鍵長の変更を可能とすることができる。【００７４】
さらに、乗算処理における演算は、演算処理回路として半導体基板上に形成して乗算処理用半導体デバイスとすることもでき、この乗算処理用半導体デバイスを備えた暗号化／復号化装置として、暗号化及び復号化のさらなる高速化を図ることができ、しかも、並列処理化が可能であって、一層の高速化を図ることができる。また、拡大体の乗算装置として乗算処理用半導体デバイスを用いることもできる。【００７５】
すなわち、乗算処理用半導体デバイスでは、半導体基板上に、所要の演算を実行可能とした演算器を形成するとともに、各記憶部として以下のレジスタ及びレジスタ群を形成している。
・標数ｐを記憶するレジスタ。
・拡大次数ｍを記憶するレジスタ。
・拡大次数ｍに基づく拡大体Fpmの元Ａを記憶するレジスタ群。
・拡大次数ｍに基づく拡大体Fpmの元Ｂを記憶するレジスタ群。
・設定された拡大次数ｍに対応した正整数ｋを特定して記憶するレジスタ。
・０≦ｔ≦k-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求めて記憶するレジスタ群。
・０≦ｉ≦km-1で、それぞれ０＝q[<i>]として記憶するレジスタ群。
・０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めて記憶するレジスタ群。
・０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて記憶するレジスタ群。
・０≦ｔ≦k-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込んで記憶するレジスタ群。
・０≦ｉ≦m-1で、かつ１≦ｔ≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込んで記憶するレジスタ群。
・０≦ｉ≦m-1で、kq[<0>]-q[<pi>]＝ciをそれぞれ求めて記憶するレジスタ群。【００７６】
これらのレジスタ及びレジスタ群を設けることにより、各演算は並列化が可能であるので、並列処理を行うことにより乗算処理をさらに高速化することができる。したがって、高速な暗号化及び復号化を可能とする暗号化／復号化装置、あるいは拡大体の乗算装置を提供できる。【００７７】
この乗算処理用半導体デバイスを所要の実装ボードに装着することにより、高速な乗算処理を可能とする実装ボードを提供でき、この実装ボードを用いて携帯電話機や電子計算機などを構成することにより、高速な暗号化及び復号化が可能であって、しかも公開鍵及び秘密鍵の鍵長の長さを自在に可変とした携帯電話機や電子計算機などを提供することができる。【００７８】
以下において、第２実施形態として、以下の条件下における元Ａと元Ｂの積の演算について説明する。ここで、第１実施形態との違いは、ｋ＝2k'となるk'を用いて演算を行うことである。すなわち、
・素数ｐを標数とする拡大体を定義体とする。
・拡大次数ｍに対し、2k'm+1が素数であって、F2k'm+1でｐが原始元あるいは位数がk'mかつk'mが奇数となる適当な正整数k'。
・０≦ｉ≦ｍ−１、０≦ｊ≦2k'−１。
・<ｘ>がｘのmod(2k'm+1)をとるものとする。
・ωを１の原始2k'm+1乗根として、τ＝ω＋ω-1とする。
・{a0,a1,a2,・・・，am-1}を拡大次数ｍの拡大体Fpmの元Ａ
【数６】
0004836208.tif 000008
・{b0,b1,b2,・・・，bm-1}を拡大次数ｍの拡大体Fpmの元Ｂ
【数７】
0004836208.tif 000009
【００７９】
部分体における演算の閉性から元Ａと元Ｂの積Ｃも部分体Fpmの元なることから、積Ｃのベクトル表現においても、基底ベクトルτ'とτ”のベクトル係数が等しくなる。【００８０】
ここで、表記の便宜上、
【数８】
0004836208.tif 000010
及び、
【数９】
0004836208.tif 000011
である。【００８１】
したがって、求める必要があるのは０≦ｉ≦m-1でのτ'の係数ciのみであり、
【数１０】
0004836208.tif 000012
として、係数ciは、図３に示すフローチャートに基づくプログラムにより、パーソナルコンピュータなどの電子計算機での演算によって求めることができる。【００８２】
ただし、この場合には、4p|m(p-1)となる拡大体を構成することはできない。そこで、4p|m(p-1)となる拡大体を構成する場合には、拡大次数ｍの偶数因数部分mEと奇数因数部分mOとに分けて（ｍ＝mE・mO）、それぞれを逐次拡大体に分けて拡大することにより、4p|m(p-1)となる拡大体にも対応可能とすることができる。なお、場合によっては前述した第１実施形態を組み合わせて用いることが必要となることもある。【００８３】
暗号化の場合には、まず、電子計算機では拡大次数ｍを設定する（ステップＴ１）。なお、復号化の場合には、電子計算機は、秘密鍵または公開鍵の鍵長から拡大次数ｍを特定する。【００８４】
次いで、電子計算機は、設定された拡大次数ｍに基づいて、2k'm+1が素数であって、F2k'm+1でｐが原始元あるいは位数がk'mかつk'mが奇数となる適当な正整数k'を専用プログラムを用いて特定する（ステップＴ２）。なお、前述したように、2k'＜ｍの範囲で2k'm+1が素数となる正整数k'は少なくとも１つは特定でき、電子計算機は、比較的短時間で正整数k'の特定処理を終了することができる。【００８５】
次いで、電子計算機は、０≦ｔ≦k'-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求め（ステップＴ３）、さらに、０≦ｉ≦2k'mで、それぞれ０＝q[<i>]とする（ステップＴ４）。【００８６】
次いで、電子計算機は、０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求め（ステップＴ５）、その後、０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて、０≦ｔ≦k'-1でq[<pi+(pjK[t])>]へのＭの足し込みをそれぞれ行うとともに、q[<pi−(pjK[t])>]へのＭの足し込みをそれぞれ行う（ステップＴ６）。【００８７】
その後、電子計算機は、拡大次数ｍの拡大体Fpmではなく、拡大次数k'mの拡大体を定義体として用いていることによる処理として、０≦ｉ≦m-1で、かつ１≦ｔ≦k-1で、q[<pi>]へのq[<(piK[t])>]の足し込みをそれぞれ行うとともに、q[<pi>]へのq[<-(piK[t])>]の足し込みをそれぞれ行って（ステップＴ７）、電子計算機は、最後に、０≦ｉ≦m-1で、-q[<pi>]＝ciを求めている（ステップＴ８）。【００８８】
このように、ciは、所定の元の加算または減算と、乗算との繰り返しに分解して演算を行うことができ、並列処理化が容易であって、高速演算を可能とすることができる。【００８９】
また、図３に示したフローチャートの乗算処理の演算も、演算処理回路として半導体基板上に形成して乗算処理用半導体デバイスとすることもでき、この乗算処理用半導体デバイスを備えた暗号化／復号化装置として、暗号化及び復号化のさらなる高速化を図ることができ、しかも、並列処理化が可能であって、一層の高速化を図ることができる。また、拡大体の乗算装置として乗算処理用半導体デバイスを用いることもできる。【００９０】
この場合、乗算処理用半導体デバイスでは、半導体基板上に、所要の演算を実行可能とした演算器を形成するとともに、各記憶部として以下のレジスタ及びレジスタ群を形成している。
・標数ｐを記憶するレジスタ。
・拡大次数ｍを記憶するレジスタ。
・拡大次数ｍに基づく拡大体Fpmの元Ａを記憶するレジスタ群。
・拡大次数ｍに基づく拡大体Fpmの元Ｂを記憶するレジスタ群。
・設定された拡大次数ｍに対応した正整数k'を特定して記憶するレジスタ。
・０≦ｔ≦k'-1で、<pmt>＝K[t]となる各K[t]をそれぞれ求めて記憶するレジスタ群。
・０≦ｉ≦2k'm-1で、それぞれ０＝q[<i>]として記憶するレジスタ群。
・０≦ｉ≦m-1で、aibimodp＝q[<pi>]をそれぞれ求めて記憶するレジスタ群。
・０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて記憶するレジスタ群。
・０≦ｔ≦k'-1でq[<pi+(pjK[t])>]にＭをそれぞれ足し込し込んで記憶するとともに、q[<pi-(pjK[t])>]にＭをそれぞれ足し込んで記憶するレジスタ群。
・０≦ｉ≦m-1で、かつ１≦ｔ≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込んで記憶するとともに、さらに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込んで記憶するレジスタ群。
・０≦ｉ≦m-1で、-q[<pi>]＝ciをそれぞれ求めて記憶するレジスタ群。【００９１】
これらのレジスタ及びレジスタ群を設けることにより、第１の実施形態の場合と同様に、各演算は並列化が可能であるので、並列処理を行うことにより乗算処理をさらに高速化することができる。したがって、高速な暗号化及び復号化を可能とする暗号化／復号化装置、あるいは拡大体の乗算装置を提供できる。【００９２】
さらに、km+1を素数とし、Ｓをmod km+1における位数ｋの部分巡回乗法群として、km次のＡＯＰ（All One Polynominal）（ｘkm+1−１）／（ｘ−１）の零点をωとして、
【数１１】
0004836208.tif 000013
で与えられるγを用い、次の集合を考える。
【数１２】
0004836208.tif 000014
【００９３】
［数１２］の集合が拡大体Fpmにおいて正規基底を成すことは、km/eがｍと互いに素となることと必要十分である。ここで、ｅはｐのmod km+1での位数である。前述した第１実施形態及び第２実施形態は、この正規基底を用いた乗算に適用可能となっている。【００９４】
すなわち、
・ｅをＦｋｍ＋１における元ｐの位数とする。
・ｅ'＝ｋｍ／ｅ
・１の原始ｋ乗根ε∈Ｆｋｍ＋１とする。
・{a0,a1,a2,・・・，am-1}を拡大次数ｍの拡大体Fpmの元Ａ
【数１３】
0004836208.tif 000015
・{b0,b1,b2,・・・，bm-1}を拡大次数ｍの拡大体Fpmの元Ｂ
【数１４】
0004836208.tif 000016
【００９５】
このとき、部分体における演算の閉性から元Ａと元Ｂの積Ｃは、
【数１５】
0004836208.tif 000017
として、係数ciは、図４に示すフローチャートに基づくプログラムにより、パーソナルコンピュータなどの電子計算機での演算によって求めることができる。【００９６】
ここで、暗号化の場合には、まず、電子計算機では拡大次数ｍを設定する（ステップＵ１）。なお、復号化の場合には、電子計算機は、秘密鍵または公開鍵の鍵長から拡大次数ｍを特定する。【００９７】
次いで、電子計算機は、設定された拡大次数ｍに基づいて、km+1が素数であって、ｅ'（＝ｋｍ／ｅ）とｍとが互いに素となる適当な正整数ｋを専用プログラムを用いて特定する（ステップＵ２）。正整数ｋの特定にともなって、１の原始ｋ乗根のεを特定する（ステップＵ３）。【００９８】
次いで、電子計算機は、１＝K[０]，０＝r[０]とする（ステップＵ４）。【００９９】
次いで、電子計算機は、０≦ｉ≦ｍで、０＝q[<i>]とする（ステップＵ５）。【０１００】
次いで、電子計算機は、１≦ｔ≦k-1で、<K[t-1]ε>＝K[t]とする（ステップＵ６）。【０１０１】
次いで、電子計算機は、０≦ｔ≦m-1であって、０≦ｔ≦k-1で、ｉ＋１＝r[<piK[t]>]とする（ステップＵ７）。【０１０２】
次いで、電子計算機は、０≦ｔ≦m-1で、aibimodp＝q[i+1]をそれぞれ求める（ステップＵ８）。【０１０３】
次いで、電子計算機は、０≦ｉ＜ｊ≦m-1で、(ai-aj)(bi-bj)modp＝Ｍをそれぞれ求めて、０≦ｔ≦k-1でq[r[<pi+(pjK[t])>]]へのＭの足し込みをそれぞれ行う（ステップＵ９
）。【０１０４】
最後に、電子計算機は、０≦ｉ≦m-1で、kq[<0>]-q[i+1]＝ciを求めている（ステップＵ１０）。【０１０５】
なお、ｋが偶数の場合には、ステップＵ９においてkq[<0>]＝０とすることができる。【０１０６】
このように、より多くの正規基底に対して適用可能とすることができる。しかも、ｋの値をより小さくすることができるので、演算回数の削減による演算処理の高速化を図ることもできる。【０１０７】
なお、前述したように、8p|m(p-1)あるいは4p|m(p-1)などのように、ｍがｐの倍数である場合には拡大体を構成できないことがあるが、拡大次数ｍを偶数因数部分mEと奇数因数部分mOとに分けて、それぞれを逐次拡大体に分けて拡大することにより、奇標数ｐに対しての拡大体の構成を可能とすることができ、上記の制限を排除することができる。【０１０８】
すなわち、例えば、Fp4pを構成する場合を考える。この場合には、最初にFp4の拡大体を構成し、次いで、この拡大体をｐ次逐次拡大することにより、奇標数ｐが４と互いに素であることからFp4pで表される拡大体を構成できる。すなわち、任意の奇標数及び任意次数の拡大体を構成することが可能である。【０１０９】
本発明は数学的に見た場合には、既約多項式として法多項式を準備することなく拡大体における乗算や除算を行えるものであり、見方を変えれば本発明の考え方を利用することにより、任意次数の既約多項式を生成することができることを示している。【０１１０】
ここで、例えばFp4の(1,2,1,2）というベクトル表現を持つ元はFp2の元である。真部分体に含まれないような元を真性元と呼ぶこととして、Fpmの真性元をαとした場合、そのαの最小多項式、すなわちαを零点にもつFp上の最小次数の多項式Ｍα(x)が求まれば、それはFp上のｍ次既約多項式となっている。【０１１１】
なお、Ｍα(x)は、次式で表される。
【数１６】
0004836208.tif 000018
【０１１２】
ここで、次式の計算式を考えることにする。
【数１７】
0004836208.tif 000019
【数１８】
0004836208.tif 000020
【０１１３】
上式で、ｉ＝m-2,m-3,・・・,2,1,0の順に計算されることにより既約多項式が求められることとなる。【０１１４】
すなわち、拡大体Fpmの任意の真性元αの最小多項式は、図５に示すフローチャートに基づくプログラムにより、下のようにして求めることができる。【０１１５】
まず、電子計算機では、真性元αのベクトル表現（x0,x1,x2,・・・,xm-1）を設定する（ステップＷ１）。ここで、真性元αの最小多項式Ｍα(x)は次式となるものとする。
【数１９】
0004836208.tif 000021
【０１１６】
次いで、電子計算機は、１≦ｉ≦ｍで、T[i]＝Tr(αi)とし（ステップＷ２）、a[m-1]=-T[1]とする（ステップＷ３）。【０１１７】
次いで、電子計算機は、m-2≧ｉ≧０で、０＝Ｍとし、０≦ｊ≦m-1-iで、-a[m-j]Tr(αm-i-j)のＭへの足し込みをそれぞれ行う（ステップＷ４）。【０１１８】
次いで、電子計算機は、a[i]=(m-i)-1{M-Tr(αm-i)}を求めている（ステップＷ５）。【０１１９】
これにより、ｐ＞ｍを満たす任意の既約多項式を求めることができる。なお、前述した処理は、素体Fpではない部分体に関する最小多項式の特定に用いることもできる。【０１２０】
このように任意の既約多項式を求めることができることによって、異なる定義体間の基底変換を可能とすることができる。【０１２１】
基底変換を行うためには変換行列を特定する必要があるが、ここで変換行列を生成したい拡大体F'pmがあり、これと同型の拡大体としてFpmを考える。なお、本明細書においては、数学において通常使用されている「＾」記号付きの表現が利用できないため、以下においては「＾」の代わりに「’」を代用している。【０１２２】
第１実施形態の方法を用いた基底変換行列の生成方法を考える。このとき、パラメータｋによって(xkm+1−１)/(x-1)という法多項式を考え、その零点ωを用いて次式で表されるγを考え、このγを用いて次式の正規基底を考える。ここで、ωはFpkmに真性元として存在する。
【数２０】
0004836208.tif 000022
【数２１】
0004836208.tif 000023
【０１２３】
このγに相当する元γ’を拡大体F'pmの中から見つけることができれば拡大体F'pmにおける正規基底を特定し、基底間での対応関係から変換行列を特定することができる。この変換行列の逆行列を求めれば基底変換を可能とすることができる。【０１２４】
ここで、元γ’を求めるためにはωに相当するω’を拡大体F'pkmにおいて特定すればよく、ω’を拡大体F'pkmにおいて特定するためには拡大体F'pmをｋ次逐次拡大してFpkmと同型なF'pkmを構成する。【０１２５】
ここで、ｋとｍが互いに素になるようにして、
（１）k'k+1が素数である。
（２）ｐのFk'k+1における位数がk'kである（すなわち原始元である）
ことを満たすk'を求めることができると、(xk'k+1−１)/(x-1)を法として、F'pmをｋ次逐次拡大してF'pmkを構成することができる。ここで、「k'」の「'」は「＾」の代用ではない。【０１２６】
この逐次拡大体F'pkmから次式を満たす元B'を探し、ω'を求める。
【数２２】
0004836208.tif 000024
【０１２７】
ここで、ω'は位数km+1の元となるので、Fpkmの位数km+1の元ωに対応することとなる。【０１２８】
したがって、次式で与えられる元γ’により以下の集合を考えると、この集合をFpmの基底と対応づけることができる。これを用いて変換行列及びその逆行列を求めることができ、基底変換を可能とすることができる。
【数２３】
0004836208.tif 000025
【数２４】
0004836208.tif 000026
【０１２９】
このように基底変換が可能なことから、既約多項式の因数分解を可能とすることができる。【０１３０】
すなわち、まず、Fp上のｍ次既約多項式f(x)を考え、その零点θ'による多項式基底｛１，θ'，θ'2，・・・，θ'm-1｝を用いてF'pmを構成することができる。ここで、「'」は「＾」による表示の代わりに用いている。【０１３１】
そして、F'pmの元θ'を基底変換行列によってFpmの対応する元θに写像すれば、Fp上のｍ次既約多項式f(x)の１つの解をFpm上で求めたこととなる。【０１３２】
したがって、共役元まで考えれば、f(x)をFpm上で因数分解できることとなるので、任意の拡大体上で因数分解できることとなる。
【産業上の利用可能性】
【０１３３】
パーソナルコンピュータや携帯電話、あるいはＩＣチップ付きのクレジットカードのように、他の機器とデータの送受信が行われる機器において、鍵長を任意に変更可能として、要求される安全性と、暗号化または復号化の処理負荷を調整ながら、暗号化データの送受信を可能とする。
【図１】
0004836208.tif 000027
【図２】
0004836208.tif 000028
【図３】
0004836208.tif 000029
【図４】
0004836208.tif 000030
【図５】
0004836208.tif 000031