Category: cryptography

確率的アルゴリズムと暗号化モード(ECBとCBC)

確率的アルゴリズムは安全な暗号文を作るために必要
暗号を繰り返し使って安全であるためには、同じ平文を暗号化して毎回異なる暗号文にならないといけない
EBCモードで暗号化すると、16バイトずつ暗号化しているので同じパターンが現れると同じ暗号データになってしまう
-> CBCモードでの暗号化が開発された
-> 同じ値を出力するのを決定的アルゴリズムという。一方、毎回異なる出力をするアルゴリズムを確率的アルゴリズム(CBCモード)という

### ECB(Electronic CodeBook)モード
平文をブロックに分割し、それぞれを暗号化して暗号文を作る方式

### CBC(Cipher Block Chaining)モード
CBCモードは平文をそのまま暗号化するのではなく、一つ前の暗号文ブロックと排他的論理和をとってから暗号化する
先頭の平文ブロックには一つ前の暗号文が無いので初期化ベクトルを用いる

### CTR(CounTeR)モード
ブロック暗号を使って擬似乱数を生成し、ストリーム暗号として利用するモード

CBCモードは大きな平文があった時にそれを分割して複数CPUを使って暗号化を並列処理することはできない
CTRモードは各暗号文が独立なので複数CPUを使って並列処理できる

CBCモードは以前はよく使われていたが最近は避けられる傾向にある
サーバは暗号に関するエラー情報を不用意に返さないようにする

PHP Extension ChaCha20 Encryption

include("chilkat_9_5_0.php");

$crypt = new CkCrypt2();

$crypt->put_CryptAlgorithm('chacha20');
$crypt->put_KeyLength(256);

$crypt->put_EncodingMode('hex');

$ivHex = '000000000000000000000002';
$crypt->SetEncodedIV($ivHex, 'hex');

$crypt->put_InitialCount(42);
$keyHex = '1c9240a5eb55d38af333888604f6b5f0473917c1402b80099dca5cbc207075c0';
$crypt->SetEncodedKey($keyHex, 'hex');

$plainText = ''Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.'';

$encStr = $crypt->ecnryptStringENC($plainText);
print $encStr . "\n";

$decStr = $crypt->decryptStringENC($encStr);
print $decStr . "\n";

PHPのワンタイムパッド

// 暗号化したい文字列
$str = "保つのに時があり，捨てるのに時がある。";

// ワンタイムパッド
$pad = [
  12,20,148,22,87,91,239,187,206,215,103,207,192,46,75,243,
  204,61,121,210,145,167,108,78,166,129,109,239,138,134,150,196,
  217,63,158,201,204,66,181,198,54,0,0,130,163,212,57,167,
  169,115,170,50,109,116,173,177,252,242,233,3,33,28,139,73,
];

function convert($str, $pad){
	$res = "";
	for($i=0; $i<strlen($str); $i++) {
		$c = ord(substr($str, $i, 1));
		$cx = $c ^ $pad[$i];

		$res .= chr($cx);
	}
	return $res;
}

$enc = convert($str, $pad);
echo "暗号化した文字列:{$enc}\n";

$dec = convert($enc, $pad);
echo "復号化した文字列:{$dec}\n";

PHPで共通鍵暗号を使った暗号化・復号化

$data = 'あいうえおかきくけこさしすせそ';

$ciphers = openssl_get_cipher_methods();
print_r($ciphers);

$method = 'AES-256-CBC';

$iv_length = openssl_cipher_iv_length($method);
$iv = openssl_random_pseudo_bytes($iv_length);

$option = 0;

$encrypted = openssl_encrypt($data, $method, $password, $options, $iv);
echo "暗号文": .$encrypted . "\n";

$decrypted = openssl_decrypt($ecnrypted, $method, $password, $options, $iv);
echo "平文" . $decrypted . "\n";

ストリーム暗号

ストリーム暗号は擬似乱数生成器を使うことでワンタイムパッドの問題を解決した共通鍵暗号
事前に共有すべき秘密鍵はシードだけで済む。そのような共通鍵暗号をストリーム暗号という
ただし、擬似乱数生成器では生成できない値が存在する
計算量的安全性を持つ
1987年にRC4が設計されたが平文解読攻撃が提案された。2008年にバーンスタインがChaCha20と呼ばれるストリーム暗号を開発
Intel CPUやARMの一部CPUでAES専用のハードウェア支援機構があり高速に処理されるがモバイルや組み込み環境ではChaCha20のほうがAESより高速
秘密鍵と一緒にnonceと呼ばれる値を擬似ランダム関数に入力することで繰り返し利用できる

ChaCha20
ChaCha20は256ビットの秘密鍵と96ビットのナンスを元に512ビットずつの擬似乱数を生成する
　　生成した乱数と平文の排他的論理和をとって暗号文にするストリーム暗号
　　k, n, b, c(初期定数) 8×10回繰り返す

ワンタイムパッド

