RSA暗号

問１）RSA暗号が一方向性関数を用いていることを説明せよ。

問２）2021年現在解読されているRSA素因数分解の２進数最大ビット数は？

問３）ビットコイン（256ビット楕円曲線暗号）の暗号強度はRSA暗号の２進数何ビット相当か？

暗号資産を保有するなら、RSA暗号とは何か、楕円曲線暗号とは何か、それはどれくらい解読するのが難しいのか、何となく知っていた方が良いですね。上記の質問にも答えられるようにした方が良いでしょう。何しろ、暗号通貨の価値を守るのは、政府でも企業でもなく、暗号強度だけなのです。

答１）RSA暗号は、ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの３名の頭文字を取った暗号で、合成数の素因数分解が困難であることを用いて公開鍵暗号を実装する仕組みである。

例えばRSA100は10進数で100桁の合成数であるが、素因数分解は次の内容である。

RSA-100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
= 37975227936943673922808872755445627854565536638199
× 40094690950920881030683735292761468389214899724061

上の合成数から下の二つの素数を見つけ出すには多くの計算資源（athlon64/2.2GHzで4時間相当）が必要であるが、下の二つの素数を掛け算して上の合成数を得るのは容易である。

RSA暗号では、ふたつの素数$$p,q$$を乗算した合成数$$pq$$を公開鍵として、暗号化と複号化を行うことができる。

オイラーの定理（pとqを素数とし、pやqを約数に持たない整数をaとする）a=2とするのが最も計算量が少なく検算できる。

$$a^{(p-1)(q-1)} \equiv 1\pmod{pq}$$

この両辺をk乗してからaを乗すると、

$$a^{k(p-1)(q-1)+1}\equiv a \pmod{pq}$$

ここで、$$ed=k(p-1)(q-1)+1$$となるようなedがあれば、メッセージａをe乗してpqで割った余りを得れば暗号化でき、それをd乗してpqの余りを取れば復号できることになります。RSA暗号の暗号強度は素数p,qの大きさによって決まります。なるべく大きな素数を利用することによりスパコンでも解読できない暗号強度を得ることができます。2021年現在では、1024bit（10進数で309桁）以上の素数が使われています。

答２）829bit （2020年2月に Fabrice Boudotらによって因数分解されたRSA250）ちなみに10進数260桁（862ビット RSA260）は未解読。

https://en.wikipedia.org/wiki/RSA_numbers

答３）3072bit（128ビットの総当たり攻撃に耐える安全性）

https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf

どうでしょうか。結局のところ、「政府発行通貨」と「暗号強度」のどちらを信用するかという問題に全ての論点が繋がっているわけです。現代民主制や政党政治、それに資本主義の定期的な景気循環に左右される法定通貨と、数学的に見積もられた計算量に根拠付けられた暗号資産とどちらを信用するのか、という問題です。政府が信用できないのは新聞を読んでいれば分かりますが、暗号強度がどれくらいなのかは数学の勉強をしないと分かりません。これからの時代は数学の勉強が重要だということですね。

※参考記事

Diffie-Hellman鍵合意

※参考書籍