JPH02259689A - データ転置装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は入力データ系列をある定まった転置規則に従っ
てそのデータ位置を転置し、異なったデータ系列を出力
するデータ転置装置に関する。

従来の技術 データ転置装置は画像・音声・数値データといった各種
データの秘密通信に利用される暗号装置の基本構成要素
であり、転置規則を秘密の鍵としている。

データ転置装置をハードウェアで構成する場合、高速処
理が得られる反面、転置規則が固定的であるため、容易
に転置規則が推定され安全性の面で好ましくない。一方
マイコン等のソフトウェアで構成する場合、メモリに転
置規則を蓄積し、これを更新することで適時転置規則を
変化させることができる。従って安全性の問題は解決す
る。しかし転置処理の速度はハードウェアで構成する場
合と比較して遅くなる。また安全性を考慮した転置規則
をいかに効率良く生成するかという新たな問題が生じる
。

以下ではマイフン等によるソフトウェアで実現したデー
タ転置装置の従来例について述べる。

従来例１ 第３図は従来より広く用いられているデータ転置装置の
例である（以下従来例１と称する。例えば特開昭６３−
５３５８４の従来の技術の項公報）。同図（ａ）におい
て３１は従来例１の構成によるデータ転置装置、３２は
データ転置部、３３は入力データ格納部、３４は出力デ
ータ格納部、３５は転置規則を格納する転置テーブルで
ある。

この転置装置の動作は以下の通りである。転置すべきＮ
個の入力データ系列は、３３の入力データ格納部に一旦
格納され、３２のデータ転置部に送られる。３２のデー
タ転置部に送られたデータは、そこで３５の転置テーブ
ルに従って、そのデータ位置が転置され、３４の出力デ
ータ格納部に格納される。そして転置された出力データ
系列として出力される。

同図（ｂ）は転置テーブルである。従来例１ではＮ個の
データを転置する大きさの転置テーブルが必要である。

転置テーブルの参照はそのアドレスを指定することによ
り行う。同図に示すように、大きさＮの転置テーブルに
はそのアドレスｉ（１≦ｉ≦Ｎ）のメモリ領域に、ｉ番
目の位置のデータの転置すべき位置ｐｉ（１≦ｐｉ≦Ｎ
）が格納されている。つまりこのテーブルにしたがって
、ｉ番目の位置にあったデータは９１番目の位置に転置
される。

第４図は従来例１の構成によるデータ転置装置のデータ
転置部および転置テーブルの例（この場合Ｎ＝１０）で
ある。同図（ａ）は転置テーブル、同図（ｂ）はデータ
転置部である。データ転置部では１０個のデータが転置
テーブルにしたがって、例えば先頭（入力データの１の
位置）にあったデータｄ１は先頭から５番目（出力デー
タの５の位置）に転置され、また先頭から５番目（入力
データの５の位置）にあったデータｄ５は先頭から１０
番目　（出力データの１０の位置）に転置される。

・転置テーブルの容量 転置テーブルに格納されるｐｉ　（≦Ｎ）を記述するの
に必要なメモリ容量は、 ［１ｏｇａＮ］　　（ビット） であるので、大きさＮの転置テーブルに必要なメモリ容
量は 旧＝Ｎ＊［：ｌｏｇ２Ｎコ　（ビット）　　　　（１）
となる。ここで［ａ］はａｌｂを満たす最小の整数すを
表す。具体的に大きさＮ＝６４の転置テーブルには、Ｍ
１＝３８４ビットのメモリ容量が必要である。

争装置テーブルの生成 転置規則は以下の条件を満たすように生成される必要が
ある。　（但し条件１は転置規則の生成において満たす
べき必要十分条件であるが、条件２）、３）は安全性を
高めるための十分条件である。）条件ｌ）同じ位置に重
複して転置されないｐｆ（１≦ｔ　Ｆｉ　ＮＮ　１≦ｐ
ｉ≦Ｎ）はそれぞれ相異なる 条件２）偏りなくランダムに転置される条件３）全ての
データが転置される（ｐｉ≠ｉ）条件ｌを実現するため
、従来から疑似乱数発生器（Ｎ以下の自然数を発生する
）を使用して、転置テーブルは生成される。すなわち乱
数発生器のＮ個の出力値１）ｉ（１≦ｉ≦Ｎ１１≦ｐｉ
：ａＮ）がｉ番目のデータの転置部の位置として転置テ
ーブルに格納される。

これらの条件を満たすため、以下のテーブル生成法が用
いられている。

