[VBA] 暗号数字の生成とRSA暗号の話

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

ランダム(無作為)な素数を生成するマクロ

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

'[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
    'ランダム整数を1つ選びます
    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関数を使ってランダム素数を3個作って、その積(合成数)を返す関数です。このマクロをご使用になる場合は、上にある 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 の研究も進められているそうで … まあ、技術というのはいつの時代も、いたちごっこなわけです。

コメント