(57)【特許請求の範囲】
【請求項１】
入力データを同時に暗号化し、圧縮する方法であって、
ユーザから暗号化キーを受信するステップと、
圧縮アルゴリズムにおける変数の値を決定するために前記暗号化キーを使用するステップであって、前記決定される値が変数の値のセットにより定められた複数の圧縮アルゴリズムのセットから１つの圧縮アルゴリズムを識別し、圧縮アルゴリズムの前記セットは、複数のムーブ・フォワード圧縮アルゴリズムからなる、ステップと、そして
前記入力データの第１のデータを前記１つの圧縮アルゴリズムに従って圧縮するステップと
を含み、
前記暗号化キーにより識別された前記１つの圧縮アルゴリズムに従って前記第１のデータを圧縮すると同時に、別の暗号化アルゴリズムを使用しないで、前記第１のデータを暗号化し、
ここで、前記複数のムーブ・フォワード圧縮アルゴリズムに従って前記第１のデータを前方に移動する量は、前記暗号化キーの、前記第１のデータに対応した、単一ビットに依存する、
方法。
【請求項２】
前記第１のデータは、単一の文字からなることを特徴とする前記請求項１記載の方法。
【請求項３】
前記第１のデータは、前記入力データのすべてからなることを特徴とする前記請求項１記載の方法。
【請求項４】
前記暗号化キーを使用するステップは、圧縮アルゴリズムの前記セットから前記１つの圧縮アルゴリズムを識別するために単一ビットの前記暗号化キーを使用するステップを含む、ことを特徴とする前記請求項１に記載の方法。
【請求項５】
前記変数に対して第２の値を決定し、圧縮アルゴリズムの前記セットから第２の圧縮アルゴリズムを識別するために、前記暗号化キーを使用するステップと、そして
前記入力データの第２のデータを前記第２の圧縮アルゴリズムに従って圧縮するステップと
をさらに含む前記請求項４に記載の方法。
【請求項６】
さらに、前記第１のデータを圧縮する前に、前記第１のデータの入れ替えを行うステップを包含することを特徴とする前記請求項１記載の方法。
【請求項７】
入力データを同時に暗号化し、圧縮する装置であって、
圧縮アルゴリズムにおいて変数の値のセットによって定められた複数の圧縮アルゴリズムを有する圧縮器セットであって、前記複数の圧縮アルゴリズムは、複数のムーブ・フォワード圧縮アルゴリズムからなる、圧縮器セットと、そして
ユーザから暗号化キーを受信し、前記変数の前記値を決定するように前記暗号化キーの少なくとも一部の使用に基づいて前記複数の圧縮アルゴリズムから１つの圧縮アルゴリズムを識別し、そして前記１つの圧縮アルゴリズムに従って前記入力データの第１のデータを圧縮するコンクリプタと
を備え、
前記暗号化キーにより識別された前記１つの圧縮アルゴリズムに従って前記第１のデータを圧縮すると同時に、別の暗号化アルゴリズムを使用しないで、前記第１のデータを暗号化し、
ここで、前記複数のムーブ・フォワード圧縮アルゴリズムに従って前記第１のデータを前方に移動する量は、前記第１のデータに対応する、前記暗号化キーの単一ビットに依存する、
装置。
【請求項８】
前記第１のデータは、単一の文字からなることを特徴とする前記請求項７記載の装置。
【請求項９】
前記第１のデータは、前記入力データのすべてからなることを特徴とする前記請求項７記載の装置。
【請求項１０】
前記コンクリプタは、さらに、前記複数の圧縮アルゴリズムから前記１つの圧縮アルゴリズムを識別するために、単一ビットの前記暗号化キーを使用することを特徴とする前記請求項７記載の装置。
【請求項１１】
前記コンクリプタは、さらに、前記複数の圧縮アルゴリズムから第２の圧縮アルゴリズムを識別するように前記変数の第２の値を決定し、そして前記第２の圧縮アルゴリズムに従って前記入力データの第２のデータを圧縮するために、前記暗号化キーを使用することを特徴とする前記請求項１０記載の装置。
【請求項１２】
前記コンクリプタは、さらに、前記第１のデータを圧縮する前に、前記第１のデータの入れ替えを行うことを特徴とする前記請求項７記載の装置。
【請求項１３】
プロセッサに方法を実行させる複数のインストラクションがストアされたマシン可読媒体であって、
前記方法は、
ユーザから暗号化キーを受信するステップと、
圧縮アルゴリズムにおける変数の値を決定するために前記暗号化キーを使用するステップであって、前記決定される値が変数の値のセットにより定められる複数の圧縮アルゴリズムのセットから１つの圧縮アルゴリズムを識別し、圧縮アルゴリズムの前記セットは、複数のムーブ・フォワード圧縮アルゴリズムからなる、ステップと、そして
前記１つの圧縮アルゴリズムに従って第１のデータを圧縮するステップと
を含み、
前記暗号化キーにより識別される１つの圧縮アルゴリズムに従って前記第１のデータを圧縮すると同時に、別の暗号化アルゴリズムを使用することなく、前記第１のデータを暗号化し、
ここで、前記複数のムーブ・フォワード圧縮アルゴリズムに従って前記第１のデータを前方に移動する量は、前記第１のデータに対応する、前記暗号化キーの単一ビットに依存する、
マシン可読媒体。
【請求項１４】
前記第１のデータは、単一の文字からなることを特徴とする前記請求項１３記載のマシン可読媒体。
【請求項１５】
前記暗号化キーを使用するステップは、前記圧縮アルゴリズムのセットから前記１つの圧縮アルゴリズムを識別するために単一ビットの前記暗号化キーを使用するステップを含むことを特徴とする前記請求項１３記載のマシン可読媒体。
【請求項１６】
前記方法は
前記圧縮アルゴリズムのセットから第２の圧縮アルゴリズムを識別するための前記変数の第２の値を決定するために前記暗号化キーを使用するステップと、そして
前記第２の圧縮アルゴリズムに従って第２のデータを圧縮するステップと
をさらに含むことを特徴とする前記請求項１５記載のマシン可読媒体。
【請求項１７】
前記方法は、
前記第１のデータを圧縮する前に、前記第１のデータの入れ替えを行うステップ
をさらに含むことを特徴とする前記請求項１３記載のマシン可読媒体。
【発明の詳細な説明】
【０００１】
発明の背景
発明の分野
本発明は、データの暗号化ならびにデータの圧縮に関する。より詳細に述べれば、本発明はデータの暗号化と圧縮を同時に行うことに関する。
【０００２】
背景
データの暗号化は、ほとんどものを書くことが始まって以来の個人、ビジネス、および政府の関心事である。より最近になっては、インターネット等の大衆伝達経路を介したデータ記憶ならびにデータの転送から、選択グループ以外に認識できないデータのストアならびに転送への要望が急増している。しかしながら、永久に発展し続けるコンピュータ・テクノロジによって、コードおよび暗号化スキームの解除つまり「解読」できる最新のコンピュータ・システムも高速化し続けている。つまり暗号化は、ますます難しいものとなっている。
【０００３】
それに加えて、世界が「情報化時代」に突入したことによって、データ圧縮という追加の要求が生じた。日常的に大量の情報のストアならびに転送が行われている。しかしながら、特に記憶デバイスおよび通信路は、記憶ならびに転送に対するユーザの要求に追随し得ないでいる。かくして、各種の圧縮テクニックを使用して、圧縮しないデータの場合に必要とするよりも小さい記憶デバイス、短い転送時間でデータがストアされ、あるいはその転送が行われることになる。
【０００４】
しかしながら、現在の圧縮ならびに暗号化の方法には、速度という点で１つの問題が存在する。実行される圧縮および／または暗号化の各追加のステップは、コンピュータ・システムよる追加の処理時間を必要とする。したがって、所望のストアもしくはデータ転送を得るためには、追加の時間が要求される。
【０００５】
以上のことから、データの圧縮ならびに暗号化を行う改良された方法が求められている。
【０００６】
発明の要約
データの圧縮と暗号化を同時に行うための方法および装置を開示する。本発明は、暗号化キーを識別し、当該暗号化キーを使用して圧縮アルゴリズムのセットから１つの圧縮アルゴリズムを識別する。その後、本発明は、当該１つの圧縮アルゴリズムに従ってデータを圧縮する。
【０００７】
以下、添付の図面を参照し、例を示して本発明を説明するが、本発明がこれらの図面によって限定されることはなく、また図面においては、類似の要素に類似の参照記号を用いるものとする。
【０００８】
詳細な説明
以下の説明においては、本発明の各種側面を説明する。しかしながら当業者であれば、本発明が、本発明の一部のみ、ないしはすべての側面を用いて実施し得ることを理解されるであろう。説明目的から、本発明を完全に理解させるため、具体的な数、材料および構成を示す。しかしながら、これについても当業者であれば明らかであろうが、本発明はこれらの特定の詳細から離れて実施できる。
【０００９】
以下の詳細な説明の一部は、コンピュータ・メモリ内のデータ・ビットを操作するアルゴリズムおよび記号表現として示されている。これらのアルゴリズムの記述ならびに表現は、もっとも効果的にその作用の実体を他の当業者に伝達するものとして、データ処理技術の当業者によって使用されている手段である。ここにおいて、また一般にアルゴリズムは、所望の結果を導く自己矛盾のない一連のステップであると解釈される。これらのステップは、物理量の物理的な操作を必要とする。通常これらの量は、ストア、転送、結合、比較、およびその他の操作が可能な電気または磁気信号となるが、それを必須とはしない。しばしば、専ら共通の用途を理由に、ビット、値、エレメント、記号、文字、項、数等としてこれらの信号を参照すると便利であることが立証されている。しかしながら、これらの、ならびに類似の用語のすべてが、適切な物理量に関連付けされており、その量に付された便宜上のラベルに過ぎないことを念頭に置く必要がある。特に示さない限り、以下の議論から明らかように、本発明の全体を通じて、「処理」または「演算」または「計算」または「判断」または「表示」等々は、コンピュータ・システムもしくは類似の電子コンピューティング・デバイスの、コンピュータ・システムのレジスタおよびメモリ内における物理的な（電子的な）量として表されたデータを操作し、物理量として同様に表現される、コンピュータ・システムのメモリまたはレジスタまたはその他の情報記憶デバイス、伝送デバイス、または表示デバイス内における他のデータに変換するアクションおよびプロセスを指す。
【００１０】
図１は、本発明の一実施形態に従ってデータの暗号化と圧縮を同時に行うためのデバイスを示したブロック図である。ここには、「コンクリプタ」１００、圧縮器セット１０５、および任意選択で順序変更セット１１０が図示されている。コンクリプタ１００は、入力キー１２０に基づき、入力ソース・データ１１５に対する圧縮と暗号化を同時に実行する。コンクリプタ１００の出力は、圧縮および暗号化が行われたデータ１２５であり、これを「コンクリプト済み」データと呼んでいる。
【００１１】
圧縮器セット１０５は、コンクリプタ１００による使用のための複数の圧縮アルゴリズムを包含している。一実施形態によれば、相当数の圧縮アルゴリズムが圧縮器セット１０５として使用可能である。実質的に任意数の圧縮アルゴリズムが圧縮器セット１０５として使用可能であるが、一般に少なくとも２つの圧縮アルゴリズムが圧縮器セット１０５として用意される。ここで、概して圧縮器セット１０５として使用可能な圧縮アルゴリズムの数が増加するほど、本発明のコンクリプション（圧縮暗号化）の安全性が高くなる（つまり、キーなしのデータの解読がより困難になる）ことに注意されたい。
【００１２】
複数の圧縮アルゴリズムのうち、いずれがコンクリプタ１００によって使用されるかはキー１２０に依存する。本発明の一実施形態によれば、圧縮器セット１０５内のコンクリプタ１００が使用可能な少なくともいくつかの圧縮アルゴリズムは、可変ビット・ストリーム圧縮器である。可変ビット・ストリーム圧縮器は、異なる入力文字が異なるビット数によって表現される出力を提供する。つまり、２つの異なる文字を圧縮すると、それぞれが異なるビット数によって表現され、たとえば文字「ｅ」が「０」により表され、文字「ｚ」が「１０１１０１１」によって表される。
【００１３】
順序変更セット１１０は、コンクリプタ１００による使用のための複数の順序変更アルゴリズムを包含している。詳細は後述するが、順序変更セット１１０およびコンクリプタ１００による順序変更の使用はオプションである。一実施形態によれば、相当数の順序変更アルゴリズムが順序変更セット１１０として使用可能である。事実上、任意数の順序変更アルゴリズムが順序変更セット１１０として用意することができる。複数の順序変更アルゴリズムのうち、いずれがコンクリプタ１００によって使用されるかはキー１２０に依存する。順序変更セット１１０として、ラビー・ラックオフ順列に基づく順序変更アルゴリズム等の各種広範な従来の順序変更アルゴリズムのいずれも使用することができる。ラビー・ラックオフ順列の詳細な解説については、ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｎ  Ｃｏｍｐｕｔｉｎｇ（ＳＩＡＭコンピューティング・ジャーナル）ｖ．１７、ｎｏ．２（１９８８年）３７３〜３８６ページのＭ．  Ｌｕｂｙ（Ｍ．ラビー）およびＣ．  Ｒａｃｋｏｆｆ（Ｃ．ラックオフ）による「Ｈｏｗ  ｔｏ  ｃｏｎｓｔｒｕｃｔ  ｐｓｅｕｄｏｒａｎｄｏｍ  ｐｅｒｍｕｔａｔｉｏｎｓ  ｆｒｏｍ  ｐｓｅｕｄｏｒａｎｄｏｍ  ｆｕｎｃｔｉｏｎｓ（疑似ランダム関数から疑似ランダム順列を構成する方法）」を参照されたい。
【００１４】
キー１２０は、任意の複数ビット・キーまたはパスワードとすることができる。キー１２０には、数字、アルファベット、もしくは記号形式、またはこれらの任意の組み合わせが可能である。英数字および記号は、ＡＳＣＩＩ（アスキー）コーディング等の広範な各種の従来方法において一連のビットに変換される。つまり、ユーザは、長々しい素数ないしはそれに類似した覚えにくいキーの使用を求められることなく、ユーザが覚えやすいワード、数字、フレーズ等を選択することができる。
【００１５】
ソース・データ１１５は、コンクリプタ１００によってコンクリプトされる入力データである。ソース・データ１１５は、プレーン・テキスト・データ、別の圧縮もしくは暗号化アルゴリズムによって圧縮ないしは暗号化されたデータ、イメージ・データ等を含む任意タイプのデータとすることができる。図示した例においては、コンクリプタ１００がソース・データ１１５を、文字毎ベースでコンクリプトする。変形実施形態においては、コンクリプタ１００がソース・データ１１５を、複数文字毎ベースでコンクリプトする。
【００１６】
図２は、本発明の一実施形態に従ってデータの暗号化ならびに圧縮を同時に行うステップを示したフローチャートである。まずステップ２０５において、データが受け取られる。図示した例においては、このデータは２文字または３文字ブロック等のような、複数文字からなるデータ・ブロックである。しかしながら、変形実施形態においては、それぞれのデータをより大きくし、たとえばセンテンス、パラグラフ、もしくはその他の文字のグループ、または入力データの任意数のビット（たとえば８ビットまたは１６ビット）の一部とすることも可能であり、逆に単一文字等のようにより小さくすることも可能である。
【００１７】
データを受け取るとコンクリプタ１００は、ステップ２１０において、キーに基づいて使用する特定の圧縮アルゴリズムを識別する。続いてステップ２１５においてコンクリプタ１００は、当該特定の圧縮アルゴリズムを使用してデータを圧縮し、オプションとしてそのデータの順序変更を行う。順序変更が行われる場合には、複数の順序変更アルゴリズムに対するインデックスとしてキー１２０が使用され、それによってアルゴリズムの１つが選択される。コンクリプタ１００は、キー１２０の個別のビットを使用し、あるいはそれに代えてキー１２０の複数のビットを使用して、詳細を後述するが、特定の圧縮アルゴリズムの選択と同様に、特定の順序変更アルゴリズムを識別することができる。キー１２０に基づく圧縮アルゴリズムの選択および、オプションとしての順序変更アルゴリズムの選択は、本発明の暗号化に関する部分である。コンクリプタ１００は、その後ステップ２２０において圧縮済みのデータを出力する。つまり、キーを用いて、使用する特定の圧縮アルゴリズムを識別することにより、データの圧縮および暗号化が同時に行われることがわかる。
【００１８】
したがって図２からわかるように、ソース・データは、暗号化ならびに圧縮プロセスが一体化された組み合わせを使用して、単一のステップで暗号化および圧縮が行われる。圧縮および暗号化を同時に行うことによって、本発明は、圧縮と暗号化を個別に実行する場合より、データを高速に圧縮し、暗号化することができる。さらにコンクリプタ１００の選択対象となる圧縮器セット１０５として使用可能な圧縮アルゴリズムを多数用意し、データの部分ごとに圧縮アルゴリズムを変更できるようにすれば、コンクリプタ１００は安全な暗号化プロセスを提供できる。したがって、本発明は、短時間にデータを圧縮し、かつ安全な暗号化を提供することができる。
【００１９】
コンクリプト済みのデータのデコンクリプション（伸張解読）は、データのコンクリプションに使用したステップの逆を実行することによって行われる。キーおよびコンクリプト済みのデータが与えられれば、デコンクリプタが、データの各部分の圧縮に使用された圧縮アルゴリズムを識別することが可能になり、それによって適切な伸張アルゴリズムを使用してデータを伸張することができる。
【００２０】
図示した実施形態においては、データの個々の文字ごとに、圧縮アルゴリズムを識別するためにキー１２０の各ビットが使用される。本発明の変形実施形態によれば、データの複数文字ごとに、単一のビットが使用されて圧縮アルゴリズムが識別される。例を示せば、キー１２０は、データのブロック全体、たとえばテキスト・ドキュメントの１パラグラフあるいはテキスト・ドキュメント全体に用いる特定の圧縮アルゴリズムを識別することができる。
【００２１】
本発明の一実施形態によれば、さらにキー１２０またはコンクリプト済みデータ１２５の暗号化によって追加のセキュリティが得られる。たとえば、デコンクリプトを行う相手に転送する前に、各種存在する従来の暗号化メカニズムのいずれかを使用してキー１２０またはコンクリプト済みデータ１２５を暗号化する。しかしながら、この種の追加の暗号化はデータ転送のセキュリティを高めるが、データをコンクリプトし、暗号化するための時間が増加するだけでなく、それを受け取って解読し、デコンクリプトする時間も増加することを認識する必要がある。この種の追加の暗号化方法の例としては、米国特許第５，１５９，６３２号、同第５，２７１，０６１号、および同第５，４６３，６９０号に見られる方法をはじめ、よく知られたＲＳＡアルゴリズム等の方法がある。
【００２２】
本発明の一実施形態によれば、図１に示した圧縮器セット１０５が、複数バリエーションの「ムーブ・フォワード(move-forward)圧縮アルゴリズムを備えている。ムーブ・フォワード・アルゴリズムは、周知のＢＳＴＷ圧縮アルゴリズムの変形である。標準ＢＳＴＷ圧縮においては、入力データに対応する文字のスタックが維持され、文字が入力データ内に現れるごとに、常にスタックの先頭に文字を移動する。圧縮プロセスの最後におけるスタックの状態が与えられれば、伸張器は、オリジナルのデータを再計算することができる。通常、ＢＳＴＷ圧縮内のスタックは、ＡＳＣＩＩ（アスキー）コーディングにある２５６文字を含む。ＢＳＴＷ圧縮に関するさらに詳しい議論については、１９８７年９月のＤ．Ａ．  Ｌｅｌｅｗｅｒ（Ｄ．Ａ．レレワー）およびＤ．Ｓ．  Ｈｉｓｃｈｂｅｒｇ（Ｄ．Ｓ．ヒシュバーグ）によるＡＣＭ  Ｃｏｍｐｕｔｉｎｇ  Ｓｕｒｖｅｙｓ（ＡＣＭコンピューティング・サーベイ）３、９を参照されたい。
【００２３】
ムーブ・フォワード圧縮においては、ＢＳＴＷ圧縮の場合と同様に入力データに対応する文字のスタックが維持され、文字が入力データ内に現れるごとに、スタック内を前方に、スタック内の現在のポジションより高いポジションまでそれを移動するが、必ずしもスタックの先頭まで移動されない。本発明の一実施形態によれば、スタックが２５６文字を含む。スタック・サイズの代表的な値は、２５６〜６５，５３６エレメントまでの範囲となるが、変形実施形態においては、これよりスタック・サイズを大きく、あるいは小さくすることもできる。本発明の一実施形態によれば、スタック内の各エントリまたはエレメントは、複数文字からなるデータのブロックであり、たとえば「ｅｄ」、「ｉｎｇ」、「ｔｈｅ」等となる。本発明の別の実施形態によれば、スタック内の各エントリまたはエレメントは、単一文字からなるデータのブロックであり、たとえば「ａ」、「ｂ」、「ｃ」等となる。
【００２４】
ムーブ・フォワード圧縮を使用するとき、スタック内における文字の新しいポジションは次式によって決定される。
ｘ＝ｙ−ｚ・ｙ
これにおいて、スタックの先頭はポジション０であり、ｘはスタック内におけるその文字の新しいポジション、ｙはその文字のスタック内における現在のポジション、ｚはゼロから１までの範囲の変数であり、文字を前方に移動させる程度を示す。この式から、ｚの値を大きくするほど、文字が前方に移動することがわかる。詳細は後述するが、ｚの値は、キーのビットに応じて動的に割り当てることができる。ここで、ｙおよびｚの値によっては、ｘが非整数値となり得ることに注意する必要がある。ｘが非整数値の場合は、各種ある丸め規則のいずれかに従ってｘの丸めを行う。たとえば、小数部を切り捨て、整数部のみを使用するｘの整数フロア(integer floor)を使用することが考えられる。１つの実装態様においては、ｘの小数部がカットオフ値０．５より大きければｘを切り上げ、そうでなければ切り捨てを行う。しかしながら、別の実装態様においては、ゼロから１までの範囲でこれとは異なるカットオフ値を使用することもできる。
【００２５】
図３は、ムーブ・フォワード圧縮アルゴリズムの選択および本発明の一実施形態に従ったデータの圧縮を示したフローチャートである。まずコンクリプタ１００は、ステップ３０５において個々のデータの複数文字ブロックを識別する。続いてコンクリプタ１００は、オプションのステップ３０７においてデータの複数文字ブロックを入れ替える。つまり、このオプションが選択されているときは、スタックの操作において、オリジナルのソース・データではなく、入れ替えが行われた後のデータの複数文字ブロックが使用される。
【００２６】
次にコンクリプタ１００は、その識別済みの複数文字ブロックがスタック内に存在するか否かチェックする。その複数文字ブロックがスタック内に存在しなければ、ステップ３１５においてそのブロックの実際の文字を出力する。しかしながら、識別済みの複数文字ブロックがスタック内に存在するときは、ステップ３２０においてスタック内のそのブロックのロケーションを識別し、ステップ３２５において、注目しているデータの複数文字ブロックの、圧縮後の表現としてそのロケーションを出力する。
【００２７】
図示した実施形態においては、エントロピ・ベースのエンコーダが使用されて、出力スタックのロケーションが、またスタック内に複数文字ブロックがないときはブロックの実際の文字が、それぞれエンコードされる。エントロピ・ベースのエンコーダは、可変ビット・ストリーム出力を提供し、スタック・ロケーションの数字が低いほど、ビット数が少なくなる。例を示せば、出力スタック・ロケーション内の値「０」は、スタック・ロケーション内の値「２５５」よりビット数が少ない。周知のホフマン・エンコーディング等の、各種ある従来のエントロピ・ベースのエンコーディング・スキームのいずれも使用することができる。
【００２８】
その後コンクリプタ１００は、ステップ３３０において識別済みの複数文字ブロックに対応するキー・ビットを識別し、さらにステップ３３５において、そのキー・ビットがゼロであるか否かをチェックする。このキー・ビットがゼロであれば、ステップ３４０においてコンクリプタ１００は、その複数文字ブロックを上方に向かって１／４だけ移動する。しかしながら、このキー・ビットがゼロでなければ、ステップ３４５において、その複数文字ブロックを上方に向かって１／２だけ移動する。この後ステップ３０５に戻り、次に複数文字ブロックについて以上のプロセスを繰り返す。
【００２９】
図示した実施形態においては、ソース・データ１１５の異なる複数文字ブロックが、キー１２０の異なるビットに対応する。通常ソース・データ１１５は、イメージまたはテキスト・ドキュメントのように、多数の複数文字ブロックからなるデータを含んでいる。ソース・データ１１５は、概してキー１２０内のビット数より多くの複数文字ブロックを含んでおり、そのためキー１２０の単一のビットがソース・データ１１５の複数のブロックに対応することになる。ソース・データ１１５の最初の複数文字ブロックは、キー１２０内のあらかじめ決定されたビット、たとえば先頭のビットに対応する。ソース・データ１１５の２番目の複数文字ブロックは、キー１２０内の次のビットに対応し、あらかじめ決定されたビットが先頭のビットであれば、それが２番目のビットになる。このシーケンスがキー１２０の末尾に到達するまで繰り返され、そこに到達すると、キー１２０の先頭に戻ってプロセスが繰り返される。したがって例を示せば、キー１２０を１２８ビットのキーであるとすれば、ソース・データ１１５の１２９番目の複数文字ブロックは、キー１２０の先頭のビットに対応する。
【００３０】
本発明の変形実施形態においては、キー１２０の単一のビットではなく、複数ビットが使用されて個々の複数文字ブロック用の圧縮アルゴリズムが識別される。複数のビットを使用する場合、個々の複数文字ブロックの圧縮に使用する圧縮アルゴリズムの数が増加する。たとえば、キー１２０から４ビットを使用して特定の圧縮アルゴリズムを識別する場合には、それぞれの複数文字ブロック用に使用できる圧縮アルゴリズムが２の４乗、すなわち１６になる。これらの異なる圧縮アルゴリズムの例としては、１／２、１／３、１／４、１／５、１／６等の前方移動を行うムーブ・フォワード・アルゴリズムが挙げられる。
【００３１】
ここで、キー１２０の複数ビットを使用して個々の複数文字ブロック用の圧縮アルゴリズムを識別する場合には、これらの複数ビットのセットをオーバーラップできることに注意が必要である。例を示せば、ビット１、２、３、および４を最初の複数文字ブロック用の圧縮アルゴリズムの識別に使用し、ビット２、３、４、および５を２番目の複数文字ブロック用の圧縮アルゴリズムの識別に使用するといった態様がある。それに代えて、複数ビットのセットをオーバーラップさせないことも可能である。その場合は、たとえば、ビット１、２、３、および４を最初の複数文字ブロック用の圧縮アルゴリズムの識別に使用し、ビット５、６、７、および８を２番目の複数文字ブロック用の圧縮アルゴリズムの識別に使用するという態様になる。
【００３２】
本発明の別の実施形態においては、出力データに対する入れ替えが、さらにステップ３２５において行われる。たとえば、キーからのバイトおよび識別ロケーションからのバイト、もしくはその両方を用いてステップ３２５からの出力バイトの排他的論理和を演算することができる。
【００３３】
図４ａ〜４ｆおよび図５ａ〜５ｆは、複数文字ブロックではなく単一文字のスタックを使用した圧縮プロセスの例を示している。ただし、これは説明を簡略化することのみを目的としたものであり、類似の態様でこのプロセスがデータの複数文字ブロックにも適用されることを認識する必要がある。
【００３４】
図４ａ、４ｂ、４ｃ、４ｄ、４ｅ、および４ｆは、本発明の一実施形態に従った圧縮プロセスの一例を示している。図示した例においては、ソース・データ・ストリームが「ＦＡＣＥＤ」であり、キーはビット・ストリーム「００１１」である。説明を簡略化するため、図４ａ、４ｂ、４ｃ、４ｄ、４ｅ、および４ｆそれぞれのスタック４００、４１０、４２０、４３０、４４０、および４５０を、各７文字に制限している。ただし、これは説明を容易にするためのみを理由としたものであり、スタックは任意数の文字を含むことができる。
【００３５】
図示したように、ソース・データ・ストリームの最初の文字は「Ｆ」である。文字「Ｆ」は、スタック４００内においてロケーション５を有していることから、コンクリプタ１００は値５を出力する。このソース・データ・ストリームの最初の文字は、キーの先頭のビット、すなわち「０」に対応する。前述の図３に示した実施形態に従うと、キー・ビットが「０」であるということは、その文字を上方に向かって１／４だけ移動することを意味する。５の１／４は１．２５であり、整数値に丸めると１になる。そこでスタック内において文字「Ｆ」を上方に１ロケーション分だけ移動して、図４ｂのスタック４１０に示されるようにポジション４とする。
【００３６】
ソース・データ・ストリームの次の文字は「Ａ」である。文字「Ａ」は、スタック４１０内においてロケーション０を有していることから、コンクリプタ１００は値０を出力する。ソース・データ・ストリームの２番目の文字は、キーの２番目のビット、すなわち「０」に対応する。キー・ビットが「０」であるということは、その文字を上方に向かって１／４だけ移動することを意味する。０の１／４は０であり、文字「Ａ」を上方に０ロケーション分だけ移動して、図４ｃのスタック４２０に示されるようにポジション０とする。
【００３７】
ソース・データ・ストリームの次の文字は「Ｃ」である。文字「Ｃ」は、スタック４２０内においてロケーション２を有していることから、コンクリプタ１００は値２を出力する。ソース・データ・ストリームの３番目の文字は、キーの３番目のビット、すなわち「１」に対応する。前述の図３に示した実施形態に従うと、キー・ビットが「１」であるということは、その文字を上方に向かって１／２だけ移動することを意味する。２の１／２は１である。そこでスタック内において文字「Ｃ」を上方に１ロケーション分だけ移動して、図４ｄのスタック４３０に示されるようにポジション１とする。
【００３８】
ソース・データ・ストリームの次の文字は「Ｅ」である。文字「Ｅ」は、スタック４３０内においてロケーション５を有していることから、コンクリプタ１００は値５を出力する。ソース・データ・ストリームの４番目の文字は、キーの４番目のビット、すなわち「１」に対応し、その文字を上方に向かって１／２だけ移動することになる。５の１／２は２．５であり、整数に丸めると３になることから、文字「Ｅ」を上方に３ロケーション分だけ移動して、図４ｅのスタック４４０に示されるようにポジション２とする。
【００３９】
ソース・データ・ストリームの最後の文字は「Ｄ」である。文字「Ｄ」は、スタック４４０内においてロケーション４を有していることから、コンクリプタ１００は値４を出力する。キーは４ビットしか有していないことからソース・データ・ストリームの５番目の文字はキーを「巻き戻す」ことになり、先頭のビット、すなわち「０」に対応する。「０」はその文字を上方に向かって１／４だけ移動することを示している。４の１／４は１であり、文字「Ｄ」を上方に１ロケーション分だけ移動して、図４ｆのスタック４５０に示されるようにポジション３とする。
【００４０】
前述したように、出力スタック・ロケーション（５、０、２、５、および４）は、エントロピ・ベースのエンコーダを使用してエンコーディングされ、可変ビット・ストリームのコンクリプト済みデータ出力となる。
【００４１】
図５ａ、５ｂ、５ｃ、５ｄ、５ｅ、および５ｆは、本発明の一実施形態に従った圧縮プロセスの別の例を示している。図示した例においては、ソース・データ・ストリームが「ＦＡＣＥＤ」であり、キーはビット・ストリーム「００１１」である。説明を簡略化するため、図５ａ、５ｂ、５ｃ、５ｄ、５ｅ、および５ｆそれぞれのスタック５００、５１０、５２０、５３０、５４０、および５５０を、各７文字に制限している。ただし、これは説明を容易にするためのみを理由としたものであり、スタックは任意数の文字を含むことができる。
【００４２】
図示したように、ソース・データ・ストリームの最初の文字は「Ｆ」である。文字「Ｆ」は、スタック５００内においてロケーション５を有していることから、コンクリプタ１００は値５を出力する。ソース・データ・ストリームの最初の文字は、キーの先頭のビット、すなわち「１」に対応する。前述の図３に示した実施形態に従うと、キー・ビットが「１」であるということは、その文字を上方に向かって１／２だけ移動することを意味する。５の１／２は２．５であり、整数値に丸めると３になる。そこでスタック内において文字「Ｆ」を上方に３ロケーション分だけ移動して、図５ｂのスタック５１０に示されるようにポジション２とする。
【００４３】
ソース・データ・ストリームの次の文字は「Ａ」である。文字「Ａ」は、スタック５１０内においてロケーション０を有していることから、コンクリプタ１００は値０を出力する。ソース・データ・ストリームの２番目の文字は、キーの２番目のビット、すなわち「１」に対応する。キー・ビットが「０」であるということは、その文字を上方に向かって１／４だけ移動することを意味する。０の１／４は０であり、文字「Ａ」を上方に０ロケーション分だけ移動して、図５ｃのスタック５２０に示されるようにポジション０とする。
【００４４】
ソース・データ・ストリームの次の文字は「Ｃ」である。文字「Ｃ」は、スタック５２０内においてロケーション３を有していることから、コンクリプタ１００は値３を出力する。ソース・データ・ストリームの３番目の文字は、キーの３番目のビット、すなわち「０」に対応する。前述の図３に示した実施形態に従うと、キー・ビットが「０」であるということは、その文字を上方に向かって１／４だけ移動することを意味する。２の１／４は０．５であり、整数値に丸めると１になる。そこでスタック内において文字「Ｃ」を上方に１ロケーション分だけ移動して、図５ｄのスタック５３０に示されるようにポジション２とする。
【００４５】
ソース・データ・ストリームの次の文字は「Ｅ」である。文字「Ｅ」は、スタック５３０内においてロケーション５を有していることから、コンクリプタ１００は値５を出力する。ソース・データ・ストリームの４番目の文字は、キーの４番目のビット、すなわち「０」に対応し、その文字を上方に向かって１／４だけ移動することになる。５の１／４は１．２５であり、整数に丸めると１になることから、文字「Ｅ」を上方に１ロケーション分だけ移動して、図５ｅのスタック５４０に示されるようにポジション４とする。
【００４６】
ソース・データ・ストリームの最後の文字は「Ｄ」である。文字「Ｄ」は、スタック５４０内においてロケーション５を有していることから、コンクリプタ１００は値５を出力する。キーは４ビットしか有していないことからソース・データ・ストリームの５番目の文字はキーを「巻き戻す」ことになり、先頭のビット、すなわち「１」に対応する。「１」はその文字を上方に向かって１／２だけ移動することを示している。５の１／２は２．５であり、整数に丸めると３になることから、文字「Ｄ」を上方に３ロケーション分だけ移動して、図５ｆのスタック５５０に示されるようにポジション２とする。
【００４７】
前述したように、出力スタック・ロケーション（５、０、３、５、および５）は、エントロピ・ベースのエンコーダを使用してエンコーディングされ、可変ビット・ストリームのコンクリプト済みデータ出力となる。
【００４８】
このように、図３、４ａ〜４ｆ、および５ａ〜５ｆに示したように、図１に示したコンクリプタ１００は、キー１２０を使用して圧縮器セット１０５からソース・データ１１５の文字用の特定の圧縮アルゴリズムを識別する。図４ａ〜４ｆおよび５ａ〜５ｆの例においては、圧縮器セット１０５内に用意されている圧縮アルゴリズムが２つだけである。これらの例は、説明を容易にするために２つの圧縮アルゴリズムに制限されており、本発明の別の実施形態は、これよりかなり多くの圧縮アルゴリズムを包含する。
【００４９】
さらに図３、４ａ〜４ｆ、および５ａ〜５ｆに示した実施形態においては、キー１２０のビットの値がムーブ・フォワード圧縮アルゴリズムにおける変数の値の識別に使用されている。別の実施形態においては、キー全体が使用されて、ソース・データ１１５のすべてに用いるための特定の１つのアルゴリズムが圧縮器セット１０５から識別される。したがって、ｍビットのキーは、圧縮器セット１０５内の２ｍ個の圧縮アルゴリズムから固有の１つを識別することになる。
【００５０】
図６は、本発明の一実施形態に使用することができるハードウエア・システムまたはマシンを示している。図示の実施形態においては、ハードウエア・システム６００が、図示のように相互に接続されたプロセッサ６０２およびキャッシュ・メモリ６０４を備える。それに加えてハードウエア・システム６００は、高性能入力／出力（Ｉ／Ｏ）バス６０６および標準Ｉ／Ｏバス６０８を備える。ホスト・ブリッジ６１０は、プロセッサ６０２を高性能Ｉ／Ｏバス６０６に接続し、Ｉ／Ｏバス・ブリッジ６１２は、２つのバス６０６および６０８を互いに接続する。バス６０６には、ネットワーク／通信インターフェース６２４、システム・メモリ６１４、およびビデオ・メモリ６１６が接続されている。ビデオ・メモリ６１６には、表示デバイス６１８が接続されている。一方、バス６０８には、大容量記憶デバイス６２０、キーボードおよびポインティング・デバイス６２２、およびＩ／Ｏポート６２６が接続されている。これらのエレメントは、集合的にハードウエア・システムの広いカテゴリを表すことが意図されており、それには、限定する意図ではないが、イリノイ州ショーンバーグのＭｏｔｏｒｏｌａ，  Ｉｎｃ．（モトローラ・インク）から提供されているＰｏｗｅｒＰＣ（登録商標；パワーＰＣ）プロセッサ・ファミリのプロセッサ、もしくはカリフォルニア州サンタクララのＩｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎ（インテル・コーポレーション）から提供されているＰｅｎｔｉｕｍ（登録商標；ペンティアム）プロセッサ・ファミリのプロセッサをベースにした汎用コンピュータ・システムが含まれる。
【００５１】
これらのエレメント６０２〜６２６は、当分野で周知の従来的な機能を実行する。特にネットワーク／通信インターフェース６２４は、システム６００と広範多岐にわたる従来のネットワーク、たとえばイーサネット、トークン・リング、インターネット等の間で通信するために使用される。ここでは、インターフェース６２４の回路が、システム６００に接続されるネットワークのタイプに依存することを認識する必要がある。
【００５２】
大容量記憶デバイス６２０は、前述したコンクリプションの機能を実行するためのデータおよびプログラミング・インストラクションを恒久的に記憶するために使用され、それに対してシステム・メモリ６１４は、プロセッサ６０２による実行時に、データおよびプログラミング・インストラクションを一時的に記憶するために使用される。
【００５３】
Ｉ／Ｏポート６２６は、ハードウエア・システム６００に接続される追加の周辺デバイスとの間で通信するために使用される、１ないしは複数のシリアルおよび／またはパラレル通信ポートである。
【００５４】
ハードウエア・システム６００の各種コンポーネントは、構成変更が可能であることを認識する必要がある。たとえばキャッシュ６０４をオンチップとしてプロセッサ６０２に備えてもよい。さらに、本発明のある種の実装においては、上記のコンポーネントのすべてが必要にならないこともあり、また含んでいないこともある。たとえばシステム６００が、大容量記憶デバイス６２０、キーボードおよびポインティング・デバイス６２２、および／または表示デバイス６１８ならびにビデオ・メモリ６１６を含まないこともある。それに加えて、標準Ｉ／Ｏバス６０８に接続されるものとして示されている周辺デバイスを高性能Ｉ／Ｏバス６０６に接続してもよく、また一部の実装においては、単一のバスしかなく、ハードウエア・システム６００のコンポーネントが、単一バスに結合されてもよい。さらに、追加のプロセッサ、記憶デバイス、またはメモリといった追加のコンポーネントがシステム６００に含められることも考えられる。
【００５５】
一実施形態においては、図１に示したコンクリプタ１００が、図６に示したハードウエア・システム６００によって実行される一連のソフトウエア・ルーチンとして具体化される。これらのソフトウエア・ルーチンは、ハードウエア・システム内のプロセッサ、たとえば図６に示したプロセッサ６０２によって実行される複数の、もしくは一連のインストラクションを包含している。当初、これらの一連のインストラクションは、大容量記憶デバイス６２０等の記憶デバイスにストアされている。ここで、これらの一連のインストラクションが、ディスケット、ＣＤ−ＲＯＭ、磁気テープ、ＤＶＤ（ＤＶＤは、現在のところ、ディジタル・ビデオ・ディスクを表す略語として使用されているが、その用途は、ビデオのほかにデータにも使用できるＤＶＤテクノロジの能力を反映してディジタル多目的ディスクに変わりつつある）、レーザ・ディスク、ＲＯＭ、フラッシュ・メモリ等の任意の従来メディア上にストア可能であることを認識する必要がある。さらに、これらの一連のインストラクションがローカルにストアされている必要はなく、ネットワーク上のサーバ等のリモート記憶デバイスからネットワーク／通信インターフェース６２４経由で受け取ることも可能である点に注意されたい。
【００５６】
インストラクションは、大容量記憶デバイス６２０等の記憶デバイスから、メモリ６１４にコピーされた後、プロセッサ６０２によってアクセスされ、実行される。具体化の１つにおいては、これらのソフトウエア・ルーチンが、Ｃ＋＋プログラミング言語によって記述される。しかしながら、これらのルーチンが、各種広範なプログラミング言語のいずれを用いても実装し得ることを認識する必要がある。
【００５７】
変形実施形態においては、本発明が個別のハードウエアまたはファームウエアに実装される。たとえば、変形実施形態の１つにおいて、特定用途向け集積回路（ＡＳＩＣ）に、前述した本発明の機能をプログラムすることができる。
【００５８】
本発明の一実施形態によれば、図１においてコンクリプタ１００による使用のために圧縮器セット１０５内に用意された圧縮アルゴリズムのそれぞれは、可逆圧縮アルゴリズムである。可逆圧縮においては、圧縮されるデータ・ブロックの「サイズ」が、データがまったく失われずに縮小される。つまり、データ・ブロックを圧縮し、ストアし、あるいは転送し、その後伸張したとき、伸張後のデータ・ブロックがオリジナルのデータ・ブロックとまったく同一になる。別の実施形態においては、圧縮器セット１０５が非可逆圧縮アルゴリズムを含む。非可逆圧縮においては、データ・ブロックのサイズが縮小され、少量のデータが失われる。したがって、データ・ブロックを圧縮し、ストアし、あるいは転送し、その後伸張したとき、オリジナルのデータ・ブロックとわずかな差を生じる。非可逆圧縮においてはデータの一部が失われるが、イメージ・データ等のある種のデータについては、通常、ユーザが明確に認識できるほどデータが失われることはない。
【００５９】
前述した説明においては、「ムーブ・フォワード」圧縮アルゴリズムを使用する実施形態について述べた。しかしながら変形実施形態においては、異なるタイプの圧縮アルゴリズムまたは、別のタイプの圧縮アルゴリズムとムーブ・フォワード圧縮アルゴリズムの組み合わせが使用できることに注意する必要がある。
【００６０】
以上、データの暗号化ならびに圧縮を同時に行うための方法および装置について述べてきた。当業者においては、以上の説明を読んだ後であれば、本発明に係る多くの変更ならびに変形に気づかれようが、例証として示し、説明した特定の実施形態は、限定と見なされることを意図したものでないことを当然に理解される必要がある。特定実施形態の詳細に対する参照には、特許請求の範囲を限定する意図がない。
【図面の簡単な説明】
【図１】  本発明の一実施形態に従ってデータの暗号化ならびに圧縮を同時に行うためのデバイスを示したブロック図である。
【図２】  本発明の一実施形態に従ってデータの暗号化ならびに圧縮を同時に行うステップを示したフローチャートである。
【図３】  ムーブ・フォワード圧縮アルゴリズムの選択および本発明の一実施形態に従ったデータの圧縮を示したフローチャートである。
【図４】  本発明の一実施形態に従った圧縮プロセスの一例を示す。
【図５】  本発明の一実施形態に従った圧縮プロセスの別の例を示す。
【図６】  本発明の一実施形態に使用することができるハードウエア・システムまたはマシンを示す。
【図１】
0004739519.tif 000002
【図２】
0004739519.tif 000003
【図３】
0004739519.tif 000004
【図４】
0004739519.tif 000005
【図５】
0004739519.tif 000006
【図６】
0004739519.tif 000007