ブロックチェーン技術ブログ

ブロックチェーンと英語、数学に関するブログ

公開鍵暗号 < RSA暗号 >

公開鍵暗号では、暗号化と復号で異なる鍵を使います.
また、事前に鍵を共有する必要がなく、公開鍵は他のユーザが見えるようにしておきます.
秘密鍵のみ漏洩しないように管理する必要があります.

ブロックチェーンで使用するディジタル署名でも、公開鍵暗号の仕組みが利用されています.

暗号は、トラップドア付きの一方向関数です.
暗号文から平文を計算するのは困難ですが、鍵を利用することで暗号文から平文を計算することができます.

公開鍵暗号の暗号化・復号化の図

  暗号化 (公開鍵を使用)
平文 ⇄ 暗号文
   復号 (秘密鍵を使用)

公開鍵暗号には以下の性質が求められます

  • 強秘匿性
    暗号文から平文の情報を一部でも得ることが困難である性質.

  • 識別不可能性
    二つの平文とどちらかの暗号文が与えられたときに、それがどちらの平文の暗号文であるか特定が困難である性質.

  • 頑強性
    ある平文と暗号文のペアと別の平文と暗号文のペアに何の関係もない性質.
    平文と暗号文のペアが与えられて、その平文の一部を変えた場合、暗号文が予測できないものでなければいけません.

RSA暗号

RSA暗号は、巨大な素数素因数分解が困難である性質を利用した暗号です.

暗号化・復号に以下のパラメータを利用します.

事前に2素数 p, q を用意し、暗号化・復号に使用するパラメータをそれぞれ以下とします.
n = pq
L を p-1 と q-1 の最小公倍数
e を L と互いに素な数
d を ed ≡ 1 (mod L) を満たす数

また、公開鍵、秘密鍵を以下のように定義します.
公開鍵: e, n
秘密鍵: d

暗号化、復号はそれぞれ以下の手順でおこないます.
m を 平文とします.

暗号化 c= m^{e}\pmod n

復号 m= c^{d}\pmod n

実際に p, q, e, d に値を割り当てて、確認してみましょう.
p = 5
q = 11
n = 55
L = (5 - 1) * (11 - 1) = 40
e = 3
d = 27 ( 3 * 27 ≡ 1 (mod 40) )

メッセージ m = 4 とします.

c=4^{3}\pmod {55} = 9

m=9^{27}\pmod {55} = 4

暗号文(c=9) が 平文(m=4) に復号されたことが確認できます.

指数が大き場合は、中国剰余定理とラグランジュの定理を使用して、以下のように計算できます.
 3^{54}\pmod {5} = 3^{52} * 3^{2} \pmod{5} = 9 \pmod{5} = 4
 3^{54}\pmod {11} = 3^{50} * 3^{4} \pmod{11} = 81 \pmod{11} = 4

 9^{27} = 3^{54} を使用し式を簡略化した

したがって、 9^{27}\pmod {55} = 4
(5で割ったときに余りが4になり、11で割ったときに余りが4になる、55より小さな整数は4)