Menu

Subscribe

RSA暗号の原理

公開鍵暗号

公開鍵暗号の技法は、ICカードなど多くの装置に組み込まれている。公開鍵暗号方式で実用化されたものにRSA暗号方式[^1]がある。この暗号方式はインターネットやICカードに広く使われている。

ここでは整数論の基礎的な知識から始めて、公開鍵暗号方式のアルゴリズムを理解することが目的である。プログラムをコンピュータで実行し、その結果を確認することもアルゴリズムの理解を助ける。そこで短いプログラムの断片もアルゴリズムとともに示す。

RSA暗号を理解する

1977年にMITにいたリベスト、シャミール、エイドルマンの3人が発表した暗号方式である。

はじめに

暗号学（クリプトグラフィー、Cryptography）は、解読されたり盗聴されることがないコミュニケーション方式を考案するための数学である。それに対して暗号解析（クリプトアナリシス、Cryptanalysis）は、それらの方式を打ち破るための数学である。

さて、アリスは E というある暗号システム（encryption system）を用いて、メッセージ M を暗号文 C に変換すると仮定する。

C ＝ E(M)

この暗号文の受信者であるボブは暗号文を復号（decrypt）し平文（ひらぶん、plaintext）に戻す。

M = D(C) = D(E(M))

暗号と復号の図式例

シーザー暗号の例として3文字ずらしたやり方を図式化する。

1.平文　　　　　　M　　　　　   ATTACK
2.暗号化　　　　C=E(M)      Caesar(3)
3.暗号文　　　　C　　　　　　　　DWWDFN

         (安全でない通信チャネル)

4.復号化　　　　M=D(C)　　　 Caesar(-3)
5.受信文　　　　　M　　　　　　　ATTACK

暗号への攻撃

盗聴 攻撃者はアリスからボブへのメッセージから何かをうかがい知り得るかもしれない。

模倣 攻撃者が誰かになりすまして何かをする。例えば、クラスの誰かが職員になりすまして来週の試験はキャンセルとクラス全員にメールする。

改竄 元の文章を書き換える。例、ゴルゴ13「第257話 隠されたメッセージ」では言語学の専門家が登場し文面に巧妙な細工を行った。

カギの作り方

アルファベット26文字の場合について述べる。

ABCDEFGHIJKLMNOPQRSTUVWXYZ

カギに選んだ単語から、もっと長いフレーズを作るやり方。

FIZZLEBOP            …　カギ（単語）

ABCDEFGHIJKLMNOPQRSTUVWXYZ
FIZLEBOPACDFHJKMNQRSTUVWXY     …　26文字のフレーズ

Nを法とする代数

あるNを定め、次のN個の数のみ考えることにする。

0,1,2,……,N-1

この代数では、N 以上の数からは N を引く。また、０より小さい数には N を足す。

このようにして、「０からN-1」までの範囲で数をとりあつかうことを、

N を法（ホウ）とする代数という。Nが12のときは時計代数ともよぶ。

実（被除数）　割る　法（除数）　＝　商(q)　と　剰余(r)

整数のみを考え、それをNで割った剰余のみを考える体系である。[合同算術](合同算術 (modular arithmetic)ともいう。) (modular arithmetic)ともいう。

２つの整数 a と b が N を法として合同のとき、記号でつぎのように書く。

a ≡ b (mod N)

aとbがNを法として≡のとき、aをNで割った余りとbをNで割った余りは等しい。

具体例は、次のようになる。

17 ≡ 5 (mod 12)
3+11 ≡ 2 (mod 12)

この例は、時計で、17時が午後5時、3時の11時間後は2時というように自然に解釈される。

練習問題　次の合同式が正しいことを確かめよ

38 ≡ 14 (mod 12)

-8 ≡ 7 (mod 5)

2 ≡ -3 (mod 5)

-3 ≡ -8 (mod 5)

整数a に対して

ax ≡ 1 (mod n)

が成り立つとき、x は Modular inverseと呼ばれる。

42x ≡ 1 (mod 2017) のとき、x を求めよ。

べき乗計算

1116 (=45949729863572161)を、ｎ(=233)を法とする代数で計算する。

112 ≡ 11 ✕ 11 ≡ 121 (mod 233)

113 ≡ 11 ✕ 121 ≡ 166 (mod 233)

114 ≡ 11 ✕ 166 ≡ 195 (mod 233)

つづく…

このように素朴なアルゴリズムを16回繰り返せば16乗を計算できる。

2乗のくり返し

しかし、さらに効率を良くすることができる。それは2乗をくり返す方法である。

x16 = (x8)2

次のように、

112 ≡ 11 ✕ 11 ≡ 121 (mod 233)

114 ≡ 121 ✕ 121 ≡ 195 (mod 233)

118 ≡ 195 ✕ 195 ≡ 46 (mod 233)

1116 ≡ 46 ✕ 46 ≡ 19 (mod 233)

4回のくり返しで、16乗は計算できる。

一般には指数が２のべき乗なのはめずらしい。

しかしながら、２乗のくり返しの背景にあるアイデアを任意の指数に適用することができる。

