利用者:Meauk/暗号20221225
2022年12月25日に Meauk が作成した公開鍵暗号方式について記されている。なお、2022年12月26日現在、その正式名称はまだ存在しない。
暗号の構成[編集]
鍵生成 by 受信者[編集]
- 同じ桁数だが互いに異なる2つの素数 p と q をそれぞれ選択。
- n = pq を計算。
- 法 p における原始根として g を設定。
- {(gp - 1 mod p2) - 1} / p に等しい値を仮に a と置くとき、ad ≡ 1 (mod p) となるような d を計算。
- (n, g) の組を公開鍵に、(p, q, d) の組を秘密鍵に設定。ただし、q は直接的には不使用。
- 公開鍵 (n, g) をボブ宛に送信。
暗号化 by 送信者[編集]
- n2 未満の正整数 r を無作為に選択。
- p 未満の平文 m を用意し、暗号文 C ≡ gm + nr (mod n2) を計算。
- 暗号文 C をアリス宛に送信。
復号 by 受信者[編集]
- D = {(Cp - 1 mod p2) - 1} / p を計算。
- Dd = m (mod p) により、平文 m を入手。
成立の証拠[編集]
値 d の正体[編集]
a が {(gp - 1 mod p2) - 1} / p に等しいということは、gp - 1 mod p2 が ap + 1 に等しいことを意味する。これには次の2点が関わる。
- g と p が互いに素(最大公約数が1)である時、フェルマーの小定理によれば gp - 1 ≡ 1 (mod p) が成立するということ。
- 任意の非負整数 N1 を考える時、N1 mod p2 において p2 を含む全ての項は 0 になるので、その結果は「p1 の項」よりも大きいことはないということ。
したがって、a とは「gp - 1 を p2 で割った時の p1 の項の係数」であると述べることができる。
その上で、d が ad ≡ 1 (mod p) によって求められるというので、この d は「法 p における a の逆元」に相当することになる。
値 D の正体[編集]
初めに Cp - 1 mod p2 について考える。
そもそも暗号文は C ≡ gm + nr (mod n2) によって求められるが、これは言い換えると C ≡ gm × gpqr (mod p2q2) である。
この時、次の3点に注意する。
- 任意の非負整数 N2 を用いて (N2 mod p2q2) mod p2 を計算することを考える時、それは初めから N2 mod p2 を計算することと同じである。
- 任意の3つの非負整数 x、y、z を考える時、任意の法において少なくとも次の2つが成り立つ。なお、その2つの間には直接的な関連性はない。
- (xy)z ≡ xzyz
- xyz ≡ (xy)z ≡ (xz)y
- 任意の非負整数 N3 を用いて N3p(p - 1) mod p2 を計算することを考えると、p2 に対応するカーマイケル数が p(p - 1) であることとカーマイケルの定理から、その結果は常に 1 となる。つまりその部分 p(p - 1) は、法 p2 において指数法則的に 0 であることを意味している。
この時点で、
- Cp - 1 mod p2
- ≡ (gm × gpqr)p - 1 mod p2
- ≡ gm(p - 1) × gp(p - 1)qr mod p2
- ≡ (gm)p - 1 × 1 mod p2
- ≡ (gp - 1)m mod p2
と述べられる。
ところで、節「値 d の正体」で既に出てきた次の2つを思い出したい。
- gp - 1 mod p2 が ap + 1 に等しいということ。
- 任意の非負整数 N1 を考える時、N1 mod p2 において p2 を含む全ての項は 0 になるので、その結果は「p1 の項」よりも大きいことはないということ。
ゆえに上記の過程を踏まえれば、 Cp - 1 mod p2 が (ap + 1)m mod p2 に等しく、さらに amp + 1 に等しいと述べることができる。
ここでやっと D の中身たる {(Cp - 1 mod p2) - 1} / p に触れることができるわけであるが、これまでの議論から、Cp - 1 mod p2 が amp + 1 に等しいことが判明している。
したがって、{(amp + 1) - 1} / p を計算することで、 D の正体が am であると分かる。
復号の仕組み[編集]
復号の最終過程は Dd mod p を計算することであった。
ここで次の3点を確認する。
- D は am に等しい。
- m は p 未満である。
- d は法 p において、a の逆元、すなわち a- 1 である。
このようであるから、Dd mod p を計算することは am × a- 1 mod p を計算することを意味し、結果的に平文たる m を得られる。