JPS587174A

JPS587174A - 暗号マスタ−鍵生成装置

Info

Publication number: JPS587174A
Application number: JP56105217A
Authority: JP
Inventors: 小山　謙二
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1981-07-06
Filing date: 1981-07-06
Publication date: 1983-01-14
Also published as: JPS6329743B2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】本発明は、暗号システムにおける代表的な暗号法である
Ｒ８Ａ法（Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ　ａｎｄ　Ａｄ
ｅｌｍａｎ’ｓ　ｍｅｔｈｏｄ　）に対して、その個別
暗号鍵から、各個別暗号鍵に共通に使用できる便利なマ
スター鍵の存在の判定を行ない、存在する場合は自動的
にマスター鍵を生成する暗号マスター鍵生成装置に関す
るものである。

データ通信システムやデータ処理システムなどで各種の
サービス等を行う場合、機密性の高い重要なデータの取
扱いが問題となってきており、種々の暗号鍵管理法が提
案されている。ところで、従来の暗号鍵管理法で用いら
れる通常の「マスター鍵」の概念は、個別鍵の使用時に
必らず「マスター鍵」も必要とする管理法の下での概念
であり、いわば安全性の強化を指向したものであった。

具体的には個々の暗号機における個別鍵を一旦、１つの
「マスター鍵」で暗号化ｌ−で配布し、各個別鍵の使用
に当っては、まず、その「マスター鍵」で個別鍵を復号
化してから用いる。この「マスター鍵」は、いわば「個
別鍵暗号用マスター鍵」である。一方、物理的な錠シス
テムと同時に、個別鍵の代替として直接共通に使うこと
ができるマスター鍵を「真のマスター鍵」と呼ぶ。本発
明はこの「真のマスター鍵」に係わるものである。

上記「真のマスター鍵」の概念は、従来の暗号鍵管理法
においては見当らず、また、その具体的な解析を通した
合成法は明らかにされていない。

以下では「真のマスター鍵」を単にマスター鍵と呼ぶこ
とにする。又、マスター鍵の生成を行う具体的な暗号シ
ステムとして、署名可能で鍵の配布が容易な公開鍵暗号
系（暗号化鍵と復号化鍵が異なる方式）の中で、最も有
望視されているＲＳＡ法を対象とする。

既に提案されているＲＳＡ法（Ｒｉｖｅｓｔ、Ｓｈａｍ
ｉｒ　ａｎｄ　Ａｄｅｌｍａｎ“Ａ　ｍｅｔｈｏｄ　ｆ
ｏｒ　Ｏｂｔａｉｎｉｎｇ　Ｄｉｇｉｔａｌ　Ｓｉｇｎ
ａｔｕｒｅ　ａｎｄ　Ｐｕｂｌｉｃ−Ｋｅｙ　Ｃｒｙｐ
ｔｏｓｙｓｔｅｙｍｓ”ＣＡＣＭＶｏｌ．２１，Ｎｏ２
，Ｆｅｂ，１９７８）の個別鍵を基本とした暗号原理は
次の通りである。

ｍ個の個別鍵（暗号化個別鍵Ｋｅｉ，復号化個別鍵Ｋｄ
ｉ，（１≦ｉ≦ｍ））が独立に以下の手順で求められる
。

（ｉ）任意の２つの相異なる大きな素数ｐｉ、ｑｉを選
び、ｎｉ＝ｐｉ・ｑｉを計算する。

（ｉｉ）（ｐｉ−１）（ｑｉ−１）（以下ψ（ｎｉ）と
略する）と互いに素な任窟の整数Ｋｄｉを選び出す。

（ｉｉｉ）ψ（ｎｉ）を法としたＫｄｉの乗算の逆元Ｋ
ｅｉを計算する。すなわちＫｅｉ・Ｋｄｉ＝１（ｍｏｄ　ψ（ｎｉ））を解き、Ｋ
ｅｉを求める。

そして、暗号化の鍵は（Ｋｅｉ、ｎｉ）の組であり、対
応する復号化の鍵は（Ｋｄｉ，ｎｉ）の組である。Ｋｅ
ｉ、ｎｉは公開し、Ｋｄｉは秘密にしておく。

平分Ｐを暗号文Ｃに暗号化するアルゴリズム■と、暗弓
文Ｃを平文Ｐに復号化するアルゴリズム■は、Ｃ＝■（Ｐ）＝ＰＫｅｉ（ｍｏｄ　ｎｉ）Ｐ＝■（Ｃ）
＝ＣＫｄｉ（ｍｏｄ　ｎｉ）で表わされる。

