画像に情報を埋め込む -SteganographyとWatermarking-
大学でSteganography and Watermarkingについての講義があった。
SteganographyといえばCTFでたまに出題されるが、Gussingクソ問が多くあまり良いイメージを持っていなかった。実際には色々と考えられているようで面白い分野だった。試しに両方の簡単な実装を行った。
SteganographyとWatermarking
この2つは目的が異なっている。Steganographyは「データを隠す」ことが目的であり、Watermarkingは「データに埋め込んだ情報が指定の変換に対して頑健であったり、除去することが難しい」ことを目的としている（多分）。
Watermarking
Watermarkingの目的としては著作者人格権保護などが挙げられる。たまにTwitterで他人が描いた絵を自分が描いたと言い張る人間がいるが、そういう時にどうすれば描いた本人の保証できるかを考えていた。
これはkeyに依存して画像サイズの乱数列Wrを生成し、目的のbitが0であればWr, 1であれば-Wrを画像に足し込むという手法が有名らしい。足しこんだ後の画像とWrの内積を取ることで1bitの情報を得ることが出来る。
実際には内積を取るのではなく平均値を引いた後に内積を取ってベクトルの長さで正規化することで、元の画像の性質に依らずに棄却領域を割り出す事ができる（この理論で射影空間とかがちょっと出てきて面白い）。
これを拡張して1枚の画像にn-bitの情報を埋め込めるようにする。これは画像をn個に分割してそれぞれに1bit情報を埋め込むことにした。ここでどのように分割したかが分からないようにkeyに依存して生成した乱数列によってシャッフルする。
ユーザーはkeyがわからない時に画像の情報を大きく損なわずにWrを除去するのが難しいと思われる（フィルタ掛けたりされると厳しい。白色ガウスノイズの乗せたり輝度変化したりには強いことが知られている。）
しかし、これではユーザーがWatermarkingの検証を行うことが出来ない。除去の困難性を保証するのはWrがどこに埋め込まれているかを知らないからである。
何とかして万人が検証可能で除去が困難なWatermarkingを作れないか考えたがTrusted Third Partyが存在しない限りは無理そうだった。これなら簡単で、画像とkeyとメッセージをTTPに渡して埋め込んでもらうと良い。ここでどこに埋め込まれているかは画像の作成者すら知らない。乱数はkeyとTTPのみが知る情報によって生成される。keyとTTP保有のデータで新しいkeyを作るイメージ。その後に画像とkeyを公開すれば万人がTTPに対してリクエストすることで検証を行う事ができ、またどこに埋め込まれているか分からないので除去も困難である。
Steganography
Steganographyの目的としては情報を持っている事自体の秘匿が挙げられる。つまり、画像中にデータが存在していることすらバレてはいけない。
こちらはいろんな操作に対して頑健である必要はないので一般にはWatermarkingより画像に埋め込むことができるデータ量が増える。僕の実装では800x500程度の画像中にWatermarkingでは数十byteしか埋め込めなかった一方、Steganographyでは数十Kbyte埋め込むことが出来た。なんと1000倍！（Steganographyならある画像のpngにその画像のjpegを埋め込むことくらいなら出来る）。
こちらもWatermarkingと同様にkeyに依存した乱数列を作ってやり、あとはテキトーにランダムに選んだ画素の下位1bitに埋め込むだけで良い。強いて言えば埋め込むメッセージにProbabilistic Encryptionを施すとIND-CCA安全やらが保たれて良さそう。
あまりに大量のデータを埋め込むと下位bitが一様乱数に近くなるので、DCTでスペクトルを出した時に高周波成分が多く出てそれによって埋め込んでいることがバレるかもしれない。真っ白な画像に埋め込むと即バレる。自然風景画像やらに埋め込むと強そう。
