(57)【要約】所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成し（Ｓ１０３）、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することにより得られる第３のディジット列を暗号鍵とする（Ｓ１０４）。
2008072351.tif 000002
【特許請求の範囲】
【請求項１】
ストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成方法において、  所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成し、  生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成することを特徴とする、暗号鍵生成方法。
【請求項２】
所定の第４のディジット列における特定のディジットに基づいて、前記特定の組の複数のディジットが決定される、請求項１に記載の暗号鍵生成方法。
【請求項３】
前記第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記第４のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］として、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第３のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）は、次の式により求められる、請求項２に記載の暗号鍵生成方法。  ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）
【請求項４】
ストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、  所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する手段と、  生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する手段と  を備えることを特徴とする、暗号鍵生成装置。
【請求項５】
ストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、  所定の演算処理を実施する演算装置と、  所定の第１のディジット列を記憶するメモリとを備え、  前記演算装置は、前記メモリから前記第１のディジット列を読み出し、その読み出した第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成するように構成され、  さらに、前記演算装置は、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成するように構成されていることを特徴とする、暗号鍵生成装置。
【請求項６】
ストリーム暗号処理に用いられる暗号鍵を生成する暗号演算回路において、  所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する第１関数回路と、  生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する第２関数回路と  を備えることを特徴とする、暗号演算回路。
【請求項７】
前記第２関数回路によって生成された第３のディジット列を用いて、外部から入力された平文に対する暗号化処理を実行する暗号化回路をさらに備える、請求項６に記載の暗号演算回路。
【請求項８】
前記第１のディジット列は、共通鍵である、請求項６または請求項７に記載の暗号演算回路。
【請求項９】
前記第１関数回路は、所定の第４のディジット列における特定のディジットに基づいて、前記特定の組の複数のディジットを決定するように構成されている、請求項６乃至請求項８の何れかに記載の暗号演算回路。
【請求項１０】
前記第４のディジット列としての乱数を発生する乱数発生回路をさらに備える、請求項９に記載の暗号演算回路。
【請求項１１】
前記第１関数回路は、前記第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記第４のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）を、次の式により求めるように構成されている、請求項９に記載の暗号演算回路。  ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）
【請求項１２】
外部の通信装置と非接触で通信可能な無線タグにおいて、  請求項６乃至１１の何れかに記載の暗号演算回路と、  当該暗号演算回路により生成された暗号鍵を用いて生成された暗号文を、前記通信装置に対して送信する送信装置とを備えることを特徴とする、無線タグ。
【請求項１３】
コンピュータに、ストリーム暗号処理に用いられる暗号鍵の生成を行わせるためのコンピュータプログラムにおいて、  前記コンピュータに、  所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施させることによって、第２のディジット列を生成させる手順と、  生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することにより得られる第３のディジット列である暗号鍵を生成させる手順と  を実行させるためのコンピュータプログラム。
【請求項１４】
前記第２のディジット列を生成させる手順は、前記コンピュータに、所定の第４のディジット列における特定のディジットに基づいて、前記特定の組の複数のディジットを決定させる、請求項１３に記載のコンピュータプログラム。
【請求項１５】
前記第２のディジット列を生成させる手順は、前記コンピュータに、前記第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記第４のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）を、次の式により求めさせる、請求項１３に記載のコンピュータプログラム。  ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、暗号システムにおける暗号鍵を生成する暗号鍵生成方法に関し、特に少ない計算量で高度なセキュリティが確保された暗号鍵を生成する暗号鍵生成方法、その方法を実施するための暗号鍵生成装置及び暗号演算回路、その暗号演算回路を備える無線タグ、並びに前記方法をコンピュータに実施させるためのコンピュータプログラムに関する。
【背景技術】
【０００２】  近年、高度情報化社会の発展に伴い、情報の盗取など多くの問題が発生している。その結果、それらの問題の発生を未然に防止するために、情報を暗号化することによってセキュリティを確保する技術が要求されている。【０００３】  現在、広く普及している暗号技術として、共通鍵暗号であるＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）、及びＤＥＳと比べてより暗号強度の高いＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）が挙げられる。【０００４】  また、これらのＤＥＳ及びＡＥＳ以外にも、数多くの共通鍵暗号系が提案されている。そのうちの一つに、２ｆａｃｔｏｒ暗号システムと呼ばれるものがある。この２ｆａｃｔｏｒ暗号システムでは、ＰＤＡＦ（Ｐｏｓｉｔｉｏｎ  Ｄｉｇｉｔ  Ａｌｇｅｂｒａ  Ｆｕｎｃｔｉｏｎ）及びＯＷＣ（Ｏｎｅ−Ｗａｙ  Ｃｕｔ  ｆｕｎｃｔｉｏｎ）の２つの関数を用いて、共通鍵の管理等を行う方法が提案されている（例えば、特許文献１および特許文献２を参照。）【特許文献１】米国特許出願公開第２００３／０１４９８７６号明細書
【特許文献２】米国特許出願公開第２００６／０３４４５６号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】  ところで、近年では、微少な無線チップを搭載した無線タグ（ＲＦＩＤ（Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ  ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）タグ）についての研究が進んでいる。無線タグについては、これまで、主に流通業界においてバーコードに代わる商品の識別及び管理を行う技術として研究されてきたが、現在では、いわゆるユビキタスコンピューティングの分野における中心的な技術になり得るものとして注目されている。【０００６】  今後は、無線タグを用いて、商品だけではなく、人の識別及び管理を行うことなども期待されている。この場合、その人のプライベートに関わる事項など、高度なセキュリティを保つ必要があるデータを扱うことになるため、データを暗号化する必要性が高くなる。【０００７】  しかしながら、上記のＤＥＳによる場合、暗号強度が十分ではないため、セキュリティを確保することが困難であるという問題があった。【０００８】  また、上記のＡＥＳによる場合、ＤＥＳと比べて暗号強度は十分であるといえるが、アルゴリズムが複雑であるため、計算量が多くなり、微少な電力しか供給されず且つ回路規模も小さくならざるを得ないという制約を有する無線タグにおいて、実行することは困難であった。【０００９】  本発明は、斯かる事情に鑑みてなされたものであり、その目的は、例えば無線タグのような微少な電力及び回路規模に限られるという制約がある場合であっても、セキュリティを確保することができる暗号鍵生成方法、その方法を実施するための暗号鍵生成装置及び暗号演算回路、その暗号演算回路を備える無線タグ、並びに前記方法をコンピュータに実施させるためのコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１０】  本発明者は、無線タグのように微少な電力及び回路規模に限られるという制約が伴う場合であっても、問題なく実行することができるような計算量の少ない暗号技術を実現するために、鋭意検討を重ねてきた。そして、上述した２ｆａｃｔｏｒ暗号システムで提案されているＰＤＡＦ及びＯＷＣという関数が桁上げのないディジット毎の加算のみで構成されている点に着目し、これらの考え方を用いることにより、計算量が少なく、しかもセキュリティが確保されたストリーム暗号系の暗号技術を実現することができると考えた。【００１１】  これらの知見に基づいて、本発明者は、以下に示す発明をした。【００１２】  本発明の暗号鍵生成方法は、ストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成方法において、所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成し、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する。【００１３】  このように桁上げのないディジット毎の加算のみで暗号鍵を生成することができるため、少ない計算量で足りる。【００１４】  上記発明に係る暗号鍵生成方法において、所定の第４のディジット列における特定のディジットに基づいて、前記特定の組の複数のディジットが決定されるようにしてもよい。【００１５】  また、上記発明に係る暗号鍵生成方法において、前記第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記第４のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］として、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）は、ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求められるようにしてもよい。【００１６】  本発明の暗号鍵生成装置は、ストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する手段と、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する手段とを備える。【００１７】  また、本発明の暗号鍵装置は、ストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、所定の演算処理を実施する演算装置と、所定の第１のディジット列を記憶するメモリとを備え、前記演算装置は、前記メモリから前記第１のディジット列を読み出し、その読み出した第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成するように構成され、さらに、前記演算装置は、生成した第２のディジット列を、複数のディジット��に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成するように構成されている。【００１８】  本発明の暗号演算回路は、ストリーム暗号処理に用いられる暗号鍵を生成する暗号演算回路において、所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する第１関数回路と、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する第２関数回路とを備える。【００１９】  上記発明に係る暗号演算回路において、前記第２関数回路によって生成された第３のディジット列を用いて、外部から入力された平文に対する暗号化処理を実行する暗号化回路をさらに備えるようにしてもよい。【００２０】  また、上記発明に係る暗号演算回路において、前記第１のディジット列は、共通鍵であってもよい。【００２１】  また、上記発明に係る暗号演算回路において、前記第１関数回路は、所定の第４のディジット列における特定のディジットに基づいて、前記特定の組の複数のディジットを決定するように構成されているようにしてもよい。【００２２】  また、上記発明に係る暗号演算回路において、前記第４のディジット列としての乱数を発生する乱数発生回路をさらに備えるようにしてもよい。【００２３】  さらに、上記発明に係る暗号演算回路において、前記第１関数回路は、前記第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記第４のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）を、ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求めるように構成されていてもよい。【００２４】  本発明の無線タグは、外部の通信装置と非接触で通信可能な無線タグにおいて、  上記発明に係る暗号演算回路と、当該暗号演算回路により生成された暗号鍵を用いて生成された暗号文を、前記通信装置に対して送信する送信装置とを備える。【００２５】  本発明のコンピュータプログラムは、コンピュータに、ストリーム暗号処理に用いられる暗号鍵の生成を行わせるためのコンピュータプログラムにおいて、前記コンピュータに、所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施させることによって、第２のディジット列を生成させる手順と、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することにより得られる第３のディジット列である暗号鍵を生成させる手順とを実行させる。【００２６】  上記発明に係るコンピュータプログラムにおいて、前記第２のディジット列を生成させる手順は、前記コンピュータに、所定の第４のディジット列における特定のディジットに基づいて、前記特定の組の複数のディジットを決定させるようにしてもよい。【００２７】  また、上記発明に係るコンピュータプログラムにおいて、前記第２のディジット列を生成させる手順は、前記コンピュータに、前記第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記第４のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）を、ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求めさせるようにしてもよい。【００２８】  本発明の上記目的、他の目的、特徴、及び利点は、添付図面参照の下、以下の好適な実施態様の詳細な説明から明らかにされる。
【発明の効果】
【００２９】  本発明の暗号鍵生成方法、その方法を実施するための暗号鍵生成装置、その方法を実施するための暗号鍵生成装置及び暗号演算回路、その暗号演算回路を備える無線タグ、並びに前記方法をコンピュータに実施させるためのコンピュータプログラムによれば、少ない計算量でセキュリティを確保することが可能となる。
【図面の簡単な説明】
【００３０】
【図１】図１は、本発明の実施の形態１に係る無線タグ及び暗号鍵生成装置を備える無線タグシステムの構成を示すブロック図である。
【図２】図２は、暗号文の生成に伴う、暗号演算回路の処理手順を示すフローチャートである。
【図３】図３は、復号処理に伴う、復号装置の処理手順を示すフローチャートである。
【００３１】
【図４】図４は、本発明の実施の形態２に係る暗号鍵生成装置を備えるコンピュータシステムの構成を示すブロック図である。
【符号の説明】
【００３２】  １    無線タグ  ２    暗号鍵生成装置（復号装置）  ３    暗号鍵生成装置（暗号化装置）  ４    暗号鍵生成装置（復号装置）  ５    通信ネットワーク  １１  制御回路  １２  メモリ回路  １３  暗号演算回路  １４  無線回路  １５  アンテナ  １６  電源部  ２１  ＣＰＵ  ２２  メモリ部  ２３  暗号処理プログラム  ２４  通信インタフェース  ２５  アンテナ
【発明を実施するための最良の形態】
【００３３】  以下、本発明の好ましい実施の形態を、図面を参照しながら説明する。【００３４】  （実施の形態１）  図１は、本発明の実施の形態１に係る無線タグ及び暗号鍵生成装置を備える無線タグシステムの構成を示すブロック図である。【００３５】  図１に示すように、無線タグシステムは、無線タグ１と、その無線タグ１と非接触で通信可能な暗号鍵生成装置２とを備えている。本実施の形態において、暗号鍵生成装置２は、無線タグ１によって送信された暗号文を復号する復号装置として機能する。そのため、以下では、暗号鍵生成装置２を復号装置２と称する。【００３６】  無線タグ１は、制御回路１１、メモリ回路１２、暗号演算回路１３、情報の送受信装置である無線回路１４及びアンテナ１５、並びに電源部１６を備えている。制御回路１１は、メモリ回路１２、暗号演算回路１３、及び無線回路１４と接続されており、また、無線回路１４は更に、復号装置２と通信するためのアンテナ１５及び電源部１６と接続されている。【００３７】  ここで、メモリ回路１２は、制御回路１１が処理する各種のデータを記憶するための回路である。【００３８】  また、暗号演算回路１３は、後述する処理を実行することによって、暗号鍵を生成し、その生成した暗号鍵を用いて、平文に対する暗号化処理を行う回路である。その暗号化処理の結果として生成された暗号文は、暗号演算回路１３から制御回路１１に対して出力される。【００３９】  図１に示すとおり、暗号演算回路は、乱数Ｒを発生する乱数発生回路１０１と、乱数Ｒ及び共通鍵Ｋを用いて後述する第１関数を実行する第１関数回路１０２と、後述する第２関数を実行する第２関数回路１０３と、生成された暗号鍵を用いて平文Ｐから暗号文への暗号化処理を行う暗号化回路とを備えている。ここで、乱数回路１０１、第１関数回路１０２、第２関数回路１０３、及び暗号化回路１０４は、論理回路であり、複数の論理素子の組合せにより構成される。【００４０】  無線回路１４は、アンテナ１５で受信した無線信号を復調してデジタル信号を生成し、そのデジタル信号を制御回路１１に対して出力する。また、制御回路１１の命令にしたがって、送信すべきデジタル信号を変調して無線信号を生成し、アンテナ１５を介してその無線信号を外部へ送信する。【００４１】  電源部１６は、無線回路１４から無線信号を取得し、その無線信号を電源電圧に変換する。これにより、電源部１６は、無線タグ１の内部を動作させるために必要な電力を得る。【００４２】  なお、本実施の形態では、暗号化処理を行うための専用の回路である暗号演算回路が設けられているが、これに限定されるわけではなく、例えば制御回路が暗号演算回路を兼ねるような構成であってもよい。また、暗号演算回路のようにチップ化されているのではなく、後述する暗号化処理をソフトウェアで実行するような構成であってもよい。【００４３】  また、復号装置２は、演算装置であるＣＰＵ２１、メモリ部２２、通信インタフェース（Ｉ／Ｆ）２４、及びアンテナ２５を備えている。ＣＰＵ２１は、メモリ部２２及び通信Ｉ／Ｆ２４と接続されており、また、通信Ｉ／Ｆ２４は更に、無線タグ１と通信するためのアンテナ２５と接続されている。【００４４】  ここ���、メモリ部２２は、ＣＰＵ２１が処理する各種のデータを記憶するものである。なお、図示しているように、メモリ部２２には、後述する復号処理を実現する暗号処理プログラム２３が記憶されている。この暗号処理プログラム２３は、後述する復号処理をコンピュータに行わせる手順から構成されるコンピュータプログラムである。【００４５】  暗号処理プログラム２３は、乱数Ｒを発生する乱数発生ルーチン２０１と、乱数Ｒおよび共通鍵Ｋを用いて後述する第１関数を実行する第１関数実行ルーチン２０２と、後述する第２関数を実行する第２関数実行ルーチン２０３と、生成された暗号鍵を用いて暗号文Ｃから平文Ｐへの復号処理を実行する復号処理実行ルーチン２０４とを有している。【００４６】  次に、以上のように構成された無線タグ１及び復号装置２の動作について説明する。【００４７】  ［暗号化処理］  無線タグ１が備える制御回路１１は、メモリ回路１２に記憶されている平文Ｐを適宜のタイミングで取得し、その取得した平文Ｐを暗号演算回路１３へ出力する。この平文Ｐを受け取った暗号演算回路１３は、次のようにして、暗号鍵の生成及びその暗号鍵による平文Ｐの暗号化を含む暗号化処理を実行し、暗号文Ｃを生成する。【００４８】  図２は、暗号文の生成に伴う、暗号演算回路１３の処理手順を示すフローチャートである。【００４９】  図２に示すとおり、暗号演算回路１３は、予め用意しておいたデータ配列Ｓ（−１）に共通鍵Ｋを、Ｓ（０）に乱数Ｒをそれぞれ代入する（Ｓ１０１）。なお、無線タグ１及び復号装置２は、同一の共通鍵Ｋを所定の手順にしたがって予め取得し、記憶しているものとする。また、乱数Ｒは、暗号演算回路１３が備える乱数発生回路１０１によって生成される。【００５０】  次に、暗号演算回路１３は、変数ｊに１を代入する（Ｓ１０２）。そして、暗号演算回路１３は、Ｓ（ｊ）に対して、第１関数Ｆ１［Ｓ（ｊ−２），Ｓ（ｊ−１）］を代入する（Ｓ１０３）。以下、この第１関数Ｆ１について説明する。【００５１】  本発明において、第１関数Ｆ１とは、引数として与えられたディジット列のうち、特定の位置にある複数のディジット同士を加算し、その結果を出力するものである。本実施の形態において、具体的には、以下の式にしたがって演算がなされる。【００５２】  Ｘ＝｛ｘ（１），ｘ（２），…，ｘ（ｉ），…，ｘ（ｎ）｝  Ｙ＝｛ｙ（１），ｙ（２），…，ｙ（ｉ），…，ｙ（ｎ）｝  Ｚ＝Ｆ１［Ｘ，Ｙ］＝Ｘ（Ｙ）            ＝｛ｚ（１），ｚ（２），…，ｚ（ｉ），…，ｚ（ｎ）｝  ここで、ｉが１からｎ（ｎは、平文のブロック長）になるまで、次の式１を適用することによって、ｚ（ｉ）が得られる。【００５３】  ｚ（ｉ）  ＝｛ｘ（ｉ）＋ｘ［（ｉ＋ｙ（ｉ））（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）  …式１  なお、この式１は、ディジット列であるＸ，Ｙ及びＺをｒ進法で表す場合のものである。【００５４】  このように、本実施の形態では、ディジット列Ｙにおける特定のディジットにより、ディジット列Ｘのうちの特定の組の２つのディジットが決定されることになる。そして、その２つのディジットに対して加算処理を施すことによって、ディジット列Ｚが生成される  ことになる。【００５５】  なお、本実施の形��では、上記のとおり、ディジット列Ｘのうちの特定の組の２つのディジットに対して加算処理を実行しているが、本発明はこれに限定されるわけではなく、ディジット列Ｘのうちの特定の組の３つ以上のディジットに対して加算処理を実行するようにしてもよい。【００５６】  以上の第１関数Ｆ１は、暗号演算回路１３が備える第１関数回路１０２により実行される。【００５７】  次に、暗号演算回路１３は、ステップＳ１０３を実行した結果得られたＳ（ｊ）と、ディジット列における特定の位置を示すＳＶとを引数とした第２関数Ｆ２［Ｓ（ｊ）；ＳＶ］の出力を、ｋ（ｊ）に代入する（Ｓ１０４）。以下、この第２関数Ｆ２について説明する。【００５８】  第２関数Ｆ２とは、引数Ｓ（ｊ）として与えられたディジット列を、引数ＳＶで示す位置で２つのディジット列に分け、それらのディジット列同士を加算し、その結果を出力するものである。本実施の形態においては、具体的に、以下の式にしたがって演算がなされる。【００５９】  Ｓ＝｛ｓ（１），ｓ（２），…，ｓ（ｉ），…，ｓ（ｎ）｝  Ｔ＝Ｆ２［Ｓ；ｎ／２］        ＝｛ｔ（１），ｔ（２），…，ｔ（ｉ），…，ｔ（ｎ／２）｝  ここで、ｊが１からｎ／２になるまで、次の式２を適用することによって、ｔ（ｉ）が得られる。【００６０】  ｔ（ｉ）＝｛ｓ（ｉ）＋ｓ（ｉ＋ｎ／２）｝（ｍｏｄｒ）  …式２  なお、本実施の形態では、引数Ｓ（ｊ）として与えられたディジット列を、ｎ／２の位置で２つのディジット列に分けているが、それ以外の位置で２つのディジット列に分けるようにしてもよい。【００６１】  また、本実施の形態では、引数Ｓ（ｊ）として与えられたディジット列を２つのディジット列に分けているが、本発明はこれに限定されるわけではなく、当該ディジット列を３つ以上のディジット列に分けるようにしてもよい。この場合、ＳＶが２つ以上の位置を示すようにすればよい。【００６２】  以上の第２関数Ｆ２は、暗号演算回路１３が備える第２関数回路１０３により実行される。【００６３】  このようにして第２関数Ｆ２を実行した場合の出力がｋ（ｊ）に代入される。後述するように、このｋ（ｊ）が、暗号鍵として機能することになる。すなわち、上述した内容の第１関数Ｆ１及び第２関数Ｆ２を実行することによって、暗号鍵ｋ（ｊ）が生成されることになる。【００６４】  次に、暗号演算回路１３は、暗号文の生成を行う。具体的には、Ｐ（ｊ）とｋ（ｊ）とのビット毎のｍｏｄ２加算、すなわちＰ（ｊ）とｋ（ｊ）との排他的論理和を算出し、それをＣ（ｊ）に代入する（Ｓ１０５）。【００６５】  このように、＋を円で囲った記号は、ｍｏｄ２での加算（排他的論理和）を意味している。また、Ｐ（ｊ）は平文のｊ番目のブロックを、Ｃ（ｊ）は暗号文Ｃのｊ番目のブロックをそれぞれ意味している。【００６６】  以上の暗号文Ｃの生成は、暗号演算回路１３が備える暗号化回路１０４により実行される。【００６７】  次に、暗号演算回路１３は、ｊがＮ（Ｎは、平文のブロック数）より大であるか否かを判定する（Ｓ１０６）。ここで、ｊがＮ以上であると判定した場合（Ｓ１０６でＹＥＳ）、暗号演算回路１３は、処理を終了する。【００６８】  他方、ステップＳ１０６にてｊがＮ以下であると��定した場合（Ｓ１０６でＮＯ）、暗号演算回路１３は、Ｓ（ｊ−２）にＳ（ｊ−１）を、Ｓ（ｊ−１）にＳ（ｊ）をそれぞれ代入し（Ｓ１０７）、ｊを１だけインクリメントする（Ｓ１０８）。【００６９】  その後、暗号演算回路１３は、ステップＳ１０６においてｊがＮより大と判定されるまで、ステップＳ１０３からＳ１０８までを繰り返し実行する。【００７０】  以上の処理を実行した結果、暗号文Ｃが生成される。なお、この暗号文Ｃには、予め算出された、共通鍵Ｋと乱数Ｒとの排他的論理和であるＣ（０）が含まれている。このようにして生成された暗号文Ｃは、無線タグ１から復号装置２に対して適宜のタイミングで送信される。【００７１】  上記から、第１関数回路１０２および第２関数回路１０３は、多値の非線形シフトレジスタの構成要素であること、また、これらの回路によって、暗号鍵の系列の系列が生成されていることが理解できる。【００７２】  このようにして暗号文Ｃを受信した復号装置２は、次の復号処理を実行する。【００７３】  ［復号処理］  図３は、復号処理に伴う、復号装置２の処理手順を示すフローチャートである。この図３と図２とを比較すれば分かるように、復号処理と暗号化処理とにおいて、暗号鍵を生成する処理は同一である。そのため、ステップＳ２０５を除くＳ２０１からＳ２０８までは、図２におけるステップＳ１０５を除くＳ１０１からＳ１０８までとそれぞれ同様である。ただし、ステップＳ２０１において、乱数Ｒが、Ｃ（０）とＫとの排他的論理和により得られる点については、復号処理と暗号化処理とで異なる。【００７４】  なお、ステップＳ２０３における第１関数の実行は第１関数実行ルーチン２０２によって、ステップＳ２０４における第２関数の実行は第２関数実行ルーチン２０３によって、それぞれなされる。【００７５】  以下では、ステップＳ２０５を除くＳ２０１からＳ２０８についての説明は省略し、ステップＳ２０５の処理についてのみ説明する。【００７６】  ステップＳ２０５において、復号装置２は、無線タグ１から受け取ったＣ（ｊ）とステップＳ２０４で得られたｋ（ｊ）とのｍｏｄ２加算、すなわちＣ（ｊ）とｋ（ｊ）との排他的論理和を算出する。そして、その結果得られた値をＰ（ｊ）に代入する。このように、暗号鍵ｋ（ｊ）を用いることによって、暗号文のｊブロック目であるＣ（ｊ）から平文のｊブロック目であるＰ（ｊ）が得られることになる。【００７７】  復号装置２は、ステップＳ２０６においてｊがＮより大と判定されるまで、ステップＳ２０３からＳ２０８までを繰り返し実行する。その結果、復号処理が完了し、平文Ｐが得られる。【００７８】  この復号処理は、復号処理実行ルーチン２０４によって実行される。【００７９】  次に、具体的に平文をデータとして与え、具体的な処理結果を参照しながら、上記の暗号化処理及び復号処理について説明する。なお、以下の例は、ディジット列を１６進数で表すものである。【００８０】  ［暗号化処理］  無線タグ１が備える暗号演算回路１３は、乱数Ｒとして、ディジット列２３７３９０を生成したものとする。また、共通鍵Ｋとして、ディジット列３０２４５８を記憶しているものとする。この場合、Ｃ（０）は、共通鍵Ｋ＝３０２４５���＝（００１１  ００００  ００１０  ０１００  ０１０１  １０００）と乱数Ｒ＝２３７３９０＝（００１０  ００１１  ０１１１  ００１１  １００１  ００００）との排他的論理和である１３５７Ｃ８＝（０００１  ００１１  ０１０１  ０１１１  １１００  １０００）となる。【００８１】  また、暗号演算回路１３には、平文Ｐとして、以下の値が記憶されているものとする。【００８２】  Ｐ＝｛Ｐ（１）＝５ＣＡ＝（０１１０  １１００  １０１０）        Ｐ（２）＝２０Ｆ＝（００１０  ００００  １１１１）        Ｐ（３）＝２Ａ３＝（００１０  １０１０  ００１１）        Ｐ（４）＝…………        Ｐ（５）＝………        ……………  ……                                ｝  まず、暗号演算回路１３は、Ｋ，ＲをＳ（−１），Ｓ（０）へ代入し、ｊ＝１とした後、上述したステップＳ１０３のとおり、第１関数Ｆ１を用いて、Ｓ（１）を算出する。具体的には、Ｆ１［Ｓ（−１），Ｓ（０）］、すなわちＦ１［３０２４５８，２３７３９０］を実行する。この場合のｚ（１）からｚ（６）までの値は以下のようにして求められる。【００８３】  ｚ（１）＝｛ｘ（１）＋ｘ［１＋ｙ（１）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）            ＝｛３＋ｘ［（１＋２）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）            ＝｛３＋ｘ（４）｝（ｍｏｄ１６）＝｛３＋４｝（ｍｏｄ１６）＝７  ｚ（２）＝｛ｘ（２）＋ｘ［２＋ｙ（２）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）            ＝｛０＋ｘ［（２＋３）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）            ＝｛０＋ｘ（６）｝（ｍｏｄ１６）＝｛０＋８｝（ｍｏｄ１６）＝８  ｚ（３）＝｛ｘ（３）＋ｘ［１＋ｙ（３）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）            ＝｛２＋ｘ［（３＋７）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）            ＝｛２＋ｘ（５）｝（ｍｏｄ１６）＝｛２＋５｝（ｍｏｄ１６）＝７  ｚ（４）＝｛ｘ（４）＋ｘ［４＋ｙ（４）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）            ＝｛４＋ｘ［（４＋３）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）            ＝｛４＋ｘ（２）｝（ｍｏｄ１６）＝｛４＋０｝（ｍｏｄ１６）＝４  ｚ（５）＝｛ｘ（５）＋ｘ［１＋ｙ（５）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）            ＝｛５＋ｘ［（５＋９）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）            ＝｛５＋ｘ（３）｝（ｍｏｄ１６）＝｛５＋２｝（ｍｏｄ１６）＝７  ｚ（６）＝｛ｘ（６）＋ｘ［１＋ｙ（６）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）            ＝｛８＋ｘ［（６＋０）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）            ＝｛８＋ｘ（１）｝（ｍｏｄ１６）＝｛８＋３｝（ｍｏｄ１６）＝Ｂ  以上より、Ｓ（１）の値が求まる。次に、暗号演算回路１３は、上述したステップＳ１０４のとおり、第２関数Ｆ２を用いて、暗号鍵ｋ（１）を算出する。具体的には、Ｆ２［Ｓ（１）；ｎ／２］、すなわちＦ２［７８７４７Ｂ；３］を実行する。この演算は次のとおりとなる。【００８４】  ｋ（１）＝Ｆ２［７８７４７Ｂ；３］＝７８７＋４７Ｂ          ＝ＢＦ２＝（１０１１  １１１１  ００１０）  次に、暗号演算回路１３は、上述したステップＳ１０５のとおり、Ｐ（１）とｋ（１）との排他的論理和をとることによってＣ（１）を生成する。すなわち、（０１１０  １１００  １０１０）と（１０１１  １１１１  ００１０）との排他的論理和である（１１０１  ００１１  １０００）をＣ（１）とする。【００８５】  また、暗号演算回路１３は、Ｓ（２）及びｋ（２）を次のとおり算出する。【００８６】  Ｓ（２）＝Ｆ１［Ｓ（０），Ｓ（１）］＝Ｆ１［２３７３９０，７８７４７Ｂ］    ＝９Ｃ０ＡＢ０＝（１００１  １１００  ００００  １０１０  １０１１  ００００）  ｋ（２）＝Ｆ２［Ｓ（２）；３］＝Ｆ２［９Ｃ０ＡＢ０；３］＝９ＣＤ＋ＡＢ０            ＝３７０＝（００１１  ０１１１  ００００）  その結果、Ｃ（２）として、Ｐ（２）とｋ（２）との排他的論理和である（０００１  ０１１１  １１１１）が得られる。【００８７】  さらに、暗号演算回路１３は、Ｓ（３）及びｋ（３）を次のとおり算出する。【００８８】  Ｓ（３）＝Ｆ１［Ｓ（１），Ｓ（２）］＝Ｆ１［７８７４７Ｂ，９Ｃ０ＡＢ０］    ＝ＥＦＢＢＥ２＝（１１１０  １１１１  １０１１  １０１１  １１１０  ００１０）  ｋ（３）＝Ｆ２［Ｓ（３）；３］＝Ｆ２［ＥＦＢＢＥ２；３］＝ＥＦＢ＋ＢＥ２            ＝９ＤＤ＝（１０１１  ０１１１  １１１０）  その結果、Ｃ（３）として、これらＳ（３）とｋ（３）との排他的論理和である（１０１１  ０１１１  １１１０）が得られる。【００８９】  暗号演算回路１３は、以上の処理を、ｊの値が平文のブロック数Ｎに達するまで繰り返し実行する。その結果、次のとおりの暗号文Ｃを得ることができる。【００９０】    Ｃ＝｛Ｃ（０）＝（０００１  ００１１  ０１０１  ０１１１  １１００  １０００）        Ｃ（１）＝（１１０１  ００１１  １０００）        Ｃ（２）＝（０００１  ０１１１  １１１１）        Ｃ（３）＝（１０１１  ０１１１  １１１０）        Ｃ（４）＝…………        Ｃ（５）＝………        …………  ……                            ｝  ［復号処理］  復号装置２は、無線タグ１から暗号文Ｃを受信した場合、そのうちのＣ（０）と共通鍵Ｋとの排他的論理和を算出し、これを乱数Ｒとする。そのため、この例では、（００１０  ００１１  ０１１１  ００１１  １００１  ００００）＝２３７３９０を乱数Ｒとする。【００９１】  まず、復号装置２は、Ｋ，ＲをＳ（−１），Ｓ（０）へそれぞれ代入し、ｉ＝１とした後、上述したステップＳ２０３のとおり、第１関数Ｆ１を用いて、Ｓ（１）を算出する。具体的には、Ｆ１［Ｓ（−１），Ｓ（０）］、すなわちＦ１［３０２４５８，２３７３９０］を実行する。これは、上述した暗号化処理の場合と同様であるので、Ｓ（１）＝７８７４７Ｂ＝（０１１１  １０００  ０１１１  ０１００  ０１１１  １０１１）となり、ｋ（１）＝Ｆ２［７８７４７Ｂ；３］＝ＢＦ２＝（００１１  ０１１１  ００００）となる。【００９２】  次に、復号装置２は、上述したステップＳ２０５のとおり、Ｃ（１）とｋ（１）との排他的論理和をとることによってＰ（１）を生成する。すなわち、（１１０１  ００１１  １０００）と（１０１１  １１１１  ００１０）との排他的論理和である（０１１０  １１００  １０１０）をＰ（１）とする。【００９３】  また、復号装置２は、Ｓ（２）及びｋ（２）を、上述した暗号化処理の場合と同様にして算出し、Ｓ（２）＝（１００１  １１００  ００００  １０１０  １０１１  ００００）及びｋ（２）＝（００１１  ０１１１  ００００）を得る。【００９４】  その結果、Ｐ（２）として、Ｃ（２）とｋ（２）との排他的論理和である（００１０  ００００  １１１１）が得られる。【００９５】  さらに、復号装置２は、Ｓ（３）及びｋ（３）を、上述した暗号化処理の場合と同様にして算出し、Ｓ（３）＝（１１１０  １１１１  １０１１  １０１１  １１１０  ００１０）及びｋ（３）＝（１００１  １１０１  １１０１）を得る。【００９６】  その結果、Ｐ（３）として、Ｃ（３）とｋ（３）との排他的論理和である（００１０  １０１０  ００１１）が得られる。【００９７】  復号装置２は、以上の処理を、ｉの値が暗号文のブロック数ｎに達するまで繰り返し実行する。その結果、次のとおりの平文Ｐを得ることができる。【００９８】  Ｐ＝｛Ｐ（１）＝５ＣＡ＝（０１１０  １１００  １０１０）        Ｐ（２）＝２０Ｆ＝（００１０  ００００  １１１１）        Ｐ（３）＝２Ａ３＝（００１０  １０１０  ００１１）        Ｐ（４）…………        Ｐ（５）………        …………  ……                            ｝  以上のようにして得られた平文Ｐは、無線タグ１によって暗号化処理が施される前の平文Ｐと同一のものであることが確認できる。【００９９】  以上のように暗号化及び復号を実施することにより、簡易な処理で強固なセキュリティが確保された無線タグシステムを実現することができる。【０１００】  ［安全性について］  以下、従来の共通鍵暗号系と比較して計算量が少ない本発明の暗号鍵生成方法であっても、十分なセキュリティを確保することができる点について説明する。【０１０１】  一般に、「暗号系を破る」とは、長さｎディジットの鍵Ｋが露呈するということを意味する。ここで、鍵Ｋが露呈するためには、連続する２つのＳｊの値（２つのレジスタの数値）が露呈される必要がある。【０１０２】  選択平文攻撃（Ｃｈｏｓｅｎ  ｐｌａｉｎｔｅｘｔ  ａｔｔａｃｋ）または選択暗号文攻撃（Ｃｈｏｓｅｎ  ｃｉｐｈｅｒｔｅｘｔ  ａｔｔａｃｋ）などを用いて、鍵の系列ｋ（ｊ）（１≦ｊ≦ｔ）を入手することができたとしても、ｋ（ｊ）系列は無相関の乱数系列であるため、ｋ（ｊ）（ｊ＞ｔ）を推定することは不可能である。【０１０３】  また、ｋ（ｊ）（１≦ｊ≦ｔ）によってＳ（ｊ）及びＳ（ｊ＋１）を算出するためには、（１／２）ｒｎ＝２ｍｎ−１＝２ａ−１（但し、ｒ＝２ｍ）の計算量が必要となる。この値をＣｏｍｐ＝（１／２）ｅｘｐ［（ｌ２）・ａ］と表現したものを計算量的複雑さ（Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｃｏｍｐｌｅｘｉｔｙ）と一般的に定義されている。【０１０４】  以上より、「暗号系を破る」ための計算量的複雑さは、Ｃｏｍｐ＝（１／２）ｅｘｐ［（ｌｎ２）・ａ］であり、この計算量的複雑さによって、暗号系のセキュリティレベルが証明される。したがって、ａ＝ｍｎの大きさを大きくすればするほど、暗号系のセキュリティレベルは、指数関数的に高められることになる。【０１０５】  以上をまとめると、「暗号系を破る」ために必要な計算量的複雑さを導出することにより、（計算量的）安全性を証明することができ、適用する数値のサイズａ＝ｍｎ（換言するとレジスタのサイズａ＝ｍｎ）を大きく設定することにより、十分なセキュリティを確���できることになる。【０１０６】  したがって、本発明のように、加算のみで暗号鍵を生成したとしても、ａ＝ｍｎの値を十分に大きくすることによって、十分なセキュリティを確保することが可能となる。【０１０７】  ［速度比較テスト］  上述した本実施の形態における暗号化処理及び復号処理を実行した場合の処理に要する時間（処理時間）と、従来の共通鍵暗号系であるＤＥＳを用いた暗号化処理及び復号処理を実行した場合の処理時間とを比較するテストを実行した。以下では、本実施の形態における処理を実施例と称し、ＤＥＳを用いた場合における処理を比較例と称する。【０１０８】  このテストにおいては、米インテル社製のＣｅｌｅｒｏｎ（登録商標）Ｍプロセッサ（動作周波数１．４０ＧＨｚ）及び５０４ＭＢのＲＡＭを備えたパーソナルコンピュータ（ＰＣ）を用いて行った。このＰＣには、オペレーティングシステムとして、米マイクロソフト社のＷｉｎｄｏｗｓＸＰ（登録商標）のＨｏｍｅＥｄｉｔｉｏｎ，Ｖｅｒｓｉｏｎ２００２，ＳｅｒｖｉｃｅＰａｃｋ２がインストールされていた。また、本実施の形態における暗号化処理及び復号処理並びにＤＥＳを用いた暗号化処理及び復号処理は、ＦＯＲＴＲＡＮ７７を用いて作成されたコンピュータプログラムにより実行された。【０１０９】  このテストにおける４つの条件を以下の表１にまとめた。なお、この表１において、「比較例鍵」とはＤＥＳにおける共通鍵を示し、「実施例鍵」とは本実施の形態における共通鍵を示している。【０１１０】
【表１】
2008072351.tif 000003
表１に挙げられている４つの条件についてのテスト結果を表２にまとめた。なお、表２に示されているように、各条件について２回のテストを行っている。また、各テストにおいて、１００，０００，０００回のループ処理を行っている。
【０１１１】
【表２】
2008072351.tif 000004
表２に示すように、条件１乃至４のすべての場合において、本実施例の方が比較例よりも早く処理を行うことができた。具体的には、本実施例では、比較例の場合と比べて、１０．８９倍〜１２．２０倍早く処理を行うことができた。
【０１１２】  上記の結果から、本実施例の場合では、計算量が少なく、したがって、比較例の場合と比べて処理時間も短くなることを確認することができる。【０１１３】  なお、本実施の形態では、無線タグを構成する暗号演算回路が、第１関数及び第２関数を用いることによって暗号鍵を生成し、その生成した暗号鍵によって暗号化処理を実行しているが、暗号演算回路は、このように暗号化処理を行う暗号化装置への適用に限られるわけではない。したがって、例えば、暗号演算回路が、本実施の形態における暗号化回路に代わって、または、その暗号化回路とともに、本実施の形態における復号装置が実行するような復号処理を行う論理回路である復号回路を備えることによって、復号装置として機能するようにしてもよい。【０１１４】  （実施の形態２）  実施の形態１は、無線タグと復号装置とから構成される無線タグシステムであった。これに対し、実施の形態２は、インターネットなどの通信ネットワークを介して接続される複数のコンピュータ端末から構成されるコンピュータシステムである。【０１１５】  図４は、本発明の実施の形態２に係る暗号鍵生成装置を備えるコンピュータシステムの構成を示すブロック図である。【０１１６】  図４に示すように、コンピュータシステムは、暗号鍵生成装置３と、その暗号鍵生成装置３と通信ネットワーク５を介して通信可能に接続された暗号鍵生成装置４とを備えている。【０１１７】  ここで、暗号鍵生成装置３は、暗号化処理を実行する暗号化装置として機能し、他方、暗号鍵生成装置４は、復号処理を実行する復号装置として機能する。そのため、以下では、暗号鍵生成装置３を暗号化装置３と称し、暗号鍵生成装置４を復号装置４と称する。【０１１８】  暗号化装置３は、ＣＰＵ３１、メモリ部３２、及び通信インタフェース（Ｉ／Ｆ）３４を備えている。ＣＰＵ３１は、メモリ部３２及び通信Ｉ／Ｆ３４と接続されており、これらのハードウェアを制御する。【０１１９】  メモリ部３２は、ＣＰＵ３１が処理する各種のデータを記憶するものである。なお、図示されているように、メモリ部３２には、暗号化処理を実現する暗号処理プログラム３３が記憶されている。この暗号処理プログラム３３は、実施の形態１における暗号演算回路１３が実施する暗号化処理をコンピュータに行わせる手順から構成されるコンピュータプログラムである。【０１２０】  暗号処理プログラム３３は、乱数Ｒを発生する乱数発生ルーチン３０１と、乱数Ｒ及び共通鍵Ｋを用いて第１関数を実行する第１関数実行ルーチン３０２と、第２関数を実行する第２関数実行ルーチン３０３と、生成された暗号鍵を用いて平文Ｐから暗号文Ｃへの暗号化処理を実行する暗号化処理実行ルーチン３０４とを有している。【０１２１】  また、復号装置４は、暗号化装置３と同様に、ＣＰＵ４１、メモリ部４２、及び通信Ｉ／Ｆ４４を備えている。そして、メモリ部４２には、復号処理を実現する暗号処理プログラム４３が記憶されている。この暗号処理プログラム４３は、実施の形態１における復号装置２が実施する復号処理をコンピュータに行わせる手順から構成されるコンピュータプログラムである。【０１２２】  暗号処理プログラム４３は、乱数Ｒを発生する乱数発生ルーチン４０１と、乱数Ｒおよび共通鍵Ｋを用いて第１関数を実行する第１関数実行ルーチン４０２と、第２関数を実行する第２関数実行ルーチン４０３と、生成された暗号鍵を用いて暗号文Ｃから平文Ｐへの復号処理を実行する復号処理実行ルーチン４０４とを有している。【０１２３】  以上のように構成されたコンピュータシステムにおいて、暗号化装置３は、暗号処理プログラム３３を実行することによって、実施の形態１における無線タグ１と同様にして暗号鍵を生成し、暗号文を生成する。その結果、生成された暗号文は、通信ネットワーク５を介して、暗号化装置３から復号装置４へ送信される。【０１２４】  復号装置４は、暗号化装置３から暗号文を受信した場合、暗号処理プログラム４３を実行することによって、実施の形態１における復号装置２と同様にして暗号鍵を生成し、復号を行う。【０１２５】  このように、暗号処理プログラム３３及び暗号処理プログラム４３を用いることによって、コンピュータ端末が本発明の暗号鍵生成装置として機能することになる。【０１２６】  これにより、簡易な処理で強固なセキュリティが確保されたコンピュータシステムを実現することができる。【０１２７】  なお、本実施の形態では、暗号処理プログラムを有するコンピュータ端末によりコンピュータシステムが構成されているが、例えば、実施の形態１における暗号演算回路を備えたコンピュータ端末によりコンピュータシステムが構成されていてもよい。【０１２８】  上記説明から、当業者にとっては、本発明の多くの改良や他の実施形態が明らかである。従って、上記説明は、例示としてのみ解釈されるべきであり、本発明を実行する最良の態様を当業者に教示する目的で提供されたものである。本発明の精神を逸脱することなく、その構造及び／又は機能の詳細を実質的に変更できる。
【産業上の利用可能性】
【０１２９】  本発明に係る暗号鍵生成方法、暗号鍵生成装置、暗号演算回路、無線タグ、及びコンピュータプログラムは、少ない計算量でセキュリティを確保することが可能であるため、微少な電力及び回路規模に限られるという制約を有する無線タグを備える無線タグシステム、並びに各種のコンピュータシステム等において暗号化処理及び復号処理を行う場合に有用である。
【図１】
2008072351.tif 000005
【図２】
2008072351.tif 000006
【図３】
2008072351.tif 000007
【図４】
2008072351.tif 000008
【手続補正書】
【提出日】平成19年6月6日(2007.6.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成方法において、
第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する工程（ａ）と、
生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する工程（ｂ）とを有し、
前記工程（ａ）及び（ｂ）は、前記文のブロック毎に実行され、
後行する前記工程（ａ）における第１のディジット列は、先行する前記工程（ａ）により生成された第２のディジット列であり、
後行する前記工程（ａ）における特定の組の複数のディジットは、先行する前記工程（ａ）により生成された第２のディジット列における特定のディジットに基づいて決定されることを特徴とする、暗号鍵生成方法。
【請求項２】
前記後行する前記工程（ａ）における第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記先行する前記工程（ａ）により生成された第２のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］として、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記後行する前記工程（ａ）において生成される第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）は、次の式により求められる、請求項１に記載の暗号鍵生成方法。
ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）
【請求項３】
複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、
第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列の生成処理を実行する第２のディジット列生成手段と、
生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列の生成処理を実行する第３のディジット列生成手段とを備え、
前記第２のディジット列生成手段及び前記第３のディジット列生成手段は、前記文のブロック毎に、前記第２のディジット列及び前記第３のディジット列の生成処理をそれぞれ実行するように構成されており、
後行する前記第２のディジット列生成手段による第２のディジット列の生成処理における第１のディジット列は、先行する前記第２のディジット列生成手段による第２のディジット列の生成処理により生成された第２のディジット列であり、
後行する前記第２のディジット列生成手段による第２のディジット列の生成処理における特定の組の複数のディジットは、先行する前記第２のディジット列生成手段による第２のディジット列の生成処理により生成された第２のディジット列における特定のディジットに基づいて決定されることを特徴とする、暗号鍵生成装置。
【請求項４】
複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、
所定の演算処理を実行する演算装置と、
第１のディジット列を記憶するメモリとを備え、
前記演算装置は、前記メモリから前記第１のディジット列を読み出し、その読み出した第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する第２のディジット列生成処理と、
生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する第３のディジット列生成処理とを、前記文のブロック毎に実行するように構成されており、
後行する前記第２のディジット列生成処理における第１のディジット列は、先行する前記第２のディジット列生成処理により生成された第２のディジット列であり、
後行する前記第２のディジット列生成処理における特定の組の複数のディジットは、先行する前記第２のディジット列生成処理により生成された第２のディジット列における特定のディジットに基づいて決定されることを特徴とする、暗号鍵生成装置。
【請求項５】
複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号演算回路において、
第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列の生成処理を実行する第１関数回路と、
生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列の生成処理を実行する第２関数回路とを備え、
前記第１関数回路及び前記第２関数回路は、前記文のブロック毎に、前記第２のディジット列及び前記第３のディジット列の生成処理をそれぞれ実行するように構成されており、
後行する前記第１関数回路による第２のディジット列の生成処理における第１のディジット列は、先行する前記第１関数回路による第２のディジット列の生成処理により生成された第２のディジット列であり、
後行する前記第１関数回路による第２のディジット列の生成処理における特定の組の複数のディジットは、先行する前記第１関数回路による第２のディジット列の生成処理により生成された第２のディジット列における特定のディジットに基づいて決定されることを特徴とする、暗号演算回路。
【請求項６】
前記第２関数回路によって生成された第３のディジット列を用いて、外部から入力された平文に対する暗号化処理を実行する暗号化回路をさらに備える、請求項５に記載の暗号演算回路。
【請求項７】
前記第１のディジット列は、共通鍵である、請求項５又は６に記載の暗号演算回路。
【請求項８】
前記後行する前記第１関数回路による第２のディジット列の生成処理における第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記先行する前記第１関数回路による第２のディジット列の生成処理により生成された第２のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第１関数回路は、前記後行する前記第１関数回路による第２のディジット列の生成処理において生成される第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）を、次の式により求めるように構成されている、請求項５乃至請求項７の何れかに記載の暗号演算回路。
ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）
【請求項９】
外部の通信装置と非接触で通信可能な無線タグにおいて、
請求項５乃至８の何れかに記載の暗号演算回路と、
当該暗号演算回路により生成された暗号鍵を用いて生成された暗号文を、前記通信装置に対して送信する送信装置とを備えることを特徴とする、無線タグ。
【請求項１０】
コンピュータに、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵の生成を行わせるためのコンピュータプログラムにおいて、
前記コンピュータに、
所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施させることによって、第２のディジット列を生成させる手順（ａ）と、
生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することにより得られる第３のディジット列である暗号鍵を生成させる手順（ｂ）とを、前記文のブロック毎に実行させ、
後行する前記手順（ａ）における第１のディジット列は、先行する前記手順（ａ）により生成された第２のディジット列であり、
後行する前記手順（ａ）における特定の組の複数のディジットは、先行する前記手順（ａ）により生成された第２のディジット列における特定のディジットに基づいて決定されることを特徴とする、コンピュータプログラム。
【請求項１１】
前記後行する前記手順（ａ）における第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記先行する前記手順（ａ）により生成された第２のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］として、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記後行する前記手順（ａ）において生成される第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）は、次の式により求められる、請求項１０に記載のコンピュータプログラム。
ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）  
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号システムにおける暗号鍵を生成する暗号鍵生成方法に関し、特に少ない計算量で高度なセキュリティが確保された暗号鍵を生成する暗号鍵生成方法、その方法を実施するための暗号鍵生成装置及び暗号演算回路、その暗号演算回路を備える無線タグ、並びに前記方法をコンピュータに実施させるためのコンピュータプログラムに関する。
【背景技術】
【０００２】
近年、高度情報化社会の発展に伴い、情報の盗取など多くの問題が発生している。その結果、それらの問題の発生を未然に防止するために、情報を暗号化することによってセキュリティを確保する技術が要求されている。
【０００３】
現在、広く普及している暗号技術として、共通鍵暗号であるＤＥＳ（Data Encryption Standard）、及びＤＥＳと比べてより暗号強度の高いＡＥＳ（Advanced Encryption Standard）が挙げられる。
【０００４】
また、これらのＤＥＳ及びＡＥＳ以外にも、数多くの共通鍵暗号系が提案されている。そのうちの一つに、２ｆａｃｔｏｒ暗号システムと呼ばれるものがある。この２ｆａｃｔｏｒ暗号システムでは、ＰＤＡＦ（Position Digit Algebra Function）及びＯＷＣ（One-Way Cut function）の２つの関数を用いて、共通鍵の管理等を行う方法が提案されている（例えば、特許文献１および特許文献２を参照。）
【特許文献１】米国特許出願公開第２００３／０１４９８７６号明細書
【特許文献２】米国特許出願公開第２００６／０３４４５６号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、近年では、微少な無線チップを搭載した無線タグ（ＲＦＩＤ（Radio Frequency IDentification）タグ）についての研究が進んでいる。無線タグについては、これまで、主に流通業界においてバーコードに代わる商品の識別及び管理を行う技術として研究されてきたが、現在では、いわゆるユビキタスコンピューティングの分野における中心的な技術になり得るものとして注目されている。
【０００６】
今後は、無線タグを用いて、商品だけではなく、人の識別及び管理を行うことなども期待されている。この場合、その人のプライベートに関わる事項など、高度なセキュリティを保つ必要があるデータを扱うことになるため、データを暗号化する必要性が高くなる。
【０００７】
しかしながら、上記のＤＥＳによる場合、暗号強度が十分ではないため、セキュリティを確保することが困難であるという問題があった。
【０００８】
また、上記のＡＥＳによる場合、ＤＥＳと比べて暗号強度は十分であるといえるが、アルゴリズムが複雑であるため、計算量が多くなり、微少な電力しか供給されず且つ回路規模も小さくならざるを得ないという制約を有する無線タグにおいて、実行することは困難であった。
【０００９】
本発明は、斯かる事情に鑑みてなされたものであり、その目的は、例えば無線タグのような微少な電力及び回路規模に限られるという制約がある場合であっても、セキュリティを確保することができる暗号鍵生成方法、その方法を実施するための暗号鍵生成装置及び暗号演算回路、その暗号演算回路を備える無線タグ、並びに前記方法をコンピュータに実施させるためのコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１０】
本発明者は、無線タグのように微少な電力及び回路規模に限られるという制約が伴う場合であっても、問題なく実行することができるような計算量の少ない暗号技術を実現するために、鋭意検討を重ねてきた。そして、上述した２ｆａｃｔｏｒ暗号システムで提案されているＰＤＡＦ及びＯＷＣという関数が桁上げのないディジット毎の加算のみで構成されている点に着目し、これらの考え方を用いることにより、計算量が少なく、しかもセキュリティが確保されたストリーム暗号系の暗号技術を実現することができると考えた。
【００１１】
これらの知見に基づいて、本発明者は、以下に示す発明をした。
【００１２】
本発明の暗号鍵生成方法は、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成方法において、第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する工程（ａ）と、  生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する工程（ｂ）とを有し、前記工程（ａ）及び（ｂ）は、前記文のブロック毎に実行され、後行する前記工程（ａ）における第１のディジット列は、先行する前記工程（ａ）により生成された第２のディジット列であり、後行する前記工程（ａ）における特定の組の複数のディジットは、先行する前記工程（ａ）により生成された第２のディジット列における特定のディジットに基づいて決定される。
【００１３】
このように桁上げのないディジット毎の加算のみで暗号鍵を生成することができるため、少ない計算量で足りる。
【００１４】
上記発明に係る暗号鍵生成方法において、前記後行する前記工程（ａ）における第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記先行する前記工程（ａ）により生成された第２のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］として、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記後行する前記工程（ａ）において生成される第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）は、ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求められるようにしてもよい。
【００１５】
本発明の暗号鍵生成装置は、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列の生成処理を実行する第２のディジット列生成手段と、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列の生成処理を実行する第３のディジット列生成手段とを備え、前記第２のディジット列生成手段及び前記第３のディジット列生成手段は、前記文のブロック毎に、前記第２のディジット列及び前記第３のディジット列の生成処理をそれぞれ実行するように構成されており、後行する前記第２のディジット列生成手段による第２のディジット列の生成処理における第１のディジット列は、先行する前記第２のディジット列生成手段による第２のディジット列の生成処理により生成された第２のディジット列であり、後行する前記第２のディジット列生成手段による第２のディジット列の生成処理における特定の組の複数のディジットは、先行する前記第２のディジット列生成手段による第２のディジット列の生成処理により生成された第２のディジット列における特定のディジットに基づいて決定される。
【００１６】
また、本発明の暗号鍵装置は、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、所定の演算処理を実行する演算装置と、第１のディジット列を記憶するメモリとを備え、  前記演算装置は、前記メモリから前記第１のディジット列を読み出し、その読み出した第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列を生成する第２のディジット列生成処理と、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列を生成する第３のディジット列生成処理とを、前記文のブロック毎に実行するように構成されており、後行する前記第２のディジット列生成処理における第１のディジット列は、先行する前記第２のディジット列生成処理により生成された第２のディジット列であり、後行する前記第２のディジット列生成処理における特定の組の複数のディジットは、先行する前記第２のディジット列生成処理により生成された第２のディジット列における特定のディジットに基づいて決定される。
【００１７】
本発明の暗号演算回路は、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号演算回路において、第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施すことによって、第２のディジット列の生成処理を実行する第１関数回路と、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第３のディジット列の生成処理を実行する第２関数回路とを備え、前記第１関数回路及び前記第２関数回路は、前記文のブロック毎に、前記第２のディジット列及び前記第３のディジット列の生成処理をそれぞれ実行するように構成されており、後行する前記第１関数回路による第２のディジット列の生成処理における第１のディジット列は、先行する前記第１関数回路による第２のディジット列の生成処理により生成された第２のディジット列であり、後行する前記第１関数回路による第２のディジット列の生成処理における特定の組の複数のディジットは、先行する前記第１関数回路による第２のディジット列の生成処理により生成された第２のディジット列における特定のディジットに基づいて決定される。
【００１８】
上記発明に係る暗号演算回路において、前記第２関数回路によって生成された第３のディジット列を用いて、外部から入力された平文に対する暗号化処理を実行する暗号化回路をさらに備えるようにしてもよい。
【００１９】
また、上記発明に係る暗号演算回路において、前記第１のディジット列は、共通鍵であってもよい。
【００２０】
また、上記発明に係る暗号演算回路において、前記後行する前記第１関数回路による第２のディジット列の生成処理における第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記先行する前記第１関数回路による第２のディジット列の生成処理により生成された第２のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第１関数回路は、前記後行する前記第１関数回路による第２のディジット列の生成処理において生成される第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）を、ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求められるように構成されていてもよい。
【００２１】
本発明の無線タグは、外部の通信装置と非接触で通信可能な無線タグにおいて、上記発明に係る暗号演算回路と、当該暗号演算回路により生成された暗号鍵を用いて生成された暗号文を、前記通信装置に対して送信する送信装置とを備える。
【００２２】
本発明のコンピュータプログラムは、コンピュータに、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵の生成を行わせるためのコンピュータプログラムにおいて、前記コンピュータに、所定の第１のディジット列における特定の組の複数のディジットに対して、その組を変えながら繰り返し加算処理を施させることによって、第２のディジット列を生成させる手順（ａ）と、生成した第２のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することにより得られる第３のディジット列である暗号鍵を生成させる手順（ｂ）とを、前記文のブロック毎に実行させ、後行する前記手順（ａ）における第１のディジット列は、先行する前記手順（ａ）により生成された第２のディジット列であり、後行する前記手順（ａ）における特定の組の複数のディジットは、先行する前記手順（ａ）により生成された第２のディジット列における特定のディジットに基づいて決定される。
【００２３】
上記発明に係るコンピュータプログラムにおいて、前記後行する前記手順（ａ）における第１のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、前記先行する前記手順（ａ）により生成された第２のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］として、これらのディジット列をｒ進法で表す場合であって、ｎはディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記後行する前記手順（ａ）において生成される第２のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］（ｎはディジット数）は、ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求めさせるようにしてもよい。
【００２４】
本発明の上記目的、他の目的、特徴、及び利点は、添付図面参照の下、以下の好適な実施態様の詳細な説明から明らかにされる。
【発明の効果】
【００２５】
本発明の暗号鍵生成方法、その方法を実施するための暗号鍵生成装置、その方法を実施するための暗号鍵生成装置及び暗号演算回路、その暗号演算回路を備える無線タグ、並びに前記方法をコンピュータに実施させるためのコンピュータプログラムによれば、少ない計算量でセキュリティを確保することが可能となる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の好ましい実施の形態を、図面を参照しながら説明する。
【００２７】
（実施の形態１）
図１は、本発明の実施の形態１に係る無線タグ及び暗号鍵生成装置を備える無線タグシステムの構成を示すブロック図である。
【００２８】
図１に示すように、無線タグシステムは、無線タグ１と、その無線タグ１と非接触で通信可能な暗号鍵生成装置２とを備えている。本実施の形態において、暗号鍵生成装置２は、無線タグ１によって送信された暗号文を復号する復号装置として機能する。そのため、以下では、暗号鍵生成装置２を復号装置２と称する。
【００２９】
無線タグ１は、制御回路１１、メモリ回路１２、暗号演算回路１３、情報の送受信装置である無線回路１４及びアンテナ１５、並びに電源部１６を備えている。制御回路１１は、メモリ回路１２、暗号演算回路１３、及び無線回路１４と接続されており、また、無線回路１４は更に、復号装置２と通信するためのアンテナ１５及び電源部１６と接続されている。
【００３０】
ここで、メモリ回路１２は、制御回路１１が処理する各種のデータを記憶するための回路である。
【００３１】
また、暗号演算回路１３は、後述する処理を実行することによって、暗号鍵を生成し、その生成した暗号鍵を用いて、平文に対する暗号化処理を行う回路である。その暗号化処理の結果として生成された暗号文は、暗号演算回路１３から制御回路１１に対して出力される。
【００３２】
図１に示すとおり、暗号演算回路は、乱数Ｒを発生する乱数発生回路１０１と、乱数Ｒ及び共通鍵Ｋを用いて後述する第１関数を実行する第１関数回路１０２と、後述する第２関数を実行する第２関数回路１０３と、生成された暗号鍵を用いて平文Ｐから暗号文への暗号化処理を行う暗号化回路とを備えている。ここで、乱数回路１０１、第１関数回路１０２、第２関数回路１０３、及び暗号化回路１０４は、論理回路であり、複数の論理素子の組合せにより構成される。
【００３３】
無線回路１４は、アンテナ１５で受信した無線信号を復調してデジタル信号を生成し、そのデジタル信号を制御回路１１に対して出力する。また、制御回路１１の命令にしたがって、送信すべきデジタル信号を変調して無線信号を生成し、アンテナ１５を介してその無線信号を外部へ送信する。
【００３４】
電源部１６は、無線回路１４から無線信号を取得し、その無線信号を電源電圧に変換する。これにより、電源部１６は、無線タグ１の内部を動作させるために必要な電力を得る。
【００３５】
なお、本実施の形態では、暗号化処理を行うための専用の回路である暗号演算回路が設けられているが、これに限定されるわけではなく、例えば制御回路が暗号演算回路を兼ねるような構成であってもよい。また、暗号演算回路のようにチップ化されているのではなく、後述する暗号化処理をソフトウェアで実行するような構成であってもよい。
【００３６】
また、復号装置２は、演算装置であるＣＰＵ２１、メモリ部２２、通信インタフェース（Ｉ／Ｆ）２４、及びアンテナ２５を備えている。ＣＰＵ２１は、メモリ部２２及び通信Ｉ／Ｆ２４と接続されており、また、通信Ｉ／Ｆ２４は更に、無線タグ１と通信するためのアンテナ２５と接続されている。
【００３７】
ここで、メモリ部２２は、ＣＰＵ２１が処理する各種のデータを記憶するものである。なお、図示しているように、メモリ部２２には、後述する復号処理を実現する暗号処理プログラム２３が記憶されている。この暗号処理プログラム２３は、後述する復号処理をコンピュータに行わせる手順から構成されるコンピュータプログラムである。
【００３８】
暗号処理プログラム２３は、乱数Ｒを発生する乱数発生ルーチン２０１と、乱数Ｒおよび共通鍵Ｋを用いて後述する第１関数を実行する第１関数実行ルーチン２０２と、後述する第２関数を実行する第２関数実行ルーチン２０３と、生成された暗号鍵を用いて暗号文Ｃから平文Ｐへの復号処理を実行する復号処理実行ルーチン２０４とを有している。
【００３９】
次に、以上のように構成された無線タグ１及び復号装置２の動作について説明する。
【００４０】
［暗号化処理］
無線タグ１が備える制御回路１１は、メモリ回路１２に記憶されている平文Ｐを適宜のタイミングで取得し、その取得した平文Ｐを暗号演算回路１３へ出力する。この平文Ｐを受け取った暗号演算回路１３は、次のようにして、暗号鍵の生成及びその暗号鍵による平文Ｐの暗号化を含む暗号化処理を実行し、暗号文Ｃを生成する。
【００４１】
図２は、暗号文の生成に伴う、暗号演算回路１３の処理手順を示すフローチャートである。
【００４２】
図２に示すとおり、暗号演算回路１３は、予め用意しておいたデータ配列Ｓ（−１）に共通鍵Ｋを、Ｓ（０）に乱数Ｒをそれぞれ代入する（Ｓ１０１）。なお、無線タグ１及び復号装置２は、同一の共通鍵Ｋを所定の手順にしたがって予め取得し、記憶しているものとする。また、乱数Ｒは、暗号演算回路１３が備える乱数発生回路１０１によって生成される。
【００４３】
次に、暗号演算回路１３は、変数ｊに１を代入する（Ｓ１０２）。そして、暗号演算回路１３は、Ｓ（ｊ）に対して、第１関数Ｆ１［Ｓ（ｊ−２），Ｓ（ｊ−１）］を代入する（Ｓ１０３）。以下、この第１関数Ｆ１について説明する。
【００４４】
本発明において、第１関数Ｆ１とは、引数として与えられたディジット列のうち、特定の位置にある複数のディジット同士を加算し、その結果を出力するものである。本実施の形態において、具体的には、以下の式にしたがって演算がなされる。
【００４５】
Ｘ＝｛ｘ（１），ｘ（２），…，ｘ（ｉ），…，ｘ（ｎ）｝
Ｙ＝｛ｙ（１），ｙ（２），…，ｙ（ｉ），…，ｙ（ｎ）｝
Ｚ＝Ｆ１［Ｘ，Ｙ］＝Ｘ（Ｙ）
＝｛ｚ（１），ｚ（２），…，ｚ（ｉ），…，ｚ（ｎ）｝
ここで、ｉが１からｎ（ｎは、平文のブロック長）になるまで、次の式１を適用することによって、ｚ（ｉ）が得られる。
【００４６】
ｚ（ｉ）
＝｛ｘ（ｉ）＋ｘ［（ｉ＋ｙ（ｉ））（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）  …式１
なお、この式１は、ディジット列であるＸ，Ｙ及びＺをｒ進法で表す場合のものである。
【００４７】
このように、本実施の形態では、ディジット列Ｙにおける特定のディジットにより、ディジット列Ｘのうちの特定の組の２つのディジットが決定されることになる。そして、その２つのディジットに対して加算処理を施すことによって、ディジット列Ｚが生成される  ことになる。
【００４８】
なお、本実施の形態では、上記のとおり、ディジット列Ｘのうちの特定の組の２つのディジットに対して加算処理を実行しているが、本発明はこれに限定されるわけではなく、ディジット列Ｘのうちの特定の組の３つ以上のディジットに対して加算処理を実行するようにしてもよい。
【００４９】
以上の第１関数Ｆ１は、暗号演算回路１３が備える第１関数回路１０２により実行される。
【００５０】
次に、暗号演算回路１３は、ステップＳ１０３を実行した結果得られたＳ（ｊ）と、ディジット列における特定の位置を示すＳＶとを引数とした第２関数Ｆ２［Ｓ（ｊ）；ＳＶ］の出力を、ｋ（ｊ）に代入する（Ｓ１０４）。以下、この第２関数Ｆ２について説明する。
【００５１】
第２関数Ｆ２とは、引数Ｓ（ｊ）として与えられたディジット列を、引数ＳＶで示す位置で２つのディジット列に分け、それらのディジット列同士を加算し、その結果を出力するものである。本実施の形態においては、具体的に、以下の式にしたがって演算がなされる。
【００５２】
Ｓ＝｛ｓ（１），ｓ（２），…，ｓ（ｉ），…，ｓ（ｎ）｝
Ｔ＝Ｆ２［Ｓ；ｎ／２］
＝｛ｔ（１），ｔ（２），…，ｔ（ｉ），…，ｔ（ｎ／２）｝
ここで、ｊが１からｎ／２になるまで、次の式２を適用することによって、ｔ（ｉ）が得られる。
【００５３】
ｔ（ｉ）＝｛ｓ（ｉ）＋ｓ（ｉ＋ｎ／２）｝（ｍｏｄｒ）  …式２
なお、本実施の形態では、引数Ｓ（ｊ）として与えられたディジット列を、ｎ／２の位置で２つのディジット列に分けているが、それ以外の位置で２つのディジット列に分けるようにしてもよい。
【００５４】
また、本実施の形態では、引数Ｓ（ｊ）として与えられたディジット列を２つのディジット列に分けているが、本発明はこれに限定されるわけではなく、当該ディジット列を３つ以上のディジット列に分けるようにしてもよい。この場合、ＳＶが２つ以上の位置を示すようにすればよい。
【００５５】
以上の第２関数Ｆ２は、暗号演算回路１３が備える第２関数回路１０３により実行される。
【００５６】
このようにして第２関数Ｆ２を実行した場合の出力がｋ（ｊ）に代入される。後述するように、このｋ（ｊ）が、暗号鍵として機能することになる。すなわち、上述した内容の第１関数Ｆ１及び第２関数Ｆ２を実行することによって、暗号鍵ｋ（ｊ）が生成されることになる。
【００５７】
次に、暗号演算回路１３は、暗号文の生成を行う。具体的には、Ｐ（ｊ）とｋ（ｊ）とのビット毎のｍｏｄ２加算、すなわちＰ（ｊ）とｋ（ｊ）との排他的論理和を算出し、それをＣ（ｊ）に代入する（Ｓ１０５）。
【００５８】
このように、＋を円で囲った記号は、ｍｏｄ２での加算（排他的論理和）を意味している。また、Ｐ（ｊ）は平文のｊ番目のブロックを、Ｃ（ｊ）は暗号文Ｃのｊ番目のブロックをそれぞれ意味している。
【００５９】
以上の暗号文Ｃの生成は、暗号演算回路１３が備える暗号化回路１０４により実行される。
【００６０】
次に、暗号演算回路１３は、ｊがＮ（Ｎは、平文のブロック数）より大であるか否かを判定する（Ｓ１０６）。ここで、ｊがＮ以上であると判定した場合（Ｓ１０６でＹＥＳ）、暗号演算回路１３は、処理を終了する。
【００６１】
他方、ステップＳ１０６にてｊがＮ以下であると判定した場合（Ｓ１０６でＮＯ）、暗号演算回路１３は、Ｓ（ｊ−２）にＳ（ｊ−１）を、Ｓ（ｊ−１）にＳ（ｊ）をそれぞれ代入し（Ｓ１０７）、ｊを１だけインクリメントする（Ｓ１０８）。
【００６２】
その後、暗号演算回路１３は、ステップＳ１０６においてｊがＮより大と判定されるまで、ステップＳ１０３からＳ１０８までを繰り返し実行する。
【００６３】
以上の処理を実行した結果、暗号文Ｃが生成される。なお、この暗号文Ｃには、予め算出された、共通鍵Ｋと乱数Ｒとの排他的論理和であるＣ（０）が含まれている。このようにして生成された暗号文Ｃは、無線タグ１から復号装置２に対して適宜のタイミングで送信される。
【００６４】
上記から、第１関数回路１０２および第２関数回路１０３は、多値の非線形シフトレジスタの構成要素であること、また、これらの回路によって、暗号鍵の系列の系列が生成されていることが理解できる。
【００６５】
このようにして暗号文Ｃを受信した復号装置２は、次の復号処理を実行する。
【００６６】
［復号処理］
図３は、復号処理に伴う、復号装置２の処理手順を示すフローチャートである。この図３と図２とを比較すれば分かるように、復号処理と暗号化処理とにおいて、暗号鍵を生成する処理は同一である。そのため、ステップＳ２０５を除くＳ２０１からＳ２０８までは、図２におけるステップＳ１０５を除くＳ１０１からＳ１０８までとそれぞれ同様である。ただし、ステップＳ２０１において、乱数Ｒが、Ｃ（０）とＫとの排他的論理和により得られる点については、復号処理と暗号化処理とで異なる。
【００６７】
なお、ステップＳ２０３における第１関数の実行は第１関数実行ルーチン２０２によって、ステップＳ２０４における第２関数の実行は第２関数実行ルーチン２０３によって、それぞれなされる。
【００６８】
以下では、ステップＳ２０５を除くＳ２０１からＳ２０８についての説明は省略し、ステップＳ２０５の処理についてのみ説明する。
【００６９】
ステップＳ２０５において、復号装置２は、無線タグ１から受け取ったＣ（ｊ）とステップＳ２０４で得られたｋ（ｊ）とのｍｏｄ２加算、すなわちＣ（ｊ）とｋ（ｊ）との排他的論理和を算出する。そして、その結果得られた値をＰ（ｊ）に代入する。このように、暗号鍵ｋ（ｊ）を用いることによって、暗号文のｊブロック目であるＣ（ｊ）から平文のｊブロック目であるＰ（ｊ）が得られることになる。
【００７０】
復号装置２は、ステップＳ２０６においてｊがＮより大と判定されるまで、ステップＳ２０３からＳ２０８までを繰り返し実行する。その結果、復号処理が完了し、平文Ｐが得られる。
【００７１】
この復号処理は、復号処理実行ルーチン２０４によって実行される。
【００７２】
次に、具体的に平文をデータとして与え、具体的な処理結果を参照しながら、上記の暗号化処理及び復号処理について説明する。なお、以下の例は、ディジット列を１６進数で表すものである。
【００７３】
［暗号化処理］
無線タグ１が備える暗号演算回路１３は、乱数Ｒとして、ディジット列２３７３９０を生成したものとする。また、共通鍵Ｋとして、ディジット列３０２４５８を記憶しているものとする。この場合、Ｃ（０）は、共通鍵Ｋ＝３０２４５８＝（００１１  ００００  ００１０  ０１００  ０１０１  １０００）と乱数Ｒ＝２３７３９０＝（００１０  ００１１  ０１１１  ００１１  １００１  ００００）との排他的論理和である１３５７Ｃ８＝（０００１  ００１１  ０１０１  ０１１１  １１００  １０００）となる。
【００７４】
また、暗号演算回路１３には、平文Ｐとして、以下の値が記憶されているものとする。
【００７５】
Ｐ＝｛Ｐ（１）＝５ＣＡ＝（０１１０  １１００  １０１０）
Ｐ（２）＝２０Ｆ＝（００１０  ００００  １１１１）
Ｐ（３）＝２Ａ３＝（００１０  １０１０  ００１１）
Ｐ（４）＝…………
Ｐ（５）＝………
…………  ……                                    ｝
まず、暗号演算回路１３は、Ｋ，ＲをＳ（−１），Ｓ（０）へ代入し、ｊ＝１とした後、上述したステップＳ１０３のとおり、第１関数Ｆ１を用いて、Ｓ（１）を算出する。具体的には、Ｆ１［Ｓ（−１），Ｓ（０）］、すなわちＦ１［３０２４５８，２３７３９０］を実行する。この場合のｚ（１）からｚ（６）までの値は以下のようにして求められる。
【００７６】
ｚ（１）＝｛ｘ（１）＋ｘ［１＋ｙ（１）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）
＝｛３＋ｘ［（１＋２）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）
＝｛３＋ｘ（４）｝（ｍｏｄ１６）＝｛３＋４｝（ｍｏｄ１６）＝７
ｚ（２）＝｛ｘ（２）＋ｘ［２＋ｙ（２）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）
＝｛０＋ｘ［（２＋３）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）
＝｛０＋ｘ（６）｝（ｍｏｄ１６）＝｛０＋８｝（ｍｏｄ１６）＝８
ｚ（３）＝｛ｘ（３）＋ｘ［１＋ｙ（３）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）
＝｛２＋ｘ［（３＋７）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）
＝｛２＋ｘ（５）｝（ｍｏｄ１６）＝｛２＋５｝（ｍｏｄ１６）＝７
ｚ（４）＝｛ｘ（４）＋ｘ［４＋ｙ（４）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）
＝｛４＋ｘ［（４＋３）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）
＝｛４＋ｘ（２）｝（ｍｏｄ１６）＝｛４＋０｝（ｍｏｄ１６）＝４
ｚ（５）＝｛ｘ（５）＋ｘ［１＋ｙ（５）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）
＝｛５＋ｘ［（５＋９）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）
＝｛５＋ｘ（３）｝（ｍｏｄ１６）＝｛５＋２｝（ｍｏｄ１６）＝７
ｚ（６）＝｛ｘ（６）＋ｘ［１＋ｙ（６）］（ｍｏｄ６）＋１｝（ｍｏｄ１６）
＝｛８＋ｘ［（６＋０）（ｍｏｄ６）＋１］｝（ｍｏｄ１６）
＝｛８＋ｘ（１）｝（ｍｏｄ１６）＝｛８＋３｝（ｍｏｄ１６）＝Ｂ
以上より、Ｓ（１）の値が求まる。次に、暗号演算回路１３は、上述したステップＳ１０４のとおり、第２関数Ｆ２を用いて、暗号鍵ｋ（１）を算出する。具体的には、Ｆ２［Ｓ（１）；ｎ／２］、すなわちＦ２［７８７４７Ｂ；３］を実行する。この演算は次のとおりとなる。
【００７７】
ｋ（１）＝Ｆ２［７８７４７Ｂ；３］＝７８７＋４７Ｂ
＝ＢＦ２＝（１０１１  １１１１  ００１０）
次に、暗号演算回路１３は、上述したステップＳ１０５のとおり、Ｐ（１）とｋ（１）との排他的論理和をとることによってＣ（１）を生成する。すなわち、（０１１０  １１００  １０１０）と（１０１１  １１１１  ００１０）との排他的論理和である（１１０１  ００１１  １０００）をＣ（１）とする。
【００７８】
また、暗号演算回路１３は、Ｓ（２）及びｋ（２）を次のとおり算出する。
【００７９】
Ｓ（２）＝Ｆ１［Ｓ（０），Ｓ（１）］＝Ｆ１［２３７３９０，７８７４７Ｂ］
＝９Ｃ０ＡＢ０＝（１００１  １１００  ００００  １０１０  １０１１  ００００）
ｋ（２）＝Ｆ２［Ｓ（２）；３］＝Ｆ２［９Ｃ０ＡＢ０；３］＝９ＣＤ＋ＡＢ０
＝３７０＝（００１１  ０１１１  ００００）
その結果、Ｃ（２）として、Ｐ（２）とｋ（２）との排他的論理和である（０００１  ０１１１  １１１１）が得られる。
【００８０】
さらに、暗号演算回路１３は、Ｓ（３）及びｋ（３）を次のとおり算出する。
【００８１】
Ｓ（３）＝Ｆ１［Ｓ（１），Ｓ（２）］＝Ｆ１［７８７４７Ｂ，９Ｃ０ＡＢ０］
＝ＥＦＢＢＥ２＝（１１１０  １１１１  １０１１  １０１１  １１１０  ００１０）
ｋ（３）＝Ｆ２［Ｓ（３）；３］＝Ｆ２［ＥＦＢＢＥ２；３］＝ＥＦＢ＋ＢＥ２
＝９ＤＤ＝（１０１１  ０１１１  １１１０）
その結果、Ｃ（３）として、これらＳ（３）とｋ（３）との排他的論理和である（１０１１  ０１１１  １１１０）が得られる。
【００８２】
暗号演算回路１３は、以上の処理を、ｊの値が平文のブロック数Ｎに達するまで繰り返し実行する。その結果、次のとおりの暗号文Ｃを得ることができる。
【００８３】
Ｃ＝｛Ｃ（０）＝（０００１  ００１１  ０１０１  ０１１１  １１００  １０００）
Ｃ（１）＝（１１０１  ００１１  １０００）
Ｃ（２）＝（０００１  ０１１１  １１１１）
Ｃ（３）＝（１０１１  ０１１１  １１１０）
Ｃ（４）＝…………
Ｃ（５）＝………
…………  ……                                    ｝
［復号処理］
復号装置２は、無線タグ１から暗号文Ｃを受信した場合、そのうちのＣ（０）と共通鍵Ｋとの排他的論理和を算出し、これを乱数Ｒとする。そのため、この例では、（００１０  ００１１  ０１１１  ００１１  １００１  ００００）＝２３７３９０を乱数Ｒとする。
【００８４】
まず、復号装置２は、Ｋ，ＲをＳ（−１），Ｓ（０）へそれぞれ代入し、ｉ＝１とした後、上述したステップＳ２０３のとおり、第１関数Ｆ１を用いて、Ｓ（１）を算出する。具体的には、Ｆ１［Ｓ（−１），Ｓ（０）］、すなわちＦ１［３０２４５８，２３７３９０］を実行する。これは、上述した暗号化処理の場合と同様であるので、Ｓ（１）＝７８７４７Ｂ＝（０１１１  １０００  ０１１１  ０１００  ０１１１  １０１１）となり、ｋ（１）＝Ｆ２［７８７４７Ｂ；３］＝ＢＦ２＝（００１１  ０１１１  ００００）となる。
【００８５】
次に、復号装置２は、上述したステップＳ２０５のとおり、Ｃ（１）とｋ（１）との排他的論理和をとることによってＰ（１）を生成する。すなわち、（１１０１  ００１１  １０００）と（１０１１  １１１１  ００１０）との排他的論理和である（０１１０  １１００  １０１０）をＰ（１）とする。
【００８６】
また、復号装置２は、Ｓ（２）及びｋ（２）を、上述した暗号化処理の場合と同様にして算出し、Ｓ（２）＝（１００１  １１００  ００００  １０１０  １０１１  ００００）及びｋ（２）＝（００１１  ０１１１  ００００）を得る。
【００８７】
その結果、Ｐ（２）として、Ｃ（２）とｋ（２）との排他的論理和である（００１０  ００００  １１１１）が得られる。
【００８８】
さらに、復号装置２は、Ｓ（３）及びｋ（３）を、上述した暗号化処理の場合と同様にして算出し、Ｓ（３）＝（１１１０  １１１１  １０１１  １０１１  １１１０  ００１０）及びｋ（３）＝（１００１  １１０１  １１０１）を得る。
【００８９】
その結果、Ｐ（３）として、Ｃ（３）とｋ（３）との排他的論理和である（００１０  １０１０  ００１１）が得られる。
【００９０】
復号装置２は、以上の処理を、ｉの値が暗号文のブロック数ｎに達するまで繰り返し実行する。その結果、次のとおりの平文Ｐを得ることができる。
【００９１】
Ｐ＝｛Ｐ（１）＝５ＣＡ＝（０１１０  １１００  １０１０）
Ｐ（２）＝２０Ｆ＝（００１０  ００００  １１１１）
Ｐ（３）＝２Ａ３＝（００１０  １０１０  ００１１）
Ｐ（４）＝…………
Ｐ（５）＝………
…………  ……                                    ｝
以上のようにして得られた平文Ｐは、無線タグ１によって暗号化処理が施される前の平文Ｐと同一のものであることが確認できる。
【００９２】
以上のように暗号化及び復号を実施することにより、簡易な処理で強固なセキュリティが確保された無線タグシステムを実現することができる。
【００９３】
［安全性について］
以下、従来の共通鍵暗号系と比較して計算量が少ない本発明の暗号鍵生成方法であっても、十分なセキュリティを確保することができる点について説明する。
【００９４】
一般に、「暗号系を破る」とは、長さｎディジットの鍵Ｋが露呈するということを意味する。ここで、鍵Ｋが露呈するためには、連続する２つのＳｊの値（２つのレジスタの数値）が露呈される必要がある。
【００９５】
選択平文攻撃（Chosen plaintext attack）または選択暗号文攻撃（Chosen ciphertext attack）などを用いて、鍵の系列ｋ（ｊ）（１≦ｊ≦ｔ）を入手することができたとしても、ｋ（ｊ）系列は無相関の乱数系列であるため、ｋ（ｊ）（ｊ＞ｔ）を推定することは不可能である。
【００９６】
また、ｋ（ｊ）（１≦ｊ≦ｔ）によってＳ（ｊ）及びＳ（ｊ＋１）を算出するためには、（１／２）ｒｎ＝２ｍｎ−１＝２ａ−１（但し、ｒ＝２ｍ）の計算量が必要となる。この値をＣｏｍｐ＝（１／２）ｅｘｐ［（ｌｎ２）・ａ］と表現したものを計算量的複雑さ（Computational Complexity）と一般的に定義されている。
【００９７】
以上より、「暗号系を破る」ための計算量的複雑さは、Ｃｏｍｐ＝（１／２）ｅｘｐ［（ｌｎ２）・ａ］であり、この計算量的複雑さによって、暗号系のセキュリティレベルが証明される。したがって、ａ＝ｍｎの大きさを大きくすればするほど、暗号系のセキュリティレベルは、指数関数的に高められることになる。
【００９８】
以上をまとめると、「暗号系を破る」ために必要な計算量的複雑さを導出することにより、（計算量的）安全性を証明することができ、適用する数値のサイズａ＝ｍｎ（換言するとレジスタのサイズａ＝ｍｎ）を大きく設定することにより、十分なセキュリティを確保できることになる。
【００９９】
したがって、本発明のように、加算のみで暗号鍵を生成したとしても、ａ＝ｍｎの値を十分に大きくすることによって、十分なセキュリティを確保することが可能となる。
【０１００】
［速度比較テスト］
上述した本実施の形態における暗号化処理及び復号処理を実行した場合の処理に要する時間（処理時間）と、従来の共通鍵暗号系であるＤＥＳを用いた暗号化処理及び復号処理を実行した場合の処理時間とを比較するテストを実行した。以下では、本実施の形態における処理を実施例と称し、ＤＥＳを用いた場合における処理を比較例と称する。
【０１０１】
このテストにおいては、米インテル社製のＣｅｌｅｒｏｎ（登録商標）Ｍプロセッサ（動作周波数１．４０ＧＨｚ）及び５０４ＭＢのＲＡＭを備えたパーソナルコンピュータ（ＰＣ）を用いて行った。このＰＣには、オペレーティングシステムとして、米マイクロソフト社のＷｉｎｄｏｗｓＸＰ（登録商標）のＨｏｍｅＥｄｉｔｉｏｎ，Ｖｅｒｓｉｏｎ２００２，ＳｅｒｖｉｃｅＰａｃｋ２がインストールされていた。また、本実施の形態における暗号化処理及び復号処理並びにＤＥＳを用いた暗号化処理及び復号処理は、ＦＯＲＴＲＡＮ７７を用いて作成されたコンピュータプログラムにより実行された。
【０１０２】
このテストにおける４つの条件を以下の表１にまとめた。なお、この表１において、「比較例鍵」とはＤＥＳにおける共通鍵を示し、「実施例鍵」とは本実施の形態における共通鍵を示している。
【０１０３】
【表１】
2008072351.tif 000009
【０１０４】
表１に挙げられている４つの条件についてのテスト結果を表２にまとめた。なお、表２に示されているように、各条件について２回のテストを行っている。また、各テストにおいて、１００，０００，０００回のループ処理を行っている。
【０１０５】
【表２】
2008072351.tif 000010
【０１０６】
表２に示すように、条件１乃至４のすべての場合において、本実施例の方が比較例よりも早く処理を行うことができた。具体的には、本実施例では、比較例の場合と比べて、１０．８９倍〜１２．２０倍早く処理を行うことができた。
【０１０７】
上記の結果から、本実施例の場合では、計算量が少なく、したがって、比較例の場合と比べて処理時間も短くなることを確認することができる。
【０１０８】
なお、本実施の形態では、無線タグを構成する暗号演算回路が、第１関数及び第２関数を用いることによって暗号鍵を生成し、その生成した暗号鍵によって暗号化処理を実行しているが、暗号演算回路は、このように暗号化処理を行う暗号化装置への適用に限られるわけではない。したがって、例えば、暗号演算回路が、本実施の形態における暗号化回路に代わって、または、その暗号化回路とともに、本実施の形態における復号装置が実行するような復号処理を行う論理回路である復号回路を備えることによって、復号装置として機能するようにしてもよい。
【０１０９】
（実施の形態２）
実施の形態１は、無線タグと復号装置とから構成される無線タグシステムであった。これに対し、実施の形態２は、インターネットなどの通信ネットワークを介して接続される複数のコンピュータ端末から構成されるコンピュータシステムである。
【０１１０】
図４は、本発明の実施の形態２に係る暗号鍵生成装置を備えるコンピュータシステムの構成を示すブロック図である。
【０１１１】
図４に示すように、コンピュータシステムは、暗号鍵生成装置３と、その暗号鍵生成装置３と通信ネットワーク５を介して通信可能に接続された暗号鍵生成装置４とを備えている。
【０１１２】
ここで、暗号鍵生成装置３は、暗号化処理を実行する暗号化装置として機能し、他方、暗号鍵生成装置４は、復号処理を実行する復号装置として機能する。そのため、以下では、暗号鍵生成装置３を暗号化装置３と称し、暗号鍵生成装置４を復号装置４と称する。
【０１１３】
暗号化装置３は、ＣＰＵ３１、メモリ部３２、及び通信インタフェース（Ｉ／Ｆ）３４を備えている。ＣＰＵ３１は、メモリ部３２及び通信Ｉ／Ｆ３４と接続されており、これらのハードウェアを制御する。
【０１１４】
メモリ部３２は、ＣＰＵ３１が処理する各種のデータを記憶するものである。なお、図示されているように、メモリ部３２には、暗号化処理を実現する暗号処理プログラム３３が記憶されている。この暗号処理プログラム３３は、実施の形態１における暗号演算回路１３が実施する暗号化処理をコンピュータに行わせる手順から構成されるコンピュータプログラムである。
【０１１５】
暗号処理プログラム３３は、乱数Ｒを発生する乱数発生ルーチン３０１と、乱数Ｒ及び共通鍵Ｋを用いて第１関数を実行する第１関数実行ルーチン３０２と、第２関数を実行する第２関数実行ルーチン３０３と、生成された暗号鍵を用いて平文Ｐから暗号文Ｃへの暗号化処理を実行する暗号化処理実行ルーチン３０４とを有している。
【０１１６】
また、復号装置４は、暗号化装置３と同様に、ＣＰＵ４１、メモリ部４２、及び通信Ｉ／Ｆ４４を備えている。そして、メモリ部４２には、復号処理を実現する暗号処理プログラム４３が記憶されている。この暗号処理プログラム４３は、実施の形態１における復号装置２が実施する復号処理をコンピュータに行わせる手順から構成されるコンピュータプログラムである。
【０１１７】
暗号処理プログラム４３は、乱数Ｒを発生する乱数発生ルーチン４０１と、乱数Ｒおよび共通鍵Ｋを用いて第１関数を実行する第１関数実行ルーチン４０２と、第２関数を実行する第２関数実行ルーチン４０３と、生成された暗号鍵を用いて暗号文Ｃから平文Ｐへの復号処理を実行する復号処理実行ルーチン４０４とを有している。
【０１１８】
以上のように構成されたコンピュータシステムにおいて、暗号化装置３は、暗号処理プログラム３３を実行することによって、実施の形態１における無線タグ１と同様にして暗号鍵を生成し、暗号文を生成する。その結果、生成された暗号文は、通信ネットワーク５を介して、暗号化装置３から復号装置４へ送信される。
【０１１９】
復号装置４は、暗号化装置３から暗号文を受信した場合、暗号処理プログラム４３を実行することによって、実施の形態１における復号装置２と同様にして暗号鍵を生成し、復号を行う。
【０１２０】
このように、暗号処理プログラム３３及び暗号処理プログラム４３を用いることによって、コンピュータ端末が本発明の暗号鍵生成装置として機能することになる。
【０１２１】
これにより、簡易な処理で強固なセキュリティが確保されたコンピュータシステムを実現することができる。
【０１２２】
なお、本実施の形態では、暗号処理プログラムを有するコンピュータ端末によりコンピュータシステムが構成されているが、例えば、実施の形態１における暗号演算回路を備えたコンピュータ端末によりコンピュータシステムが構成されていてもよい。
【０１２３】
上記説明から、当業者にとっては、本発明の多くの改良や他の実施形態が明らかである。従って、上記説明は、例示としてのみ解釈されるべきであり、本発明を実行する最良の態様を当業者に教示する目的で提供されたものである。本発明の精神を逸脱することなく、その構造及び／又は機能の詳細を実質的に変更できる。
【産業上の利用可能性】
【０１２４】
本発明に係る暗号鍵生成方法、暗号鍵生成装置、暗号演算回路、無線タグ、及びコンピュータプログラムは、少ない計算量でセキュリティを確保することが可能であるため、微少な電力及び回路規模に限られるという制約を有する無線タグを備える無線タグシステム、並びに各種のコンピュータシステム等において暗号化処理及び復号処理を行う場合に有用である。
【図面の簡単な説明】
【０１２５】
【図１】本発明の実施の形態１に係る無線タグ及び暗号鍵生成装置を備える無線タグシステムの構成を示すブロック図である。
【図２】暗号文の生成に伴う、暗号演算回路の処理手順を示すフローチャートである。
【図３】復号処理に伴う、復号装置の処理手順を示すフローチャートである。
【図４】本発明の実施の形態２に係る暗号鍵生成装置を備えるコンピュータシステムの構成を示すブロック図である。
【符号の説明】
【０１２６】
１    無線タグ
２    暗号鍵生成装置（復号装置）
３    暗号鍵生成装置（暗号化装置）
４    暗号鍵生成装置（復号装置）
５    通信ネットワーク
１１  制御回路
１２  メモリ回路
１３  暗号演算回路
１４  無線回路
１５  アンテナ
１６  電源部
２１  ＣＰＵ
２２  メモリ部
２３  暗号処理プログラム
２４  通信インタフェース
２５  アンテナ
【手続補正書】
【提出日】平成19年11月16日(2007.11.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、
第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する第３のディジット列生成処理を実行する第３のディジット列生成手段と、
生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する第４のディジット列生成処理を実行する第４のディジット列生成手段とを備え、
前記第３のディジット列生成手段及び前記第４のディジット列生成手段は、前記文のブロック毎に、前記第３のディジット列生成処理及び前記第４のディジット列生成処理をそれぞれ実行するように構成されており、
第１回目及び第２回目の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列であり、
それより後の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記第３のディジット列生成処理により生成された第３のディジット列であることを特徴とする、暗号鍵生成装置。
【請求項２】
複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、
所定の演算処理を実行する演算装置を備え、
前記演算装置は、
第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する第３のディジット列生成処理と、
生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する第４のディジット列生成処理とを、前記文のブロック毎に実行するように構成されており、
第１回目及び第２回目の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列であり、
それより後の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記第３のディジット列生成処理により生成された第３のディジット列であることを特徴とする、暗号鍵生成装置。
【請求項３】
複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号演算回路において、
第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する第３のディジット列生成処理を実行する第１関数回路と、
生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する第４のディジット列生成処理を実行する第２関数回路とを備え、
前記第１関数回路及び前記第２関数回路は、前記文のブロック毎に、前記第３のディジット列生成処理及び前記第４のディジット列生成処理をそれぞれ実行するように構成されており、
第１回目及び第２回目の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列であり、
それより後の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記第３のディジット列生成処理により生成された第３のディジット列であることを特徴とする、暗号演算回路。
【請求項４】
第１回目の前記第３のディジット列生成処理における第１のディジット列及び第２のディジット列はそれぞれ、第１の初期値ディジット列及び第２の初期値ディジット列であり、
第２回目の前記第３のディジット列生成処理における第１のディジット列及び第２のディジット列はそれぞれ、前記第２の初期値ディジット列及び第１回目の前記第３のディジット列生成処理により生成された第３のディジット列であり、
第Ｎ回目（Ｎは３以上）の前記第３のディジット列生成処理における第１のディジット列及び第２のディジット列はそれぞれ、第Ｎ−２回目の前記第３のディジット列生成処理により生成された第３のディジット列及び第Ｎ−１回目の前記第３のディジット列生成処理により生成された第３のディジット列である、請求項３に記載の暗号演算回路。
【請求項５】
前記第２関数回路によって生成された第４のディジット列を用いて、外部から入力された平文に対する暗号化処理を実行する暗号化回路をさらに備える、請求項３又は４に記載の暗号演算回路。
【請求項６】
前記第１の初期値ディジット列は共通鍵であり、前記第２の初期値ディジット列は乱数のディジット列である、請求項４に記載の暗号演算回路。
【請求項７】
第Ｎ−２回目の第３のディジット列生成処理により生成された第３のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、第Ｎ−１回目の第３のディジット列生成処理により生成された第３のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット列を構成するディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第１関数回路は、第Ｎ回目の第３のディジット列生成処理において生成される第３のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］を、次の式により求めるように構成されている、請求項４に記載の暗号演算回路。
ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）
【請求項８】
外部の通信装置と非接触で通信可能な無線タグにおいて、
請求項３乃至７の何れかに記載の暗号演算回路と、
当該暗号演算回路により生成された暗号鍵を用いて生成された暗号文を、前記通信装置に対して送信する送信装置とを備えることを特徴とする、無線タグ。
【請求項９】
コンピュータに、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵の生成を行わせるためのコンピュータプログラムにおいて、
前記コンピュータに、
第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する手順（ａ）と、
生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する手順（ｂ）とを、前記文のブロック毎に実行させ、
第１回目及び第２回目の前記手順（ａ）における第１のディジット列は、所与の初期値ディジット列であり、
それより後の前記手順（ａ）における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記手順（ａ）により生成された第３のディジット列であることを特徴とする、コンピュータプログラム。
【請求項１０】
第１回目の前記手順（ａ）における第１のディジット列及び第２のディジット列はそれぞれ、第１の初期値ディジット列及び第２の初期値ディジット列であり、
第２回目の前記手順（ａ）における第１のディジット列及び第２のディジット列はそれぞれ、前記第２の初期値ディジット列及び第１回目の前記手順（ａ）により生成された第３のディジット列であり、
第Ｎ回目（Ｎは３以上）の前記手順（ａ）における第１のディジット列及び第２のディジット列はそれぞれ、第Ｎ−２回目の前記手順（ａ）により生成された第３のディジット列及び第Ｎ−１回目の前記手順（ａ）により生成された第３のディジット列である、請求項９に記載のコンピュータプログラム。
【請求項１１】
第Ｎ−２回目の前記手順（ａ）により生成された第３のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、第Ｎ−１回目の前記手順（ａ）により生成された第３のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット列を構成するディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、第Ｎ回目の前記手順（ａ）において生成される第３のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］は、次の式により求められる、請求項１０に記載のコンピュータプログラム。
ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）  
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
本発明の暗号鍵生成装置は、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する第３のディジット列生成処理を実行する第３のディジット列生成手段と、生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する第４のディジット列生成処理を実行する第４のディジット列生成手段とを備え、前記第３のディジット列生成手段及び前記第４のディジット列生成手段は、前記文のブロック毎に、前記第３のディジット列生成処理及び前記第４のディジット列生成処理をそれぞれ実行するように構成されており、第１回目及び第２回目の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列であり、それより後の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記第３のディジット列生成処理により生成された第３のディジット列であることを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
また、本発明の暗号鍵生成装置は、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号鍵生成装置において、  所定の演算処理を実行する演算装置を備え、前記演算装置は、第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する第３のディジット列生成処理と、生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する第４のディジット列生成処理とを、前記文のブロック毎に実行するように構成されており、第１回目及び第２回目の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列であり、それより後の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記第３のディジット列生成処理により生成された第３のディジット列であることを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
また、本発明の暗号演算回路は、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵を生成する暗号演算回路において、第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する第３のディジット列生成処理を実行する第１関数回路と、  生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する第４のディジット列生成処理を実行する第２関数回路とを備え、前記第１関数回路及び前記第２関数回路は、前記文のブロック毎に、前記第３のディジット列生成処理及び前記第４のディジット列生成処理をそれぞれ実行するように構成されており、第１回目及び第２回目の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列であり、それより後の前記第３のディジット列生成処理における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記第３のディジット列生成処理により生成された第３のディジット列であることを特徴とする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
このように桁上げのないディジット毎の加算のみで暗号鍵を生成することができるため、少ない計算量で足りる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
また、上記発明に係る暗号演算回路において、第１回目の前記第３のディジット列生成処理における第１のディジット列及び第２のディジット列はそれぞれ、第１の初期値ディジット列及び第２の初期値ディジット列であり、第２回目の前記第３のディジット列生成処理における第１のディジット列及び第２のディジット列はそれぞれ、前記第２の初期値ディジット列及び第１回目の前記第３のディジット列生成処理により生成された第３のディジット列であり、第Ｎ回目（Ｎは３以上）の前記第３のディジット列生成処理における第１のディジット列及び第２のディジット列はそれぞれ、第Ｎ−２回目の前記第３のディジット列生成処理により生成された第３のディジット列及び第Ｎ−１回目の前記第３のディジット列生成処理により生成された第３のディジット列であるようにしてもよい。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
また、上記発明に係る演算回路が、前記第２関数回路によって生成された第４のディジット列を用いて、外部から入力された平文に対する暗号化処理を実行するようにしてもよい。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
また、上記発明に係る演算回路において、前記第１の初期値ディジット列は共通鍵であり、前記第２の初期値ディジット列は乱数のディジット列であってもよい。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
また、上記発明に係る演算回路において、第Ｎ−２回目の第３のディジット列生成処理により生成された第３のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、第Ｎ−１回目の第３のディジット列生成処理により生成された第３のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット列を構成するディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、前記第１関数回路が、第Ｎ回目の第３のディジット列の生成処理において生成される第３のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］を、式ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求めるように構成されていてもよい。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
本発明の無線タグは、外部の通信装置と非接触で通信可能な無線タグにおいて、上記発明に係る暗号演算回路と、当該暗号演算回路により生成された暗号鍵を用いて生成された暗号文を、前記通信装置に対して送信する送信装置とを備えることを特徴とする。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
本発明のコンピュータプログラムは、コンピュータに、複数のブロックから構成される文に対して適用されるストリーム暗号処理に用いられる暗号鍵の生成を行わせるためのコンピュータプログラムにおいて、前記コンピュータに、第１のディジット列の中から、第２のディジット列における特定のディジットに基づいて、複数のディジットを選択し、選択された複数のディジット同士を加算する加算処理を、当該特定のディジットを変化させることによって、選択される複数のディジットを変えながら繰り返し実行し、各加算処理により得られたディジットを並べることによって、第３のディジット列を生成する手順（ａ）と、生成した第３のディジット列を、複数のディジット列に分け、それらの複数のディジット列同士を加算することによって、暗号鍵としての第４のディジット列を生成する手順（ｂ）とを、前記文のブロック毎に実行させ、第１回目及び第２回目の前記手順（ａ）における第１のディジット列は、所与の初期値ディジット列であり、それより後の前記手順（ａ）における第１のディジット列は、所与の初期値ディジット列に引き続く、先行する前記手順（ａ）により生成された第３のディジット列であることを特徴とする。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
上記発明に係るコンピュータプログラムにおいて、第１回目の前記手順（ａ）における第１のディジット列及び第２のディジット列はそれぞれ、第１の初期値ディジット列及び第２の初期値ディジット列であり、第２回目の前記手順（ａ）における第１のディジット列及び第２のディジット列はそれぞれ、前記第２の初期値ディジット列及び第１回目の前記手順（ａ）により生成された第３のディジット列であり、第Ｎ回目（Ｎは３以上）の前記手順（ａ）における第１のディジット列及び第２のディジット列はそれぞれ、第Ｎ−２回目の前記手順（ａ）により生成された第３のディジット列及び第Ｎ−１回目の前記手順（ａ）により生成された第３のディジット列であってもよい。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
また、上記発明に係るコンピュータプログラムにおいて、第Ｎ−２回目の前記手順（ａ）により生成された第３のディジット列をｘ［１］，ｘ［２］，…，ｘ［ｉ］，…，ｘ［ｎ］とし、第Ｎ−１回目の前記手順（ａ）により生成された第３のディジット列をｙ［１］，ｙ［２］，…，ｙ［ｉ］，…，ｙ［ｎ］とし、これらのディジット列をｒ進法で表す場合であって、ｎはディジット列を構成するディジット数を、ｉは１からｎまでの整数をそれぞれ表すとき、第Ｎ回目の前記手順（ａ）において生成される第３のディジット列であるｚ［１］，ｚ［２］，…，ｚ［ｉ］，…，ｚ［ｎ］が、式ｚ［ｉ］＝｛ｘ［ｉ］＋ｘ［（ｉ＋ｙ［ｉ］）（ｍｏｄｎ）＋１］｝（ｍｏｄｒ）により求められるようにしてもよい。
【国際調査報告】
2008072351.tif 000011
2008072351.tif 000012