本発明は、従来の個別鍵のみから成る暗号システムを発
展させて、複数の個別鍵に共通に適用できるマスター鍵
の生成を行ない、個別鍵全体を格納する記憶容量の削減
および、マスター鍵所有者が、各個別鍵を所有しなくと
も、緊急時および日常の便宜のために使用できるように
、暗号鍵管理が柔軟かつ効率的に行えることを目的とし
た暗しマスター鍵生成装置を提供することにある。

以下、本発明をマスター鍵の存在条件のチェック法と存
在する場合の具体的な導出法にそれぞれ分けて説明する
。なお、マスター鍵はｍ組の個別鍵に対するものとする
。

初め存在条件のチェック法について説明する。

ここで、暗号化個別鍵をＫｅｉ（ｉ＝１、２．・・、ｍ
）、復号化個別鍵をＫｄｉ、（ｉ＝１，２，・・・、ｍ
）とし、暗号化マスター鍵をＫｅＭ、復号化マスター鍵
をＫｄＭとする。暗号化と復号化の関数はｎｉを法とし
て、ある数（平文または暗号文）をべき乗するという意
味で同形であり、暗号鍵と復号鍵のマスター鍵の存在条
件は独立に同様に求められする。以下では簡単化のため
ＫｄｉとＫｅｉ、ＫｅＭとＫｄＭの添字ｅとｄを省略し
て、それぞれＫｉ、ＫＭで表わし、ＰとＣに対しては代
表してＭで表わす。

マスター鍵の存在する条件は、１からｍまでのすべての
ｉと、０からｎｉ−１までのすべての整数Ｍに対して、ＭＫＭ≡ＭＫｉ（ｍｏｄ　ｎｉ）（１）が成立すること
である。式（１）をＭがｐｉと互いに素な場合と、Ｍが
ｑｉと互いに素な場合に分けて考察すると、式（１）が
成立する必要十分条件はＫＭＫｉ＋ｌｉＥｉ　（ｉ＝’
ｌ、・・・、ｍ）（２）Ｅｉ＝ＬＣＭ｛（Ｐｉ−１）、
（ｑｉ−１）｝（３）であることが導かれる。、ここで
、ＬＣＭ｛（ｐｉ−１）、（ｑｉ−１）｝は（ｐｉ−１
）と（ｑｉ−１）の最小公倍数を表わし、ｌｉは整数で
ある。

更に条件を具体化すると、マスター鍵の存在する条件は
、１からｍの間のすべての整数ｉ、ｊの組合せに対して
、次式が成立することである。

Ｋｊ−Ｋｉ＝ａｉｊ×ｇｉｊｇｉｊ＝ＧＣＤ（Ｅｉ、Ｅｊ）ここで、ＧＣＤ　（Ｅｉ、Ｅｊ）はＥｉとＥｊの最大公
約数を表わし、ａｉｊは整数である。

次に、上記に示したマスター鍵の存在条件を満だす個別
鍵Ｋｉが与えられた場合のマスター鍵ＫＭの具体的な求
め方を説明する。１番目からｉ番目（１≦ｉ≦ｍ）まで
の個別鍵に対するマスター鍵をＫＭ，ｉと表わす。当然
ＫＭ，ｍ＝ＫＭ，ＫＭ，１＝Ｋ１となる。

存在条件より、例えばＫＭ，２に関してはＫＭ，２＝Ｋ
１−ｌ１Ｅ１ＫＭ，２＝Ｋ２＋ｌ２Ｅ２を満たす。したがって、ＫＭ，２を消去して、ｌ１Ｅ１
−ｌ２Ｅ＝Ｋ２−Ｋ１となり、この２元１次不定方程式を解き、ｌ１，ｌ２を
求める。したがって、ＫＭ，２が求まる。次にＫＭ，３
に関しては、ＫＭ，３＝ＫＭ，２＋ｌ２ＬＣＭ（Ｅ１，Ｅ２）ＫＭ，
３＝Ｋ３＋ｌ３Ｅ３　（６）を解き、ｌ２，ｌ３を求める。したがって、ＫＭ，３が
求まる。順次同様にしてＫＭ，ｉを求めていくと、一般
的にＫｍ，ｉ＝（ｉ＝２、・・・、ｍ）に関してＫＭ，
ｉ＝ＫＭ，ｉ−１＋ｌｉ−１・Ｌｉ−１ＫＭ，ｉ＝Ｋｉ
＋ｌｉＥｉ　（７）が成立する。ただし、Ｌｉ＝ＬＣＭ（Ｅ１、Ｅ２、・・
・Ｅｉ）（ｉ＝１，・・・、ｍ−１）である。

しだがって、式（７）はｌｉ−１・Ｌｉ−１−ｌｉＥｉ＝Ｋｉ−ＫＭ，ｉ−１と
なり、この２元１次不定方程式を解き、ｌｉ−１、ｌｉ
を求める。求まったｌｉより、ＫＭ，ｉが求まる。

