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

暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置 コモンズ 新技術説明会 外国出願あり

国内特許コード P110005386
掲載日 2011年8月18日
出願番号 特願2008-526767
登録番号 特許第4836208号
出願日 平成19年7月24日(2007.7.24)
登録日 平成23年10月7日(2011.10.7)
国際出願番号 JP2007064474
国際公開番号 WO2008013154
国際出願日 平成19年7月24日(2007.7.24)
国際公開日 平成20年1月31日(2008.1.31)
優先権データ
  • 特願2006-200946 (2006.7.24) JP
  • 特願2007-010072 (2007.1.19) JP
発明者
  • 野上 保之
  • 森川 良孝
出願人
  • 国立大学法人 岡山大学
発明の名称 暗号化/復号化プログラム、暗号化/復号化装置及び拡大体の乗算装置 コモンズ 新技術説明会 外国出願あり
発明の概要

任意な鍵長を選択可能としながら高速に拡大体の乗算処理を実行可能とした暗号化/復号化プログラム、暗号化/復号化装置、及び拡大体の乗算装置を提供する。
素数pを標数とし、拡大次数mの拡大体Fpmの2つの元A={a0,a1,a2,・・・,am-1}、B={b0,b1,b2,・・・,bm-1}を乗算する際に、km+1が素数であって、Fkm+1でpが原始元となる正整数kを特定し、2つの元A,Bを、正整数kを用いて素数pを標数とする拡大次数kmの拡大体Fpkmにおける2つの元として演算し、この演算結果を用いて部分体である拡大次数mの拡大体Fpmの元における乗算の結果を求める。

従来技術、競合技術の概要


従来、インターネットなどの電気通信回線を利用した情報通信において、送受信されるデータの秘匿性を保持するために、データの暗号化が行われている。すなわち、平文データを送信する送信者は、平文データに暗号化処理を施して暗号データを生成し、この暗号データを受信者に送信している。一方、暗号データを受信した受信者は、暗号データに復号化処理を施して平文データを生成することにより、平文データを受け取ることができる。



このような暗号化及び復号化の方法として、昨今では公開鍵暗号と呼ばれる方法が用いられている。公開鍵暗号では、公開鍵と秘密鍵があらかじめ設定され、所定の平文データを送信する送信者に公開鍵を開示しており、送信者は公開鍵を用いて平文データを暗号化することにより暗号データを生成し、受信者に送信している。受信者は、暗号データを受信すると、秘密鍵を用いて暗号データを復号化して平文データを生成している。



ここで、平文データを暗号化する場合には、平文データを暗号化に用いる公開鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長平文データを生成し、各単位長平文データと公開鍵を用いて乗算処理を行うことにより単位長暗号データを生成し、所定数の単位長暗号データで構成された暗号データを生成している。



一方、暗号データを復号化する場合には、暗号データを復号化に用いる秘密鍵の鍵長に合わせた所定のデータ長ごとに分断して複数の単位長暗号データを生成し、各単位長暗号データと秘密鍵を用いて乗算処理を行うことにより単位長平文データを生成し、所定数の単位長平文データで構成された平文データを生成している。



このような公開鍵暗号には様々な方式が提案されており、Rivest Shamir Adleman(RSA)暗号、楕円曲線暗号、ElGamal暗号などが知られている。



昨今、パーソナルコンピュータなどの電子計算機の性能向上にともなって、各種の暗号方法で暗号化された暗号データが解読されるおそれが高まっている。すなわち、暗号データは、秘密鍵さえ分かれば解読できることから、電子計算機によって手当たり次第に秘密鍵を生成して復号化を試みることにより、時間はかかるものの解読されるおそれがあった。



そこで、各暗号方法では、安全性を高めるために公開鍵及び秘密鍵の鍵長を長くすることが行われている。すなわち、公開鍵及び秘密鍵の鍵長を長くすると、解読に用いる秘密鍵の数が飛躍的に増大し、現実的な時間内での解読を不可能とすることができるからである。そのため、現在では、RSA暗号では1024ビット以上、楕円曲線暗号では160ビット以上、ElGamal暗号では1024ビット以上の鍵長が求められている。



