「利用者:Meauk/sandbox」の版間の差分
提供: Yourpedia
(→値 D の正体: 下書き4) |
(下書き5) |
||
| 1行目: | 1行目: | ||
== 成立の証拠 == | == 成立の証拠 == | ||
=== 値 d の正体 === | === 値 d の正体 === | ||
| − | <span style="color:red">'''a'''</span> が <span style="color:red">'''{(g<sup>p - 1</sup> mod p<sup>2</sup>) - 1} / p'''</span> に等しいということは、<span style="color:red">'''g<sup>p - 1</sup> mod p<sup>2</sup>'''</span> が <span style="color:red">'''ap + 1'''</span> に等しいことを意味する。これには次の2点が関わる。 | + | <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>p - 1</sup> ≡ 1 (mod p)'''</span> が成立するということ。 | + | # <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>1</sub>'''</span> を考える時、<span style="color:red">'''N<sub>1</sub> mod p<sup>2</sup>'''</span> において <span style="color:red">'''p<sup>2</sup>'''</span> を含む全ての項は <span style="color:red">'''0'''</span> になるので、その結果は「<span style="color:red">'''p<sup>1</sup>'''</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>p - 1</sup>'''</span> を <span style="color:red">'''p<sup>2</sup>'''</span> で割った時の <span style="color:red">'''p<sup>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> の逆元」に相当することになる。 | その上で、<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 の正体 === | === 値 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>m + nr</sup> (mod n<sup>2</sup>)'''</span> によって求められるが、これは言い換えると <span style="color:red">'''C ≡ g<sup>m</sup> × g<sup>pqr</sup> (mod p<sup>2</sup>q<sup>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点に注意する。 | この時、次の3点に注意する。 | ||
| − | # 任意の非負整数 <span style="color:red">'''N<sub>2</sub>'''</span> を用いて <span style="color:red">'''(N<sub>2</sub> mod p<sup>2</sup>q<sup>2</sup>) mod p<sup>2</sup>'''</span> を計算することを考える時、それは初めから <span style="color:red">'''N<sub>2</sub> mod p<sup>2</sup>'''</span> を計算することと同じである。 | + | # 任意の非負整数 <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> | + | # 任意の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>z</sup> ≡ x<sup>z</sup>y<sup>z</sup>'''</span> | + | #* <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>yz</sup> ≡ (x<sup>y</sup>)<sup>z</sup> ≡ (x<sup>z</sup>)<sup>y</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>3</sub>'''</span> を用いて <span style="color:red">'''N<sub>3</sub><sup>p(p - 1)</sup> mod p<sup>2</sup>'''</span> を計算することを考えると、<span style="color:red">'''p<sup>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>2</sup>'''</span> において指数法則的に <span style="color:red">'''0'''</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>p - 1</sup> mod p<sup>2</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">'''≡ (g<sup>m</sup> × g<sup>pqr</sup>)<sup>p - 1</sup> mod p<sup>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>m(p - 1)</sup> × g<sup>p(p - 1)qr</sup> mod p<sup>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>m</sup>)<sup>p - 1</sup> × 1 mod p<sup>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>p - 1</sup>)<sup>m</sup> mod p<sup>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つを思い出したい。 | ところで、節「[[#値 d の正体|値 d の正体]]」で既に出てきた次の2つを思い出したい。 | ||
| − | # <span style="color:red">'''g<sup>p - 1</sup> mod p<sup>2</sup>'''</span> が <span style="color:red">'''ap + 1'''</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> に等しいということ。 |
| − | # 任意の非負整数 <span style="color:red">'''N<sub>1</sub>'''</span> を考える時、<span style="color:red">'''N<sub>1</sub> mod p<sup>2</sup>'''</span> において <span style="color:red">'''p<sup>2</sup>'''</span> を含む全ての項は <span style="color:red">'''0'''</span> になるので、その結果は「<span style="color:red">'''p<sup>1</sup>'''</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>p - 1</sup> mod p<sup>2</sup>'''</span> が <span style="color:red">'''(ap + 1)<sup>m</sup> mod p<sup>2</sup>'''</span> に等しく、さらに <span style="color:red">'''amp + 1'''</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> であると分かる。 | ||
| + | === 復号の仕組み === | ||
| + | （加筆予定） | ||
2022年12月26日 (月) 18:16時点における版
成立の証拠
値 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 であると分かる。
復号の仕組み
（加筆予定）
