利用者:Meauk/暗号20221225

2022年12月25日に Meauk が作成した暗号について記されている。

暗号の構成

鍵生成 by Alice

1. 同じ桁数だが互いに異なる2つの素数 p と q をそれぞれ選択。
2. n = pq を計算。
3. p を法とする原始根として g を設定。
4. {(g^{p - 1} mod p²) - 1} / p に等しい値を仮に a と置くとき、ad ≡ 1 (mod p) となるような d を計算。
5. (n, g) の組を公開鍵に、(p, q, d) の組を秘密鍵に設定。ただし、q は直接的には不使用。
6. 公開鍵 (n, g) をボブ宛に送信。

暗号化 by Bob

1. n² 未満の正整数 r を無作為に選択。
2. p 未満の平文 m を用意し、暗号文 C ≡ g^{m + nr} (mod n²) を計算。
3. 暗号文 C をアリス宛に送信。

復号 by Alice

1. D = {(C^{p - 1} mod p²) - 1} / p を計算。
2. Dd = m (mod p) により、平文 m を入手。