【セキュリティ基礎】オイラーの定理とRSA暗号の仕組みを確認

公開鍵暗号方式は共通鍵暗号方式と異なり、閉める鍵と開ける鍵が異なる暗号系。

閉める鍵は一般公開されているので 公開鍵、開ける鍵は 秘密鍵 と呼ばれます。

公開鍵と秘密鍵には数学的な関係性があり、理論的に公開鍵から秘密鍵を計算することが可能ですが、現在では公開鍵から秘密鍵を知るには多大な時間を要するので、実質的に不可能と言われます。

POINT計算量が多すぎて実質解読不可能な性質を「計算量的安全性」と呼ぶ!!

公開鍵暗号方式は一方向性(順方向の計算は簡単でも逆方向の計算は困難)である必要があり、例えば $1061*3823$ の掛け算(答えは4056203)は簡単に可能ですが、逆に4056203の因数分解は人にとって非常に困難でコンピュータでさえ容易ではありません。

この性質がまさに一方向性であり、計算量の多さを逆手に取ったのが公開鍵暗号式。

ちなみに本書ではRSA-768と呼ばれるチャレンジナンバーが紹介されており、2000台(2.2GHzのAMD Opteron CPU)のPCで約3年かかったそうなので、一般人のPCでは到底無理ですね。

オイラーの定理

RSAの理解に必要な初等整数論の基本定理の一つオイラーの定理。

オイラーの定理で素数p、q、そのp、qを約数に持たない整数aに対し$N=pq$の場合、以下が成立。

$a^{(p-1)(q-1)} ≡ 1 (mod N)$

高校数学をバッサリ忘れてるので、ちょっと何言ってるか分からないんですが、数学の≡は合同で、modは剰余演算、さらにAとBのNで割った余りは等しいことを $A≡B(mod N)$ と定義。

例えば12と7を5で割った余りは2なので等しくなり、これを $12≡7mod5$ と記述。

一例として $p=5$,$q=7$ と仮定すると $N=5*7=35$ 、pとqの約数を持たないaを2と仮定。

$a^{(p-1)(q-1)} – 1 = 2^{24} – 1 = 16777215 = 479349 \times 35$

35の倍数になっているので最終的にはこうなります。

$a^{(5-1)(7-1)} ≡ 1 (mod 35)$

高校数学を完全に忘れている身としては、ここまで辿り着くのも四苦八苦(;^_^

RSA暗号

オイラーの定理の両辺をk乗して両辺aに掛けると…

$a^{k(p-1)(q-1)+1} ≡ a (mod N)$

左辺の指数部分に着目。

$ed = k(p-1)(q-1) + 1$

を満たすeとdを選べれば、(e,N)を閉める鍵、(d,N)を開ける鍵に指定可能。

メッセージMに対して、暗号文Cを以下のように定義。

$C ≡ M^e (mod N)$

暗号文Cをd乗すれば復号が可能。

$C^d ≡ (M^e)^d ≡ M^{ed} ≡ M^{k(p-1)(q-1) + 1} ≡ M (mod N)$

$p=11$ , $q=17$ , $N=pq=187$ , $e=3$ , $d=107$ , $(p-1)(q-1)=(11-1)(17-1)=160$ と仮定。

$3 \times 107 – 2 \times 160 = 1$

メッセージMを19とすると暗号文はこうなる。

$C = 19^3\,mod\,187 = 6859\,mod\,187 = 127$

これを復号すると…

$C^d\,mod\,N = 127^{107}\,mod\,187$

この巨大な数値を187で余りは19になり復号に成功。

RSA暗号では1024bit(10進数で309桁)、2048bit(10進数で617桁)といった数字を扱っており、(観測可能な)宇宙の原子の総数が10進数で80桁〜100桁らしいので途方もない桁数…まあ肌感覚で解読困難なことが何となく理解ですが、これ最初に思いついた人はホント頭良いですよね(;^_^

素数という名のライフル弾

RSA暗号は2組の素数で秘密鍵と公開鍵を作るため、肝心の素数の組み合わせが重要。

ユークリッドが素数は無限に存在することを証明したらしいですが、18世紀頃に素数がどのくらいあるか定量的に予想する素数定理が生まれ、それによれば1024bitの素数は0.14%しか無いそうです。

とはいえ、ブルートフォースで素数の同定が出来るほど少ない訳ではない模様。

ちなみに暗号学の世界では素数を見つける実用的な技術(ミラー・ラビンテスト)があります。

興味のある方はググってみてくださいmm