生成法：乱数を１個ずつ発生し、条件を溝だす乱数を１
個ずつ決定していく。条 件を満たさない乱数は棄却し、新た に乱数を発生する。この操作を条件 を溝たす乱数が得られるまで繰り返 す。

この方法ではテーブルの大きさＮの増加に伴って、テー
ブル生成に要する時間が多大となり、かつ生成に要する
時間のばらつきが大きくなる。従って限られた時間内に
転置テーブルを更新する必要のある場合に、テーブルの
大きさＮをある程度小さく設定する必要がある。しかし
従来例１の構成においてテーブルの大きさＮを小さくす
ることは、次に示す安全性の面から好ましくない。

拳安全性 ここでは転置規則を悉皆的に推定し、転置されたデータ
系列に対して、逆転置を施して元のデータ系列を復元す
るという転置規則の解読法に対する安全性について述べ
る。但しこのような解読が成功するのは、解読者が元の
データ系列に関してなんらかの情報（例えば使用言語、
コード等）を知っている場合に限られる。つまり逆転置
によってこれらの意味のあるデータが得られることで解
読の成否を判定できる場合に限り解読可能となる。

このような解読を現実的に不可能にするため、転置規則
を十分大きな母集合の中から選択する必要がある。

従来例１において、選択されるべき転置規則の母集合の
大きさは、簡単のために条件１のみを満たす場合を考え
ると Ｎ！　　　　　　　　　　　　（２） である。Ｎの値を転置規則を推定するのが困難なように
、つまり（２）式が十分大きくなるよう、に設定する（
但し実際は他の条件をも満たす転置規則の母集合の大き
さを十分大きくする）。具体的にはＮ＝３２程度で（２
）式が１０３ｅ以上となり実用上安全となる。

従来例２ 第５図にデータ転置装置の第２の従来例を示す（以下従
来例２と称する、例えば特開昭６１−１０７３７５公報
）。これは入力データ系列をいくつかの小さなブロック
に分割し、ブロック単位での転置（ブロック転置）と各
ブロック内での転置の２段構成を取っている。このこと
によりＮ個のデータを転置するのに必要な転置テーブル
の大きさを小さくでき、その生成も容易になる。

同図において５１は上記構成によるデータ転置装置であ
り、以下の各部で構成されている。５２はブロック分割
部、５３はブロック転置部、５４は各ブロック毎のデー
タ転置部、５５はブロック結合部である。また５６は入
力データの格納部、５７は出力データの格納部、５８は
ブロック転置テーブル、５９は各ブロック毎に定められ
た転置テーブルである。

この転置装置の動作は以下の通りである。転置すべき入
力データ系列は、５６の入力データ格納部に一旦格納さ
れ、５２のブロック分割部に送られる。ブロック分割部
で、分割され、５３のブロック転置部に送られる。ブロ
ック転置部では、５８のブロック転置テーブルに従って
ブロック単位でまとめて転置される（各ブロック内での
データの位置は変わらない）。次にブロック転置された
各データは各ブロック毎に５４のデータ転置部に送られ
各ブロック毎に５９のデータ転置テーブルに従って各ブ
ロック内で転置される。次に各ブロックの転置されたデ
ータは５５のブロック結合部で結合され、５７の出力デ
ータ格納部に格納される。以下ではＮ：データ系列長、
Ｌニブロック長、ｍ：　ブロック数と記す。

この構成によるデータの転置装置の具体例を第６図に示
す。この例ではＮ＝２４、Ｌ＝６、ｍ＝４である。以下
にその動作を説明する。４個のブロックに分割されたデ
ータは、まずブロック単位の転置（各ブロックの６個の
データをまとめて転置する。但し各ブロック内でのデー
タの順序は変更されない。）が同図（ｂ）に示すブロッ
ク転置テーブルを用いて施される。例えばブロック１は
ブロック３の位置に、またブロック２はブロック１の位
置に転置される。次にブロック転置されたデータはそれ
ぞれ各ブロック毎に定め・られたデータ転置テーブル（
同図（Ｃ）に示す）に従って各ブロック内で転置される
。たとえばブロック１の位置に転置された各データは、
転置テーブル１にしたがって転置される。