ｉを増加させると、最終的にＫＭ，ｍ（＝ＫＭ）が求ま
る。

次に、以上のマスター鍵の存在条件のチェックとマスタ
ー鍵の生成機能を備えた本発明装置の一実施例を説明す
る。

第１図は本究明に係る暗号マスター鍵生成装置の一実施
例のブロック図である。第１図において、線１０よりデ
ータ読込み回路１１に個別鍵Ｋｉと基本定数ｐｉ、ｑｉ
がｍ組入力されると、プログラム格納メモリ１０内のプ
ログラムの指令により、加算器１２、乗算器１３、除算
器１４より成る演算器１５を用いてマスター鍵の存在の
チェックとマスター鍵の導出を実行し、データ格納メモ
リ１７に中間変数を格納しながら、その結果をデータ書
込み回路１８により出力する。

第１図の主要部の詳細を第２図に示す。第２図において
、線２６より個別鍵Ｋｉが入力されると、そのままデー
タ格納メモリ１７に格納する。線２１よりｐｉ、ｑｉが
入力されると、プログラム格納メモリ１６中の最小公倍
数導出プログラムを起動して、演算器１５を用いて式（
３）のＥｉを求め、データ格納メモリ１７に格納する。

ｍ組のＫｉとＥｉの格納が完了すると、プログラム格納
メモリ１６の最大公約数導出プロクラムを起動し、デー
タＥｉと演算器１５を用いて、式（４）のｇｉｊを求め
、データ格納メモリ１７に格納する。次に、データＫｉ
と加算器１２を用いてＫｉ−Ｋｊを求め、データ格納メ
モリ１７に格納する。Ｋｉ−Ｋｊを除算器１４によりｇ
ｉｊで割り、その余りを線２７に出力する。

比較器２８により余りが０か否かを判定し、もし０でな
いならば、線２つにより信号を送り、データ書込み回路
１８を通して「マスター鍵は存在しない」とメツセージ
を出力する。、ｍ個の余りがすべて０ならばマスター鍵は存在するので
、マスター鍵生成段階へ移行する。まずデータＥ１、Ｅ
２、・・・、Ｅｉよりプログラム格納メモリ１６内の最
小公倍数書出プログラムを起動し、演算器１５を用いて
Ｌｉを求め、データ格納メモリ１７に格納する。次にプ
ログラム格納メモリ１６内の２元１次不定方程式の解法
プログラムを起動し、データＥｉ、Ｌｉ−１、．ＫＭ，
ｉ−１，Ｋｉ（ｉ＝２、・・・、ｍ−１）と演算器１５
を用いて式（７）のｌｉを求め、更に演算器１５を用い
てＫＭ，ｉを求め、データ格納メモリ１７に格納する。

上記の２元１次不定方程式を、ｉが１からｍまで逐次的
に実行することにより、最終的に全体のマスター鍵ＫＭ
（＝ＫＭｍ）が得られる。

このＫＭをデータ書込み回路１８を用いて出力する。

以上説明したように、本発明の暗号マスター鍵生成装置
は次の利点がある。

（１）従来、マスター鍵の存在が不明であつた暗号シス
テムに対し、具体的にその存在条件を明らかにし、各個
別鍵がその存在条件に適するか否かを自動的にチェック
できる。

（２）マスター鍵の存在条件を満たす場合に、マスター
鍵を個別鍵から自動的に生成できる。

（３）鍵の格納する容量が小さい。

（４）緊急時にマスター鍵所有者が各個別鍵を用いなく
とも、迅速に鍵入力操作ができる。

（５）個別鍵を紛失または破壊しても、マスター鍵によ
り代替できるので、信頼性が向上する。

【図面の簡単な説明】

第１図は本発明にかヽる暗号マスター鍵生成装置の一実
施例のブロック図、第２図は第１図の主要部の詳細図で
ある。１１・・データ読込み回路、１２・・・加算器、１３乗
算器、１４・・除算器、１５・・・演算器、１６・・・
プログラム格納メモリ、１７・・・データ格納メモリ、
１８・・・データ書込み回路、２８・・比較器。

Claims

【特許請求の範囲】

１、複数の相異なる個別暗号鍵を入力する手段と、前記
複数の相異なる個別暗号鍵がそれらに共通して代替でき
るマスター鍵の存在条件を満たすか否かの判定を行う手
段と、マスター鍵の存在条件を満たす場合、前記複数の
個別暗号鍵に共通に適用できるマスター鍵を生成する手
段とを有することを特徴とする暗号マスター鍵生成装置
。