【4話】やさしく学ぶBitcoinの暗号技術:RSA暗号の仕組み(前編)

前回までに\( {\rm mod}\)と素数の準備を終わらせました。

【3話】やさしく学ぶBitcoinの暗号技術:RSA暗号の準備体操

2017.09.30

\(N\)を法とする世界の乗算


もう一度素数\(p\)に素数\(q\)を乗じた\(N\)を法とする世界を考えてみましょう。

この世界では以下の数式が成り立ちます。
$$x\cdot y=(x\times y)\ {\rm mod}\ N$$
因みに左項の「\(\cdot\)」は\(N\)を法とする世界での乗算で、右項の「\(\times\)」は通常の意味での乗算となります。
文字で表現するとわかりにくいので、実際に数字を入れてみていきます。

前提は下記の通りにします。
\(p=3,\ q=7,\ N=21\)です。
仮に\(x=5,\ y=8\)としてみましょう。すると、
$$x\cdot y=(5\times 8)\ {\rm mod}\ 21=19$$
となり、21を法とする世界では\(x=5,\ y=8\)のとき\(x\cdot y=19\)になることが確認できました。

累乗しても元に戻る\(M\)

\(x\cdot y=(x\times y)\ {\rm mod}\ N\)が成り立つ世界において、ある条件を満たすと、不思議な現象が起こります。その現象とは
$$M^w=M$$
です。

つまり、ある整数\(M\)を\(w\)乗したら、またもとの\(M\)に戻るというわけです。不思議ですね~。この現象が起こる条件はどんな条件なのでしょうか。その条件とは
$$w=(p-1)(q-1)+1$$
です。

つまり、最初に選んだ素数\(p\)と\(q\)を用いた条件\(w\)を満たしたとき、\(M^w=M\)という現象が起こるのです!

ここまでの振り返りと実例の確かめ

文系ビットコイナーのみんな、ちゃんとHODLしてますか?まだあまり実感が掴めていなくても大丈夫。今からここまでの総復習と、実際に数字をいれて確かめを行います。

まずは\(N\)を法とする世界の準備と条件の確認をし、その上で成り立つ現象を確認します。「\(\forall\)」は「任意の」という記号です。

準備

$$\forall p, \forall q \in 素数$$
$$\forall x, \forall y \in 自然数$$
$$N=p\times q$$
$$A\ {\rm mod}\ B=AをBで割った余り$$

条件

$$x\cdot y=(x\times y)\ {\rm mod}\ N$$
左項の「\(\cdot\)」は\(N\)を法とする世界での乗算で、右項の「\(\times\)」は通常の意味での乗算です。
$$w=(p-1)(q-1)+1$$

現象

この準備、条件が成り立つとき、\(M=x\cdot y=(x\times y)\ {\rm mod}\ N\)とすると下記の現象が起こります。
$$M^w=M$$

確かめ

  1. \(p=29,\ q=541\)(試しに素数の大きさで10番目と100番目をチョイス。)
  2. \(N=p×q=29×541=15689\)(\(N\)の値を\(p,\ q\)を用いて計算。)
  3. \(w=(p-1)(q-1)+1=28×540+1=15121\)
  4. \(x\cdot y=(x\times y)\ {\rm mod}\ N=(x\times y)\ {\rm mod}\ 15689\)が成り立つ。
  5. \(x=123,\ y=456\)(試しにチョイス。意味はないです。)
  6. \(M=x\cdot y=(x\times y)\ {\rm mod}\ N=(123\times 456)\ {\rm mod}\ 15689=9021\)
  7. \(M^w=M^w\ {\rm mod}\ N=9021^{15121}\ {\rm mod}\ 15689=9021\)
  8. \(M^w=M\)
    1. \(M^w\)が\(M\)に一致したのがおわかりいただけただろうか…。

      この仕組みを使って平文を暗号化しよう!


      と思ったのですが、結構沢山数式がでてきましたらね。
      疲れちゃいました。暗号化は次回に持ち越しです!

      次回もお楽しみに!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です