伝書鳩用暗号化プロトコル(草案)
概要
コンピュータなしで使えそうな、
2点間の通信で鍵交換を含めて伝書鳩で行うための
そこそこ強度のありそうな暗号化手段ってどんなものか考えてみた
手順
要約すると、DH鍵交換した共有数と暗号表を組み合わせた方法となる。
XOR方陣について
暗号化の時に利用するxor演算を簡単にするため
事前に方陣を用意しておく、
縦軸の文字と横軸の文字からxorの結果を求められる便利な方陣だ。
他にも何かにつかえるはず?
xor計算は以下のような特性がある
a^b=c の時以下の式が全て成り立つ b^a=c a^c=b c^a=b b^c=a c^b=a
注意点として文字数が 2^n 個にする事が必要
#XOR方陣スクリプト chars="abcdefghijklmnopqrstuvwxyz012345" chars_len = len(chars) for x in range(chars_len): for y in range(chars_len): idx = (x ^ y) print "%s\t" % chars[idx], print
このスクリプトでは以下のような出力が得られる。
abcdefghijklmnopqrstuvwxyz012345 badcfehgjilknmporqtsvuxwzy103254 cdabghefklijopmnstqrwxuv01yz4523 dcbahgfelkjiponmtsrqxwvu10zy5432 efghabcdmnopijkluvwxqrst2345yz01 fehgbadcnmpojilkvuxwrats3254zy10 ghefcdabopmnklijwxuvstqr452301yz hgfedcbaponmlkjixwvutsrq543210zy ijklmnopabcdefghyz012345qrstuvwx jilknmpobadcfehgzy103254rqtsvuxw klijopmncdabghef01yz4523stqrwxuv lkjiponmdcbahgfe10zy5432tsrqxwvu mnopijklefghabcd2345yz01uvwxqrst nmpojilkfehgbadc3254zy10vuxwrqts opmnklijghefcdab452301yzwxuvstqr ponmlkjihgfedcba543210zyxwvutsrq qrstuvwxyz012345abcdefghijklmnop rqtsvuxwzy103254badcfehgjilknmpo stqrwxuv01yz4523cdabghefklijopmn tsrqxwvu10zy5432dcbahgfelkjiponm uvwxqrst2345yz01efghabcdmnopijkl vuxwrqts3254zy10fehgbadcnmpojilk wxuvstqr452301yzghefcdabopmnklij xwvutsrq543210zyhgfedcbaponmlkji yz012345qrstuvwxijklmnopabcdefgh zy103254rqtsvuxwjilknmpobadcfehg 01yz4523stqrwxuvklijopmncdabghef 10zy5432tsrqxwvulkjiponmdcbahgfe 2345yz01uvwxqrstmnopijklefghabcd 3254zy10vuxwrqtsnmpojilkfehgbadc 452301yzwxuvstqropmnklijghefcdab 543210zyxwvutsrqponmlkjihgfedcba
それと、これはただの方陣なので、
秘匿する必要はまったくない。
鍵伸長方陣について
共有数から共有鍵を作成するためのテーブルを用意する。
文字をランダムに入れ替えただけの方陣で、
本番ではトランプをシャッフルするような形で作成する。
import random chars="abcdefghijklmnopqrstuvwxyz012345" chars_len = len(chars) rowcount = 17 for x in range(rowcount): myrow = list(chars) random.shuffle(myrow) for y in range(chars_len): print "%s\t" % myrow[y], print
出力は以下のような形になる。
#乱数を利用するため出力は毎回異なる
fxygu5mdv2hjne0bslp43owtiz1qackr lzph4wxsn2kbiye3vdagj05qrftu1ocm mghbcl1en0x2ys4qjpkiftrwouv3zd5a s0odu3ye2rhc1gpxtj5bwivnzmafqkl4 jyvm4shlfak0guqx5tcr23wzb1iendpo 3tpymfdwo42xuehvgiqnj5zkr0slab1c quhzty0cwl4km5p3ajeio1dfbnvs2gxr a3psylxjonw4v0izmebug25rht1kfcqd ludxo4rpifsgvkmtwy1a5hc32j0beznq yzspgntmhqrfx1a3ouil0edb5k42jcvw vu0sjxrbwqinpgktmc153hdaf4olyze2 ez43mdj1yqtwl0igcksrxhv2ufaonp5b earubq3l2gdjmx0tsnychv4wpof1kz5i hui0zeb53rsqvtg1ajmpxdkln2cyfow4 ut15n3gwmyhrosqcxeak0fvjz24dipbl oa5xde0qfjsrlgp4bmwh1c32ykutnvzi pomg0lr4xkaiw1hn2e5sbycdvjfqzu3t
これも、ただの乱数テーブルなので秘匿の必要はあまりない?
漏れてもそこまで深刻ではないはず
DH鍵交換について
今回の暗号化方式の要。
通信内容がすべて傍受されていても、
2者が秘密の共有数を持てる
現代でも利用されているDH鍵交換について。
http://d.hatena.ne.jp/rikunora/20120514/p1
http://www.techscore.com/tech/Java/JavaSE/JCE/11/
鍵交換の手順
1. aとbはそれぞれ公開の数 G P と 秘密の数 A B を決める
2.Aを直接送る代わりに「G^A mod P」を送る
Bを直接送る代わりに「G^B mod P」を送る
3.aは (G^B mod P)^A mod P を計算
bは (G^A mod P)^B mod P を計算
4. お互いの手元に同じ数が共有される
暗号鍵の生成について
共有数 と 文字数 の剰余算と除算を行い
共有数から数列を取得する。
例: 共有数が 1234 の場合 1回目 1234 / 32 = 38 あまり 18 2回目 38 / 32 = 1 あまり 6 3回目 1 / 32 = 0 あまり 1 このように{18,6,1}の数列を作成
この数列と鍵伸長方陣を利用して暗号鍵を作る
0番目から数える事がポイントになる。
1行目の18番目は"p" 2行目の6番目は"x" 3行目の1番目は"g"
以上で p x g の暗号鍵が得られた。
暗号文の生成
XOR方陣を利用し共通鍵と平文からCBC方式で暗号文を生成する。
以下に擬似コードを書く
C[] //暗号文 M[] //平文 K[] //鍵 L //鍵長 暗号化 C[i] = M[i] ^ C[i-1] ^ K[i % L] 復号化 M[i] = C[i] ^ K[i % L] ^ C[i-1]
例として"hellworld"を暗号化してみる。
鍵は先程の"pxg"を利用する
#暗号化 h ^ p = i e ^ x ^ i = t ^ i = 1 l ^ g ^ 1 = n ^ 1 = w l ^ p ^ x = e ^ w = s w ^ x ^ t = b ^ s = t o ^ g ^ s = i ^ t = 1 r ^ p ^ 0 = 4 ^ 1 = f l ^ x ^ e = 2 ^ f = z d ^ g ^ y = f ^ z = 2
暗号文は "i1wst1fz2" になった。
復号化も行なってみる
i ^ p = h 1 ^ x ^ i = m ^ i = e w ^ g ^ 1 = q ^ 1 = l s ^ p ^ w = 3 ^ w = l t ^ x ^ s = e ^ s = w 1 ^ g ^ t = 3 ^ t = o f ^ p ^ 1 = k ^ 1 = r z ^ x ^ f = o ^ f = l 2 ^ g ^ z = 0 ^ z = d
無事に復号化もできた