JPH0130148B2

JPH0130148B2 -

Info

Publication number: JPH0130148B2
Application number: JP59104228A
Authority: JP
Inventors: Toshihiko Namekawa; Masao Kasahara; Kinichiro Tokiwa; Choko Matsumi; Yutaka Nishikado; Masayasu Fujii
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1984-05-23
Filing date: 1984-05-23
Publication date: 1989-06-16
Also published as: JPS60247683A

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明は、情報を複数の分割情報に分散管理
し、前記分割情報を暗号化することで保護するデ
ータ保護管理システムに関するものである。

〔従来の技術〕従来、この種の暗号化方式として、米国のデー
タ暗号化規格（DES）や公開鍵暗号方式がある
（例えば土井範久著、“米国のデータ暗号化規格
DES”、コンピユータ・サイエンス、bit Vol.13、
No.２、P4〜P15共立出版（1981）参照）。

米国のデータ暗号化規格（DES）は、元の情
報列を64ビツト毎のブロツクに分割してそれぞれ
を入力ブロツクとし、換字及び転置処理を施すこ
とにより、暗号化された64ビツトの出力情報を作
成するものである。すなわち、入力ブロツクに対
し、64ビツトの鍵を使うことにより暗号文を作り
出すものである。DESでは暗号化の鍵と復合化
の鍵は同一であるが、公開鍵暗号方式では、暗号
化と復合化の鍵が異なるため、暗合化の鍵は公開
される。

〔発明が解決しようとする課題〕

従来のこの種の暗合化方式は、以上のように構
成されていたので、１つの暗合化された情報とそ
れを復合化するための鍵さえあれば、元の情報列
を容易に再生できるという問題点があつた。

この発明は上記のような従来のものの問題点を
除去するためになされたもので、元の情報列を暗
合化された複数個の情報に分割し、それらの中か
ら元の情報列の情報量以上の分割情報を集めると
元の情報列が再生できるいわば情報を分割管理す
るデータ保護管理システムを提供することを目的
としている。

〔課題を解決するための手段〕

この発明に係るデータ保護管理システムは、元
の情報列から暗合化された複数の分割情報を作成
する情報分割手段を設けると共に、元の情報列の
情報量以上の上記分割情報より元の情報列を再生
する、つまり、分割情報の情報量の和が元の情報
列の情報量以上となるとき再生する情報再生手段
を設けたものである。

〔作用〕

この発明におけるデータ保護管理システムは、
元の情報列の機密性を保持するために、上記情報
分割手段により、暗合化された複数の情報を分散
して管理することを可能にする。又、分割された
情報の紛失、盗難等による情報の再現性、あるい
は改ざんノイズ誤りに対する誤り検出及び訂正能
力等を向上させるために、上記情報再生手段によ
り、元の情報列の情報量以上の分割情報から元の
情報を再生することを可能にする。

〔発明の実施例〕

以下、この発明の一実施例を図について説明す
る。第１図において、１は元の情報列ｆ（ｘ）と
して用いるデータ・ベース、２はＮ個に分割さ
れ、暗合化して分割管理される分割情報、３はＮ
個の分割情報２中Ｋ個以上により再生されるデー
タ・ベース、４は元の情報列ｆ（ｘ）をＮ個に分
割する情報分割手段、５はＫ個以上の分割情報２
より元の情報列ｆ（ｘ）を再生する情報再生手段
である。情報分割手段４は、第２図に示すように
並列に元の情報列ｆ（ｘ）を入力し、互いに素な
GF2上の多項式m_i（ｘ）で割つた余りを分割情報
a_i（ｘ）として出力する第１のGF2除算器６から
なり、情報再生手段５は第３図に示すように、分
割情報a_i（ｘ）を入力をする第１のGF2乗算器７、
GF2除算器８及び第２のGF2乗算器９を並列に配
し、加算器１０でGF2乗算器９の各出力を加算し
Ｍ（ｘ）（後述）で割つた余りを出力する第２の
GF2により元の情報列ｆ（ｘ）を出力する。ここ
で、上記情報分割手段２及び情報再生手段５の理
論的裏づけとして用いられる中国人の剰余定理に
ついて説明する。

(a) 整数における中国人の剰余定理について説明
する。

m_i（ｉ＝１、２、………、ｒ）を互いに素で
ある整数とし、Ｍ＝_r 〓ⁱ⁼¹ m_i とおく。この時、任意の整数a_i（ｉ＝１、２、…
……、ｒ）が与えられるとすると、 a_i≡ｆ（mod m_i）０≦ｆ＜Ｍを満たす整数ｆはただ１つ必ず存在する。

例えば、m₁＝５、m₂＝６、m₃＝７とすると、
Ｍ＝210となる。

