暗号の数理－RSA暗号のしくみ－

暗号の仕組み

現代社会では、様々なケースで暗号が使われています。以前少し触れましたが、ネットでのクレジットカード番号などの暗号化は、その基本は素数です。ある数が、素数なのか素数でないのかの判断をコンピューターでやっているわけです。

たとえば、よくない例として、カード番号が、36282525 であるとします。これをカード会社に送ることになるわけですが、各数字を１だけずらし、47393636　を送ったとします。数字を１ずらした事を知らなければ、これは、他人に知られることはありませんが、この方法は非常に危険なものだと言わざるを得ません。１だけずらすと言う方法を知られてしまったり、コンピューターでためせば、あっという間に正しいクレジット番号が分かってしまいます。

RSA暗号の仕組み

そこで、カード番号を暗号化する方法であるRSA暗号を紹介しましょう。

1.RSA暗号では、公開鍵を使って暗号化します。この方法では素数をつかうのですが、うえに挙げた様な暗号を読み取られる可能性はほとんどありません。RSA暗号では、公開鍵として、11111111111　などの大きな数を利用者に送ります。これは、誰でも見ることができます。子の暗号は、11111111111＝21649ｘ513249という素因数分解できるということを知っている人だけが、暗号を解く事ができるのです。

具体的なRSA暗号

少し簡単な例で説明しましょう。公開鍵を（55と3）としましょう。55＝5ｘ11です。この公開鍵をウエブサイトから、受け取ることになります。

公開鍵を使って、カード番号を暗号化します。簡単のためにクレジット番号を17だとしましょう。ユーザーは、公開鍵の55と3を使って次の計算をします。

ユーザーは、17を３乗し、55で割ったあまりを求めます。
\(17^3≡18　(mod55）\)ですから余りは、18となります。この１８がRSA暗号の暗号数字です。

公開鍵を使って暗号を解くのはほぼ不可能

第３者が、公開鍵で暗号を解くには、「３乗して55で割った余りが１８になる数」を１つずつ探して試していくしかありません。

ここでは、小さな数を使ったので、解けますが、実際の公開鍵は非常に大きな数字ですから、上の方法での計算では、コンピューターを使ったとしても、現実的にカード番号を計算することはできません。

RSA暗号の解き方

公開鍵を公開しているウエブサイトだけが、秘密鍵を知っており、それは、うえの例では、55の２つの約数5と11です。これがあれば、簡単にカード番号をわかります。

11-1と5-1の10と4の最小公倍数を求めます。つまり、２０です。
次に、Aｘ3÷20＝B余り１となるAを求めると、A=7となります。カード番号は、
\(18^7＝612220032\)を求め、公開鍵５５で割ればカード番号がもとめられます。

つまり、612220032÷55＝11131273余り17　となりますから、求めるカード番号は、１７となり、復元されたことになります。

いずれにしても、公開鍵は大きな素数の積ですから、極めて大きな数の素因数分解ができなければ、現実的な時間でカード番号は求まらないことになります。

ただし、素数の全貌が明白になったら、この手は使えないと言う事になってしまい、素数定理に関連するリーマン予想は、暗号にとっても極めて重要だといえると思います。