・テーブル容量 データ長Ｎ１　　データ長Ｌ１　　ブロック数ｍのデー
タ転置装置に必要な転置テーブルのメモリ容量はＭ２＝
ｍ＊　　Ｃｌｏｇ２　ｍコ　＋　（ｍ＊　Ｌ）＊　［ｌ
ｏｇ２Ｌコ　（ビット）　　（３）である。内訳はブロ
ック転置テーブルにｍ＊　［ｌｏｇ２ｍコ　　　　（ビ
ット）　　（４）と、各ブロック毎の転置テーブルに Ｌ　＊　［Ｉｏｇ２Ｌコ　　　　（ビット）　　（５）
である。第６図の例（Ｎ＝　２４、Ｌ＝６、百＝４）で
はＭ２＝　８０ビツトとなる。また従来例１と比較する
ため、Ｎ＝６４、ｍ＝８の場合Ｍ２＝　２１６ビツトと
なり、従来例１の５７％となる。このようにブロック数
ｍをうまく選べば必要なメモリ容量を従来例１の約半分
に削減できる。

・テーブル生成 従来例２の構成によるデータ転置装置では、大きさｍの
転置テーブル１個 大きさＬの転置テーブルｍ個 必要であるが、転置テーブルの大きさｍｌ　　Ｌを（Ｎ
　（＜Ｎ）程度にすると、テーブル生成を従来例１と比
較して容易にできる。つまりデータ長Ｎ＝６４の場合、
従来例１では大きさθ４の転置テーブルが必要であった
が、従来例２ではブロック数ｍ＝８とすることで、大き
さ８のテーブルを５つ生成すればよい。

・安全性 従来例２において、選択されるべき転置規則の母集合の
大きさは、簡単のため条件１を満たす規則を考えると ｍｌ　　＊（Ｌ！　　）ｍ　　　　　　　　　　　　　
（６）である。式（６）を転置規則を推定するのが困難
なように設定する（但し実際は他の条件をも満たす転置
規則の母集合の大きさを十分大きくする）。

例えばＮ＝８４、ｍ＝Ｌ＝８とすれば１０３６程度とな
る。しかし、このようにＬとｍを設定しても以下に示す
問題点から安全といえない。

第６図の例において、ブロック１に転置されたデータ（
転置されたデータ系列の１〜６番目のデータ）は元のデ
ータ系列のブロック２のデータ（元のデータ系列の７〜
１２番目のデータ）を転置したものであることからも分
かるように、この構成によれば、各ブロックのデータは
それぞれそのブロック内に偏って転置される。すなわち
各ブロック毎に独立に転置規則を推定されるという危険
性を有している。つまり転置データの各ブロックに対し
て転置規則を推定して、元のデータ系列の一部（ブロッ
ク）を復元し、次に、ブロック転置テーブルを推定して
元のデータ系列を復元するといった解読が可能である。

各ブロックの転置テーブルはそれぞれ大きさＬ！　　　
　　　　　　　　　　（７）の転置規則の母集合から選
ばれるため、この解読現実的に不可能にするためには式
（７）を大きくしなければならない。

発明が解決しようとする課題 従来例１の構成によれば、転置テーブルの大きさを十分
大きくとる必要があり、そのために生成時間が多大で、
かつ一定でないため、頻繁に転置規則を更新させたい場
合効率的でない。一方従来例２の構成によれば従来例１
に比較して小さな（従来例１の大きさの平方根程度）転
置テーブルで実現できるため、テーブルの生成時間を短
縮でき、さらにメモリ容量も小さくすることが可能とさ
れているが、前項で指摘したように各ブロック内で施さ
れるデータの転置規則が転置されたデータの偏りから容
易に推定される危険性があり安全性の面で好ましくない
。

本発明は上述の問題点に鑑み試されたもので転置テーブ
ルの生成時間及びテーブルのメモリ容量を従来例２程度
にでき、かつ転置規則の推定を容易に行えないデータ転
置を提供することを目的とする 課題を解決するための手段 本発明は上述した問題点を解決するため入力データ系列
をブロックに分割する手段と、同一ブロックの各データ
をいくつかのグループに分配し配置する手段と、各グル
ープに分配されたデータを各グループ内で転置する手段
と、転置さ、れたデータを各グループから収集し新たな
ブロックに配置する収集手段と得られたブロックを結合
し転置データ系列を得る結合手段を備えたものである。

作用 本発明は分配手段が各ブロックに属するデータをいくつ
かのグループにランダムに分配配置することで各グルー
プの属するデータは元のデータ系列に対してまったく偏
りのないものにできるため、データ転置手段の各グルー
プ毎に行う転置規則を容易に推定できないものとしてい
る。

