FC2ブログ
C言語を使ったゲームプログラムや、隼君とお出かけしたツーリング日記などを書いています(´▽`)

C言語と ゲームと 時々 隼君日記

Dixqの週末 | main | いつもと違って
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
| スポンサー広告 | --:-- |
暗号化プログラム
※今回の話はプログラムの話なのでプログラムに興味無い人は面白くないかも?!※


簡単で、ある程度実用的で、改竄チェックの出来る暗号化の方法無いかな~と考えている今日この頃です。

考えているのは「簡単で」ってのが一番重要です。かといってシーザー暗号みたいな使い物にならないものはダメw

暗号化する為のライブラリはいくつか公開されているようですが、なるべく標準ライブラリのみで、かつ簡単に実装したいと思っています。
ゲームプログラミングの館で論理積と論理和でわけて保存する方法紹介しているけど、組み合わせによっては改竄が解らない場合があるし、あれではダメなんですよね~。

やはり簡易暗号化の王道と言えば排他的論理和。
一応ブログなので、説明すると排他的論理和とは、

0と0で0
0と1で1
1と0で1
1と1で0

を表すもので、同じ数で2回排他的論理和を計算すると元の数に戻るという性質を持つ計算方法です。

例えば「100」に「200」で排他的論理和を計算すると「172」になります。
(100^200→172)※「^」は排他的論理和を表す

「172」にもう一度「200」で排他的論理和を計算すると「100」になるのです。
(172^200→100)

つまり 100^200^200 は 100なのです。(各ビット全て紙に書いて排他的論理和を計算すると解ります)

例えばゲーム中の所持金が100円だとして、セーブデータファイルに100と保存したいと思います。
しかし、100と保存してしまうと、ユーザーが勝手にファイルを開いて1000にしてしまうかもしれません。

ここで、排他的論理和の出番と言う事です。
100をそのままファイルに保存するのではなく、一度暗号化キーである「200」で排他的論理和を計算した172をファイルに保存します。

172であればもう一度200を排他的論理和することで正常に100に変換出来ますが、他の値では戻す事は出来ません。

と言う事でセーブデータには排他的論理和をという考え方があるのですが、結局ユーザーが期待する改竄が出来なくなる(1000の排他的論理和は800)ものの、
データが改ざんされても発見できないので、何度も期待するデータになるまで書き換えて試しせば、そのうち期待する改竄が出来てしまいます。

そこでこんな方法考えてみました。

01_20100730232707.jpg

今、aの配列に入っているデータをセーブしたいとしましょう。
a[0]のデータは乱数と排他的論理和の結果に変換してセーブします。
更にもう一度a[0]のデータは今度は違う乱数と排他的論理和を計算して結果をセーブします。

つまり、一つのデータを二つにわけて保存します。
ですから、二つのどちらかさえ分かれば複合出来ます。

※?は乱数を意味する

02_20100730232706.jpg

dataOriginは元のセーブデータ、dataSaveは暗号化したセーブデータです。
dataSaveの方をセーブデータとして保存します。
ここで重要なのが、乱数のシードを一緒に保存しておくことです。

暗号化したファイルを複合化する時は、まず乱数のシードを読み込み、乱数の初期値を暗号化した時と同じにします。
そして、一つずつ乱数と排他的論理和を計算して元に戻します。
この時、同じデータを2つに分けて保存しましたが、計算結果は両方同じにならないとおかしいはずです。

00_20100730232708.jpg

ユーザーは見た目訳が解らないデータの羅列なので、改竄するならどこかを適当に変更するしかありません。
しかしどこか1か所でも適当に変更したら計算結果が狂うので改竄した事が検知出来ます。

こんなのどうかな~?なんて思いました。
もし、この考え方には穴があるよ!
とかもっと簡単かつ有効な方法があるよ!って方いらっしゃいましたらアドバイス下さい~ヽ(´▽`)ノ