任意の指数計算

次の式の値を求めたいとしよう。

ga　(mod n).

ここで、指数 a を次のように２進数に展開する。

(bk, bk-1, bk-2,… ,b0,)

次にd=1からはじめ、aを２進数展開したものについて位の高いビットから低いビットへ順に読んでいくことにする。

各段階で

d ← d2 (mod n)

かつ、もしもビットが１ならば次の演算を行うことにする。

d ← d ✕ g (mod n)

具体例

1125 (mod 233) を計算する。

25の2進数展開は11001であるから、各ステップとその結果は、

ステップ　ビット　2乗　　積
  1        1    1    11
  2        1   121  166
  3        0    62
  4        0   116
  5        1   175   61

となる。したがってたかだか aを2進数展開したけた数の、ステップ数の計算で完了する。各ステップの計算は2数のｎを法とする乗算だけである。

ユークリッド（Euclid）の互除法

２つの正の整数 m, n の最大公約数は次の命令によって求められる。

  1. m　と　n　を比較し、必要なら入れかえて、m ≧ n とせよ。

  2. m　を　n　で割り、商を ｑ、余りを ｒ とせよ。

  3. 余りｒ が 0（ｍがｎで割り切れた）ならば、ｎ が最大公約数であり、完了した。

  4. 余りｒ が 0でなければ、ｎ を ｍ、 ｒ を ｎ と置き、２へ戻れ。

この操作を反復すれば、いつかは必ず m が n で割り切れて、手続きは完了する。

このように、あいまいな操作がなく、それらを忠実に実行すれば必ず完了する命令の集まりをアルゴリズムという。

ユークリッドの互除法は、古代ギリシャの用語ではないが古くから**「ユークリッドのアルゴリズム」**と呼ばれていた。

このユークリッドのアルゴリズムは現存するアルゴリズムのなかで最も初期のものであり、かつ現代でも利用されるものである。

練習問題　ユークリッドの互除法をもちいて、m=356256 と n=66600 として m と n の最大公約数(GCD)を求めよ。この方法では、GCDが求まるまでに何回割り算が実行されたか。

練習問題　m, n のけた数を大きくしたとき、割り算が実行される回数はどのように増えていくだろうか。m,nのけた数とGCDが求まるまでの割り算の実行回数を調べる。

ユークリッドのアルゴリズム

いまa を次のような式で表すことにする。

a = qb + r

ここで、q は a を b で割った商、 r < b は余りとよばれる。

さて　d=gcd(a,b) は、bとrを割り切ることになる。さらに、容易にわかることは、bとｒを割り切る数は、aも割り切ることができる。

したがって、

d = gcd(a,b) = gcd(b,r)

である。

このことから自明な再帰的関数(recursive function) gcd(a,b)の定義が導かれる：

function gcd(a,b)
   if b=0 return a
   else return gcd(b, a mod b)

JavaScript でユークリッドのアルゴリズムを記述し、HTMLファイルで実行するには次のファイルに名前をつけて保存しブラウザで読み込めばよい。

Imgur

この例、gcd(450,42)を計算する。

関数呼び出し     a    =     q・b   +  r
gcd(450,42)   450   =    10・42  + 30
gcd(42,32)     42   =     1・30  + 12
gcd(30,12)     30   =     2・12  +  6
gcd(12,6)      12   =     2・6   +  0
gcd(6,0)

練習問題

関数　gcd(a,b)をHTMLの インプットタグを使って数を入力し、それをJavaScriptのdocumentオブジェクトに対するメソッドquerySelectorを使って処理するHTMLファイルを次に示す。入力と出力の表示方法を調べ、表示を日本語化するなど入出力をもう少し工夫してみよう。

Imgur

Imgur

オイラー関数φの値

1761年（宝暦11年）にレオンハルト・オイラーによって発見された関数φ(n)は、正整数nのn 以下の互いに素な自然数の総数を出力する。

オンライン整数列大辞典によればオイラー関数の値は1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, のようになる。すなわち、

φ(1)    1
φ(2)    1
φ(3)    2
φ(4)    2
φ(5)    4
φ(6)    2
φ(7)    6
φ(8)    4
φ(9)    6
φ(10)    4
φ(11)    10
φ(12)    4
φ(13)    1
φ(14)    2

のようにつづく。

オイラー関数φ(n)は、[オイラーのトーシェント関数](https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0)(Euler's totient function)とも呼ばれている。

たとえば、n=6のとき、1から6までの *1,2,3,4,5,6* のうちで互いに素な自然数は、1と5の2個であるから、φ(n)の値は2となる。

これは分母をnとしたときの既約分数の個数を数えると言ってよい。実際に1/6と5/6以外(*2/6,3/6,4/6,6/6*) はそれぞれ約分(1/3,1/2,2/3,1/1)できるため既約分数ではない。

このようにnとn以下の互いに素である個数を数えるのと、n以下の既約分数の個数を数えるのは同じことである。

#### Euler's totient function　（オイラー関数φの計算プログラム）

φ(40) の計算をするJavaScript プログラム。

<a href="https://imgur.com/tWJ8c8B"><img src="https://i.imgur.com/tWJ8c8B.png" title="source: imgur.com" /></a>


#### オイラー関数φの基本性質
飯高茂『数学の研究をはじめよう（Ⅰ)』第3章、29,30頁より一部引用。

