Rabin暗号

概要

RSA暗号の欠点を補うべくRabin が開発した暗号。実用目的ではなく、研究目的で作成された。安全性の証明を行った初の公開鍵暗号として知られている。

安全性の証明

RSA暗号では「暗号解読が素因数分解以上に難しい」ことを証明できていないが、Rabin暗号では証明に成功している。

欠点とその改良

Rabin暗号には、暗号文を解読した結果の平文が一意に定まらないという特徴がある。従ってこのままでは実用に耐えない。この欠点を補うべく Williams により、平文の候補を複数生成してしまう鍵を排除できるように改良されたWilliams暗号が提案された。