【セキュリティ基礎】オイラーの定理と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の場合)
\begin{eqnarray*}
a^{(p-1)(q-1)} ≡ 1 (mod N)
\end{eqnarray*}

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

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

POINTA ≡ B ( modN )は A – B がnの倍数となる意味になる!!

一例としてp=5,q=7と仮定するとN=5*7=35、pとqの約数を持たないaを2と仮定。
\begin{eqnarray*}
a^{(p-1)(q-1)} – 1 = 2^{24} – 1 = 16777215 = 479349 \times 35
\end{eqnarray*}
35の倍数になっているので最終的にはこうなります。
\begin{eqnarray*}
a^{(5-1)(7-1)} ≡ 1 (mod 35)
\end{eqnarray*}
高校数学を完全に忘れている身としては、ここまで辿り着くのも四苦八苦(;^_^

RSA暗号

オイラーの定理の両辺をk乗して両辺aに掛けると…
\begin{eqnarray*}
a^{k(p-1)(q-1)+1} ≡ a (mod N)
\end{eqnarray*}
左辺の指数部分に着目。
\begin{eqnarray*}
ed = k(p-1)(q-1) + 1
\end{eqnarray*}
を満たすeとdを選べれば、(e,N)を閉める鍵、(d,N)を開ける鍵に指定可能。

メッセージMに対して、暗号文Cを以下のように定義。
\begin{eqnarray*}
C ≡ M^e (mod N)
\end{eqnarray*}
暗号文Cをd乗すれば復号が可能。
\begin{eqnarray*}
C^d ≡ (M^e)^d ≡ M^{ed} ≡ M^{k(p-1)(q-1) + 1} ≡ M (mod N)
\end{eqnarray*}

ではp=11,q=17,N=pq=187,e=3,d=107,(p-1)(q-1)=(11-1)(17-1)=160と仮定すると…
\begin{eqnarray*}
3 \times 107 – 2 \times 160 = 1
\end{eqnarray*}
メッセージMを19とすると暗号文はこうなる。
\begin{eqnarray*}
C = 19^3\,mod\,187 = 6859\,mod\,187 = 127
\end{eqnarray*}
これを復号すると…
\begin{eqnarray*}
C^d\,mod\,N = 127^{107}\,mod\,187
\end{eqnarray*}
この巨大な数値を187で余りは19になり復号に成功。

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

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

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

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

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

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

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