TOP > 国内特許検索 > 暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置 > 明細書

明細書 :暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4836208号 (P4836208)
登録日 平成23年10月7日(2011.10.7)
発行日 平成23年12月14日(2011.12.14)
発明の名称または考案の名称 暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置
国際特許分類 G09C   1/00        (2006.01)
FI G09C 1/00 650A
G09C 1/00 660D
請求項の数または発明の数 11
全頁数 22
出願番号 特願2008-526767 (P2008-526767)
出願日 平成19年7月24日(2007.7.24)
国際出願番号 PCT/JP2007/064474
国際公開番号 WO2008/013154
国際公開日 平成20年1月31日(2008.1.31)
優先権出願番号 2006200946
2007010072
優先日 平成18年7月24日(2006.7.24)
平成19年1月19日(2007.1.19)
優先権主張国 日本国(JP)
日本国(JP)
審査請求日 平成22年6月9日(2010.6.9)
特許権者または実用新案権者 【識別番号】504147243
【氏名又は名称】国立大学法人 岡山大学
発明者または考案者 【氏名】野上 保之
【氏名】森川 良孝
早期審査対象出願または早期審理対象出願 早期審査対象出願
個別代理人の代理人 【識別番号】100080160、【弁理士】、【氏名又は名称】松尾 憲一郎
審査官 【審査官】石田 信行
参考文献・文献 特開2007-271715(JP,A)
特開2005-284111(JP,A)
特開2003-84666(JP,A)
特開2002-304120(JP,A)
特開2001-51832(JP,A)
特開2001-34167(JP,A)
調査した分野 G09C 1/00
G06F 7/72
特許請求の範囲 【請求項1】
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、
電子計算機で、前記平文データと前記暗号化鍵とを乗算して暗号データの元C={c0,c1,c2,・・・,cm-1}を生成させる、または前記暗号データと前記復号化鍵とを乗算して平文データの元C={c0,c1,c2,・・・,cm-1}を生成させる暗号化/復号化プログラムにおいて、
km+1が素数であって、Fkm+1でpが原始元となる正整数kを特定する第1のステップと、
前記の2つの元A,Bを、前記正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として乗算を行う第2のステップと、
この乗算の結果を用いて部分体である前記拡大次数mの拡大体Fpmの元における乗算の結果を求める第3のステップと
を有することを特徴とする暗号化/復号化プログラム。
【請求項2】
0≦i≦m-1、0≦j≦k-1とし、
<x>がxのmod(km+1)をとるものとして、
前記第2のステップは、
0≦t≦k-1で、<p>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦kmで、それぞれ0=q[]とするステップと、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k-1でq[<p+(pjK[t])>]にMをそれぞれ足し込むステップと
を有することを特徴とする請求項1記載の暗号化/復号化プログラム。
【請求項3】
前記第3のステップは、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、kq[<0>]-q[<p>]=ciをそれぞれ求めるステップと
を有することを特徴とする請求項2記載の暗号化/復号化プログラム。
【請求項4】
k=2k'の場合に、
F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'とし、
0≦i≦m-1、0≦j≦2k'-1とし、
<x>がxのmod(2k'm+1)をとるものとして、
前記第2のステップは、
0≦t≦k'-1で、<p>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦2k'mで、それぞれ0=q[]とするステップと、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k'-1でq[<p+(pjK[t])>]にMをそれぞれ足し込むとともに、q[<p-(pjK[t])>]にMをそれぞれ足し込むステップと
を有することを特徴とする請求項1記載の暗号化/復号化プログラム。
【請求項5】
前記第3のステップは、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込むとともに、q[<p>]にq[<-(pK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、-q[<p>]=ciをそれぞれ求めるステップと
を有することを特徴とする請求項4記載の暗号化/復号化プログラム。
【請求項6】
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、
前記平文データと前記暗号化鍵とを乗算させて元C={c0,c1,c2,・・・,cm-1}を生成することにより暗号化する、または前記暗号データと前記復号化鍵とを乗算させて元C={c0,c1,c2,・・・,cm-1}を生成することにより復号化する演算器を備えた暗号化/復号化装置において、
前記元をそれぞれ記憶する第1の記憶部と、
前記拡大次数mを記憶する第2の記憶部と、
km+1が素数であって、Fkm+1でpが原始元となる正整数kを前記演算器による演算に基づいて特定して記憶する第3の記憶部と、
前記の2つの元A,Bを、前記正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として前記演算器で乗算した結果を記憶する第4の記憶部と、
前記拡大次数kmの拡大体Fpkmの元の乗算結果を用いて前記演算器で所定の演算を行って、部分体である前記拡大次数mの拡大体Fpmの元における乗算の結果を求めて記憶する第5の記憶部と
を有することを特徴とする暗号化/復号化装置。
【請求項7】
0≦i≦m-1、0≦j≦k-1とし、
<x>がxのmod(km+1)をとるものとして、
前記第4の記憶部は、
0≦t≦k-1で、<p>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦kmで、それぞれ0=q[]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k-1でq[<p+(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項6記載の暗号化/復号化装置。
【請求項8】
前記第5の記憶部は、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、kq[<0>]-q[<p>]=ciをそれぞれ求めて記憶する記憶部と
を有することを特徴とする請求項7記載の暗号化/復号化装置。
【請求項9】
k=2k'の場合に、
F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'として、この正整数k'を記憶する記憶部を有し、
0≦i≦m-1、0≦j≦2k'-1とし、
<x>がxのmod(2k'm+1)をとるものとして、
前記第4の記憶部は、
0≦t≦k'-1で、<p>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦2k'mで、それぞれ0=q[]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k'-1でq[<p+(pjK[t])>]にMをそれぞれ足し込し込んで記憶するとともに、q[<p-(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項6記載の暗号化/復号化装置。
【請求項10】
前記第5の記憶部は、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込むとともに、q[<p>]にq[<-(pK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、-q[<p>]=ciをそれぞれ求めて記憶する記憶部と
を有することを特徴とする請求項9記載の暗号化/復号化装置。
【請求項11】
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を乗算して元C={c0,c1,c2,・・・,cm-1}を生成する演算器を備えた拡大体の乗算装置において、
前記元をそれぞれ記憶する第1の記憶部と、
前記拡大次数mを記憶する第2の記憶部と、
km+1が素数であって、Fkm+1でpが原始元となる正整数kを前記演算器による演算に基づいて特定して記憶する第3の記憶部と、
前記の2つの元A,Bを、前記正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として前記演算器で乗算した結果を記憶する第4の記憶部と、
前記拡大次数kmの拡大体Fpkmの元の乗算結果を用いて前記演算器で所定の演算を行って、部分体である前記拡大次数mの拡大体Fpmの元における乗算の結果を求めて記憶する第5の記憶部と
を有することを特徴とする拡大体の乗算装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、暗号化/復号化プログラム、暗号化/復号化装置、及び暗号化または復号化における乗算処理を実行する拡大体の乗算装置に関する。
【背景技術】
【0002】
従来、インターネットなどの電気通信回線を利用した情報通信において、送受信されるデータの秘匿性を保持するために、データの暗号化が行われている。すなわち、平文データを送信する送信者は、平文データに暗号化処理を施して暗号データを生成し、この暗号データを受信者に送信している。一方、暗号データを受信した受信者は、暗号データに復号化処理を施して平文データを生成することにより、平文データを受け取ることができる。
【0003】
このような暗号化及び復号化の方法として、昨今では公開鍵暗号と呼ばれる方法が用いられている。公開鍵暗号では、公開鍵と秘密鍵があらかじめ設定され、所定の平文データを送信する送信者に公開鍵を開示しており、送信者は公開鍵を用いて平文データを暗号化することにより暗号データを生成し、受信者に送信している。受信者は、暗号データを受信すると、秘密鍵を用いて暗号データを復号化して平文データを生成している。
【0004】
ここで、平文データを暗号化する場合には、平文データを暗号化に用いる公開鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長平文データを生成し、各単位長平文データと公開鍵を用いて乗算処理を行うことにより単位長暗号データを生成し、所定数の単位長暗号データで構成された暗号データを生成している。
【0005】
一方、暗号データを復号化する場合には、暗号データを復号化に用いる秘密鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長暗号データを生成し、各単位長暗号データと秘密鍵を用いて乗算処理を行うことにより単位長平文データを生成し、所定数の単位長平文データで構成された平文データを生成している。
【0006】
このような公開鍵暗号には様々な方式が提案されており、Rivest Shamir Adleman(RSA)暗号、楕円曲線暗号、ElGamal暗号などが知られている。
【0007】
昨今、パーソナルコンピュータなどの電子計算機の性能向上にともなって、各種の暗号方法で暗号化された暗号データが解読されるおそれが高まっている。すなわち、暗号データは、秘密鍵さえ分かれば解読できることから、電子計算機によって手当たり次第に秘密鍵を生成して復号化を試みることにより、時間はかかるものの解読されるおそれがあった。
【0008】
そこで、各暗号方法では、安全性を高めるために公開鍵及び秘密鍵の鍵長を長くすることが行われている。すなわち、公開鍵及び秘密鍵の鍵長を長くすると、解読に用いる秘密鍵の数が飛躍的に増大し、現実的な時間内での解読を不可能とすることができるからである。そのため、現在では、RSA暗号では1024ビット以上、楕円曲線暗号では160ビット以上、ElGamal暗号では1024ビット以上の鍵長が求められている。
【0009】
しかしながら、公開鍵及び秘密鍵の鍵長を長くした場合には、公開鍵を用いた乗算処理による暗号化、及び秘密鍵を用いた乗算処理による復号化に多大な時間を要することとなっていた。この場合、処理時間の短縮のためには、乗算処理の演算速度が高速な演算手段が必要となることにより、安全性を高めるためのコストが増大することとなっていた。
【0010】
一方で、現実的には、電気通信回線中を流れているデータにおいては重要度が様々に異なっており、利用価値が高いために高度の秘匿性が必要なデータから、利用価値が低いために秘匿性を必要としないデータまでが存在している。
【0011】
したがって、何れのデータに対しても同等の安全性で暗号化する必要はなく、高い安全性が要求されるデータには長い鍵長の公開鍵及び秘密鍵を用い、高い安全性が要求されないデータには短い鍵長の公開鍵及び秘密鍵が用いられている。
【0012】
また、パーソナルコンピュータなどのような高速な演算処理の実行が可能な装置では、できるだけ長い鍵長の公開鍵及び秘密鍵による暗号化が利用されており、携帯電話機やICカードなどのような演算処理能力の乏しい装置では、比較的短い鍵長の公開鍵及び秘密鍵による暗号化が利用され、保証され得る安全性の範囲内でデータの送受信が行われている。
【0013】
特に、パーソナルコンピュータなどの電子計算機では、複数種類の鍵長の公開鍵及び秘密鍵が利用可能となっており、送信するデータに応じた安全性、あるいは送信先の装置における乗算処理の処理能力などに応じて鍵長を変えて暗号化することも行われており、鍵長に汎用性を持たせることが提案されている(例えば、特許文献1参照。)。

【特許文献1】特開2001-051832号公報
【発明の開示】
【発明が解決しようとする課題】
【0014】
しかしながら、通常、鍵長の決定にともなって、乗算処理などの演算処理に必要となる拡大体が、所定の拡大体に特定されてしまうために、鍵長に汎用性を持たせた場合には、鍵長ごとの拡大体をあらかじめ準備しておかなければならなかった。したがって、鍵長の汎用性を高めようとすればするほど、鍵長に対応した拡大体を記憶しておくためのより大きな記憶領域が必要となっていた。
【0015】
したがって、現実的には、準備できる記憶領域の大きさの制限から、鍵長は3~5種類程度しか準備されておらず、必ずしも十分な汎用性が提供できてはいなかった。そのため、準備された鍵長の公開鍵及び秘密鍵では安全性が十分に保証できない状態となった場合に、安全性をさらに高めることはできなかった。
【0016】
しかも、従来の暗号化または復号化における乗算処理では、多項式積の計算の後に多項式剰余算の計算が必要であって、多項式積の計算が終了するまでは多項式剰余算の計算を開始することができなかった。したがって、このような乗算処理を演算回路を構成して実行する場合には、演算回路の並列化が困難であって、処理速度の高速化を図りにくいという問題もあった。
【0017】
本発明者らは、このような現状に鑑み、任意な鍵長を選択可能としながら高速に乗算処理を実行可能とすることにより、利便性の高い暗号化及び復号化のシステムを構築可能とするために研究を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【0018】
本発明の暗号化/復号化プログラムでは、素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、電子計算機で、平文データと暗号化鍵とを乗算して暗号データの元C={c0,c1,c2,・・・,cm-1}を生成させる、または暗号データと復号化鍵とを乗算して平文データの元C={c0,c1,c2,・・・,cm-1}を生成させる暗号化/復号化プログラムにおいて、km+1が素数であって、Fkm+1でpが原始元となる正整数kを特定する第1のステップと、2つの元A,Bを、正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として乗算を行う第2のステップと、この乗算の結果を用いて部分体である拡大次数mの拡大体Fpmの元における乗算の結果を求める第3のステップとを有することとした。
【0019】
さらに、本発明の暗号化/復号化プログラムでは、
0≦i≦m-1、0≦j≦k-1とし、
<x>がxのmod(km+1)をとるものとして、
第2のステップが、
0≦t≦k-1で、<p>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦kmで、それぞれ0=q[]とするステップと、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k-1でq[<p+(pjK[t])>]にMをそれぞれ足し込むステップと
を有することにも特徴を有するものであり、
第3のステップが、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、kq[<0>]-q[<p>]=ciをそれぞれ求めるステップと
を有することにも特徴を有するものである。
【0020】
さらに、本発明の暗号化/復号化プログラムでは、
k=2k'の場合に、
F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'とし、
0≦i≦m-1、0≦j≦2k'-1とし、
<x>がxのmod(2k'm+1)をとるものとして、
第2のステップが、
0≦t≦k'-1で、<p>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦2k'mで、それぞれ0=q[]とするステップと、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k'-1でq[<p+(pjK[t])>]にMをそれぞれ足し込むとともに、q[<p-(pjK[t])>]にMをそれぞれ足し込むステップと
を有することにも特徴を有し、
第3のステップが、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込むとともに、q[<p>]にq[<-(pK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、-q[<p>]=ciをそれぞれ求めるステップと
を有することにも特徴を有するものである。
【0021】
また、本発明の暗号化/復号化装置では、素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を、平文データと暗号化鍵、または暗号データと復号化鍵として、平文データと暗号化鍵とを乗算させて元C={c0,c1,c2,・・・,cm-1}を生成することにより暗号化する、または暗号データと復号化鍵とを乗算させて元C={c0,c1,c2,・・・,cm-1}を生成することにより復号化する演算器を備えた暗号化/復号化装置において、元をそれぞれ記憶する第1の記憶部と、拡大次数mを記憶する第2の記憶部と、km+1が素数であって、Fkm+1でpが原始元となる正整数kを演算器による演算に基づいて特定して記憶する第3の記憶部と、2つの元A,Bを、正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として演算器で乗算した結果を記憶する第4の記憶部と、拡大次数kmの拡大体Fpkmの元の乗算結果を用いて演算器で所定の演算を行って、部分体である拡大次数mの拡大体Fpmの元における乗算の結果を求めて記憶する第5の記憶部とを有することとした。
【0022】
さらに、本発明の暗号化/復号化装置では、
0≦i≦m-1、0≦j≦k-1とし、
<x>がxのmod(km+1)をとるものとして、
第4の記憶部が、
0≦t≦k-1で、<p>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦kmで、それぞれ0=q[]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k-1でq[<p+(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することにも特徴を有し、
第5の記憶部が、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、kq[<0>]-q[<p>]=ciをそれぞれ求めて記憶する記憶部と
を有することにも特徴を有するものである。
【0023】
さらに、本発明の暗号化/復号化装置では、
k=2k'の場合に、
F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる正整数k'として、この正整数k'を記憶する記憶部を有し、
0≦i≦m-1、0≦j≦2k'-1とし、
<x>がxのmod(2k'm+1)をとるものとして、
第4の記憶部が、
0≦t≦k'-1で、<p>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦2k'mで、それぞれ0=q[]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k'-1でq[<p+(pjK[t])>]にMをそれぞれ足し込し込んで記憶するとともに、q[<p-(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することにも特徴を有し、
第5の記憶部が、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込むとともに、q[<p>]にq[<-(pK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、-q[<p>]=ciをそれぞれ求めて記憶する記憶部と
を有することにも特徴を有するものである。
【0024】
また、本発明の乗算装置では、素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を乗算して元C={c0,c1,c2,・・・,cm-1}を生成する演算器を備えた拡大体の乗算装置において、元をそれぞれ記憶する第1の記憶部と、拡大次数mを記憶する第2の記憶部と、km+1が素数であって、Fkm+1でpが原始元となる正整数kを演算器による演算に基づいて特定して記憶する第3の記憶部と、2つの元A,Bを、正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として演算器で乗算した結果を記憶する第4の記憶部と、拡大次数kmの拡大体Fpkmの元の乗算結果を用いて演算器で所定の演算を行って、部分体である拡大次数mの拡大体Fpmの元における乗算の結果を求めて記憶する第5の記憶部とを有することとした。
【発明の効果】
【0025】
本発明では、素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を乗算して元C={c0,c1,c2,・・・,cm-1}を生成する際に、km+1が素数であって、Fkm+1でpが原始元となる正整数kを用いて、素数pを標数とする拡大次数kmの拡大体Fpkmを定義体として想定して演算を行うことにより、拡大次数mを任意の整数とすることができる。
【0026】
すなわち、任意の拡大次数mを用いても、km+1が素数であって、Fkm+1でpが原始元となる正整数kを用いた拡大次数kmの拡大体によって、演算に必要な拡大体を極めて容易に準備できるので、拡大次数mごとに対応した拡大体を準備する必要がなく、拡大次数mを無制限に選択することができる。
【0027】
この拡大次数mは、暗号化及び復号化における鍵長であって、鍵長を任意に選択することができるので、必要に応じて暗号データの安全性を任意に選択可能とすることができる。特に、安全性を高めたければ拡大次数mをできるだけ大きくするだけでよく、暗号データの解読行為に対して極めて容易に対応できる。
【0028】
しかも、拡大次数kmの拡大体を定義体として用いることにより、乗算を、所定の元の加算または減算と、乗算との繰り返しに分解して演算することができ、並列処理化が容易であって、高速演算を可能とすることができる。
【0029】
さらに、k=2k'となるk'を用いた場合には、所定の元の加算または減算と、乗算との繰り返し回数を削減できることにより、演算のさらなる高速化を図ることができる。
【図面の簡単な説明】
【0030】
【図1】本発明に係る暗号化/復号化装置のブロック図である。
【図2】本発明に係る暗号化/復号化プログラムにおけるフローチャートである。
【図3】本発明に係る暗号化/復号化プログラムにおけるフローチャートである。
【図4】他の実施形態のフローチャートである。
【図5】既約多項式を求めるフローチャートである。
【符号の説明】
【0031】
10 演算器
20 不揮発性記憶部
30 揮発性記憶部
40 データ入出力部
50 データバス
【発明を実施するための最良の形態】
【0032】
本発明の暗号化/復号化プログラム、暗号化/復号化装置、及び拡大体の乗算装置では、素数pを標数とする拡大体を定義体とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を乗算して元C={c0,c1,c2,・・・,cm-1}を生成する際に、拡大次数mに対応し、km+1が素数であって、Fkm+1でpが原始元となる正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmを新たな定義体として乗算を行い、この乗算の結果を用いて部分体である拡大次数mの拡大体Fpmの元における乗算の結果を求めている。
【0033】
すなわち、任意の拡大次数mに対応して、km+1が素数であって、Fkm+1でpが原始元となる正整数kを用いることにより、素数pを標数とする拡大次数mの拡大体Fpmを部分体とする拡大次数kmの拡大体Fpkmを定義体として用いることができ、拡大次数m及び標数pを任意としても2つの元A、Bの乗算を行うことができる。
【0034】
ここで、拡大次数mは、暗号化及び復号化における鍵長に当たり、任意の拡大次数mが選択できるということは、鍵長を任意に選択できることを示しており、必要に応じて適宜の鍵長として暗号データを生成することができる。
【0035】
したがって、状況に応じて鍵長を選択することにより、暗号データの安全性と、暗号化及び復号化の演算の負荷をバランスさせながら適宜の鍵長とした暗号データを生成できる。
【0036】
例えば、標数p=2500-863の500ビットの素数を用いた場合には、下表に示すように、拡大次数m、パラメータとなる正整数k、鍵長の組み合わせを選択できる。
【表1】
JP0004836208B2_000002t.gif

【0037】
ここで、鍵長が短くなる組み合わせを用いれば、暗号化及び復号化の演算速度を向上させることができ、鍵長が長くなる組み合わせを用いれば、解読困難な暗号化データを生成して安全性を向上させることができる。
【0038】
特に、拡大次数mは、任意な正整数とすることができ、いくらでも大きくすることもできる。また、標数pも任意の素数とすることができる。
【0039】
なお、暗号化に必要となる鍵は、Diffie-Hellman鍵交換アルゴリズムを用いて受け渡すことにより、安全に受け渡すことができる。
【0040】
すなわち、アリスとボブが鍵交換を行う場合、まず、アリスからボブに鍵データとしてg,A=ga∈Fpmを送信している。
【0041】
ボブは、Aを受信すると、C=Ab=gab∈Fpmを計算して、B=gb∈Fpmを計算し、B=gbをアリスに送信している。
【0042】
アリスは、Bを受信してC=Ba=gab∈Fpmを計算することにより、アリスとボブとを接続するネットワーク上に鍵gabを流すことなく共有することができる。
【0043】
なお、ICカードにおける認証用データに用いる鍵の場合には、ICカードの作成時にあらかじめICカードに鍵データを記憶させておくことにより、ネットワーク上に鍵を流すことなく共有することができる。
【0044】
あるいは、一般的な公開鍵暗号の場合であれば、ボブがアリスから所要のデータを受け取る際に、ボブは予め公開鍵を公開しておく。
【0045】
例えば、Elgamal暗号の場合であれば、ボブは秘密鍵sを用いて、g,B=gs∈Fpmを計算して公開しておく。
【0046】
メッセージMを送信するアリスは、ボブの公開鍵データg,Bをダウンロードして、メッセージMに対して、
C1=M×Bt、 C2=gt
を計算することにより暗号化を行っている。ここで、tは乱数である。
【0047】
また、C1の演算を行うに当たり、後述する本発明の暗号化/復号化プログラム、暗号化/復号化装置、あるいは拡大体の乗算装置を用いている。
【0048】
アリスは、C1、C2をボブに送信し、ボブは、受信したC1、C2を用いて、C1/C2sを演算することによりメッセージMの復号化を行っている。すなわち、
C1/C2s=MBt/gts=Mgts/gts
【0049】
この復号化においても、後述する本発明の暗号化/復号化プログラム、暗号化/復号化装置、あるいは拡大体の乗算装置を用いている。
【0050】
このようにメッセージMの復号化は、sを秘密にもつボブのみが行える計算であり、対称鍵暗号のようにある一つのパスワードを互いに共有する必要がなく、かつ安全性が確保される長さの鍵を使用することで高い信頼性を有することができる。
【0051】
図1は、本実施形態の暗号化/復号化装置のブロック図である。なお、この暗号化/復号化装置は拡大体の乗算装置でもある。
【0052】
暗号化/復号化装置は、CPU(中央演算装置)などの演算器10と、この演算器10が実行するプログラムなどを記憶した不揮発性記憶部20と、プログラムの実行にともなって必要となるデータを一時的に格納する揮発性記憶部30とを備えている。不揮発性記憶部20は、いわゆるROM(Read Only Memory)あるいはハードディスクなどの不揮発性の記憶手段で構成し、揮発性記憶部30はいわゆるRAM(Random Access Memory)で構成している。
【0053】
特に、揮発性記憶部30は、複数のレジスタを備えており、それぞれのレジスタで所要のデータを記憶している。
【0054】
不揮発性記憶部20には、本実施形態の暗号化/復号化プログラムを記憶しており、この暗号化/復号化プログラムを起動させることにより、必要に応じて暗号化/復号化プログラムを揮発性記憶部30に展開して、暗号化あるいは復号化の演算を行っている。
【0055】
さらに、暗号化/復号化装置にはデータ入出力部40を設けており、このデータ入力部40を介して任意の拡大次数mの値を入力可能とし、入力された拡大次数mの値に基づいて暗号化を実行可能としている。あるいは、拡大次数mの値だけでなく、標数pの値を変更可能とすることもできる。
【0056】
また、データ入出力部40では、公開鍵となる鍵データの出力や、暗号化されたデータの入出力などを行っている。図1中、50はデータバスである。
【0057】
演算器10では、必要に応じて、揮発性記憶部30に記憶されている所要の鍵データ、標数pの値、拡大次数mなどを不揮発性記憶部20に記憶させてもよい。
【0058】
暗号化/復号化装置あるいは拡大体の乗算装置は、このように暗号化/復号化プログラムを実行する電子計算機などの装置に限定するものではなく、暗号化/復号化プログラムに相当する演算を実行する演算回路を備えた演算用デバイスとして、演算処理の高速化を図ることもできる。
【0059】
以下において、暗号化あるいは復号化における2つの元の乗算について説明する。
【0060】
まず、第1実施形態として、以下の条件下における元Aと元Bの積の演算について説明する。ここで、この積の演算が暗号化である場合には、元Aと元Bのいずれか一方が暗号化鍵であって、他方が暗号化鍵の鍵長ごとに分断された単位長平文データであり、積の演算が復号化である場合には、元Aと元Bのいずれか一方が復号化鍵であって、他方が復号化鍵の鍵長ごとに分断された単位長暗号データである。
【0061】
・素数pを標数とする拡大体を定義体とする。
・拡大次数mに対し、km+1が素数であって、Fkm+1でpが原始元となる適当な正整数k。
・0≦i≦m-1、0≦j≦k-1。
・<x>がxのmod(km+1)をとるものとする。
・ωを1の原始km+1乗根とする。
・{a0,a1,a2,・・・,am-1}を拡大次数mの拡大体Fpmの元A
【数1】
JP0004836208B2_000003t.gif
・{b0,b1,b2,・・・,bm-1}を拡大次数mの拡大体Fpmの元B
【数2】
JP0004836208B2_000004t.gif

【0062】
なお、任意の正整数mに対して、km+1が素数となる正整数kが少なくともk<mの範囲に存在していることは一般的に証明済みの事実であり、正整数kを特定する専用プログラムを用いて容易に見つけ出すことができる。
【0063】
通常、元Aと元Bの積C=ABは、CVMA(Cyclic Vector Multiplication Algorithm)で計算されるが、部分体における演算の閉性から元Aと元Bの積Cも部分体Fpmの元なることから、積Cのベクトル表現においても、基底ベクトルω'とω”のベクトル係数が等しくなる。
【0064】
ここで、表記の便宜上、
【数3】
JP0004836208B2_000005t.gif
及び、
【数4】
JP0004836208B2_000006t.gif
である。
【0065】
したがって、求める必要があるのは0≦i≦m-1でのω'の各係数ciのみであり、
【数5】
JP0004836208B2_000007t.gif
として、係数ciは、図2に示すフローチャートに基づく暗号化/復号化プログラムにより、パーソナルコンピュータなどの電子計算機での演算によって求めることができる。
【0066】
ただし、この場合、直接、8p|m(p-1)となる拡大体を構成することはできない。そこで、8p|m(p-1)となる拡大体を構成する場合には、拡大次数mの偶数因数部分mEと奇数因数部分mOとに分けて(m=mE・mO)、それぞれを逐次拡大体に分けて拡大することにより、8p|m(p-1)となる拡大体にも対応可能とすることができる。なお、場合によっては後述する第2実施形態を組み合わせて用いることが必要となることもある。
【0067】
暗号化の場合には、まず、電子計算機では拡大次数mを設定する(ステップS1)。なお、復号化の場合には、電子計算機は、秘密鍵または公開鍵の鍵長から拡大次数mを特定することもできる。
【0068】
次いで、電子計算機は、設定された拡大次数mに基づいて、km+1が素数であって、Fkm+1でpが原始元となる適当な正整数kを専用プログラムを用いて特定する(ステップS2)。なお、前述したように、k<mの範囲でkm+1が素数となる正整数kは少なくとも1つは特定でき、電子計算機は、比較的短時間で正整数kの特定処理を終了することができる。
【0069】
次いで、電子計算機は、0≦t≦k-1で、<p>=K[t]となる各K[t]をそれぞれ求め(ステップS3)、さらに、0≦i≦kmで、それぞれ0=q[]とする(ステップS4)。
【0070】
次いで、電子計算機は、0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求め(ステップS5)、その後、0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k-1でq[<p+(pjK[t])>]へのMの足し込みをそれぞれ行う(ステップS6)。
【0071】
その後、電子計算機は、拡大次数mの拡大体Fpmではなく、拡大次数kmの拡大体を定義体として用いていることによる処理として、0≦i≦m-1で、かつ1≦t≦k-1で、q[<p>]へのq[<(pK[t])>]の足し込みをそれぞれ行って(ステップS7)、最後に、0≦i≦m-1で、kq[<0>]-q[<p>]=ciを求めている(ステップS8)。
【0072】
このように、ciは、拡大次数kmの拡大体Fpkmにおける所定の元の加算または減算と、乗算との繰り返しに分解して演算を行うことができ、並列処理化が容易であって、高速演算を可能とすることができる。
【0073】
特に、演算の負荷が小さいことにより、携帯電話機やICカードなどの演算機能の乏しい装置でも容易に乗算処理を実行でき、しかも公開鍵及び秘密鍵の鍵長の変更を可能とすることができる。
【0074】
さらに、乗算処理における演算は、演算処理回路として半導体基板上に形成して乗算処理用半導体デバイスとすることもでき、この乗算処理用半導体デバイスを備えた暗号化/復号化装置として、暗号化及び復号化のさらなる高速化を図ることができ、しかも、並列処理化が可能であって、一層の高速化を図ることができる。また、拡大体の乗算装置として乗算処理用半導体デバイスを用いることもできる。
【0075】
すなわち、乗算処理用半導体デバイスでは、半導体基板上に、所要の演算を実行可能とした演算器を形成するとともに、各記憶部として以下のレジスタ及びレジスタ群を形成している。
・標数pを記憶するレジスタ。
・拡大次数mを記憶するレジスタ。
・拡大次数mに基づく拡大体Fpmの元Aを記憶するレジスタ群。
・拡大次数mに基づく拡大体Fpmの元Bを記憶するレジスタ群。
・設定された拡大次数mに対応した正整数kを特定して記憶するレジスタ。
・0≦t≦k-1で、<p>=K[t]となる各K[t]をそれぞれ求めて記憶するレジスタ群。
・0≦i≦km-1で、それぞれ0=q[]として記憶するレジスタ群。
・0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めて記憶するレジスタ群。
・0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶するレジスタ群。
・0≦t≦k-1でq[<p+(pjK[t])>]にMをそれぞれ足し込んで記憶するレジスタ群。
・0≦i≦m-1で、かつ1≦t≦k-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込んで記憶するレジスタ群。
・0≦i≦m-1で、kq[<0>]-q[<p>]=ciをそれぞれ求めて記憶するレジスタ群。
【0076】
これらのレジスタ及びレジスタ群を設けることにより、各演算は並列化が可能であるので、並列処理を行うことにより乗算処理をさらに高速化することができる。したがって、高速な暗号化及び復号化を可能とする暗号化/復号化装置、あるいは拡大体の乗算装置を提供できる。
【0077】
この乗算処理用半導体デバイスを所要の実装ボードに装着することにより、高速な乗算処理を可能とする実装ボードを提供でき、この実装ボードを用いて携帯電話機や電子計算機などを構成することにより、高速な暗号化及び復号化が可能であって、しかも公開鍵及び秘密鍵の鍵長の長さを自在に可変とした携帯電話機や電子計算機などを提供することができる。
【0078】
以下において、第2実施形態として、以下の条件下における元Aと元Bの積の演算について説明する。ここで、第1実施形態との違いは、k=2k'となるk'を用いて演算を行うことである。すなわち、
・素数pを標数とする拡大体を定義体とする。
・拡大次数mに対し、2k'm+1が素数であって、F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる適当な正整数k'。
・0≦i≦m-1、0≦j≦2k'-1。
・<x>がxのmod(2k'm+1)をとるものとする。
・ωを1の原始2k'm+1乗根として、τ=ω+ω-1とする。
・{a0,a1,a2,・・・,am-1}を拡大次数mの拡大体Fpmの元A
【数6】
JP0004836208B2_000008t.gif
・{b0,b1,b2,・・・,bm-1}を拡大次数mの拡大体Fpmの元B
【数7】
JP0004836208B2_000009t.gif

【0079】
部分体における演算の閉性から元Aと元Bの積Cも部分体Fpmの元なることから、積Cのベクトル表現においても、基底ベクトルτ'とτ”のベクトル係数が等しくなる。
【0080】
ここで、表記の便宜上、
【数8】
JP0004836208B2_000010t.gif
及び、
【数9】
JP0004836208B2_000011t.gif
である。
【0081】
したがって、求める必要があるのは0≦i≦m-1でのτ'の係数ciのみであり、
【数10】
JP0004836208B2_000012t.gif
として、係数ciは、図3に示すフローチャートに基づくプログラムにより、パーソナルコンピュータなどの電子計算機での演算によって求めることができる。
【0082】
ただし、この場合には、4p|m(p-1)となる拡大体を構成することはできない。そこで、4p|m(p-1)となる拡大体を構成する場合には、拡大次数mの偶数因数部分mEと奇数因数部分mOとに分けて(m=mE・mO)、それぞれを逐次拡大体に分けて拡大することにより、4p|m(p-1)となる拡大体にも対応可能とすることができる。なお、場合によっては前述した第1実施形態を組み合わせて用いることが必要となることもある。
【0083】
暗号化の場合には、まず、電子計算機では拡大次数mを設定する(ステップT1)。なお、復号化の場合には、電子計算機は、秘密鍵または公開鍵の鍵長から拡大次数mを特定する。
【0084】
次いで、電子計算機は、設定された拡大次数mに基づいて、2k'm+1が素数であって、F2k'm+1でpが原始元あるいは位数がk'mかつk'mが奇数となる適当な正整数k'を専用プログラムを用いて特定する(ステップT2)。なお、前述したように、2k'<mの範囲で2k'm+1が素数となる正整数k'は少なくとも1つは特定でき、電子計算機は、比較的短時間で正整数k'の特定処理を終了することができる。
【0085】
次いで、電子計算機は、0≦t≦k'-1で、<p>=K[t]となる各K[t]をそれぞれ求め(ステップT3)、さらに、0≦i≦2k'mで、それぞれ0=q[]とする(ステップT4)。
【0086】
次いで、電子計算機は、0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求め(ステップT5)、その後、0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k'-1でq[<p+(pjK[t])>]へのMの足し込みをそれぞれ行うとともに、q[<p-(pjK[t])>]へのMの足し込みをそれぞれ行う(ステップT6)。
【0087】
その後、電子計算機は、拡大次数mの拡大体Fpmではなく、拡大次数k'mの拡大体を定義体として用いていることによる処理として、0≦i≦m-1で、かつ1≦t≦k-1で、q[<p>]へのq[<(pK[t])>]の足し込みをそれぞれ行うとともに、q[<p>]へのq[<-(pK[t])>]の足し込みをそれぞれ行って(ステップT7)、電子計算機は、最後に、0≦i≦m-1で、-q[<p>]=ciを求めている(ステップT8)。
【0088】
このように、ciは、所定の元の加算または減算と、乗算との繰り返しに分解して演算を行うことができ、並列処理化が容易であって、高速演算を可能とすることができる。
【0089】
また、図3に示したフローチャートの乗算処理の演算も、演算処理回路として半導体基板上に形成して乗算処理用半導体デバイスとすることもでき、この乗算処理用半導体デバイスを備えた暗号化/復号化装置として、暗号化及び復号化のさらなる高速化を図ることができ、しかも、並列処理化が可能であって、一層の高速化を図ることができる。また、拡大体の乗算装置として乗算処理用半導体デバイスを用いることもできる。
【0090】
この場合、乗算処理用半導体デバイスでは、半導体基板上に、所要の演算を実行可能とした演算器を形成するとともに、各記憶部として以下のレジスタ及びレジスタ群を形成している。
・標数pを記憶するレジスタ。
・拡大次数mを記憶するレジスタ。
・拡大次数mに基づく拡大体Fpmの元Aを記憶するレジスタ群。
・拡大次数mに基づく拡大体Fpmの元Bを記憶するレジスタ群。
・設定された拡大次数mに対応した正整数k'を特定して記憶するレジスタ。
・0≦t≦k'-1で、<p>=K[t]となる各K[t]をそれぞれ求めて記憶するレジスタ群。
・0≦i≦2k'm-1で、それぞれ0=q[]として記憶するレジスタ群。
・0≦i≦m-1で、aibimodp=q[<p>]をそれぞれ求めて記憶するレジスタ群。
・0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶するレジスタ群。
・0≦t≦k'-1でq[<p+(pjK[t])>]にMをそれぞれ足し込し込んで記憶するとともに、q[<p-(pjK[t])>]にMをそれぞれ足し込んで記憶するレジスタ群。
・0≦i≦m-1で、かつ1≦t≦k'-1で、q[<p>]にq[<(pK[t])>]をそれぞれ足し込んで記憶するとともに、さらに、q[<p>]にq[<-(pK[t])>]をそれぞれ足し込んで記憶するレジスタ群。
・0≦i≦m-1で、-q[<p>]=ciをそれぞれ求めて記憶するレジスタ群。
【0091】
これらのレジスタ及びレジスタ群を設けることにより、第1の実施形態の場合と同様に、各演算は並列化が可能であるので、並列処理を行うことにより乗算処理をさらに高速化することができる。したがって、高速な暗号化及び復号化を可能とする暗号化/復号化装置、あるいは拡大体の乗算装置を提供できる。
【0092】
さらに、km+1を素数とし、Sをmod km+1における位数kの部分巡回乗法群として、km次のAOP(All One Polynominal)(xkm+1-1)/(x-1)の零点をωとして、
【数11】
JP0004836208B2_000013t.gif
で与えられるγを用い、次の集合を考える。
【数12】
JP0004836208B2_000014t.gif

【0093】
[数12]の集合が拡大体Fpmにおいて正規基底を成すことは、km/eがmと互いに素となることと必要十分である。ここで、eはpのmod km+1での位数である。前述した第1実施形態及び第2実施形態は、この正規基底を用いた乗算に適用可能となっている。
【0094】
すなわち、
・eをFkm+1における元pの位数とする。
・e'=km/e
・1の原始k乗根ε∈Fkm+1とする。
・{a0,a1,a2,・・・,am-1}を拡大次数mの拡大体Fpmの元A
【数13】
JP0004836208B2_000015t.gif
・{b0,b1,b2,・・・,bm-1}を拡大次数mの拡大体Fpmの元B
【数14】
JP0004836208B2_000016t.gif

【0095】
このとき、部分体における演算の閉性から元Aと元Bの積Cは、
【数15】
JP0004836208B2_000017t.gif
として、係数ciは、図4に示すフローチャートに基づくプログラムにより、パーソナルコンピュータなどの電子計算機での演算によって求めることができる。
【0096】
ここで、暗号化の場合には、まず、電子計算機では拡大次数mを設定する(ステップU1)。なお、復号化の場合には、電子計算機は、秘密鍵または公開鍵の鍵長から拡大次数mを特定する。
【0097】
次いで、電子計算機は、設定された拡大次数mに基づいて、km+1が素数であって、e'(=km/e)とmとが互いに素となる適当な正整数kを専用プログラムを用いて特定する(ステップU2)。正整数kの特定にともなって、1の原始k乗根のεを特定する(ステップU3)。
【0098】
次いで、電子計算機は、1=K[0],0=r[0]とする(ステップU4)。
【0099】
次いで、電子計算機は、0≦i≦mで、0=q[]とする(ステップU5)。
【0100】
次いで、電子計算機は、1≦t≦k-1で、<K[t-1]ε>=K[t]とする(ステップU6)。
【0101】
次いで、電子計算機は、0≦t≦m-1であって、0≦t≦k-1で、i+1=r[<pK[t]>]とする(ステップU7)。
【0102】
次いで、電子計算機は、0≦t≦m-1で、aibimodp=q[i+1]をそれぞれ求める(ステップU8)。
【0103】
次いで、電子計算機は、0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k-1でq[r[<p+(pjK[t])>]]へのMの足し込みをそれぞれ行う(ステップU9
)。
【0104】
最後に、電子計算機は、0≦i≦m-1で、kq[<0>]-q[i+1]=ciを求めている(ステップU10)。
【0105】
なお、kが偶数の場合には、ステップU9においてkq[<0>]=0とすることができる。
【0106】
このように、より多くの正規基底に対して適用可能とすることができる。しかも、kの値をより小さくすることができるので、演算回数の削減による演算処理の高速化を図ることもできる。
【0107】
なお、前述したように、8p|m(p-1)あるいは4p|m(p-1)などのように、mがpの倍数である場合には拡大体を構成できないことがあるが、拡大次数mを偶数因数部分mEと奇数因数部分mOとに分けて、それぞれを逐次拡大体に分けて拡大することにより、奇標数pに対しての拡大体の構成を可能とすることができ、上記の制限を排除することができる。
【0108】
すなわち、例えば、Fp4pを構成する場合を考える。この場合には、最初にFp4の拡大体を構成し、次いで、この拡大体をp次逐次拡大することにより、奇標数pが4と互いに素であることからFp4pで表される拡大体を構成できる。すなわち、任意の奇標数及び任意次数の拡大体を構成することが可能である。
【0109】
本発明は数学的に見た場合には、既約多項式として法多項式を準備することなく拡大体における乗算や除算を行えるものであり、見方を変えれば本発明の考え方を利用することにより、任意次数の既約多項式を生成することができることを示している。
【0110】
ここで、例えばFp4の(1,2,1,2)というベクトル表現を持つ元はFp2の元である。真部分体に含まれないような元を真性元と呼ぶこととして、Fpmの真性元をαとした場合、そのαの最小多項式、すなわちαを零点にもつFp上の最小次数の多項式Mα(x)が求まれば、それはFp上のm次既約多項式となっている。
【0111】
なお、Mα(x)は、次式で表される。
【数16】
JP0004836208B2_000018t.gif

【0112】
ここで、次式の計算式を考えることにする。
【数17】
JP0004836208B2_000019t.gif
【数18】
JP0004836208B2_000020t.gif

【0113】
上式で、i=m-2,m-3,・・・,2,1,0の順に計算されることにより既約多項式が求められることとなる。
【0114】
すなわち、拡大体Fpmの任意の真性元αの最小多項式は、図5に示すフローチャートに基づくプログラムにより、下のようにして求めることができる。
【0115】
まず、電子計算機では、真性元αのベクトル表現(x0,x1,x2,・・・,xm-1)を設定する(ステップW1)。ここで、真性元αの最小多項式Mα(x)は次式となるものとする。
【数19】
JP0004836208B2_000021t.gif

【0116】
次いで、電子計算機は、1≦i≦mで、T[i]=Tr(αi)とし(ステップW2)、a[m-1]=-T[1]とする(ステップW3)。
【0117】
次いで、電子計算機は、m-2≧i≧0で、0=Mとし、0≦j≦m-1-iで、-a[m-j]Tr(αm-i-j)のMへの足し込みをそれぞれ行う(ステップW4)。
【0118】
次いで、電子計算機は、a[i]=(m-i)-1{M-Tr(αm-i)}を求めている(ステップW5)。
【0119】
これにより、p>mを満たす任意の既約多項式を求めることができる。なお、前述した処理は、素体Fpではない部分体に関する最小多項式の特定に用いることもできる。
【0120】
このように任意の既約多項式を求めることができることによって、異なる定義体間の基底変換を可能とすることができる。
【0121】
基底変換を行うためには変換行列を特定する必要があるが、ここで変換行列を生成したい拡大体F'pmがあり、これと同型の拡大体としてFpmを考える。なお、本明細書においては、数学において通常使用されている「^」記号付きの表現が利用できないため、以下においては「^」の代わりに「’」を代用している。
【0122】
第1実施形態の方法を用いた基底変換行列の生成方法を考える。このとき、パラメータkによって(xkm+1-1)/(x-1)という法多項式を考え、その零点ωを用いて次式で表されるγを考え、このγを用いて次式の正規基底を考える。ここで、ωはFpkmに真性元として存在する。
【数20】
JP0004836208B2_000022t.gif
【数21】
JP0004836208B2_000023t.gif

【0123】
このγに相当する元γ’を拡大体F'pmの中から見つけることができれば拡大体F'pmにおける正規基底を特定し、基底間での対応関係から変換行列を特定することができる。この変換行列の逆行列を求めれば基底変換を可能とすることができる。
【0124】
ここで、元γ’を求めるためにはωに相当するω’を拡大体F'pkmにおいて特定すればよく、ω’を拡大体F'pkmにおいて特定するためには拡大体F'pmをk次逐次拡大してFpkmと同型なF'pkmを構成する。
【0125】
ここで、kとmが互いに素になるようにして、
(1)k'k+1が素数である。
(2)pのFk'k+1における位数がk'kである(すなわち原始元である)
ことを満たすk'を求めることができると、(xk'k+1-1)/(x-1)を法として、F'pmをk次逐次拡大してF'pmkを構成することができる。ここで、「k'」の「'」は「^」の代用ではない。
【0126】
この逐次拡大体F'pkmから次式を満たす元B'を探し、ω'を求める。
【数22】
JP0004836208B2_000024t.gif

【0127】
ここで、ω'は位数km+1の元となるので、Fpkmの位数km+1の元ωに対応することとなる。
【0128】
したがって、次式で与えられる元γ’により以下の集合を考えると、この集合をFpmの基底と対応づけることができる。これを用いて変換行列及びその逆行列を求めることができ、基底変換を可能とすることができる。
【数23】
JP0004836208B2_000025t.gif
【数24】
JP0004836208B2_000026t.gif

【0129】
このように基底変換が可能なことから、既約多項式の因数分解を可能とすることができる。
【0130】
すなわち、まず、Fp上のm次既約多項式f(x)を考え、その零点θ'による多項式基底{1,θ',θ'2,・・・,θ'm-1}を用いてF'pmを構成することができる。ここで、「'」は「^」による表示の代わりに用いている。
【0131】
そして、F'pmの元θ'を基底変換行列によってFpmの対応する元θに写像すれば、Fp上のm次既約多項式f(x)の1つの解をFpm上で求めたこととなる。
【0132】
したがって、共役元まで考えれば、f(x)をFpm上で因数分解できることとなるので、任意の拡大体上で因数分解できることとなる。
【産業上の利用可能性】
【0133】
パーソナルコンピュータや携帯電話、あるいはICチップ付きのクレジットカードのように、他の機器とデータの送受信が行われる機器において、鍵長を任意に変更可能として、要求される安全性と、暗号化または復号化の処理負荷を調整ながら、暗号化データの送受信を可能とする。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4