キーカプセル化メカニズム

暗号学において、鍵カプセル化メカニズム（KEM ）は、送信者が短い秘密鍵を生成し、盗聴や傍受の危険を冒して安全に受信者に送信できるようにする公開鍵暗号システムです。^{[1] [2] [3] [4]}

KEMは、公開鍵を知っている送信者がKEMのカプセル化アルゴリズムによって短いランダムな秘密鍵と秘密鍵のカプセル化または暗号文を同時に生成することを可能にする。公開鍵に対応する秘密鍵を知っている受信者は、KEMのカプセル化解除アルゴリズムによってカプセル化から同じランダムな秘密鍵を復元することができる。^{[1] [2] [3]}

KEM のセキュリティ目標は、盗聴したり、受信者の反応を調べるために他のカプセル化を受信者に送信したりした後でも、秘密鍵を知らない人がカプセル化された秘密鍵に関する情報を回復できないようにすることです。^{[1] [2] [3]}

公開鍵暗号化方式とKEMの違いは、公開鍵暗号化方式では送信者が可能なメッセージ空間から任意のメッセージを選択できるのに対し、KEMでは送信者のために短い秘密鍵をランダムに選択することです。^{[1] [2] [3]}

送信者はKEMによって生成されたランダムな秘密鍵を取得し、それを認証暗号の対称鍵として使用し、その暗号文をカプセル化とともに受信者に送信することができます。これにより、ハイブリッド暗号システムでKEMと対称鍵認証暗号から公開鍵暗号化方式が構成されます。^{[1] [2] [3] [5]}

RSAES-PKCS1-v1_5、RSAES-OAEP、エルガマル暗号化などのほとんどの公開鍵暗号化方式は、小さなメッセージに限定されており^{[6] [7]}、ハイブリッド暗号システムで短いランダムな秘密鍵を暗号化するためにほとんど常に使用されています。^{[8] [9] [5]} また、公開鍵暗号化方式は、ランダムな秘密鍵を選択してそれをメッセージとして暗号化することでKEMに変換できますが、安全な公開鍵暗号化方式を基礎として設計するよりも、安全なKEMを設計して分析する方が簡単です。そのため、ほとんどの現代の公開鍵暗号化方式は、KEMをベースとしており、その逆ではありません。^{[10] [5]}

KEMは3つのアルゴリズムから構成される: ^{[1] [2] [3] [11] [12]}