つまりＮ＝３に分割する場合、m_i（ｉ＝１、
２、３、）の情報量は３（ビツト）であるから、３
つの分割情報a_iの情報量は２（ビツト）になるた
め、情報量５（ビツト）の元の情報を再生するた
め必要な分割情報の数はＫ＝３となり、 a₁＝２、a₂＝４、a₃＝１のとき、ｆ＝22とな
る。

すなわち、 22≡２（mod5） 22≡４（mod6） 22≡１（mod7）０≦22＜210 が成立する。

(b) 多項式における中国人の剰余定理について説
明する。

m_i（ｘ）（ｉ＝１、２、………、Ｎ）を互い
に素であるガロアフイールド２（GF2）上の多
項式とする。

Ｍ（ｘ）＝_K 〓ⁱ⁼¹ m_i（ｘ） ………(4) とおく。

任意の多項式a_i（ｘ）（ｉ＝１、２、………、
Ｎ）が与えれた時、 a_i（ｘ）≡ｆ（ｘ）（mod m_i（ｘ）） ………(5) 次数ｆ（ｘ）＜次数Ｍ（ｘ） ………(6) を満たす多項式の元の情報列ｆ（ｘ）はただ１つ
必ず存在する。

上記の多項式に拡張された中国人の剰余定理に
より次の関係を導くことができる。

ｆ（ｘ）をm_i（ｘ）（ｉ＝１、２、………、Ｎ）
で割つた余りをa_i（ｘ）とする。この時、ｆ（ｘ）
はＮ個のa_i（ｘ）の中から任意に選んだＫ個のa_i
（ｘ）（ｉ＝１、２、………、Ｋ）から次のように
再生できる。

f_i（ｘ）＝_K 〓ⁱ⁼¹ Ｍ（ｘ）／m_i（ｘ）・t_i（ｘ）・a_i（ｘ）（mod Ｍ（ｘ）） ………(7) 但し、 t_i（ｘ）は１≡Ｍ（ｘ）／m_i（ｘ）・t_i（ｘ）（mod m_i（ｘ））…
……(8) これらの関係式を第１図のシステムに対応させ
ると、m_i（ｘ）はＮ分割を特徴づける多項式、Ｋ
は再生個数、a_i（ｘ）はＮ個の分割情報２、ｆ
（ｘ）は元の情報列に対応する。

いま、m_i（ｘ）（ｉ＝１、２、………、Ｎ）が
すべてｄ次の多項式とすると、ｆ（ｘ）は式(4)と
式(6)の関係よりdK−１次の多項式すなわち、元
の情報列ｆ（ｘ）はdKビツトの情報量となる。ま
たa_i（ｘ）はm_i（ｘ）で割つた余りであることか
ら、ｄ−１次の多項式すなわち、分割情報２はｄ
ビツトの情報量となる。従つて、各分割情報２の
情報量は元の情報列ｆ（ｘ）のものの１／Ｋとな
つていることがわかる。

例えばＮ＝３とすると、互いに素の４次（ｄ＝
４）のGF2上の多項式を３つ選ぶ。

このとき、m_i（ｘ）（ｉ＝１、２、３）の情報
量はそれぞれ５（ビツト）で、３つの分割情報の
情報量は４（ビツト）となる。

m₁（ｘ）＝x⁴＋ｘ＋１ ………(9) m₂（ｘ）＝x⁴＋x²＋１ ………(10) m₃（ｘ）＝x⁴＋x³＋１ ………(11) 上記GF2上の多項式から情報分割手段４により
分割暗号化する。仮に１つのブロツク化した情報
列が情報量８（ビツト）10100011とすると、ｆ（ｘ）＝x⁷＋x⁵＋ｘ＋１と表わされる。また元の情報列の情報量は８（ビ
ツト）であるから再生に必要な分割情報は２個以
上必要となる。更にこの時の分割情報２は３個の
GF2剰余器６の剰余として a₁（ｘ）≡ｆ（ｘ）（mod m₁（ｘ）） ≡x³＋x²＋ｘ→1110 ………(12) a₂（ｘ）≡ｆ（ｘ）（mod m₂（ｘ）） ≡x³＋ｘ＋１→1011 ………（13） a₃（ｘ）≡ｆ（ｘ）（mod m₃（ｘ）） ≡x³＋x²＋ｘ＋１→111 ………（14）と分割暗号化される。このようにして、４ビツト
（元の情報列ｆ（ｘ）の１／Ｋ＝１／２の情報量）
の分割情報２がＮ個、すなわち３個できる。元の
情報列を再生する前に式(8)のt_i（ｘ）を計算して
おく。

(i) 再生時にa₁（ｘ）とa₂（ｘ）を使う場合 t₁（ｘ）＝x²＋ｘ＋１ ………（15） t₂（ｘ）＝x²＋ｘ ………（16） (ii) 再生時にa₂（ｘ）とa₃（ｘ）を使う場合 t₂（ｘ）＝ｘ＋１ ………（17） t₃（ｘ）＝ｘ ………（18） (iii) 再生時にa₃（ｘ）とa₁（ｘ）を使う場合 t₃（ｘ）＝x³＋ｘ＋１ ………（19） t₁（ｘ）＝x³＋x² ………（20）最後に任意のＫ個の分割情報２より元の情報列
ｆ（ｘ）を情報再生手段５により復号する場合を
を説明する。

