暗号通貨 要素技術

RSA暗号方式

投稿日:2017年6月3日 更新日:


 

 

RSA暗号の仕組み

ビットコインの説明で用いた「暗号ダイヤル」について詳しく解説していきます。この暗号ダイヤルというのは”RSA暗号”というもののモデル化です。

簡単に説明したのは,
・「秘密の回数」だけ回した暗号ダイヤルに表示された数字を入力エリアに入れた暗号ダイヤルを「公開の回数」だけ回すと元の数字が表示される.
という特徴でした.

この不思議なダイヤルがどのような仕組みで成り立っているのかについて解説していきます.

暗号ダイヤルの挙動

まず,文章を数字に変えます.たとえば,テキストが5という数字に変換されたとしてください.(もちろん実際はもっと大きな数字に変換されます)
暗号ダイヤルには型番があり,型番はたとえば”mod 33″のようにそれぞれのダイヤルに書かれています.
この型番は何を意味するのでしょうか?

暗号ダイヤルを実際に回してみましょう.
最初にテキストとして5を暗号ダイヤルに入力します.

入力すると表示エリアは1となります.(5の0乗です)
この暗号ダイヤルを一回回してみます.

5になりました.
1(表示)×5(input)が計算されました.
もう一回回してみましょう.

5(表示)×5(input)=25
もうわかりましたね.
次は
25×5=125より,125だ!
と思いきや,表示されたのは

26
です.
何が起こったのでしょうか?
ここで型番が登場します.
125÷33 = 3 あまり 26
型番で割ったあまりが表示されました.
これが暗号ダイヤルの機能です.

暗号としての動作

では,続いて本題.「秘密の回数」回した暗号ダイヤルで表示された数字を入力に入れ,「公開の回数」だけ回すと元の数字に戻る.ということについて解説します.
もとの数字が5,秘密の回数が7,ダイヤルの型番は33,公開の回数は3とします.
まず,もとの数字を入れ,秘密の回数だけダイヤルを回します.
$$
5(もとの数字)^{7(秘密の回数) }mod 33(型番)\\
= 78125 mod 33\\
= 14
$$

続いてoutputをinputに代入します.


そして公開した回数だけダイヤルを回します.
$$
14^{3(公開の回数)} \;\;mod 33\\
= 5
$$

もとの数字に戻りましたね!

RSA暗号の数学的な説明

これらの回数はデタラメに決めていいわけではありません.
「フェルマーの小定理」というもので成り立っています.
$$gが素数pの倍数でないとき,g^{p-1} mod \; p = 1$$
証明は帰納法を用いて簡単にできます.

これを少し拡張させます.
$$g^{(p-1)(q-1)} mod\; pq = 1$$

(証明)
この拡張は「aは3と5の倍数であるから,aは15の倍数だ」というイメージです.
$$g^{p-1} mod\;p = 1 より$$
$$g^{(p-1)(q-1)} mod\;p = 1$$
$$(8 mod 5 = 3であり,このとき8^2 mod \;5 = 3^2 mod\; 5のように,一度割り切った数は無視できます)$$

$$g^{(p-1)(q-1)} mod\;p = 1 よりg^{(p-1)(q-1)}-1はpの倍数$$
(参考:16÷3 = 5 あまり 1のとき16-1 は5の倍数)
$$g^{(p-1)(q-1)} mod\; q = 1 よりg^{(p-1)(q-1)}-1はqの倍数$$
$$pとqは互いに素であるため,g^{(p-1)(q-1)} -1 はpqの倍数$$
$$g^{(p-1)(q-1)} mod\; pq = 1$$

この式にさらにgをかけると,
$$g×g^{(p-1)(q-1)}mod\; pq = 1 × g = g$$
要するに,
$$g^{(p-1)(q-1)+1} mod\; pq = gとなるのです.$$
あとは 「公開鍵」×「秘密鍵」= (p-1)(q-1)+1となる数字を準備するだけです!


-暗号通貨, 要素技術

執筆者:


  1. […] 暗号ダイヤルに関しては詳しく別記事で解説しました. […]

comment

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

関連記事

no image

暗号通貨 情報サイト

暗号通貨の価値は大きく変動します. 何がその変動をもたらすのでしょうか. 株取引をしている方は日本語のニュースを見ていれば十分でしょうが,暗号通貨の場合,最新情報はやはり英語サイトです. bitcoi …

no image

Bitcoinの仕組み

Bitcoinの仕組み ブロックチェーン技術の中でも本記事ではbitcoinの仕組みに焦点をしぼって解説します. bitcoin のnetwork まず,bitcoinのwhitepaper(サトシナ …

no image

暗号通貨投資法

私は2017年2月ごろにようやくbitcoinが盛り上がってきていることに気づいたので参入は遅いです. しかし,投資法が良かったのか,2カ月後には投資した額が3倍になっていました. 功を奏したのは「b …

no image

暗号通貨の認証方式

暗号通貨として最も有名なのはBitcoinですが,その認証方式が”Proof of work”ということはご存じでしょう. 他の認証方式としてはEthereumで用いられる&# …