しかしながら、公開鍵及び秘密鍵の鍵長を長くした場合には、公開鍵を用いた乗算処理による暗号化、及び秘密鍵を用いた乗算処理による復号化に多大な時間を要することとなっていた。この場合、処理時間の短縮のためには、乗算処理の演算速度が高速な演算手段が必要となることにより、安全性を高めるためのコストが増大することとなっていた。



一方で、現実的には、電気通信回線中を流れているデータにおいては重要度が様々に異なっており、利用価値が高いために高度の秘匿性が必要なデータから、利用価値が低いために秘匿性を必要としないデータまでが存在している。



したがって、何れのデータに対しても同等の安全性で暗号化する必要はなく、高い安全性が要求されるデータには長い鍵長の公開鍵及び秘密鍵を用い、高い安全性が要求されないデータには短い鍵長の公開鍵及び秘密鍵が用いられている。



また、パーソナルコンピュータなどのような高速な演算処理の実行が可能な装置では、できるだけ長い鍵長の公開鍵及び秘密鍵による暗号化が利用されており、携帯電話機やICカードなどのような演算処理能力の乏しい装置では、比較的短い鍵長の公開鍵及び秘密鍵による暗号化が利用され、保証され得る安全性の範囲内でデータの送受信が行われている。



特に、パーソナルコンピュータなどの電子計算機では、複数種類の鍵長の公開鍵及び秘密鍵が利用可能となっており、送信するデータに応じた安全性、あるいは送信先の装置における乗算処理の処理能力などに応じて鍵長を変えて暗号化することも行われており、鍵長に汎用性を持たせることが提案されている(例えば、特許文献1参照。)。

【特許文献1】特開2001-051832号公報

産業上の利用分野


本発明は、暗号化/復号化プログラム、暗号化/復号化装置、及び暗号化または復号化における乗算処理を実行する拡大体の乗算装置に関する。

特許請求の範囲 【請求項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で、<pmt>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦kmで、それぞれ0=q[<i>]とするステップと、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込むステップと
を有することを特徴とする請求項1記載の暗号化/復号化プログラム。
【請求項3】
前記第3のステップは、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、kq[<0>]-q[<pi>]=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で、<pmt>=K[t]となる各K[t]をそれぞれ求めるステップと、
0≦i≦2k'mで、それぞれ0=q[<i>]とするステップと、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めるステップと、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて、0≦t≦k'-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込むとともに、q[<pi-(pjK[t])>]にMをそれぞれ足し込むステップと
を有することを特徴とする請求項1記載の暗号化/復号化プログラム。
【請求項5】
前記第3のステップは、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込むステップと、
0≦i≦m-1で、-q[<pi>]=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で、<pmt>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦kmで、それぞれ0=q[<i>]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項6記載の暗号化/復号化装置。
【請求項8】
前記第5の記憶部は、
0≦i≦m-1で、かつ1≦t≦k-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、kq[<0>]-q[<pi>]=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で、<pmt>=K[t]となる各K[t]をそれぞれ求めて記憶する記憶部と、
0≦i≦2k'mで、それぞれ0=q[<i>]として記憶する記憶部と、
0≦i≦m-1で、aibimodp=q[<pi>]をそれぞれ求めて記憶する記憶部と、
0≦i<j≦m-1で、(ai-aj)(bi-bj)modp=Mをそれぞれ求めて記憶する記憶部と、
0≦t≦k'-1でq[<pi+(pjK[t])>]にMをそれぞれ足し込し込んで記憶するとともに、q[<pi-(pjK[t])>]にMをそれぞれ足し込んで記憶する記憶部と
を有することを特徴とする請求項6記載の暗号化/復号化装置。
【請求項10】
前記第5の記憶部は、
0≦i≦m-1で、かつ1≦t≦k'-1で、q[<pi>]にq[<(piK[t])>]をそれぞれ足し込むとともに、q[<pi>]にq[<-(piK[t])>]をそれぞれ足し込んで記憶する記憶部と、
0≦i≦m-1で、-q[<pi>]=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の記憶部と
を有することを特徴とする拡大体の乗算装置。
産業区分
  • その他通信
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2008526767thum.jpg
出願権利状態 権利存続中
特許内容に関しての問い合せ窓口は岡山大学連携機構知的財産部門です。

技術移転に関しては岡山TLOが窓口になります。


PAGE TOP

close
close
close
close
close
close
close