/cubing_cipher

cubing暗号アルゴリズム

Primary LanguageRustMIT LicenseMIT

github pages

cubing 暗号

この暗号化アルゴリズムはセキュリティ・キャンプ全国大会 2019 暗号化通信ゼミにて開発されました.

cubing 暗号の暗号化/復号アルゴリズム

執筆中

cubing 暗号の暗号化利用モード

概要

  • 平文ブロック長:45 文字
  • 暗号文ブロック長:54 文字
  • 鍵長:可変
  • 暗号化処理の並列化:部分的に可 (※但し,Shuffle がボトルネックとなる)
  • 復号処理の並列化:部分的に可 (※但し,Sort がボトルネックとなる)
  • Random Read:不可

暗号化-復号の図

CubingModeImage

各ブロックの内容

cubing_block

流れ

暗号化

  1. 平文をブロックに分ける
  2. 必要があればパディングを用意する
  3. 全ての平文に対してマスク処理 1 を行う
  4. 全てのブロックに対し,エンコードを行う
  5. 全てのブロックのハッシュに対してマスク処理 2 を行う
  6. ブロックごとに暗号化を行う
  7. ブロックをシャッフルする (下記「shuffle」参照)

復号

  1. 暗号文をブロックに分ける
  2. 全てのブロックに対して復号を行う
  3. 暗号化の(5)で使用したマスク処理を元に戻す
  4. (3)により現れるシーケンス番号を元に,ブロック間ソートを行う
  5. 暗号化の(3)で使用したマスク処理を元に戻す
  6. 全てのブロックに対し,デコードを行う
  7. 全てのブロックを結合させ,平文を生成する

パディング

平文ブロックが 45 文字 に満たない場合,1 文字 分 null 入れ,残りはランダムな英数列を入れる.

98 進数の説明

下記の文字集合を用いて表現できる数であり,この集合を表示可能文字と呼ぶ.表示可能文字は下記の順に順序を持っている.エスケープシーケンスに関しては ASCII コード参照.

{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '!', '"', '#', '$', '%', '&', ''', '(', ')', '*', '+', ',', '-', '.', '/', ':', ';', '<', '=', '>', '?', '@', '[', '\', ']', '^', '_', '`', '{', '|', '}', '~', ' ', '\n', '\0', '\t'}

エンコード

本節では以下の記号を用いる.

$n$:現在操作しているブロックの番号(0,1,2,...) $C_i$:ブロックの$i$ 文字目の文字 $\mathrm{toas}(C)$:特定の文字$C$の ASCII コードにおける番号 $\mathrm{fras}(N)$:特定の数字$N$の ASCII コードにおける文字 $\mathrm{rand}()$:アルファベット又は数字から 1 文字を一様に選ぶ関数 $\mathrm{to62}(x)$:$[0, 98)$ の自然数 x を 98 進数に従って文字に変換する関数

この時,

$$\begin{aligned} C_{45+i} &= \mathrm{fras}\left(\left(\left(\sum_{j=9(i-1)+1}^{9i}{\mathrm{toas}(C_j)}\right)\bmod 26\right)+\mathrm{toas}\left(\mathrm{A}\right)\right)\\\ C_{51} &= \mathrm{to62}\left (\left \lfloor\frac{n}{98}\right \rfloor \right)\\\ C_{52} &= \mathrm{to62}\left ( n \bmod 98 \right)\\\ C_{53} &= \mathrm{rand}()\\\ C_{54} &= \mathrm{rand}()\\\ \end{aligned}$$

とする.ただし,$i=1,2,3,4,5$ とする.これを全てのブロックに対して行う.

デコード

上記「エンコード」で付与した値を削除する.また,ハッシュが一致しているかチェックする.これにより改ざんやビット反転を検知することができる.

mask(1)

mask(1)では各ブロックの平文の先頭 45 文字にマスク処理を行う.まず,以下を定義する.

平文の$i$文字目:$Pi$ > $i$番目のマスク:$Mi$ 表示可能文字内の文字$Pi$のインデックス:$\mathrm{Idx}(Pi)$

とすると,

$$Pi=\mathrm{printable\_table}[(\mathrm{Idx}(Pi)+Mi) \bmod 98]\\$$

とする.

mask(2)

mask(2)ではハッシュとシーケンス番号にマスクをかける.計算方法は上記「mask(1)」と同様.

encrypt

暗号化処理

decrypt

復号処理

shuffle

暗号化後に全ブロックをシャッフルする.Fisher–Yates のアルゴリズムを用いることによって高速に実現可能となる.

sort

各ブロックの 51,52 番目を 98 進数として扱い,この値が昇順になるようにブロックごとにソートする.

送信内容

  1. 暗号文 ( $N$ ブロック)
  2. mask(1) ( $N*45$ 文字)
  3. mask(2) ( $N*5$ 文字)

リプレイ攻撃対策

上記shuffleを行うことによって,どのブロックがもともとどこに在ったのか,という情報が隠蔽され,ブロックのすり替えができなくなる.

ブロックが$98^2$より多くある時の処理

$62^2$個のブロックを1つの大きなブロックとして考え,各大きなブロックを ECB モードで暗号化する. 上記「shuffle」では,$98^2$個の大きなブロックごとにシャッフルする.