一応上の理論実装したプログラム置いてきます。
SAVEの定義を有効にするとセーブデータが作られます。外すと作ったセーブデータをデコードします。
http://dixq.net/private/Encrypt.cpp
スポンサーサイト
| 未分類 | 22:35 | トラックバック:0コメント:6
コメント
パリティチェックのような事も合わせてやってやれば効果あがるかな・・?
2010.07.31 Sat 02:20 | URL | Dixq
 PCフリーゲームのセーブデータという用途を考えるならこれで十分だと思います。

 ただ元データの2倍必要になるところとかどうなんでしょうね。
 改竄を調べるなら MD5とかのハッシュを暗号化前のデータに入れておけば十分じゃないかと思いますけど。

 暗号としての実装面では randを使っているあたりが気になります。
 randの質に対する懸念もありますが、ビルド環境が異なるアプリ間で暗号化・復号化できない可能性が……ってそれも含めての暗号化って考えればそれもありかも。
2010.07.31 Sat 02:25 | URL | Justy
Justyさん

こんな所にまで来て下さってありがとうございます^^

> ただ元データの2倍必要になるところとかどうなんでしょうね。

確かに効率は悪いですね;

> MD5

なるほど、改竄チェックが出来る手法なんですね。
http://www.studyinghttp.net/md5
この辺でアルゴリズム確認してみましたが、プログラムが少々複雑になりそうな予感が・・><;

今回の日記の目的を述べていませんでした。
実は館とかで紹介している簡易暗号化があまりにも穴があるので、簡単に実装出来て、かつ割と使い物になる方法を探していました。

しかしたとえ難しくなったとしても有効な方法であるならば両方解説して、閲覧者が好きに選べばいいようにすればよいですよね。

MD5を用いた方法も実装してみます。ありがとうございます^^

> randの質に対する懸念もありますが、ビルド環境が異なるアプリ間で暗号化・復号化できない可能性が

なるほど、ビルド環境の違いまで考慮していませんでした。
環境が変わっても有効な手法を考えるべきですね^^;
2010.07.31 Sat 10:46 | URL | Dixq
お久しぶりです。

個人的にはバイクよりプログラムの話の方が興味があり
まs(ry

md5の話が出てきたので・・・md5を使わなくてもという話です。


データに基づいた不可逆変換の暗号値を、読込み時に、同じアルゴリズムを元に再度データを不可逆変換の暗号値に変換して、暗号値が一致するかを見れば改竄を見抜くことができると思います。(これがmd5の根底だと思います)

要は、必ずしも暗号データを復元する必要は無いという事です。

復元する必要が無い(不可逆変換)という事は、大胆な暗号化をする事が可能になると思うのですが、注意する点としては、同じデータからは、同じ暗号値が生成されなければいけないという事です。

あとは、いかに「与えられた値から暗号データを生成するための関数」を簡単に実装するかですね。

2010.07.31 Sat 15:37 | URL | サウス
>簡単に実装出来て、かつ割と使い物になる方法を探していました
 なるほど。
 そうなるとちょっと改竄チェックとしては弱くなりますけど CRCとかチェックサムあたりで代用すると楽でしょうかね。
 ただのチェックサムでも暗号化してしまえばぱっと見た目わからなくなりますし。
2010.08.01 Sun 02:08 | URL | Justy
> サウスさん

バイクの話は完全に自己満足だと思ってます^^;
mixiだとプログラムの話は人気ないことが多いんですが、見てくださっている方が違うんですねw

> 要は、必ずしも暗号データを復元する必要は無いという事です。

なるほど^^
データの実装の仕方や中身がばれて困るわけではなく、要するに改ざんさせたくないだけですからね。
参考になります^^


> Justyさん

mixiにも同じ日記を書いたところ、ま~くさんにCRCの件アドバイス頂きました。
やはり偉い人の行き着く答えは同じなのですね(ぇ
しかしこのようにアドバイス頂けて助かります。ありがとうございます^^

ただ今回の件で、自分であれこれ考えるより先人の考えたアルゴリズムを探すほうがよっぽど有効なんだということがわかりましたw
2010.08.02 Mon 00:00 | URL | Dixq (管理人)
コメントする














管理者にだけ表示を許可する

この記事のトラックバックURL
http://directxq.blog58.fc2.com/tb.php/284-93f1a57f
この記事にトラックバックする(FC2ブログユーザー)
トラックバック
| ホーム |

プロフィール

Dixq

Author:Dixq
FC2ブログへようこそ!

最近の記事
最近のコメント
最近のトラックバック
月別アーカイブ
カテゴリー
ブロとも申請フォーム
ブログ内検索

RSSフィード
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。