(57)【要約】  少なくとも１つのデータ処理デバイス、特に少なくとも１つの埋め込みシステム、例えば少なくとも１つのチップカード又はスマートカードを、少なくとも１つの攻撃、特に少なくとも１つの電磁放射攻撃から保護するための装置及び方法であって、上記データ処理デバイスは、計算、特に暗号演算を行う少なくとも１つの集積回路を備え、上記電磁放射攻撃は秘密鍵を見つけ出すことを目的とし、安全に回避すべきものであり、上記装置及び方法を更に発展させるために、少なくとも１つのＦ−証明で上記計算をチェックすることを提案する。
2008533791.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのデータ処理デバイス、特に少なくとも１つの埋め込みシステム、例えば少なくとも１つのチップカード又はスマートカードを、少なくとも１つの攻撃、特に少なくとも１つの電磁放射攻撃から保護する装置であって、前記データ処理デバイスが、計算、特に暗号演算を実行する少なくとも１つの集積回路を備えた装置において、
前記計算を少なくとも１つのＦ−証明でチェックすることを特徴とする装置。
【請求項２】
請求項１に記載の装置において、前記Ｆ−証明が１６進法用に設計されていることを特徴とする装置。
【請求項３】
請求項１又は請求項２に記載の装置において、前記計算において前記Ｆ−証明によって少なくとも１つのエラーが発見されると、前記データ処理デバイスへのアクセスを拒否することを特徴とする装置。
【請求項４】
請求項１〜請求項３のいずれか１つに記載の装置において、前記計算がリベスト−シャミア−エーデルマン（ＲＳＡ）アルゴリズム及び／又は楕円曲線暗号（ＥＣＣ）アルゴリズムに基づくことを特徴とする装置。
【請求項５】
データ処理デバイス、特に埋め込みシステム、例えばチップカード又はあるスマートカードであって、計算、特に暗号演算を実行する少なくとも１つの集積回路を備えたデータ処理デバイスにおいて、
少なくとも１つのＦ−証明で前記計算をチェックすることによって、前記集積回路を少なくとも１つの攻撃、特に少なくとも１つの電磁放射攻撃から保護することを特徴とするデータ処理デバイス。
【請求項６】
少なくとも１つのデータ処理デバイス、特に少なくとも１つの埋め込みシステム、例えば少なくとも１つのチップカード又はスマートカードを、少なくとも１つの攻撃、特に少なくとも１つの電磁放射攻撃から保護する方法であって、前記データ処理デバイス、特に前記データ処理デバイスの少なくとも１つの集積回路が計算、特に暗号演算を実行する方法において、
前記計算を少なくとも１つのＦ−証明でチェックすることを特徴とする方法。
【請求項７】
請求項６に記載の方法において、前記Ｆ−証明が１６進法用に設計されていることを特徴とする方法。
【請求項８】
請求項６又は請求項７に記載の方法において、前記計算において前記Ｆ−証明によって少なくとも１つのエラーが発見されると、前記データ処理デバイスへのアクセスを拒否することを特徴とする方法。
【請求項９】
請求項６〜請求項８のいずれか１つに記載の方法において、前記計算がリベスト−シャミア−エーデルマン（ＲＳＡ）アルゴリズム及び／又は楕円曲線暗号（ＥＣＣ）アルゴリズムに基づくことを特徴とする方法。
【請求項１０】
請求項５に記載の少なくとも１つのデータ処理デバイスにおける、請求項１〜請求項４のいずれか１つに記載の少なくとも１つの装置及び／又は請求項６〜請求項８のいずれか１つに記載の方法の使用法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、暗号解析を阻止する技術分野に関するものであり、特に、少なくとも１つのデータ処理デバイスを少なくとも１つの電磁放射攻撃から保護する技術分野に関するものである。
【０００２】
本発明は具体的には、少なくとも１つのデータ処理デバイス、特に少なくとも１つのチップカード又はスマートカード等の少なくとも１つの埋め込みシステムを、少なくとも１つの攻撃、特に少なくとも１つの電磁放射攻撃から保護するための装置及び方法であって、このデータ処理デバイスが、計算、特に暗号演算を行う少なくとも１つの集積回路を備えている装置及び方法に関するものである。
【背景技術】
【０００３】
データ処理デバイス、特にチップカード又はスマートカード等の埋め込みシステムは、ＰＫＩ（公開鍵基盤）システムを用いて鍵を交換し、そして秘密鍵を見つけ出すことを目的とするいくつかの形の攻撃から保護しなければならない。
かかる攻撃の１つは、むき出しの（従って感光性の）チップに、
１つ以上の光源又は
ある種の電磁放射源
を指向させることにより、計算、特に暗号演算に影響を与えることである。
【０００４】
【特許文献１】独国特許公開第４０１８６８８号明細書
【０００５】
機械的なチップ又は電子光線若しくはレーザ光線による極秘データの読み出しから集積回路を保護するために、従来技術文献である独国特許公開第４０１８６８８号明細書は、集積回路の感光性の部分に保護層を設けること、及びこの保護層の容量、誘導性、又は抵抗が外部からの侵害により変化していないか周期的にチェックすることを提案している。
【０００６】
【特許文献２】特開平１１−００８６１６号明細書
【０００７】
特開平１１−００８６１６号明細書は、中国人剰余定理を用いることによって高速に署名作成処理を行うＩＣ（集積回路）カードの欠陥を利用する攻撃に対して、このＩＣカードの安全性を高めることを開示している。
【０００８】
【特許文献３】欧州特許公開第１２３３３７２号明細書
【０００９】
欧州特許公開第１２３３３７２号明細書によれば、不正及び／又は操作からチップ装置を保護する電気回路又は電子回路装置及び方法を提供するために、検出器ユニットの出力電圧がこの検出器ユニット上への入射光の尺度である検出器ユニット、及びこの検出器ユニットに後続し、この検出器ユニットの出力電圧と基準電圧とを比較するために設けた比較器ユニットを配置している。このようにして、検出器の出力電圧と基準電圧との比較中に故障メッセージが発生した場合に、保護すべきチップ装置のデータ及び／又は機能を一時的又は永久に遮断及び／又は消去及び／又はブロック及び／又は中断する。
【００１０】
【特許文献４】欧州特許公開第１３２６２０３号明細書
【００１１】
欧州特許公開第１３２６２０３号は、回路のデジタル部分を保護するための方法及び装置に関するものである。この方法及び装置は特に、かかるデジタル回路内のメモリユニット、特に秘密データを含むスマートカードコントローラ内のメモリユニットを、回路のデジタル部分、特にスマートカードコントローラのデジタル部分を、例えば光フラッシュ攻撃による短時間の電圧降下によって未定義状態に変化させる攻撃から保護するために用いることができる。
【００１２】
【特許文献５】英国特許公開第２３１９１５０号明細書
【００１３】
英国特許公開第２３１９１５０号は、関連するセキュリティ方法を伴う認証方法を提案する。この認証方法は、秘密鍵アルゴリズムを施した乱数から計算結果を得るステップを含む。上記セキュリティ方法は、上記秘密鍵アルゴリズムを施した基準乱数からテスト結果を計算するステップと、このテスト結果と基準結果を比較するステップと、このテスト結果がこの基準結果と同一であるときのみに計算結果を送ることを保証するステップとを含む。
【００１４】
上述した欠点及び短所から始まり、以上で説明した従来技術を考慮すれば、本発明の目的は、技術分野の所で述べた種類の装置及び方法を更に発展させて、秘密鍵を見つけ出すことを目的とする電磁放射攻撃を安全に回避することを可能にすることにある。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の目的は、請求項１の特徴を備える装置並びに請求項６の特徴を備える方法によって達成される。本発明の有利な好適例及び目的に合わせた改良については、それぞれの従属請求項に開示する。
【課題を解決するための手段】
【００１６】
本発明は、電磁放射攻撃、特に、たとえば光フラッシュ攻撃のような光攻撃からチップカード又はスマートカードを保護するためのＦ−計算及び／又はＦ−証明（Ｆ−プルーフ（Ｆ−ｐｒｏｏｆ））を使用し、これにより、ＩＣ（集積回路）カードの欠陥を利用したこうした攻撃に対するＩＣカードの安全性が大幅に高まる、という思想に主に基づくものである。
【００１７】
Ｆ−計算及び／又はＦ−チェック（いわゆるＦ−証明）を用いることは、英国特許公開第２３１９１５０に開示されている乱数計算よりもより一般化された方法である、というのは本発明も４ビットの倍数で良好に機能するからである。
【００１８】
かかる電磁放射攻撃は、光源又は他の電磁放射源をチップ上に指向させることにより計算に影響を与えることによって秘密鍵を見つけ出そうとする。埋め込みシステム、特にチップカード又はスマートカードを保護するために、Ｆ−証明によって計算をチェックする。Ｆ−証明は１６進法用であり、１０進法用の９−証明（９−プルーフ（９−ｐｒｏｏｆ））と類似している。
【００１９】
１０進法用には、この９−証明は既知である。２つの数を乗算する際には、各数において各桁の数字を加算し、両方の加算値を乗算し、その結果を９で除算し、その剰余を保存する。そして、上記２つの数を乗算した結果を求め、その各桁の数字を加算し、ここでも９で除算し、その剰余を保存しておく。９−証明では、両方の剰余が等しくなる。
【００２０】
１６進法用には、Ｆ−証明がこれに相当する証明である。このＦ−証明は、ＧＦ（ｐ）ですでに知られているかもしれないが、本発明が証明を記述するＧＦ（２ｎ）では知られていない。この関係では、アーキテクチャが、素数（ｐ）拡大体のオペランドとバイナリ（２ｎ）拡大体のオペランドで共に機能することができる場合は、このアーキテクチャは統一されていると言われる。
【００２１】
ｐが素数の場合、ｐを法とする整数は、ｐ個の要素を有する体を形成し、ＧＦ（ｐ）で表される。有限体は、有限の体次数の体、つまり有限の要素数の体であり、ガロア体又はＧＦともいわれる。有限体の次数は、常に素数又は素数の累乗である。素数の累乗毎に、ちょうど１つの有限体ＧＦ（）が存在する（注：「ちょうど１つ」とは「同型まで含めてちょうど１つ」という意味である）。ＧＦ（ｐ）は次数ｐの素体といわれ、ｐを法とする剰余類の体である。
【００２２】
ｎ＞１である際には、ＧＦ（）は、その係数がＧＦ（ｐ）に属する多項式の同値類の体として表わすことができる。ｎ次のあらゆる既約の多項式は、同型まで含めて同じ体を生み出す。
【００２３】
本発明の特に進歩的な改良によれば、Ｆ−証明によって計算のエラーが見つかると、埋め込みシステムへのアクセスを拒否する。この関係では、Ｆ−計算は、いわゆるＦ−証明によって計算、特に暗号演算をチェックする。Ｆ−計算がエラーを見つけると、結果を出さない。
【００２４】
かかるＦ−計算又はＦ−チェックは効果的である、というのは、光攻撃又は電磁放射攻撃は粗く、かかる攻撃の場所も時間も微細でないからである。この理由により、攻撃者は正確な瞬間における計算も、必要な部分、つまりゲート位置も正確に攻撃することはできない。かかる攻撃のために、ほとんどの場合、試行錯誤法が用いられる。
【００２５】
本発明は更に、計算、特に暗号演算を行う少なくとも１つの集積回路を備えたデータ処理デバイス、特に埋め込みシステム、例えばチップカード又はスマートカードに関するものであり、ここでは、少なくとも１つのＦ−証明で上記計算をチェックすることによって、少なくとも１つの攻撃、特に少なくとも１つの電磁放射攻撃から上記集積回路を保護する。
【００２６】
最後に、本発明は、上述した装置の少なくとも１つ及び／又は上述した方法の少なくとも１つの、上述したデータ処理デバイスの少なくとも１つにおける使用に関するものである。
【００２７】
既に上記したように、本発明の教示を有利な方法で具体化並びに改善するいくつかの選択肢が存在する。この目的のために、請求項１及び請求項６にそれぞれ従属する請求項を参照し、本発明の更なる改善、特徴、及び利点を、好適な実施例及び添付の図面を参照しながら、以下でより詳細に説明する。
【発明を実施するための最良の形態】
【００２８】
図１から図３では、対応する部分には同一の参照番号を用いる。
【００２９】
データ処理デバイス、すなわち、暗号演算を行うＩＣ（集積回路）を備えたチップカード又はスマートカードの形の埋め込みシステムの実施例は、ＰＫＩ（公開鍵基盤）システムを参照し、本発明の方法により機能し、すなわち不正及び／又は操作から保護される。
【００３０】
【特許文献６】米国特許４４０５８２９号
【非特許文献１】Ｒｏｎ  Ｒｉｖｅｓｔ，Ａｄｉ  Ｓｈａｍｉｒ，Ｌｅｎ  Ａｄｌｅｍａｎ：”Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ”
【００３１】
上記集積回路の暗号計算は、暗号化Ｃ＝Ｍｅ  ｍｏｄ（Ｎ）のための計算を行うＲＳＡ（リベスト−シャミア−エーデルマン）アルゴリズム（米国特許４４０５８２９号又はＲｏｎ  Ｒｉｖｅｓｔ，Ａｄｉ  Ｓｈａｍｉｒ，Ｌｅｎ  Ａｄｌｅｍａｎ著：”Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ、２１（２），１２０〜１２６ページ，１９７８年２月）に基づくものである。ここに、
Ｍは暗号化すべき平文であり、
Ｎ＝ｐ・ｑであり、
ｅは（ｐ−１）（ｑ−１）と互いに素であり、
ｄはｘｅｄ  ｍｏｄ［（ｐ−１）（ｑ−１）］＝１を満足し、
暗号解読するにはＭ＝Ｃｄ  ｍｏｄ（Ｎ）を計算する。
【００３２】
Ｍｅ（又はＣｄ）を計算する方法の１つは次の通りである：
Ｒ＝Ｍから開始し、
指数ｅを左から右にスキャンし、
常にＲ＝Ｒ２  ｍｏｄ（Ｎ）を計算し、
スキャンしたｅのビットが１であるとき、さらに、Ｒ＝Ｒ・Ｍ  ｍｏｄ（Ｎ）を計算する。
【００３３】
従って、計算は、多くの平方算及び乗算から成る。約すために、剰余Ｎは多数（Ｑ）回結果から減算されるか結果に加算される。
【００３４】
乗算は一般に以下のようになる：
Ｒ＝Ｘ・Ｙ−Ｑ・Ｎ、ただしＸ＝Ｒ、Ｙ＝Ｍである。
始めに、Ｆ（Ｍ）及びＦ（Ｎ）を計算し、ＦＭ及びＦＮとして記憶する。Ｘ（＝Ｒ）が前の計算結果であるので、Ｆ（Ｘ）も既知でありＦＸとして記憶する。
【００３５】
Ｆ−証明は、Ｆ＝ＦＸ・ＦＹ−Ｆ（Ｑ）・ＦＮ及びＦ（Ｒ）を計算し、即ち結果から計算する。
【００３６】
そしてＦ−証明はＦ＝Ｆ（Ｒ）であることをチェックする。この値は次のチェックで用いるために記憶しておく。
【００３７】
係数Ｑが計算されると、約す期間中にＦ（Ｑ）が計算される。
【００３８】
平方算は一般に以下のようになる：
Ｒ＝Ｘ２−Ｑ・Ｎ、ただしＸ＝Ｒである。
Ｆ−証明は、Ｆ（Ｒ）＝ＦＸ２−Ｆ（Ｑ）・ＦＮであることをチェックする。
【００３９】
【非特許文献２】Ｍ．Ｅｒｎｅｓｔ，Ｍ．Ｊｕｎｇ，Ｆ．Ｍａｄｌｅｎｅｒ，ｅｔ  ａｌ：”Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｓｙｓｔｅｍ  ｏｎ  Ｃｈｉｐ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｏｖｅｒ  ＧＦ（２ｎ）”
【００４０】
ＥＣＣ（楕円曲線暗号法）（Ｍ．Ｅｒｎｅｓｔ，Ｍ．Ｊｕｎｇ，Ｆ．Ｍａｄｌｅｎｅｒ他著：”Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｓｙｓｔｅｍ  ｏｎ  Ｃｈｉｐ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｏｖｅｒ  ＧＦ（２ｎ）”、３８１〜３９９ページ参照）については、ある楕円曲線及びこの曲線上のある点Ｐを選択する。
【００４１】
第１のインスタンス（手続き）Ａでは、乱数ａを選択し、ａ・Ｐを計算し、公開鍵として第２の手続きＢに送る。この第２のインスタンスＢでは、乱数ｂを選択し、ｂ・Ｐを計算し、公開鍵として第１のインスタンスＢに送る。そして、第１のインスタンスＡはＫ＝ａ・（ｂ・Ｐ）を計算し、第２のインスタンスＢはＫ’＝ｂ・（ａ・Ｐ）を計算する。このときＫ＝Ｋ’であり、これは２つのインスタンスＡとＢに共有の秘密である。
【００４２】
基本演算は点Ｐにスカラーａを掛ける乗算である。これは、点の反復加算、即ちＸ＝ａＰ＝Ｐ＋Ｐ＋…＋Ｐ（ａ回）である：
Ｒ＝Ｐから開始し、
スカラーａを左から右にスキャンし、
常にＲ＝２Ｒ  ｍｏｄ（Ｎ）を計算し（いわゆる点の倍加）、
スキャンしたａのビットが１のとき、さらにＲ＝Ｒ＋Ｐ  ｍｏｄ（Ｎ）を計算する（いわゆる点の加算）。
【００４３】
いわゆる点の倍加に関するアルゴリズム及びいわゆる点の加算のためのアルゴリズムは、演算Ｘ・Ｙ±Ｚ  ｍｏｄ（Ｎ）及びＸ２±Ｚ  ｍｏｄ（Ｎ）を用いる（ＲＳＡ（リベスト−シャミア−エーデルマン）アルゴリズムのようであるが第３のオペランドＺを加算又は減算する）。
【００４４】
ＲＳＡ（リベスト−シャミア−エーデルマン）アルゴリズムと同様の方法で、Ｆ−証明は：
Ｆ（Ｒ）＝ＦＸ・ＦＹ±ＦＺ−Ｆ（Ｑ）・ＦＮ；
Ｆ（Ｒ）＝ＦＸ２±ＦＺ−Ｆ（Ｑ）・ＦＮ
をチェックする。
【００４５】
点の倍加アルゴリズム及び点の加算アルゴリズムは逆数演算も必要とし、この演算はＸ−１［Ｘ・Ｘ−１  ｍｏｄ（Ｎ）＝１］を計算する。この演算も、Ｆ−証明によって、すなわち、いわゆる逆数用のＦ−証明によってチェックすることができる（以下参照）。
【００４６】
Ｘ  ｍｏｄ（Ｎ）の逆数をＸ−１とし、即ちＸ・Ｘ−１＝１  ｍｏｄ（Ｎ）である。
【００４７】
Ｆ（Ｘ）は前に計算されていると仮定し、Ｘの逆数の計算後に、つまりＸ−１の計算後に、Ｆ（Ｘ−１）  ｍｏｄ（Ｆ）を計算する。
【００４８】
ここで、逆数Ｘ−１の計算は、Ｆ（Ｘ・Ｘ−１）  ｍｏｄ（Ｆ）＝Ｆ（Ｘ）・Ｆ（Ｘ−１）  ｍｏｄ（Ｆ）＝１を計算することによって容易にチェックすることができる。
【００４９】
結果が１と異なる場合は、逆数Ｘ−１の計算は、特にある種の攻撃、例えば電磁放射攻撃により誤っている。
【００５０】
このチェック、つまりこの逆数用のＦ−証明は、ＸとＸ−１  ｍｏｄ（Ｎ）との乗算よりも使う演算パワーがずっと小さく、この乗算の結果も１になるべきものである。さらに、Ｆ（Ｘ−１）の値も残りのチェックのために必要である。従って、Ｆ（Ｘ）・Ｆ（Ｘ−１）  ｍｏｄ（Ｆ）の計算が加わるだけである。
【００５１】
Ｆ−証明自体については、次の定義及び性質が存在する。
【００５２】
ガロア体ＧＦ（ｐ）について、
Ｘ＝ｘｎ−１Ｂｎ−１＋ｘｎ−２Ｂｎ−２＋...＋ｘ０;
Ｂ＝２４；
ＧＦ（ｐ）に対しＦ＝Ｂ−１
とする。
【００５３】
ガロア体ＧＦ（２ｎ）について、
【数１】
2008533791.tif 000003
Ｂ＝ａ４；
ＧＦ（２ｎ）に対し
【数２】
2008533791.tif 000004
とする。
【００５４】
定義Ｆ（Ｘ）＝Ｘ  ｍｏｄ（Ｆ）により、第１の補助定理は：
Ｆ（Ｘ）＝ｘｎ−１＋ｘｎ−２＋...＋ｘ０  ｍｏｄ（Ｆ）である。
【００５５】
ＧＦ（ｐ）についての証明：
Ｆ（Ｘ）＝ｘｎ−１Ｂｎ−１＋ｘｎ−２Ｂｎ−２＋...＋ｘ０  ｍｏｄ（Ｂ−１）  （Ｂ−１をｘｎ−１Ｂｎ−２回減算する）
＝（ｘｎ−１＋ｘｎ−２）Ｂｎ−２＋...＋ｘ０  ｍｏｄ（Ｂ−１）  （Ｂ−１を（ｘｎ−１＋ｘｎ−２）Ｂｎ−３回減算する）
＝（ｘｎ−１＋ｘｎ−２＋ｘｎ−３）Ｂｎ−３＋...＋ｘ０  ｍｏｄ（Ｂ−１）  （Ｂ−１を（ｘｎ−１＋ｘｎ−２＋ｘｎ−３）Ｂｎ−４回減算する）
この手順を繰り返して、Ｆ（Ｘ）＝ｘｎ−１＋ｘｎ−２＋...＋ｘ０  ｍｏｄ（Ｆ）を得る。
【００５６】
ＧＦ（２ｎ）についての証明は、Ｂ−１を減算する代わりに
2008533791.tif 000005
を加算することに
よって、同様の方法で行われる。
【００５７】
第２の補助定理は、Ｆ（Ｘ＋Ｙ）＝Ｆ（Ｘ）＋Ｆ（Ｙ）  ｍｏｄ（Ｆ）である。
【００５８】
ＧＦ（ｐ）についての証明：
Ｆ（Ｘ＋Ｙ）＝Ｆ（Ｘ）＋Ｆ（Ｙ）  ｍｏｄ（Ｆ）
＝ｘｎ−１Ｂｎ−１＋ｘｎ−２Ｂｎ−２＋…＋ｘ０＋（ｙｎ−１Ｂｎ−１＋ｙｎ−２Ｂｎ−２＋...＋ｙ０）  ｍｏｄ（Ｂ−１）
＝（ｘｎ−１＋ｙｎ−１）Ｂｎ−１＋（ｘｎ−２＋ｙｎ−２）Ｂｎ−２＋...＋（ｘ０＋ｙ０）  ｍｏｄ（Ｂ−１）
＝ｘｎ−１＋ｙｎ−１＋ｘｎ−２＋ｙｎ−２＋...＋（ｘ０＋ｙ０）  ｍｏｄ（Ｂ−１）
＝ｘｎ−１＋ｘｎ−２＋…＋ｘ０＋ｙｎ−１＋ｙｎ−２＋...＋ｙ０
＝Ｆ（Ｘ）＋Ｆ（Ｙ）
【００５９】
ＧＦ（２ｎ）についての証明は、＋を
2008533791.tif 000006
に置き換えることによって、同様の方法で行われる。
【００６０】
第３の補助定理は、Ｆ（Ｘ−Ｙ）＝Ｆ（Ｘ）−Ｆ（Ｙ）  ｍｏｄ（Ｆ）である。
【００６１】
ＧＦ（ｐ）についての証明：
Ｆ（Ｘ−Ｙ）＝Ｆ（Ｘ）−Ｆ（Ｙ）  ｍｏｄ（Ｆ）
＝ｘｎ−１Ｂｎ−１＋ｘｎ−２Ｂｎ−２＋...＋ｘ０−（ｙｎ−１Ｂｎ−１＋ｙｎ−２Ｂｎ−２＋...＋ｙ０）  ｍｏｄ（Ｂ−１）
＝（ｘｎ−１−ｙｎ−１）Ｂｎ−１＋（ｘｎ−２−ｙｎ−２）Ｂｎ−２＋...＋（ｘ０−ｙ０）  ｍｏｄ（Ｂ−１）
＝ｘｎ−１−ｙｎ−１＋ｘｎ−２−ｙｎ−２＋...＋（ｘ０−ｙ０）  ｍｏｄ（Ｂ−１）
＝ｘｎ−１＋ｘｎ−２＋...＋ｘ０−（ｙｎ−１＋ｙｎ−２＋...＋ｙ０）
＝Ｆ（Ｘ）−Ｆ（Ｙ）
ＧＦ（２ｎ）においては、こうした演算はない。
【００６２】
第４の補助定理は、Ｆ（Ｘ・Ｙ）＝Ｆ（Ｘ）・Ｆ（Ｙ）  ｍｏｄ（Ｆ）である。
【００６３】
ＧＦ（ｐ）についての証明：
Ｆ（Ｘ・Ｙ）＝Ｆ（Ｘ）・Ｆ（Ｙ）  ｍｏｄ（Ｆ）
＝（ｘｎ−１Ｂｎ−１＋ｘｎ−２Ｂｎ−２＋...＋ｘ０）（ｙｎ−１Ｂｎ−１＋ｙｎ−２Ｂｎ−２＋...＋ｙ０）  ｍｏｄ（Ｂ−１）
＝ｘｎ−１Ｂｎ−１（ｙｎ−１Ｂｎ−１＋ｙｎ−２Ｂｎ−２＋...＋ｙ０）
＋ｘｎ−２Ｂｎ−２（ｙｎ−１Ｂｎ−１＋ｙｎ−２Ｂｎ−２＋...＋ｙ０）
＋...
＋ｘ０（ｙｎ−１Ｂｎ−１＋ｙｎ−２Ｂｎ−２＋...＋ｙ０）  ｍｏｄ（Ｂ−１）
＝Ｂｎ−１（ｘｎ−１ｙｎ−１Ｂｎ−１＋ｘｎ−１ｙｎ−２Ｂｎ−２＋...＋ｘｎ−１ｙ０）
＋Ｂｎ−２（ｘｎ−２ｙｎ−１Ｂｎ−１＋ｘｎ−２ｙｎ−２Ｂｎ−２＋...＋ｘｎ−２ｙ０）
＋Ｂｎ−３（ｘｎ−３ｙｎ−１Ｂｎ−１＋ｘｎ−３ｙｎ−２Ｂｎ−２＋...＋ｘｎ−３ｙ０）
＋...
＋Ｂ０（ｘ０ｙｎ−１Ｂｎ−１＋ｘ０ｙｎ−２Ｂｎ−２＋…＋ｘ０ｙ０）  ｍｏｄ（Ｂ−１）
＝Ｂｎ−１（ｘｎ−１ｙｎ−１＋ｘｎ−１ｙｎ−２＋…＋ｘｎ−１ｙ０）  （第１の補助定理により）
＋Ｂｎ−２（ｘｎ−２ｙｎ−１＋ｘｎ−２ｙｎ−２＋…＋ｘｎ−２ｙ０）
＋Ｂｎ−３（ｘｎ−３ｙｎ−１＋ｘｎ−３ｙｎ−２＋…＋ｘｎ−３ｙ０）
＋...
＋Ｂ０（ｘ０ｙｎ−１＋ｘ０ｙｎ−２＋…＋ｘ０ｙ０）  ｍｏｄ（Ｂ−１）
＝ｘｎ−１’Ｂｎ−１＋ｘｎ−２’Ｂｎ−２＋…＋ｘ０’
ここに、ｉ＝０，１，…，ｎ−１についてｘｉ−１’＝ｘｉ−１（ｙｎ−１＋ｙｎ−２＋…＋ｙ０）である。
Ｆ（Ｘ・Ｙ）＝ｘｎ−１’＋ｘｎ−２’＋…＋ｘ０’＝（ｘｎ−１＋ｘｎ−２＋…＋ｘ０）（ｙｎ−１＋ｙｎ−２＋…＋ｙ０）＝Ｆ（Ｘ）Ｆ（Ｙ）
【００６４】
ＧＦ（２ｎ）についての証明は、＋を
2008533791.tif 000007
に置き換えることによって、同様の方法で行われる。
【００６５】
本発明の実施に関しては、ｘ＝Ｆ（Ｘ）、ｙ＝Ｆ（Ｙ）の表記を用い、ｘ及びｙは４ビット（１ニブル）から成る。
【００６６】
ＧＦ（ｐ）に関する総和  ｍｏｄ（Ｆ）は次式となる：
Ｆ（Ｘ＋Ｙ）＝Ｆ（ｘ）＋Ｆ（ｙ）  ｍｏｄ（Ｆ）＝ｘ＋ｙ  ｍｏｄ（Ｆ）。
【００６７】
多数回の連続演算を行わなければならないので、オペランドのうち１つ（ここではｘ）は桁上げ保存型となる。結果がＦであるときは、Ｆを０に戻さないでＦのままにする。
【００６８】
【表１】
2008533791.tif 000008
【００６９】
ｘ４ｃ’は、ｘ３ｓ＋ｘ３ｃ＋ｙ３の和の桁上げである。
【００７０】
この結果は、ｍｏｄ（Ｆ）をとらなければならない。従ってｘ４ｃ’＝１の場合、Ｆはを減算するか、あるいはその２の補数、即ち１を加算する。従って、ｘ４ｃ’はＬＳＢ（最下位ビット）に加算される。しかし、この加算を繰り下げて、０であるｘ０ｃの箇所に記憶する。従って、以下の結果が得られる。ここでＦ（ｘ’）＝Ｆ（ｘ）＋Ｆ（ｙ）＝Ｆ（ｘ＋ｙ）である。
【００７１】
【表２】
2008533791.tif 000009
【００７２】
要約すれば、通常の桁上げ保存加算が実行され、桁上げは、ＬＳＢ（最下位ビット）として（ビット４の代わりにビット０に）記憶される。
【００７３】
ＧＦ（２ｎ）の場合、（指標ｃを有する）すべての桁上げ項は０である。加算は単純なビット単位の排他論理和となる。
【００７４】
加算の場合には、入力は反転されないが、減算の場合は、入力は排他論理和によって反転される（図１の加算、減算を参照）。
【００７５】
レジスタを経由して出力を入力ｘにフィードバックし、そして入力ｙがＹオペランドの連続するニブル（４ビット）である際に、回路はＦ（Ｙ）を計算し、即ちオペランド全体のＦ（Ｙ）を４ビットのステップで計算する。
【００７６】
減算  ｍｏｄ（Ｆ）は以下のようになる：
Ｆ（Ｘ−Ｙ）＝Ｆ（Ｘ）−Ｆ（Ｙ）  ｍｏｄ（Ｆ）＝ｘ−ｙ  ｍｏｄ（Ｆ）、
ここにｘ−ｙ＝−Ｂ＋ｘ＋（Ｂ−ｙ−１）＋１  ｍｏｄ（Ｆ）である。Ｆ＝Ｂ−１を加算すると、ｘ−ｙ＝ｘ＋（Ｂ−ｙ−１）＝ｘ＋ｙ’が得られ、ここに
【数３】
2008533791.tif 000010
である。
【００７７】
減算の代わりに、Ｆ（Ｘ）とＦ（Ｙ）のビット単位の反転とを加算する。
【００７８】
ＧＦ（２ｎ）の場合には、減算は存在しない。
【００７９】
ＧＦ（ｐ）についての乗算  ｍｏｄ（Ｆ）は次式のようになる：
Ｆ（Ｘ・Ｙ）＝Ｆ（Ｘ）・Ｆ（Ｙ）ｍｏｄ（Ｆ）＝ｘ・ｙｍｏｄ（Ｆ）。
【００８０】
まず、倍加  ｍｏｄ（Ｆ）を調べる：
Ｆ（２ｘ）＝２ｘ３２３＋２ｘ２２２＋２ｘ１２１＋２ｘ０２０  ｍｏｄ（Ｆ）＝ｘ３２４＋ｘ２２３＋ｘ１２２＋ｘ０２１。
【００８１】
この式を減算ｘ３（Ｂ−１）＝ｘ３（２４−１）によって約すと：
Ｆ（２ｘ）＝ｘ３＋ｘ２２３＋ｘ１２２＋ｘ０２１となる。
【００８２】
従って、倍加  ｍｏｄ（Ｆ）は、１ビットの左ローテーション（循環）と同じである。同様の方法で、２ｎ  ｍｏｄ（Ｆ）の乗算は、ｎビットの左ローテーションと同じであることを証明することができる。乗算は、シフトしたオペランドを多数回加算することと同じであり、従って１ビットに代わるローテーションが行われる。
Ｆ（ｘ・ｙ）＝ｘ・ｙ  ｍｏｄ（Ｆ）
＝（ｘ３２３＋ｘ２２２＋ｘ１２１＋ｘ０２０）（ｙ３２３＋ｙ２２２＋ｙ１２１＋ｙ０２０）
＝２３（ｘ３ｙ３２３＋ｘ３ｙ２２２＋ｘ３ｙ１２１＋ｘ３ｙ０２０）
＋２２（ｘ２ｙ３２３＋ｘ２ｙ２２２＋ｘ２ｙ１２１＋ｘ２ｙ０２０）
＋２１（ｘ１ｙ３２３＋ｘ１ｙ２２２＋ｘ１ｙ１２１＋ｘ１ｙ０２０）
＋２０（ｘ０ｙ３２３＋ｘ０ｙ２２２＋ｘ０ｙ１２１＋ｘ０ｙ０２０）  ｍｏｄ（Ｆ）
＝ｘ３ｙ０２３＋ｘ３ｙ３２２＋ｘ３ｙ２２１＋ｘ３ｙ１２０
＋ｘ２ｙ１２３＋ｘ２ｙ０２２＋ｘ２ｙ３２１＋ｘ２ｙ２２０
＋ｘ１ｙ２２３＋ｘ１ｙ１２２＋ｘ１ｙ０２１＋ｘ１ｙ３２０
＋ｘ０ｙ３２３＋ｘ０ｙ２２２＋ｘ０ｙ１２１＋ｘ０ｙ０２０  ｍｏｄ（Ｆ）
＝（ｘ３ｙ０＋ｘ２ｙ１＋ｘ１ｙ２＋ｘ０ｙ３）２３
＋（ｘ３ｙ３＋ｘ２ｙ０＋ｘ１ｙ１＋ｘ０ｙ２）２３
＋（ｘ３ｙ２＋ｘ２ｙ３＋ｘ１ｙ０＋ｘ０ｙ１）２３
＋（ｘ３ｙ１＋ｘ２ｙ２＋ｘ１ｙ３＋ｘ０ｙ０）２３  ｍｏｄ（Ｆ）
【００８３】
この計算は、桁上げ保存加算器ＣＳＡによってなされる（図２参照）。ＣＳＡ（桁上げ保存加算器）は、３つの数を一緒に加算するという課題を２つの数を加算するという課題に変換する。９つの数を一緒に加算する場合には、３個のＣＳＡ（桁上げ保存加算器）を用いて９つの数を６つの数に減らすことができ、そして、これらの６つの数は４つの数に減らすことができる。この関係では、桁上がり入力を前の計算から取得し、桁上がり出力を、その後の計算のために記憶する。
【００８４】
ＣＳＡ演算技法の利点はその速さである、というのは、乗算ステップが大幅に短く、乗算中の桁上げ伝搬が存在しない、即ち桁上げは後のために保存されるからである。桁上げ保存加算器は、冗長桁表現と呼ばれる計算技法の基本例である。
冗長桁表現のための基本的なモチベーション（動機付け）は、次の点にある：
コンパクトでない数の異なる表現では、計算がより容易になることが多い；
中間結果に２進表現を用いることは、表現をコンパクトにするために特別な論理回路を必要とする。
【００８５】
従って、３つの結果を加算し、桁上げ及び和の結果を与える。以上で示したように、総和  ｍｏｄ（Ｆ）の下では、上位の桁上げはビット０になる。そして、第４の結果を加算し、このことも桁上げ及び和の結果を与える。そして、上位の桁上げはビット０、即ちｆ０ｃとなる。
【００８６】
ＧＦ（２ｎ）については、通常のように全ての桁上げ項が削除される。
【００８７】
平方算  ｍｏｄ（Ｆ）に関しては、ｘ＝ｙとして乗算関数Ｆ（Ｘ２）を用いる可能性の他に、この関数用の演算論理回路は非常に単純である。Ｆ（ｘ）の平方を示す次の表中にＦ（Ｘ２）を見つけて、容易に合成することができる。
【００８８】
【表３】
2008533791.tif 000011
【００８９】
全ての入力ビットが反転する際に、結果は変化しない。
【００９０】
最後に結果を、桁上げ総和形式から、桁上げ保存加算器とは独立した全加算器（図３参照）によって標準形式に変換しなければならない。出てくる桁上げをまず計算し、そして桁上がり入力として加算する。
【００９１】
発生器をＧｉ＝ｆｉｓｆｉｃとし、伝搬器を
【数４】
2008533791.tif 000012
とすると、
Ｃ＝Ｇ３＋Ｐ３Ｇ２＋Ｐ３Ｐ２Ｇ１＋Ｐ３Ｐ２Ｐ１Ｇ０となる。
【００９２】
ＧＦ（２ｎ）については、通常のように全ての桁上げ項が削除される。
【図面の簡単な説明】
【００９３】
【図１】図１は、本発明の一部である４個の桁上げ保存加算器（ＣＳＡ）の具体例を概略的に示す図である。
【図２】図２は、本発明の一部である８個の相互接続された桁上げ保存加算器（ＣＳＡ）の具体例を概略的に示す図である。
【図３】図３は、本発明の一部である全加算器の具体例を概略的に示す図である。
【図１】
2008533791.tif 000013
【図２】
2008533791.tif 000014
【図３】
2008533791.tif 000015
【国際調査報告】
2008533791.tif 000016
2008533791.tif 000017
2008533791.tif 000018