MHナップザック暗号

1978 年に Merkle と Hellman が発明した 部分和問題の難しさを利用した公開鍵暗号です。

【鍵生成】

Bob は 超増加数列 (s₁, s₂, ..., s_n) を生成し，この数列全ての和よりも大きい法 P と、

P と互いに素な秘密の整数 w を用いて、数列 (a₁, a₂, ..., a_n) に変換し、この数列を公開する。

【暗号化】

Alice は Bob の 暗号化鍵 (s₁, s₂, ..., s_n) を入手する。

Alice は nビットの平文 (m₁, m₂, ..., m_n) を次式により暗号文 C に暗号化する。

C = a₁m₁ + a₂m₂ + ... + a_nm_n

【復号】

Bob は 暗号文 C を w^-1 倍して P で割った余りを中間平文 M とし、

超増加数列の性質を利用して大きい方(s_n )から順に引けるか否かを判定し、

平文 (m₁, m₂, ..., m_n) を復号する。

M = w^-1 C mod P, M → (m₁, m₂, ..., m_n)