消失訂正とは? わかりやすく解説

消失訂正

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/10/12 00:38 UTC 版)

消失訂正(しょうしつていせい、erasure correction)とは、前方誤り訂正において、特に発生した誤りの位置が判明している場合にそれを復元することである。

改竄検出ではない誤り検出訂正符号は、たとえ誤り訂正能力を持たなくともその検出能力内であれば消失訂正が可能である。 また改竄検出であっても、総当たりをすれば消失訂正できる可能性が高い[注釈 1]

消失訂正は一般に、誤り検出訂正の逆算を行なうことを言い、下記の例もそれに従う。が、基本的に消失範囲にあり得る値の全てを試行して符号語に一致する唯一の値を発見することでも可能である。

チェックサム

チェックサムは、各情報の総和を符号語とした誤り検出である。

1,2,3,4を情報とした場合、符号語は1+2+3+4=10となる。この場合、例えば三番目の情報が消失し1,2,X,4となっていた場合、(1+2+X+4)=10→10-(1+2+4)=Xとして消失した情報を得る。

パリティビット

パリティビットは、各ビットの排他的論理和を符号語としたものである。

101101を情報とした場合、排他的論理和を⊕とすると符号語は1⊕0⊕1⊕1⊕0⊕1=0となる。この場合、例えば三番目の情報が消失し10X101となっていた場合、1⊕0⊕X⊕1⊕0⊕1=1→1⊕(1⊕0⊕1⊕0⊕1)=Xとして消失した情報を得る。

応用

一般的に前方誤り訂正が求められる場合には、消失訂正よりも汎用性の高い誤り訂正が用いられる。しかし別途消失箇所を特定する手段がある場合には、汎用性の高い誤り訂正と比較して低コストな誤り検出を使用する消失訂正が用いられる。

RAID

RAIDの5および6では、水平パリティと呼ばれるパリティビット(誤り訂正能力を持たない誤り検出符号)を用いて、読み書きに失敗した[注釈 2]ハードディスクドライブを消失位置として消失訂正を行なうことで耐障害性を高めている。

さらにRAIDの6では、それに加えてQパリティと呼ばれるCRC[注釈 3]を併用することで、単独での消失訂正の他に、水平パリティと組み合わせた連立方程式を解くことで二台のハードディスクドライブが故障しても耐えられる消失訂正を行なっている。

コンピュータウイルス

ファイル圧縮伸長プログラムLHAは、そのアーカイブファイルが通信エラーなどにより破損していないことを確認するためのCRCを用いた検査能力を持っていた。この機能はアーカイブファイルとして自分自身を指定すると自己検査するようになっていた。なのでこれにコンピュータウイルスが感染すると「破損している」と看做されるので手軽に感染が判明した。そのためにコンピュータウイルス配布者はCRC符号を含めて書き換えてから配布するようにしたが、今度はオリジナルのLHAのCRC符号を公開することで対策された。そこでコンピュータウイルスの一部に未使用領域を設け、感染LHAに対して当該未使用領域が消失したものとして消失訂正を行なうことで公開CRC符号と一致する感染LHAを生成した。

これはCRC符号を始めとする誤り検出訂正符号では改竄検出ができないことを示す一例となっている。

また改竄検出であっても、その改竄検出符号ごと差し替えられてしまえば検出はできないことも示している。これを防ぐためには電子署名メッセージ認証符号などの、単なる検出符号にとどまらない対策が必要となる。

脚注

注釈

  1. ^ 必ずできるわけではない。詳しくは改竄検出#消失訂正を参照。
  2. ^ 壊れた、であるが、必ずしも壊れたとは限らない。
  3. ^ これも誤り訂正能力を持たない誤り検出符号である

出典

関連項目


消失訂正

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/25 05:06 UTC 版)

改竄検出」の記事における「消失訂正」の解説

改竄検出では消失訂正はできないが、それが本当に消失したであれば、その消失範囲総当たり再計算して同じ符号語となるものを探すことで高い確率で消失訂正が行なえる。 しかしそれが行なえることは保証されていない保証できるような数学的関連性持っていないことが暗号学的ハッシュ関数重要な特徴だからである。 同様に消失範囲総当たりする場合には「本当に総当たりをしなければならない。それはその消失範囲中に同じ符号語となる値が複数含まれていて一つ定まらない可能性があるからである。一つに定まらなかったなら消失訂正に失敗したことになる。この一つ定まらない場合とは単なる衝突のことではないので、誕生日のパラドックス発生しないこのため改竄検出符号用いて消失訂正を行なうことは(特に暗号学的ハッシュ関数実行高コストであることから)非現実的であり、自動再送要求などの再送可能な状況下での使用想定される。もしも前方誤り訂正を必要とする場合には別途誤り訂正符号設けるのが現実的であるが、この誤り訂正により改竄耐性失われ大きなセキュリティホールとなる場合があるので併用の際には充分な注意が必要である。その他の攻撃存在考え合わせれば前方誤り訂正をするのではなく改竄検出され段階でただちに全て破棄して切断し再接続するべきである。

※この「消失訂正」の解説は、「改竄検出」の解説の一部です。
「消失訂正」を含む「改竄検出」の記事については、「改竄検出」の概要を参照ください。

ウィキペディア小見出し辞書の「消失訂正」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「消失訂正」の関連用語

消失訂正のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



消失訂正のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの消失訂正 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの改竄検出 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS