逆数え上げ符号化・復号法

全文

(1)社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 2003−CSEC−23 (7) 2003／12／19. 逆数え上げ符号化・復号法鈴木英男. あらまし. プリペイドカードのデータ改ざん検出に一方向性記録媒体と. 符号には. の数え上げ符号. のバランス符号. 符号が利用できる. 符号などの符号化法が知られ. ている数え上げ符号の符号化を逆順に行うと逆数え上げ符号が得られるが簡単で容易に理解できる逆数え上げ符号の符号化・復号アルゴリズムを示したこれらアルゴリズムはそれぞれステップ追加するだけで数え上げ符号の符号化・復号アルゴリズムとして使えるものである. キーワード数え上げ符号重み一定符号一方向性誤り改ざん検出プリペイドカード. 東京情報大学環境情報学科〒. 千葉市若葉区谷当町. −37−.

(2) まえがき近年プリペイドカードに関する偽造変造改ざんなどの犯罪が大きな社会問題となっているプリペイドカードは紙幣と同様の価値をもつ金券として扱われ方によっては個人に莫大な損害を与えかねない恐ろしいものであるこの問題に対応するために種々の改良が加えられてきた情報の暗号化もその対策の一つであるが暗号の対策だけでは不十分であったそこで一方向性記録媒体とすべての改ざんを検出できる符号を組み合わせての使用がこの問題に非常に効果的に働くことが考えられる例えば次のように実現できる特殊な設備でしか製造し得ないホログラムパターンをもつプリペイドカードを媒体に用いることで偽造困難なカードとするそのホログラムパターンを破壊するかしないかによってディジタル情報の単位ビットを表現することで一方向性記録媒体を構成するその情報の符号語にすべての改ざんを検出できる符号を用いて改ざん不可能なカードとすることができるのである. 符号一方向性記録媒体においてすべての改ざんを検出できる符号としては. 符号. 全一方向誤り検出符号があるここで情報理論における「誤り」は意図的な誤りとしての改ざんの意味を含む符号. 符号には. の数え上げ符号. などの符号化法が知られている. の数え上げ符号. 表. 数え上げ符号の符号化例情報進. 数え上げ符号語. 進. の符号化例を表に示す. ←→ 数え上げ符号語. 進. 進. 進. 進ではのように. ら数え上げてそれぞれ. 進情報. と呼ばれる所以である. ∼. 進数の重み付けで昇順に並べて小さい方か. に対応させるのであるこれが数え上げ符号. 進はハミング重みの重み一定符号. 符号とも言うとなる符号語の個数は二項係数が. のバランス符号. 個の場合は符号化できるこの符号を記録する媒体が. 進は ∼ →. より. 個となる扱える符号語の個数. までとなる. の一方向にしか記録できない一方向性記録媒体の場合. ビットでも. 改ざんされればハミング重みが変化してしまうので重み一定符号はすべての改ざんが検知できるのである. →. の一方向にしか記録できない媒体の場合も同様のことが言えるのバランス符号となり. とは例えば. 情報が. のとき左から. との数がバランスする左から数えた位置を. が反転位置情報部となるこのとき置情報部を連接させて. のバランス符号語は一部分. となりハミング重み. −38−. の重み一定符号. ビットを反転させれば. の重み一定符号で表現した反転された情報部と反転位符号とも言う.

(3) となるバランス符号も重み一定符号なので改ざん検出の原理は数え上げ符号と同様である符号. とは例えば. で表現するととなる. →. 情報が. のとき. が検査部となるこの場合. のビット数を数えるとである. を進数. 符号語は情報部と検査部を連接させて. の一方向にしか記録できない一方向性記録媒体を仮定すると例えば情報部のある. 情報ビットが改ざんされ. になったとすると正しい符号語とするためには. 査部をからにしないといけないが一方向性記録媒体のために号はすべての改ざんを検知できる. →. は. つの. のビット数を表す検. にならないので. 符. の一方向にしか記録できない媒体の場合も同様のことが言える. 検査部が改ざんされた場合は数え上げ符号と同様に検知できる数え上げ符号をバランス符号. 符号と比較するとバランス符号と. 数え上げ符号は非組織符号であるなり. 符号の符号語は. 符号は組織符号であり. の情報を符号化する場合数え上げ符号の符号語はとなりバランス符号では. の良い符号である一方数え上げ符号の符号化処理では複数回算量が大きいという欠点があり情報ビット数が不充分とされてきたしかしながら今日の. と. となり数え上げ符号が一番効率項係数を計算する必要があるために計. のように大きい場合従来の. 処理能力では. 処理能力からはさほど問題ではなくなってきている. 本論文では数え上げ符号を逆順に数え上げた逆数え上げ符号の符号化・復号法を開発したので報告する. 逆数え上げ符号の符号化・復号法逆数え上げ符号の符号化例を表に示す表. 逆数え上げ符号の符号化例情報進. 表を表と比較すると. ←→. 進. ←→ 逆数え上げ符号語. 進. 進. 進. の対応が逆順になる数え上げ符号と逆数え上げ符号の違いは単に. 順番が逆なだけので数え上げ符号から逆数え上げ符号を得ることや逆数え上げ符号から数え上げ符号を得ることは容易である数え上げ符号の符号化アルゴリズム. →. を. に復号アルゴリズム. →. を. に示すのアルゴリズムとなり. を省くと数え上げ符号の符号化アルゴリズムが逆数え上げ符号の符号化の. を省くと数え上げ符号の復号アルゴリズムが逆数え上. げ符号の復号アルゴリズムとなるこれらアルゴリズムは基本的に逆数え上げ符号のために開発したものでありそれぞれに図を用いて. を追加して数え上げ符号化・復号に使えるようにしたものであるを除く逆数え上げ符号の復号アルゴリズム. −39−. の基本原理を説明す.

(4) るまず組合せ論の基本定理. により符号語集合を分割していく例えば表. のように下の数. に分割され. の場合第. がとなったら分割を終了する. 段階で次のように分割する. は. は. に分割される下の数. がとなるか. 割するときには分割前の最も左のビットが. 分割が終了する条件により次の. 以上により逆数え上げ符号. のようにであるか. となる場合にも分割を終了する分であるかで次のように処理が分かれる. 通りの処理が行われる. は復号されるのである符号化の原理は復号の原理から容易に推察でき. るので紙数の都合上ここでの説明は省略する. むすび本論文では逆数え上げ符号の符号化・復号法を示したその原理は号化・復号法よりも直感的に理解しやすいものであるまた. の数え上げ符号. の符. を追加することで容易に数え上げ. 符号の符号化・復号法とすることができるものであるこの数え上げ符号の符号化・復号アルゴリズムを任意多倍長整数演算パッケージを用いてにしたムは. 言語プログラムを実現した. という非常に大きな値を扱えるよう. 符号を符号化・復号するのにかかる処理時間は１秒程度である本論文のプログラ以上の数も扱うことが可能なので将来より高速な. が出現すれば. の符号化. も現実的な処理時間で符号化・復号できるものである一方向性記録媒体にこの数え上げ符号の符号化・復号プログラムを用いて情報を記録するとすべての改ざんを検出できるプリペイドカードを実現することができる. の重み一定符号では. の大きな情報を１つの符号語で記録できるので実用性の高いものとすることができた. −40−. も.

(5) 参考文献. −41−.

(6) . . │. │. │. │. │. │. ↓. ↓. ↓. →. 図. の原理. −42−.

(7)