暗号送受信では、送りたいメッセージ(平文)を何らかの加工をして全く意味不明の数値(暗号化)にして送信し、受信者はあるロジックで元の平文に返還(復合化)して判読する

暗号の複号化を検証

では具体的に公開鍵と秘密鍵の関係を、例を基に見てみましょう。ここでは紙面の関係で便宜的に素数3と素数5の積である15という極めて小さい数値を法とする世界で検証します。

法Y=P×Q=15=3×5(実際の運用では法は10の160乗程度の数値のようです)。法を15とした場合、全ての自然数は下表左の通り0から14の値しかとり得ません。

下表左で値2の行(青点線の行)を例にとると、2を1乗した2を15で割った余りは2、2乗した4を15で割った余りは4、3乗した8を15で割った余りは8、4乗した16を15で割った余りは1となることを示した表になります。右に行くにしたがってべき乗数が増えることを表しています。ここでは紙面の関係で10乗までしか書いておりません。また縦方向には、例えば47の3乗の103,823を15で割ると余りは8になるので8行目に相当します。

さてここで、下表の配列で何か面白い特性に気づきませんか?　そうです。縦の列で周期的に元の数値に戻っていますよね。例えば5列目(5乗した値の列)は上から順に0、1、2、3、4、……、14になり、また9列目でも同様になっています。法の世界では、(p-1)と(q-1)の最小公倍数に1を加えた数値をべき乗する毎に元の数値に戻る、という大変素晴らしい特性があります。この原理さえ理解すればRSA暗号化は99%理解できたことになります。「ほんまかいね?」という人のために下表右に検証用の例を用意しました。さらに原理を極めたい人はオイラーの定理を調べると良いでしょう。

仮に平文の数値を「2」「5」「9」「13」としましょう。ここで受信者は法を15にして、平文を3乗(公開鍵)した暗号文で送るように依頼します。送信者は言われた通り元の数値を3乗し法15で割った余りの「8」「5」「9」「7」を送信します。受信者は元に戻る周期4n+1が分かっていますから、ここでは簡単なn=1を入れた「5」として自分の秘密鍵を5-3(公開鍵)+1=3として「8」「5」「9」「7」をそれぞれ3乗して15で割った余りを求めます。すると、どうでしょう。それぞれが元の「2」「5」「9」「13」に戻るではありませんか。これがRSA暗号の暗号化と復号化における公開鍵と秘密鍵の原理なのです。

本記事は、アイ・ユー・ケイが運営するブログ「つぶやきの部屋」を転載したものになります。

(マイナビニュース広告企画：提供 アイ・ユー・ケイ)

[PR]提供：