【VBA】素数暗号の生成とRSA暗号の話

素数暗号

大きな素数同士の積を作ることは簡単ですが、そのようにして作られた数を逆に素因数分解して元の素数に戻すことは、コンピューターを用いても非常に時間のかかる作業になります。この事実を応用したのが素数暗号とよばれる技術です。この記事では VBA でランダム素数を生成するマクロと、ランダムな素数３個の積（暗号）を生成するマクロを作ってみます。この記事にあるマクロを動作させるには、素数を判定する PRIME関数 を先にコピーしてモジュールに貼りつけておいてください。

１個のランダム素数を生成するユーザー定義関数です。

'[VBA]ランダム素数の生成

Function RPRIME(Optional t As Integer = 2)

　　Dim m As Long

　　'指定する桁が5より大きければエラー
　　If t > 5 Then
　　　　RPRIME = CVErr(xlErrNA)
　　End If

　　RPRIME = 2

　　Randomize

　　For k = 1 To 1000
　　　　'ランダム整数を１つ選びます
　　　　m = Int(RND * 10 ^ t)
　　　　'ランダム整数が素数ならそれを採用
　　　　If PRIME(m) = 1 Then
　　　　　　RPRIME = m
　　　　　　Exit For
　　　　End If
　　Next k

End Function

オプション引数は桁の上限を指定します。何も指定せずに

=RPRIME()

と入力すると 2 桁を指定したことになります。つまり 1 ～ 99 までにある素数（7 や 59 など）を無作為に返します。

=RPRIME(3)

とすれば、1 ～ 999 までにある素数 (223 や 881 など) を無作為に返します。指定できる桁の上限は 5 としてあります。

RPRIME関数を使ってランダム素数を３個作って、その積（暗号）を返す関数です。このマクロをご使用になる場合は、上にある RPRIME関数を先にコピーしてください。

'[VBA]素数暗号生成関数
Function PRIME_PRODUCT() As Long
　　Dim m1 As Long
　　Dim m2 As Long
　　Dim m3 As Long
　　m1 = RPRIME(3)
　　m2 = RPRIME(3)
　　m3 = RPRIME(3)
　　PRIMEPRODUCT = m1 * m2 * m3
End Function

素因数は 3 桁の数字としてあります。すなわち最大で 9 桁の数値が返されます。

RSA暗号

素因数分解プログラムはこちらにあります が、3 桁素数を 3 つ掛け合わせた数字の素因数分解であっても、相当にマシンパワーがないと、かなり時間がかかります。冒頭でも少し触れましたが、こうした素因数分解の困難さを利用してパスワードなどを保護する技術をRSA暗号とよびます。

ランダム素数を用意して積をつくるのは簡単ですが、その逆の素因数分解はとても難しいのです。しかも現在使われているのは 2 つの巨大素数を掛け合わせて 300 桁以上（！）という途方もない数値です。ここまで大きくしなくてもよさそうな気もしますが、コンピュータの演算能力の進歩を警戒して、大きめの数字にして余裕をもたせてあるのです。ただし、万能にも思えるこの暗号技術も、近年急ピッチで開発の進む量子コンピュータであれば簡単に破ってしまうと言われています。ただ、そうした場合にも対抗できる新型 RSA の研究も進められているそうで … まあ、技術というのはいつの時代も、いたちごっこなわけです。