(57)【要約】【課題】安全性、回路規模及び動作周波数を考慮した論理回路の設計装置を提供する。【解決手段】入力された論理式に対応する論理回路の設計装置であって、レジスタ数を入力する入力手段と、前記論理回路への入力値を保存するレジスタと、前記論理回路の出力値を保存するレジスタとは別に、中間値を保存する前記レジスタ数のレジスタの挿入位置を決定する決定手段と、を備えており、前記決定手段は、レジスタ間の論理素子数の差が所定の値以下となる様にレジスタの挿入位置を決定する。【選択図】図９
2014109865.tif 000002
【特許請求の範囲】
【請求項１】
入力された論理式に対応する論理回路の設計装置であって、
レジスタ数を入力する入力手段と、
前記論理回路への入力値を保存するレジスタと、前記論理回路の出力値を保存するレジスタとは別に、中間値を保存する前記レジスタ数のレジスタの挿入位置を決定する決定手段と、
を備えており、
前記決定手段は、レジスタ間の論理素子数の差が所定の値以下となる様にレジスタの挿入位置を決定することを特徴とする設計装置。
【請求項２】
前記決定手段は、
前記論理式を木構造に対応させ、当該木構造のルート・ノードから、当該ルート・ノードとの距離が最も遠い葉ノードに至る経路を分割することで生じる２つの部分のノード数が同じか、その差が１となる様に当該木構造を分割し、
追加するレジスタ数が２以上である場合には、さらに、分割して生じた各木構造について、ルート・ノードからの距離が最も遠い葉ノードを有する木構造のルート・ノードから、当該最も遠い葉ノードに至る経路上であって、当該経路を分割することで生じる２つの部分のノード数が同じか、その差が１となる位置で当該木構造を分割することを、追加するレジスタ数から１だけ引いた回数だけ繰り返し、
木構造を分割した位置を、前記中間値を保存するレジスタの挿入位置に決定することを特徴とする請求項１に記載の設計装置。
【請求項３】
入力された論理式に対応する論理回路の設計装置であって、
レジスタ数及び最大素子数を入力する入力手段と、
前記論理回路への入力値を保存するレジスタと、前記論理回路の出力値を保存するレジスタとは別に、前記論理回路の中間値を保存するレジスタを、前記入力手段に入力されたレジスタ数だけ挿入することでレジスタ間の素子数を前記最大素子数以下にできるかを判定する判定手段と、
前記最大素子数以下にできない場合には警告を出力する出力手段と、
を備えていることを特徴とする設計装置。
【請求項４】
前記レジスタ間の素子数が前記最大素子数以下となる様にレジスタの挿入位置を決定する決定手段と、
前記決定手段が挿入位置を決定したレジスタ数が、前記入力手段に入力されたレジスタ数未満である場合、追加するレジスタ数が前記入力手段に入力されたレジスタ数に等しくなる様に、ダミーの論理回路を生成する生成手段と、
を備えていることを特徴とする請求項３に記載の設計装置。
【請求項５】
請求項１から４のいずれか１項に記載の設計装置としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路規模、動作周波数及びサイドチャネル攻撃への耐性を考慮した論理回路の設計技術に関する。
【背景技術】
【０００２】
例えば、暗号処理を行うハードウェアは、当該ハードウェアが扱う暗号鍵等の秘密情報が、サイドチャネル攻撃等によって漏洩することを防ぐ様に構成しなければならない。特許文献１及び２並びに非特許文献１及び２は、ハードウェアが扱う情報の漏えいを防ぐ論理回路の安全な実装方法を開示している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−３３４０１６号公報
【特許文献２】特開２０１２−００４８８８号公報
【非特許文献】
【０００４】
【非特許文献１】Ｊｏａｎ  Ｄａｅｍｅｎ，  ｅｔ  ａｌ．，"Ｂｉｔｓｌｉｃｅ  Ｃｉｐｈｅｒｓ  ａｎｄ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  Ａｔｔａｃｋｓ，"Ｐｒｏｃ．  ｏｆ  Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ  （ＦＳＥ２０００），Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １９７８,   ｐｐ.１３４−１４９，２０００年
【非特許文献２】Ｊｏｖａｎ  Ｄｊ．  Ｇｏｌｉｃ，  ｅｔ  ａｌ．，"Ｕｎｉｖｒｓａｌ  Ｍａｓｋｉｎｇ  ｏｎ  Ｌｏｇｉｃ  Ｇａｔｅ  Ｌｅｖｅｌ"，Ｅｌｅｃｔｒｏｎｉｃｓ  Ｌｅｔｔｅｒｓ，Ｖｏｌ．４０，Ｎｏ.９，２００４年４月２９日
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ハードウェアの構成においては、サイドチャネル攻撃等に対する安全性のみならず、回路規模や動作周波数をも考慮する必要がある。しかしながら、上記従来技術は、回路規模や動作周波数を考慮してはいない。
【０００６】
本発明は、安全性、回路規模及び動作周波数を考慮した論理回路の設計装置及び当該設計装置としてコンピュータを機能させるプログラムを提供するものである。
【課題を解決するための手段】
【０００７】
本発明の一態様によると、入力された論理式に対応する論理回路の設計装置であって、レジスタ数を入力する入力手段と、前記論理回路への入力値を保存するレジスタと、前記論理回路の出力値を保存するレジスタとは別に、中間値を保存する前記レジスタ数のレジスタの挿入位置を決定する決定手段と、を備えており、前記決定手段は、レジスタ間の論理素子数の差が所定の値以下となる様にレジスタの挿入位置を決定することを特徴とする。
【０００８】
本発明の一態様によると、入力された論理式に対応する論理回路の設計装置であって、レジスタ数及び最大素子数を入力する入力手段と、前記論理回路への入力値を保存するレジスタと、前記論理回路の出力値を保存するレジスタとは別に、前記論理回路の中間値を保存するレジスタを、前記入力手段に入力されたレジスタ数だけ挿入することでレジスタ間の素子数を前記最大素子数以下にできるかを判定する判定手段と、前記最大素子数以下にできない場合には警告を出力する出力手段と、を備えていることを特徴とする。
【発明の効果】
【０００９】
安全性、回路規模及び動作周波数を考慮した論理回路を設計することができる。
【図面の簡単な説明】
【００１０】
【図１】一実施形態による論理回路の設計方法の説明図。
【図２】一実施形態による論理回路の設計方法の説明図。
【図３】一実施形態による論理回路の設計方法の説明図。
【図４】一実施形態による論理回路の設計方法の説明図。
【図５】一実施形態による論理回路の設計方法の説明図。
【図６】一実施形態による論理回路の設計方法の説明図。
【図７】一実施形態による論理回路の設計方法の説明図。
【図８】一実施形態による論理回路の設計方法のフローチャート。
【図９】一実施形態による論理回路の設計装置の概略的な構成図。
【発明を実施するための形態】
【００１１】
以下、本発明の例示的な実施形態について図面を参照して説明する。なお、以下の各図においては、実施形態の説明に必要ではない構成要素については図から省略する。
【００１２】
何らかの論理演算を行う論理回路は、ＡＮＤゲートやＯＲゲート等の論理素子を複数組み合わせて実現するが、これら論理回路の中間段に中間値を保存するためのレジスタを設けることがある。ここで、レジスタ数を抑えるために、レジスタ間の論理素子数を増大させると、動作クロックを低くする必要が生じ動作周波数が低下する。つまり、動作周波数を速くするためには、レジスタ間の論理素子数を減らす必要がある。しかしながら、これは、レジスタ数を増加させ回路規模を増大させる。一方、レジスタ数を多くし、回路規模を大きくすると、各素子が発するノイズ等が増加しサイドチャネル攻撃への耐性が向上する。つまり、一般的には、回路規模を小さくすると、動作周波数及びサイドチャネル攻撃に対する耐性が低下し、動作周波数及びサイドチャネル攻撃に対する耐性を増加させようとすると回路規模が増大することになる。
【００１３】
ここで、目標とする回路規模が与えられたとしても、そのために追加するレジスタの位置によっては、動作周波数が最適にはならないといった様に、ある条件のもとで、できるだけ適切な回路構成を決定する必要がある。本発明は、その様な設計装置を提供するものである。
【００１４】
＜第一実施形態＞
本実施形態において、設計装置は、論理式と、所望の安全性及び回路規模を考慮して決定した追加するレジスタ数を入力として、動作周波数をできるだけ高くする回路構成を出力する。なお、以下の各実施形態において各論理素子における遅延時間は同じであるものとする。
【００１５】
図９（Ａ）は、本実施形態における設計装置１の概略的な構成図である。以下、本実施形態における設計処理について説明する。
【００１６】
手順０：設計装置１の入力部１１に論理式と、追加するレジスタ数を入力する。なお、以下の説明においては、一例として、入力する論理式を（Ｘ∧（Ｙ−)∨(Ｚ∧(Ｕ∨Ｗ)−))とし、追加するレジスタ数を３とする。なお、演算子"−"は、否定（ＮＯＴ）演算を意味している。
【００１７】
手順１：設計装置の変換部１２は、入力された論理式を木構造で表す。なお、木構造の葉ノードは、各変数の値を格納するレジスタであり、それ以外のノードは論理素子であるものとする。また、論理式の出力は、レジスタＲＥＧに格納する。本例における入力論理式（Ｘ∧（Ｙ−)∨(Ｚ∧(Ｕ∨Ｗ)−))は、図１の木構造で表すことができる。図１において、Ｘ、Ｙ、Ｕ、Ｗ、Ｚは、変数を表すレジスタであり、ルート・ノードは、論理式の結果が格納されるレジスタＲＥＧではなく、最後に実行されるＯＲ演算とする。
【００１８】
手順２：設計装置の分割部１３は、木構造の各葉ノードの深さを計算する。ノードの深さは、ノードのルート・ノードからの距離を示し、ここでは、ルート・ノードの深さを０とし、その他のノードの深さは、親ノードの深さに１を足したものとする。例えば、図１の各葉ノードの下の数字は、各葉ノードの深さを示している。
【００１９】
手順３：分割部１３は、最大の深さを持つ葉ノードを選択し、ルート・ノードから選択した葉ノードに至る経路の中間点にレジスタを挿入して木構造を２つに分割する。ここで、中間点とは、レジスタを挿入して当該経路を２つの部分に分割することで、分割された２つの部分の論理素子数が同じか、その差が１となる位置である。なお、最大の深さを持つ葉ノードが複数存在する場合には、任意の１つを選択する。例えば、図１においては深さの最大値は４であり、葉ノードＵ又はＷを選択する。ここで、葉ノードＵを選択すると、ＡＮＤ演算とＮＯＴ演算の間の位置にレジスタを挿入して２つに分割することで、レジスタＵと挿入するレジスタ間の論理素子数と、レジスタＲＥＧと挿入するレジスタ間の論理素子数は共に２となるため、この位置にレジスタを挿入する。図２は、分割後の２つの木構造を示している。図２に示す様に、分割して生成した新たな木構造のルート・ノードはＮＯＴ演算であり、ＮＯＴ演算の結果は挿入したレジスタＲＥＧ１に格納される。
【００２０】
手順４：分割部１３は、追加したレジスタ数が、入力されたレジスタ数である３となるまで手順２及び３を繰り返す。本例においては、２回目の手順２で計算される葉ノードの深さは図２に示す通りとなり、２回目の手順３で最大の深さを持つ葉ノードＹが選択される。この場合、ＡＮＤ演算とＮＯＴ演算の間にレジスタＲＥＧ２を挿入して木構造を分割する。分割後の状態は図３に示す通りとなる。
【００２１】
さらに、３回目の手順２で計算される葉ノードの深さは図３に示す通りとなる。３回目の手順３で最大の深さ２を持つ葉ノードＸを選択したとすると、例えば、ＯＲ演算とＡＮＤ演算の間にレジスタＲＥＧ３を挿入して木構造を分割する。分割後の状態は図４に示す通りとなる。この時点で追加したレジスタ数が、入力されたレジスタ数と等しくなるため手順４を終了する。
【００２２】
手順５：設計装置の出力部１４は、手順４で決定した木構造の通りに論理回路を構成する。
【００２３】
本実施形態においては、最大の深さを持つ葉ノードに至る経路の中点にレジスタを追加して木構造を分割することを追加するレジスタ数だけ繰り返す。その結果、レジスタ間の論理素子数は略平均化され、よって、レジスタ間の論理素子数が偏ることにより、レジスタ間の論理素子数の最大数により論理回路全体の動作周波数が制限されることを防ぐことができる。なお、上記実施形態では、レジスタ間の論理素子数の差は最大で１であるが、所定の値以下となる様にレジスタを挿入する形態であっても良い。
【００２４】
＜第二実施形態＞
本実施形態において、設計装置は、論理式と、安全性を考慮して決定した追加するレジスタの数と、動作周波数を考慮して決定したレジスタ間の論理素子の最大数とを入力として、入力されたレジスタ数を追加し、かつ、レジスタ間の論理素子の最大数を満たす回路構成が可能であるか否かを判定し、可能な場合にはその回路構成を出力する。図９（Ｂ）は、本実施形態における設計装置２の概略的な構成図であり、図８は、本実施形態の処理のフローチャートである。以下、本実施形態における設計処理について説明する。
【００２５】
手順０：設計装置２の入力部２１に論理式と、追加するレジスタ数と、レジスタ間の論理素子の最大数（最大素子数）を入力する。なお、以下の説明においては、入力された論理式を（Ｘ∧（Ｙ−)∨(Ｚ∧Ｕ)）とし、追加するレジスタ数Ｍを２とし、レジスタ間の論理素子の最大数Ｎを２とする。
【００２６】
図８のＳ１０で、設計装置２の変換部２２は、第一実施形態と同様に入力された論理式を木構造で表す。図５は、入力された（Ｘ∧（Ｙ−)∨(Ｚ∧Ｕ)）を木構造で表したものである。なお、ＲＥＧは、第一実施形態と同様に入力された論理式の出力を格納するレジスタである。設計装置２の分割部２３は、Ｓ１０でカウンタｉを０に初期化する。
【００２７】
Ｓ１１で、分割部２３は、第一実施形態と同様に木構造の各葉ノードの深さを計算する。図５の各葉ノードの下の数字は、各葉ノードの深さを示している。そして、分割部２３は、Ｓ１１で最大の深さがレジスタ間の論理素子の最大数Ｎより大きいか否かを判定する。大きい場合にはＳ１３に進み、そうでない場合にはＳ１２に進む。例えば、図５において、最大の深さは３であり、最大数Ｎ＝２より大きいためＳ１２に進む。
【００２８】
分割部２３は、Ｓ１２で最大の深さを持つ葉ノードを選択し、ルート・ノードから選択した葉ノードに至る経路上においてレジスタを挿入して木構造を２つに分割する。なお、レジスタを挿入する位置は、レジスタを挿入して当該経路を２つの部分に分割することで、分割された２つの部分のいずれかの論理素子数が最大数Ｎとなる位置である。なお、最大の深さを持つ葉ノードが複数存在する場合には、任意の１つを選択する。例えば、図５において、最大の深さ３を持つ葉ノードＹに至る経路上のＡＮＤ演算とＮＯＴ演算の間にレジスタを挿入して２つの木構造に分割するで、レジスタＲＥＧと挿入するレジスタ間の論理素子数が最大数Ｎ＝２となるため、この位置にレジスタを挿入する。図６は、分割後の２つの木構造を示している。また、分割部２３は、レジスタを１つ追加したのでカウンタｉを１だけ増加させる。その後、再度、Ｓ１１を行う。
【００２９】
本例においては、２回目のＳ１１で木構造の最大の深さは２であり、最大数Ｎ＝２に等しいため、Ｓ１３に進む。
【００３０】
設計装置２の判定部２４は、Ｓ１３で追加したレジスタ数を示すｉが追加するレジスタ数Ｍ＝２未満であるかを判定する。ｉがＭ未満であるとＳ１４に進み、そうでなければＳ１５に進む。本例においては、追加したレジスタ数ｉは１であり、追加するレジスタ数Ｍ＝２未満であるため、Ｓ１４に進む。Ｓ１４において、設計装置２の生成部２５は、追加するレジスタ数が入力されたレジスタ数Ｍとなる様に、（Ｍ−ｉ個）ダミーの論理回路を追加する。追加するダミーの論理回路は、レジスタ間の論理素子の数が最大数Ｎ以下であればその演算式の内容は任意である。本例においては（Ｍ−ｉ）＝１であるため、図７に示す様に、入力された論理式（Ｘ∧（Ｙ−)∨(Ｚ∧Ｕ)）とは無関係に、ＲＥＧ２＝（Ｘ∨Ｙ）−を演算する１つの論理回路を挿入している。設計装置２の出力部２６は、ダミーを含む木構造の通りに論理回路を構成して処理を終了する。
【００３１】
なお、Ｓ１３でｉがＭ未満ではない場合、判定部２４は、Ｓ１５でｉとＭが等しいかを判定する。ｉとＭが等しい場合、ダミーの論理回路を追加する必要がないので、出力部２６は、木構造の通りに論理回路を構成して処理を終了する。一方、Ｓ１５でｉとＭが等しくなければ、レジスタ間の論理素子数の最大数をＮ以下とするためには、追加するレジスタ数をＭより大きくしなければならないため、出力部２６は、Ｓ１６でレジスタ数Ｍでは最大数をＮ以下にできないことを示す出力を行って処理を終了する。
【００３２】
本実施形態においては、所望の安全性及び動作周波数を満足する論理回路構成が存在するか否かと、存在する場合にはその構成を決定できる。
【００３３】
なお、本発明による設計装置１、２は、コンピュータを設計装置１、２として動作させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。
【図１】
2014109865.tif 000003
【図２】
2014109865.tif 000004
【図３】
2014109865.tif 000005
【図４】
2014109865.tif 000006
【図５】
2014109865.tif 000007
【図６】
2014109865.tif 000008
【図７】
2014109865.tif 000009
【図８】
2014109865.tif 000010
【図９】
2014109865.tif 000011