MathematicaでRSA暗号を実行してみる

◼
  • 執筆者：技術部・降旗
    • ◼
  • 使用したバージョン：Mathematica14.2
    • ◼
  • 使用した主な関数：
    PowerMod
    ,
    ModularInverse
    ,
    FactorInteger
    ,
    GenerateAsymmetricKeyPair
    ,
    Encrypt
    ,
    Decrypt

    • はじめに

    この時期になるとスタジオ地図・細田守監督作品『サマーウォーズ』(2009)がよく話題に上ります。今年も8月1日に「金曜ロードショー」で放送されました。
    劇中では主人公が暗号を解読するシーンが登場しており、この暗号が何の暗号なのかは触れられていませんが、「RSA暗号」が有力ではないかとされています。
    今回はこのRSA暗号をMathematicaを使って実装し、実際に暗号を解読するところまで試してみたいと思います。

    RSA暗号とは

    RSA暗号については以下の通りです。
    RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号の一つである。暗号とデジタル署名を実現できる方式として最初に公開されたものである。
    (引用元：Wikipedia https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7 )
    具体的には次のような手順で暗号化と復号を行います。

    鍵の生成

    1
    .
    異なる2つの大きな素数
    p
    ,
    q
    を選ぶ
    2
    .
    n=pq
    を計算 (これが公開鍵の一部となる)
    3
    .
    オイラーのφ関数
    φ(n)=(p-1)(q-1)
    を計算
    4
    .
    1<e<φ(n)
    かつ
    gcd(e,φ(n))=1
    となる
    e
    を選ぶ (公開鍵)
    5
    .
    ed≡1modφ(n)
    となる
    d
    を求める (秘密鍵)

    暗号化

    平文
    m
    を暗号化：
    c≡
    e
    m
    modn

    復号

    暗号文
    c
    を復号：
    m≡
    d
    c
    modn

    簡単な例の実装

    鍵の生成

    まずは鍵の生成を行います。
    安全性を保つには
    p
    ,
    q
    に大きな素数を選ばなければなりませんが、ここでは動きを見るために小さな素数を選択します。
    In[]:=
    p=61;​​q=53;
    素数であることを確かめるにはPrimeQを利用できます。
    In[]:=
    PrimeQ[{61,53}]
    Out[]=
    {True,True}
    またPrimeを使ってn番目の素数を求めることもできます。
    In[]:=
    Prime[16]
    Out[]=
    53
    続いてnとφを求めます。
    In[]:=
    n=p*q
    Out[]=
    3233
    In[]:=
    phi=(p-1)*(q-1)
    Out[]=
    3120
    次にeを選びます。よく使われる値は3と65537のようですが、今回はこれらの値は使わずに17と設定しておきます。
    In[]:=
    e=17;
    eとφが互いに素であることはGCDを使って確認できます。
    In[]:=
    GCD[e,phi]
    Out[]=
    1
    最後にdを求めます。MathematicaではPowerModもしくはModularInverseを使うことで求めることが可能です。
    In[]:=
    d=PowerMod[e,-1,phi]
    Out[]=
    2753
    In[]:=
    ModularInverse[e,phi]
    Out[]=
    2753
    これで公開鍵n=3233,e=17と秘密鍵d=2753の準備ができました。これを使って暗号化と復号を試します。

    暗号化

    公開鍵を使って1から10の値のリストを暗号化してみます。
    In[]:=
    m=Range[10](*平文*)
    Out[]=
    {1,2,3,4,5,6,7,8,9,10}
    In[]:=
    c=PowerMod[m,e,n]
    Out[]=
    {1,1752,1211,1387,3086,824,2369,2041,1972,1096}
    1は変わっていませんが、それ以外の値は大きく変わったことが確認できます。

    復号

    暗号化した数値のリストを秘密鍵を使って復号してみます。
    In[]:=
    PowerMod[c,d,n]
    Out[]=
    {1,2,3,4,5,6,7,8,9,10}
    正しく復号できることが確認できました。
    なお、今回はp,qに小さな素数を使いましたので、FactorIntegerを使って公開鍵nからこの値をすぐに求めることが可能であり、安全性はありません。
    In[]:=
    FactorInteger[n]
    Out[]=
    {{53,1},{61,1}}

    文字列の暗号化と復号について

    上の例では数値のリストを暗号化しましたが、一般的には文字列を暗号化したい場合が多いと思います。
    ToCharacterCodeを使うことで文字列を数値(文字コード)のリストに変換できます。
    In[]:=
    m=ToCharacterCode["ヒューリンクス","ShiftJIS"]
    Out[]=
    {131,113,131,133,129,91,131,138,131,147,131,78,131,88}
    この数値に対して暗号化と復号を試してみます。
    In[]:=
    c=PowerMod[m,e,n]
    Out[]=
    {2582,1627,2582,2085,1454,1421,2582,561,2582,1662,2582,3165,2582,1345}
    In[]:=
    PowerMod[c,d,n]
    Out[]=
    {131,113,131,133,129,91,131,138,131,147,131,78,131,88}
    文字コードから文字列の変換にはFromCharacterCodeが使えます。
    In[]:=
    FromCharacterCode[%,"ShiftJIS"]
    Out[]=
    ヒューリンクス
    こちらも正しく復号できることが確認できました。

    鍵の桁数について

    最近の鍵は2048bit以上、桁数にすると600桁を超える値が使われているそうです。
    試しにどれくらいの長さだと素因数を求める難しくなってくるのか簡単なテストを行ってみました。
    Primeを使ってa番目の素数とa+1番目の素数を求め、その二つの数を使ってnを計算し、その結果をFactorIntegerに渡して素数を求める関数を定義して実行してみます。
    In[]:=
    f[a_Integer]:=Module[{p,q,length,n,time,result},​​p=Prime[a];​​q=Prime[a+1];​​n=p*q;​​length=IntegerLength[n];​​{time,result}=AbsoluteTiming[FactorInteger[n]];​​Print["p:"<>ToString[p]];​​Print["q:"<>ToString[q]];​​Print["桁数:"<>ToString[length]<>"桁"];​​Print["time:"<>ToString[time]<>"秒"];​​Print["素因数:"<>ToString[result]];​​]
    まず、aを3000とすると、7912、3001番目の素数は7927となり、nは8桁の数となることが確認できます。なお、桁数はIntegerLengthを使うことで確認できます。そしてFactorIntegerでその素因数を求めてみると、ほぼ0秒で計算できていることが分かります。
    In[]:=
    f[1000]
    p:7919
    q:7927
    桁数:8桁
    time:0.000011秒
    素因数:{{7919, 1}, {7927, 1}}
    次にa=1,000,000,000とすると、桁数は21桁になりますが、こちらもすぐに結果が返されることが確認できます。
    In[]:=
    f[1000000000]
    p:22801763489
    q:22801763513
    桁数:21桁
    time:0.0006038秒
    さらにaの桁数を増やしてa=100,000,000,000,000,000とすると、実行に少し時間がかかるようになります。
    しかし、素因数を求める箇所は0.05秒程しかかかかっていませんので、素因数ではなく素数を求めるところに時間がかかっているようです。
    さらにaの桁数を１つ増やしたところ、Prime関数が値を返さなくなりました。
    Primeについて少し試してしてみたところ、Primeでは21京6300兆番目を超える素数は求められないようです。
    確認できた素数を用いて計算を実行してみると、秘密鍵の桁数は38桁で、素因数を求める時間は0.066秒でした。この桁数でもすぐに求められ、まだ安全性は無いようです。
    このテストでは素因数分解がどの程度の桁数から難しくなるのかを確認する前に、素数を求めるところで躓くという結果になりました。

    組込み関数を使用する

    ここまでRSA暗号を定義に沿って実装してみましたが、Mathematicaには組込みの関数も用意されています。
    まず秘密鍵と公開鍵を生成するための関数にGenerateAsymmetricKeyPairがあります。
    暗号化にはEncryptが使えます。
    なお、Encryptは入力として数値のリストだけでなくメモリ効率の良いバイト配列を使用することができます。
    そのため、文字列を数値に変換する際にはStringToByteArrayが役に立ちます。
    バイト配列に含まれる値を確認するにはNormalが利用できます。
    そして復号にはDecryptが、バイト配列から文字列に変換するにはByteArrayToStringが使えます。
    なお、生成された公開鍵の値は”PublicHexString”と指定することで確認が可能です。
    これをFromDigitsを使って10進数に変換してみると、600桁を超えていることが確認できます。
    この値から素因数を求めてみようと思いましたが、確認できた範囲では結果は返されませんでした。(もしすぐに結果が返ってきたら、それはそれで問題ですが。)
    評価メニュー > 評価を放棄を選択すると、計算を中断できます。

    おわりに

    今回はRSA暗号の実装方法と、組込み関数を使って実行する方法を見てきました。
    次回『サマーウォーズ』が放送されるときに意識してみると、印象が少し違って見えてくるかもしれません。