暗号特集

暗号化方式の設計

安全だと言われている暗号化方式でも，
実装がまずいと脆弱になる例はいくらでもあります．

特に鍵管理は厄介なものです．

こちらの記事でも鍵管理について述べてくれています [1]．

参考文献

鴨志田昭輝：暗号化は鍵管理まで仕様に盛り込め．1分で理解するプロの知恵［セキュリティ編］．http://itpro.nikkeibp.co.jp/

ブログ記事を読む

ハイブリッド暗号その3

鍵カプセル化メカニズム（KEM）に加えて，
今度はデータカプセル化メカニズム（DEM）についてお話します．

DEMは大まかに2つのアルゴリズムからなります．

暗号化アルゴリズム：データの暗号化
復号アルゴリズム：暗号文の復号

暗号化アルゴリズム

共通鍵とラベルと平文を入力すると暗号文を生成します．
ラベルと平文はどんな長さでも構いません．
共通鍵暗号で暗号化するので，公開鍵暗号に比べれば十分に高速に動作するので問題ありません．

また，ラベルは通信毎に更新すべきです．
ワンタイム鍵のように扱う必要があります．

復号アルゴリズム

共通鍵暗号の鍵とラベルと暗号文を入力すると平文を生成します．
普通の共通鍵暗号の動作と変わりません．

また，DEMの暗号化で使った鍵とラベルと暗号文をそのまま復号アルゴリズムに通すと，
元の平文に戻るということが保障されていなければなりません．

この正当性も共通鍵暗号や公開鍵暗号単体で使った場合と変わりません．

一見名前だけで難しそうだと感じますが，
構成要素を1個ずつ見ていけばたいして難しくありません．

他の分野でもそうですね．

ブログ記事を読む

ハイブリッド暗号その2

ハイブリッド暗号について，今度は鍵カプセル化メカニズム（KEM）について説明します．

KEMは大まかには次の3つのアルゴリズムで構成されています．

鍵生成アルゴリズム
鍵カプセル化アルゴリズム
復号アルゴリズム

鍵生成アルゴリズム

初期値\( 1^k \)を入力すると，公開鍵暗号における公開鍵と秘密鍵のペア\( (pk, sk) \)を出力します．

鍵カプセル化アルゴリズム

公開鍵\( pk \)を入力すると，共通鍵暗号の鍵\( K \)とその暗号文\( C \)を生成します．

復号アルゴリズム

公開鍵\( pk \)，秘密鍵\( sk \)および暗号文\( C \)を入力すると，鍵\( K \)か復号失敗\( \bot \)のどちらかを出力します．

ブログ記事を読む

ハイブリッド暗号

公開鍵暗号は計算時間がかかる．
共通鍵暗号は鍵の配送や保管を考えなければならない．

そのお悩みを解決する手段の一つとしてハイブリッド暗号があります．

ハイブリッド暗号では公開鍵暗号を共通鍵暗号の鍵配送に使って，
共通鍵暗号をデータの暗号化に使います．

送信者は共通鍵暗号の秘密鍵を受信者の公開鍵で暗号化します．
送信したいデータを共通鍵暗号の秘密鍵で暗号化して，2つの暗号文を受信者に送ります．
受信者はそれぞれを復号すればもとのデータを復元することができます．

図で表すとこんな感じです．
送信者の共通鍵暗号の秘密鍵と受信者の公開鍵暗号の秘密鍵はもちろん厳重に保管しなければなりません．

Shoup [1]はハイブリッド暗号の基本的な構成要素として次のように定式化しました．

鍵カプセル化メカニズム（key encapsulation mechanism, KEM）：
公開鍵暗号における鍵共有
データカプセル化メカニズム（data encapsulation mechanism, DEM）：
共通鍵暗号におけるデータの秘匿

KEMとDEMそれぞれについて別の記事で説明します．

参考文献

V. Shoup: A Proposal for an ISO Standard for Public Key Encryption
フリー素材SOZONOMONO，http://sozonomono.com/

ブログ記事を読む

楕円曲線暗号

楕円曲線について日本語で説明してくれている動画を発見しましたので，
こちらに貼り付けておきます．

群構造の話は参考になると思います．

スライドはこちらでダウンロードできます．

ブログ記事を読む

有限巡回群\( (\mathbb{G}, \odot) \)の位数を\( n \)，生成元を\( g \)とします．
このとき，任意の\( a \in \mathbb{G} \)に対して \[ a = \underbrace{g \odot \dots \odot g}_x \] となる\( x \in \mathbb{Z} \)が一意に定まります．
この\( x \)を群\( \mathbb{G} \)における底\( g \)に対する\( a \)の離散対数といいます．

群\( \mathbb{G}\)および\( g, a \in \mathbb{G} \)が与えられたときに，\( a \)の離散対数を求める問題を
一般化された離散対数問題といいます．

この一般化された離散対数問題と楕円曲線暗号がどう関係があるのでしょうか？
続きは後ほど話していきましょう．

ブログ記事を読む

有限巡回群

有限群\( (\mathbb{G}, \odot) \)について考えてみましょう．

\( g \in \mathbb{G} \)に対して \[ \langle g \rangle = \{e, g, g \odot g, g \odot g \odot g, \ldots \} \] と定義する（演算を何回も適用した数の集合）と，\( (\langle g \rangle, \odot)\)も群になります．
この群を有限巡回群といいます．

