ＣＳ白狐村塾（第１話-その2） 量子コンピューターによりRSA暗号は終焉するのか？

今回はその1に続いて、暗号化方式のお話です。まだ、ＣＳ白狐村塾（第１話）
サイバーセキュリティに必須の技術、詳細に解説！　その1　をお読みでないかたは、まずはこちらをお読みください。

RSA暗号の終焉、量子コンピューターで破らるのか？

公開鍵から、そのペアの秘密鍵を作れてしまうと「おしまい」です。暗号が突破されてしまったということになりますから。
　
従って、それがどの程度難しいのか？　ということが非常に重要です。2048bitsのRSA暗号は、スーパーコンピューターを含むノイマン型コンピューターでは計算不能と言われています。2030年ぐらいに登場するスーパーコンピューターを数年使って解けるのは786bits辺りだと言われています。

しかし、量子デジタルコンピュータが実現され、Shor Algorithmを適用すれば、2048bitsのRSA暗号も数日で解けると言われています。

と言っても、現時点でみなさんが気に病む必要はありません。Shor Algorithmを扱うには少なくとも１億量子ビット（qubit）が必要です。しかし、実稼働しているものは数10qubitで、IBMが2023年1000qubit超え、2026年に百万qubitを目指すというロードマップを掲げているというのが現状です。
　
また、量子コンピュータが実用化されれば「格子暗号」を効率的に扱えるようになり、実用的な暗号の強度も飛躍的に向上します。守る技術が現状ままで、破る技術だけが進化することはありません。要するに、守ることと、それを破ることは常に「イタチごっこ」ということです（暗号に限らず）。

RSA暗号 その数学的な意味

さあ、いよいよRSA暗号の仕組みです。これを理解するには数学的な知識が必要になりますし、本質的な理解をするためには整数論に通じる必要があります。

ということで、絶対に眠くなるパターンですので、深入りしたい奇特な方は別として、「なんとなく」こんな感じなんだ、とうことを理解してもらえればと思います。

「奇特な方」は、RFC 3447やRFC 2315 を参照してください（英語が苦手な場合は、Google先生などに助けてもらってください）。
　➣RFC3447：https://datatracker.ietf.org/doc/html/rfc3447
　➣RFC2315：https://datatracker.ietf.org/doc/html/rfc2315

レシピ

では、実際にペア鍵（秘密鍵と公開鍵）を作ってみましょう。

大きな素数を２つ（p、q）準備します。素数とは、自分と1しか約数を持たない整数です（小学校で学んだ、公約数、公倍数を思い出してください）。

　たとえば..
　12 は 12, 6, 4, 3, 2, 1 と６つの約数として持ちます。12 は素数ではありません。
　13 は 13, 1 しか約数がありません。13 は素数です。

ちなみに、素数は無限にあることが証明されています。証明方法はいくつかあります。興味がある方は、ユークリッドによる証明（背理法）、オイラーによる証明（背理法）、フェルマー数を用いた証明、サイダックの証明などを調べてみてください。

特に、サイダックの証明は、21世紀になってから発見された、非常に美しい証明方法です。

　N と N ＋ １ は 互いに素
　従って、N’ = N ( N + 1 ) は、異なる素因数を２個以上持つ
　同様に、N” = N’ ( N’ + 1 ) は、異なる素因数を３個以上持つ
　この繰り返しで、異なる素因数を持つ整数は無限に存在し、結果、素数は無限に存在する。

素晴らしいですね。整数論の美しさを感じられる一コマです。

　分かり辛い場合は、試してみましょう。
　N = 2 でスタートしてみます。
　N’ = 2 x 3 で、新たな素数 3 が得られます。
　N” = 6 x 7 = 2 x 3 x 7 で、新たな素数 7 が得られます。
　N”’ = 42 x 43 = 2 x 3 x 7 x 43 で、新たな素数 43 が得られます。
　　　　：
　　　　：

鍵の生成にいくらでも大きな素数を割り当てることが可能なので、我々は安心してペア鍵のbit数を増やすことが可能ということです。

素数の説明が長くなってしまいましたが、鍵を作る話でしたね。数式(*1) が出てきますが、お付き合いください。