すなわちグループ毎に転置規則を解読できない構成を取
っている。またグループ毎の転置を施すことで必要な転
置テーブルのメモリ容量を小さくできる。

実施例 第１図は本発明によるデータ転置装置の実施例である。

同図において、１は本発明の構成によるデータ転置装置
であり、以下の各部分から構成される。２はブロック分
割部、３はデータ分配部、４はデータ転置部、５はデー
タ収集部、６はブロック結合部であり、７は入力データ
格納部、８は出力データ格納部、９はデータ分配規則を
格納するメモリ、１０は転置規則を格納する転置テーブ
ル、１１は結合規則を格納するメモリである。

この転置装置の動作は以下の通りである。転置すべきデ
ータ系列は、７の入力データ格納部に一旦格納され、２
のブロック分割部に送られる。そしてそこで先頭から順
次ブロックに分割される。

次に各ブロックのデータはブロック毎に、３の分配部に
送られ、そこで９の分配規則に従って、いくつかのグル
ープに分配配置される。次に各グループに分配配置され
たデータは４のデータ転置部に各グループ毎に送られ、
１０の転置テーブルに従って転置される。各グループで
転置されたデータは５の収集部で１０の収集規則に従っ
て新たなブロックに収集され配置され、６のデータ結合
部に送られ各ブロックが結合されて、８の出力データ格
納部に格納される。そして最後に転置データ系列として
出力される。なお分配規則メモリにはそのブロックの各
データがどのグループのどの位置に配置するかが記述さ
れている。また収集規則には各ブロックがどのグループ
のどの位置のデータを収集するかがか記述されている。

以下でＮ：データ長、ｍ：　ブロック数、Ｌ：　ブロッ
ク長、ｋニゲループ数、Ｑｊ（１≦ｊ≦ｋ）：　グルー
プ長、と記す。なお各グループ長を同一としてもよい。

第２図に上記構成による具体例を示す。同図に示す具体
例は、Ｎ＝２４、ｍ＝３、ｋ＝８、ｋ＝３、Ｑ１＝９、
Ｑ２＝６、Ｑ３＝９のデータ転置装置であり、その動作
は以下の通りである。

２４個のデータはまず８個ずつ３個のブロックに分けら
れる。次に各ブロックの８個のデータは同図（ｂ）に示
された分配規則に従って３個のグループに分配される（
各ブロック共通にこの規則を用いる）。分配規則は次に
示す通りとする。

ａ）メモリにはブロックの各データをどのグループに分
配するかのみを記述し、 各グループでの配置は、そのグループ への分配順序に従う。

例えば最初にグループ１に分配されるデータはブロック
１の１番目のデータであり、それはグループ１の１番目
に分配配置される。次にグループ１に分配されるデータ
はブロック１の４番目のデータでありそれがこのグルー
プの２番目に分配される。

次に各グループ内でそれぞれ転置規則にしたがってデー
タ位置が転置される。例えば、グループ１のデータは転
置規則１に従って、１番目のデータは４番目に、２番目
のデータは５番目にというようにである。なお り）この例のように転置規則は左あるいは右巡回シフト
で構成してもよい。

この場合転置テーブルのメモリ容量を減少できる（巡回
するシフト量のみメモリに記述すればよい）。

さらに、各グループのデータに対して、収集規則に従っ
て各データが新たなブロックに収集される。

収集規則は次の通りである。

Ｃ）各グループの転置されたデータに対して分配規則と
まったく逆の規則で各ブ ロックに収集した上で、左巡回シフト を施す。

例えばデータ分配部でブロック１の３番目のデータをグ
ループ２の１番目に分配しているのに対し、分配部と逆
の手順でグループ２の１番目に転置されたデータをブロ
ック１の３番目のデータに配置するといった操作を全デ
ータに対した後に１だけこれを左に巡回シフトする（例
えばブロック１の３番目に配置されたデータはブロック
１の２番目に、ブロック２の１番目のデータはブロック
１の９番目にブロック１の１番目のデータはブロック３
０９番目にというようにである。）。なお収集規則は ｄ）各グループをそのまま新たなとブロックとみなす。

ものとしてもよくこのばあい結合部では各ブロック（つ
まり各グループ）のデータを順次結合する。

つまりグループ１の１〜６の位置のデータの次にグルー
プ２の１〜６の位置のデータを結合するというようにで
ある。

最後に各ブロックのデータは結合される。