共通鍵暗号の一つであるワンタイムパッドは情報が絶対もれないという意味でも最も安全な暗号
OTP(One-Time Pad)とはnビットの平文mを暗号化するためにnビットの秘密鍵sを使う暗号方式。秘密鍵は1度しか使ってはいけないのでワンタイム
平文mと秘密鍵sの各ビットごとに排他的論理和+をとって暗号文を作る
平文mを秘密鍵sで暗号化することをEnc(s, m)と書く
暗号文cを秘密鍵sで複合することをDec(s, c)と書く

ワンタイムパッドは秘密鍵に真の乱数を使うと絶対に破られない暗号(情報理論的安全性がある)
　L 暗号文を作るたびに毎回新しく乱数で秘密鍵を用意して相手と共有しなければならない
　L しかも秘密鍵は暗号文と同じサイズでなければならない

暗号における乱数

予想不可能性、再現不可能性が大事
Linuxの/dev/randomはCPUのハードウェアだけでなく様々な情報を組み合わせて、仮にどれか一つに問題があったとしても最終出力には影響が出ないように設計されている(ストリーム暗号(sec.12)を用いた疑似乱数生成器)
疑似乱数…他人が推測できてはいけない
疑似ランダム関数(PseudoRandom Function)は、シードsを与えたときに任意の値に対して疑似乱数を生成する関する
L HAMCを繰り返して適用して実装する方法がある

共通鍵暗号と排他的論理和

暗号化する時と複合するときに同じ鍵を使う。秘密鍵暗号、対称鍵暗号ともいう。
s(secret), m(message), c(ciphertext)
c = Enc(s, m)
c = Enc(m)
m = Dec(c)

Chosen Plaintext Attack, Choosen Ciphertext Attackなどがあります

### 共通鍵暗号の種類
ブロック暗号とストリーム暗号に分類される
– ブロック暗号: 一定のブロックごとに平文をかき混ぜて暗号化
– ストリーム暗号: ノイズ(乱数)を生成し、それと平文を混ぜ合わせて暗号化

### ビットと排他的論理和
真理値表に従い恒等変換という
論理積: 両方の入力が1の時のみ1
論理和: どちらか一方が1なら1
排他的論理和: aとbどちらか片方が1の時1、それ以外が0
交換法則: aとbを交換しても同じ値になる
結合法則: 3この1ビットa, b, cがあったときに、どちらから先に計算しても同じになる

排他的論理和で考えると、aを平文、bを鍵とすると a^bは暗号文、(a^b)^b = a が暗号文を復号して元の平文aを取り出す操作

アルゴリズムと安全性

アルゴリズムの性能を分類するのはO記法を使用する
O記法はパラメータnに関する関数f(n)のnが大きくなった時の振る舞いを表現
f(n)のオーダーはO(n^d)
入力パラメータによる計算式に応じて、定数時間アルゴリズム、線形時間アルゴリズム、多項式アルゴリズムという
e.g. y=2^x, y=x^2, y=x, y=log(x)
メモリの消費量もO(n), O(n log(n))など色々なものがある
ビットと表現可能な範囲

### セキュリティパラメータ
暗号を破るのに必要な計算コスト
暗号技術の危殆化とは、計算機の性能向上や暗号解読・攻撃手法の進展に伴って暗号の安全性が低下すること

現在安全とされる128ビットセキュリティ
– 共通鍵暗号:128
– ハッシュ関数: 256
– RSA暗号: 約3000
– 楕円曲線暗号: 256 (2024ビットRSAより安全と考えられている)

古典暗号

1970年代後半からを現代暗号とした場合、それ以前の暗号を古典暗号という

### シフト暗号
数字を決めておき、その数だけ文字をずらして暗号文を作成する
シーザー暗号とも言われる

function str_rot($s, $n = 13) {

	static $letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
	$n = (int)$n % 26;
	if(!$n) return $s;
	if($n == 13) return str_rot13($s);
	for($i = 0, $l = strlen($s); $i < $l; $i++){
		$c = $s[$i];
		if($c >= 'a' && $c <= 'z'){
			$s[$i] = $letters[(ord($c) - 71 + $n)% 26];
		} else if($c >= 'A' && $c <= 'Z'){
			$s[$i] = $letters[(ord($c) - 39 + $n)%26 + 26];
		}
	}
	return $s;
}

### 換字式暗号
換字表を作り、それに従って暗号化する
-> e, a, tの順番に出現頻度が高い。文字の偏りが出てしまう。

### 符号化
文章やデータをコンピュータで扱える形にすることを符号化という。
最もポピュラーなのは、アルファベットや数字、多少の記号だけに限定したASCIIと呼ばれる文字コード。ASCIIコードは16進数で表記することが多い。
上位(2~7)、下位(0~9a~f)の16進数でアルファベットを表現する
上位０、１に対応するのは特殊文字
helloは「68 65 6c 6c 6f」と表現できる