FPGA 向けの真性乱数生成器 (TRNG; True Random Number Generator) の設計法に関するコースの第2回です．今回は、FPGA の回路素子を用いた TRNG に関するサーベイ論文を土台に、FPGA 向きの TRNG の生成手法について、その基本的な考え方を説明します。
今回の記事は、FPGA 関連の世界最大級の国際会議の1つである FPL で2016年に発表された論文 [1] を土台としています。ただ、紹介する手法のうちのいくつかは、私の手元の FPGA ボードで再現実験をしたときの実装をもとに説明します。
リングオシレータ
リングオシレータとその動作
ディジタル回路、特に FPGA で TRNG を作るにあたり、多くの場合の基礎となる回路が、下図に例示するリングオシレータ (RO; Ring Oscillator) です。RO は一般に、奇数個の NOT ゲートを環状に接続したものです。
上図に示した3個の NOT ゲートからなる RO の動作について考えてみます。とはいえ、この回路には入力がないので、いずれかの信号の時刻ゼロにおける信号値を仮定して、そこから各信号の時間変化を求めてみます。ここでは各 NOT ゲートの出力を Q0、Q1、Q2 とし、回路の出力 Q は Q2 と定義します。また、各 NOT ゲートは τ の伝搬遅延をもつ (つまり、入力が変化してから τ 経過した後に出力が変化する) ものとします。
下図に、以上の仮定のもとで求めた RO のタイミングチャートを示します。
時刻0では、仮定どおり Q2 = ‘0’ として、Q0、Q1 は不定値とします。時刻 τ では、左側の NOT ゲートの入力 Q2 = ‘0’ より、Q0 は ‘1’ に変化します。その変化により、時刻 2τ では中央の NOT ゲートの出力 Q1 が ‘0’ に変化します。時刻 3τ 以降も同様に、Q2 = ‘1’、Q0 = ‘0’、Q1 = ‘1’、……と変化します。
結果として、いつまで経ってもこの回路の信号はぐるぐると変化し続ける、つまり発振するということになります。環状 (リング) のゲートにより作られる発振回路 (オシレータ) なので、この回路をリングオシレータとよぶわけです。
ちなみに、NOT ゲートが偶数個の場合には、最終的に全ての NOT ゲートの出力値を安定に (発振することなく) 定めることができます。これは、ある信号の値を ‘0’ と定めた場合でも、’1′ と定めた場合でも成り立ちます。こうした回路は、2つの安定状態をもつ回路、すなわち2安定 (バイステーブル) 回路といいます。2安定回路はフリップフロップや SRAM の記憶素子の基礎になっています。
ただ、先に示した RO はあくまで原理を説明するためのもので、そのまま使われることはまれです。特に、現実には発振するかどうかを決める有効入力がないと不便です。
そのため、NOT ゲートのうち1つを NAND ゲートで置き換えて、その一方の入力を有効入力とすることが多いです。また、このとき残った偶数個の NOT ゲートは、単に任意の個数のバッファ (入力をそのまま出力するゲート) としてしまっても、論理的に等価です。
ということで、実際に使われる RO は、上図に示す1個の NAND ゲートと任意個のバッファからなる構成をもつ場合が多いです。以降の説明では、これを1入力1出力の回路ブロック RO で表します。
今回の想定事項
セキュアなシステムに関する研究では、攻撃者がどのような攻撃を行うのか、あるいは構成要素をどこまで信頼できるものとみなすか、といった想定をきちんと定めることが大切です。ある1つの手法であらゆる攻撃に対処できるということはまずないので、通常は複数の手法が組み合わせて用いられます。どう組み合わせるかを考えるには、そもそも採用する手法がカバーできる範囲を知らないといけないわけです。
今回紹介するサーベイ論文では、外部クロック入力も信頼できない (攻撃者によって操作されうる) ものとみなしています。つまり、TRNG で使うクロック信号は内部で作り出さなければならないということです。そのため今回は、クロック信号は RO を使って生成します。
とはいえ、この想定はやや厳しすぎるようにも見えます。外部クロック入力は信頼できるという想定はそれほど不合理というわけでもないですし、仮にそうでなくても、システム全体でクロック入力の異常を検知できる仕組みを持っていれば十分かもしれません。次回以降は、外部クロック入力も使用できる想定で話を進めていきます。
リングオシレータを使った TRNG の例
下図に、基本的なリングオシレータ型 (ERO 型; Elementary RO) の TRNG の構造を示します。これは、2つの RO と分周比 K の分周回路、そして D フリップフロップ (D-FF) から構成されます。
RO の出力周波数は一定ではありません。先に示したタイミングチャートでは全ての NOT ゲートの伝搬遅延を τ で一定とみなしました。しかし、実際には素子の細かな特性の違いによって伝搬遅延は少しずつ異なります。そのため、同じ形の RO でも、使うチップや素子の配置によってその出力周波数は異なります。
また、ある RO から出力される波形を細かく見れば、その周期にはほんの少しだけ (ピコ秒単位の) ばらつきがあります。これをジッタといいます。
これらの不確実性の影響によって、RO2 の出力を十分大きな K で分周した信号で RO1 の出力を D-FF でサンプリングすると、その出力からは ‘0’ と ‘1’ がほぼ半々の確率で、しかも予測不可能な形で現れます。K をどれくらい大きくするべきかは、確率的モデルから計算できます。具体的には、デバイスによっても異なりますが、数万～数十万程度のようです。
ERO 型の TRNG は、シンプルなハードウェアで実現できて、ランダム性も十分、デバイスや環境への非依存性も申し分ないのですが、乱数の生成速度が極めて低いのが弱点です。RO の出力周波数はおおむね数百 MHz なので、それを数万～数十万で分周するということは、数 kbit 毎秒程度でしか乱数が生成できないことを意味します。
じゃあそれを複数並べれば……と思った方は鋭いです。ただ、単に ERO 型の TRNG を複数並べるよりも、複数の RO の出力を XOR したものを乱数として使った方が、回路面積の面で効率が良くなります。それが下図に示す複数リングオシレータ型 (MURO 型; Multi RO) の TRNG です。
多数の RO を使えば、それだけ分周比 K を小さくできます。論文では、120個の RO を使い、K を100に設定しています。ERO 型 TRNG を多数並べる場合と比べ、分周回路は1個だけで済みますし、K が小さいので分周回路自体も小さく作れます。これにより、数 Mbit 毎秒の速度での乱数生成が効率良く行えます。
また、複数個の RO の出力をサンプリングするのではなく、非同期回路のハンドシェイクで用いられる回路素子を使った Self-timed Ring (STR) というリングを構成し、その各出力をサンプリング、XOR する方法も提案されています。これを Self-timed Ring 型 (STR 型) の TRNG とよびます。論文では、255 素子の STR を用いることで、サンプリングクロックの分周が不要となることが示されています。つまり STR 型 TRNG では数百 Mbit 毎秒での乱数生成が可能です。
ただ、MURO 型と STR 型の TRNG は、必要な論理素子 (LUT や D-FF) の絶対数が多い (ともに百個単位) 点に注意が必要です。また STR 型では、望んだ動作をさせるために多くの素子を注意深く配置する必要があり、配置の自由度が低いということも、問題点として挙げられています。
コヒーレントサンプリング
2つの独立なクロック源を使う方法
次に紹介するのは、下図に示すコヒーレントサンプリング型 (COSO 型; Coherent Sampling RO) の TRNG です。今度は、2つの RO の出力が直接 D-FF のデータ入力 D とクロック入力に接続されています。詳しい原理は次回に説明したいと思いますが、ここでは簡単にその動きを紹介します。
COSO 型 TRNG では、2つの RO から出力されるクロック信号がほんの少しだけ異なる周波数 (周期) をもつと考えます。そうすると、RO2 の出力によるサンプリングのたびに、RO1 の出力との間の位相が少しずつズレていきます (これがコヒーレントサンプリングです)。その結果、D-FF の出力は ‘0’ の連続と ‘1’ の連続を繰り返します。
実際に ‘0’ が何回連続するかには不確定性があります。この回数の偶奇を T フリップフロップ (T-FF) で数え、左の D-FF から ‘1’ が出力されたら、その結果を右の D-FF から出力します。これにより乱数を取り出すのが、COSO 型の TRNG です。
この COSO 型の TRNG は、周期が少しだけ異なる RO のペアを運良く見つけることができれば、1 Mbit 毎秒程度の乱数を極めて少ない数の論理素子 (LUT 20個と D-FF 3個程度) で実現できます。問題は、そうしたペアを見つけることが難しい、ということです。
サーベイ論文が発表された2016年時点では、この問題は未解決でした。しかし、2019年の FPL にてこの問題を解決する COSO 型 TRNG の改良が提案されています [2]。この論文は第5回で紹介する私の研究の土台にもなっているので、詳細はそのときに説明したいと思います。
1つのクロック源から周波数合成する方法
前述の通り、COSO 型 TRNG では周期が少しだけ異なる2つのクロック信号を用意する必要があります。実はその方法はもう1つあります。1つのクロック源 (RO) から PLL (Phase-locked Loop) を使って分周・逓倍を行い、そうしたクロック信号のペアを生み出すという方法です。この考えに基づくのが、下図に示す PLL を用いたコヒーレントサンプリング型 (PLL 型) TRNG です。
FPGA では、用途によっては様々な周波数のクロックが必要とされる場合があります。そのため、PLL などのクロッキング素子は FPGA 内にそれなりの個数存在しています。とはいえ、実際にその全てを使うことはまれですから、そのうちの2個をこうした用途で使用しても、ほとんどの場合問題はありません。
動作の基本原理は COSO 型と同様にコヒーレントサンプリングなので、COSO 型の利点の多くは PLL 型でも共通です。ただし、クロッキング素子は FPGA のメーカーや世代によって作りが変わっていることも多く、新しい世代の FPGA でこの手法が引き続き使用できるかどうかは、しっかりと検討しなければなりません。この辺りの詳しい話は、また次回することとします。
SR ラッチと TERO (遷移効果リングオシレータ)
SR ラッチの禁止状態
最後に紹介するのは、遷移効果リングオシレータ型 (TERO 型; Transition Effect RO) の TRNG ですが、その説明のために前回示した SR ラッチを再掲しておきます。
前回、この SR ラッチを禁止状態から一気に保持状態に移行させると何が起きるか……という話をしました。RO のタイミングチャートを検討したときと同様に考えてみると、Q と /Q とでそれぞれ時間 τ ごとに ‘0’ と ‘1’ とを繰り返す波形が得られます (詳しくは第4回で検討します)。つまり、これも一種の発振回路として動作してしまうことになります。TERO 型 TRNG では、これを遷移効果リングオシレータとよんでいます。
ただ、現実にはこの発振は永遠には続きません。様々な要因により、どこかのタイミングで ‘0’ や ‘1’ の安定な状態に落ち着きます。回路をうまく調整してやると、最終的にどちらで安定するか (出力) や、安定するまでにどれくらい時間がかかるか (発振の回数) に不確実性が生まれます。このうち後者に着目したものが、TERO 型の TRNG です。
なお、前者に着目する、つまり SR ラッチの出力そのものに注目することでも TRNG を構成できます [3]。本コースでは、こうした TRNG について第4回で扱うことにします。ただし、この種の TRNG は厳密な確率的モデルが用意されているものではないため、今回のサーベイ論文では議論の対象外となっています。
TERO 型 TRNG
TERO 型の TRNG の構成例を下図に示します。左上に見える8の字状に接続された2つの NAND ゲートと任意個のバッファは、SR ラッチの2つの入力に同じ信号 /CTRL を接続した場合と論理的に等価です。
CTRL が ‘0’ の間は、ラッチは禁止状態で、両方の NAND ゲートが ‘0’ を出力します。CTRL が ‘1’ になると、ラッチは禁止状態から一気に保持状態に移行し、しばらくの間発振します。発振の回数の偶奇は、NAND ゲートの出力の立上りを T-FF で数えることで求めます。再び CTRL が ‘0’ になると、その結果が D-FF に取り込まれ、出力されます。これにより乱数を取り出すのが、TERO 型の TRNG です。
TERO 型の TRNG で十分なランダム性が取り出せるとき、発振する時間は概ね 1 マイクロ秒弱です。そのため、TERO 型の TRNG からはおよそ 1 Mbit 毎秒程度の乱数が取り出せます．必要な論理素子の数もかなり少なく済みます。
TERO 型の TRNG の問題点は、ちょうど良い回数の発振が起きるように回路を調整することが難しいことです。COSO 型と同様に、2016年時点でこの問題は未解決でした。しかし、2020年の FPL で発表した私の最近の研究で、回路の構成を工夫し、COSO 型 TRNG で行われたのと似た改良を施すことで、この問題も解決できることがわかりました [4]。詳細は、本コースの第5回で説明したいと思います。
まとめ
今回は、FPGA 向けの TRNG の構成法のいくつかを概説するとともに、本コースで今後説明していく内容の導入を行いました。今回は、要点を挙げるかわりに、紹介した6種類の TRNG の利点・欠点を表にまとめておきます。
| 型 | 利点 | 欠点 |
|---|---|---|
| ERO 型 | 構成がシンプル，デバイス非依存性も良好 | 乱数の生成速度が極めて低い |
| MURO 型 | デバイス非依存性が良好 | 使用する論理素子数が多い |
| STR 型 | 乱数の生成速度が極めて高い | 使用する論理素子数が多い |
| COSO 型 | 使用する論理素子数が少ない | 良好なクロックの組を見つけるのが難しい |
| PLL 型 | 使用する論理素子数が少ない | 使用するクロッキング素子の影響が大きい |
| TERO 型 | 使用する論理素子数が少ない | 回路の調整が難しい |
次回は、PLL 型の TRNG の動作についてもう少し詳しく説明したあと、これらを Xilinx 社の最近の FPGA でどうやれば活用できるかについて、我々の最近の研究成果をもとにお話したいと思います。
愛知⼯業⼤学 藤枝直輝
参考文献
- [1] O. Petura, U. Mureddu, N. Bochard, V. Fischer, and L. Bossuet: A Survey of AIS-20/31 Compliant TRNG Cores Suitable for FPGA Devices, 26th International Conference on Field Programmable Logic and Applications (FPL 2016), pp. 1–10, 2016. DOI: 10.1109/FPL.2016.7577379
- [2] A. Peetermans, V. Rožić, and I. Verbauwhede: A Highly-Portable True Random Number Generator based on Coherent Sampling, 29th International Conference on Field Programmable Logic and Applications (FPL 2019) pp. 218–224, 2019. DOI: 10.1109/FPL.2019.00041
- [3] H. Hata and S. Ichikawa: FPGA Implementation of Metastability-based True Random Number Generator,” IEICE Transactions on Information and Systems, Vol. E95-D, No. 2, pp. 426–436, 2012. DOI: 10.1587/transinf.E95.D.426
- [4] N. Fujieda: On the feasibility of TERO-based true random number generator on Xilinx FPGAs, 30th International Conference on Field-Programmable Logic and Applications (FPL 2020), pp. 103–108, 2020. DOI: 10.1109/FPL50879.2020.00027