RSA暗号単語

アールエスエーアンゴウ

  • 21
  • 0
掲示板をみる(27)
  • twitter
  • facebook
  • はてな
  • LINE
  • ほめる(21)
  •  
  •  
  •  
  •  
  • その他

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 

関連項目

この記事を編集する

掲示板

  • 25ななしのよっしん

    2017/05/29(月) 20:54:27 ID: rM4gVhqFIV

    素数3つだと、ダメなのは何故?別に説明見る限りでは特に問題なさそうだし、そっちの方が安全性も上がりそうだけど…

  • 26ななしのよっしん

    2017/10/05(木) 12:07:55 ID: GzjXURTEyt

    >>25
    実際に計算してみれば確かに素数3つでもよいが、2つに定着したのは安全さのためじゃないかと思う
    なぜなら、300桁の合成数の場合、素数2つの積である時、小さい方の因数は最大150桁なのに対し、素数3つだと一番小さい因数は最大100桁しかない
    つまり、素数2つの積の方が素因数分解されにくいということによるとおもう

  • 27ななしのよっしん

    2019/05/27(月) 05:27:13 ID: LYOTwCvlqQ

    pq を法としたただの合同算術って考えるとすんなり腑に落ちてしまう。(p-1)(q-1)乗が1になるのもちょっと数学やった身だとああそうだよねって思えるようになる。

    >>13 >>14
    桁の数に平方根記号をかぶせたものから素因数の二乗(専門的には方因子という)を括り出す、中高でおなじみのアレなら、素因数分解を兼ねてるから、当たらずと言えども遠からずって感じ……? 小数で計算するのは楽勝だもんね

おすすめトレンド

急上昇ワード改

最終更新:2020/09/25(金) 05:00

ほめられた記事

最終更新:2020/09/25(金) 05:00

スマホで作られた新規記事

ウォッチリストに追加しました!

すでにウォッチリストに
入っています。

OK

追加に失敗しました。

OK

追加にはログインが必要です。

           

ほめた!

すでにほめています。

すでにほめています。

ほめるを取消しました。

OK

ほめるに失敗しました。

OK

ほめるの取消しに失敗しました。

OK

ほめるにはログインが必要です。

タグ編集にはログインが必要です。

タグ編集には利用規約の同意が必要です。

TOP