💨

RSA-OAEP暗号

2021/11/30に公開

メモ

暗号

tech

公開鍵暗号の安全性評価

公開鍵暗号の安全性は、攻撃者がどのような条件で攻撃をするのか（攻撃モデル）、その攻撃によってどのような安全性を保証するのか（安全性）の２つの条件を定義して議論される。主に攻撃モデルは3種類、安全性の種類は4種類に分類される。

攻撃モデルの種類

選択平文攻撃(CPA: Chosen Plaintext Attack)
攻撃者が任意の平文を選び、それに対応する暗号文を得られる。（公開鍵暗号では常に可能な攻撃）
選択暗号文攻撃（CCA1: Chosen Ciphertext Attack 1)
攻撃者が解読したい暗号文を入手する前にあらかじめ任意の暗号文に対する平文を入手できる。
適応的選択暗号文攻撃（CCA2: Chosen Ciphertext Attack 2)
攻撃者はあらかじめ任意の暗号文に対する平文を入手し、解読したい暗号文を入手した後でも（その暗号文を除いて）任意の暗号文に対する平文を入手できる。

下にいくほど敵の攻撃能力が高くなる。脅威が大きい。

安全性の定義

一方向性（OW: One-Wayness)
暗号文から平文を求めることができない。
強秘匿性(SS: Semantically Secure)
暗号文から平文に関して1bitの情報も分からない。
識別不可能性（IND: Indistinguishability)
暗号文が平文 $M_1$ 、 $M_2$ どちらのものか識別できない。
頑強性NM: Non-Malleability)
暗号文から別の暗号文を生成することができない。

下にいくほど条件が厳しくなる。安全性が高い。

公開鍵暗号の安全性評価の方法

公開鍵暗号の安全性評価は、上記の3種類の攻撃モデルと4種類の安全性の組み合わせた12種類の基準に分類される。その中で最も厳しい条件は、NM-CCA2となる。NMの条件を理論的に扱うのは難しいが、CCA2においてINDとNMは等価であることがわかっている。したがって、IND-CCA2はNM-CCA2と同様、最も厳密な基準である。RSA暗号では、IND-CCA2化したRSA-OAEP方式が提案され使われている。

RSA-OAEP暗号の暗号化

1.メッセージ $m$ を特定のデータ長になるようにゼロパディングをして $(m\;|\;0)$ にする。

2.乱数 $r$ を生成して、ハッシュ関数 $G(x)$ を使って、 $G(r)$ を生成する。

3.ゼロパディングした $(m\;|\;0)$ と $G(r)$ のXOR演算（排他的論理和）を行い $z$ を生成する。
$(m\;|\;0)\;\; \oplus\;\;G(r)=z$

4.ハッシュ関数 $F(x)$ を使って、 $F(z)$ を生成する。

5. $F(z)$ と $r$ のXOR演算を行い $v$ を生成する。
$F(z)\;\; \oplus\;\;r=v$

6. $z$ に $v$ を付け足したものを暗号化することで、暗号文 $c$ を得る。
$c=(z\;|\;v)^e\;mod\;N$

RSA-OAEP暗号の復号

1.暗号文 $c$ を復号化して $z$ と $v$ を得る。
$(z\;|\;v)=c^d\;mod\;N$

2.ハッシュ関数 $F(x)$ を使って $F(z)$ を生成して、 $F(z)$ と $v\;(v=F(z)\;\;xor\;\;r)$ のXOR演算を行うと乱数 $r$ を得ることができる。
$F(z)\;\; \oplus\;\;v=r$

3.ハッシュ関数 $G(x)$ を使って $G(r)$ を生成して、 $z\;(z=m\;\; \oplus\;\;G(r))$ と $G(r)$ のXOR演算を行うことで、 $(m\;|\;0)$ を手に入れ、メッセージ $m$ を得ることができる。
$z\;\; \oplus\;\;G(r)=(m\;|\;0)$

参考文献URL

Optimal Asymmetric Encryption Padding - Wikipedia
RSAに対する適応的選択暗号文攻撃とパディング方式
 猫にはわかる暗号技術 1
Pythonで暗号：IND-CCA2とRSA-OAEP
安全性を証明するために知っておくべき４つのこと