「利用者:Meauk/暗号20221225」の版間の差分

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

2022年12月26日 (月) 22:34時点における最新版

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

暗号の構成[編集]

鍵生成 by 受信者[編集]

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

暗号化 by 送信者[編集]

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

復号 by 受信者[編集]

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

成立の証拠[編集]

値 d の正体[編集]

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

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

したがって、a とは「gp - 1p2 で割った時の p1 の項の係数」であると述べることができる。

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

値 D の正体[編集]

初めに Cp - 1 mod p2 について考える。

そもそも暗号文は C ≡ gm + nr (mod n2) によって求められるが、これは言い換えると C ≡ gm × gpqr (mod p2q2) である。

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

  1. 任意の非負整数 N2 を用いて (N2 mod p2q2) mod p2 を計算することを考える時、それは初めから N2 mod p2 を計算することと同じである。
  2. 任意の3つの非負整数 xyz を考える時、任意の法において少なくとも次の2つが成り立つ。なお、その2つの間には直接的な関連性はない。
    • (xy)z ≡ xzyz
    • xyz ≡ (xy)z ≡ (xz)y
  3. 任意の非負整数 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つを思い出したい。

  1. gp - 1 mod p2ap + 1 に等しいということ。
  2. 任意の非負整数 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 p2amp + 1 に等しいことが判明している。

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

復号の仕組み[編集]

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

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

  1. Dam に等しい。
  2. mp 未満である。
  3. d は法 p において、a の逆元、すなわち a- 1 である。

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