\( \underbrace{g \odot \dots \odot g}_r = e \)となるような\( r \)を\( g \)の位数といいます．
演算を繰り返していったときにはじめて単位元になるような演算回数のことです．

有限巡回群\( (\langle g \rangle, \odot) \)の位数は\( g \)の位数と等しいです．
また，位数が\( \mathbb{G} \)の要素数に等しい元\( g \in \mathbb{G} \)が存在するとき，
つまり，\( g \)を\( |\mathbb{G}| \)の回数だけ演算して初めて単位元\( e \in \mathbb{G}\)になるときに，
\( \langle g \rangle = \mathbb{G} \)なので，群同士も等しくなり \[ (\langle g \rangle, \odot) = (\mathbb{G}, \odot) \] より，\( (\mathbb{G}, \odot) \)も有限巡回群です．
このような\( g \)を\( \mathbb{G} \)の生成元といいます．

足し算の結果を6で割った余りの世界（つまり，\( (\mathbb{Z}_6, +) \)）で見てみましょう．
単位元は0だということはわかるでしょう． \[ 1 \not\equiv 0 \pmod{6} \] \[ 1 + 1 \not\equiv 0 \pmod{6} \] \[ 1 + 1 + 1 \not\equiv 0 \pmod{6} \] \[ 1 + 1 + 1 + 1 \not\equiv 0 \pmod{6} \] \[ 1 + 1 + 1 + 1 + 1 \not\equiv 0 \pmod{6} \] \[ 1 + 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod{6} \] より，6回目で初めて0になる（位数が6である）ので，1は生成元です．
しかし \[ 2 \not\equiv 0 \pmod{6} \] \[ 2 + 2 \not\equiv 0 \pmod{6} \] \[ 2 + 2 + 2 \equiv 0 \pmod{6} \] より，3回目で初めて0になる（位数が3である）ので，2は生成元にはなりません．

ブログ記事を読む

一般化されたフェルマーの定理

MathJax初導入ということで，離散対数問題を \( \bmod \) 演算だけでなく，
演算を一般化して考えてみましょう．

まずは，集合と演算子の組 \( (\mathbb{G}, \odot) \) が
群になす条件について復習しましょう．
\( \TeX \) の数式が使えるからうれしい．

なぜ， \( \mathbb{G} \) なのか？

群を英語で言うとGroupで，
頭文字をとって \( \mathbb{G} \) としているからです．

全ての \( x, y \in \mathbb{G} \) に対して， \( x \odot y \in \mathbb{G} \) ．
つまり，演算結果も集合 \( \mathbb{G} \) の中に入っているということです．
全ての \( x, y \in \mathbb{G} \) に対して， \( (x \odot y) \odot z = x \odot (y \odot z) \)．
いわゆる，結合法則ですね．

ここまで満たせば半群になりますが，
群をなすというためにはさらに二つの条件が必要です．

全ての \( x \in \mathbb{G} \) に対して \( x \odot e = e \odot x = x \) となるような
\( e \in \mathbb{G} \) がただ一つ存在する．
つまり，単位元が存在するということで，演算を施しても自分自身であるということですね．
全ての \( x \in \mathbb{G} \) に対して \( x \odot y = y \odot x = e \) となるような
\( y \in \mathbb{G} \) がただ一つ存在する．
つまり，逆元が存在するということで，この \( y \) を \( y = x^{-1} \) と書きます．
足し算だったら， \( y = -x \) と書いたほうがわかりやすいでしょう．

集合 \( \mathbb{G} \) の要素数 \( |\mathbb{G}| \) を
群 \( (\mathbb{G}, \odot) \) の位数といいます．

位数が有限の群を有限群といいます．

このとき，次の定理が知られています．
これはフェルマーの定理を一般化したものです．

定理有限群 \( (\mathbb{G}, \odot) \) において，任意の \( a \in \mathbb{G} \) に対して \[ \underbrace{a \odot a \odot \dots \odot a}_{|\mathbb{G}|} = e \] である．

この定理の意味は，どんな \( a \) を \( \mathbb{G} \) の要素数の回数だけ演算すれば，
必ず単位元 \( e \) に戻ってくるということです．

では，例を見てみましょう．
5で割った余りの世界（つまり集合 \( \mathbb{Z}_5 \) ）で考えてみましょう．

\( (\mathbb{Z}_5, +) \) の単位元は0ですね（小学生でもわかるはずです）．
5回同じ数で足し算して，その答えを5で割って，余りを計算してみましょう．
\[ 0 + 0 + 0 + 0 + 0 = 0 \equiv 0 \pmod{5} \] \[ 1 + 1 + 1 + 1 + 1 = 5 \equiv 0 \pmod{5} \] \[ 2 + 2 + 2 + 2 + 2 = 10 \equiv 0 \pmod{5} \] \[ 3 + 3 + 3 + 3 + 3 = 15 \equiv 0 \pmod{5} \] \[ 4 + 4 + 4 + 4 + 4 = 20 \equiv 0 \pmod{5} \]

ちゃんと0になったので，フェルマーの定理が正しいことが確かめられました．
めでたしめでたし．

ブログ記事を読む