Φテーブル容量 データ長Ｎ１　　ブロック長Ｌ１　　ブロック数ｍ１　
　グループ数に１　　グループ長はそれぞれＱｊ（すな
わちＱｊ　（１≦ｊ≦に１　Ｎ＝ΣＱｊ）個ずつに個の
グループに分配する）として必要なメモリはＭ＝Ｌ＊　
　［ｌｏｇ　　ｋコ　＋に＊［ｌｏｇＬコ＋ΣＱｊ［ｌ
ｏｇＱｊコ　（ビット）　　（８）ｊ：１−ｑ となる。内訳はデータ分配規則格納用テーブルの容量は
各ブロックのデータがどのグループに分配するかのみを
規定すれば良いから Ｌ＊［！ｏｇｋコ　　（ビット）　　　（９）である。

また各グループの転置テーブルに必要なメモリ容量は、 Ｑｊ＊［ｌｏｇＱｊコ　（ビット）（１０）である。さ
らに結合規則としては、各グループのデータがどのブロ
ックに収集するかのみを規定すれば良いから に＊　［ｌｏｇ　Ｌ］　　（ビット）（ＬＬ）となる。

なお第６図の例では、Ｍ＝４２ビットとなる。またＮ＝
６４、ｍ＝Ｌ＝に＝Ｑｊ　（１≦ｊ≦８）＝８とすれば
、Ｍ＝２４０ビットとなり、従来例１と比較して６２％
のメモリ容量となる。

また従来例２と同程度となる（２４ピツト（収集規則メ
モリの容量分）増加する）。

・テーブルの生成 必要とする。この生成時間は従来例２と同程度と見積ら
れる。この転置装置では 大きさＬのテーブル１個 大きさＱｊ　（１≦ｊ≦ｋ）のテーブル大きさｋのテー
ブル１個 （ｋ、　　Ｌ、　　ＱｊはｒＮ程度にできる）必要とす
る。この生成時間は従来例２程度と見積られる。

・安全性 本構成によるデータの転置装置では元のデータ系列の各
データを各グループにランダムに分配するため各グルー
プ毎に解読を行っても元のデータ系列の１部分は復元で
きない。すなわち転置規則の解読を各グループ毎に独立
には行えない。このため解読は本構成によってとり得る
すべての転置規則について施さねばならない。従ってこ
の値を十分に大きく設定することで（例えば１Ｑ２１以
上）解読を不可能にできる。

具体例では実現可能な転置規則数は に！　＊　（Ｑｊ　）ｋ　　　　　　　　　（１２）で
ある。

発明の効果 以上の説明から明らかなように本発明は、データをグル
ープに分配し、各グループで転置するとういう手段によ
り、安全性の高いデータの転置を実現している。さらに
、転置テーブルが容易に生成できるため、頻ばんに転置
規則を変化させることが可能となる。またメモリ容量も
従来例２程度にすることができる。

【図面の簡単な説明】

第１図は本発明によるデータ転置装置の実施例を示す構
成図、第２図は同実施例における動作説明図、第３図は
従来例１の転置装置を示す構成図、第４図は従来例１の
動作説明図、第５図は従来例２の転置装置を示す構成図
、第６図は従来例２の動作説明図である。 １・・・データ転置装置、２・・・ブロック分割部、３
・・・データ分配部、４・・・データ転置部、５・・・
データ収集部、６・・・データ結合部、７・・・入力デ
ータ格納部、８・・・出力データ格納部、９・・・デー
タ分配規則を格納するメモリ、１０・・・データ転置テ
ーブルを格納するメモリ、１１・・・データ結合規則を
格納するメモ１几 代理人の氏名　弁理士　粟野重孝　はか１名纂 図 第 図 マ１ （ｂ） 蘂 図 （ａ） （ｂ） 第 （ｔ２．２ （ｂ） 礪 図 第 図 （ｃＬ）

Claims (1)

【特許請求の範囲】
1. 入力データ系列を、ある定められた個数毎のブロックに
   分割するブロック分割手段と、同一ブロックに属する各
   データを、定められたある分配規則にしたがって、いく
   つかのグループに分配し、配置するデータ分配手段と、
   各グループに分配配置されたデータを、定められたある
   転置規則に従って各グループ内で転置するデータ転置手
   段と、各グループにおいて転置されたデータを定められ
   たある収集規則にしたがって新たなブロックに収集し、
   配置するデータ収集手段と、各ブロックのデータを結合
   し、転置された出力データ系列を得るブロック結合手段
   とを備えることを特徴とするデータ転置装置。