(i) a₁（ｘ）とa₂（ｘ）より復号する場合式(7)に式(9)、(10)、(12)、（13）、（15）、（16）
を
代入して、ｆ（ｘ）≡m₂（ｘ）t₁（ｘ）a₁（ｘ）＋m₁（ｘ）t₂（ｘ）a₂（ｘ） ≡x⁷＋x⁵＋ｘ＋１ mod m₁（ｘ）m₂（ｘ） ………（21） (ii) a₂（ｘ）とa₃（ｘ）より復号する場合式(7)に式(10)、(11)、（13）、（14）、（17）、（1
8）
を代入して、ｆ（ｘ）≡m₃（ｘ）t₂（ｘ）a₂（ｘ）＋m₂（ｘ）t₃（ｘ）a₃（ｘ） ≡x⁷＋x⁵＋ｘ＋１ mod m₂（ｘ）m₃（ｘ） ………（22） (iii) a₃（ｘ）とa₁（ｘ）より復号する場合式(7)に式(9)、(11)、(12)、（14）、（19）、（20）
を
代入して、ｆ（ｘ）＝m₁（ｘ）t₃（ｘ）a₃（ｘ）＋m₃（ｘ）t₁（ｘ）a₁（ｘ） ≡x⁷＋x⁵＋ｘ＋１ mod m₃（ｘ）m₁（ｘ） ………（23）以上のように再生した結果、式（21）（22）
（23）はいずれの場合も元の情報列ｆ（ｘ）を正し
く再生し、元のデータベース１と同一内容のデー
タベース３を再生することができる。

式（21）の再生動作を第３図において説明す
る。情報再生手段５に入力される２個の分割情報
２であるa₁（ｘ）及びa₂（ｘ）は、GF2乗算器７に
よりt_i（ｘ）、t₂（ｘ）、t_k（ｘ）と乗算され、それぞ
れt_i（ｘ）a_i（ｘ）及びt₂（ｘ）a₂（ｘ）となつて出力
される。次に式（21）のmod m₁（ｘ）m₂（ｘ）
なる関係を保つためにGF2除算器８に入力され、
m₁（ｘ）、m₂（ｘ）、m_k（ｘ）により除算され、そ
れぞれの剰余が出力され、更にGF2乗算器９によ
り _k 〓^i=l

Claims

【特許請求の範囲】１複数の情報列を有するデータベースにおい
て、上記情報列を互いに素であるガロアフイールド
２（以下GF2と示す）上の多項式で割つた余りを
分割情報として出力する第１のGF2剰余器を並列
に配し、複数の暗号化された分割情報を保管する
情報分割手段と、上記分割情報を入力とする第１のGF2乗算器、
この第１のGF2乗算器からの出力を入力とする
GF2除算器、さらにこのGF2除算器の出力を入力
とする第２の乗算器とからなる複数の直列系を並
列に配し、上記第２のGF2乗算器の各出力を加算
する加算器、この加算器の出力を入力とするGF2
剰余器を配して、上記分割情報の中から元の情報
列の情報量以上の分割情報を集めて再生する情報
再生手段と、から構成されるデータ保護システム。２上記情報分割手段において、元の情報列ｆ
（ｘ）を、暗号化の鍵となる互いに素であるGF2
上の多項式m_i（ｘ）（ｉ＝１、………、ｒ＝Ｎ）
からa_i≡ｆ（ｘ）（modm_i（ｘ）、ｉ＝１、………、
ｒ＝Ｎ）を満たすようにＮ分割し、分割情報a_iを
作成することを特徴とする特許請求の範囲第１項
記載のデータ保護管理システム。３上記情報再生手段において、元の情報列ｆ
（ｘ）が０≦ｆ（ｘ）＜Ｍ（ｘ）＝_N 〓ⁱ⁼¹ m_i（ｘ）を満た
すものとして、１≡Ｍ（ｘ）／m_i（ｘ）・t_i（ｘ）（mod m_i（ｘ））（ｉ＝１、………、Ｎ）を満たす最小次数の多項
式t_i（ｘ）と、元の情報列の情報量以上の（Ｋ個、
Ｋ≦Ｎとする）分割情報a_i（ｘ）から元の情報列ｆ（ｘ）≡_K 〓ⁱ⁼¹ Ｍ（ｘ）／m_i（ｘ）・t_i（ｘ）・ a_i （ｘ）（mod Ｍ（ｘ））を再生することを特徴とする特許請求の範囲第１
項記載のデータ保護管理システム。