(57)【特許請求の範囲】
【請求項１】
２つの入力のあるいくつかのビットが変化した時に、これら２つの入力の和（出力）のあるいくつかのビットが変化する確率（差分確率）を計算する装置であって、
上記２つの入力の各差分値と、出力の差分値が入力され、
これら３つの差分値の排他的論理和を演算して各ビットへの繰り上がり（ｃａｒｒｙ）の差分値を計算する繰り上がり差分演算手段と、
上記２つの入力差分値のｉビット目の値（ｉ＝０，１，２，…，ｎ−２、ｎは各入力のビット数）と、繰り上がりの差分値のｉビット目の値との和を演算する和演算手段と、
上記和演算手段の演算結果と上記繰り上がりの差分値のｉ＋１ビット目の値とから、そのｉ＋１ビット目の値となる確率を求める手段と、
上記各ｉについて求めた確率から上記差分確率を求める手段と、
を備えることを特徴とする加算の差分確率計算装置。
【請求項２】
２つの入力のあるいくつかのビットが変化した時に、これら２つの入力の和（出力）のあるいくつかのビットが変化する確率（差分確率）を計算する装置であって、
上記２つの入力の各差分値と、出力の差分値が入力され、
これら３つの差分値の排他的論理和を演算して各ビットへの繰り上がり（ｃａｒｒｙ）の差分値を計算する繰り上がり差分演算手段と、
上記２つの入力差分値のｉビット目の値（ｉ＝０，１，２，…，ｎ−２、ｎは各入力のビット数）と、上記出力差分値のｉビット目の値との和を演算する和演算手段と、
上記和演算手段の演算結果と上記繰り上がり差分値のｉ＋１ビット目の値とから、そのｉ＋１ビット目の値となる確率を求める手段と、
上記各ｉについて求めた確率から上記差分確率を求める手段と、
を備えることを特徴とする加算の差分確率計算装置。
【請求項３】
請求項１又は２記載の装置において、
上記２つの入力差分値、上記出力差分値、上記繰り上がり差分値、確率Ｐ、パラメータｉを記憶する記憶手段と、
記憶手段から読出し、上記繰り上がり差分演算手段を実行させ、繰り上がり差分演算手段の演算結果を記憶手段に記憶し、上記和演算手段を実行させ、上記求めた確率により、記憶手段内の確率を更新させるなどの制御を行う制御手段とを備え、
上記確率を求める手段及び上記差分確率を求める手段は、上記和演算結果が０で、上記繰り上がり差分値のｉ＋１ビット目の値が１であれば確率Ｐを０とし、ｉ＋１ビット目の値が０であればｉを＋１し、
上記和演算結果が１又は２であれば、上記確率Ｐを１／２してその値に確率Ｐを更新し、上記和演算結果が３で、上記繰り上がり差分値のｉ＋１ビット目の値が０であれば上記確率Ｐを０とし、ｉ＋１ビット目の値が１であればｉを＋１し、ｉ＝０からｉ＝ｎ−２について、ｉ＝０における確率Ｐを１に初期化して上記処理を順次行って得られた上記確率Ｐを上記差分確率とする手段であることを特徴とする加算の差分確率計算装置。
【請求項４】
請求項１又は２記載の装置において、
上記２つの入力差分値、上記出力差分値、上記繰り上がり差分値、確率を２のべき乗で表現した時の指数部Ｐ、パラメータｉを記憶する記憶手段と、
記憶手段から読出し、上記繰り上がり差分演算手段を実行させ、繰り上がり差分演算手段の演算結果を記憶手段に記憶し、上記和演算手段を実行させ、上記求めた確率の指数部により、記憶手段内の確率の指数部Ｐを更新させるなどの制御を行う制御手段とを備え、
上記確率を求める手段及び上記差分確率を求める手段は、上記和演算結果が０で、上記繰り上がり差分値のｉ＋１ビット目の値が１であれば上記差分確率を０とし、ｉ＋１ビット目の値が０であればｉを＋１し、
上記和演算結果が１又は２であれば、上記確率の指数部Ｐを＋１してその値に確率の指数部Ｐを更新し、上記和演算結果が３で、上記繰り上がり差分値のｉ＋１ビット目の値が０であれば上記差分確率を０とし、ｉ＋１ビット目の値が１であればｉを＋１し、ｉ＝０からｉ＝ｎ−２について、ｉ＝０における確率の指数部Ｐを０に初期化して上記処理を順次行って得られた上記確率の指数部Ｐを用いて２-Pを演算して上記差分確率とする手段であることを特徴とする加算の差分確率計算装置。
【請求項５】
請求項１乃至４の何れかに記載の加算の差分確率計算装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えば加算が利用されている暗号装置および暗号化方法の差分解読法およびその拡張に対する強度評価をするために用いられ、加算の差分確率を計算する装置およびそのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
データを秘匿するためには暗号化技術が有効である。暗号化の方法は共通鍵暗号と公開鍵暗号がある。高速かつ安全な共通鍵暗号を構成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。ブロック暗号に対する攻撃法の一つとして「差分解読法」が文献、「Ｅ．Ｂｉｈａｍ，Ａ．Ｓｈａｍｉｒ：“Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｃｒｙｐｔａｎａｌｙｓｉｓ  ｏｆ  ＤＥＳ−ｌｉｋｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ，”Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ，Ｖｏｌ．４，Ｎｏ．１，ｐｐ．３−７２」で提案されている。この差分解読法に対するブロック暗号の強度を評価するためには、ブロック暗号で用いられている個々の演算について、入力が変化した時の各出力の変化の傾向を調べる必要がある。一般にはこれらの差分確率の偏りが小さいほど（＝これらの差分確率の最大値が小さいほど）暗号強度が高いものとなる。具体的には、入力のあるいくつかのビットが変化した時に（この変化分を入力差分値と呼ぶ）、出力のあるいくつかのビットが変化する（この変化分を出力差分値と呼ぶ）差分確率を、全ての入力差分値と全ての出力差分値について計算する。
【０００３】
この発明は例えば多くのブロック暗号に利用されている「加算」の差分解率を計算する方法に関する。
ｘ，ｙ，ｚをｎビットデータとし、２ｎ  を法とする加算ｆ
ｆ（ｘ，ｙ）＝ｘ＋ｙ＝ｚ  （ｍｏｄ  ２ｎ  ）
を考える。また、ｘ＊  ，ｙ＊  ，ｚ＊  もｎビットデータとし、ｘ，ｙ，ｚがそれぞれｘ＊  ，ｙ＊  ，ｚ＊  に変化した時、Δｘ＝ｘ（＋）ｘ＊  ，Δｙ＝ｙ（＋）ｙ＊  ，Δｚ＝ｚ（＋）ｚ＊  をそれぞれｘ，ｙ，ｚの差分値と呼ぶ。ここでＡ（＋）ＢはＡとＢとの排他的論理和演算を示す。この時、加算の差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）を以下のように定義する。
定義１（加算の差分確率）
ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝Ｐｒｘ，ｙ  ［（ｆ（ｘ，ｙ）（＋）ｆ（ｘ（＋）Δｘ，ｙ（＋）Δｙ））＝Δｚ］          （１）
従来の加算の差分確率の計算方法は、与えられたΔｘ，Δｙ，Δｚについて、入力ｘ，ｙのそれぞれ全てのｎビットの値（合計２２ｎ通り）について式（２）
（ｆ（ｘ，ｙ）（＋）ｆ（ｘ（＋）Δｘ，ｙ（＋）Δｙ））＝Δｚ    （２）
が成り立つか調べることで計算する方法であり、必要な計算量はＯ（２２ｎ）（２２ｎのオーダ）であった。この方法は加算の入出力ビット数が８ビット、すなわちｎ＝８の場合などｎが小さい時は実行可能であるが、ｎ＝３２などになると、個人のもつ計算機能力では現実的に実行不可能であった。
【０００４】
加算の差分特性については文献「Ｋ．Ａｏｋｉ，Ｋ．Ｋｏｂａｙａｓｈｉ，Ｓ．Ｍｏｒｉａｉ，“Ｔｈｅ  Ｂｅｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ  Ｓｅａｒｃｈ  ｏｆ  ＦＥＡＬ，”ＩＥＩＣＥ  Ｔｒａｎｓ．  Ｆｕｎｄａｍｅｎｔａｌｓ，  ｖｏｌ．  Ｅ８１−Ａ，ｎｏ．１，ｐｐ．９８−１０４，１９９８．」などで研究されているが、ここで示された性質を利用しても差分確率の計算は数倍程度しか高速化できない。
また、関連する研究として、加算の入力の１つが固定である場合に、与えられた入出力差分値に対する差分確率を求める方法が文献「宮野  浩「加法の差分特性の加算数依存性」、電子情報通信学会技術研究報告、ＩＳＥＣ９６−１，１９９６年５月．」で示されている。これに対しこの発明は加算の２つの入力がともに変化する場合の差分確率を求める方法を対象とする。
【０００５】
【発明が解決しようとする課題】
近年、ブロック暗号の安全性を高めるためにブロック長が６４ビットから１２８ビットに拡大され、それとともに入出力ビット数が３２ビットの加算がＭＡＲＳ，ＲＣ６，Ｔｗｏｆｉｓｈなど多くのブロック暗号で利用されている。
この発明の目的は、２ｎ  を法とするｎビット入出力の加算について、入出力差分値が与えられた時にその差分確率を、計算量が従来のＯ（２２ｎ）よりも格段と少ないＯ（ｎ）で計算することができる装置及び方法、およびプログラム記録媒体を提供することにある。
【０００６】
【課題を解決するための手段】
この発明では加算の入力ｘ，ｙのそれぞれ全てのｎビットの値（合計２２ｎ通り）について式（２）を計算することなく、与えられた入出力差分値Δｘ，Δｙ，Δｚのみから、式（１）で定義される差分確率を計算する。
ｘ，ｙ，ｚの２進表現の下位からｉビット目をそれぞれｘｉ  ，ｙｉ  ，ｚｉ  とおく。但し、最下位ビットはｘ０  ，ｙ０  ，ｚ０  とする。ｘｉ  ，ｙｉ  ，ｚｉ  についても同様にそれぞれの差分値Δｘｉ  ，Δｙｉ  ，Δｚｉ  を定義する。
【０００７】
また、ｉビット目への繰り上がり（ｃａｒｒｙ）をｃｉ  とする。ｘやｙに差分が発生した時、各ビットへのｃａｒｒｙにも差分が生じる。この時、ｉビット目へのｃａｒｒｙ（ｃｉ  ）の差分値をΔｃｉ  とする。
まず、各ビットへの繰り上がり（ｃａｒｒｙ）の差分を式（３）
Δｃｉ  ＝Δｘｉ  （＋）Δｙｉ  （＋）Δｚｉ              （３）
により計算する。次に０以上ｎ−２以下の各ｉに対して（Δｘｉ  ，Δｙｉ  ，Δｃｉ  ）の値の組み合わせとΔｃｉ＋１  の値からΔｃｉ＋１  が０または１となる確率を求める。この確率は（Δｘｉ  ，Δｙｉ  ，Δｚｉ  ）の値の組み合わせとΔｃｉ＋１  の値からΔｃｉ＋１  が０または１となる確率を求めてもよい。これらの確率の積をとることで加算の差分確率を計算する。つまり入力ｘ，ｙの変化にともなう出力ｚの変化（Δｚ）は、繰り上がり（ｃａｒｒｙ）ｃの変化（Δｃ）に表れるので、０以上ｎ−２以下の各ｉに対してΔｃｉ＋１  が０または１となる確率を求めることにより加算の差分確率を計算できる。
作用
この発明により加算の差分確率が計算できる理由を示す。
【０００８】
まず、式（３）が成り立つ理由は以下の通りである。
定理１  ０＜ｉ＜ｎ−１について、
Δｘｉ  （＋）Δｙｉ  （＋）Δｃｉ  ＝Δｚｉ  
が成り立つ。
証明  ０＜ｉ＜ｎ−１について、ｘｉ  ，ｙｉ  ，ｃｉ  ，ｚｉ  の間に下記の関係式が成り立つ。同様にｘｉ  ＊  ，ｙｉ  ＊  ，ｃｉ  ＊  ，ｚｉ  ＊  の間に下記の関係式が成り立つ。
【０００９】
ｘｉ  （＋）ｙｉ  （＋）ｃｉ  ＝ｚｉ  ，
ｘｉ  ＊  （＋）ｙｉ  ＊  （＋）ｃｉ  ＊  ＝ｚｉ  ＊
これらの２つの式の辺々の排他的論理和をとることで証明される。
次に（Δｘｉ  ，Δｙｉ  ，Δｃｉ  ）の値の組み合わせとΔｃｉ＋１  の値からΔｃｉ＋１  が０または１となる確率を定理２に示す。
定理２  １＜ｉ＜ｎ−１について、（Δｘｉ  ，Δｙｉ  ，Δｃｉ  ）の値の組み合わせが与えられた時、Δｃｉ＋１  は以下のように決まる。
【００１０】
0003628230.tif 000002
で与えられることから、（ｘｉ  ，ｙｉ  ，ｃｉ  ）の値の組み合わせによりｃｉ＋１  は決まる。すなわち、（ｘｉ  ，ｙｉ  ，ｃｉ  ）の値を並べかえてもｃｉ＋１  が０または１をとる確率は同じである。よって、（Δｘｉ  ，Δｙｉ  ，Δｃｉ  ）の値を並べかえてもΔｃｉ＋１  が０または１をとる確率は同じとなる。上記の表は式（４）
Δｃｉ＋１  ＝（ｘｉ  ｙｉ  （＋）ｙｉ  ｃｉ  （＋）ｃｉ  ｘｉ  ）（＋）（ｘｉ  ＊  ｙｉ  ＊  （＋）ｙｉ  ＊  ｃｉ  ＊  （＋）ｃｉ  ＊  ｘｉ  ＊  ）    （４）
により得られる。
系１（定理２：ｉ＝０の場合）（Δｘ０  ，Δｙ０  ）の値の組み合わせが与えられた時、Δｃ１  は以下のように決まる。
【００１１】
0003628230.tif 000003
証明  最下位ビットへのｃａｒｒｙは常に０（ｃ０  ＝０）である。よってΔｃ０  ＝０が成り立つことから明らか。
【００１２】
次に（Δｘｉ  ，Δｙｉ  ，Δｚｉ  ）の値の組み合わせとΔｃｉ＋１  の値からΔｃｉ＋１  が０または１となる確率を定理３に示す。
定理３  １＜ｉ＜ｎ−１について、（Δｘｉ  ，Δｙｉ  ，Δｚｉ  ）の値の組み合わせが与えられた時、Δｃｉ＋１  は以下のように決まる。
0003628230.tif 000004
証明  定理１を用いて定理２を定理３のように書きかえることができることから明らかである。例えばΔｘｉ  ＝０，Δｙｉ  ＝１，Δｃｉ  ＝０の場合は定理３の（Δｘｉ  ，Δｙｉ  ，Δｚｉ  ）＝（０，１，１）に対応する。
系２（定理３：ｉ＝０の場合）（Δｘ０  ，Δｙ０  ，Δｚ０  ）の値の組み合わせが与えられた時、Δｃ１  は以下のように決まる。
【００１３】
0003628230.tif 000005
証明  Δｃ０  は常に０であることから明らか。なお（０，０，１）、（１，１，１）の各状態は存在し得ない場合であり（これらの場合Δｃ０＝１となるため）、当然Δｃ１  は考えられず、確率は０となる。
【００１４】
【発明の実施の形態】
実施例１
この発明の実施例１として、系１および定理２を利用して加算の差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）を計算する装置を図１に示す。
この装置には２つの入力の差分値Δｘ，Δｙと出力の差分値Δｚが入力部１１に入力され、これら差分値Δｘ，Δｙ，Δｚは記憶部１２に格納される。制御部１３はプログラムメモリ１９内のプログラムを読出し、解釈実行して、記憶部１２からΔｘ，Δｙ，Δｚを読出して、Δｃ演算手段１４で排他的論理和演算し、その演算結果を繰り上がり差分値Δｃとして記憶部１２に格納し、また各ｉビット目（ｉ＝０，１，…，ｎ−２、ｎは入力ｘ，ｙの各ビット数）のΔｘｉ  ，Δｙｉ  ，Δｃｉを記憶部１２から取出して、これらを加算手段１５で加算し、その加算値Ａと、繰り上がり差分値Δｃのｉ＋１ビット目Δｃｉ＋１  とからＰ計算手段１６で確率又はその確率を２のべき乗で表現した時の指数部（の絶対値）を計算し、記憶部１２内のＰの値を更新し、かつｉの値を＋１して更新する。ｉ＝ｎ−２に対する処理が終ると、Ｐが確率の場合はその値を差分確率として出力部１７から出力し、Ｐが確率の指数部の場合はそのＰで確率計算手段１８で２−Ｐを演算して、差分確率として出力部１７から出力する。
【００１５】
これら各制御部１３内の各機能を個別に設けて、これらを制御部１３が順次動作させてもよい。
次に図２を参照して図１の装置の処理手順を説明する。
Ｓｔｅｐ．１−１  入力部１１に入力されたΔｘ，Δｙ，Δｚを取込んで記憶部１２に格納する。
Ｓｔｅｐ．１−２  定理１によりΔｃｉ  （０＜ｉ＜ｎ）を求める。つまり記憶部１２からΔｘ，Δｙ，Δｚを取出し、Δｃ＝Δｘ（＋）Δｙ（＋）ΔｚをΔｃ計算手段１４で計算して全ｎビットのｃａｒｒｙの差分値を同時に求める。
【００１６】
Ｓｔｅｐ．２−１  そのΔｃの０ビット目Δｃ０  ＝１か否かを調べ、１であれば差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝０となるので（Δｃ０  ＝０に矛盾するため）、終了。
Ｓｔｅｐ．２−２  Δｃ０  ＝１でなければΔｃを記憶部１２に一旦記憶する。
Ｓｔｅｐ．３  与えられたΔｘ，Δｙの値とＳｔｅｐ．１で求めたΔｃｉ  （０＜ｉ＜ｎ−２）を用いて、系１および定理２により、ＤＰｆ  （Δｘ，Δｙ，Δｚ）を求める。
【００１７】
Ｓｔｅｐ．３−１  ビット番号パラメータｉと確率パラメータＰをそれぞれｉ＝０、Ｐ＝１と初期化し、これらを記憶部１２に保持する。
Ｓｔｅｐ．３−２  Δｘｉ  ，Δｙｉ  ，Δｃｉ  を記憶部１２から取出し、これらの値の和Δｘｉ  ＋Δｙｉ  ＋Δｃｉ  ＝Ａを加算手段１５で計算する。
Ｓｔｅｐ．３−３  Ａが０か否かを調べる。
Ｓｔｅｐ．３−４  Ａ＝０であればΔｃｉ＋１  を記憶部１２から取出して、Δｃｉ＋１  が１か否かを調べる。
【００１８】
Ｓｔｅｐ．３−５  Δｃｉ＋１  ＝１であればＰ＝０とし、
Ｓｔｅｐ．３−６  Δｃｉ＋１  ＝０ならば、記憶部１２内のｉをｉ＝ｉ＋１に更新する。
Ｓｔｅｐ．３−７  その更新されたｉがｎ−１と等しいかを調べ、等しくなければ、Ｓｔｅｐ３−２に戻り、等しければＳｔｅｐ．４に進む。
Ｓｔｅｐ．３−８  Ｓｔｅｐ３−３でＡが０でなければＡが１又は２であるかを調べる。
【００１９】
Ｓｔｅｐ．３−９  Ａが１又は２であれば記憶部１２内のＰをＰ＝１／２Ｐに更新してＳｔｅｐ．３−６に移る。
Ｓｔｅｐ．３−１０  Ｓｔｅｐ．３−８でＡが１又は２でなければ、つまりＡ＝３であれば、記憶部１２内のΔｃｉ＋１  を取出してΔｃｉ＋１  が０であるか否かを調べ、Δｃｉ＋１  ＝０であればＳｔｅｐ．３−５へ移りつまりＰ＝０とし、またΔｃｉ＋１  ＝１ならばＳｔｅｐ．３へ移りｉをｉ＝ｉ＋１に更新する。
【００２０】
Ｓｔｅｐ．４  ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝Ｐとして出力部１７から出力して終了する。
なおＳｔｅｐ．３−３乃至Ｓｔｅｐ．３−１０の処理はＰ計算手段１６により行われる。
以上のＳｔｅｐ．３−２乃至Ｓｔｅｐ．４の処理を要約すると以下のようになる。
【００２１】
つまりΔｘｉ  ＋Δｙｉ  ＋Δｃｉ  ＝Ａを加算し、
Ａ＝０であれば、Δｃｉ＋１  が１か否かに応じてＰ＝０とするか、ｉ←ｉ＋１とし、
Ａ＝１又は２であれば、Ｐ←Ｐ／２としてｉ←ｉ＋１とし、
Ａ＝３であればΔｃｉ＋１  が０か否かに応じてＰ＝０とするか、ｉ←ｉ＋１とすることを、
ｉ＝０から、ｉ＝ｎ−２まで行い、その途中でＰ＝０となってＤＰｆ  （Δｘ，Δｙ，Δｚ）＝０として終了しない場合はｉ＝ｎ−２の時のＰをＤＰｆ  （Δｘ，Δｙ，Δｚ）として出力する。
【００２２】
上述したようにＤＰｆ  （Δｘ，Δｙ，Δｚ）は２のべきで表されるので、Ｓｔｅｐ．３−９におけるＰの計算はシフト演算を利用できる。すなわち、Ｐに１／２を乗じる演算は、Ｐを右１ビットシフトに対応させればよい。
また、ＤＰｆ  （Δｘ，Δｙ，Δｚ）は２のべきで表されることからＰ計算手段１６では指数部を計算してもよい。この場合、乗算またはシフトでなく、加算で計算できる。これを実施例２とする。
実施例２
ブロック機能構成としては図１に示した装置と同様であるが、主としてＰ計算手段１６における処理が異なり、また確率計算手段１８が設けられる。
【００２３】
処理手順において、Ｓｔｅｐ．１−１乃至Ｓｔｅｐ．２−２は図２と同様である。
Ｓｔｅｐ．３  与えられたΔｘ，Δｙの値とＳｔｅｐ．１で求めたΔｃｉ  （０＜ｉ＜ｎ−２）を用いて、系１および定理２により、ＤＰｆ  （Δｘ，Δｙ，Δｚ）を求める。
Ｓｔｅｐ．３−１でｉ＝０とするがＰ＝１ではなく、Ｐ＝０と初期化する。
【００２４】
Ｓｔｅｐ．３−２  ｉ＝ｎ−２まで以下の処理を行なう。
Δｘｉ  ＋Δｙｉ  ＋Δｃｉ  ＝Ａが
０の時、Δｃｉ＋１  ＝０ならば
ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝０とし、終了。
Δｃｉ＋１  ＝１ならば
ｉ＝ｉ＋１としてＳｔｅｐ．３−２に戻る。
【００２５】
１，２の時、Ｐ＝Ｐ＋１とし、ｉ＝ｉ＋１として
Ｓｔｅｐ．３−２を繰り返す。
３の時、Δｃｉ＋１  ＝０ならば
ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝０とし、終了。
Δｃｉ＋１  ＝１ならば
ｉ＝ｉ＋１としてＳｔｅｐ．３−２に戻る。
【００２６】
Ｓｔｅｐ．４−１  ｉ＝ｎ−２で求めたＰを用いて確率計算部１８で２−Ｐを計算する。
Ｓｔｅｐ．４−２  ２−ＰをＤＰｆ  （Δｘ，Δｙ，Δｚ）として出力部１７から出力する。
この場合の図２と対応した処理手順を図３に図２と異なる部分があるＳｔｅｐ．３−１から示し、対応する部分に同一のＳｔｅｐ番号を付けてある。だだしＳｔｅｐ．３−１では先に述べたようにＰ＝０とする点が異なり、Ｓｔｅｐ．３−４でΔｃｉ＋１  ＝１であればＳｔｅｐ．４−３でＤＰｆ  （Δｘ，Δｙ，Δｚ）＝０として出力して終了し、Ｓｔｅｐ．３−９ではＰをＰ＋１に更新し、Ｓｔｅｐ．３−１０でΔｃｉ＋１  ＝０であればＳｔｅｐ．４−３に移り、Ｓｔｅｐ．３−７でｉ＝ｎ−１であればＳｔｅｐ．４−１に移り、その時のＰを用いて確率計算手段１８で２−Ｐを計算し、Ｓｔｅｐ．４−２で２−ＰをＤＰｆ  （Δｘ，Δｙ，Δｚ）として出力部１７より出力する点が図２と異なる。
【００２７】
次に実施例３として、系２および定理３を利用して加算の差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）を計算する方法を示す。
実施例３
Δｘ，Δｙ，Δｚの値が与えられた時、定理１、定理３を用いて加算の差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）を求める例を以下に示す。
ブロック機能構成としては図１に示した装置と同様であるが加算演算手段１５でΔｘｉ  ＋Δｙｉ  ＋Δｚｉ  ＝Ａを演算する点が異なる。
【００２８】
処理手順において、Δｘ，Δｙ，Δｚの取込みからΔｃ０  の判定までは図２と同一である。
Ｓｔｅｐ．１  定理１によりΔｃｉ  （０＜ｉ＜ｎ）を求める。Δｃ＝Δｘ（＋）Δｙ（＋）Δｚを計算すれば全ｎビットのｃａｒｒｙの差分値が同時に得られる。
Ｓｔｅｐ．２  Δｃ０  ＝１ならば、ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝０となるので（Δｃ０  ＝０に矛盾するため）、終了。
【００２９】
Ｓｔｅｐ．３  与えられたΔｘ，Δｙ，Δｚの値とＳｔｅｐ．１で求めたΔｃｉ  （０＜ｉ＜ｎ−２）を用いて、系２および定理３により、ＤＰｆ  （Δｘ，Δｙ，Δｚ）を求める。
Ｓｔｅｐ．３−１  ｉ＝０，Ｐ＝１と初期化する。
Ｓｔｅｐ．３−２  ｉ＝ｎ−２まで以下の処理を行なう。
Δｘｉ  ＋Δｙｉ  ＋Δｚｉ  の値が
０の時、Δｃｉ＋１  ＝１ならば
Ｐ＝０とし、Ｓｔｅｐ．４へ。
【００３０】
Δｃｉ＋１  ＝０ならば
ｉ＝ｉ＋１としてＳｔｅｐ．３−２に戻る。
１，２の時、Ｐ＝１／２Ｐとし、ｉ＝ｉ＋１として
Ｓｔｅｐ．３−２を繰り返す。
３の時、Δｃｉ＋１  ＝０ならば
Ｐ＝０とし、Ｓｔｅｐ．４へ。
【００３１】
Δｃｉ＋１  ＝１ならば
ｉ＝ｉ＋１としてＳｔｅｐ．３−２に戻る。
Ｓｔｅｐ．４  その時のＰを加算の差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝Ｐとして出力部１７より出力する。
この場合は図２と対応した処理手順を図４に、Ｓｔｅｐ．３−１以下から示し、同一の処理は同一Ｓｔｅｐ番号を付けて重複説明を省略した。図２に対し、Ｓｔｅｐ．３−２においてΔｘｉ  ＋Δｙｉ  ＋Δｚｉ  ＝Ａを演算している点が異なるだけである。
【００３２】
ＤＰｆ  （Δｘ，Δｙ，Δｚ）は２のべきで表されるので、Ｓｔｅｐ．３−９におけるＰの計算はシフト演算を利用できる。すなわち、１／２を乗じる演算を、Ｐの右１ビットシフトに対応させればよい。
また、ＤＰｆ  （Δｘ，Δｙ，Δｚ）は２のべきで表されることから実施例２と同様に指数部のみを計算してもよい。この場合、乗算またはシフトでなく、加算で計算できる。この場合の処理手順は図３中のＳｔｅｐ．３−２においてΔｘｉ  ＋Δｙｉ  ＋Δｚｉ  ＝Ａを演算する点が異なるだけでその他は同様に処理すればよい。
数値例
次に具体的数値例を上げて処理を説明する。いま図５（Ａ）に示すようにΔｘ＝００１０１１１０、Δｙ＝０１０１１０００、Δｚ＝１０１１１０００が入力されたとする。
【００３３】
Ｓｔｅｐ．１  Δｃ演算手段１４においてΔｃ＝Δｘ（＋）Δｙ（＋）Δｚを計算し、この結果Δｃ＝１１１０１１１０を記憶部１２に記憶する。
Ｓｔｅｐ．２  記憶部１２に記憶したΔｃの最下位ビットが１ならば、ＤＰｆ  （Δｘ，Δｙ，Δｚ）＝０となるので終了するが、この例ではΔｃの最下位ビットは０であるからＳｔｅｐ．３に進む。
Ｓｔｅｐ．３  記憶部１２からΔｘ，Δｙ，Δｚ，Δｃの値を１ビットずつ最下位から順に取出して加算の差分確率を計算していく。求める確率を２のべき乗で表現した時の指数の絶対値をＰで表し、記憶部１２に記憶する。
【００３４】
Ｓｔｅｐ．３−１  Ｐを０に初期化する。
Ｓｔｅｐ．３−２  Δｘ，Δｙ，Δｚの取出した同一位置のビットの和Ａを求める。
Ａ＝０の時、Δｃの一つ上位のビットが１ならば
出力部１７からＤＰｆ  （Δｘ，Δｙ，Δｚ）として０を出力して終了。
図５（Ａ）の例では最下位ビットの和Ａが０であり、かつΔｃの一つ上位ビットが１であるからＤＰｆ  （Δｘ，Δｙ，Δｚ）を０として出力して終了する。
【００３５】
Δｃの一つ上位のビットが０ならば
Ｓｔｅｐ．３−２に戻り、一つ上位のビットについて同様の処理を行なう。
Ａ＝１又は２の時、Ｐを１増やしてＳｔｅｐ３−２に戻り、一つ上位のビットについて同様の処理を行なう。
Ａ＝３の時、Δｃの一つ上位のビットが０ならば
出力部１７からＤＰｆ  （Δｘ，Δｙ，Δｚ）として０を出力して終了。
【００３６】
Δｃの一つ上位のビットが１ならば
Ｓｔｅｐ．３−２に戻り、一つ上位のビットについて同様の処理を行なう。
Ｓｔｅｐ．４  Δｃの最上位ビットのチェックが終れば、出力部１７からＤＰｆ  （Δｘ，Δｙ，Δｚ）＝２−Ｐを出力して終了する。
図５（Ｂ）に示す例ではΔｃは１１０１１１００となり、ステップ３において最下位ビット（ｉ＝０）のΔｘ０  ＝０、Δｙ０  ＝０、Δｚ０  ＝０を取出し、これらの加算値Ａを求めるとＡ＝０であり、またΔｃ１  ＝０であるから、ｉ＝１とされる。
【００３７】
よってΔｘ１  ＝１、Δｙ１  ＝０、Δｚ１  ＝１が取出され、これらの和Ａは２であるからＰ＝０＋１＝１とされ、ｉ＝２とされる。
Δｘ２  ＝１、Δｙ２  ＝０、Δｚ２  ＝０が取出され、これらの和Ａ＝１であり、Ｐ＝１＋１＝２とされ、ｉ＝３とされる。
Δｘ３  ＝１、Δｙ３  ＝１、Δｚ３  ＝１が取出され、これらの和Ａ＝３であり、Δｃ４  ＝１であるからｉ＝４とされる。
【００３８】
以下同様に処理され、この数値例ではＰは図５（Ｂ）に示すように１，２，２，３，４，５と変化し、ｉ＝６でΔｃの最上位ビットΔｃ７  のチェックが終り、この時Ｐ＝５となる。
Ｓｔｅｐ．４  確率計算手段１８で２−５が計算され、出力部１７からＤＰｆ  （Δｘ，Δｙ，Δｚ）として２−５が出力される。
【００３９】
【発明の効果】
以上述べたように、この発明では、加算の入力ｘ，ｙそれぞれ全てのｎビットの値（合計２２ｎ通り）について式（２）を計算することなく、与えられた入出力差分値Δｘ，Δｙ，Δｚのみから式（１）で定義される差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）を計算することができる。
従来法では差分確率ＤＰｆ  （Δｘ，Δｙ，Δｚ）を求める計算量はＯ（２２ｎ）であったが、この発明により、計算量はＯ（ｎ）と大幅に改善された。
【００４０】
特に、例えばｎ＝３２など入出力ビット数が大きい場合、従来は現実的に計算不可能であった差分確率を容易に求めることが可能となった。
【図面の簡単な説明】
【図１】この発明の実施例の機能構成を示すブロック図。
【図２】図１に示した装置でΔｘｉ  ，Δｙｉ  ，Δｃｉ  の和を用いる処理手順の一例を示す流れ図。
【図３】図１に示した装置で確率の指数部をパラメータとした場合の処理手順の例を示す流れ図。
【図４】図１に示した装置でΔｘｉ  ，Δｙｉ  ，Δｚｉ  の和を用いる処理手順の一例を示す流れ図。
【図５】この発明の実施例を具体的数値に適用した各値を示す図。
【図１】
0003628230.tif 000006
【図２】
0003628230.tif 000007
【図３】
0003628230.tif 000008
【図４】
0003628230.tif 000009
【図５】
0003628230.tif 000010