1.　n が素数pならpより小さい分子はすべてpと互いに素なのでφ(p)=p-1.
2.　nが素数p<sup>2</sup>なら分子はpの倍数でないときp<sup>2</sup>と互いに素なのでφ(p<sup>2</sup>)=p<sup>2</sup>-p=p(p-1).
3.　一般にはφ(p<sup>e</sup>)=p<sup>e-1</sup>(p-1).
4. p,q が互いに素なら φ(pq)=φ(p)φ(q).

オイラー関数φについて、これらの性質をプログラムを使って確かめてみよう。



### 拡張ユークリッド アルゴリズム

さて、a と b の最大公約数 d を求めることができたので、次に d を a と b を線形に組み合わせることによって表してみよう。

    d = xa + yb

すなわち、われわれはこの式を満たす、x と y を見つけなければならない。

このために関数gcd(a,b)を拡張し、aとbを与えれば、 triple(d,x,y)を値として返す関数を作らなければならない。ただし、d=gcd(a,b)=xa+yb.

    if b=0
    return (a,1,0)

再帰的なケースについて考察する：

    a=qb+r

かつ、再帰解から

    d=x'b + y'r

であるから

    d = x'b + y'(a-qb) = y'a + (x'-qy')b

となる。

ゆえに、

    (d,x',y') ← gcd(b, a mod b)
    (d,x,y) ← (d,y',x' - y' int(a/b))
    return (d,x,y)




## RSA 暗号の手順

1. 十分大きな２個の素数 *p,q* を選ぶ（100けた以上の素数）。

* その積 *n=p✕q* と、*φ(n)=(p-1)(q-1)* を計算する。

* 小さな奇数*e*を選ぶ。そのとき φ(n)に対して互いに素(relatively prime to each other)であるようにする。

* ユークリッドの拡張アルゴリズムを用いて次の式を解く。

    *ed ≡ 1 (mod φ(n)).*

* 公開鍵は *(n,e)* である。これを公開する。秘密鍵は *d* である。


## RSA暗号システムの使い方

1. あなたがボブにメッセージ m を暗号化して送りたいと仮定する。そこで、あなたはボブの公開鍵 (n,e)を見つけ、次の式のように平文*m*を*e*乗してからそれのnを法とした数を計算で求める。これで平文*m*が暗号文*c*に変換される。そこであなたは、ボブにメッセージ c を送信する。

  *c = m<sup>e</sup> (mod n)*

2. ボブは、メッセージ*c* を受信したら、彼自身の秘密鍵 d を使って、次の計算をする。

 *c<sup>d</sup> (mod n)*

 したがって、ボブは次の計算をすることになる。

 *c<sup>d</sup> = m<sup>ed</sup> = m<sup>1+kφ(n)</sup> = m(m<sup>φ(n)</sup>)<sup>k</sup>*

 ここで初等整数論の定理により、任意の*x*について次の式が成り立つ。


 *x<sup>φ(n)</sup> ≡ 1 (mod n)*


3. 故に、

 *m<sup>ed</sup> ≡ m (mod n).*

### RSA コードの例

[RSA code - rosettacode.org](http://rosettacode.org/wiki/RSA_code)


#### J コード

N=: 9516311845790656153499716760847001433441357x
E=: 65537x
D=: 5617843187844953170308463622230283376298685x

] text=: 'Rosetta Code'
Rosetta Code
] num=: 256x #. a.i.text
25512506514985639724585018469
num >: N NB. check if blocking is necessary (0 means no)
0
] enc=: N&|@^&E num
916709442744356653386978770799029131264344
] dec=: N&|@^&D enc
25512506514985639724585018469
] final=: a. {~ 256x #.inv dec
Rosetta Code



#### コードの解説

#### Ascii code

a. i. 'R'
82
a. i. 'o'
111

したがって、text =: 'Rosetta Code'のとき

a.i.text
82 111 115 101 116 116 97 32 67 111 100 101


問題

`a.` とJコンソール画面でタイプするとどうなるだろうか。

問題

`77 { a.` とJコンソール画面でタイプするとどうなるだろうか。


問題

自分の名前を アスキーコード で打ち込む。

問題

#### n進法

2 #. 1 0 1
5
3 #. 1 0 1
10
4 #. 1 0 1
17
5 #. 1 0 1
26
6 #. 1 0 1
37
12 #. 1 0 1
145

256x #. a.i.text
25512506514985639724585018469






---


### Enigma

[How 2,000 Droplets Broke the Enigma Code in 13 Minutes](https://blog.digitalocean.com/how-2000-droplets-broke-the-enigma-code-in-13-minutes/?utm_medium=email&utm_source=IaaN&utm_campaign=07052018)




------

[*1]: RSA(Rivest–Shamir–Adleman) Cryptosystem. 1977.