n=p∙qとします。
(p-1)(q-1)と互いに素な整数k_eを選びます。
k_e∙k_d≡1∙mod((p-1)(q-1))となる整数k_dを選びます。
mod( )は剰余（割った余り）を求める関数です。
0≤k_d≤(p-1)(q-1)＊＊＊とするとk_dが 一意に定まることは、カーマイケルの定理によって証明されています。
nとk_eを公開鍵とします。k_dを含む情報を秘密鍵とします。

以上、単純な演算で（＝高速に）処理可能です。単純な演算で求められることは実用上重要です。
　鍵ができたので、次はデータの暗号化です。
　データをｍとします。 ただし、0≤m≤nとします。

暗号化したデータ C は、公開鍵を用いて下記で求めます。
C= m^k_e・mod(n)

次は、復号化です。
m= C^k_d・mod(n)
これを計算すると、あら不思議。元のデータmが得られます。

Cとn、k_eが分かったとしても、k_dが分からなければ、mを得ることは（現代の CPUにおける現実的な処理時間では）難しい、ということで安全性を確保しています。

普通の言葉で書くと「（例えば 1024bits 規模の）大きな整数の素因数分解は非常に難しいということを利用して暗号の安全性を確保しているということです。

なぜ上記の演算で、復号が可能なのかは、フェルマーの小定理を用いた証明が有名ですので、みなさんで証明を試してみてください（嘘です、ネット検索して、分かった気分になってください。いずれにしても放り投げ）。 さて、登場人物が揃ったところ、秘密鍵の構成を見てみましょう（下記は、Linux系のコマンドラインです。OpenSSLというコマンドを用いています）。

$ openssl rsa -text -noout -in sample.key    
Private-Key: (256 bit)
modulus:
    00:d3:f1:68:70:0c:29:c8:1d:45:92:42:0a:9f:6e:
    05:da:b4:b5:1e:70:33:b4:0b:2a:00:4f:96:74:9a:
    43:eb:19
publicExponent: 65537 (0x10001)
privateExponent:
    00:cd:aa:79:5a:21:b3:79:c9:4d:f5:bb:b8:6b:35:
    6c:df:25:e0:08:bf:79:65:82:88:47:ee:66:71:3d:
    a2:83:31
prime1:
    00:f4:38:52:be:37:f2:72:16:93:e4:80:0a:1c:37:
    60:ab
prime2:
    00:de:2a:85:97:36:bf:aa:81:b9:d7:1e:b9:d3:29:
    cb:4b
exponent1:
    00:a1:1a:fa:b2:93:33:b3:c1:63:24:8c:b6:9e:b0:
    85:6b
exponent2:
    04:ab:dc:37:3b:bd:77:f6:56:54:01:9f:62:a3:44:
    55
coefficient:
    00:aa:42:14:ff:24:2f:12:a9:5e:c5:cd:70:78:65:
    c5:79

ちなみに、それぞれ、下記の通りです。

modulus:    n=p∙q
publicExponent:   k_e=65537=0_x10001　※ これは、通常「お決まり」です
privateExponent:   k_d=e^-1∙mod(LCM(p-1,q-1))　※ LCM は 最小公倍数を求める演算
prime1:    p
prime2:    q
exponent1:    k_d∙mode(p-1)
exponent2:    k_d∙mode(q-1)
coefficient:    q^-1∙mod(p)

確かに、k_dが含まれていますね。これがバレてはだめですね。また、p、q もバレると、k_dを簡単に計算できてしまうので、これも内緒です。だから「秘密」鍵なのです。

ついでに、復号時の計算に必要なデータも予め計算して秘密鍵に含めておくので、公開鍵と比較して秘密鍵は長くなっているということになります。

今回は、サイバーセキュリティを支える重要な技術である暗号化、その中で RSA暗号に関して説明しました。初回なので、説明の深さなど、いろいろと手探りでした。可能でしたら皆さまからのコメントなども頂ければ幸いです。
次回は、楕円曲線暗号、ストリーム暗号など、現在多用されている暗号化方式に関して触れたいと思います。

---

(*1) 数式

今回、数式はWordの機能を用いて書いてみました。UNIXやLinux上では「eqn」という数式を記述するツールがあるので、以前はそれを使っていましたが、Wordの方が直ぐに表示に反映できて便利ですね。

---

サイバーセキュリティ白狐村塾話は、新たなお話が公開されたときにメールマガジンにてご案内致します。是非JAPANSecuritySummit Updateのメールマガジンにご登録ください。
メールマガジンの登録はこちらからお願いします。