現代暗号史_公開鍵暗号

現代暗号史_公開鍵暗号

素因数分解/RSA

RSA暗号

Rabin暗号

鍵生成
暗号

c=m^2 mod n

復号

cの平方剰余を取る

安全性

素因数分解が困難ならばOW-CPA

補足

復号の際に4通りの平方剰余が得られる. 平文空間をQR_nに限定すると一意性が保証される.

Blum-Goldwasser暗号

鍵生成
  • 秘密鍵:(d,p,q) (ただし, p, qは8k+7の形)
  • 公開鍵:(n,e)
暗号

m \in \{0,1\}^l暗号化する

  1. z \in \mathbb{Z}_nをランダムに選ぶ
  2. x_0 = z^2 \bmod{n}とする.
  3. x_i = x_{i-1}^2 \bmod{n}とする.
  4. s=(lsb(x_0),lsb(x_1),...,lsb(x_{l-1}))とする.
  5. c_1=s\oplus mとする.

暗号文はc=(c_1,x_l).

復号

安全性

素因数分解が困難ならばIND-CPA (多分)

補足

Blum-Blum-Shubで疑似乱数生成をしている.

Goldwasser-Micali暗号

鍵生成
暗号
復号

Paillier暗号

補足

加法的準同型性を持つ点が重要.

Cramer-Shoup暗号 (の一部)