こんにちは。Inishie Once-in-a-Lifetime Chanceブログのいにしえ時渡です。前回と前々回は当記事でミックスするための2つのキーワードに関して説明をしました。つまり、一次合同式とフェルマーの小定理についてです。覚えてますか？僕のこと。久しぶりに会う友人ではないですが、この2つのキーワードについて再度確認していきたいと思います。
さて、一次合同式は「aとbはmを法として合同である」ということです。いきなり読者さんを錯乱させようとしていますが、a ≡ b (mod m)という式について、aとbをmで割った余りは同じということを意味します。僕の錯乱作戦は、ファンタジーの世界では、月見草などを使って混乱を解いてもらいたいのですが、次はさらに高難易度のフェルマーの小定理です。
フェルマーの小定理は、a^(p-1)≡1 (mod p)という式で、pを素数とすると、aは1からp-1までの値でmod pで1になるという難攻不落の暗号です。今回は、楕円曲線暗号について話を進めていきたいので、暗号というキーワードは伏線だと思ってください。
もし、前回のオイラーのファイ関数という名前を少しでも覚えていたら、正しくはa^φ(p)= 1 mod pであったことを思い出すはずです。ここで、前回の記事のリンクを貼っておきますね。僕は基本的に記事に関するたらい回しは好きではないので、もしコケて救急車を呼ぶことになったら、すぐにファンタジーの世界に連れていって足がなくても歩ける呪文を教えてあげます。幽霊か！？少しシュールですね（笑）。
まあ、久しぶりの空回ったギャグはここまでにしておいて、φ(p)とはpが互いに素になる数値の個数でした。つまり、pが素数の7であれば、7-1=6個であるし、pが素数でない合成数の9であれば、1,2,4,5,7,8の6個でした。この場合、それぞれφ(7)=6とφ(9)=6となります。つまり、aを6回掛けてmod pすると、aとpが互いに素なら、1 mod pとなるということでした。
さて、ここまで結構手抜きで足早に説明してきました。復習ということですが、詳しく知りたい方は前回と前々回の記事を参照してください。
ここからは、暗号の話です。暗号という名の魔界についての話ですが、よろしければ引き続き僕の話をお楽しみください。
暗号というと古代文明のルーン文字を思いつく人もいるでしょう。はるか昔に使われていた文字は現代の人から見れば、まさに暗号の名にふさわしいです。レッツ・暗号！！
暗号の中でも現代でよく使われる暗号はRSA暗号、つまり素因数分解に関する暗号と、楕円曲線暗号つまり楕円曲線を用いた暗号になります。素因数分解の暗号である、RSA暗号はクレジットカードの暗証番号を預金口座のある銀行に送信するために使われる暗号です。一方、楕円曲線はご老人に聞いても、はて？と言われそうな暗号通貨に関する暗号で利用されています。
今回はこの楕円曲線について簡単に解が見つかる方法を紹介したいと思います。みなさんも、はて？一次合同式？フェルマーの小定理？何だったかな？と言わずに、ぜひ前の記事で予習復習に努めてみてください。そうすれば、僕の話の糸口が見えてくるはずです。
さて、ビットコインで使われる楕円曲線暗号とはいかなるものか。まず、次の式を見てください。今回はxを掛けるという意味ではなく、一つの変数として表しています。ご注意を！！
y^2 ≡ x^3 + 7 mod p
なにやら複雑な術式を使うなとお思いの方。ご安心ください。yとpについてはあらかじめ値が分かっているのでxだけを求めます。ちなみに、「^」という記号ですが、y^2とはyの2乗。つまりyが2回掛けられたもの。x^3とはxの3乗。つまり、xが3回掛けられたもの、を意味します。
例えば、y=11、p=17としましょう。実際に、数値を代入して、整理してみると次のようになります。
11^2 ≡ x^3 + 7 mod 17
121 – 7 ≡ x^3 mod17
x^3 ≡ 114 mod 17 ≡ 12 mod 17
x^3 ≡ 12 mod 17
ここで、114を17で割った余りは12となります。ポイントの一つなのですが、この楕円曲線の式は三次合同式です。つまりxの3乗の合同式です。これに対して、フェルマーの小定理を適用してみましょう。両辺を5乗してみます。
x^(3×5) ≡ 12^5 mod 17
p=17は素数なので、x^16はxとpが互いに素であれば、1mod17となります。さらに両辺にxを掛けます。
x^(3×5+1) ≡ x(12^5) mod17
x^16 mod 17 ≡ 1mod17 ①
(12^5)x mod 17 ≡ 248832x mod17 ≡ 3x mod17 ②
3x mod 17 ≡ 1 mod 17 ②＝①
両辺に6を掛けると18xとなり17x+x ≡ x mod17となります。この両辺に掛ける6の求め方に関しては前回の記事のユークリッドの互除法を参照してください。
x mod 17 ≡ 6 mod 17
答え：x = 6 mod 17
検算：x^3 ≡ 6^3 ≡ 12 mod 17
よって、答えが分かります。もう一つ、例を挙げてみましょう。y=8,p=17の場合はどうでしょうか。
8^2 ≡ x^3 + 7 mod 17
64 – 7 ≡ x^3 mod17
x^3 ≡ 57 mod 17 ≡ 6 mod 17
x^3 ≡ 6 mod 17
x^(3×5) ≡ 6^5 mod 17
x^(3×5+1) ≡ x(6^5) mod 17
x^16 ≡ 1 mod 17 ≡ (6^5)x mod 17 ≡ 7776x mod 17 ≡ 7x mod 17
7x ≡ 1 mod 17
両辺に5を掛ける。
35x ≡ x ≡ 5 mod 17
x ≡ 5 mod 17
x^3 ≡ 5^3 ≡ 6 mod 17
よって、答えが分かりました。ここでのポイントはフェルマーの小定理です。フェルマーの小定理の使い方次第ではa^(p-1)が1 mod pになるというところがポイントです。どれだけ多くのaが掛け合わされていても条件次第では1 mod pと変換できるのです。
今回は楕円曲線について答えの求め方を解説しましたが、例えば、a^3+b^3+c^3=pについても与えられるpの値に対してaとbとcを求めることが可能かもしれません。これに関しては自分で計算してみましょう。難易度は相当高いですよ。伝説を作ろうの会。
いかがでしたか。一次合同式とフェルマーの小定理は関係性が深いように思えますが、合成してみると新しい数式の解き方を発見することができました。今回は2つのキーワードを混ぜただけですが、キーワードを3つ混ぜるとさらに進んだ考え方を見つけることができるかもしれませんね。今回は以上です。
コメント