1. はじめに
パスワードとは，正規の利用者かどうかを認証するための文字列である．利用者本人だけが知っている合言葉を利用することで本人確認を行うことができ，一般的に，長ければ長いほど安全である．しかし，長すぎるパスワードは覚えづらいので，パスワードの使いまわしの原因になり，安全性が低下してしまうことがある．
パスワードの安全性の定式化について書かれた文書には，アメリカ国防総省の文書[1]がある．それによると，パスワードが有効期限までに推測される確率を$P$，有効期限までにパスワードを推測できる回数を$G$，生成できるパスワードの総数を$S$，パスワードの有効期間を$L$，単位時間あたりの推測できるパスワードの数を$R$，パスワードに使用可能な文字の数を$A$，パスワードの長さを$M$と置くと，$P=G/S$,$G=LR$,$S=A^M$のように定式化できる．しかし，コンピューターの技術的進歩が考慮されておらず，組み合わせの計算が単純であるため，安全性の将来予測ができていない．そこで，本記事では，2つの要素に注目してパスワードの安全性について考えた．1つ目は，スーパーコンピューターの処理速度の指数関数的増加である．2つ目は，ファイルや，Googleアカウント・Microsoftアカウントなどのサービスに設定するパスワード作成ルールである．また，それらを用いて，パスワードのどのような運用がよいか考えた．
本記事の構成は以下の通りである．2章では，パスワードの安全性を計算するための条件を説明した．3章では，パスワードがどのようなときにどの程度安全といえるか定式化した．4章では，実際にパスワードを管理するときに，3章で作成した数理モデルをどう活用するか説明した．5章では，4章の内容をもとに，コンピューターに計算させる内容を示した．6章では，5章の計算結果を示した．7章では，6章の計算結果について考察した．8章では，本記事の成果と課題を示した．
2. 条件
ここでは，パスワードの安全性を計算するための条件を説明する．
図 1のように，パスワードの利用者(ユーザー)は何らかのサービス・ファイルを利用し，設定時に要求される作成ルールを満たした1つのパスワードを設定する．パスワードの攻撃者(ハッカー)は，パスワードのハッシュ値をいつでも手に入れることができ，そのハッシュ値のもととなったパスワードを推測する．推測する方法は，パスワード作成ルール通りの文字列で，すべての組み合わせを試す総当たり攻撃を文字数の少ないものから仕掛けるというものである．
また，攻撃に使用するコンピューターを各時代で処理速度が最も速いスーパーコンピューターとする．パスワードの暗号化方式はサービスやファイルによって異なるが，使用する暗号学的ハッシュ関数をSHA-256と仮定する．異なる2つのパスワードのハッシュ値の衝突を考慮しない．
暗号学的ハッシュ関数は，任意の長さの入力をハッシュ化し，固定長のハッシュ値にして出力する関数であり，出力から入力を予想することが困難である．そのため，攻撃者は，ハッシュ値がどの文字列に一致するかを一つ一つ確認しなければならない．
図 1条件
3. 定式化
本章では，パスワードがどのようなときにどの程度安全といえるか定式化する．
日時にはすべて1899年12月31日0時00分00秒からの経過日数を用いた．また，人間の寿命の限界の目安を43829.1日(グレゴリオ暦で120年)とした．
設定日時$s[日]$から有効期限$t[日]$までにパスワードを推測できる回数を$G[\rm{hash}]$，作成ルールを満たした$M$文字以下のパスワードの総数を$T_M[\rm{hash}]$，人間の寿命の限界の目安を$l=43829.1日$，$l$の間$M$文字のパスワードが推測されない確率を$Q$，パスワードの有効期間を\begin{eqnarray}L=t-s[日]\end{eqnarray}とし，$s<t$，$L \leqq l$と置く．ここで，$\rm{hash}$はハッシュ関数の計算回数の単位である．$l$は，$s$から$t$までの時間の$l/L$倍であるから，\begin{eqnarray}Q=\begin{cases}1 & (0 \leqq G \leqq T_{M-1} < T_M) \\ \left(\displaystyle\frac{T_{M}-G}{T_{M}-T_{M-1}}\right)^\frac{l}{L} & (0 \leqq T_{M-1} < G < T_M) \\ 0 & \left((0 = T_{M-1} = T_M)または(0 \leqq T_{M-1} < T_M \leqq G)\right)\end{cases}\end{eqnarray}とする数理モデルが考えられる．
3.1. 設定日時$s$から有効期限$t$までにパスワードを推測できる回数$G$
TOP500[2]とは，年2回開催される，スーパーコンピューターの演算速度を競うプロジェクトである．そのデータによると，時間の経過とともに倍精度浮動小数点演算の処理速度が指数関数的に増大することが分かる．
2つのパラメータ$a, b$について$a>0, b>0$として，日時$x[日]$での倍精度浮動小数点演算の処理速度を\begin{eqnarray}y=ae^{bx}[\rm{flop}/秒]\end{eqnarray}と置くと，パスワードの設定日時$s[日]$から有効期限$t[日]$までの倍精度浮動小数点演算の処理量は，1日が86400秒であるから，(1)式より，\[Y=\int_s^t 86400ydx=\frac{86400ae^{bs}(e^{bL}-1)}{b}[\rm{flop}]\]となる．$s$から$t$までにパスワードを推測できる回数$G[\rm{hash}]$を求めるためには，$Y$の単位である$\rm{flop}$を$\rm{hash}$に変換する必要がある．
SHA-256というハッシュ関数は，パスワードのハッシュ値の計算だけでなく，ビットコインのマイニングにも使われる．$\rm{hash}$と$\rm{flop}$は単位が異なるため，$Y$の単位を単純に変換することができない[3]が，例えば，GPU「Radeon HD 5970」のSHA-256のハッシュ値の計算は$863.4\rm{Mhash}/秒$[4]，倍精度浮動小数点演算の処理速度は$928\rm{Gflop}/秒$[5]であるから，$c=(863.4 \times 10^6)/(928 \times 10^9)=9.30 \times 10^{-4}[\rm{hash/flop}]$と仮定すると，\begin{eqnarray}G=cY=\frac{86400ace^{bs}(e^{bL}-1)}{b}\end{eqnarray}のように単位を変換できる．
次に，日時と処理速度からなる$N$個のデータの組$(x_i,y_i)(i=1,2,\cdots,N)$から$a,b$の最適な値を求める．$\tilde{a}=\log a,\tilde{y}=\log y$と置くと，(3)式より，\begin{eqnarray}\tilde{y}=bx+\tilde{a}\end{eqnarray}と表せられる．$i=1,2,\cdots,N$の範囲で$\tilde{y_i}=\log y_i$とし，$x$の分散を${\sigma_x}^2$，$x$と$\tilde{y}$の共分散を$\sigma_{x\tilde{y}}$，$x$の平均を$\bar{x}$，$\tilde{y}$の平均を$\bar{\tilde{y}}$とする．日時と，処理速度の自然対数からなる$N$個のデータの組$(x_i,\tilde{y_i})(i=1,2,\cdots,N)$を(5)式に合わせて回帰分析すると\[\begin{cases}b=\frac{\displaystyle N\sum_{i=1}^N (x_i \tilde{y_i})-\sum_{i=1}^N x_i \sum_{i=1}^N \tilde{y_i}}{\displaystyle N\sum_{i=1}^N ({x_i}^2)-\left(\sum_{i=1}^N x_i \right)^2}=\displaystyle\frac{\sigma_{x\tilde{y}}}{{\sigma_x}^2} \\ \tilde{a}=\frac{\displaystyle\sum_{i=1}^N ({x_i}^2)\sum_{i=1}^N \tilde{y_i}-\sum_{i=1}^N x_i \sum_{i=1}^N (x_i \tilde{y_i})}{\displaystyle N\sum_{i=1}^N ({x_i}^2)-\left(\sum_{i=1}^N x_i \right)^2}=\bar{\tilde{y}}-b\bar{x}\end{cases}\]であるから，\begin{eqnarray}\begin{cases}a=\displaystyle\exp\left(\frac{\displaystyle\sum_{i=1}^N ({x_i}^2)\sum_{i=1}^N \log y_i-\sum_{i=1}^N x_i \sum_{i=1}^N (x_i \log{y_i})}{\displaystyle N\sum_{i=1}^N ({x_i}^2)-\left(\sum_{i=1}^N x_i \right)^2}\right)=e^{\bar{\tilde{y}}-b\bar{x}} \\ b=\frac{\displaystyle N\sum_{i=1}^N (x_i \log y_i)-\sum_{i=1}^N x_i \sum_{i=1}^N \log y_i}{\displaystyle N\sum_{i=1}^N ({x_i}^2)-\left(\sum_{i=1}^N x_i \right)^2}=\displaystyle\frac{\sigma_{x\tilde{y}}}{{\sigma_x}^2}\end{cases}\end{eqnarray}と計算できる．$x_1=x_2=\cdots=x_N$または$y_i\leqq0$となる$i$が存在するときは，この回帰分析ができない．
3.2. 作成ルールを満たした$M$文字以下のパスワードの総数$T_M$
パスワードによく使用される文字は，大文字，小文字，数字，記号である．空白文字が使用されることもある．記号の全部または一部が使用できないときもあるが，記号がすべて使用できるときに使用できる記号は，
!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
の32文字である．
設定時に要求されるパスワード作成ルールは，表 1のようにサービスごとに異なる．そのため，作成ルールを満たした$M$文字以下のパスワードの総数$T_M[\rm{hash}]$もサービスやファイルごとに異なる．多くのサービスやファイルのパスワード作成ルールを調査した結果，
- 10文字以上
- 小文字，数字をそれぞれ1文字以上含む
- 同一の文字が3連続しない
というルールで作成されたパスワードは，多くのサービスやファイルで使用可能であることが分かった．これらのルールに加え，
- 小文字，数字のみを含む
- $M$文字以下
で作成可能な文字列の組み合わせを$T_M$と仮定する．大文字や記号が必要なサービスやファイルでは，必要な文字を追加してパスワードを作成するとよい．
表 1サービスごとのパスワード作成ルールの例．ただし，サービス名を非公開とした．
| サービス | パスワード作成ルール |
| サービス1 |
|
| サービス2 |
!#$%+,-./:=@_
|
| サービス3 |
|
| サービス4 |
#$&-./:?@[]_
|
| サービス5 |
|
| サービス6 |
|
| サービス7 |
|
$A$を2以上の正の整数，$n$を正の整数とする．$A$種類の文字から選ばれた$n$文字の文字列の状態が
- 最後の2文字が異なるか，後ろから2文字目が存在しない組み合わせ(例: word)を$a_n[通り]$
- 最後の2文字が同じだが，その前の文字とは異なるか後ろから3文字目が存在しない組み合わせ(例: pass)を$b_n[通り]$
と置くと，\[\begin{cases}a_{n+1}=(A-1)(a_n+b_n) & a_1=A \\ b_{n+1}=a_n & b_1=0\end{cases}\]であるから，\[\begin{cases}a_n=\frac{\displaystyle A\sqrt{(A-1)(A+3)}\left(\left(A-1+\sqrt{(A-1)(A+3)}\right)^n-\left(A-1-\sqrt{(A-1)(A+3)}\right)^n\right)}{\displaystyle 2^n(A-1)(A+3)} \\ b_n=\frac{\displaystyle A\sqrt{(A-1)(A+3)}\left(\left(A-1+\sqrt{(A-1)(A+3)}\right)^{n-1}-\left(A-1-\sqrt{(A-1)(A+3)}\right)^{n-1}\right)}{\displaystyle 2^{n-1}(A-1)(A+3)}\end{cases}\]と求められる．また，$A$種類の文字を，同一の文字が3連続しないように$n$文字並べる組み合わせを$c_n[通り]$とすると，\begin{eqnarray}c_n&=&a_n+b_n\notag \\ &=&\frac{A\sqrt{(A-1)(A+3)}}{2^n(A-1)(A+3)}\left(\left(A+1+\sqrt{(A-1)(A+3)}\right)\left(A-1+\sqrt{(A-1)(A+3)}\right)^{n-1}-\left(A+1-\sqrt{(A-1)(A+3)}\right)\left(A-1-\sqrt{(A-1)(A+3)}\right)^{n-1}\right)\notag\end{eqnarray}である．$M=10,11,\cdots$とし，\begin{eqnarray}f(A)&=&\sum_{k=10}^M c_k\notag \\ &=&\frac{A}{512(A-1)(A+3)(2A-3)}\left(\left((A-1)(A+3)+A\sqrt{(A-1)(A+3)}\right)\left(A-1+\sqrt{(A-1)(A+3)}\right)^9\left(\left(\frac{A-1+\sqrt{(A-1)(A+3)}}{2}\right)^{M-9}-1\right)-\left((A-1)(A+3)-A\sqrt{(A-1)(A+3)}\right)\left(A-1-\sqrt{(A-1)(A+3)}\right)^9\left(\left(\frac{A-1-\sqrt{(A-1)(A+3)}}{2}\right)^{M-9}-1\right)\right)\notag\end{eqnarray}と置くと，\begin{eqnarray}T_n=\begin{cases}0 & (M=1,2,\cdots,9) \\ f(36)-f(26)-f(10) & (M=10,11,\cdots)\end{cases}\end{eqnarray}が成り立つ．$f(36)-f(26)-f(10)$の値を付録に示す．
4. 実際のパスワード管理にあたって
ここでは，実際にパスワードを管理するときに，3章で作成した数理モデルをどう活用するか説明する．
パスワードの最適な長さと変更頻度を求めるため，パスワードが推測されない，すなわち$Q=1$のときの条件を求める．Webサービスでは，パスワードを変更できるが，パスワードを設定したファイルを盗まれた場合，パスワードを変更できない．そのため，ファイルに設定するパスワードのほうが，破られやすい．ファイルに設定するパスワードには，Webサービスのパスワードより長い有効期間を設定すべきである．
許容できる最短のパスワードの有効期間$L_{min}[日]$について，$0<L_{min} \leqq L$と置く．$Q=1$のとき，(2), (4)式より\begin{eqnarray}\frac{86400ace^{bs}(e^{bL}-1)}{b} \leqq T_{M-1}\end{eqnarray}と成るから，\begin{eqnarray}s \leqq \frac{1}{b}\log\frac{bT_{M-1}}{86400ac(e^{bL}-1)} \\ L \leqq \log\left(\frac{bT_{M-1}}{86400ace^{bs}}+1\right)\end{eqnarray}である．(8)式を満たす$M$の最小値を$M_{min}$とし，12以上の整数のパラメータ$p$を用いると，(9)式より\begin{eqnarray}M_{min}=\begin{cases}11 & \left(s \leqq \frac{\displaystyle 1}{\displaystyle b}\log\frac{\displaystyle bT_{10}}{\displaystyle 86400ac(e^{bL_{min}}-1)}\right) \\ p & \left(\frac{\displaystyle 1}{\displaystyle b}\log\frac{\displaystyle bT_{p-2}}{\displaystyle 86400ac(e^{bL_{min}}-1)} < s \leqq \frac{\displaystyle 1}{\displaystyle b}\log\frac{\displaystyle bT_{p-1}}{\displaystyle 86400ac(e^{bL_{min}}-1)}\right)\end{cases}\end{eqnarray}のように求められる．また，(10)式より，$M=M_{min}$のときの$L$の最大値$L_{max}$は\begin{eqnarray}L_{max}=\frac{1}{b}\log\left(\frac{bT_{M_{min}-1}}{86400ace^{bs}}+1\right)\end{eqnarray}と成る．
本記事で述べた数理モデルは，総当たり攻撃を前提としたものである．そのため，実際のパスワードの管理にあたっては，
- よく使われる単語の羅列
- キーボードをなぞるだけの文字列
- パスワード利用者本人や関係がある人の情報
を利用したパスワードは，辞書攻撃や類推攻撃などで破られるので注意すべきである．実際のパスワード管理では，複数のパスワードを管理することになる．どのパスワードについても，最初に作成するときや，有効期限が来たときに，
- (6)式により，最新の$a,b$を求める．
- Webサービスに設定するパスワードならば$L_{min}=72日$，ファイルに設定するパスワードならば$L_{min}=l$とする．「パスワードを72日おきに変更する」オプションがMicrosoftアカウントで設定できるため，Webサービスに設定するパスワードについて，$L_{min}=72$とした．
- 設定日時を$s$とする．
- (11)式により$M_{min}$を求め，新たに設定するパスワードの文字数とする．
- (12)式により$L_{max}$を求め，$s+L_{max}$を有効期限とする．
と良い．
5. パスワードが推測されない条件の計算手順
本章では，4章の内容をもとに，コンピューターに計算させる内容を示す．
- 過去の日時$x_i(i=1,2,\cdots,N)$と，その時代で最も高速なスーパーコンピューターの処理速度$y_i(i=1,2,\cdots,N)$の組$(x_i,y_i)(i=1,2,\cdots,N)$をデータとして取り込み，(6)式により$a,b$を求めた．$y_i(i=1,2,\cdots,N)$には，理論値(Rpeak)ではなく実測値(Rmax)を用いた．入力に用いたデータの組数は，$N=59$(1993年6月30日～2022年6月1日)である．
- Webサービスのパスワードについて考える．$L_{min}=72,Q=1$のときの，$36892(2001/1/1) \leqq s < 73416(2101/1/1)$に対応する$M_{min},L_{max},t$を(1), (11), (12)式により求めた．
- ファイルに設定するパスワードについて考える．$L_{min}=l,Q=1$のときの，$36892 \leqq s < 73416$に対応する$M_{min},L_{max},t$を(1), (11), (12)式により求めた．
6. 計算結果
ここでは，5章の計算結果を示す．
回帰分析に用いた2つのパラメータの値は，$a=1.4897 \times 10^{-13},b=1.6020 \times 10^{-3}$であった．以下に，得られた結果を示す．
表 2Webサービスのパスワードの文字数と設定日時
| 最小の文字数$M_{min}[文字]$ | 設定日時$s$の最大値$[日]$ | 設定日時$s$の範囲 |
| 12 | 37593 | 1996/ 9/24～2002/12/ 3 |
| 13 | 39835 | 2002/12/ 3～2009/ 1/21 |
| 14 | 42075 | 2009/ 1/21～2015/ 3/11 |
| 15 | 44314 | 2015/ 3/11～2021/ 4/27 |
| 16 | 46552 | 2021/ 4/27～2027/ 6/14 |
| 17 | 48790 | 2027/ 6/14～2033/ 7/29 |
| 18 | 51027 | 2033/ 7/29～2039/ 9/14 |
| 19 | 53264 | 2039/ 9/14～2045/10/29 |
| 20 | 55501 | 2045/10/29～2051/12/14 |
| 21 | 57738 | 2051/12/14～2058/ 1/28 |
| 22 | 59975 | 2058/ 1/28～2064/ 3/13 |
| 23 | 62211 | 2064/ 3/13～2070/ 4/28 |
| 24 | 64448 | 2070/ 4/28～2076/ 6/11 |
| 25 | 66684 | 2076/ 6/11～2082/ 7/27 |
| 26 | 68921 | 2082/ 7/27～2088/ 9/ 9 |
| 27 | 71157 | 2088/ 9/ 9～2094/10/25 |
| 28 | 73394 | 2094/10/25～2100/12/ 9 |
| 29 | 75630 | 2100/12/ 9～2107/ 1/24 |
表 3ファイルに設定するパスワードの文字数と設定日時
| 最小の文字数$M_{min}[文字]$ | 設定日時$s$の最大値$[日]$ | 設定日時$s$の範囲 |
| 32 | 37199 | 1995/ 9/20～2001/11/ 3 |
| 33 | 39435 | 2001/11/ 3～2007/12/19 |
| 34 | 41672 | 2007/12/19～2014/ 2/ 1 |
| 35 | 43908 | 2014/ 2/ 1～2020/ 3/18 |
| 36 | 46144 | 2020/ 3/18～2026/ 5/ 2 |
| 37 | 48381 | 2026/ 5/ 2～2032/ 6/15 |
| 38 | 50617 | 2032/ 6/15～2038/ 7/31 |
| 39 | 52854 | 2038/ 7/31～2044/ 9/13 |
| 40 | 55090 | 2044/ 9/13～2050/10/29 |
| 41 | 57327 | 2050/10/29～2056/12/12 |
| 42 | 59563 | 2056/12/12～2063/ 1/27 |
| 43 | 61799 | 2063/ 1/27～2069/ 3/12 |
| 44 | 64036 | 2069/ 3/12～2075/ 4/26 |
| 45 | 66272 | 2075/ 4/26～2081/ 6/10 |
| 46 | 68509 | 2081/ 6/10～2087/ 7/25 |
| 47 | 70745 | 2087/ 7/25～2093/ 9/ 8 |
| 48 | 72982 | 2093/ 9/ 8～2099/10/23 |
| 49 | 75218 | 2099/10/23～2105/12/ 7 |
図 2Webサービスのパスワードの設定日時と文字数と有効期間
図 3Webサービスのパスワードの設定日時と有効期限
図 4ファイルに設定するパスワードの設定日時と文字数と有効期間
図 5ファイルに設定するパスワードの設定日時と有効期限
7. 考察
図 3と図 5を見ると，パスワードの文字数$M_{min}$は，設定日時$s$が増えるにつれてほぼ一定時間ごとに1文字ずつ増えていることがわかる．一定時間ごとにパスワードの文字数を増やせば，パスワードの組み合わせが指数関数的に増加し，時間経過によるコンピューターの処理能力の指数関数的増加に対応することができるからである．
文字数$M_{min}$が1増加するためにかかる時間は，(11)式より\[\lim_{M_{min}\to\infty}\left(\frac{1}{b}\log\frac{bT_{p-1}}{86400ac(e^{bL_{min}}-1)}-\frac{1}{b}\log\frac{bT_{p-2}}{86400ac(e^{bL_{min}}-1)}\right)=\frac{1}{b}\log\frac{35+\sqrt{1365}}{2}\]に収束する．$b=1.6020 \times 10^{-3}$であるから，2236.4日に収束する．
文字数$M_{min}$が十分長いときの有効期間$L_{max}$の上限は，(11), (12)式より\[\limsup_{M_{min}\to\infty}L_{max}=\frac{1}{b}\log\left(\frac{(35+\sqrt{1365})(e^{bL_{min}}-1)}{2}+1\right)\]である．$b=1.6020 \times 10^{-3}$であるから，
- $L_{min}=72日$のとき，1052.5日
- $L_{min}=l$のとき，46066日
と成る．
図 4と図 6を見ると，設定日時$s$が新しいほど，有効期限$t$も新しくなることがわかる．
設定日時$s$の関数である有効期限$t$は$L_{max} \neq L_{min}$のとき微分可能であり，$L=L_{max}$とすると，(1), (12)式より，\[\frac{dt}{ds}=\frac{86400ace^{bs}}{bT_{M_{min}-1}+86400ace^{bs}}\]であるから，$0<dt/ds<1$である．
8. おわりに
スーパーコンピューターの技術的進歩と，設定時に要求されるパスワード作成ルールを参考にして，パスワードの安全性について考え，実際のパスワード管理方法を提案することができた．その結果は12文字から49文字までという幅の広いものだが，文字数が多すぎるといえる．複数のアカウントでパスワードレスや生体認証が用いられるようになってきたのは，長くて異なるパスワードを覚えるのが難しいからであろう．
秘密の質問の答えでも，今回紹介した式が使えそうである．しかし，秘密の質問の答え作成ルールもサービスやファイルごとに異なるため，追加の調査が必要である．
9. 参考文献
[1] DoD Computer Security Center. (1985年4月12日). Department of Defense Password Management Guideline. https://apps.dtic.mil/sti/pdfs/ADA425705.pdf
[2] TOP500.org. (2021年11月16日). Home - | TOP500. https://www.top500.org/
[3] 星暁雄. (2017年3月9日). 「ビットコインのP2Pネットワークは世界最大のコンピュータ」なのか？ | さくらのナレッジ. https://knowledge.sakura.ad.jp/7858/
[4] Bitcoin Wiki. (2019年6月10日). Non-specialized hardware comparison - Bitcoin Wiki. https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison
[5] Wikipedia. (2022年1月4日). Radeon HD 5000 series – Wikipedia. https://en.wikipedia.org/wiki/Radeon_HD_5000_series
付録
(7)式の$f(36)-f(26)-f(10)$の値を以下に示す．\[\frac{1}{256}\left(\frac{6}{10465}\left((455+12\sqrt{1365})(35+\sqrt{1365})^9\left(\left(\frac{35+\sqrt{1365}}{2}\right)^{M-9}-1\right)-(455-12\sqrt{1365})(35-\sqrt{1365})^9\left(\left(\frac{35-\sqrt{1365}}{2}\right)^{M-9}-1\right)\right)-\frac{5078125}{1421}\left((145+26\sqrt{29})(5+\sqrt{29})^9\left(\left(\frac{5(5+\sqrt{29})}{2}\right)^{M-9}-1\right)-(145-26\sqrt{29})(5-\sqrt{29})^9\left(\left(\frac{5(5-\sqrt{29})}{2}\right)^{M-9}-1\right)\right)-\frac{32805}{221}\left((39+10\sqrt{13})(3+\sqrt{13})^9\left(\left(\frac{3(3+\sqrt{13})}{2}\right)^{M-9}-1\right)-(39-10\sqrt{13})(3-\sqrt{13})^9\left(\left(\frac{3(3-\sqrt{13})}{2}\right)^{M-9}-1\right)\right)\right)\]
