(57)【要約】【課題】  入力段階の除算を省略しつつ、モンゴメリ演算を実現する。【解決手段】  従来のｍｏｄ演算及びモンゴメリ変換に代えて、乗算、加算及びビットシフトからなるモンゴメリ還元とモンゴメリ乗算とにより、除算を用いずに２ｎビットの入力ｍからｎビットのモンゴメリ変換結果ｍ’（＝ｍＲ  ｍｏｄ  ｐ）を得る構成としたので、上記課題を解決できる。【選択図】  図１
2006145852.tif 000002
【特許請求の範囲】
【請求項１】
ｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、２ｎビットの入力ｍからｎビットのモンゴメリ変換結果ｍ’（＝ｍＲ  ｍｏｄ  ｐ）を得るモンゴメリ変換装置であって、
前記法ｐ及び前記乗数Ｒに基づいて、乗算、加算及びビットシフトからなるモンゴメリ還元を２ｎビットの入力ｍに実行し、ｎビットのモンゴメリ還元結果（ｍＲ-1  ｍｏｄ  ｐ）を得るモンゴメリ還元手段と、
前記乗数Ｒ及び前記法ｐに基づいて、前記モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒ３  ｍｏｄ  ｐ）とのモンゴメリ乗算を実行し、得られたｎビットのモンゴメリ乗算結果（ｍＲ  ｍｏｄ  ｐ）を前記モンゴメリ変換結果ｍ’として出力するモンゴメリ乗算手段と
を備えたことを特徴とするモンゴメリ変換装置。
【請求項２】
ｎビット以上の乗数Ｒｐ，Ｒｑ、ｎビットの法ｐ，ｑ及びｎビットのべき指数ｄに基づいて、２ｎビットの入力ｍに対する法ｐｑでのｄ乗を算出し、ｎビットのべき乗剰余ｓ（＝ｍｄ  ｍｏｄ  ｐｑ）を得る演算装置であって、
前記乗数Ｒｐ及び前記法ｐに基づいて、乗算、加算及びビットシフトからなるモンゴメリ還元を２ｎビットの入力ｍに実行し、ｎビットの第１モンゴメリ還元結果（ｍＲｐ-1  ｍｏｄ  ｐ）を得る第１モンゴメリ還元手段と、
前記乗数Ｒｐ及び前記法ｐに基づいて、前記第１モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒｐ３  ｍｏｄ  ｐ）とのモンゴメリ乗算を実行し、ｎビットの第１モンゴメリ乗算結果ｍｐ’（＝ｍＲｐ  ｍｏｄ  ｐ）を得る第１モンゴメリ乗算手段と、
前記べき指数ｄ、前記乗数Ｒｐ及び法ｐに基づいて、前記第１モンゴメリ乗算結果ｍｐ’をｄｐ乗し（但し、ｄｐ＝ｄ  ｍｏｄ（ｐ−１））、ｎビットの第１べき乗剰余ｓｐ’（＝ｍｐ’＾ｄｐ×Ｒｐ  ｍｏｄ  ｐ）を得る第１モンゴメリべき乗手段と、
前記乗数Ｒｐ及び前記法ｐに基づいて、前記第１べき乗剰余ｓｐ’にモンゴメリ逆変換を実行し、ｎビットの第１モンゴメリ逆変換結果ｓｐ（＝ｍｄ  ｍｏｄ  ｐ）を得る第１モンゴメリ逆変換手段と、
前記乗数Ｒｑ及び前記法ｑに基づいて、前記入力ｍにモンゴメリ還元を実行し、ｎビットの第２モンゴメリ還元結果（ｍＲｑ-1  ｍｏｄ  ｑ）を得る第２モンゴメリ還元手段と、
前記乗数Ｒｑ及び前記法ｑに基づいて、前記第２モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒｑ３  ｍｏｄ  ｑ）とのモンゴメリ乗算を実行し、ｎビットの第２モンゴメリ乗算結果ｍｑ’（＝ｍＲｑ  ｍｏｄ  ｑ）を得る第２モンゴメリ乗算手段と、
前記べき指数ｄ、前記乗数Ｒｑ及び法ｑに基づいて、前記第２モンゴメリ乗算結果ｍｑ’をｄｑ乗し（但し、ｄｑ＝ｄ  ｍｏｄ（ｑ−１））、ｎビットの第２べき乗剰余ｓｑ’（＝ｍｑ’＾ｄｑ×Ｒｑ  ｍｏｄ  ｑ）を得る第２モンゴメリべき乗手段と、
前記乗数Ｒｑ及び前記法ｑに基づいて、前記第２べき乗剰余ｓｑ’にモンゴメリ逆変換を実行し、ｎビットの第２モンゴメリ逆変換結果ｓｑ（＝ｍｄ  ｍｏｄ  ｑ）を得る第２モンゴメリ逆変換手段と、
前記法ｐ，ｑ及び中国人剰余定理に基づいて、前記第１モンゴメリ逆変換結果ｓｐと前記第２モンゴメリ逆変換結果ｓｐとの連立方程式を解き、得られたｎビットの解（ｍｄ  ｍｏｄ  ｐｑ）を前記べき乗剰余ｓとして出力する べき乗剰余出力手段と
を備えたことを特徴とする演算装置。
【請求項３】
請求項２に記載の演算装置を備え、署名対象の文書データＤに対し、ＲＳＡ署名方式の秘密鍵ｄによりＲＳＡ署名処理を実行するＩＣカードにおいて、
前記ＲＳＡ署名処理を実行する際に、前記文書データＤの一方向性ハッシュ関数を演算し、ハッシュ値ｈ（Ｄ）を得るハッシュ演算手段と、
前記ハッシュ値ｈ（Ｄ）を前記入力ｍとして前記演算装置に入力する第１入力手段と、
前記秘密鍵ｄをべき指数ｄとして前記演算装置に入力する第２入力手段と、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ署名ｓ（＝ｈ（Ｄ）ｄ  ｍｏｄ  ｐｑ）として出力する署名出力手段と
を備えたことを特徴とするＩＣカード。
【請求項４】
請求項２に記載の演算装置を備え、ＲＳＡ暗号方式の公開鍵ｅにより平文データＤが暗号処理されてなる暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）に対し、前記公開鍵ｅの鍵ペアである秘密鍵ｄによるＲＳＡ復号処理を実行するＩＣカードにおいて、
前記ＲＳＡ復号処理を実行する際に、前記暗号文ｃを前記入力ｍとして前記演算装置に入力する第１入力手段と、
前記秘密鍵ｄをべき指数ｄとして前記演算装置に入力する第２入力手段と、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ復号結果ｓ（＝ｃｄ  ｍｏｄ  ｐｑ）として出力する復号結果出力手段と
を備えたことを特徴とするＩＣカード。
【請求項５】
請求項２に記載の演算装置を備え、署名対象の文書データＤに対し、ＤＳＡ署名方式の公開鍵ｇ及び秘密鍵ｘに基づいてＤＳＡ署名処理を実行するＩＣカードにおいて、
前記ＤＳＡ署名処理を実行する際に、法ｑの乗法群Ｚｑ＊からランダムに乱数ｋを選択する乱数選択手段と、
前記公開鍵ｇを入力ｍとして前記第１モンゴメリ還元手段に入力する第１入力手段と、
前記乱数ｋをべき指数ｄとして前記第１モンゴメリべき乗手段に入力する第２入力手段と、
前記第１及び第２入力手段による入力の後、前記第１モンゴメリ逆変換手段から出力されたべき乗剰余（ｇｋ  ｍｏｄ  ｐ）及び予め保持した法ｑに基づいて、ＤＳＡ署名の第１部分データｒ（＝（ｇｋ  ｍｏｄ  ｐ）  ｍｏｄ  ｑ）を生成する第１部分データ生成手段と、
前記文書データＤの一方向性ハッシュ関数を演算し、ハッシュ値ｈ（Ｄ）を得るハッシュ演算手段と、
前記乱数ｋ、前記ハッシュ値ｈ（Ｄ）、前記秘密鍵ｘ、前記第１部分データｒ及び前記法ｑに基づいてＤＳＡ署名処理を実行し、ＤＳＡ署名の第２部分データｓ（＝ｋ-1（ｈ（Ｄ）＋ｘｒ）ｍｏｄ  ｑ）を生成する第２部分データ生成手段と、
前記第１及び第２部分データｒ，ｓをＤＳＡ署名（ｒ，ｓ）として出力する署名出力手段と
を備えたことを特徴とするＩＣカード。
【請求項６】
請求項２に記載の演算装置を備え、暗号化対象の平文データＤに対し、ＲＳＡ暗号方式の公開鍵ｅに基づいてＲＳＡ暗号処理を実行する暗号装置において、
前記ＲＳＡ暗号処理を実行する際に、前記平文データＤを前記入力ｍとして前記演算装置に入力する第１入力手段と、
前記公開鍵ｅをべき指数ｄとして前記演算装置に入力する第２入力手段と、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）として出力する暗号文出力手段と
を備えたことを特徴とする復号装置。
【請求項７】
請求項２に記載の演算装置を備え、ＲＳＡ暗号方式の公開鍵ｅにより平文データＤが暗号処理されてなる暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）に対し、前記公開鍵ｅの鍵ペアである秘密鍵ｄによるＲＳＡ復号処理を実行する復号装置において、
前記ＲＳＡ復号処理を実行する際に、前記暗号文ｃを前記入力ｍとして前記演算装置に入力する第１入力手段と、
前記秘密鍵ｄをべき指数ｄとして前記演算装置に入力する第２入力手段と、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ復号結果ｓ（＝ｃｄ  ｍｏｄ  ｐｑ）として出力する復号結果出力手段と
を備えたことを特徴とする復号装置。
【請求項８】
メモリに保持されたｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、２ｎビットの入力ｍからｎビットのモンゴメリ変換結果ｍ’（＝ｍＲ  ｍｏｄ  ｐ）を得るモンゴメリ変換装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記メモリ内の法ｐ及び乗数Ｒに基づいて、２ｎビットの入力ｍにモンゴメリ還元を実行し、ｎビットのモンゴメリ還元結果（ｍＲ-1  ｍｏｄ  ｐ）を得るモンゴメリ還元手段、
前記メモリ内の乗数Ｒ及び法ｐに基づいて、前記モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒ３  ｍｏｄ  ｐ）とのモンゴメリ乗算を実行し、得られたｎビットのモンゴメリ乗算結果（ｍＲ  ｍｏｄ  ｐ）を前記モンゴメリ変換結果ｍ’として出力するモンゴメリ乗算手段、
として機能させるためのプログラム。
【請求項９】
メモリに保持されたｎビット以上の乗数Ｒｐ，Ｒｑ、ｎビットの法ｐ，ｑ及び入力されるｎビットのべき指数ｄに基づいて、２ｎビットの入力ｍに対する法ｐｑでのｄ乗を算出し、ｎビットのべき乗剰余ｓ（＝ｍｄ  ｍｏｄ  ｐｑ）を得る演算装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記メモリ内の乗数Ｒｐ及び法ｐに基づいて、前記入力ｍにモンゴメリ還元を実行し、ｎビットの第１モンゴメリ還元結果（ｍＲｐ-1  ｍｏｄ  ｐ）を得る第１モンゴメリ還元手段、
前記メモリ内の乗数Ｒｐ及び法ｐに基づいて、前記第１モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒｐ３  ｍｏｄ  ｐ）とのモンゴメリ乗算を実行し、ｎビットの第１モンゴメリ乗算結果ｍｐ’（＝ｍＲｐ  ｍｏｄ  ｐ）を得る第１モンゴメリ乗算手段、
前記べき指数ｄ、前記乗数Ｒｐ及び法ｐに基づいて、前記第１モンゴメリ乗算結果ｍｐ’をｄｐ乗し（但し、ｄｐ＝ｄ  ｍｏｄ（ｐ−１））、ｎビットの第１べき乗剰余ｓｐ’（＝ｍｐ’＾ｄｐ×Ｒｐ  ｍｏｄ  ｐ）を得る第１モンゴメリべき乗手段、
前記メモリ内の乗数Ｒｐ及び法ｐに基づいて、前記第１べき乗剰余ｓｐ’にモンゴメリ逆変換を実行し、ｎビットの第１モンゴメリ逆変換結果ｓｐ（＝ｍｄ  ｍｏｄ  ｐ）を得る第１モンゴメリ逆変換手段、
前記メモリ内の乗数Ｒｑ及び法ｑに基づいて、前記入力ｍにモンゴメリ還元を実行し、ｎビットの第２モンゴメリ還元結果（ｍＲｑ-1  ｍｏｄ  ｑ）を得る第２モンゴメリ還元手段、
前記メモリ内の乗数Ｒｑ及び法ｑに基づいて、前記第２モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒｑ３  ｍｏｄ  ｑ）とのモンゴメリ乗算を実行し、ｎビットの第２モンゴメリ乗算結果ｍｑ’（＝ｍＲｑ  ｍｏｄ  ｑ）を得る第２モンゴメリ乗算手段、
前記べき指数ｄ、前記乗数Ｒｑ及び法ｑに基づいて、前記第２モンゴメリ乗算結果ｍｑ’をｄｑ乗し（但し、ｄｑ＝ｄ  ｍｏｄ（ｑ−１））、ｎビットの第２べき乗剰余ｓｑ’（＝ｍｑ’＾ｄｑ×Ｒｑ  ｍｏｄ  ｑ）を得る第２モンゴメリべき乗手段、
前記メモリ内の乗数Ｒｑ及び法ｑに基づいて、前記第２べき乗剰余ｓｑ’にモンゴメリ逆変換を実行し、ｎビットの第２モンゴメリ逆変換結果ｓｑ（＝ｍｄ  ｍｏｄ  ｑ）を得る第２モンゴメリ逆変換手段、
前記メモリ内の法ｐ，ｑ及び中国人剰余定理に基づいて、前記第１モンゴメリ逆変換結果ｓｐと前記第２モンゴメリ逆変換結果ｓｐとの連立方程式を解き、得られたｎビットの解（ｍｄ  ｍｏｄ  ｐｑ）を前記べき乗剰余ｓとして出力する べき乗剰余出力手段、
として機能させるためのプログラム。
【請求項１０】
請求項９に記載のプログラムをインストールした演算装置を備え、且つ署名対象の文書データＤに対して、ＲＳＡ署名方式の秘密鍵ｄによりＲＳＡ署名処理を実行するＩＣカードに関し、前記ＩＣカードのコンピュータに用いられるプログラムにおいて、
前記コンピュータを、
前記ＲＳＡ署名処理を実行する際に、前記文書データＤの一方向性ハッシュ関数を演算し、ハッシュ値ｈ（Ｄ）を得るハッシュ演算手段、
前記ハッシュ値ｈ（Ｄ）を前記入力ｍとして前記演算装置に入力する第１入力手段、
前記秘密鍵ｄをべき指数ｄとして前記演算装置に入力する第２入力手段、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ署名ｓ（＝ｈ（Ｄ）ｄ  ｍｏｄ  ｐｑ）として出力する署名出力手段、
として機能させるためのプログラム。
【請求項１１】
請求項９に記載のプログラムをインストールした演算装置を備え、且つＲＳＡ暗号方式の公開鍵ｅにより平文データＤが暗号処理されてなる暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）に対して、前記公開鍵ｅの鍵ペアである秘密鍵ｄによるＲＳＡ復号処理を実行するＩＣカードに関し、前記ＩＣカードのコンピュータに用いられるプログラムにおいて、
前記コンピュータを、
前記ＲＳＡ復号処理を実行する際に、前記暗号文ｃを前記入力ｍとして前記演算装置に入力する第１入力手段、
前記秘密鍵ｄをべき指数ｄとして前記演算装置に入力する第２入力手段、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ復号結果ｓ（＝ｃｄ  ｍｏｄ  ｐｑ）として出力する復号結果出力手段、
として機能させるためのプログラム。
【請求項１２】
請求項９に記載のプログラムをインストールした演算装置を備え、且つ署名対象の文書データＤに対して、ＤＳＡ署名方式の公開鍵ｇ及び秘密鍵ｘに基づいてＤＳＡ署名処理を実行するＩＣカードに関し、前記ＩＣカードのコンピュータに用いられるプログラムにおいて、
前記コンピュータを、
前記ＤＳＡ署名処理を実行する際に、法ｑの乗法群Ｚｑ＊からランダムに乱数ｋを選択する乱数選択手段、
前記公開鍵ｇを入力ｍとして前記演算装置の第１モンゴメリ還元手段に入力する第１入力手段と、
前記乱数ｋをべき指数ｄとして前記演算装置の第１モンゴメリべき乗手段に入力する第２入力手段、
前記第１及び第２入力手段による入力の後、前記演算装置の第１モンゴメリ逆変換手段から出力されたべき乗剰余（ｇｋ  ｍｏｄ  ｐ）及び予め保持した法ｑに基づいて、ＤＳＡ署名の第１部分データｒ（＝（ｇｋ  ｍｏｄ  ｐ）  ｍｏｄ  ｑ）を生成する第１部分データ生成手段、
前記文書データＤの一方向性ハッシュ関数を演算し、ハッシュ値ｈ（Ｄ）を得るハッシュ演算手段、
前記乱数ｋ、前記ハッシュ値ｈ（Ｄ）、前記秘密鍵ｘ、前記第１部分データｒ及び前記法ｑに基づいてＤＳＡ署名処理を実行し、ＤＳＡ署名の第２部分データｓ（＝ｋ-1（ｈ（Ｄ）＋ｘｒ）ｍｏｄ  ｑ）を生成する第２部分データ生成手段、
前記第１及び第２部分データｒ，ｓをＤＳＡ署名（ｒ，ｓ）として出力する署名出力手段、
として機能させるためのプログラム。
【請求項１３】
請求項９に記載のプログラムをインストールした演算装置を備え、且つ暗号化対象の平文データＤに対して、ＲＳＡ暗号方式の公開鍵ｅに基づいてＲＳＡ暗号処理を実行する暗号装置に関し、前記暗号装置のコンピュータに用いられるプログラムにおいて、
前記コンピュータを、
前記ＲＳＡ暗号処理を実行する際に、前記平文データＤを前記入力ｍとして前記演算装置に入力する第１入力手段、
前記公開鍵ｅをべき指数ｄとして前記演算装置に入力する第２入力手段、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）として出力する暗号文出力手段、
として機能させるためのプログラム。
【請求項１４】
請求項９に記載のプログラムをインストールした演算装置を備え、且つＲＳＡ暗号方式の公開鍵ｅにより平文データＤが暗号処理されてなる暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）に対して、前記公開鍵ｅの鍵ペアである秘密鍵ｄによるＲＳＡ復号処理を実行する復号装置に関し、前記復号装置のコンピュータに用いられるプログラムにおいて、
前記コンピュータを、
前記ＲＳＡ復号処理を実行する際に、前記暗号文ｃを前記入力ｍとして前記演算装置に入力する第１入力手段、
前記秘密鍵ｄをべき指数ｄとして前記演算装置に入力する第２入力手段、
前記第１及び第２入力手段による入力の後、前記演算装置から出力されたべき乗剰余ｓをＲＳＡ復号結果ｓ（＝ｃｄ  ｍｏｄ  ｐｑ）として出力する復号結果出力手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＣカード（スマートカード）に組み込めるような小型のモンゴメリ変換装置、演算装置、ＩＣカード、暗号装置、復号装置及びプログラムに関する。
【背景技術】
【０００２】
公開鍵暗号方式は、暗号技術の中でも最も重要な技術の一つであり、例えばＲＳＡ暗号、ＲＳＡ署名及びＤＳＡ署名などが広く用いられている。近年、公開鍵暗号方式は、ＲＳＡ署名がＩＣカードで実行可能となり、セキュリティの応用分野が広がっている。
【０００３】
なお、ＩＣカードは、ＣＰＵが非力なため、ＣＰＵ単体では署名時間がかかり過ぎる。そこで、暗号アクセラレータやコプロセッサと呼ばれる演算装置がＩＣカードに付加され、署名時間が短縮されている。
【０００４】
主要な公開鍵暗号方式は、有限体上の算術演算により構成されている。演算対象は、例えば１０２４ビットのような多倍長の整数である。ここで、暗号アクセラレータは小型化や高速化のための数多くの演算技術が研究されている。特に重要な演算技術は、中国人剰余定理（ＣＲＴ；Chinese remainder theorem）とモンゴメリ還元(Montgomery reduction)を用いる方式である。中国人剰余定理とモンゴメリ還元の詳細は、例えば非特許文献１に記載されている。
【０００５】
中国人剰余定理は、法の因数分解が既知という前提で、部分体による計算を実行し、計算時間を短縮可能である。ＲＳＡ暗号の場合、法ｎを二つの素数ｐ，ｑに素因数分解できるという前提があるので、ｍｏｄ  ｐの計算結果とｍｏｄ  ｑの計算結果とに基づいて、ｍｏｄ  ｎ（＝ｍｏｄ  ｐｑ）の計算結果を算出可能である。この場合、途中の計算は全て半分程度の桁数で済むため、計算量が低減されている。
【０００６】
モンゴメリ還元は、有限体上の計算で必須となる剰余を、除算無しで乗算のみで算出可能である。通常、除算は回路規模や演算速度の面で乗算よりも不利である。モンゴメリ還元は除算を用いないので、小型化や高速化に有効である。なお、除算のアルゴリズムでは剰余を求めるとき、部分商を算出する。部分商の算出効率を上げると、誤差が生じて足し直しや引き直しといった試行錯誤が必要となる。これが除算が不利な理由である。
【０００７】
中国人剰余定理とモンゴメリ還元はいずれも効率化に有効な手法であり、独立しているので、両者を組み合わせることが可能である。
【０００８】
図１９は中国人剰余定理とモンゴメリ還元を用い、べき乗剰余を演算する演算装置の論理的な構成を示す模式図である。入力ｍは法ｐｑでのｄ乗を求めたいものとする。
【０００９】
演算装置は、２ｎビットの入力ｍとべき指数ｄに対し、それぞれｍｏｄ（剰余算）演算部１，２が剰余ｍｐ（＝ｍ  ｍｏｄ  ｐ）と、ｍｑ（＝ｍ  ｍｏｄ  ｑ）とを計算し、ｎビットの剰余ｍｐとｍｑを得る。
【００１０】
次に、モンゴメリ変換部３，４は、モンゴメリ演算を使うための準備としてそれぞれ剰余ｍｐ，ｍｑをモンゴメリ変換し、ｎビットの変換結果ｍｐ’（＝ｍ×Ｒｐ  ｍｏｄ  ｐ）とｍｑ’（＝ｍ×Ｒｑ  ｍｏｄ  ｑ）を得る。
【００１１】
このとき、ＲｐとＲｑは事前に計算されている定数である。定数Ｒｐは素数ｐより大きい２のべき乗であり、モンゴメリ還元の際に除算に代えてビットシフトを用いるための値である。同様に、定数Ｒｑは素数ｑより大きい２のべき乗である。
【００１２】
次に、モンゴメリべき剰部５，６は、それぞれ変換結果ｍｐ’とｍｑ’に対してモンゴメリ還元を用いたべき乗剰余を計算し、ｎビットのべき乗剰余ｓｐ’（＝ｍｐ’＾ｄｐ×Ｒｐ  ｍｏｄ  ｐ）とｓｑ’（＝ｍｑ’＾ｄｑ×Ｒｑ  ｍｏｄ  ｑ）を得る。但し、ｄｐ＝ｄ  ｍｏｄ  （ｐ−１）、ｄｑ＝ｄ  ｍｏｄ  （ｑ−１）。べき指数ｄｐ，ｄｑは事前に計算されているものとする。
【００１３】
なお、得られたべき乗剰余ｓｐ’とｓｑ’は、モンゴメリ空間上の値であるので有限体上の値に戻す必要がある。このため、モンゴメリ逆変換部７，８は、それぞれべき乗剰余ｓｐ’とｓｑ’をモンゴメリ逆変換し、有限体上のべき乗剰余ｓｐ（＝ｓ  ｍｏｄ  ｐ）とｓｑ（＝ｓ  ｍｏｄ  ｑ）を得る。
【００１４】
しかる後、ＣＲＴ（中国人剰余定理）演算部９は、ｎビットのべき乗剰余ｓｐ（＝ｓ  ｍｏｄ  ｐ）とｓｑ（＝ｓ  ｍｏｄ  ｑ）の連立方程式を中国人剰余定理に基づいて解き、２ｎビットの解ｓとしてｓ＝ｓ  ｍｏｄ  ｐｑを得る。この解ｓは、最終結果のべき乗剰余ｓ＝ｍｄ  ｍｏｄ  ｐｑとなっている。
【００１５】
以上でべき乗剰余計算が完了する。実際には安全性を確保するため、素数ｐ，ｑを５１２ビット程度とし、入力ｍを１０２４ビット程度として運用されている。
【非特許文献１】A.J. Menezes, P.C. van Oorshot, and S.A. Vanstone, "Handbook of applied cryptography", CRC Press, section 14 等, (1997).
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、以上のような演算装置は、中国人剰余定理とモンゴメリ演算を組合せるために、入力段階で剰余算（ｍｏｄ演算）が必要となっている。理由は、モンゴメリ変換部３，４がｎビットの入力ｍｐ，ｍｑを受け付けるが、２ｎビットの入力ｍを受け付けないからである。しかしながら、剰余算は剰余を得るのに除算を要するが、除算は前述した通り、回路規模と演算速度の面で不利である。
【００１７】
本発明は上記実情を考慮してなされたもので、入力段階の除算を省略しつつ、モンゴメリ演算を実現し得るモンゴメリ変換装置及びプログラムを提供することを目的とする。
【００１８】
また、本発明の他の目的は、入力段階の除算を省略しつつ、中国人剰余定理とモンゴメリ演算とを組み合わせた べき乗剰余算を実行し得る演算装置、ＩＣカード、暗号装置、復号装置及びプログラムを提供することにある。
【課題を解決するための手段】
【００１９】
第１の発明は、ｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、２ｎビットの入力ｍからｎビットのモンゴメリ変換結果ｍ’（＝ｍＲ  ｍｏｄ  ｐ）を得るモンゴメリ変換装置であって、前記法ｐ及び前記乗数Ｒに基づいて、乗算、加算及びビットシフトからなるモンゴメリ還元を２ｎビットの入力ｍに実行し、ｎビットのモンゴメリ還元結果（ｍＲ-1  ｍｏｄ  ｐ）を得るモンゴメリ還元手段と、前記乗数Ｒ及び前記法ｐに基づいて、前記モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒ３  ｍｏｄ  ｐ）とのモンゴメリ乗算を実行し、得られたｎビットのモンゴメリ乗算結果（ｍＲ  ｍｏｄ  ｐ）を前記モンゴメリ変換結果ｍ’として出力するモンゴメリ乗算手段とを備えたモンゴメリ変換装置である。
【００２０】
第２の発明は、ｎビット以上の乗数Ｒｐ，Ｒｑ、ｎビットの法ｐ，ｑ及びｎビットのべき指数ｄに基づいて、２ｎビットの入力ｍに対する法ｐｑでのｄ乗を算出し、ｎビットのべき乗剰余ｓ（＝ｍｄ  ｍｏｄ  ｐｑ）を得る演算装置であって、前記乗数Ｒｐ及び前記法ｐに基づいて、乗算、加算及びビットシフトからなるモンゴメリ還元を２ｎビットの入力ｍに実行し、ｎビットの第１モンゴメリ還元結果（ｍＲｐ-1  ｍｏｄ  ｐ）を得る第１モンゴメリ還元手段と、前記乗数Ｒｐ及び前記法ｐに基づいて、前記第１モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒｐ３  ｍｏｄ  ｐ）とのモンゴメリ乗算を実行し、ｎビットの第１モンゴメリ乗算結果ｍｐ’（＝ｍＲｐ  ｍｏｄ  ｐ）を得る第１モンゴメリ乗算手段と、前記べき指数ｄ、前記乗数Ｒｐ及び法ｐに基づいて、前記第１モンゴメリ乗算結果ｍｐ’をｄｐ乗し（但し、ｄｐ＝ｄ  ｍｏｄ（ｐ−１））、ｎビットの第１べき乗剰余ｓｐ’（＝ｍｐ’＾ｄｐ×Ｒｐ  ｍｏｄ  ｐ）を得る第１モンゴメリべき乗手段と、前記乗数Ｒｐ及び前記法ｐに基づいて、前記第１べき乗剰余ｓｐ’にモンゴメリ逆変換を実行し、ｎビットの第１モンゴメリ逆変換結果ｓｐ（＝ｍｄ  ｍｏｄ  ｐ）を得る第１モンゴメリ逆変換手段と、前記乗数Ｒｑ及び前記法ｑに基づいて、前記入力ｍにモンゴメリ還元を実行し、ｎビットの第２モンゴメリ還元結果（ｍＲｑ-1  ｍｏｄ  ｑ）を得る第２モンゴメリ還元手段と、前記乗数Ｒｑ及び前記法ｑに基づいて、前記第２モンゴメリ還元結果と前記乗数Ｒの３乗（Ｒｑ３  ｍｏｄ  ｑ）とのモンゴメリ乗算を実行し、ｎビットの第２モンゴメリ乗算結果ｍｑ’（＝ｍＲｑ  ｍｏｄ  ｑ）を得る第２モンゴメリ乗算手段と、前記べき指数ｄ、前記乗数Ｒｑ及び法ｑに基づいて、前記第２モンゴメリ乗算結果ｍｑ’をｄｑ乗し（但し、ｄｑ＝ｄ  ｍｏｄ（ｑ−１））、ｎビットの第２べき乗剰余ｓｑ’（＝ｍｑ’＾ｄｑ×Ｒｑ  ｍｏｄ  ｑ）を得る第２モンゴメリべき乗手段と、前記乗数Ｒｑ及び前記法ｑに基づいて、前記第２べき乗剰余ｓｑ’にモンゴメリ逆変換を実行し、ｎビットの第２モンゴメリ逆変換結果ｓｑ（＝ｍｄ  ｍｏｄ  ｑ）を得る第２モンゴメリ逆変換手段と、前記法ｐ，ｑ及び中国人剰余定理に基づいて、前記第１モンゴメリ逆変換結果ｓｐと前記第２モンゴメリ逆変換結果ｓｐとの連立方程式を解き、得られたｎビットの解（ｍｄ  ｍｏｄ  ｐｑ）を前記べき乗剰余ｓとして出力する べき乗剰余出力手段とを備えた演算装置である。
【００２１】
なお、第２の発明の演算装置は、ＩＣカード、暗号装置又は復号装置などの任意の装置に備えられ、べき乗演算に使用されてもよい。
【００２２】
（作用）
第１の発明は、従来のｍｏｄ演算及びモンゴメリ変換に代えて、乗算、加算及びビットシフトからなるモンゴメリ還元とモンゴメリ乗算とにより、除算を用いずに２ｎビットの入力ｍからｎビットのモンゴメリ変換結果を得る構成としたので、入力段階の除算を省略しつつ、モンゴメリ演算を実現することができる。
【００２３】
同様に、第２の発明は、第１の発明の構成を、中国人剰余定理を用いた べき乗剰余算の入力段階に備えたので、入力段階の除算を省略しつつ、中国人剰余定理とモンゴメリ演算とを組み合わせた べき乗剰余算を実行することができる。
【発明の効果】
【００２４】
以上説明したように本発明によれば、入力段階の除算を省略しつつ、モンゴメリ演算を実現できる。また、入力段階の除算を省略しつつ、中国人剰余定理とモンゴメリ演算とを組み合わせた べき乗剰余算を実行できる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の各実施形態について図面を参照しながら説明する。  
（第１の実施形態）
図１は本発明の第１の実施形態に係るモンゴメリ変換装置の構成を示す模式図であり、図１９と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した説明を省略する。
【００２６】
すなわち、本実施形態は、従来のｍｏｄ演算部１及びモンゴメリ変換部３の部分に関し、ｍｏｄ演算を用いずに、２ｎビットの入力ｍからｎビットのモンゴメリ変換結果ｍ’（＝ｍＲ  ｍｏｄ  ｐ）を得るモンゴメリ変換装置１０を備えている。
【００２７】
なお、モンゴメリ変換装置１０は、ハードウェア構成で実現可能であり、又はハードウェア構成とソフトウエア構成の組合せとしても実現可能となっている。後者の場合、ソフトウエア構成は、予め記憶媒体又はネットワークから得られたプログラムがモンゴメリ変換装置１０のコンピュータにインストールされて実現される。このプログラムは、モンゴメリ還元部１１及びモンゴメリ乗算部１２の機能をモンゴメリ変換装置１０のコンピュータに実現させるためのものである。以下の各実施形態で述べる演算装置、ＩＣカード、暗号装置及び復号装置といった各装置も同様にして実現可能となっている。
【００２８】
ここで、モンゴメリ変換装置１０は、モンゴメリ還元部１１及びモンゴメリ乗算部１２を備えている。
【００２９】
モンゴメリ還元部１１は、ｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、２ｎビットの入力ｍにモンゴメリ還元を実行し、得られたｎビットのモンゴメリ還元結果（ｍＲ-1  ｍｏｄ  ｐ）をモンゴメリ乗算部１２に出力するものである。なお、モンゴメリ還元は、乗算、加算及びビットシフトからなり、除算を用いない演算であり、例えば非特許文献１に記載されている。
【００３０】
乗数Ｒは、事前に計算されている定数である。定数Ｒは素数ｐより大きい２のべき乗であり、モンゴメリ還元の際に除算に代えてビットシフトを用いるための値である。素数ｐが５１２ビットの場合、定数Ｒ＝２512にする。ビットシフトよりバイトシフトやワードシフトの方が効率がよい場合、定数Ｒはバイトやワードのビット数の倍数に選ばれる。
【００３１】
ここで、乗数Ｒを用いた演算について補足的に説明する。乗数Ｒが２ｎのとき、図２に示すように、剰余算（ｍｏｄ  Ｒ）は、２ｎビットの演算対象データに対し、下位ｎビットで剰余を算出すればよいことから、演算が容易化されている。
【００３２】
除算（Ｒ-1又は１／Ｒの乗算）は、２ｎビットの演算対象データに対し、上位ｎビットを得るように、ｎビットだけ右シフトすればよいので、演算が容易化されている。
【００３３】
乗算（ｍＲ）は、演算対象データｍに対し、ｎビットだけ左シフトすればよいので、演算が容易化されている。
【００３４】
モンゴメリ乗算部１２は、ｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、モンゴメリ還元部１１によるモンゴメリ還元結果と、乗数Ｒの３乗（Ｒ３  ｍｏｄ  ｐ）とのモンゴメリ乗算を実行するモンゴメリ乗算機能を有し、得られたｎビットのモンゴメリ乗算結果（ｍＲ  ｍｏｄ  ｐ）をモンゴメリ変換結果ｍ’として出力するものである。
【００３５】
ここで、モンゴメリ乗算機能は、図３に示すように、二つのｎビット入力ａ，ｂからｎビットの出力ａｂＲ＾（−１）を算出する機能１２ｆである。具体的には例えば、モンゴメリ乗算機能ｆ１２は、図４に示すように、ｎビット入力ａ，ｂを互いに乗算する通常の乗算機能１２ｆ１と、乗算結果ａｂにモンゴメリ還元を実行するモンゴメリ還元機能１２ｆ２とからなる構成により実現可能となっている。
【００３６】
なお、乗数Ｒの３乗（Ｒ３  ｍｏｄ  ｐ）は、例えば事前に計算して蓄えておけばよい。また、乗数Ｒの３乗（Ｒ３  ｍｏｄ  ｐ）は、これに限らず、乗数Ｒの２乗（Ｒ２  ｍｏｄ  ｐ）を事前に計算して蓄えておき、この乗数Ｒ２  ｍｏｄ  ｐをモンゴメリ乗算で処理することにより、算出してもよい。乗数Ｒの２乗を別途保持する必要がある場合には、乗数Ｒの３乗（Ｒ３  ｍｏｄ  ｐ）と、乗数Ｒの２乗（Ｒ２  ｍｏｄ  ｐ）との両者を格納するときよりも記憶領域を節約できる。但し、乗数Ｒの２乗を別途保持する必要が無い場合にはいずれでもよい。
【００３７】
なお、モンゴメリ還元及びモンゴメリ乗算の各々の演算は、例えば非特許文献１に記載されている。
【００３８】
次に、以上のように構成されたモンゴメリ変換装置の動作を説明する。なお、従来のモンゴメリ変換部３は、図１９に示したように、入力がｎビットである。これに対し、本実施形態のモンゴメリ変換装置１０は、入力が２ｎビットである点が異なっている。以下、順次、説明する。
【００３９】
モンゴメリ変換装置１０では、モンゴメリ還元部１１により、２ｎビットの入力ｍをモンゴメリ還元する。このとき、モンゴメリ還元部１１は、ｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、２ｎビットの入力ｍにモンゴメリ還元を実行し、得られたｎビットのモンゴメリ還元結果（ｍＲ-1  ｍｏｄ  ｐ）をモンゴメリ乗算部１２に出力する。
【００４０】
続いて、モンゴメリ変換装置１０では、モンゴメリ乗算部１２により、モンゴメリ還元結果と、ｎビットの乗数Ｒ＾３  ｍｏｄ  ｐとをモンゴメリ乗算する。
【００４１】
このとき、モンゴメリ乗算部１２は、ｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、モンゴメリ還元結果と、乗数Ｒの３乗Ｒ３  ｍｏｄ  ｐとのモンゴメリ乗算を実行し、得られたｎビットのモンゴメリ乗算結果（ｍＲ  ｍｏｄ  ｐ）をモンゴメリ変換結果ｍ’として出力する。
【００４２】
このように、モンゴメリ変換装置１０は、２ｎビットの入力ｍからｎビットのモンゴメリ変換結果ｍ’（＝ｍＲ  ｍｏｄ  ｐ）を得ることができる。
【００４３】
上述したように本実施形態によれば、従来のｍｏｄ演算及びモンゴメリ変換に代えて、除算を用いないモンゴメリ還元とモンゴメリ乗算とにより２ｎビットの入力ｍからｎビットのモンゴメリ変換結果を得る構成としたので、入力段階の除算（ｍｏｄ演算）を省略しつつ、モンゴメリ演算を実現することができる。
【００４４】
なお、従来のモンゴメリ変換は、図５に示すように、ｎビットの入力ｍと定数Ｒと法ｐを入力し、モンゴメリ変換結果ｍＲ  ｍｏｄ  ｐを出力する。従来のモンゴメリ変換は、図６又は図７に示すように実行される。図６に示す従来のモンゴメリ変換は、入力ｍを左シフトする左シフト機能３ｆ１と、左シフトした入力ｍの法ｐによる剰余を求めるｍｏｄ演算機能３ｆ２とにより、直接計算で実行される。符号ｒは乗数Ｒのビット数を表す。また、図７に示す従来のモンゴメリ変換は、ｎビットの入力ｍと、乗数の二乗Ｒ２ ｍｏｄ  ｐとのモンゴメリ乗算機能３ｆ３により計算される。乗数Ｒの二乗Ｒ＾２  ｍｏｄ  ｐは、事前に計算されている。
【００４５】
いずれにしても、従来のモンゴメリ変換は、図５〜図７に示したように、ｎビットの入力しか扱えないので、２ｎビットの入力ｍをｎビットに減らすｍｏｄ演算部１を入力段階で必要とする。
【００４６】
一方、本実施形態のモンゴメリ変換装置１０は、前述した通り、入力段階の除算を省略しつつ、２ｎビットの入力ｍからｎビットのモンゴメリ変換結果を得ることができる。
【００４７】
（第２の実施形態）
図８は本発明の第２の実施形態に係る演算装置の構成を示す模式図である。  
本実施形態は、第１の実施形態の応用例であり、図１９に示したｍｏｄ演算部１，２及びモンゴメリ変換部３，４に代えて、図１に示したモンゴメリ変換装置１０と同一構成のモンゴメリ変換部１０１，１０２を備えている。
【００４８】
ここで、各モンゴメリ変換部１０１，１０２は、それぞれ前述したモンゴメリ還元部１１及びモンゴメリ乗算部１２を備えている。
【００４９】
また、他のモンゴメリべき乗部５，６、モンゴメリ逆変換部７，８及びＣＲＴ演算部９は、前述した通りである。但し、ここではモンゴメリ還元、モンゴメリべき乗、モンゴメリ逆変換、ＣＲＴ（中国人剰余定理）演算、などの演算について法ｐの場合を例に挙げて簡単に説明する。なお、法ｑの場合も同様に演算できることはいうまでもない。これら各演算の詳細は非特許文献１に記載されている。
【００５０】
モンゴメリ還元部１１は、図９に示すように、除算を使用せず、モンゴメリ還元により、２ｎビットの入力ｍからｎビットの出力ｘｐ＝ｍＲ-1  ｍｏｄ  ｐを計算する。多倍長演算を利用したモンゴメリ還元の効率的な計算方法は非特許文献１に詳しい。
【００５１】
モンゴメリべき乗部５は、図１０に示すように、ｎビットの入力ｍに対してｎビットの出力ｍｄ Ｒ  ｍｏｄ  ｐを計算するモンゴメリべき乗機能５ｆを有している。ここでは、モンゴメリべき乗部５は、図１１に示すように、べき指数ｄ、乗数Ｒｐ及び法ｐに基づいて、モンゴメリ乗算部１２によるモンゴメリ乗算結果ｍｐ’をｄｐ乗し（但し、ｄｐ＝ｄ  ｍｏｄ（ｐ−１））、ｎビットのべき乗剰余ｓｐ’（＝ｍｐ’＾ｄｐ×Ｒｐ  ｍｏｄ  ｐ）を得ている。
【００５２】
モンゴメリ逆変換部７は、図１２に示すように、ｎビットの入力ｍをｎビットの出力ｍＲ-1に変換するモンゴメリ逆変換機能７ｆをもっている。ここでは、モンゴメリ逆変換部７は、図１３に示すように、乗数Ｒｐ及び法ｐに基づいて、モンゴメリべき乗剰余部５からのべき乗剰余ｓｐ’にモンゴメリ逆変換を実行し、ｎビットのモンゴメリ逆変換結果ｓｐ（＝ｍｄ  ｍｏｄ  ｐ）を得ている。
【００５３】
ここで、モンゴメリ逆変換の過程を詳述する。  
モンゴメリ逆変換部７は、入力ｓｐ’をｎビットの出力ｓｐ（＝ｓｐ’Ｒｐ-1  ｍｏｄ  ｐ）にモンゴメリ逆変換し、ｎビットのモンゴメリ逆変換結果ｓｐ（＝ｍｄ  ｍｏｄ  ｐ）を得る。この過程は以下の通りである。
【００５４】
ｓｐ＝ｓｐ’Ｒｐ-1  ｍｏｄ  ｐ  
＝（ｍｐ’＾dp Ｒｐ）Ｒｐ-1  ｍｏｄ  ｐ  
＝ｍｐ’＾dp Ｒｐ-1  ｍｏｄ  ｐ  
＝ｍ＾dp Ｒｐ＾dp Ｒｐ＾-(dp-1)  Ｒｐ-1  ｍｏｄ  ｐ  
＝ｍ＾dp  ｍｏｄ  ｐ  
＝ｍd mod (p-1)  ｍｏｄ  ｐ  
＝ｍk(p-1)+ｄ  ｍｏｄ  ｐ  
＝（ｍp-1）k ｍｄ  ｍｏｄ  ｐ  
＝ｍｄ  ｍｏｄ  ｐ
但し、ｋは任意の整数。ｍp-1 ≡ １  ｍｏｄ  ｐはフェルマーの小定理。
【００５５】
なお、モンゴメリ逆変換機能７ｆは、図１４に示すように、入力ｍに１を乗じるようにしたモンゴメリ乗算機能により実現可能である。
【００５６】
ＣＲＴ演算部９は、図１５に示すように、２つのｎビット入力ｓ  ｍｏｄ  ｐとｓ  ｍｏｄ  ｑから中国人剰余定理（ＣＲＴ）に基づいて、２ｎビットのｓ  ｍｏｄ  ｐｑを計算するＣＲＴ演算機能９ｆをもっている。ここでは、ＣＲＴ演算部９は、法ｐ，ｑ及び中国人剰余定理に基づいて、２つのモンゴメリ逆変換部７，８によるモンゴメリ逆変換結果ｓｐとｓｐとの連立方程式を解き、得られたｎビットの解（ｍｄ  ｍｏｄ  ｐｑ）をべき乗剰余ｓとして出力している。
【００５７】
次に、以上のように構成された演算装置の動作を説明する。  
演算装置では、各モンゴメリ還元部１１により、２ｎビットの入力ｍを各々モンゴメリ還元する。このとき、一方のモンゴメリ還元部１１は、ｎビット以上の乗数Ｒ及びｎビットの法ｐに基づいて、２ｎビットの入力ｍにモンゴメリ還元を実行し、得られたｎビットのモンゴメリ還元結果ｘｐ（＝ｍＲ-1  ｍｏｄ  ｐ）をモンゴメリ乗算部１２に出力する。同様に、他方のモンゴメリ還元部１１は、ｎビット以上の乗数Ｒ及びｎビットの法ｑに基づいて、２ｎビットの入力ｍにモンゴメリ還元を実行し、得られたｎビットのモンゴメリ還元結果ｘｑ（＝ｍＲ-1  ｍｏｄ  ｑ）をモンゴメリ乗算部１２に出力する。
【００５８】
次に、一方のモンゴメリ乗算部１２は、モンゴメリ還元結果ｘｐと乗数Ｒｐ３  ｍｏｄ  ｐとをモンゴメリ乗算し、得られたモンゴメリ乗算結果ｍｐ’（＝ｍＲｐ  ｍｏｄ  ｐ）をモンゴメリべき乗部５に出力する。同様に、他方のモンゴメリ乗算部１２は、モンゴメリ還元結果ｘｑと乗数Ｒｑ３  ｍｏｄ  ｑとをモンゴメリ乗算し、得られたモンゴメリ乗算結果ｍｑ’（＝ｍＲｑ  ｍｏｄ  ｑ）をモンゴメリべき乗部６に出力する。
【００５９】
これら各モンゴメリ乗算結果ｍｐ’ｍｑ’は、図１９に示した従来のモンゴメリ変換部３，４の出力と一致しており、ここまでの計算でｍｏｄ演算は使用していない。
【００６０】
以下、図１９に示した通り、モンゴメリべき乗、モンゴメリ逆変換を経て中国人剰余定理により、べき乗剰余ｓ＝ｍｄ  ｍｏｄ  ｐｑが計算される。
【００６１】
上述したように本実施形態によれば、従来のｍｏｄ演算及びモンゴメリ変換に代えて、モンゴメリ還元とモンゴメリ乗算とにより２ｎビットの入力ｍからｎビットのモンゴメリ変換結果を得る構成を、中国人剰余定理を用いた べき乗剰余算の入力段階に備えたので、入力段階の除算を省略しつつ、中国人剰余定理とモンゴメリ演算とを組み合わせた べき乗剰余算を実行することができる。
【００６２】
補足すると、本実施形態の演算装置は、入力段階で除算が無くても、中国人剰余定理とモンゴメリ演算を組み合わせた効率的な実装を実現できるため、回路規模の小型化と、演算速度の高速化とを実現できる。なお、除算は入力によって実行時間や処理が変わる演算なのでサイドチャネル攻撃に対して脆弱であるという欠点をもっている。しかしながら、本実施形態の演算装置は、除算を用いないので、サイドチャネル攻撃に対する安全性を向上させることができる。
【００６３】
（第３の実施形態）
図１７は本発明の第３の実施形態に係るＩＣカードの構成を示す模式図である。このＩＣカード２０は、ＩＣチップ３０を備えている。
【００６４】
ここで、ＩＣチップ３０は、ＲＯＭ３１、ＮＶＲＡＭ３２、ＲＡＭ３３、Ｉ／Ｏ３４、ＣＰＵ３５及び暗号アクセラレータ３６が互いにバス３７を介して接続されている。暗号アクセラレータ以外のハードウェア構成は、通常のコンピュータと同様である。
【００６５】
暗号アクセラレータ（コプロセッサ）３６は、暗号処理を効率化するための演算装置であり、図１８に示すように、積和演算回路３８及び制御回路３９を備えている。
【００６６】
積和演算回路３８は、レジスタ３８ａ、ＡＬＵ（算術論理演算装置）３８ｂ、乗算器３８ｃ及び加算器３８ｄ等の複数の演算器から構成されており、制御回路３９からの制御により、バス３７から入力された２ｎビットの入力ｍからｎビットのべき乗剰余ｍｄ  ｍｏｄ  ｐｑを算出する機能をもっている。
【００６７】
制御回路３９は、第２の実施形態に述べたモンゴメリ還元、モンゴメリ乗算、モンゴメリべき乗、モンゴメリ逆変換及びＣＲＴ演算からなる一連のべき乗剰余算を実行するように、積和演算回路３８を制御するものである。これら一連のべき乗剰余算は、乗算器３８ｃや加算器３８ｄなどによる演算の組合せで実現可能である。
【００６８】
次に、以上のように構成されたＩＣカードの動作を説明する。  
ＩＣカード２０では、ＣＰＵ３５が何らかの処理中に、演算対象データｍに対し、べき乗剰余ｍｄｍｏｄ ｐｑを算出する必要を生じたとする。何らかの処理とは、例えば公開鍵暗号方式における暗号処理、復号処理、署名生成処理又は署名検証処理などである。
【００６９】
ＣＰＵ３５は、２ｎビットの演算対象データｍを暗号アクセラレータ３６に入力する。暗号アクセラレータ３６は、２ｎビットの入力ｍに対し、積和演算回路３８が制御回路３９の制御により一連のべき乗剰余算を実行する。
【００７０】
このとき、制御回路３９は、モンゴメリ還元とモンゴメリ乗算とにより２ｎビットの入力ｍからｎビットのモンゴメリ変換結果を得るように、中国人剰余定理を用いた べき乗剰余算の入力段階を制御する。
【００７１】
従って、暗号アクセラレータ３６は、入力段階の除算を省略しつつ、中国人剰余定理とモンゴメリ演算とを組み合わせた べき乗剰余算を実行することができる。なお、暗号アクセラレータ３６は、得られたｎビットのべき乗剰余ｍｄｍｏｄ ｐｑをバス３７を介してＲＡＭ３２に書き込む。
【００７２】
ＣＰＵ３５は、ＲＡＭ３２内のべき乗剰余を用いて処理を継続する。
【００７３】
上述したように本実施形態によれば、第２の実施形態に述べた べき乗剰余算を実行する暗号アクセラレータ３６をＩＣチップ３０に備えたので、第２の実施形態の効果を奏するＩＣカード２０を実現させることができる。
【００７４】
なお、本実施形態は、制御回路３９による制御に限らず、ＲＯＭ３１内のプログラムに基づいて、ＣＰＵ３５が暗号アクセラレータ３６によるべき乗剰余算を制御する構成に変形してもよい。このように変形しても、前述同様に、第２の実施形態の効果を奏するＩＣカード２０を実現させることができる。
【００７５】
（第４〜第６の実施形態）
続いて、本発明の第４〜第６の実施形態について説明する。第４〜第６の実施形態は、第３の実施形態の具体例であり、ＣＰＵ３５が実行中の処理をＲＳＡ署名処理、ＲＳＡ復号処理、又はＤＳＡ署名処理としたものである。以下、順次説明する。
【００７６】
（第４の実施形態）
本実施形態は、前述した暗号アクセラレータ３６を備え、署名対象の文書データＤに対し、ＲＳＡ署名方式の秘密鍵ｄによりＲＳＡ署名処理を実行するＩＣカード２０に関する。
【００７７】
ここで、ＩＣカード２０は、以下の機能３５ｆ１〜３５ｆ４をＣＰＵ３５に実行させるためのプログラムがＲＯＭ３１に保存されている。
【００７８】
（３５ｆ１）ＲＳＡ署名処理を実行する際に、文書データＤの一方向性ハッシュ関数を演算し、ハッシュ値ｈ（Ｄ）を得る機能。
【００７９】
（３５ｆ２）このハッシュ値ｈ（Ｄ）を入力ｍとして暗号アクセラレータ３６に入力すると共に、秘密鍵ｄをべき指数ｄとして暗号アクセラレータ３６に入力する機能。
【００８０】
（３５ｆ３）これら入力の後、暗号アクセラレータから出力されたべき乗剰余ｓをＲＳＡ署名ｓ（＝ｈ（Ｄ）ｄ  ｍｏｄ  ｐｑ）としてＮＶＲＡＭ３２に保存する機能。
【００８１】
（３５ｆ４）ＲＳＡ署名ｓをＩ／Ｏ３４を介して外部コンピュータ等に出力する機能。
【００８２】
以上のような構成によれば、ＲＳＡ署名処理の際に、ＣＰＵ３５が、ハッシュ値ｈ（Ｄ）のべき乗剰余算を暗号アクセラレータ３６に実行させるので、ＲＳＡ署名処理において、第２の実施形態の効果を奏するＩＣカード２０を実現させることができる。
【００８３】
（第５の実施形態）
本実施形態は、前述した暗号アクセラレータ３６を備え、ＲＳＡ暗号方式の公開鍵ｅにより平文データＤが暗号処理されてなる暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）に対し、公開鍵ｅの鍵ペアである秘密鍵ｄによるＲＳＡ復号処理を実行するＩＣカード２０に関する。
【００８４】
ここで、ＩＣカード２０は、以下の機能３５ｆ１１〜３５ｆ１４をＣＰＵ３５に実行させるためのプログラムがＲＯＭ３１に保存されている。
【００８５】
（３５ｆ１１）ＲＳＡ復号処理を実行する際に、暗号文ｃを入力ｍとして暗号アクセラレータ３６に入力する機能と共に、秘密鍵ｄをべき指数ｄとして暗号アクセラレータ３６に入力する機能。
【００８６】
（３５ｆ１２）これら入力の後、暗号アクセラレータ３６から出力されたべき乗剰余ｓをＲＳＡ復号結果ｓ（＝ｃｄ  ｍｏｄ  ｐｑ）としてＮＶＲＡＭ３２に保存する機能。
【００８７】
（３５ｆ１３）ＲＳＡ復号結果ｓをＩ／Ｏ３４を介して外部コンピュータ等に出力する機能。
【００８８】
以上のような構成によれば、ＲＳＡ復号処理の際に、ＣＰＵ３５が、暗号文ｃのべき乗剰余算を暗号アクセラレータ３６に実行させるので、ＲＳＡ復号処理において、第２の実施形態の効果を奏するＩＣカード２０を実現させることができる。
【００８９】
（第６の実施形態）
本実施形態は、前述した暗号アクセラレータ３６を備え、署名対象の文書データＤに対し、ＤＳＡ署名方式の公開鍵ｇ及び秘密鍵ｘに基づいてＤＳＡ署名処理を実行するＩＣカード２０に関する。
【００９０】
ここで、ＩＣカード２０は、以下の機能３５ｆ２１〜３５ｆ２８をＣＰＵ３５に実行させるためのプログラムがＲＯＭ３１に保存されている。
【００９１】
（３５ｆ２１）ＤＳＡ署名処理を実行する際に、法ｑの乗法群Ｚｑ＊からランダムに乱数ｋを選択する機能。
【００９２】
（３５ｆ２２）公開鍵ｇを入力ｍとして暗号アクセラレータ３６に入力すると共に、乱数ｋをべき指数ｄとして暗号アクセラレータ３６に入力する機能。
【００９３】
（３５ｆ２３）これら入力の後、暗号アクセラレータ３６を、一方のモンゴメリ変換部１０１、モンゴメリべき乗部５及びモンゴメリ逆変換部７として機能するように制御する機能。
【００９４】
（３５ｆ２４）暗号アクセラレータ３６から出力されたべき乗剰余（ｇｋ  ｍｏｄ  ｐ）及び予め保持した法ｑに基づいて、ＤＳＡ署名の第１部分データｒ（＝（ｇｋ  ｍｏｄ  ｐ）  ｍｏｄ  ｑ）を生成する機能。
【００９５】
（３５ｆ２５）文書データＤの一方向性ハッシュ関数を演算し、ハッシュ値ｈ（Ｄ）を得る機能。
【００９６】
（３５ｆ２６）乱数ｋ、ハッシュ値ｈ（Ｄ）、秘密鍵ｘ、第１部分データｒ及び法ｑに基づいてＤＳＡ署名処理を実行し、ＤＳＡ署名の第２部分データｓ（＝ｋ-1（ｈ（Ｄ）＋ｘｒ）ｍｏｄ  ｑ）を生成する機能。
【００９７】
（３５ｆ２７）第１及び第２部分データｒ，ｓをＤＳＡ署名（ｒ，ｓ）としてＮＶＲＡＭ３２に保存する機能。
【００９８】
（３５ｆ２８）ＤＳＡ署名（ｒ，ｓ）をＩ／Ｏ３４を介して外部コンピュータ等に出力する機能。
【００９９】
以上のような構成によれば、ＤＳＡ署名処理の際に、ＣＰＵ３５が、暗号文ｃのべき乗剰余算を暗号アクセラレータ３６に実行させるので、ＤＳＡ署名処理において、第２の実施形態の効果を奏するＩＣカード２０を実現させることができる。
【０１００】
（第７〜第８の実施形態）
続いて、本発明の第７〜第８の実施形態について説明する。第７〜第８の実施形態は、第３の実施形態の具体例及び変形例であり、ＣＰＵ３５が実行中の処理をＲＳＡ暗号処理又はＲＳＡ復号処理としたものである。但し、ＩＣチップ３０を備えたＩＣカード２０に代えて、同様のＩＣチップ３０を備えた暗号装置又は復号装置として実現したものである。以下、順次説明する。
【０１０１】
（第７の実施形態）
本実施形態は、前述した暗号アクセラレータ３６を備え、暗号化対象の平文データＤに対し、ＲＳＡ暗号方式の公開鍵ｅに基づいてＲＳＡ暗号処理を実行する暗号装置に関する。
【０１０２】
ここで、暗号装置は、以下の機能３５ｆ３１〜３５ｆ３３をＣＰＵ３５に実行させるためのプログラムがＲＯＭ３１に保存されている。
【０１０３】
（３５ｆ３１）ＲＳＡ暗号処理を実行する際に、平文データＤを入力ｍとして暗号アクセラレータ３６に入力すると共に、公開鍵ｅをべき指数ｄとして暗号アクセラレータ３６に入力する機能。
【０１０４】
（３５ｆ３２）これら入力の後、暗号アクセラレータ３６から出力されたべき乗剰余ｓをＲＳＡ暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）としてＮＶＲＡＭ３２に保存する機能。
【０１０５】
（３５ｆ３３）ＲＳＡ暗号文ｃをＩ／Ｏ３４を介して外部コンピュータ等に出力する機能。
【０１０６】
以上のような構成によれば、ＲＳＡ暗号化処理の際に、ＣＰＵ３５が、平文データＤのべき乗剰余算を暗号アクセラレータ３６に実行させるので、ＲＳＡ暗号化処理において、第２の実施形態の効果を奏する暗号装置を実現させることができる。
【０１０７】
（第８の実施形態）
本実施形態は、前述した暗号アクセラレータ３６を備え、ＲＳＡ暗号方式の公開鍵ｅにより平文データＤが暗号処理されてなる暗号文ｃ（＝Ｄｅ  ｍｏｄ  ｐｑ）に対し、公開鍵ｅの鍵ペアである秘密鍵ｄによるＲＳＡ復号処理を実行する復号装置に関する。
【０１０８】
ここで、復号装置は、以下の機能３５ｆ４１〜３５ｆ４３をＣＰＵ３５に実行させるためのプログラムがＲＯＭ３１に保存されている。
【０１０９】
（３５ｆ４１）ＲＳＡ復号処理を実行する際に、暗号文ｃを入力ｍとして暗号アクセラレータ３６に入力する機能と共に、秘密鍵ｄをべき指数ｄとして暗号アクセラレータ３６に入力する機能。
【０１１０】
（３５ｆ４２）これら入力の後、暗号アクセラレータ３６から出力されたべき乗剰余ｓをＲＳＡ復号結果ｓ（＝ｃｄ  ｍｏｄ  ｐｑ）としてＮＶＲＡＭ３２に保存する機能。
【０１１１】
（３５ｆ４３）ＲＳＡ復号結果ｓをＩ／Ｏ３４を介して外部コンピュータ等に出力する機能。
【０１１２】
以上のような構成によれば、ＲＳＡ復号処理の際に、ＣＰＵ３５が、暗号文ｃのべき乗剰余算を暗号アクセラレータ３６に実行させるので、ＲＳＡ復号処理において、第２の実施形態の効果を奏する復号装置を実現させることができる。
【０１１３】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１１４】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１１５】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１１６】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１１７】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１８】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１１９】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１２０】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１２１】
【図１】本発明の第１の実施形態に係るモンゴメリ変換装置の構成を示す模式図である。
【図２】同実施形態における乗数Ｒを用いた演算を説明するための模式図である。
【図３】一般的なモンゴメリ乗算機能を説明するための模式図である。
【図４】一般的なモンゴメリ乗算機能の構成を示す模式図である。
【図５】従来のモンゴメリ変換を説明するための模式図である。
【図６】従来のモンゴメリ変換の構成を示す模式図である。
【図７】従来のモンゴメリ変換の構成を示す模式図である。
【図８】本発明の第２の実施形態に係る演算装置の構成を示す模式図である。
【図９】同実施形態におけるモンゴメリ還元部の構成を示す模式図である。
【図１０】一般的なモンゴメリべき乗機能を説明するための模式図である。
【図１１】同実施形態におけるモンゴメリべき乗部の構成を示す模式図である。
【図１２】一般的なモンゴメリ逆変換機能を説明するための模式図である。
【図１３】同実施形態におけるモンゴメリ逆変換部の構成を示す模式図である。
【図１４】一般的なモンゴメリ逆変換機能の構成を示す模式図である。
【図１５】一般的なＣＲＴ演算機能を説明するための模式図である。
【図１６】同実施形態におけるＣＲＴ演算部の構成を示す模式図である。
【図１７】本発明の第３の実施形態に係るＩＣカードの構成を示す模式図である。
【図１８】同実施形態における暗号アクセラレータの構成を示す模式図である。
【図１９】従来の演算装置の論理的な構成を示す模式図である。
【符号の説明】
【０１２２】
５，６…モンゴメリべき乗部、７，８…モンゴメリ逆変換部、９…ＣＲＴ演算部、１０…モンゴメリ変換装置、１０１，１０２…モンゴメリ変換部、１１…モンゴメリ還元部、１２…モンゴメリ乗算部、２０…ＩＣカード、３０…ＩＣチップ、３１…ＲＯＭ、３２…ＮＶＲＡＭ、３３…ＲＡＭ、３４…Ｉ／Ｏ、３５…ＣＰＵ、３６…暗号アクセラレータ、３７…バス、３８…積和演算回路、３８ａ…レジスタ、３８ｂ…ＡＬＵ、３８ｃ…乗算器、３８ｄ…加算器、３９…制御回路。
【図１】
2006145852.tif 000003
【図２】
2006145852.tif 000004
【図３】
2006145852.tif 000005
【図４】
2006145852.tif 000006
【図５】
2006145852.tif 000007
【図６】
2006145852.tif 000008
【図７】
2006145852.tif 000009
【図８】
2006145852.tif 000010
【図９】
2006145852.tif 000011
【図１０】
2006145852.tif 000012
【図１１】
2006145852.tif 000013
【図１２】
2006145852.tif 000014
【図１３】
2006145852.tif 000015
【図１４】
2006145852.tif 000016
【図１５】
2006145852.tif 000017
【図１６】
2006145852.tif 000018
【図１７】
2006145852.tif 000019
【図１８】
2006145852.tif 000020
【図１９】
2006145852.tif 000021