RSAの由来
いきなりRSAといっても何だかわかりませんね。
現代の暗号にもっとも大きな影響を与えた暗号システムのことで、このシステムを開発した3人(Rivest, Shamir, Adleman)の頭文字をとって名付けられたものです。
RSAと素数
このシステム（RSA暗号システム, RSA cryptosystem）において、「素数」はきわめて重要な役割を担います。
RSA暗号は、巨大な数が簡単に素因数分解できないことを利用したものです。
素数が現代のセキュリティを守っているといわれる所以です。
さて、どのように現代セキュリティ（暗号化）に素数が関わるのでしょうか？
たとえば、適当に２つの素数を選んでみます。
$p=99,119$、 $q=99,991$とでもしましょう。
ここで$p×q$を計算してみます。すると、$pq=9,911,007,929$が得られます。
われわれは、$9,911,007,929$という数字が$p$と$q$を掛け合わせて出てきたことを知っていますが、いきなり$9,911,007,929$という数字が出てきたら、これが素数なのか合成数なのかわかりません。
そこで、コンピューターの登場。
さて、この数字が素数なのか、合成数なのかを調べるには、基本的にエラトステネスのふるいを使ったアルゴリズムを使うのが最も効率的ですので、まず、$9,911,007,929$の平方根を求めます。
電卓をたたくと$99,554.04…$ですから、$99,554$までの素数を見つけて、その倍数を除外すればいいことになります。
$9,911,007,929$という数字は大体$10^{10}$に近い数字ですから、コンピュータでもかなり時間がかかることがわかります。
セキュリティに応用する場合には、$10^{10}$などという遠慮した大きさの数字ではなく$10^{308}$などというとてつもなく大きな数字を使って、$p$と$q$の２つを特定されにくくするわけです。
-
脳ブロックFF（プラパズルNo.600）
記事がありません
Wrote this article この記事を書いた人
