アイデア: 秘密分散法とワンタイムパッド使って、異なるサーバーにデータを分散して安全性を高めたい案
前提とか目的とか
セキュアにchatする方法を考えていて思いついたのでメモ。Chatに限らずデータ送信で使える。
サーバーを信用しないというのが前提で考えている。
サーバーがデータを保存したとしても、他のサーバーのデータを得ない限り、復号できないはず。
チャット以外でも使えるが、Nを大きくするとデータ量 x Nのデータを送信する必要があるため、チャットみたいな小さいデータに向いてそう。
手法
まずは、シンプルに2つに分散する例。
($ \oplusはXOR)
1. 元データ$ Srcがある
2. $ Srcと同じ長さのランダム$ R1を生成する
3. $ R2 = Src \oplus R2 で$ R2を生成する。
送信者は$ R1と$ R2を受信者に送る。
受信者は$ Src = R1 \oplus R2で$ Srcを得る。
$ R1と$ R2は完璧にランダムであり、片方だけを取得しても$ Srcを論理的に復元不可能なはず。
論理的に不可能なのはワンタイムパッドの性質から言えるはず。
(ただのバイト列のXORをするだけ)
code:ruby
def xor(a, b)
a.zip(b).map{|x, y| x ^ y}
end
def random_bytes(size)
size.times.map{rand(0..255)}
end
def str(bs)
bs.pack("C*")
end
# Source text
src = "I ♥ Ruby"
# Get source byte array
bs = src.bytes
# Get length of bytes
size = bs.size
# Generate random bytes
r1 = random_bytes(size)
# XOR r1 and bytes
r2 = xor(r1, bs)
# Decrypt
d1 = xor(r1, r2)
puts str(d1)
分散数Nに拡張
上記の仕組みは2つに分散だた。これを任意の自然数Nに分散方法の具体例。
以下の手法はすべてデータが揃って復元できる秘密分散。つまり「3つのうち2つで復元」とかではない。
(厳密にはN-1とかN+1とかはここでは気にしない。)
($ \oplusはXOR)
1. 元データ$ Srcがある
2. $ Srcと同じ長さのランダム$ R1を生成する
3. $ R2 = Src \oplus R2 で$ R2を生成する。 (ここでやめれば$ R1, R2を送る)
4. $ Srcと同じ長さのランダム$ R3を生成する
5. $ R4 = R2 \oplus R3 で$ R4を生成する。(ここでやめれば$ R1, R3, R4を送る)
6. $ Srcと同じ長さのランダム$ R5を生成する
7. $ R6 = R4 \oplus R5 で$ R6を生成する。(ここでやめれば$ R1, R3, R5, R6を送る)
...
「ここでやめればOOOを送る」の数がNになるまで続ければよいはず
みたいに続けて行けば好きな数で分散できる。
記述した最後のステップやれば$ R1, R3, R5, R6を送ることになる。$ R2, R4は送らない。なぜなら$ R2とR1がある時点で$ Srcが復元できてしまうから。すべて揃わないと復元できないようにしたくてこの方法になっている。
安全性に関する保証は、ワンタイムパッドを使っていることと、$ R1, R3, R5が互いに無関係であることが挙げられる。無関係というのは、$ R1, R3, R5は任意の乱数だからである($ Srcと同じ長さの任意のランダムバイト列)。XORした結果などではない。ユーザーが自由に決めたランダムバイト列。$ R6はXOR後の結果なので多少関連ある気もするが、ランダムバイト列同士のXORだしワンタイムパッド使ってるし全然問題ないはず。
つまり、論理的に$ R1, R3, R5を手に入れても元データは絶対に復元できない(これは証明すぐできるはず)。$ R6を手に入れる必要が絶対にある。証明できないが、すべて揃わないと$ Srcの復元もできないはず(ワンタイムパッドの性質よりで証明できてるかもしれない)。
復元方法
1. $ R4 = R5 \oplus R6
2. $ R2 = R3 \oplus R4
3. $ Src = R1 \oplus R2
これで$ Srcが手にはいる。
以下のように一行で求めることもできる。
$ Src = R1 \oplus (R3 \oplus (R5 \oplus R6))
そして、XORは結合法則・交換法則がなりたつため、$ R1, R3, R5, R6の順番を気にせずに全部XORしてしまえば$ Srcになるはずである。順番情報などをつける必要がないのはメリット。
分散数Nに拡張はいくつもバリエーションがあるはず。$ R2まで生成したら、そのあと$ R1とR2のどちらを次のXORに使うか、そのあとも$ R3や$ R4を生成するXORも順番にバリエーションがあるはず。
上記のNへの拡張はリスト上になっている。「$ Src = ...」のカッコの結合順番を見てもわかると思う。これをツリー状にXORしていく方法もあると思う。どちらがセキュリティー的に強いのかもしくは変わらないのか、考えてみたい。
「3つのうち2つ」あれば復号できるとかにも対応できたら良いかも(冗長性があって)。
Nへの拡張のRubyコード:
code:ruby
def xor(a, b)
a.zip(b).map{|x, y| x ^ y}
end
def random_bytes(size)
size.times.map{rand(0..255)}
end
def str(bs)
bs.pack("C*")
end
# Source text
src = "I ♥ Ruby"
# Get source byte array
bs = src.bytes
# Get length of bytes
size = bs.size
# Generate random bytes
r1 = random_bytes(size)
# XOR r1 and bytes
r2 = xor(r1, bs)
# Generate random bytes
r3 = random_bytes(size)
# XOR
r4 = xor(r2, r3)
# Generate random bytes
r5 = random_bytes(size)
# XOR
r6 = xor(r4, r5)
# Decrypt
d = xor(r1, xor(r3, xor(r5, r6)))
puts str(d)
説明文と対応させるために、r1~r6の生成方法は、上記のようになっている。
これをループで書くとnを指定するだけで、[r1, ..., rn]みたいなバイト列の配列を返すようにすることもできると思う。