単語記事: RSA暗号

編集

RSA暗号とは、開鍵暗号のひとつであり、現在インターネットで広く使われている暗号である。

概要

大きな数を素因数分解するのは、現代の技術をもってしても非常に時間がかかる。RSA暗号はこれを利用しているのである。どんなに大きな数でも素因数分解不可能ではないので、いつかは解読されてしまう。しかし、その頃には情報としての価値はなくなっているので、暗号としての役割を果たす。

方法

鍵生成

まず、暗号で用いる鍵を次のようにして用意する。

  1. 異なる2つの素数p,qを適当にとる。
  2. n = pqとする。
  3. 自然数eを、(p-1)(q-1)との最大公約数が1となるように適当にとる。
  4. 自然数dを、edを(p-1)(q-1)で割った余りが1となるように適当にとる。
  5. (e,n)を開鍵とし、(d,n)を秘密鍵とする。

dをめる際には、ユークリッドの互除法を応用することで簡単にめることができる。詳しく説明すると長くなるのでここでは割愛する。eとnは開鍵なので開するものだが、p,q,dはいずれも他人に知られてはならない。

暗号化

開鍵で文xを暗号化し、暗号文yを得る方法。ここでxは1以上n未満の自然数とする。xがn以上であれば、分割して複数のn未満の数にする。自然数以外の情報を扱う場合、適当自然数に対応させてから暗号化する。

  1. xをe乗する。
  2. それをnで割った余りをyとする。

これで完成ね、簡単でしょ?

復号

秘密鍵で暗号文yを復号し、文xを得る方法。

  1. yをd乗する。
  2. それをnで割った余りをxとする。

