(57)【特許請求の範囲】
【請求項１】
自然数である被演算値Ｓを保持している保持手段と、
被演算値Ｓを読み出す読出手段と、
（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数１】
0004638176.tif 000025
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出手段と、
有限体上のべき乗剰余演算
Ｓ’＝  Ｓ１／Ｐ  ｍｏｄ  Ｎ          （式１）
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出手段により選出された全素数の積）
を行う演算手段と、 前記演算手段により演算された演算結果値Ｓ’に可逆演算を施し、可逆演算結果値を得る可逆演算手段と、
前記可逆演算手段により演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする書込手段とを備え、
前記選出手段による選出、前記演算手段によるべき乗剰余演算、前記可逆演算手段による可逆演算、前記書込手段による可逆演算結果値の前記保持手段への上書きを繰り返すよう制御する
ことを特徴とするべき乗剰余演算装置。
【請求項２】
前記選出手段は、
ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、
ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、
前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択手段と
を備えることを特徴とする請求項１に記載のべき乗剰余演算装置。
【請求項３】
前記べき乗剰余演算装置は、
ａ分木のルートから１のリーフまでの経路上の各枝について、ルートからリーフへの順序で、前記枝取得手段、前記素数選択手段、前記演算手段、前記可逆演算手段、前記書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式１に基づくべき乗剰余演算と、演算結果値Ｓ’への可逆演算と、可逆演算結果値の前記保持手段への上書きとを繰り返すように制御する繰返制御手段
を備えることを特徴とする請求項２に記載のべき乗剰余演算装置。
【請求項４】
前記可逆演算手段は、前記演算手段により演算された演算結果値Ｓ’に定数を加算して、可逆演算結果値を得る
ことを特徴とする請求項１に記載のべき乗剰余演算装置。
【請求項５】
ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、
ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記いずれかのノードに接続するａ個の枝のうち、無効化されていない枝全てを含む組合せに対応する素数を選出する有効素数選出手段と、
被演算値Ｔを保持するための保持手段と、
有限体上のべき乗剰余演算
Ｔ１／Ｐ  ｍｏｄ  Ｎ          （式２）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記有効素数選出手段により選出された素数である）  を行う演算手段と、
自然数である被演算値Ｓを記憶している記憶手段と、
被演算値Ｓを読み出す読出手段と、
ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、
前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選出手段と、
有限体上のべき乗剰余演算
Ｓ’＝Ｓ１／Ｑ  ｍｏｄ  Ｎ          （式３）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記素数選出手段により選出された全素数の積である）
を行う生成手段と、
前記生成手段により演算された演算結果値Ｓ’に可逆演算を施して、前記記憶手段に記憶している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込手段と、
ａ分木のルートから１のノードまでの経路上の各枝について、ルートから前記ノードへの順序で、前記枝取得手段、前記素数選出手段、前記生成手段、前記第１書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式３に基づくべき乗剰余演算と、演算された演算結果値Ｓ’への可逆演算及び可逆演算結果の上書きとを繰り返すように制御する繰返制御手段と、
前記繰返制御手段による繰り返し制御により得られた結果値Ｓ’を、Ｔとして前記保持手段に書き込む第２書込手段と、  前記有効素数選出手段、前記演算手段に対して、それぞれ、無効化されていない枝全てを含む組合せに対応する素数の選出と、式２に基づくべき乗剰余演算とを行わせるよう制御する演算制御手段と
を備えることを特徴とするべき乗剰余演算装置。
【請求項６】
ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、
前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得手段と、
被演算値Ｓ’を保持するための保持手段と、
有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ              （式４）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）  を行う演算手段と、
自然数である被演算値Ｓを記憶している記憶手段と、
被演算値Ｓを読み出す読出手段と、
ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、
前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択手段と、
有限体上のべき乗剰余演算
Ｒ  ＝  ＳＰ  ｍｏｄ  Ｎ          （式５）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記素数選択手段により選出された全素数の積）を行う生成手段と、
前記生成手段により演算された演算結果値Ｒに可逆演算を施して、前記記憶手段に記憶している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込手段と、
ａ分木の１のリーフから１のノードまでの経路上の各枝について、前記リーフから前記ノードへの順序で、前記枝取得手段、前記素数選出手段、前記生成手段、前記第１書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式５に基づくべき乗剰余演算と、演算された演算結果値Ｒへの可逆演算及び可逆演算結果の上書きとを繰り返すように制御する繰返制御手段と、
前記繰返制御手段による繰り返し制御により得られた結果値ＲをＳ’として前記保持手段に書き込む第２書込手段と、
前記取得手段、前記演算手段に対して、それぞれ、前記指定情報の取得と、式４に基づくべき乗剰余演算とを行わせるよう制御する演算制御手段と
を備えることを特徴とするべき乗剰余演算装置。
【請求項７】
請求項１に記載のべき乗剰余演算装置による演算結果Ｓ’に対し、演算を行うべき乗剰余演算装置であって、
前記Ｓ’を保持する保持手段と、
（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数２】
0004638176.tif 000026
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出手段と、
有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出手段により選出された全素数の積）  を行う演算手段と、
前記演算手段により演算された演算結果値に可逆演算を施し、可逆演算結果値を得る可逆演算手段と、
前記可逆演算手段により演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓ’に、前記被演算値Ｓ’として上書きする書込手段とを備え、
前記選出手段による選出、前記演算手段によるべき乗剰余演算、前記可逆演算手段による可逆演算、前記書込手段による可逆演算結果値の前記保持手段への上書きを繰り返すよう制御する
ことを特徴とするべき乗剰余演算装置。
【請求項８】
再生装置においてコンテンツの復号に用いられる鍵を管理する鍵管理装置であって、
べき乗剰余演算装置を含み、
前記べき乗剰余演算装置は、
自然数である被演算値Ｓを保持している保持手段と、
被演算値Ｓを読み出す読出手段と、
（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数３】
0004638176.tif 000027
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出手段と、
有限体上のべき乗剰余演算
Ｓ’＝  Ｓ１／Ｐ  ｍｏｄ  Ｎ          （式１）
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出手段により選出された全素数の積）  を行う演算手段と、
前記演算手段により演算された演算結果値Ｓ’に可逆演算を施し、可逆演算結果値を得る可逆演算手段と、
前記可逆演算手段により演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする書込手段とを備え、
前記選出手段による選出、前記演算手段によるべき乗剰余演算、前記可逆演算手段による可逆演算、前記書込手段による可逆演算結果値の前記保持手段への上書きを繰り返すよう制御し、得られたＳ’を前記コンテンツの復号に用いられるデバイス鍵として管理する
ことを特徴とする鍵管理装置。
【請求項９】
再生装置においてコンテンツの復号に用いられる鍵を管理する鍵管理装置であって、
べき乗剰余演算装置を含み、
前記べき乗剰余演算装置は、
ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、
ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記いずれかのノードに接続するａ個の枝のうち、無効化されていない枝全てを含む組合せに対応する素数を選出する有効素数選出手段と、
被演算値Ｔを保持するための保持手段と、
有限体上のべき乗剰余演算
Ｔ１／Ｐ  ｍｏｄ  Ｎ          （式２）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記有効素数選出手段により選出された素数である）  を行う演算手段と、
自然数である被演算値Ｓを記憶している記憶手段と、
被演算値Ｓを読み出す読出手段と、
ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、
前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選出手段と、
有限体上のべき乗剰余演算
Ｓ’＝Ｓ１／Ｑ  ｍｏｄ  Ｎ          （式３）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記素数選出手段により選出された全素数の積である）
を行う生成手段と、
前記生成手段により演算された演算結果値Ｓ’に可逆演算を施して、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込手段と、
ａ分木のルートから１のノードまでの経路上の各枝について、ルートから前記ノードへの順序で、前記枝取得手段、前記素数選出手段、前記生成手段、前記第１書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式３に基づくべき乗剰余演算と、演算された演算結果値Ｓ’へ可逆演算及び可逆演算結果のＳとしての出力とを繰り返すように制御する繰返制御手段と、
前記繰返制御手段による繰り返し制御により得られた結果値Ｓ’を、Ｔとして前記保持手段に書き込む第２書込手段と、  前記有効素数選出手段、前記演算手段に対して、それぞれ、無効化されていない枝全てを含む組合せに対応する素数の選出と、式２に基づくべき乗剰余演算とを行わせるよう制御する演算制御手段とを備え、
前記演算手段による演算結果値を前記コンテンツの復号に用いられる鍵とする
ことを特徴とする鍵管理装置。
【請求項１０】
暗号化コンテンツを復号再生する再生装置であって、
べき乗剰余演算装置を含み、
前記べき乗剰余演算装置は、
ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、
前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得手段と、
被演算値Ｓ’を保持するための保持手段と、
有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ  （式４）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）  を行う演算手段と、
自然数である被演算値Ｓを記憶している記憶手段と、
被演算値Ｓを読み出す読出手段と、
ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、
前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択手段と、
有限体上のべき乗剰余演算
Ｒ  ＝  ＳＰ  ｍｏｄ  Ｎ          （式５）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記素数選択手段により選出された全素数の積）を行う生成手段と、
前記生成手段により演算された演算結果値Ｒに可逆演算を施して、前記記憶手段に記憶している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込手段と、
ａ分木の１のリーフから１のノードまでの経路上の各枝について、前記リーフから前記ノードへの順序で、前記枝取得手段、前記素数選出手段、前記生成手段、前記第１書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式５に基づくべき乗剰余演算と、演算された演算結果値Ｒの前記記憶手段への書込みとを繰り返すように制御する繰返制御手段と、
前記繰返制御手段による繰り返し制御の終了後、前記演算結果値Ｒを、Ｓ’として前記保持手段に書き込む第２書込手段と、
前記取得手段、前記演算手段に対して、それぞれ、前記指定情報の取得と、式４に基づくべき乗剰余演算とを行わせるよう制御する演算制御手段とを備え、
前記演算手段による演算結果値を復号鍵として前記暗号化コンテンツを復号し、再生する
ことを特徴とする再生装置。
【請求項１１】
コンテンツを暗号化して記録する記録装置であって、
べき乗剰余演算装置を含み、
前記べき乗剰余演算装置は、
ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、
前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得手段と、
被演算値Ｓ’を保持するための保持手段と、
有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ  （式４）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）  を行う演算手段と、
自然数である被演算値Ｓを記憶している記憶手段と、
被演算値Ｓを読み出す読出手段と、
ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、
前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択手段と、
有限体上のべき乗剰余演算
Ｒ  ＝  ＳＰ  ｍｏｄ  Ｎ          （式５）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記素数選択手段により選出された全素数の積）を行う生成手段と、
前記生成手段により演算された演算結果値Ｒに可逆演算を施して、前記記憶手段に記憶している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込手段と、
ａ分木の１のリーフから１のノードまでの経路上の各枝について、前記リーフから前記ノードへの順序で、前記枝取得手段、前記素数選出手段、前記生成手段、前記第１書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式５に基づくべき乗剰余演算と、演算された演算結果値Ｒの前記記憶手段への書込みとを繰り返すように制御する繰返制御手段と、
前記繰返制御手段による繰り返し制御の終了後、前記演算結果値Ｒを、Ｓ’として前記保持手段に書き込む第２書込手段と、
前記取得手段、前記演算手段に対して、それぞれ、前記指定情報の取得と、式４に基づくべき乗剰余演算とを行わせるよう制御する演算制御手段とを備え、
前記演算手段による演算結果値に基づき前記コンテンツを暗号化し、記憶する
ことを特徴とする記録装置。
【請求項１２】
コンテンツを暗号化して記録する記録装置であって、
べき乗剰余演算装置を含み、
前記べき乗剰余演算装置は、
自然数である被演算数Ｓ’を保持している保持手段と、
（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数４】
0004638176.tif 000028
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出手段と、
有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出手段により選出された全素数の積）  を行う演算手段と、
前記演算手段により演算された演算結果値に可逆演算を施し、可逆演算結果値を得る可逆演算手段と、
前記可逆演算手段により演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓ’に、前記被演算値Ｓ’として上書きする書込手段とを備え、
前記選出手段による選出、前記演算手段によるべき乗剰余演算、前記可逆演算手段による可逆演算、前記書込手段による可逆演算結果値の前記保持手段への上書きを繰り返すよう制御し、得られた結果に基づき前記コンテンツを暗号化し記憶する
ことを特徴とする記録装置。
【請求項１３】
自然数である被演算値Ｓを保持している保持手段と、読出手段と、選出手段と、演算手段と、可逆演算手段と、書込手段とから成るべき乗剰余演算装置による、べき乗剰余演算方法であって、
単位ステップを繰り返す繰り返しステップを含み、
前記単位ステップは、
前記読出手段により、被演算値Ｓを読み出す読出ステップと、
前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数５】
0004638176.tif 000029
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、
前記演算手段により、有限体上のべき乗剰余演算
Ｓ’＝  Ｓ１／Ｐ  ｍｏｄ  Ｎ          （式１）
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出ステップにおいて選出された全素数の積）
を行う演算ステップと、 前記可逆演算手段により、前記演算ステップにおいて演算された演算結果値Ｓ’に可逆演算を施し、可逆演算結果値を得る可逆演算ステップと、
前記書込手段により、前記可逆演算ステップにおいて演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする書込ステップと
を含むことを特徴とするべき乗剰余演算方法。
【請求項１４】
被演算値Ｔを保持するための保持手段と、自然数である被演算値Ｓを記憶している記憶手段と、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、有効素数選出手段と、演算手段と、読出手段と、枝取得手段と、素数選出手段と、生成手段と、第１書込手段と、第２書込手段と、演算制御手段とから成るべき乗剰余演算装置による、べき乗剰余演算方法であって、
前記有効素数選出手段により、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記いずれかのノードに接続するａ個の枝のうち、無効化されていない枝全てを含む組合せに対応する素数を選出する有効素数選出ステップと、
前記演算手段により、有限体上のべき乗剰余演算
Ｔ１／Ｐ  ｍｏｄ  Ｎ          （式２）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記有効素数選出ステップにおいて選出された素数である）  を行う演算ステップと、
ａ分木のルートから１のノードまでの経路上の各枝について、ルートから前記ノードへの順序で単位ステップを繰り返す繰り返しステップとを含み、
前記単位ステップは、
前記読出手段により、被演算値Ｓを読み出す読出ステップと、
前記枝取得手段により、ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得ステップと、
前記素数選出手段により、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選出ステップと、
前記生成手段により、有限体上のべき乗剰余演算
Ｓ’＝Ｓ１／Ｑ  ｍｏｄ  Ｎ          （式３）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記素数選出ステップにおいて選出された全素数の積である）
を行う生成ステップと、
前記第１書込手段により、前記生成ステップにおいて演算された演算結果値Ｓ’に可逆演算を施して、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込ステップとを含み、
さらに、前記第２書込手段により、前記繰り返しステップにより得られた結果値Ｓ’を、Ｔとして前記保持手段に書き込む第２書込ステップと、  前記演算制御手段により、前記有効素数選出ステップ、前記演算ステップを行わせるよう制御する演算制御ステップと
を含むことを特徴とするべき乗剰余演算方法
【請求項１５】
被演算数Ｓ’を保持するための保持手段と、自然数である被演算値Ｓを記憶している記憶手段と、ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、取得手段と、演算手段と、読出手段と、枝取得手段と、素数選択手段と、生成手段と、第１書込手段と、第２書込手段と、演算制御手段とから成るべき乗剰余演算装置による、べき乗剰余演算方法であって、
前記取得手段により、前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得ステップと、
前記演算手段により、有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ              （式４）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）  を行う演算ステップと、
ａ分木の１のリーフから１のノードまでの経路上の各枝について、前記リーフから前記ノードへの順序で単位ステップを繰り返す繰り返しステップとを含み、
前記単位ステップは、
前記読出手段により、被演算値Ｓを読み出す読出ステップと、
前記枝取得手段により、ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得ステップと、
前記素数選択手段により、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択ステップと、
前記生成手段により、
有限体上のべき乗剰余演算
Ｒ  ＝  ＳＰ  ｍｏｄ  Ｎ          （式５）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記素数選択ステップにおいて選出された全素数の積）を行う生成ステップと、
前記第１書込手段により、前記生成ステップにおいて演算された演算結果値Ｒに可逆演算を施して、前記記憶手段に記憶している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込ステップと
を含み、
さらに、前記第２書込手段により、前記繰り返しステップにより得られた結果値Ｒを、Ｓ’として前記保持手段に書き込む第２書込ステップと、  前記演算制御手段により、前記取得ステップ、前記演算ステップを行わせるよう制御する演算制御ステップと
を含むことを特徴とするべき乗剰余演算方法。
【請求項１６】
請求項１３に記載のべき乗剰余演算方法による演算結果Ｓ’に対し演算を行う、前記Ｓ’を保持する保持手段と、選出手段と、演算手段と、可逆演算手段と、書込手段とから成るべき乗剰余演算装置によるべき乗剰余演算方法であって、  単位ステップを繰り返す繰り返しステップを含み、
前記単位ステップは、
前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数６】
0004638176.tif 000030
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、
前記演算手段により、有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出ステップにおいて選出された全素数の積）  を行う演算ステップと、
前記可逆演算手段により、前記演算ステップにおいて演算された演算結果値に可逆演算を施し、可逆演算結果値を得る可逆演算ステップと、
前記書込手段により、前記可逆演算ステップにおいて演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓ’に、前記被演算値Ｓ’として上書きする書込ステップと
を含むことを特徴とするべき乗剰余演算方法。
【請求項１７】
自然数である被演算値Ｓを保持している保持手段と、読出手段と、選出手段と、演算手段と、可逆演算手段と、書込手段とから成るべき乗剰余演算装置に適用されるプログラムであって、
単位ステップを繰り返す繰り返しステップを含み、
前記単位ステップは、
前記読出手段により、被演算値Ｓを読み出す読出ステップと、
前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数７】
0004638176.tif 000031
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、
前記演算手段により、有限体上のべき乗剰余演算
Ｓ’＝  Ｓ１／Ｐ  ｍｏｄ  Ｎ          （式１）
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出ステップにおいて選出された全素数の積）
を行う演算ステップと、 前記可逆演算手段により、前記演算ステップにおいて演算された演算結果値Ｓ’に可逆演算を施し、可逆演算結果値を得る可逆演算ステップと、
前記書込手段により、前記可逆演算ステップにおいて演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする書込ステップと
を含むことを特徴とするプログラム。
【請求項１８】
被演算値Ｔを保持するための保持手段と、自然数である被演算値Ｓを記憶している記憶手段と、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、有効素数選出手段と、演算手段と、読出手段と、枝取得手段と、素数選出手段と、生成手段と、第１書込手段と、第２書込手段と、演算制御手段とから成るべき乗剰余演算装置に適用されるプログラムであって、
前記有効素数選出手段により、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記いずれかのノードに接続するａ個の枝のうち、無効化されていない枝全てを含む組合せに対応する素数を選出する有効素数選出ステップと、
前記演算手段により、有限体上のべき乗剰余演算
Ｔ１／Ｐ  ｍｏｄ  Ｎ          （式２）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記有効素数選出ステップにおいて選出された素数である）  を行う演算ステップと、
ａ分木のルートから１のノードまでの経路上の各枝について、ルートから前記ノードへの順序で単位ステップを繰り返す繰り返しステップとを含み、
前記単位ステップは、
前記読出手段により、被演算値Ｓを読み出す読出ステップと、
前記枝取得手段により、ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得ステップと、
前記素数選出手段により、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選出ステップと、
前記生成手段により、有限体上のべき乗剰余演算
Ｓ’＝Ｓ１／Ｑ  ｍｏｄ  Ｎ          （式３）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記素数選出ステップにより選出された全素数の積である）
を行う生成ステップと、
前記第１書込手段により、前記生成ステップにおいて演算された演算結果値Ｓ’に可逆演算を施して、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込ステップとを含み、
さらに、前記第２書込手段により、前記繰り返しステップにより得られた結果値Ｓ’を、Ｔとして前記保持手段に書き込む第２書込ステップと、  前記演算制御手段により、前記有効素数選出ステップ、前記演算ステップを行わせるよう制御する演算制御ステップと
を含むことを特徴とするプログラム。
【請求項１９】
被演算数Ｓ’を保持するための保持手段と、自然数である被演算値Ｓを記憶している記憶手段と、ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、取得手段と、演算手段と、読出手段と、枝取得手段と、素数選択手段と、生成手段と、第１書込手段と、第２書込手段と、演算制御手段とから成るべき乗剰余演算装置に適用されるプログラムであって、
前記取得手段により、前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得ステップと、
前記演算手段により、有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ              （式４）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）  を行う演算ステップと、
ａ分木の１のリーフから１のノードまでの経路上の各枝について、前記リーフから前記ノードへの順序で単位ステップを繰り返す繰り返しステップとを含み、
前記単位ステップは、
前記読出手段により、被演算値Ｓを読み出す読出ステップと、
前記枝取得手段により、ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得ステップと、
前記素数選択手段により、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択ステップと、
前記生成手段により、
有限体上のべき乗剰余演算
Ｒ  ＝  ＳＰ  ｍｏｄ  Ｎ          （式５）
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記素数選択ステップにおいて選出された全素数の積）  を行う生成ステップと、
前記第１書込手段により、前記生成手段により演算された演算結果値Ｒに可逆演算を施して、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込ステップと
を含み、
さらに、前記第２書込手段により、前記繰り返しステップにより得られた結果値Ｒを、Ｓ’として前記保持手段に書き込む第２書込ステップと、  前記演算制御手段により、前記取得ステップ、前記演算ステップを行わせるよう制御する演算制御ステップと
を含むことを特徴とするプログラム。
【請求項２０】
請求項１７に記載のプログラムによる演算結果Ｓ’に対し演算を行う、前記Ｓ’を保持する保持手段と、選出手段と、演算手段と、可逆演算手段と、書込手段とから成るべき乗剰余演算装置に適用されるプログラムであって、  単位ステップを繰り返す繰り返しステップを含み、
前記単位ステップは、
前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【数８】
0004638176.tif 000032
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、
前記演算手段により、有限体上のべき乗剰余演算
（Ｓ’）Ｑ  ｍｏｄ  Ｎ
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出ステップにおいて選出された全素数の積）  を行う演算ステップと、
前記可逆演算手段により、前記演算ステップにおいて演算された演算結果値に可逆演算を施し、可逆演算結果値を得る可逆演算ステップと、
前記書込手段により、前記可逆演算ステップにおいて演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓ’に、前記被演算値Ｓ’として上書きする書込ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映画や音楽等、著作権を保護すべきコンテンツを光ディスク等の大容量記録媒体に記録し、再生するシステムに関し、特に著作権の保護が行われない不正な装置によるコンテンツの正常な再生を防止する技術に関する。
【背景技術】
【０００２】
近年、コンピュータによる動画処理速度の向上、光ディスク等記録媒体の大容量化、通信回線の速度向上などマルチメディア関連技術の発展に伴い、動画、音声等の、データサイズの大きいデジタルコンテンツ（以下、コンテンツという。）を、大容量記録媒体、ネットワーク、放送等を介して配信するビジネスが盛んに行われており、このようなビジネスにおいては、コンテンツの著作権保護が大変重要である。
【０００３】
著作権を保護し、かつコンテンツを配信するシステムにおいては、暗号化技術がよく使用されており、配信装置はコンテンツを暗号化して配信し、再生装置は、予め配布された復号鍵を用いて、前記暗号化されたコンテンツの復号を行っている。
前記システムでは、暗号化技術に加え、不正者による再生装置内部の解析等により前記鍵が外部に暴露される場合に備え、一旦暴露された鍵で、以後提供するコンテンツを復号できなくするための鍵無効化技術も使用されている（特許文献１参照）。
【０００４】
特許文献１に記載のシステムは、各再生装置を、木構造と呼ばれるＮ階層（Ｎは、２以上の自然数）構造を利用して管理するものであり、再生装置が、自装置に対応する当該木構造の末端から、最上端への経路上の各ノードに配置されたＮ個のデバイス鍵を保持しており、保持している前記デバイス鍵のうち、記録媒体中の情報で特定されるデバイス鍵を用いて、対応する暗号文を復号してメディア鍵を得て、暗号化コンテンツを復号し、コンテンツを再生する。前記暗号文は、有効なデバイス鍵の個数分、記録媒体中に記憶されている。
【特許文献１】特開２００２−２８１０１３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の鍵無効化技術では、各装置が保有する鍵の数は、木構造と呼ばれる階層構造の階層数（以下、高さという。）に比例し、前記木構造の階層の高さは、当該著作権保護システムがサポートする装置の総数の対数に比例するため、当該システムに属する装置の総数が多くなるに従い各装置が保有する鍵数が増加し、鍵の保有に必要なメモリ容量が増加し、結果、装置の製造コストが上昇するという問題がある。
【０００６】
そこで本発明はかかる問題に鑑みてなされたものであり、システムに属する装置の総数に関わらず、製造コストを抑制することができる著作権保護システムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明は、配布システムと、再生装置とから成る著作権保護システムであって、前記配布システムは、自然数である被演算値Ｓを保持している被演算値保持手段と、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【０００８】
0004638176.tif 000002
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出手段と、有限体上のべき乗剰余演算
【０００９】
0004638176.tif 000003
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出手段により選出された全素数の積）
を行う第１演算手段と、前記被演算値Ｓを用いてコンテンツの暗号化を行う暗号化手段と、前記選出した素数を示す指示情報と、暗号化された前記コンテンツとを配布する配布手段とを備え、前記再生装置は、１以上の素数を示す指示情報と、前記暗号化されたコンテンツを取得する取得手段と、前記Ｓ'を予め保持する結果保持手段と、有限体上のべき乗剰余演算
【００１０】
0004638176.tif 000004
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記取得した指示情報により示された全素数の積）
を行う第２演算手段と、前記第２演算手段による演算結果を用いて、取得した前記暗号化コンテンツを復号する復号手段とを備える。
【発明の効果】
【００１１】
本発明の著作権保護システムは、上述の構成を備えることにより、配布システムによるべき乗剰余演算結果を第１の鍵として、再生装置に対し１つ配布しておき、再生装置において、第１の鍵から第２の鍵を得て、第２の鍵を用いて、情報の復号を行うシステムを提供することができる。
なお、前記第１の鍵に関し、再生装置が当該第１の鍵に対し、配布システムによるべき乗剰余演算に用いられた複数の素数のうち１の素数を除いた全ての素数で、更にべき乗剰余演算を行うことにより第２の鍵を得ることとすると、再生装置が、前記１の素数の逆元でべき乗剰余演算されていない、べき乗剰余演算結果である第３の鍵から前記第２の鍵を得ることは、計算量的に困難であり、前記１の素数としていずれの素数を選択するかによって、第１の鍵から、暗号及び復号用の鍵である第２の鍵を生成できるか否かが変わることとなる。
【００１２】
本発明のべき乗剰余演算装置は、自然数である被演算値Ｓを保持している保持手段と、被演算値Ｓを読み出す読出手段と、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【００１３】
0004638176.tif 000005
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出手段と、有限体上のべき乗剰余演算
【００１４】
0004638176.tif 000006
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出手段により選出された全素数の積）
を行う演算手段とを備える。
この構成によれば、選出手段が選出する素数により異なる、べき乗剰余演算結果を得ることができる。
【００１５】
特に、前記べき乗剰余演算装置は、前記べき乗剰余演算結果を第１の鍵とし、当該第１の鍵から第２の鍵を生成するシステムに対し有効であり、１の前記べき乗剰余演算結果を第１の鍵とし、当該第１の鍵に対し、前記べき乗剰余演算に用いた複数の素数のうち１の素数を除いた全ての素数で、更にべき乗剰余演算を行い、保持手段に保持する被演算数に前記１の素数の逆元でべき乗剰余演算した数である第２の鍵を得ることができるが、前記１の素数の逆元でべき乗剰余演算されていないべき乗剰余演算結果からは、前記第２の鍵を得ることは、計算量的に困難であることから、第２の鍵を暗号、復号に用いれば、前記１の素数としていずれを選択するかにより、１のべき乗剰余演算結果から、前記第２の鍵を生成できるか否かを制御することができる。
【００１６】
また、前記べき乗剰余演算装置は、前記選出手段は、ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択手段とを備えてもよい。
【００１７】
この構成によれば、ａ分木の１のノードに接続する枝のうち、１の枝を含む全ての組合せに対応した各素数を選出し、選出した素数の逆元でべき乗剰余演算した演算結果を得ることができる。
また、前記べき乗剰余演算装置は、更に、前記演算手段により演算された演算結果値Ｓ'を前記被演算値Ｓとして、前記保持手段に保持している前記被演算値Ｓに上書きする書込手段と、ａ分木のルートから１のリーフまでの経路上の各枝について、ルートからリーフへの順序で、前記枝取得手段、前記素数選択手段、前記演算手段、前記書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式１に基づくべき乗剰余演算と、演算された演算結果値Ｓ'の前記保持手段への書込みとを繰り返すように制御する繰返制御手段とを備えてもよい。
【００１８】
この構成によれば、各リーフについて、ルートからリーフに至る経路に対応する一意な演算結果を得ることができる。
前記べき乗剰余演算装置は、更に、前記演算手段により演算された演算結果値Ｓ'に可逆演算を施し、可逆演算結果値を得る可逆演算手段と、前記可逆演算手段により演算された可逆演算結果値を、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする書込手段と、ａ分木のルートから１のリーフまでの経路上の各枝について、ルートからリーフへの順序で、前記枝取得手段、前記素数選択手段、前記演算手段、前記可逆演算手段、前記書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式１に基づくべき乗剰余演算と、演算結果値Ｓ'への可逆演算と、得られた可逆演算結果値の前記保持手段への書込みとを繰り返すように制御する繰返制御手段とを備えてもよい。
【００１９】
この構成によれば、定数に可逆演算を行うことにより、ａ分木における階層毎に演算を区切った演算結果を得ることができる。
前記べき乗剰余演算装置は、前記可逆演算手段が、前記演算手段により演算された演算結果値Ｓ'に定数を加算して、可逆演算結果値を得てもよい。
この構成によれば、定数を加算することにより、ａ分木における階層毎に演算を区切った演算結果を得ることができる。
【００２０】
本発明のべき乗剰余演算装置は、自然数である被演算値Ｔを保持している保持手段と、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記いずれかのノードに接続するａ個の枝のうち、無効化されていない枝全てを含む組合せに対応する素数を選出する有効素数選出手段と、
有限体上のべき乗剰余演算
【００２１】
0004638176.tif 000007
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記有効素数選出手段により選出された素数である）
を行う演算手段とを備える。
この構成によれば、ａ分木のいずれかのノードに接続する有効な全枝に対応づけられた素数の逆元に係る演算結果を得ることができる。
【００２２】
また、前記べき乗剰余演算装置は、更に、自然数である被演算値Ｓを記憶している記憶手段と、被演算値Ｓを読み出す読出手段と、ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選出手段と、有限体上のべき乗剰余演算
【００２３】
0004638176.tif 000008
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出手段により選出された全素数の積である）
を行う生成手段と、前記生成手段により演算された演算結果値Ｓ'を、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込手段と、ａ分木のルートから１のノードまでの経路上の各枝について、ルートから前記ノードへの順序で、前記枝取得手段、前記素数選出手段、前記生成手段、前記第１書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式３に基づくべき乗剰余演算と、演算された演算結果値Ｓ'の前記記憶手段への書込みとを繰り返すように制御する繰返制御手段と、前記繰返制御手段による繰り返し制御の終了後、前記演算結果値Ｓ'を、Ｔとして保持手段に書き込む第２書込手段と、
前記有効素数選出手段、前記演算手段に対して、それぞれ、無効化されていない枝全てを含む組合せに対応する素数の選出と、式２に基づくべき乗剰余演算とを行わせるよう制御する演算制御手段とを備えてもよい。
【００２４】
この構成によれば、ａ分木のルートからリーフに至る経路に対応する各リーフ毎に一意な演算結果を得ることができる。
本発明の演算装置は、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、１のノードに接続するａ個の枝のうち（ａ−１）個以下の無効化された枝を選出する無効枝選出手段と、前記ノードに接続するａ個の前記枝から、無効化されていない１の枝を選出する有効枝選出手段と、前記素数記憶手段が記憶する素数のうち、選択した前記無効化されていない枝と、前記無効化された枝の少なくとも１つとを含む全組合せのそれぞれに対応する素数を示す指示情報を再生装置へと配布する指示情報配布手段とを備える。
【００２５】
この構成によれば、有効な枝に対応する再生装置のみ、コンテンツを復号させるための鍵無効化情報を生成し、配布することができる。
また、前記演算装置は、前記指示情報配布手段が前記指示情報を通信により配布する通信手段を備えてもよい。
この構成によれば、再生装置に対し、有効な枝に対応する再生装置のみコンテンツを復号させるための鍵無効化情報を、通信を介して配布することができる。
【００２６】
前記演算装置は、前記指示情報配布手段が、前記指示情報を記録媒体に書き込む媒体書込手段を備えてもよい。
この構成によれば、再生装置に対し、有効な枝に対応する再生装置のみコンテンツを復号させるための鍵無効化情報を、記録媒体を介して配布することができる。
本発明のべき乗剰余演算装置は、自然数である被演算数Ｓ'を保持している保持手段と、ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得手段と、有限体上のべき乗剰余演算
【００２７】
0004638176.tif 000009
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）
を行う演算手段とを備える。
この構成によれば、指定された１個以上の素数の積の逆元を用いたべき乗剰余演算結果を得ることができる。
【００２８】
特に、前記べき乗剰余演算装置は、前記べき乗剰余演算結果を第１の鍵とし、当該第１の鍵から第２の鍵を生成するシステムに対し有効であり、予め保持する当該第１の鍵に対し、所定の素数のうち指定された素数を除いた素数を用いべき乗剰余演算を行い、第２の鍵を得ることができるが、予め保持する第１の鍵が、前記１の素数の逆元でべき乗剰余演算されたものでない場合、前記第２の鍵を得ることは、計算量的に困難であり、前記第１の鍵の内容と、前記指定する素数とに応じて、前記第２の鍵を生成できるか否かを制御することができる。
【００２９】
また、前記べき乗剰余演算装置は、更に、
自然数である被演算値Ｓを記憶している記憶手段と、被演算値Ｓを読み出す読出手段と、ａ個の前記枝のうち、１の枝を指定する枝指定情報を取得する枝取得手段と、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記枝指定情報により指定される枝を含む組合せに対応する素数を全て選出する素数選択手段と、有限体上のべき乗剰余演算
【００３０】
0004638176.tif 000010
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出手段により選出された全素数の積）
を行う生成手段と、前記生成手段により演算された演算結果値Ｒを、前記保持手段に保持している前記被演算値Ｓに、前記被演算値Ｓとして上書きする第１書込手段と、ａ分木の１のリーフから１のノードまでの経路上の各枝について、前記リーフから前記ノードへの順序で、前記枝取得手段、前記素数選出手段、前記生成手段、前記第１書込手段に対して、それぞれ、当該枝を指定する枝指定情報の取得と、指定された枝を含む組合せに対応する全ての素数の選択と、式５に基づくべき乗剰余演算と、演算された演算結果値Ｒの前記記憶手段への書込みとを繰り返すように制御する繰返制御手段と、前記繰返制御手段による繰り返し制御の終了後、前記演算結果値Ｒを、Ｓ'として保持手段に書き込む第２書込手段と、前記取得手段、前記演算手段に対して、それぞれ、前記指定情報の取得と、式４に基づくべき乗剰余演算とを行わせるよう制御する演算制御手段とを備えてもよい。
【００３１】
この構成によれば、ａ分木の階層に応じたべき乗剰余演算を行うべき乗剰余演算装置を実現できる。
本発明のべき乗剰余演算装置は、前記べき乗剰余演算装置による演算結果Ｓ'に対し、演算を行う演算装置であって、前記Ｓ'を保持する保持手段と、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【００３２】
0004638176.tif 000011
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出手段と、有限体上のべき乗剰余演算
【００３３】
0004638176.tif 000012
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出手段により選出された全素数の積）
を行う演算手段とを備えることを特徴とする。
この構成によれば、元になる数に対し素数の逆元によるべき乗剰余演算によって生成された被演算数から、前記元になる数を生成することができる。
本発明の記録媒体は、前記演算装置により配布された前記指示情報を記録する。
【００３４】
この構成によれば、記録した情報により、再生装置を無効化できる。
本発明の鍵管理装置は、再生装置においてコンテンツの復号に用いられる鍵を管理する鍵管理装置であって、前記べき乗剰余演算装置を含む。
この構成によれば、コンテンツの復号に用いられるデバイス鍵を生成する、べき乗剰余演算装置を含む鍵管理装置を実現できる。
【００３５】
本発明の鍵管理装置は、再生装置においてコンテンツの復号に用いられる鍵を管理する鍵管理装置であって、前記べき乗剰余演算装置を含むことを特徴とする。
この構成によれば、復号鍵を生成する、べき乗剰余演算装置を含む鍵管理装置を実現できる。
本発明の鍵管理装置は、再生装置においてコンテンツの復号に用いられる鍵を管理する鍵管理装置であって、前記べき乗剰余演算装置を含む。
【００３６】
この構成によれば、鍵無効化データを生成する、べき乗剰余演算装置を含む鍵管理装置を実現できる。
本発明の再生装置は、コンテンツを復号再生する再生装置であって、前記べき乗剰余演算装置を含む。
この構成によれば、デバイス鍵から復号鍵を生成する、べき乗剰余演算装置を含み、当該復号鍵を用いて暗号化されたコンテンツを復号する再生装置を構成できる。
【００３７】
本発明の記録装置は、コンテンツを記録する記録装置であって、前記のべき乗剰余演算装置を含む。
この構成によれば、デバイス鍵から復号鍵を生成するべき乗剰余演算装置を含み、当該復号鍵によりコンテンツを暗号化する記録装置を実現できる。
本発明のべき乗剰余演算方法は、自然数である被演算値Ｓを保持している保持手段と、読出手段と、選出手段と、演算手段とから成るべき乗剰余演算装置による、べき乗剰余演算方法であって、前記読出手段により、被演算値Ｓを読み出す読出ステップと、前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【００３８】
0004638176.tif 000013
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、前記演算手段により、有限体上のべき乗剰余演算
【００３９】
0004638176.tif 000014
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出手段により選出された全素数の積）
を行う演算ステップとを含む。
この構成によれば、選出手段が選出する素数により異なる、べき乗剰余演算結果を得ることができる。
【００４０】
特に、前記べき乗剰余演算装置は、前記べき乗剰余演算結果を第１の鍵とし、当該第１の鍵から第２の鍵を生成するシステムに対し有効であり、１の前記べき乗剰余演算結果を第１の鍵とし、当該第１の鍵に対し、前記べき乗剰余演算に用いた複数の素数のうち１の素数を除いた全ての素数で、更にべき乗剰余演算を行い、保持手段に保持する被演算数に前記１の素数の逆元でべき乗剰余演算した数である第２の鍵を得ることができるが、前記１の素数の逆元でべき乗剰余演算されていないべき乗剰余演算結果からは、前記第２の鍵を得ることは、計算量的に困難であることから、第２の鍵を暗号、復号に用いれば、前記１の素数としていずれを選択するかにより、１のべき乗剰余演算結果から、前記第２の鍵を生成できるか否かを制御することができる。
本発明のべき乗剰余演算方法は、自然数である被演算値Ｔを保持している保持手段と、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、有効素数選出手段と、演算手段とから成るべき乗剰余演算装置による、べき乗剰余演算方法であって、
前記有効素数選出手段により、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記いずれかのノードに接続するａ個の枝のうち、無効化されていない枝全てを含む組合せに対応する素数を選出する有効素数選出ステップと、
前記演算手段により、有限体上のべき乗剰余演算
【００４１】
0004638176.tif 000015
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記有効素数選出手段により選出された素数である）
を行う演算ステップとを含む。
この構成によれば、ａ分木のいずれかのノードに接続する有効な全枝に対応づけられた素数の逆元に係る演算結果を得ることができる。
【００４２】
本発明の演算方法は、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、無効枝選出手段と、有効枝選出手段と、指示情報配布手段とから成る演算装置による、演算方法であって、前記無効枝選出手段により、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、１のノードに接続するａ個の枝のうち（ａ−１）個以下の無効化された枝を選出する無効枝選出ステップと、前記有効枝選出手段により、前記ノードに接続するａ個の前記枝から、無効化されていない１の枝を選出する有効枝選出ステップと、前記指示情報配布手段により、前記素数記憶手段が記憶する素数のうち、選択した前記無効化されていない枝と、前記無効化された枝の少なくとも１つとを含む全組合せのそれぞれに対応する素数を示す指示情報を再生装置へと配布する指示情報配布ステップとを含む。
【００４３】
この構成によれば、有効な枝に対応する再生装置のみ、コンテンツを復号させるための鍵無効化情報を生成し、配布することができる。
本発明のべき乗剰余演算方法は、自然数である被演算数Ｓ'を保持している保持手段と、ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、取得手段と、演算手段とから成るべき乗剰余演算装置による、べき乗剰余演算方法であって、前記取得手段により、前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得ステップと、前記演算手段により、有限体上のべき乗剰余演算
【００４４】
0004638176.tif 000016
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）
を行う演算ステップとを含む。
この構成によれば、指定された１個以上の素数の積の逆元を用いたべき乗剰余演算結果を得ることができる。
本発明のべき乗剰余演算方法は、請求項２に記載のべき乗剰余演算装置による演算結果Ｓ'に対し演算を行う、前記Ｓ'を保持する保持手段と、選出手段と、演算手段とから成るべき乗剰余演算装置によるべき乗剰余演算方法であって、前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【００４５】
0004638176.tif 000017
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、前記演算手段により、有限体上のべき乗剰余演算
【００４６】
0004638176.tif 000018
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出手段により選出された全素数の積）
を行う演算ステップとを含む。
この構成によれば、元になる数に対し素数の逆元によるべき乗剰余演算によって生成された被演算数から、前記元になる数を生成することができる。
本発明のプログラムは、自然数である被演算値Ｓを保持している保持手段と、読出手段と、選出手段と、演算手段とから成るべき乗剰余演算装置に適用されるプログラムであって、前記読出手段により、被演算値Ｓを読み出す読出ステップと、
前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
【００４７】
0004638176.tif 000019
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、前記演算手段により、有限体上のべき乗剰余演算
【００４８】
0004638176.tif 000020
（Ｎは素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記選出手段により選出された全素数の積）
を行う演算ステップとの各ステップをコンピュータに実行させる。
この構成によれば、選出手段が選出する素数により異なる、べき乗剰余演算結果を得ることができる。
【００４９】
特に、前記べき乗剰余演算装置は、前記べき乗剰余演算結果を第１の鍵とし、当該第１の鍵から第２の鍵を生成するシステムに対し有効であり、１の前記べき乗剰余演算結果を第１の鍵とし、当該第１の鍵に対し、前記べき乗剰余演算に用いた複数の素数のうち１の素数を除いた全ての素数で、更にべき乗剰余演算を行い、保持手段に保持する被演算数に前記１の素数の逆元でべき乗剰余演算した数である第２の鍵を得ることができるが、前記１の素数の逆元でべき乗剰余演算されていないべき乗剰余演算結果からは、前記第２の鍵を得ることは、計算量的に困難であることから、第２の鍵を暗号、復号に用いれば、前記１の素数としていずれを選択するかにより、１のべき乗剰余演算結果から、前記第２の鍵を生成できるか否かを制御することができる。
本発明のプログラムは、自然数である被演算値Ｔを保持している保持手段と、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、有効素数選出手段と、演算手段とから成るべき乗剰余演算装置に適用されるプログラムであって、前記有効素数選出手段により、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、前記素数記憶手段に記憶されている（２a−２）個の前記素数から、前記いずれかのノードに接続するａ個の枝のうち、無効化されていない枝全てを含む組合せに対応する素数を選出する有効素数選出ステップと、前記演算手段により、有限体上のべき乗剰余演算
【００５０】
0004638176.tif 000021
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｐは、前記有効素数選出手段により選出された素数である）
を行う演算ステップとの各ステップをコンピュータに実行させる。
この構成によれば、ａ分木のいずれかのノードに接続する有効な全枝に対応づけられた素数の逆元に係る演算結果を得ることができる。
本発明のプログラムは、ａ分木（ａは２以上の自然数）のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の素数を記憶している素数記憶手段と、無効枝選出手段と、有効枝選出手段と、指示情報配布手段とから成る演算装置に適用されるプログラムであって、前記無効枝選出手段により、ａ分木のルートからいずれかのリーフへの経路上の全枝は無効化されており、１のノードに接続するａ個の枝のうち（ａ−１）個以下の無効化された枝を選出する無効枝選出ステップと、
前記有効枝選出手段により、前記ノードに接続するａ個の前記枝から、無効化されていない１の枝を選出する有効枝選出ステップと、前記指示情報配布手段により、前記素数記憶手段が記憶する素数のうち、選択した前記無効化されていない枝と、前記無効化された枝の少なくとも１つとを含む全組合せのそれぞれに対応する素数を示す指示情報を再生装置へと配布する指示情報配布ステップとの各ステップをコンピュータに実行させる。
【００５１】
この構成によれば、有効な枝に対応する再生装置のみ、コンテンツを復号させるための鍵無効化情報を生成し、配布することができる。
本発明のプログラムは、自然数である被演算数Ｓ'を保持している保持手段と、ａ分木のいずれかのノードに接続するａ個の枝から、１以上（ａ−１）以下の全ての数のそれぞれについて、当該数の枝を選択する組合せが生成され、生成された全組合せのいずれかに重複することなく対応する（２a−２）個の前記素数を記憶している素数記憶手段と、取得手段と、演算手段とから成るべき乗剰余演算装置に適用されるプログラムであって、前記取得手段により、前記素数記憶手段が記憶している素数のうち、１個以上の素数を指定する指定情報を取得する取得ステップと、前記演算手段により、有限体上のべき乗剰余演算
【００５２】
0004638176.tif 000022
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記指定情報により指定された素数全ての積）
を行う演算ステップとの各ステップをコンピュータに実行させる。
この構成によれば、指定された１個以上の素数の積の逆元を用いたべき乗剰余演算結果を得ることができる。
本発明のプログラムは、前記べき乗剰余演算装置による演算結果Ｓ'に対し演算を行う、前記Ｓ'を保持する保持手段と、選出手段と、演算手段とから成るべき乗剰余演算装置に適用されるプログラムであって、前記選出手段により、（２a−２）個（ａは２以上の自然数）の相異なる素数から、
0004638176.tif 000023
【００５３】
（ｍは変数であり、１から（ａ−１）までの自然数をとる）
で示される個数の素数を選出する選出ステップと、前記演算手段により、有限体上のべき乗剰余演算
【００５４】
0004638176.tif 000024
（Ｎは、素数ｐ及び素数ｑの積であり、素数ｐ、素数ｑはそれぞれ所定値より大きく、Ｑは、前記選出手段により選出された全素数の積）
を行う演算ステップとの各ステップをコンピュータに実行させる。
この構成によれば、元になる数に対し素数の逆元によるべき乗剰余演算によって生成された被演算数から、前記元になる数を生成することができる。
【発明を実施するための最良の形態】
【００５５】
以下、図面を使って、本発明の実施の形態を説明する。
本発明の著作権保護システムは、鍵が暴露されるなどしてコンテンツの著作権の保護が不可能となった不正な再生装置によって著作権を保護すべきコンテンツが正常に再生されるのを防ぐことにより前記コンテンツの著作権を保護するシステムである。
まず、本発明の一実施形態である著作権保護システムの構成の概略について述べる。
【００５６】
図１は、前記著作権保護システムの構成の概略を示す図である。
前記著作権保護システムは、図１に示すように、鍵管理装置１００、記録装置１１０、記録媒体１２０、再生装置１３０、１３０ａ、・・・、１３０ｂから成る。
鍵管理装置１００は、再生装置１３０、１３０ａ、・・・１３０ｂ等を販売、管理する会社により運用され、ネットワークに接続しているサーバであり、再生装置毎に一意なデバイス鍵を生成し、対応する再生装置に送信すると共に、生成した全デバイス鍵を記録装置１１０にも送信する。
【００５７】
前記会社は、コンテンツを記録するための記録媒体１２０の製造も行っており、
鍵管理装置１００は、前記各再生装置の中で、デバイス鍵が暴露されるなど、著作権保護が不可能となった特定の再生装置が、著作権保護のため暗号化したコンテンツを復号するのを妨げるためのデータである鍵無効化データを記録媒体１２０に記録する。前記鍵無効化データが書き込まれた記録媒体１２０に、暗号化コンテンツを記録した場合、前記特定の再生装置では、前記暗号化コンテンツの復号が不可能となる。
【００５８】
記録装置１１０は、著作権を保護すべきコンテンツを暗号化し、鍵管理装置１００により前記鍵無効化データ等の各種情報が書き込まれた記録媒体１２０に記録する。
再生装置１３０、１３０ａ、１３０ｂ・・・は、記録媒体１２０が挿入されると、記録媒体１２０に記録された情報と、保持しているデバイス鍵とを用いて所定の処理を行い、当該処理の結果、前記コンテンツを復号するための鍵の復号に成功した場合に、当該獲得した鍵を用いてコンテンツを復号して、再生する。
【００５９】
本実施形態においては、記録装置と、再生装置とを別構成としているが、記録装置の記録機能と再生装置の再生機能とを合わせて、コンテンツの記録及び再生が可能な記録再生装置を構成してもよい。
前記著作権保護システムにおける情報の暗号化、復号には、デバイス鍵、暗号鍵（及び当該暗号鍵と同一の復号鍵）、メディア鍵、コンテンツ鍵の４種類が用いられる。
【００６０】
デバイス鍵は、前述の通り、再生装置、記録装置毎に一意な鍵であり、鍵管理装置１００により生成され、各再生装置、記録装置に配布される。
復号鍵は、前述の通り、暗号鍵と同一であって、メディア鍵を暗号化し、暗号化メディア鍵を復号するための鍵であり、鍵管理装置１００が生成する。無効化されていない有効な再生装置及び記録装置は、前記鍵無効化データとデバイス鍵とを用い所定の処理を行うことにより、復号鍵を生成することができるようになっている。
【００６１】
メディア鍵は、コンテンツ鍵を暗号化及び復号するための鍵であり、鍵管理装置１００が保持しており、鍵管理装置１００により、復号鍵を用いて暗号化され、記録媒体１２０に記録される。
コンテンツ鍵は、コンテンツの暗号化及び復号に用いられる鍵であり、記録装置１１０が保持しており、記録装置１１０により、メディア鍵を用いて暗号化されて、記録媒体１２０に記録される。
【００６２】
次に、前記著作権保護システム全体の動作について述べる。
図２は、前記著作権保護システム全体の動作を示すフローチャートである。
図２のＳ１０１からＳ１０７は、鍵管理装置１００による処理であり、Ｓ１０８からＳ１１１は、記録装置１１０による処理であり、Ｓ１１２からＳ１１７は、再生装置１３０による処理である。
【００６３】
鍵管理装置１００は、素数表を生成する（Ｓ１０１）。
前記素数表には、鍵管理装置１００が、デバイス鍵の生成に用いるための素数が示される。
鍵管理装置１００は、前記素数表を用い、各再生装置に対応するデバイス鍵を生成し（Ｓ１０２）、対応する再生装置及び記録装置に対して配布する（Ｓ１０３）。
【００６４】
鍵管理装置１００は、復号鍵を生成し（Ｓ１０４）、更に、鍵無効化データを生成する（Ｓ１０５）。
鍵無効化データには、無効化されていない再生装置のみに復号鍵を生成させるための情報が含まれる。また、Ｓ１０４において生成される復号鍵の数は、無効化される再生装置の数に応じて変わる。
【００６５】
鍵管理装置１００は、Ｓ１０４で生成したそれぞれの復号鍵と同一の暗号鍵で、メディア鍵を暗号化し（Ｓ１０６）、暗号化メディア鍵を含めた鍵無効化データを記録媒体１２０に書き込む（Ｓ１０７）。
記録装置１１０は、鍵管理装置１００から取得したデバイス鍵と、記録媒体１２０に記録されている鍵無効化データを用いて、復号鍵を生成する（Ｓ１０８）。
【００６６】
記録装置１１０は、鍵無効化データから暗号化メディア鍵を抜き出し、Ｓ１０８において生成した復号鍵で復号し、メディア鍵を得る（Ｓ１０９）。
記録装置１１０は、コンテンツと、コンテンツ鍵とを保持しており、当該コンテンツ鍵を用いてコンテンツを暗号化して記録媒体１２０に記録し（Ｓ１１０）、また、コンテンツ鍵をＳ１０９において生成したメディア鍵で暗号化し、記録媒体１２０に記録する（Ｓ１１１）。
【００６７】
再生装置１３０は、記録媒体１２０から読み出した鍵無効化データを用い、復号鍵の生成を試みる（Ｓ１１２）。再生装置１３０が無効化されていない装置であれば、前記復号鍵の生成に成功することとなる。
再生装置１３０は、復号鍵の生成に成功したか否かを判定し（Ｓ１１３）、復号鍵の生成に失敗した場合（Ｓ１１３＝Ｎｏ）には、処理を終了する。
復号鍵の生成に成功した場合（Ｓ１１３＝Ｙｅｓ）、生成した復号鍵で、記録媒体１２０に記録された暗号化メディア鍵を復号する（Ｓ１１４）。
【００６８】
Ｓ１１４で復号したメディア鍵を用い、記録媒体１２０に記録されている暗号化コンテンツ鍵を復号する（Ｓ１１５）。
再生装置１３０は、Ｓ１１５において生成したコンテンツ鍵を用い、記録媒体１２０に記録された暗号化コンテンツを復号し（Ｓ１１６）、コンテンツの再生を行う（Ｓ１１７）。
次に、前記著作権保護システムを構成する各装置について、詳細に述べる。
＜鍵管理装置１００＞
鍵管理装置１００は、再生装置、記録装置毎に一意なデバイス鍵を生成し、生成したデバイス鍵を、当該デバイス鍵に対応する再生装置及び記録装置へ配布し、また、鍵無効化データを生成して、記録媒体へ書き込む。
【００６９】
鍵管理装置１００は、再生装置１３０、１３０ａ、・・・、１３０ｂから成る再生装置群、記録装置を、木構造を利用して管理する。本実施形態では、鍵管理装置１００が管理する再生装置及び記録装置は合計で２７台あるものとし、前記木構造は３分木であるとする。
先ず、前記木構造について述べる。
【００７０】
図３は、２７台の装置を管理するための３分木の木構造を示す図である。
図３のＮ0〜Ｎ333はノードを示し、ノード間をつなぐ線（以下、パスという。）には、図に示すように、左から順に１、２、３と番号（以下、パス番号という。）が付与されている。
各ノードには、木構造において、ルートノードであるＮ0から当該ノードに到達するまでに経由するパスを表すノードＩＤが付されている。
【００７１】
図３のＮabcは、ノードＩＤが「ａｂｃ」であるノードを示しており、ルートノードであるＮ0からＮabcに到達するまでに、パス番号がａの経路、ｂの経路、ｃの経路の順に経由していることを示す。
また、前記木構造は、レイヤ０を最上位階層として、レイヤ０〜レイヤ３までの論理的な４つの階層に分けられている。ノードＩＤの桁数がＬであるノードはレイヤＬに属することとなる。
【００７２】
例えば、図３に示すように、Ｎ1はレイヤ１に属し、Ｎ11はレイヤ２に属する。Ｎ0は、ルートとなる特別なノードであり、レイヤ０に属する。
前記木構造の最下位階層であるレイヤ３に属するノード群Ｎ111〜Ｎ333には、ノードＩＤと同値の装置ＩＤを持ち、再生装置１３０、再生装置１３０ａ、・・・再生装置１３０ｂ、記録装置１１０に相当する装置が対応づけられている。
【００７３】
前記レイヤ３のノードに対応する２７台の装置を、図３に示すように、以下、装置１〜装置２７という。装置１〜装置２７には、デバイス鍵Ｋ１〜Ｋ２７を配布することとなる。例えば、鍵管理装置１００は、装置ＩＤが「１１２」である装置２に対しデバイス鍵としてＫ２を配布し、また、装置ＩＤが「３１２」である装置２０に対しデバイス鍵としてＫ２０を配布する。
【００７４】
次に、鍵管理装置１００の構成の詳細について述べる。
図４は、鍵管理装置１００の構成を示すブロック図である。
鍵管理装置１００は、図４に示すように、素数割当部２０１、乱数生成部２０２、鍵情報格納部２０３、デバイス鍵生成部２０４、無効化装置特定部２０５、鍵無効化データ生成部２０６、送信部２０７、書込部２０８とを備え、ハードウェアとしては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ハードディスク、キーボード、ネットワークアダプタ等を備えたコンピュータシステムであり、ＲＯＭ又は前記ハードディスクには、コンピュータプログラムが記憶され、前記ＣＰＵが、前記コンピュータプログラムに従って動作することにより、鍵管理装置１００は、その機能を実現する。
【００７５】
素数割当部２０１は、デバイス鍵の生成に必要な、ＲＳＡ暗号の法であるｎを算出するための素数ｐ、ｑを予め保持しており、鍵情報格納部２０３に保持させる。
前述のＲＳＡ暗号は、素数ｐ、ｑの積である合成数ｎを法として、素数である公開鍵と、前記公開鍵の逆元である復号鍵とを使用する暗号であり、素数ｐ、ｑを知らない場合、ある素数の逆元を算出するのは計算量的に困難であるという特徴を有する。
【００７６】
ここでｐ、ｑ、ｎは一例として、ｐ ＝ FFFFFFFF EA2DE66E D3B1B7E9 61B75DFC D9FAE2FF A07A2345 9B7956FB 1B9B16D7 E1B6D59B BDF45B85 3CBF08EA 3BC7A1BD 541CB3A8 80E02E43 87CA7DEF 50948E87、ｑ ＝ FFFFFFFF E275B7F4 98A3811D E906ACF7 BFEB5CD6 A445AF09 D7906DE1 97CC2CCD 87614718 8C7C084F CE9231CA B7CFA113 13C3DDCF F1B70A54 84494467 8FCEF193、ｎ ＝ ｐｑ ＝ FFFFFFFF CCA39E63 6ED9CF52 950C23A0 38AE0291 012B984A 964FFBBD 99E9DACB 91400431 0C5DD264 B1873126 44A725C5 D5BC73F4 97CFD100 89FD1342 656026BE 3FB583FE B134FF43 6957A1E1 D975B5BE DF1A9570 4C81A337 F06E5F9F 9388A7AC 5ABFD5CF 0356D91A 9861C69F E50509C2 323E5270 F2015FBD C08AA2C0 391CEE85とする。但し上記ｐ、ｑ、ｎは、１６進による表記である。
【００７７】
ＲＳＡ暗号については、「「暗号理論入門」、岡本栄司、共立出版株式会社」にその詳細が開示されているため、ここでの説明は省略する。
また、素数割当部２０１は、デバイス鍵の生成に必要なｍ個の素数を鍵情報格納部２０３に保持させる。
ｍは、木構造に依存し、木構造がａ分木の場合、ｍ＝２a−２個となり、例えば、図３の例では、木構造は３分木であるので、ｍ＝２3−２＝６である。
【００７８】
ｍは、パス番号「１」、「２」・・・「ａ」について、全てのパス番号を選択する場合を除き、選択し得るパス番号の組合せの数と一致する。つまり、
ｍ＝aＣ1＋aＣ2＋・・・＋aＣ(a-1)
である。
例えば、３分木の場合、３つのパス番号「１」、「２」、「３」について、全てのパス番号を選択する場合を除き、選択し得るパス番号の組合せは、（１）「１」のみ選択、（２）「２」のみ選択、（３）「３」のみ選択、（４）「１」と「２」とを選択、（５）「１」と「３」とを選択、（６）「２」と「３」とを選択、の６通りの組合せがある。
【００７９】
素数割当部２０１は、ｍ個以上の素数を予め保持しており、前記ｍ個の各組合せに対し、相異なる素数を割り当てる。各組合せに対応する素数を生成素数といい、以下、Ｐxのように記載する。Ｐxの記載におけるｘは、選択したパス番号を連結したものであり、ｘを選択パス番号という。
例えば、上記の「（１）「１」のみ選択」に対応する選択パス番号は「１」であり、対応する素数はＰ1であり、また、上記「（４）「１」と「２」とを選択」に対応する選択パス番号は「１２」であり、対応する素数は、Ｐ12である。
【００８０】
次に、素数割当部２０１が行う素数表の生成について述べる。
図５は、素数割当部２０１が生成して保持する素数表であり、図５（ａ）は、木構造が３分木である場合に対応し、図５（ｂ）は、木構造が４分木である場合に対応する。図５（ａ）（ｂ）において、素数表の各行は、選択パス番号と、生成素数との組から成る。
例えば、図５（ａ）において、素数表の４行目は、上記（４）のパス番号「１」と「２」との組合せに対応しており、選択パス番号は１２であり、生成素数は、Ｐ12であることを示す。
【００８１】
図６は、ａ分木について、素数割当部２０１が、素数表を生成するための処理を示すフローチャートであり、図２におけるＳ１０１に相当する。
素数割当部２０１は、演算に用いる変数ｋ、ｌを初期化する（Ｓ２０１）。
ｋには初期値１を代入し、ｌには、初期値ｋ−１を代入する。
素数割当部２０１は、演算に用いるパス番号の格納領域Ｐ（０）〜Ｐ（ａ−１）を、Ｐ（ｘ）＝（ｘ＋１）（但し、０≦ｘ≦（ｋ−１））となるよう初期化する（Ｓ２０２）。
【００８２】
例えば、Ｐ（０）＝１、Ｐ（１）＝２・・・Ｐ（ｋ−１）＝ｋとなる。
また、素数割当部２０１は、素数表における書き込み先のポインタを、素数表の１行目を指すよう初期化する（Ｓ２０３）。
Ｐ（０）〜Ｐ（ｋ−１）を連結した数を、ポインタが指す書込先の「選択パス番号」に書き込む（Ｓ２０４）。
【００８３】
素数を生成し、ポインタが指す書込先の「生成素数」に書き込む（Ｓ２０５）。
Ｐ（ｋ−１）＋１がａより大きいか否かを判定する（Ｓ２０６）。
小さい又は等しいと判定した場合（Ｓ２０６＝Ｎｏ）、Ｐ（ｋ−１）をインクリメントする（Ｓ２０７）。
次の領域を示すようポインタを更新する（Ｓ２０８）。
【００８４】
大きいと判定した場合（Ｓ２０６＝Ｙｅｓ）、ｌ−１が０以上であるか否か判定する（Ｓ２０９）。
０以上であると判定した場合（Ｓ２０９＝Ｙｅｓ）、Ｐ（ｌ−ｋ）＋ｋがａより大きいか否かを判定する（Ｓ２１０）。
小さい又は等しいと判定した場合（Ｓ２１０＝Ｎｏ）、ｌをデクリメントする（Ｓ２１１）。
【００８５】
Ｐ（ｌ）に保持している数値をインクリメントした後、Ｐ（ｌ＋ｘ）＝Ｐ（ｌ）＋ｘ（但し１≦ｘ≦（ｋ−１−ｌ））で示す処理を行い、Ｓ２０８に進む（Ｓ２１２）。
ｌ−１が０未満であると判定した場合（Ｓ２０９＝Ｎｏ）或いはＳ２１０において小さいと判定した場合（Ｓ２１０＝Ｙｅｓ）、（ｋ＋１）が（ａ−１）より大きいか否かを判定する（Ｓ２１３）。
【００８６】
Ｓ２１３において（ｋ＋１）が（ａ−１）未満であると判定した場合（Ｓ２１３＝ＮＯ）、処理を終了する。
Ｓ２１３において大きいと判定した場合（Ｓ２１３＝ＹＥＳ）、ｋをインクリメントし、ｌに（ｋ−１）を代入する（Ｓ２１４）。
Ｐ（０）＝１、Ｐ（１）＝２、・・・Ｐ（ｋ−１）＝ｋとする（Ｓ２１５）。
【００８７】
以上、Ｓ２０１〜Ｓ２１５により、素数割当部２０１は、図５に示す素数表を生成し、保持することとなる。
乱数生成部２０２は、デバイス鍵の生成に必要な乱数（乱数Ｓ）を生成し、鍵情報格納部２０３に保持させる。
鍵情報格納部２０３は、素数割当部２０１が生成した素数、及び乱数生成部２０２が生成した乱数を保持する。
【００８８】
また、鍵情報格納部２０３は、記録媒体１２０を含む各記録媒体に固有のメディア鍵を予め保持しているものとする。
デバイス鍵生成部２０４は、鍵情報格納部２０３が保持する情報に基づき、前記装置１〜２７の各装置に対応するデバイス鍵を生成する。
図７は、デバイス鍵生成部２０４が、前記３分木である木構造に基づいてデバイス鍵を生成する処理を示すフローチャートであり、図２におけるＳ１０２に相当する。
【００８９】
図７において、「ＩＤ（Ｊ）」の記載は、デバイス鍵の発行先装置の装置ＩＤの下位桁からＪ番目のパス番号を示している。例えば、装置ＩＤが「３１２」である装置２０の場合、ＩＤ（１）＝２、ＩＤ（２）＝１、ＩＤ（３）＝３となる。
なお、以降に示す、べき乗演算は、記載が無くとも法ｎの下でのｍｏｄ  ｎ演算を行っているものとする。
【００９０】
デバイス鍵生成部２０４は、演算に用いる各変数の初期化を行う（Ｓ４０１）。
変数Ｘには、鍵情報格納部２０３が格納している前記乱数Ｓを代入し、変数Ｊには０を代入し、変数Ｌに装置ＩＤの桁数を代入する。
図３の木構造の例ではＬ＝３である。
ＩＤ（Ｊ）の値が１であるかどうかを判定する（Ｓ４０２）。１である場合はＳ４０４に進み、１でない場合はＳ４０３に進む。
【００９１】
ＩＤ（Ｊ）の値が２であるかどうかを判定する（Ｓ４０３）。２である場合はＳ４０５に進み、２でない場合はＳ４０６に進む。
なお、Ｓ４０２とＳ４０３の両ステップは、ＩＤ（Ｊ）が３分木に対応する１、２、３の各場合に実行するべき乗剰余演算を選択するためのステップであり、ａ分木の場合であれば、ＩＤ（Ｊ）が１、２・・・・、（ａ−１）、ａの各場合に実行するべき乗剰余演算を選択する必要があるので、Ｓ４０２（或いはＳ４０３）と同等な判断を行うステップが、（ａ−１）個必要となる。
【００９２】
変数Ｘに対して、素数Ｐ1、Ｐ12、Ｐ13の逆元をべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ４０４）。
Ｓ４０４における、べき乗剰余演算において逆元を使用する素数は、ＩＤ（Ｊ）＝１に対応する、前記素数表の選択パス番号に値「１」が含まれる全ての素数である。
３分木においては、図５（ａ）に記載の素数のうち、対応する選択パス番号に値「１」を含むＰ1、Ｐ12、Ｐ13が、Ｓ４０４の演算において、使用される。
【００９３】
４分木においては、図５（ｂ）の選択パス番号に値「１」を含む、Ｐ1、Ｐ12、Ｐ13、Ｐ14、Ｐ123、Ｐ124、Ｐ134が使用されることとなる。
また、素数Ｐxの逆元を、１／Ｐxと記載している。
変数Ｘに対して、素数Ｐ2、Ｐ12、Ｐ23の逆元をべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ４０５）。
【００９４】
Ｓ４０５における、べき乗剰余演算において逆元を使用する素数は、ＩＤ（Ｊ）＝２に対応する、前記素数表の選択パス番号に値「２」が含まれる全ての素数である。
変数Ｘに対して、素数Ｐ3、Ｐ13、Ｐ23の逆元をべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ４０６）。
Ｓ４０６における、べき乗剰余演算において逆元を使用する素数は、ＩＤ（Ｊ）＝３に対応する、前記素数表の選択パス番号に値「３」が含まれる全ての素数である。
【００９５】
なお、Ｓ４０４、Ｓ４０５、Ｓ４０６の各ステップは、ＩＤ（Ｊ）が３分木に対応する１、２、３の各場合に実行するべき乗剰余演算処理であり、ａ分木の場合であれば、ＩＤ（Ｊ）が１、２・・・・、（ａ−１）、ａの各場合に実行するべき乗剰余演算ステップが必要となる。つまり、Ｓ４０４（或いはＳ４０５、Ｓ４０６）と同等なべき乗剰余演算実行ステップが、ａ個必要となり、べき乗剰余演算において逆元を使用する素数は、ＩＤ（Ｊ）＝ｈ（ｈ：  １≦ｈ≦ａ）に対応する、前記素数表の選択パス番号に値「ｈ」が含まれる全ての素数である。
【００９６】
変数Ｊが、変数Ｌ−２より大きいかどうか判定する（Ｓ４０７）。大きい場合Ｓ４１０に進み、大きくない場合はＳ４０８に進む。
変数Ｘに対して、１を加算して、その結果を変数Ｘに代入する（Ｓ４０８）。
変数Ｊに対して、１を加算して、その結果を変数Ｊに代入する（Ｓ４０９）。
算出した変数Ｘの値をＫｉに代入して、デバイス鍵Ｋｉを装置ｉに発行する（Ｓ４１０）。
【００９７】
以上、図７のフローチャートで示す処理を、デバイス鍵の生成対象となる装置の数だけ繰り返す。
ここで、図７に示したフローチャートに従い、例えば、前記装置２０に対するデバイス鍵を計算する場合、まず、Ｓ４０６において、Ｓ＾｛１／（Ｐ3Ｐ13Ｐ23）｝を計算してから、Ｓ４０８において１を加算する。次に加算結果Ｘに対して、Ｓ４０４において、Ｘ＾｛１／（Ｐ1Ｐ12Ｐ13）｝を計算してから、再びＳ４０８において１を加算する。最後に加算結果Ｘに対して、Ｓ４０５において、Ｘ＾｛１／（Ｐ2Ｐ12Ｐ23）｝を計算する。
以上の処理により、装置２０に対して発行するデバイス鍵Ｋ２０は、
Ｋ２０ ＝ （（Ｓ^（１／（Ｐ3Ｐ13Ｐ23））＋１）^（１／（Ｐ1Ｐ12Ｐ13））＋１）^（１／(Ｐ2Ｐ12Ｐ23））
となる。
【００９８】
同様に、装置２に対して発行するデバイス鍵Ｋ２は、
Ｋ２ ＝ （（Ｓ^（１／(Ｐ1Ｐ12Ｐ13））＋１）^（１／（Ｐ1Ｐ12Ｐ13））＋１）^（１／（Ｐ2Ｐ12Ｐ23））
となる。
無効化装置特定部２０５は、鍵管理装置１００が備えるキーボード（図示せず）等を用いオペレータが入力するなどした無効化すべき装置を示す無効装置識別情報を保持する。
【００９９】
ここで、本実施形態においては、装置１〜装置２７の各装置に対し、Ｋ１〜Ｋ２７の各デバイス鍵が配布された後、装置１と装置２６とに対応するデバイス鍵Ｋ１とＫ２６とが暴露されてしまったものとし、鍵管理装置１００は、Ｋ１及びＫ２６を用いても、コンテンツの復号ができないよう鍵無効化データを生成する。
図８は、前記木構造において、装置１と装置２６を無効化する場合の暗号化鍵を出力するノードと暗号化鍵の値との関係を模式的に示す図である。
【０１００】
装置ｎを無効化する場合には、前記木構造における装置ｎに対応するノードからＮ0への経路上のノードに対する暗号鍵を生成することとなる。
例えば、図８において、装置１を無効化する場合には、装置１からＮ0への経路上のノード（Ｎ11、Ｎ1、Ｎ0）に対する暗号鍵を生成し、装置２６を無効化する場合には、装置２６からＮ0への経路上のノード（Ｎ33、Ｎ3、Ｎ0）に対する暗号鍵を生成することとなる。
【０１０１】
本実施形態において、装置１と装置２６を無効化するため生成する暗号鍵は、上述の装置１からＮ0への経路上のノードと装置２６からＮ0への経路上のノードのうち重複するノードを除くＮ0、Ｎ1、Ｎ2、Ｎ11，Ｎ22のそれぞれに対応するＫｅ１〜Ｋｅ５の５つとなる。以下、Ｎ11、Ｎ1、Ｎ0、Ｎ33、Ｎ3をそれぞれ無効化ノードという。
無効化装置特定部２０５は、前記オペレータによる入力等の結果、前記無効装置識別情報として、装置１の装置ＩＤである「１１１」と、装置２６の装置ＩＤである「３３２」という値を保持する。
【０１０２】
図９は、無効化装置特定部２０５が保持する、前記無効化装置識別情報と、前記木構造とに基づく無効表である。
前記無効表は、無効表の各行は、ノードＩＤと、無効フラグと、選択パス番号とから成る。ノードＩＤを示す列には、前記木構造中の最下位レイヤを除く全てのノードのノードＩＤが登録される。無効フラグは、ノードＩＤで示されるノードが無効であるか否かを示し、無効である場合には値「１」、有効である場合には値「０」を登録する。選択パス番号は、当該ノードに繋がるうち有効なパス番号の組合せを示し、選択パス番号の各桁は、それぞれが有効なパス番号を示している。
【０１０３】
鍵無効化データ生成部２０６は、鍵情報格納部２０３が格納している情報、及び前記無効表とから、記録媒体１２０に記録するための鍵無効化データのヘッダ部を生成する。
図１０は、鍵無効化データ生成部２０６における、鍵無効化データのヘッダ部を生成するための処理を示すフローチャートであり、図２におけるＳ１０５に相当する。
鍵無効化データは、１以上の鍵無効化エントリから成り、前記鍵無効化エントリは、ノードＩＤと、選択パス番号と、暗号化メディア鍵とから成り、前記鍵無効化エントリのうち、前記暗号化メディア鍵を除く、前記ノードＩＤと、前記選択パス番号とを合わせて、以下、鍵無効化データのヘッダ部という。
【０１０４】
鍵無効化データ生成部２０６による、鍵無効化データのヘッダ部生成処理について図１０を用い説明する。
鍵無効化データ生成部２０６は、生成する鍵無効化データを記憶するための記憶領域を持つ。
鍵無効化データ生成部２０６は、まず、演算に用いる変数Ｅを１で初期化する（Ｓ４５１）。
【０１０５】
演算に用いるポインタを、先頭の鍵無効化エントリ記憶領域に設定する（Ｓ４５２）。
前記無効表のＥ行目の内容（以下、エントリＥという。）を取得する（Ｓ４５３）。
例えば、図９の無効表において、Ｅ＝１の場合のエントリＥの、ノードＩＤは「０」、無効フラグは「１」、選択パス番号は「２」である。
Ｓ４５３で取得したエントリＥの無効フラグが、無効を示す「１」であるか否か判定する（Ｓ４５４）。
【０１０６】
無効を示す「１」でない場合（Ｓ４５４＝Ｎｏ）、Ｓ４５７に進む。
無効を示す「１」である場合（Ｓ４５４＝Ｙｅｓ）、ポインタが指す領域の無効化情報エントリ記憶領域にノードＩＤとして、前記エントリＥのノードＩＤを書き込み、選択パス番号として、前記エントリＥの選択パス番号を書き込む（Ｓ４５５）。
鍵無効化データ生成部２０６は、ポインタが次の無効化情報エントリ記憶領域を指すよう設定する（Ｓ４５６）。
【０１０７】
Ｅ＋１が無効表の行数より大きいか否か判定する（Ｓ４５７）。
大きい場合（Ｓ４５７＝Ｙｅｓ）は、処理を終了する。
小さいか等しい場合（Ｓ４５７＝Ｎｏ）、Ｅをインクリメントする（Ｓ４５８）。
図１１は、記録媒体に記録される鍵無効化データのデータ構造を示す。
図１１（ａ）は、無効化された装置がある場合の鍵無効化データであり、図１１（ｂ）は、無効化された装置が無い場合の鍵無効化データである。
【０１０８】
図１１の各列は、「ノードＩＤ」、「選択パス番号」、「暗号化メディア鍵」である。
Ｓ４５１〜Ｓ４５８により、鍵無効化データ生成部２０６は、図１１に示す鍵無効化データのうち「ノードＩＤ」、「選択パス番号」、「暗号化メディア鍵」から成るヘッダ部の部分を生成して書き込むこととなる。
「暗号化メディア鍵」は、復号鍵と同一の鍵である暗号鍵で暗号化されたメディア鍵であり、説明は、後述する。
【０１０９】
次に、鍵無効化データ生成部２０６による、暗号鍵の生成処理について述べる。
「暗号鍵」と「復号鍵」とは、同一の鍵を示しており、情報の暗号化及び復号の双方に使用される。
図１２〜図１４は、復号鍵と同一の鍵である前記暗号鍵を生成する際の動作を示すフローチャートであり、図２におけるＳ１０４に相当する。
【０１１０】
ここで、図１３における「ＮＩＤ（Ｊ）」の記載は、ノードＩＤの下位桁からＪ番目のパス番号を示している。例えば、ノードＩＤが３１の場合、ＮＩＤ（１）＝１、ＮＩＤ（２）＝３である。また、図中の「ルート」、「ルートノード」の記載は、Ｎ0を示している。
鍵無効化データ生成部２０６は、前記木構造において、無効化装置特定部２０５が特定した無効化すべき装置とＮ0を結ぶ経路上に存在するノードを全て無効化ノードと判定して、記憶する（Ｓ５０１）。
【０１１１】
鍵無効化データ生成部２０６は、鍵情報格納部２０３に格納する木構造のＮ0を起点として、上位レイヤから下位レイヤ、同一レイヤでは左のノードから右のノードの順で、リーフを除く各ノードを、処理ノードとして選出する（Ｓ５０２）。
Ｓ５０２において、処理ノードが選出できた場合は、全ノードの探索が未完了であると判定し、選出するノードが無かった場合は完了と判定する（Ｓ５０３）。未完了の場合はＳ５０４に進み、完了の場合はＳ５０７に進む。
【０１１２】
Ｓ５０２で選出した処理ノードが、無効化ノードで、かつ子ノードのうち少なくとも１つのノードが無効化ノードでないかどうかを判定する（Ｓ５０４）。当該ノードが無効化ノード、かつ無効化ノードでない子ノードが存在する場合はＳ５０６に進み、当該ノードは無効化ノードでない、あるいは子ノードが全て無効化ノードの場合はＳ５０５に進む。
ここで、子ノードとは、対象となるノードとパスにより繋がっている１階層下のノードであり、例えば、レイヤ１に属するＮ3の子ノードは、レイヤ２に属するＮ31、Ｎ32、Ｎ33である。
【０１１３】
前記処理ノードについては暗号化鍵を生成する必要がないため、Ｓ５０２と同様の方法で、次の処理ノードの選出を行う（Ｓ５０５）。
処理ノードがルート（Ｎ0）でないか否かを判定する（Ｓ５０６）。ルートである場合には、Ｓ６０１に進み、ルートでない場合はＳ７０２に進む。
発行済みの全ての暗号化鍵Ｋｅｉで、メディア鍵を個別に暗号化し、鍵無効化データを生成する（Ｓ５０７）。
【０１１４】
本実施形態において、装置１と装置２６を無効化する場合、生成された暗号化鍵Ｋｅ１〜Ｋｅ５は、図８に示す値となる。
鍵無効化データ生成部２０６は、計算に用いる各変数の初期化を行う。変数Ｘに鍵情報格納部２０３が格納する乱数Ｓを代入して、変数Ｊを０で初期化して、変数ＬをノードＩＤの桁数とする（Ｓ６０１）。図３の例ではＬ＝２である。
【０１１５】
処理ノードについて、ＮＩＤ（Ｊ）の値が１であるかどうかを判定する（Ｓ６０２）。１である場合はＳ６０４に進み、１でない場合はＳ６０３に進む。
処理ノードについて、ＮＩＤ（Ｊ）の値が２であるかどうかを判定する（Ｓ６０３）。２である場合はＳ６０５に進み、２でない場合はＳ６０６に進む。
なお、Ｓ６０２とＳ６０３の両ステップは、ＮＩＤ（Ｊ）が３分木に対応する１、２、３の各場合に実行するべき乗剰余演算を選択するためのステップであり、ａ分木の場合であれば、ＮＩＤ（Ｊ）が１、２・・・・、（ａ−１）、ａの各場合に実行するべき乗剰余演算を選択する必要があるので、Ｓ６０２（或いはＳ６０３）と同等な判断を行うステップが、（ａ−１）個必要となる。
【０１１６】
変数Ｘに対して、素数Ｐ1、Ｐ12、Ｐ13の逆元（１／Ｐ1、１／Ｐ12、１／Ｐ13）をべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ６０４）。
変数Ｘに対して、素数Ｐ2、Ｐ12、Ｐ23の逆元（１／Ｐ2、１／Ｐ12、１／Ｐ23）をべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ６０５）。
変数Ｘに対して、素数Ｐ3、Ｐ13、Ｐ23の逆元（１／Ｐ3、１／Ｐ13、１／Ｐ23）をべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ６０６）。
【０１１７】
なお、Ｓ６０４、Ｓ６０５、Ｓ６０６の各ステップは、ＮＩＤ（Ｊ）が３分木に対応する１、２、３の各場合に実行するべき乗剰余演算処理であり、ａ分木の場合であれば、ＮＩＤ（Ｊ）が１、２・・・・、（ａ−１）、ａの各場合に実行するべき乗剰余演算ステップが必要となる。つまり、Ｓ６０４（或いはＳ６０５、Ｓ６０６）と同等なべき乗剰余演算実行ステップが、ａ個必要となり、べき乗剰余演算において逆元を使用する素数は、ＮＩＤ（Ｊ）＝ｈ（ｈ：  １≦ｈ≦ａ）に対応する、前記素数表の選択パス番号に値「ｈ」が含まれる全ての素数である。
【０１１８】
変数Ｊが、変数Ｌ−２より大きいかどうか判定する（Ｓ６０７）。大きい場合は図１４のＳ７０１に進み、大きくない場合はＳ６０８に進む。
変数Ｘに対して、１を加算して、その結果を変数Ｘに代入する（Ｓ６０８）。
変数Ｊに対して、１を加算して、その結果を変数Ｊに代入する（Ｓ６０９）。
変数Ｘに対して、１を加算して、その結果を変数Ｘに代入する（Ｓ７０１）。
【０１１９】
処理ノードに係る子ノードが、無効化ノードであるか否かの状態を確認する（Ｓ７０２）。
処理ノードと、パス番号１でつながる子ノードのみが無効化ノードの場合は、変数Ｘに対して、素数Ｐ23の逆元（１／Ｐ23）をべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ７０３）。当該ノードと、パス番号２でつながる子ノードのみが無効化ノードの場合は、変数Ｘに対して、素数Ｐ13の逆元（１／Ｐ13）をべき乗剰余演算して、その結果を変数Ｘに代入する。当該ノードと、パス番号３でつながる子ノードのみが無効化ノードの場合は、変数Ｘに対して、素数Ｐ12の逆元（１／Ｐ12）をべき乗剰余演算して、その結果を変数Ｘに代入する。当該ノードと、パス番号１、及び２でつながる子ノードが無効化ノードの場合は、変数Ｘに対して、素数Ｐ3の逆元（１／Ｐ3）をべき乗剰余演算して、その結果を変数Ｘに代入する。当該ノードと、パス番号１、及び３でつながる子ノードが無効化ノードの場合は、変数Ｘに対して、素数Ｐ2の逆元（１／Ｐ2）をべき乗剰余演算して、その結果を変数Ｘに代入する。当該ノードと、パス番号２、及び３でつながる子ノードが無効化ノードの場合は、変数Ｘに対して、素数Ｐ1の逆元（１／Ｐ1）をべき乗剰余演算して、その結果を変数Ｘに代入する。
【０１２０】
算出した変数Ｘの値をＫｅｉに代入して、暗号化鍵Ｋｅｉを出力する（Ｓ７０４）。
鍵無効化データ生成部２０６は、以上のＳ５０１〜Ｓ７０４の処理を実行することにより、暗号鍵Ｋｅ１〜Ｋｅ５を生成し、Ｋｅ１〜Ｋｅ５それぞれを用いて、鍵情報格納部２０３が保持しているメディア鍵Ｋｍを暗号化する。
また、無効化すべき装置が存在しない場合には、鍵管理装置１００は鍵情報格納部２０３に格納する乱数Ｓを唯一の暗号化鍵として、メディア鍵を暗号化することとなり、記録媒体１２０には、図１１（ｂ）に示すような鍵無効化データが記録される。
【０１２１】
鍵無効化データ生成部２０６は、記録媒体１２０に対し、書込部２０８を介して、鍵無効化データ１２１の書き込みを行う。
なお、記録媒体１２０は、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）等の可搬型の記録メディアである。
【０１２２】
図１５は、記録媒体１２０に記録されるデータを模式的に示す図である。
鍵無効化データ部１２１は、図１１に示した鍵無効化データが記録される。
暗号化コンテンツ鍵部１２２には、記録装置１１０により暗号化されたコンテンツ鍵が書き込まれ、暗号化コンテンツ部１２３には、記録装置１１０により、前記コンテンツ鍵を用いて暗号化されたコンテンツが書き込まれる。
【０１２３】
書込部２０８は、鍵無効化データ生成部２０６が生成した暗号化鍵を、記録媒体１２０に記録する。
＜記録装置１１０＞
記録装置１１０は、自装置内に保持するコンテンツ鍵を用いて著作権を保護すべきコンテンツを暗号化し、記録媒体１２０に記録した後、鍵管理装置１００から取得したデバイス鍵と、当該鍵無効化データとを用いて、メディア鍵を生成し、前記コンテンツ鍵を当該メディア鍵で暗号化し、前記記録媒体１２０に記録する。
【０１２４】
図１６は、記録装置１１０の構成を示すブロック図である。
記録装置１１０は、図１６に示すように、通信部１０００と、デバイス鍵格納部１００１と、復号鍵生成部１００２と、復号部１００３と、暗号化部１００４と、暗号化部１００５と、入出力部１００６と、記憶部１００７とを備え、ハードウェアとしてはＣＰＵ、ＲＯＭ、ＲＡＭ、ハードディスク、キーボード、ネットワークアダプタ等を備えたコンピュータシステムであり、前記ＲＯＭ又は前記ハードディスクには、コンピュータプログラムが記憶され、前記ＣＰＵが、前記コンピュータプログラムに従って動作することにより、記録装置１１０は、その機能を実現する。
また、記録装置１１０は、前述のように、前記木構造の最下位階層であるレイヤ３に属するノードに対応づけられており、装置ＩＤが予め割り当てられている。
【０１２５】
通信部１０００は、ネットワークアダプタとその制御部とから成り、ネットワークを介して鍵管理装置１００と通信を行う。
デバイス鍵格納部１００１は、不揮発性メモリ等の記憶装置とその制御部とから成り、通信部１０００が受信したデバイス鍵を格納する。
復号鍵生成部１００２は、入出力部１００６を介して記録媒体１２０から鍵無効化データ１２１を読み出し、鍵無効化データ１２１と、デバイス鍵格納部１００１が保持するデバイス鍵とを用い、復号鍵を算出する。
【０１２６】
ここで、復号鍵生成部１００２は、デバイス鍵の生成に必要な６個の素数Ｐ1、Ｐ2、Ｐ3、Ｐ12、Ｐ13、Ｐ23を予め保持しているものとする。
以下に、復号鍵生成部１００２が、復号鍵を算出する処理について説明する。
図１７及び図１８は、復号鍵を生成する処理を表すフローチャートである。
復号鍵生成部１００２は、入出力部１００６を介し記録媒体１２０に記録されている鍵無効化データの先頭の鍵無効化エントリを処理フィールドとして読み出す（Ｓ１２０１）。
【０１２７】
復号鍵生成部１００２は、処理フィールドが存在するか否かを判定する（Ｓ１２０２）。即ち、鍵無効化データの全フィールドを読み出してしまい、処理フィールドがない場合、全フィールドのチェックが完了し、処理フィールドがあった場合には、全フィールドのチェックが未完了であると判定する。
全フィールドのチェックが、完了している場合（Ｓ１２０２＝ＮＯ）、本装置が、無効化されていることを示すので処理を終了する。
【０１２８】
全フィールドのチェックが、未完了の場合（Ｓ１２０２＝ＹＥＳ）、処理フィールドに記載されたノードＩＤと、前記装置ＩＤの上位から前記ノードＩＤの桁数分とが、一致するか否かを判定する（Ｓ１２０３）。但し、処理フィールドに記載されたノードＩＤが「０」である場合には、一致すると判定する。
一致しないと判定した場合（Ｓ１２０３＝ＮＯ）、復号鍵生成部１００２は、前回読み出した鍵無効化エントリの次の鍵無効化エントリを、処理フィールドとして読み出す（Ｓ１２０５）。
【０１２９】
一致すると判定した場合（Ｓ１２０３＝ＹＥＳ）、前記木構造において、対応装置を示すノード（レイヤ３に属する）が、前記処理フィールドに記載のノードＩＤで示されるノードから、前記処理フィールドに記載のパス番号で示されるパスを経由して到達するノード（以下、子孫ノードという。）であるか否か判定する（Ｓ１２０４）。
子孫ノードでなかった場合（Ｓ１２０４＝ＮＯ）、Ｓ１２０５へ進む。
【０１３０】
子孫ノードであった場合（Ｓ１２０４＝ＹＥＳ）、復号鍵生成部１００２は、入出力部１００６を介し、記録媒体１２０に記録されている鍵無効化データの、処理フィールドに対応する暗号化メディア鍵を処理暗号化メディア鍵として読み出す（Ｓ１２０６）。
復号鍵生成部１００２は、計算に用いる各変数の初期化を行う。変数Ｘに前記デバイス鍵Ｋｉを代入し、変数Ｊに前記装置ＩＤの桁数を代入する（Ｓ１３０１）。
【０１３１】
復号鍵生成部１００２は、ＩＤ（Ｊ）の示すパスが、前記処理フィールドに記載のノードＩＤが示すノードと直接繋がっているか否かを判定する（Ｓ１３０２）。  図１８において、「ＩＤ（Ｊ）」の記載は、前記装置ＩＤの下位桁からＪ番目のパス番号を示している。例えば、装置ＩＤが「３１２」である装置２０の場合、ＩＤ（１）＝２、ＩＤ（２）＝１、ＩＤ（３）＝３となる。
【０１３２】
繋がっていない場合（Ｓ１３０２＝ＮＯ）、変数Ｘに対して、ＩＤ（Ｊ）に対応する素数の積Ｐｘをべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ１３０３）。
ただし、ＩＤ（Ｊ）に対応する素数Ｐｘとは、ＩＤ（Ｊ）＝１の場合はＰｘ＝Ｐ1Ｐ12Ｐ13であり、ＩＤ（Ｊ）＝２の場合はＰｘ＝Ｐ2Ｐ12Ｐ23、ＩＤ（Ｊ）＝３の場合はＰｘ＝Ｐ3Ｐ13Ｐ23である。
【０１３３】
次に、変数Ｘに対しては１を加算して、その結果を変数Ｘに代入し、変数Ｊに対しては１を減算して、その結果を変数Ｊに代入する（Ｓ１３０４）。
繋がっている場合には（Ｓ１３０２＝ＹＥＳ）、変数Ｘに対して、ＩＤ（Ｊ）に対応する素数の積Ｐｘから処理フィールドにより示される素数Ｐｙを除いたものをべき乗剰余演算して、その結果を変数Ｘに代入する（Ｓ１３０５）。
【０１３４】
前述のＰｙにおけるｙは、前記処理フィールドの選択パス番号を示しており、例えば、選択パス番号が「１２」であれば、Ｐｙは、Ｐ12であり、ＩＤ（Ｊ）＝１の場合、Ｐｘ＝Ｐ1Ｐ12Ｐ13のうちＰｙであるＰ12を除いたＰ1Ｐ13をべき乗剰余演算して、その結果を変数Ｘに代入することとなる。
ここで、図中の「Ｐｘ／Ｐｙ」の記載は、上述した通り、Ｐ12は用いずに、Ｐ1Ｐ13を計算することを意味しており、Ｐｘ＝Ｐ1Ｐ12Ｐ13に、ＰｙであるＰ12の逆元である１／Ｐ12を掛けることを意味するものではない。
【０１３５】
算出した変数Ｘの値をＫｄｉに代入して、復号鍵Ｋｄｉを出力する（Ｓ１３０６）。
復号鍵生成部１００２は、Ｓ１２０６で取り出した暗号化メディア鍵を、Ｓ１３０６で得た復号鍵Ｋｄｉで復号しメディア鍵を取得する（Ｓ１３０７）。
以上のステップにより、無効化されていない各装置は自身が保有するデバイス鍵から復号鍵を求めることができ、求めた復号鍵を使ってメディア鍵を復号することができる。一方、無効化されている装置が保有するデバイス鍵では、いずれの復号鍵も求めることができないため、メディア鍵を復号することができない。
【０１３６】
暗号化部１００４は、復号部１００３により復号されたメディア鍵を用いて、記憶部１００７に記憶されているコンテンツ鍵を暗号化し、入出力部１００６を介して、暗号化コンテンツ鍵格納部１０１２に格納する。
暗号化部１００５は、記憶部１００７に記憶されているコンテンツ鍵を用い、記憶部１００７に記憶されているコンテンツを暗号化し、入出力部１００６を介して、暗号化コンテンツ格納部１０１３に書き込む。
【０１３７】
入出力部１００６は、記録媒体１２０に対するデータの書き込み、及び記録媒体１２０からのデータの読み出しを行う。
記憶部１００７は、著作権を保護すべきコンテンツと、当該コンテンツを暗号化するためのコンテンツ鍵とを予め記憶する。
＜再生装置１３０＞
再生装置１３０は、鍵管理装置１００により配布されたデバイス鍵を保持しており、記録媒体１２０から鍵無効化データを読み出し、デバイス鍵と前記鍵無効化データとを用いてメディア鍵を取得し、記録媒体１２０から暗号化コンテンツ鍵を読み出し、前記メディア鍵で暗号化コンテンツ鍵を復号し、暗号化コンテンツを読み出して、コンテンツ鍵で復号し、復号したコンテンツを、当該コンテンツの再生を行う。
【０１３８】
図１９は、再生装置１３０の構成を示すブロック図である。
再生装置１３０は、図１９に示すように、通信部１１００と、デバイス鍵格納部１１０１と、復号鍵生成部１１０２と、復号部１１０３と、復号部１１０４と、復号部１１０５と、入出力部１１０６と、再生部１１０７とを備え、ハードウェアとしてはＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ハードディスク、ネットワークアダプタ、トランスポートデコーダ、フロントエンド等を備えたＤＶＤレコーダ等の記録再生装置であり、ＲＯＭ又は前記ハードディスクには、コンピュータプログラムが記憶され、前記ＣＰＵが、上記コンピュータプログラムに従って動作することにより、再生装置１３０は、その機能を実現する。
【０１３９】
通信部１１００は、ネットワークアダプタとその制御部から成り、ネットワークを介して、鍵管理装置１００と通信を行う。
デバイス鍵格納部１１０１は、不揮発性メモリ等の記録装置とその制御部とから成り、通信部１１００が、鍵管理装置１００より発行されたデバイス鍵を取得した場合に、当該デバイス鍵を格納する。
【０１４０】
また、前記デバイス鍵は、予め、ＲＯＭに書き込まれていてもよい。
復号鍵生成部１１０２は、入出力部１１０６を介して記録媒体１２０から鍵無効化データ１２１を読み出し、鍵無効化データ１２１と、デバイス鍵格納部１１０１が保持するデバイス鍵とを用い、復号鍵を算出する。
復号鍵生成部１１０２は、デバイス鍵の生成に必要な６個の素数Ｐ1、Ｐ2、Ｐ3、Ｐ12、Ｐ13、Ｐ23を予め保持しているものとし、復号鍵生成部１００２と同様、図１７、図１８で示したフローチャートに従い前記復号鍵を算出する。
【０１４１】
上述した、図１７、図１８についての説明において、入出力部１００６を入出力部１１０６と読替え、復号鍵生成部１００２を、復号鍵生成部１１０２と読み替えることにより、復号鍵生成部１１０２が行う復号鍵の生成処理が説明できる。
ここで、例えば、図３に示した木構造に関し、装置１がデバイス鍵Ｋ１から復号鍵Ｋｄ４を求めるためには、デバイス鍵Ｋ１に対して、Ｐ1Ｐ12Ｐ13をべき乗剰余演算して、さらにＰ23の逆元（１／Ｐ23）をべき乗剰余演算しなければならない。しかし、法ｎ（ｎ：ｎ＝ｐ×ｑ）に関する素数ｐ、ｑは、鍵管理装置１００だけが知る秘密の値であり、各装置はその値を知らないため、素数Ｐ23から、その逆元１／Ｐ23を求めることは、計算量的に困難である。
【０１４２】
したがって、無効化されている装置１は自身が保有するデバイス鍵Ｋ１から復号鍵Ｋｄ４を求めることができない。
同様の理由により、装置１は、Ｋｄ１〜Ｋｄ３、Ｋｄ５のいずれの復号鍵も求めることができず、さらに、装置２６も、Ｋｄ１〜Ｋｄ５のいずれの復号鍵も求めることができないため、無効化すべき不正装置によるコンテンツの著作権侵害を防止することが可能となる。
【０１４３】
復号部１１０３は、入出力部１１０６を介して、記録媒体１２０から暗号化メディア鍵を読み出し、復号鍵生成部１１０２で生成した復号鍵を用いて、当該暗号化メディア鍵を復号し、メディア鍵を取得する。
復号部１１０４は、復号部１１０３により復号されたメディア鍵を用いて、記録媒体１２０から読み出した暗号化コンテンツ鍵を復号し、コンテンツ鍵を得る。
【０１４４】
復号部１１０５は、記録媒体１２０から暗号化コンテンツを読み出し、前記コンテンツ鍵を用いて、前記暗号化コンテンツを復号し、コンテンツを得る。
入出力部１１０６は、記録媒体１２０に対する情報の入出力を行う。
再生部１１０７は、復号部１１０５が得たコンテンツを再生する。
＜動作＞
鍵管理装置１００が３分木を用いて２７台の装置を管理する場合の著作権保護システムの全体動作について述べる。
【０１４５】
鍵管理装置１００において、素数割当部２０１は、図３に示した木構造である３分木を用いるので、図６に示すフローチャートに従い、図５（ａ）に示す素数表を生成し保持する。素数表の生成過程で生成した、２3−２＝６個の素数、Ｐ1、Ｐ2、Ｐ3、Ｐ12、Ｐ13、Ｐ23は、記録装置１１０と再生装置１３０に予め配布される。ここで再生装置１３０は、図３に示した木構造における、装置２６であるとする。
【０１４６】
次に、デバイス鍵生成部２０４は、素数割当部２０１により生成され鍵情報格納部２０３に保持されたＰ１〜Ｐ２３と、乱数生成部２０２により生成された乱数Ｓとを用い、図７に示したフローチャートに従い、各再生装置に対するデバイス鍵を生成する。
ここで、装置２６に対するデバイス鍵Ｋ２６は、
Ｋ２６ ＝ （（Ｓ^（１／（Ｐ3Ｐ13Ｐ23））＋１）^（１／（Ｐ3Ｐ13Ｐ23））＋１）^（１／(Ｐ2Ｐ12Ｐ23））
である。
【０１４７】
生成したデバイス鍵Ｋ２６は、送信部２０７を介して、Ｋ２６に対応する装置である再生装置１３０に配布する。
再生装置１３０において、通信部１１００がＫ２６を受信し、デバイス鍵格納部１１０１がＫ２６を保持する。
次に、再生装置によりコンテンツが再生されるまでの動作を、無効化された装置がない場合と、無効化された装置に装置２６が含まれない場合と、無効化された装置に装置２６が含まれる場合とに分けて述べる。
＜無効化された装置がない場合＞
鍵管理装置１００において、鍵無効化データ生成部２０６は、無効化された装置がない場合には、図１０のフローチャートによらず、図１１（ｂ）に示す鍵無効化データを生成し、書込部２０８が、当該無効化データを記録媒体１２０に記録する。
【０１４８】
鍵無効化データが記録された記録媒体１２０は、記録装置１１０へと転送される。
次に、記録装置１１０は、記録媒体１２０に記録された鍵無効化データと、無効化されていない装置に対するデバイス鍵、ここではＫ２６を用い、図１２〜図１４のフローチャートに従い、復号鍵Ｓを生成する。
記録装置１１０は、復号鍵Ｓを用い、前記鍵無効化データに記録された暗号化メディア鍵を復号して、メディア鍵を取得する。
【０１４９】
記録装置１１０は、記憶部１００７に記憶するコンテンツ鍵を用いて、同じく記憶部１００７に記憶するコンテンツを暗号化し、記録媒体１２０の暗号化コンテンツ部１２３に記録し、また、前記メディア鍵を用いて、前記コンテンツ鍵を暗号化し、暗号化コンテンツ鍵部１２２に記録する。
記録媒体１２０は、販売されるなど配布されて再生装置１３０の所持者の手元に渡り、再生装置１３０により再生処理が行われる。
【０１５０】
再生装置１３０において、復号鍵生成部１１０２は、鍵無効化データ１２１を用い、図１７、図１８に示すフローチャートにより、デバイス鍵Ｋ２６から復号鍵Ｓを生成する。
復号部１１０３は、復号鍵Ｓを用い、前記鍵無効化データに記録された暗号化メディア鍵を復号し、メディア鍵を取得する。復号部１１０４は、前記メディア鍵を用いて、記録媒体１２０に記録された暗号化コンテンツ鍵を復号し、コンテンツ鍵を生成する。復号部１１０５は、前記コンテンツ鍵を用いて、記録媒体１２０に記録された暗号化コンテンツを復号し、コンテンツを生成する。再生部１１０７は、前記コンテンツを再生する。
＜再生装置１３０が、無効化されていない装置２７である場合＞
鍵管理装置１００において、鍵無効化データ生成部２０６は、無効化された装置が装置１及び２６である場合に、図１０のフローチャートに従い、図１１（ａ）に示す鍵無効化データを生成し、記録媒体１２０に記録する。
【０１５１】
鍵無効化データが記録された記録媒体１２０は、記録装置１１０へと転送される。
次に、記録装置１１０は、記録媒体１２０に記録された鍵無効化データと、無効化されていない装置に対するデバイス鍵、ここではＫ２６を用い、図１２〜図１４のフローチャートに従い、復号鍵Ｋｅ５を生成する。
記録装置１１０は、復号鍵Ｋｅ５を用い、前記鍵無効化データに記録された暗号化メディア鍵を復号して、メディア鍵を取得する。
【０１５２】
記録装置１１０は、記憶部１００７に記憶するコンテンツ鍵を用いて、同じく記憶部１００７に記憶するコンテンツを暗号化し、記録媒体１２０の暗号化コンテンツ部１２３に記録し、また、前記メディア鍵を用いて、前記コンテンツ鍵を暗号化し、暗号化コンテンツ鍵部１２２に記録する。
記録媒体１２０は、販売等に配布され、再生装置１３０の所持者の手元に渡り、再生装置１３０により再生処理が行われる。
【０１５３】
ここで再生装置１３０は、無効化されていない装置である装置２７であるとする。
再生装置１３０において、復号鍵生成部１１０２は、鍵無効化データ１２１を用い、図１７、図１８に示すフローチャートにより、デバイス鍵Ｋ２７から復号鍵Ｋｅ５を生成する。
Ｋ２７は、
Ｋ２７ ＝ （（Ｓ^（１／（Ｐ3Ｐ13Ｐ23））＋１）^（１／（Ｐ3Ｐ13Ｐ23））＋１）^（１／(Ｐ3Ｐ13Ｐ23））
である。
【０１５４】
図３の木構造によると、装置２７の装置ＩＤは「３３３」であり、図１７のステップＳ１２０３において、鍵無効化データの１〜４行目が処理フィールドである場合には、判定がＮｏとなり、Ｓ１２０５に進むが、鍵無効化データの５行目のエントリが処理フィールドである場合に、ノードＩＤである「３３」が、装置ＩＤ「３３３」の上位２桁である「３３」と一致するので、判定がＹｅｓとなり、Ｓ１２０４に処理が進む。
【０１５５】
Ｓ１２０４において、鍵無効化データの５行目の選択パス番号は「１３」であり、装置２７は、前記木構造において、パス番号３のパスでＮ３３と繋がっているので、復号鍵生成部１１０２は、子孫に含まれると判断し、Ｓ１２０６へと進む。
復号鍵生成部１１０２は、Ｓ１２０６において、対応する暗号化メディア鍵であるＥ（Ｋｅ５，Ｋｍ）を取り出す。
【０１５６】
Ｓ１３０１において、ＸにＫ２７を代入し、Ｊに３を代入する。
Ｓ１３０２において、ＩＤ（３）の示すパス「３」が、選択パス番号である「１３」のうちの「３」に該当するため、Ｙｅｓと判定される。
Ｓ１３０５において、Ｐ3、Ｐ13、Ｐ23のうち、選択パス番号である１３で示されるＰ13を除いた、Ｐ3、Ｐ23の各逆元を、Ｋ２７に対し、べき乗剰余演算する。
【０１５７】
（Ｋ２７）＾（Ｐ3Ｐ23）＝ （（Ｓ^（１／（Ｐ3Ｐ13Ｐ23））＋１）^（１／（Ｐ3Ｐ13Ｐ23））＋１）^（１／(Ｐ13））  ＝  Ｋｅ５
であり、復号鍵生成部１１０２は、Ｋｅ５を生成できたことになる。
次に、復号部１１０３は、復号鍵Ｋｅ５を用い、前記鍵無効化データに記録された暗号化メディア鍵を復号し、メディア鍵を取得する。
【０１５８】
復号部１１０４は、前記メディア鍵を用いて、記録媒体１２０に記録された暗号化コンテンツ鍵を復号し、コンテンツ鍵を生成する。
復号部１１０５は、前記コンテンツ鍵を用いて、記録媒体１２０に記録された暗号化コンテンツを復号し、コンテンツを生成する。
再生部１１０７は、前記コンテンツを再生する。
＜再生装置１３０が、無効化された装置２６である場合＞
鍵管理装置１００において、鍵無効化データ生成部２０６は、無効化された装置が装置１及び２６である場合に、図１０のフローチャートに従い、図１１（ａ）に示す鍵無効化データを生成し、記録媒体１２０に記録する。
【０１５９】
鍵無効化データが記録された記録媒体１２０は、記録装置１１０へと転送される。
次に、記録装置１１０は、記録媒体１２０に記録された鍵無効化データと、無効化されていない装置に対するデバイス鍵、ここではＫ２６でないＫ２７を用い、図１２〜図１４のフローチャートに従い、復号鍵Ｋｅ５を生成する。
記録装置１１０は、復号鍵Ｋｅ５を用い、前記鍵無効化データに記録された暗号化メディア鍵を復号して、メディア鍵を取得する。
【０１６０】
記録装置１１０は、記憶部１００７に記憶するコンテンツ鍵を用いて、同じく記憶部１００７に記憶するコンテンツを暗号化し、記録媒体１２０の暗号化コンテンツ部１２３に記録し、また、前記メディア鍵を用いて、前記コンテンツ鍵を暗号化し、暗号化コンテンツ鍵部１２２に記録する。
記録媒体１２０は、販売等に配布され、再生装置１３０の所持者の手元に渡り、再生装置１３０により再生処理が行われる。
【０１６１】
ここで再生装置１３０は、無効化された装置である装置２６であるとする。
再生装置１３０において、復号鍵生成部１１０２は、鍵無効化データ１２１を用い、図１７、図１８に示すフローチャートにより、デバイス鍵Ｋ２６から復号鍵Ｋｅ５の生成を試みる。
しかし、図３の木構造によると、装置２６の装置ＩＤは「３３２」であり、図１７のステップＳ１２０３において、鍵無効化データの１〜４行目が処理フィールドである場合には、判定がＮｏとなり、Ｓ１２０５に進むが、鍵無効化データの５行目のエントリが処理フィールドである場合に、ノードＩＤである「３３」が、装置ＩＤ「３３２」の上位２桁である「３３」と一致するので、判定がＹｅｓとなり、Ｓ１２０４に処理が進む。
【０１６２】
Ｓ１２０４において、鍵無効化データの５行目の選択パス番号は「１３」であり、装置２６は、前記木構造において、パス番号２のパスでＮ３３と繋がっているので、復号鍵生成部１１０２は、子孫に含まれないと判断し、Ｓ１２０５へと進む。
復号鍵生成部１１０２は、Ｓ１２０５において、読み出すべきフィールドがなく、Ｓ１２０２において、全フィールドのチェックが完了したと判定し（Ｓ１２０２＝Ｙｅｓ）、処理を終了するので、Ｋｅ５はもとより、Ｋｅ５以外のＫｅ１〜Ｋｅ４のいずれの復号鍵も生成することができない。
【０１６３】
また、Ｋｅ５の不当な方法での生成を試みる場合、Ｐ13の逆元を計算により求める必要があるが、法であるｎのみを知り、ｎを生成するためのｐ、ｑを知らないので、Ｐ13の逆元を計算することは計算量的に困難である。
また、Ｋｅ１〜Ｋｅ４のいずれも、Ｋｅ５の生成を試みる場合と同等の理由によって、生成することは困難である。
【０１６４】
よって、メディア鍵、コンテンツ鍵等の生成も困難であり、装置２６においては、コンテンツの再生ができない。
＜その他変形例＞
（１）本発明では、記録媒体をＤＶＤ−ＲＡＭのようなレコーダブルメディアとする構成としたが、本発明はその構成に限定されるものではない。例えば、記録媒体をＤＶＤ−Ｖｉｄｅｏのようなプリレコーディッドメディアとして、各再生装置がデバイス鍵を保有して、記録媒体に記録されたコンテンツを再生する構成であってもよい。また、この場合、記録媒体への書き込み装置がデバイス鍵を保有する必要はなく、鍵管理装置から直接メディア鍵を受け取り、そのメディア鍵に基づいてコンテンツを暗号化して書き込む構成であってもよい。
【０１６５】
（２）本発明では、コンテンツを暗号化するメカニズムとして、メディア鍵でコンテンツ鍵を暗号化して、コンテンツ鍵でコンテンツを暗号化する構成としたが、本発明はその構成に限定されるものではない。例えば、メディア鍵で直接コンテンツを暗号化して鍵階層を１つ減らす構成でもよく、逆にディスク鍵を導入して、メディア鍵でディスク鍵を暗号化して、ディスク鍵でコンテンツ鍵を暗号化して、コンテンツ鍵でコンテンツを暗号化して鍵階層を１つ増やす構成であってもよい。あるいは、鍵階層の途中で別途異なる情報を追加して鍵を変調するような構成であってもよい。
【０１６６】
（３）本発明では、鍵無効化データと暗号化コンテンツを同一の記録媒体に記録する構成としたが、本発明はその構成に限定されるものではない。例えば、鍵無効化データを記録する記録媒体と、暗号化コンテンツを記録する記録媒体を変えて配布する構成であってもよい。その場合、記録装置、あるいは再生装置では、まず、鍵無効化データが記録された記録媒体を挿入してメディア鍵を算出してから、別の記録媒体を挿入して、コンテンツの記録、あるいは再生を行う構成となる。
【０１６７】
（４）本発明では、鍵無効化データ、並びに暗号化コンテンツを記録媒体に記録して配布する構成としてが、本発明はその構成に限定されるものではない。例えば、放送や、インターネットなどの通信媒体を利用して配布する構成であってもよい。
（５）本発明では、鍵管理装置が、鍵、あるいは各装置を管理するための木構造を３分木として構成したが、本発明はその構成に限定されるものではない。例えば、木構造は２分木であっても、４分木であってもよい。２分木の場合は、デバイス鍵の生成等に利用する素数は２個であり、４分木の場合は１４個となる。
【０１６８】
（６）本発明では、鍵管理装置におけるデバイス鍵の生成ステップで、レイヤごとにべき乗剰余演算を行った後、１を加算する構成としたが、本発明はその構成に限定されるものではない。例えば、加算する値は２であってもよく、その演算も減算、乗算、除算、ＸＯＲ演算等、可逆性のある演算であればその演算、並びに演算する値を限定するものではない。
【０１６９】
（７）本発明では、記録装置でメディア鍵を暗号化する際、デバイス鍵から算出した暗号化鍵で直接メディア鍵を暗号化する構成としたが、本発明はその構成に限定されるものではない。例えば、暗号化鍵をＳＨＡ−１などの圧縮関数へ入力して、その出力値、あるいはその一部で個々のメディア鍵を暗号化していく構成であってもよい。この場合、再生装置でも同様に、算出した復号鍵を圧縮関数に入力してその出力値、あるいはその一部でメディア鍵を復号する。あるいは、算出した暗号化鍵で、当該暗号化鍵よりも短いサイズのブロック鍵を暗号化しておき、そのブロック鍵で個々のメディア鍵を暗号化していく構成であってもよい。この場合、再生装置では、算出した復号鍵で、まずブロック鍵を復号してからメディア鍵を復号する。
【０１７０】
（８）本発明では、各レイヤ、各ノードで共通の素数を利用する形態としたが、本発明はその構成に限定されるものではない。例えば、レイヤごとに利用する素数の集合を変えたり、ノードごとに利用する素数の集合を変えたりする構成であってもよい。
（９）本発明の実施の形態では、３分木の木構造の例で、６つの素数を利用する形態を示した。本発明では、この６つの素数に特に制限はなく、計算量の削減を目的として、小さい６つの素数を選択することも可能である。具体的には、この６つの素数は、小さい順に、３、５、７、１１、１３、１７の６つであってもよい。
【０１７１】
（１０）本発明では、素数を予め生成して保持する形態を示したが、本発明はその構成に限定されるものではない。例えば、素数生成のルールだけを予め決めておき、その都度素数を生成してから演算を実行する構成であってもよい。
（１１）各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。
【０１７２】
（１２）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０１７３】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。
【０１７４】
また、前記プログラム又は前記デジタル信号を前記記録媒体に記録して移送することにより、又は前記プログラム又は前記デジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（１３）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【産業上の利用可能性】
【０１７５】
本発明の著作権保護システムは、著作権の保護が必要であるコンテンツを暗号化して配布する配布システムと、暗号化されたコンテンツを復号して再生する再生装置とから成るシステムの基盤技術として使用されるものであり、前記配布システム及び前記再生装置は、デジタルコンテンツを再生するデジタル家電等の製造業者により生産等がなされる。
【図面の簡単な説明】
【０１７６】
【図１】本発明の著作権保護システムの構成の概略を示す図である。
【図２】本発明の著作権保護システム全体の動作を示すフローチャートである。
【図３】２７台の装置を管理するための３分木である木構造を示す図である。
【図４】本発明の鍵管理装置の構成を示すブロック図である。
【図５】素数割当部が生成して保持する素数表を示す図である。
【図６】ａ分木について、素数割当部が、素数表を生成するための処理を示すフローチャートである。
【図７】デバイス鍵生成部が、３分木である木構造に基づきデバイス鍵を生成する処理を示すフローチャートである。
【図８】木構造において、装置を無効化する場合の暗号化鍵を出力するノードと暗号化鍵の値との関係を模式的に示す図である。
【図９】無効化装置特定部が保持する、無効化装置識別情報と木構造とに基づく無効表を示す図である。
【図１０】鍵無効化データ生成部における、鍵無効化データのヘッダ部を生成するための処理を示すフローチャートである。
【図１１】記録媒体に記録される鍵無効化データのデータ構造を示す図である。
【図１２】暗号鍵を生成する際の動作を示すフローチャートである。
【図１３】暗号鍵を生成する際の動作を示すフローチャートである。
【図１４】暗号鍵を生成する際の動作を示すフローチャートである。
【図１５】記録媒体に記録されるデータを模式的に示す図である。
【図１６】本発明の記録装置の構成を示すブロック図である。
【図１７】復号鍵を生成する処理を表すフローチャートである。
【図１８】復号鍵を生成する処理を表すフローチャートである。
【図１９】再生装置の構成を示すブロック図である。
【符号の説明】
【０１７７】
１００  鍵管理装置
１１０  記録装置
１２０  記録媒体
１２１  鍵無効化データ部
１２２  暗号化コンテンツ鍵部
１２３  暗号化コンテンツ部
１３０  再生装置
【図１】
0004638176.tif 000033
【図２】
0004638176.tif 000034
【図３】
0004638176.tif 000035
【図４】
0004638176.tif 000036
【図５】
0004638176.tif 000037
【図６】
0004638176.tif 000038
【図７】
0004638176.tif 000039
【図８】
0004638176.tif 000040
【図９】
0004638176.tif 000041
【図１０】
0004638176.tif 000042
【図１１】
0004638176.tif 000043
【図１２】
0004638176.tif 000044
【図１３】
0004638176.tif 000045
【図１４】
0004638176.tif 000046
【図１５】
0004638176.tif 000047
【図１６】
0004638176.tif 000048
【図１７】
0004638176.tif 000049
【図１８】
0004638176.tif 000050
【図１９】
0004638176.tif 000051