利用者:Meauk/暗号20221225

2022年12月25日に Meauk が作成した公開鍵暗号方式について記されている。なお、2022年12月26日現在、その正式名称はまだ存在しない。

暗号の構成

鍵生成 by 受信者

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 送信者

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

復号 by 受信者

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

成立の証拠

値 d の正体

a が {(g^{p - 1} mod p²) - 1} / p に等しいということは、g^{p - 1} mod p² が ap + 1 に等しいことを意味する。これには次の2点が関わる。

1. g と p が互いに素（最大公約数が1）である時、フェルマーの小定理によれば g^{p - 1} ≡ 1 (mod p) が成立するということ。
2. 任意の非負整数 N₁ を考える時、N₁ mod p² において p² を含む全ての項は 0 になるので、その結果は「p¹ の項」よりも大きいことはないということ。

したがって、a とは「g^{p - 1} を p² で割った時の p¹ の項の係数」であると述べることができる。

その上で、d が ad ≡ 1 (mod p) によって求められるというので、この d は「法 p における a の逆元」に相当することになる。

値 D の正体

初めに C^{p - 1} mod p² について考える。

そもそも暗号文は C ≡ g^{m + nr} (mod n²) によって求められるが、これは言い換えると C ≡ g^m × g^pqr (mod p²q²) である。

この時、次の3点に注意する。

1. 任意の非負整数 N₂ を用いて (N₂ mod p²q²) mod p² を計算することを考える時、それは初めから N₂ mod p² を計算することと同じである。
2. 任意の3つの非負整数 x、y、z を考える時、任意の法において少なくとも次の2つが成り立つ。なお、その2つの間には直接的な関連性はない。
   • (xy)^z ≡ x^zy^z
   • x^yz ≡ (x^y)^z ≡ (x^z)^y
3. 任意の非負整数 N₃ を用いて N₃^{p(p - 1)} mod p² を計算することを考えると、p² に対応するカーマイケル数が p(p - 1) であることとカーマイケルの定理から、その結果は常に 1 となる。つまりその部分 p(p - 1) は、法 p² において指数法則的に 0 であることを意味している。

この時点で、

C^{p - 1} mod p²

≡ (g^m × g^pqr)^{p - 1} mod p²

≡ g^{m(p - 1)} × g^{p(p - 1)qr} mod p²

≡ (g^m)^{p - 1} × 1 mod p²

≡ (g^{p - 1})^m mod p²

と述べられる。

ところで、節「値 d の正体」で既に出てきた次の2つを思い出したい。

1. g^{p - 1} mod p² が ap + 1 に等しいということ。
2. 任意の非負整数 N₁ を考える時、N₁ mod p² において p² を含む全ての項は 0 になるので、その結果は「p¹ の項」よりも大きいことはないということ。

ゆえに上記の過程を踏まえれば、 C^{p - 1} mod p² が (ap + 1)^m mod p² に等しく、さらに amp + 1 に等しいと述べることができる。

ここでやっと D の中身たる {(C^{p - 1} mod p²) - 1} / p に触れることができるわけであるが、これまでの議論から、C^{p - 1} mod p² が amp + 1 に等しいことが判明している。

したがって、{(amp + 1) - 1} / p を計算することで、 D の正体が am であると分かる。

復号の仕組み

復号の最終過程は Dd mod p を計算することであった。

ここで次の3点を確認する。

1. D は am に等しい。
2. m は p 未満である。
3. d は法 p において、a の逆元、すなわち a^{- 1} である。

このようであるから、Dd mod p を計算することは am × a^{- 1} mod p を計算することを意味し、結果的に平文たる m を得られる。