1. 鍵生成 は入力を取らず、公開鍵と秘密鍵のペアを返します。${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$${\displaystyle {\mathit {pk}}}$${\displaystyle {\mathit {sk}}}$
2. カプセル化 は、公開鍵を受け取り、秘密鍵をランダムに選択し、そのカプセル化とともに返します。${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$${\displaystyle {\mathit {pk}}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle c}$
3. カプセル化解除 ( )は、秘密鍵とカプセル化 ()を受け取り、カプセル化された秘密鍵を返すか、または失敗します。失敗は、 を返すことで示されることもあります(「一番下」と呼ばれます)。${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$${\displaystyle {\mathit {sk}}}$${\displaystyle c'}$${\displaystyle k'}$${\displaystyle \bot}$

KEMが正しいのは、によって生成された任意の鍵ペアについて、によって返されたカプセル化を高い確率で解除すると、同じ鍵、つまり が得られる場合です。^{[2] [3] [11] [12]}${\displaystyle ({\mathit {pk}},{\mathit {sk}})}$${\displaystyle \operatorname {Gen} }$${\displaystyle c}$${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$${\displaystyle k}$${\displaystyle \operatorname {Decap} ({\mathit {sk}},c)=k}$

KEM のセキュリティは、選択暗号文攻撃(IND-CCA) に対する判別不能性によって定量化されます。これは、ランダムなキーとカプセル化が与えられた場合に、そのキーがそのカプセル化によってカプセル化されているか、独立したランダムなキーであるかを敵対者がコイントスよりもどれだけうまく判断できるかを示します。^{[2] [3] [11] [12]}

具体的には、IND-CCA ゲームでは次のようになります。

1. キー生成アルゴリズムが実行され、 が生成されます。${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$
2. ${\displaystyle {\mathit {pk}}}$敵対者に明らかにされます。
3. 攻撃者は、攻撃者が選択した任意のカプセル化を照会できます。${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$${\displaystyle c'}$
4. カプセル化アルゴリズムが実行され、秘密鍵とカプセル化がランダムに生成され、別の秘密鍵が独立してランダムに生成されます。${\displaystyle (k_{0},c):=\operatorname {Encap} ({\mathit {pk}})}$${\displaystyle k_{1}}$
5. 公平なコインを投げて、結果を決定します。${\displaystyle b\in \{0,1\}}$
6. ペアは敵に公開されます。${\displaystyle (k_{b},c)}$
7. 敵対者は、を除いて、敵対者が選択した任意のカプセル化を再度照会できます。${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$${\displaystyle c'}$${\displaystyle c}$
8. 対戦相手は推測を返し、 であればゲームに勝ちます。${\displaystyle b'\in \{0,1\}}$${\displaystyle b=b'}$

敵対者の IND-CCA の利点は、つまり、カプセル化されたキーを独立してランダムに選択されたキーと正しく区別する、公平なコイントスを超える確率です。 ${\displaystyle \left|\Pr[b'=b]-1/2\right|}$

ビットの係数と指数を持つ従来のRSA暗号化は次のように定義されます。^{[13] [14] [15]}${\displaystyle t}$${\displaystyle e}$

• キー生成:${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$

1. を満たすビットの半素数をランダムに生成します。ここで はカーマイケル関数です。${\displaystyle t}$${\displaystyle n}$${\displaystyle 2^{t-1}n<2^{t}}$${\displaystyle \gcd(e,\lambda (n))=1}$${\displaystyle \lambda (n)}$
2. 計算します。${\displaystyle d:=e^{-1}{\bmod {\lambda }}(n)}$
3. 公開鍵と秘密鍵として返します。（鍵生成アルゴリズムと秘密鍵の形式には多くのバリエーションがあります。 ^[16]）${\displaystyle {\mathit {pk}}:=n}$${\displaystyle {\mathit {sk}}:=(n,d)}$

• ビットのメッセージを公開鍵で暗号化すると、次のようになります。${\displaystyle (t-1)}$${\displaystyle m}$${\displaystyle {\mathit {pk}}=n}$${\displaystyle c:=\operatorname {暗号化} ({\mathit {pk}},m)}$

1. ビット文字列を整数としてエンコードします。${\displaystyle m}$${\displaystyle r}$${\displaystyle 0\leq r<n}$
2. 戻る。${\displaystyle c:=r^{e}{\bmod {n}}}$

• 秘密鍵を使用して暗号文を復号すると、次のようになります。${\displaystyle c'}$${\displaystyle {\mathit {sk}}=(n,d)}$${\displaystyle m':=\operatorname {復号} ({\mathit {sk}},c')}$

1. 計算します。${\displaystyle r':=(c')^{d}{\bmod {n}}}$
2. 整数をビット文字列としてデコードします。${\displaystyle r'}$${\displaystyle m'}$

この単純なアプローチは完全に安全ではありません。たとえば、ランダム化されていないため、既知平文​​攻撃ATTACK AT DAWNに対しても安全ではありません。つまり、攻撃者はメッセージを暗号化して暗号文を比較するだけで、送信者がメッセージを送信しているのか、それともメッセージを送信しているのかを判断できますATTACK AT DUSK。

が常にランダムな秘密鍵、例えば256ビットのAES鍵であるとしても、効率を最適化するために が選択されると、実数の3乗根を取るだけで暗号文からメッセージを計算することができ、プレーンRSA に対する攻撃は他にも数多く存在します。^{[13] [14]} さまざまなランダムパディング方式が考案され、 RSAES-PKCS1-v1_5 ^{[13] [17] [18]}のように、任意の短いメッセージ を安全にするための試みとして、時には失敗しました。^{[13] [14]}${\displaystyle m}$${\displaystyle e}$${\displaystyle e=3}$${\displaystyle m}$${\displaystyle c}$${\displaystyle m}$

メッセージはほとんどの場合、任意のビット文字列メッセージを暗号化するために使用される対称鍵認証暗号の短い秘密鍵であるため、 RSA-KEMと呼ばれるより単純なアプローチでは、ランダムに の要素を選択し、それを使用して鍵導出関数 を使って秘密鍵を導出します。おおよそ次のようになります。^{[19] [8]}${\displaystyle m}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle H}$

• キー生成: 上記の通り。
• 公開鍵のカプセル化は次のようになります:${\displaystyle {\mathit {pk}}=n}$${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$

1. 均一にランダムに整数を選択します。${\displaystyle r}$${\displaystyle 0\leq r<n}$
2. 戻り、カプセル化として。${\displaystyle k:=H(r)}$${\displaystyle c:=r^{e}{\bmod {n}}}$

• 秘密鍵を使用してカプセル化を解除すると、次のようになります。${\displaystyle c'}$${\displaystyle {\mathit {sk}}=(n,d)}$${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$

1. 計算します。${\displaystyle r':=(c')^{d}{\bmod {n}}}$
2. 戻る。${\displaystyle k':=H(r')}$

このアプローチは実装が簡単で、RSAES-OAEPのようなパディング方式よりもRSA問題に対するより厳密な削減を提供します。^[19]

伝統的なエルガマル暗号は、有限体の乗法部分群上で次のように定義される。^{[20] [21]}${\displaystyle \mathbb {Z} /p\mathbb {Z} }$${\displaystyle g}$${\displaystyle q}$

• キー生成:${\displaystyle (pk,sk):=\operatorname {Gen} ()}$

1. 均一にランダムに選択します。${\displaystyle x\in \mathbb {Z} /q\mathbb {Z} }$
2. 計算します。${\displaystyle y:=g^{x}{\bmod {p}}}$
3. 秘密鍵と公開鍵として返します。${\displaystyle {\mathit {sk}}:=x}$${\displaystyle {\mathit {pk}}:=y}$

• メッセージを公開鍵で暗号化すると、次のようになります:${\displaystyle m\in \mathbb {Z} /p\mathbb {Z} }$${\displaystyle {\mathit {pk}}=y}$${\displaystyle c:=\operatorname {暗号化} ({\mathit {pk}},m)}$

1. 均一にランダムに選択します。${\displaystyle r\in \mathbb {Z} /q\mathbb {Z} }$
2. コンピューティング:$${\displaystyle {\begin{aligned}t&:=y^{r}{\bmod {p}}\\c_{1}&:=g^{r}{\bmod {p}}\\c_{2}&:=(t\cdot m){\bmod {p}}\end{aligned}}}$$
3. 暗号文を返します。${\displaystyle c:=(c_{1},c_{2})}$

• 秘密鍵による暗号文の復号化は次のようになる:${\displaystyle c'=(c'_{1},c'_{2})}$${\displaystyle {\mathit {sk}}=x}$${\displaystyle m':=\operatorname {復号} ({\mathit {sk}},c')}$

1. またはの場合、つまりまたは がによって生成されたサブグループ内にない場合は、失敗して を返します。${\displaystyle \bot}$${\displaystyle (c'_{1})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$${\displaystyle (c'_{2})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$${\displaystyle c'_{1}}$${\displaystyle c'_{2}}$${\displaystyle g}$
2. 計算します。${\displaystyle t':=(c'_{1})^{x}{\bmod {p}}}$
3. 戻る。${\displaystyle m':=t^{-1}c'_{2}{\bmod {p}}}$

これは、空間内のメッセージに制限された公開鍵暗号化方式の構文を満たしています（ の一般的な値では、数百バイトのメッセージに制限されます）。復号化時に暗号文を検証することにより、によって生成されたグループの外側で悪意を持って選択された暗号文を通じて秘密鍵のビットが漏洩することを回避します。 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$${\displaystyle p}$${\displaystyle x}$${\displaystyle g}$

しかし、これは選択暗号文攻撃に対する区別不能性を達成できない。例えば、未知のメッセージの暗号文を持っている攻撃者は、復号化オラクルに別の暗号文を問い合わせることで簡単にそれを復号化でき、関連する平文が得られ、それを復号化することで復元できる。^[20]${\displaystyle c=(c_{1},c_{2})}$${\displaystyle m}$${\displaystyle c':=(c_{1},c_{2}g)}$${\displaystyle m':=mg{\bmod {p}}}$${\displaystyle m}$${\displaystyle m=m'g^{-1}{\bmod {p}}}$

伝統的なエルガマル暗号は楕円曲線の設定に適応できるが、曲線上の点としてメッセージを可逆的にエンコードする何らかの方法が必要であり、これはメッセージを mod の整数としてエンコードするよりも簡単ではない。^[22]${\displaystyle p}$

メッセージはほとんどの場合、任意のビット列メッセージを暗号化するために使用される対称鍵認証暗号の短い秘密鍵であるため、より簡単な方法は、KEMとして鍵導出関数を使用して秘密鍵を導出し、完全に省略することです。^[1]${\displaystyle m}$ ${\displaystyle t}$${\displaystyle m}$${\displaystyle c_{2}}$ ${\displaystyle H}$

• キー生成: 上記の通り。
• 公開鍵のカプセル化は次のようになります:${\displaystyle {\mathit {pk}}=y}$${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$

1. 均一にランダムに選択します。${\displaystyle r\in \mathbb {Z} /q\mathbb {Z} }$
2. 計算します。${\displaystyle t:=y^{r}{\bmod {p}}}$
3. 戻り、カプセル化として。${\displaystyle k:=H(t)}$${\displaystyle c:=g^{r}{\bmod {p}}}$

• 秘密鍵を使用してカプセル化を解除すると、次のようになります。${\displaystyle c'}$${\displaystyle {\mathit {sk}}=x}$${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$

1. 、つまり が によって生成されたサブグループ内にない場合は失敗して を返します。${\displaystyle \bot }$${\displaystyle (c')^{(p-1)/q}\not \equiv 1{\pmod {p}}}$${\displaystyle c'}$${\displaystyle g}$
2. 計算します。${\displaystyle t':=(c')^{x}{\bmod {p}}}$
3. 戻る。${\displaystyle k':=H(t')}$

任意のビット文字列メッセージを暗号化するための認証暗号と組み合わせると、その組み合わせは本質的に統合暗号化方式になります。この KEM では、この場合、定義されているグループのランダム要素をハッシュするための一方向の鍵導出関数のみが必要であり、メッセージの可逆エンコードは必要ないため、 ECIES (楕円曲線統合暗号化方式)のように、同じセキュリティでよりコンパクトで効率的な楕円曲線グループに拡張するのは簡単です。 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

• キーラップ
• 最適な非対称暗号化パディング
• ハイブリッド暗号システム