前項でのxと本項でのxは一致する。ね、簡単で(ry

実際にやってみよう

暗号化してみよう

暗号化なら鍵と文を適当に用意すれば可だけど、見るだけでいいという人のためにひとつ例をあげよう。尚、計算を簡単にするために次の定理を用いるよ。

余りが等しい2つの数は、同じだけ累乗しても同じ数を掛けても余りは等しい」

p = 5 , q = 7 , n = 35 , e = 5 , d = 5とし、12を暗号化する。
125 = (122)2×12 = 1442×12
14435で割った余りは4なので、1442×12と42×12は余りが等しい。
42×12 = 192であり、これを35で割った余り17
よって暗号17を得る。

復号も同じ要領でやればおk。ちゃんと12になるか確かめてみよう。

解読してみよう

今度はこちらで作成した開鍵と暗号文だけを見せるので、元の数を当ててみよう。

開鍵 (e,n) = (27,123)
暗号105

正解は72でした。ちなみにdの値は3。dはこれである必要はないけど、一番小さいのがこれ。小さいほうが計算少なくて済むね。

解説(選択して読んでね)

秘密鍵がわかればよいので、ここではdの値をめることを的とする。eの値は既にわかっているので、鍵生成の方法から、(p-1)(q-1)の値がわかればdの値をめることができる。(p-1)(q-1)の値は、nを素因数分解すればめられる。

n = 123 = 3×41なので、(p-1)(q-1) = 2×40 = 80
よって、27dを80で割って1余ればよい。つまり、27d = 1,81,161,・・・のいずれか。
dは適当にひとつ選べばよいので、例えばd = 3をとればよい。d = 83等でもかまわない。 

あとは、105を3乗して123で割った余りめるだけ。

安全性

前項で解読した方は、「あれっ、簡単じゃないか?」と思った方が多いのではないだろうか。実際、nを素因数分解できればdの値をめることができ、簡単に文が得られる。一方、素因数分解を用いるよりも効率的かつ実用的な解読法は現在のところ考え出されていない。つまり、RSA暗号の解読が容易であるか困難であるかは素因数分解のそれに依存するのである。現在RSA暗号において実際に使われているnの値は300桁以上である。これを素因数分解するのに、いかに時間がかかるかおわかりだろうか。

このページを開いた方の中には、現在でも使われている暗号なだけあって、難解なことでもするのかと思った方もいらっしゃるかもしれない。しかし、暗号化や復号のやりかただけ見れば、さほど難しいことではない。最悪、累乗と余りの知識さえあれば十分である。暗号本質的価値は解読の困難さにあり、暗号そのもののわかりにくさは関係ない。また、実際に暗号を運用するにあたって、正規の方法による暗号化や復号は高速かつ容易に行う必要がある。RSA暗号はそれらを満たす、優れた暗号といえる。

証明

暗号化する前と復号した後が一致することを明する。

まず、記号を準備する。ここで扱う記号と|である。どちらも2つの整数の関係性を表す記号である。ab (mod n)は、「aとbはnで割った余りが等しい」という意味である。詳しくはの記事を参照されたし。a|bは、「aはbの約数である」という意味である。「bはaの倍数である」とも言う。ab (mod n)とn|a-bは同値である。というかこれが合同関係の定義。また、この明はフェルマーの小定理を前提とする。

文をx,暗号文をy,それを復号したものをzとする。z = xを示す。

暗号化の方法より、yxe (mod n)
復号の方法より、zyd (mod n)
よって、z(xe)dxed (mod n)

鍵生成の方法より、ed1 (mod (p-1)(q-1))
よって、(p-1)(q-1)|ed-1
p-1|(p-1)(q-1)なので、p-1|ed-1
q-1|(p-1)(q-1)なので、q-1|ed-1
よって、ed1 (mod p-1) かつ ed1 (mod q-1)

xとpが互いに素であれば、フェルマーの小定理よりxp-11 (mod p)
ed1 (mod p-1)より、ある整数kが存在し、ed = k(p-1)+1
よって、xedxk(p-1)+1(xp-1)kx1kxx (mod p)
xとpが互いに素でなければ、pは素数なのでp|x
よって、x0 (mod p)したがって、xed0 (mod p)

いずれにせよ、xedx (mod p)が成り立つ。
qに関しても同様に、xedx (mod q)
よって、p|xed-x かつ q|xed-x
pとqは互いに素なので、pq|xed-x
n = pqより、xedx (mod n)
よって、zx (mod n)
どちらも0以上n未満なので、z = x 

関連項目


【スポンサーリンク】

携帯版URL:
http://dic.nicomoba.jp/k/a/rsa%E6%9A%97%E5%8F%B7
ページ番号: 4188581 リビジョン番号: 2327924
読み:アールエスエーアンゴウ
初版作成日: 09/10/23 23:45 ◆ 最終更新日: 16/02/21 00:17
編集内容についての説明/コメント: 「安全性」を少し修正。
記事編集 / 編集履歴を閲覧

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

RSA暗号について語るスレ

15 : ななしのよっしん :2013/11/07(木) 12:54:17 ID: VqwtWl+b+2
そしてP≠NPとかどうのこうの
16 : ななしのよっしん :2014/02/04(火) 15:57:59 ID: QxG472wfZO
これで興味持ったサイモンシン暗号解読って本読むといいよ
暗号製作者と暗号読者の戦いの歴史を知れる
17 : ななしのよっしん :2014/07/18(金) 23:40:13 ID: cPlY3HMUd5
「RSA フェルマー」でググったら、他のサイトを差し置いて検索順位1位ニコニコ大百科が出てきてワロタ

レポートの参考にします。マジサンクス
18 : ななしのよっしん :2014/07/30(水) 21:09:15 ID: 0gf3QiANMD
おお、良記事。
たまにこういう専門的なのにわかりやすい記事があるから嬉しい。

電子署名の時は鍵の開と秘密を逆にするんだよな
昔勉強した時に混乱したわ。(RSA暗号に限らない話だから蛇足だけど)
19 : ななしのよっしん :2015/01/27(火) 09:55:42 ID: Dlme7IByYP
ちょっと別の記事書くために色々ググってたんだが良い記事だなおい
記事主プレミアム退会しちゃってるっぽいのが惜しまれる
20 : ななしのよっしん :2015/01/29(木) 23:12:51 ID: tbayEO4PgQ
鍵錬成の手順5
>(e,n)を開鍵とし、(d,n)を秘密鍵とする。
って
>(e,n)を開鍵とし、(d,p,q)を秘密鍵とする
の誤り??nは開鍵だし。
21 : ななしのよっしん :2015/02/02(月) 21:45:22 ID: 633HoyWSOD
>>20
復号の方法をよく見てみよう
p, q, dはいずれも秘密にしなければいけない情報だが、復号の際に必要になる情報(=秘密鍵)はdとnだけ

まあ、nはすでに開しているから秘密鍵はdだけと考えることもできるけど、どちらにしろp, qはばれるとまずい(dがわかってしまうため)情報ではあるが、そもそもp, qは鍵生成の過程で一時的に必要になるだけであって、保管しておく必要自体ないわけだ
22 : ななしのよっしん :2015/04/26(日) 12:12:18 ID: N5A2CBRgN5
記事の p = 5,q = 7,n = 35,e = 5,d = 5 のところ
中途半端にスペース入れてあって見づらいと思います。
入れるなら p = 5 , q = 7 , n = 35 , e = 5 , d = 5 で良いのでは。
23 : ななしのよっしん :2015/04/26(日) 12:15:59 ID: N5A2CBRgN5
p = 5, q = 7, n = 35, e = 5, d = 5 や
p=5, q=7, n=35, e=5, d=5 のほうが自然かな。
ともかく、イコールの前後に入れて、コンマの後に入れないのは変に思える。
24 : ななしのよっしん :2016/02/05(金) 00:37:11 ID: DhlCZGjEY9
くっ
  JASRAC許諾番号: 9011622001Y31015