TOP > 国内特許検索 > 暗号装置、復号装置、暗号プログラム、復号プログラム、及び記録媒体 > 明細書

明細書 :暗号装置、復号装置、暗号プログラム、復号プログラム、及び記録媒体

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4737334号 (P4737334)
登録日 平成23年5月13日(2011.5.13)
発行日 平成23年7月27日(2011.7.27)
発明の名称または考案の名称 暗号装置、復号装置、暗号プログラム、復号プログラム、及び記録媒体
国際特許分類 G09C   1/00        (2006.01)
FI G09C 1/00 610A
請求項の数または発明の数 9
全頁数 28
出願番号 特願2009-505246 (P2009-505246)
出願日 平成20年3月19日(2008.3.19)
国際出願番号 PCT/JP2008/055132
国際公開番号 WO2008/114829
国際公開日 平成20年9月25日(2008.9.25)
優先権出願番号 2007071432
優先日 平成19年3月19日(2007.3.19)
優先権主張国 日本国(JP)
審査請求日 平成23年2月18日(2011.2.18)
特許権者または実用新案権者 【識別番号】800000068
【氏名又は名称】学校法人東京電機大学
発明者または考案者 【氏名】鈴木 秀一
早期審査対象出願または早期審理対象出願 早期審査対象出願
個別代理人の代理人 【識別番号】100083806、【弁理士】、【氏名又は名称】三好 秀和
審査官 【審査官】西田 聡子
参考文献・文献 特開2008-124936(JP,A)
特開2006-191626(JP,A)
特開平10-173646(JP,A)
特開昭62-237834(JP,A)
特開昭62-81145(JP,A)
調査した分野 G09C 1/00
特許請求の範囲 【請求項1】
平文を入力する入力部と、
一の擬似乱数列を生成する擬似乱数生成部と、
前記第一の擬似乱数列を初期値として第の擬似乱数列を生成する公開可能な擬似乱数生成部と、
前記平文と前記第の擬似乱数列とを排他的論理和したデータに前記第一の擬似乱数列をヘッダとして付加したデータを再配置表を用いて一体化する変換処理部と、
前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理部と、
前記生成された暗号文を出力する出力部と、
を備えたことを特徴とする暗号装置。
【請求項2】
平文を入力する入力部と、
一の擬似乱数列を生成する擬似乱数生成部と、
前記第一の擬似乱数列を鍵として前記平文をブロック暗号化するブロック暗号文生成部と、
前記ブロック暗号化されたデータに前記第一の擬似乱数列をヘッダとして付与したデータを再配置表を用いて一体化する変換処理部と、
前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理部と、
前記生成された暗号文を出力する出力部と、
を備えたことを特徴とする暗号装置。
【請求項3】
暗号文を入力する入力部と、
前記暗号文を所定の分割数に分割し、再配置表を秘密鍵として用いて分割されたデータを元の配置に戻す逆再配置処理部と、
前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理部と、
前記第1のデータを初期値として擬似乱数列を生成する公開可能な擬似乱数生成部と、
生成された擬似乱数列と前記第2のデータとを排他的論理和したデータを平文として出力する出力部と、
を備えたことを特徴とする復号装置。
【請求項4】
暗号文を入力する入力部と、
前記暗号文を所定の分割数に分割し、再配置表を秘密鍵として用いて分割されたデータを元の配置に戻す逆再配置処理部と、
前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理部と、
擬似乱数列を生成する擬似乱数生成部と、
生成された擬似乱数列を鍵として用いることにより前記第2のデータをブロック復号化したデータを平文として出力する出力部と、
を備えたことを特徴とする復号装置。
【請求項5】
コンピュータを、
平文を入力する入力手段と、
一の擬似乱数列を生成する擬似乱数生成手段と、
前記第一の擬似乱数列を初期値として第の擬似乱数列を生成する公開可能な擬似乱数生成手段と、
前記平文と前記第の擬似乱数列とを排他的論理和したデータに前記第一の擬似乱数列をヘッダとして付加したデータを再配置表を用いて一体化する変換処理手段と、
前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理手段と、
前記生成された暗号文を出力する出力手段と、
して機能させることを特徴とする暗号プログラム。
【請求項6】
コンピュータを、
平文を入力する入力手段と、
一の擬似乱数列を生成する擬似乱数生手段と、
前記第一の擬似乱数列を鍵として前記平文をブロック暗号化するブロック暗号文生成手段と、
前記ブロック暗号化されたデータに前記第一の擬似乱数列をヘッダとして付与したデータを再配置表を用いて一体化する変換処理手段と、
前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理手段と、
前記生成された暗号文を出力する出力手段と、
して機能させることを特徴とする暗号プログラム。
【請求項7】
コンピュータを、
暗号文を入力する入力手段と、
前記暗号文を所定の分割数に分割し、再配置表を用いて分割されたデータを元の配置に戻す逆再配置処理手段と、
前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理手段と、
前記第1のデータを初期値として擬似乱数列を生成する公開可能な擬似乱数生成手段と、
生成された擬似乱数列と前記第2のデータとを排他的論理和したデータを平文として出力する出力手段と、
して機能させることを特徴とする復号プログラム。
【請求項8】
コンピュータを、
暗号文を入力する入力手段と、
前記暗号文を所定の分割数に分割し、再配置表を用いて分割されたデータを元の配置に戻す逆再配置処理手段と、
前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理手段と、
擬似乱数列を生成する擬似乱数生成手段と、
生成された擬似乱数列を鍵として用いることにより前記第2のデータをブロック復号化したデータを平文として出力する出力手段と、
して機能させることを特徴とする復号プログラム。
【請求項9】
請求項乃至のいずれか1項に記載のプログラムが記録されたコンピュータが読み取り可能な記録媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、既知平文攻撃を排除可能とする暗号装置及び暗号プログラム、これらの暗号装置及び暗号プログラムによって作成された暗号文を復号する復号装置及び復号プログラム、及びこれらのプログラムを記録する記録媒体に関する。
【背景技術】
【0002】
従来使用されてきた暗号方式(共通鍵暗号方式:ブロック暗号、ストリーム暗号)は、既知平文攻撃を許容する(非特許文献1)。既知平文攻撃とは、平文とその暗号文との組を多数用いて暗号鍵を特定する攻撃のことであり、線形攻撃や差分攻撃などがその代表的な手法である。DES(Data Encryption Standard)やAES(Advanced Encryption Standard)などの標準的なブロック暗号方式では、鍵スケジュールと10ラウンド以上のデータ攪拌とによって、これらの攻撃に対抗してきた。

【非特許文献1】“Cryptography: Theory and practice,3rd-Ed.”, Stinson, D.R., Chapman & Hall/CRC Press Inc. 2006.
【発明の開示】
【0003】
上記の手法においてセキュリティレベルを引き上げるためには、暗号鍵の長さを長くしたり、データ攪拌処理において使用されるS-BOXの非線形性を強くしたりする必要がある。しかし、その分、暗号化の速度が低下し、共通鍵暗号方式の従来の利点を損なう。また、既知平文攻撃に対して強い特別なS-BOXを設計する必要があり、そのための研究開発費や計算機資源も増大することになる。
【0004】
本発明は、上記の実情を鑑みて為されたものであり、既知平文攻撃を排除可能とすると共に、高速度で暗号化を行うことのできる暗号装置及び暗号プログラム、これらの暗号装置及び暗号プログラムによって作成された暗号文を復号化する復号装置及び復号プログラム、及びこれらのプログラムを記憶する記憶媒体を提供することを目的とする。
【0005】
本発明の第1の側面によれば、平文を入力する入力部と、第一の擬似乱数列を生成する擬似乱数生成部と、前記第一の擬似乱数列を初期値として第の擬似乱数列を生成する公開可能な擬似乱数生成部と、前記平文と前記第の擬似乱数列とを排他的論理和したデータに前記第一の擬似乱数列をヘッダとして付加したデータを再配置表を用いて一体化する変換処理部と、前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理部と、前記生成された暗号文を出力する出力部とを備えたことを特徴とする暗号装置が提供される。
【0006】
本発明の第2の側面によれば、平文を入力する入力部と、第一の擬似乱数列を生成する擬似乱数生成部と、前記第一の擬似乱数列を鍵として前記平文をブロック暗号化するブロック暗号文生成部と、前記ブロック暗号化されたデータに前記第一の擬似乱数列をヘッダとして付与したデータを再配置表を用いて一体化する変換処理部と、前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理部と、前記生成された暗号文を出力する出力部とを備えたことを特徴とする暗号装置が提供される。
【0007】
本発明の第3の側面によれば、暗号文を入力する入力部と、前記暗号文を所定の分割数に分割し、再配置表を秘密鍵として用いて分割されたデータを元の配置に戻す逆再配置処理部と、前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理部と、
前記第1のデータを初期値として擬似乱数列を生成する公開可能な擬似乱数生成部と、生成された擬似乱数列と前記第2のデータとを排他的論理和したデータを平文として出力する出力部とを備えたことを特徴とする復号装置が提供される。
【0008】
本発明の第4の側面によれば、暗号文を入力する入力部と、前記暗号文を所定の分割数に分割し、再配置表を秘密鍵として用いて分割されたデータを元の配置に戻す逆再配置処理部と、前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理部と、擬似乱数列を生成する秘密の擬似乱数生成部と、生成された擬似乱数列を鍵として用いることにより前記第2のデータをブロック復号化したデータを平文として出力する出力部とを備えたことを特徴とする復号装置が提供される。
【0009】
本発明の第5の側面によれば、コンピュータを、平文を入力する入力手段と、第一の擬似乱数列を生成する擬似乱数生成手段と、前記第一の擬似乱数列を初期値として第の擬似乱数列を生成する公開可能な擬似乱数生成手段と、前記平文と前記第の擬似乱数列とを排他的論理和したデータに前記第一の擬似乱数列をヘッダとして付加したデータを再配置表を用いて一体化する変換処理手段と、前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理手段と、前記生成された暗号文を出力する出力手段として機能させることを特徴とする暗号プログラムが提供される。
【0010】
本発明の第6の側面によれば、平文を入力する入力手段と、第一の擬似乱数列を生成する擬似乱数生手段と、前記第一の擬似乱数列を鍵として前記平文をブロック暗号化するブロック暗号文生成手段と、前記ブロック暗号化されたデータに前記第一の擬似乱数列をヘッダとして付与したデータを再配置表を用いて一体化する変換処理手段と、前記一体化されたデータを複数のブロックデータに分割し、前記再配置表を秘密鍵として用いることにより前記複数のブロックデータを重複することなく再配置したデータを暗号文として生成する再配置処理手段と、前記生成された暗号文を出力する出力手段として機能させることを特徴とする暗号プログラムが提供される。
【0011】
本発明の第7の側面によれば、コンピュータを、暗号文を入力する入力手段と、前記暗号文を所定の分割数に分割し、再配置表を秘密鍵として用いて分割されたデータを元の配置に戻す逆再配置処理手段と、前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理手段と、前記第1のデータを初期値として擬似乱数列を生成する公開可能な擬似乱数生成手段と、生成された擬似乱数列と前記第2のデータとを排他的論理和したデータを平文として出力する出力手段として機能させることを特徴とする復号プログラムが提供される。
【0012】
本発明の第8の側面によれば、コンピュータを、暗号文を入力する入力手段と、前記暗号文を所定の分割数に分割し、再配置表を秘密鍵として用いて分割されたデータを元の配置に戻す逆再配置処理手段と、前記再配置表を用いて逆再配置されたデータを逆変換し、逆変換されたデータを先頭から所定のデータ長を有する第1のデータと残りの第2のデータと分離する逆変換処理手段と、擬似乱数列を生成する秘密の擬似乱数生成手段と、生成された擬似乱数列を鍵として用いることにより前記第2のデータをブロック復号化したデータを平文として出力する出力手段として機能させることを特徴とする復号プログラムが提供される。
【0013】
本発明の第9の側面によれば、上記のプログラムのうちの少なくとも一つが記録されたコンピュータが読み取り可能な記録媒体が提供される。
【図面の簡単な説明】
【0014】
【図1】図1は、本発明に係る暗号方式の特徴をストリーム暗号において示した概念図である。
【図2】図2は、本発明に係る暗号装置の概略的な構成を示したブロック図である。
【図3】図3は、本発明に係る暗号化処理の手順を示したフローチャートである。
【図4】図4は、図3に示した暗号化処理における変換処理の具体的な手順を示したフローチャートである。
【図5】図5は、図3に示した暗号化処理における再配置処理の具体的な手順を示したフローチャートである。
【図6】図6は、図4に示した変換処理の一例を示した図である。
【図7】図7は、本発明に係る復号装置の概略的な構成を示したブロック図である。
【図8】図8は、本発明に係る復号化処理の手順を示したフローチャートである。
【図9】図9は、図8に示した復号化処理における逆再配置処理の具体的な手順を示したフローチャートである。
【図10】図10は、図8に示した復号化処理における逆変換処理の具体的な手順を示したフローチャートである。
【図11】図11は、本発明のその他の暗号装置の概略的な構成を示したブロック図である。
【図12】図12は、図11に示した暗号装置における暗号化の手順を示した概念図である。

【発明を実施するための最良の形態】
【0015】
図1は、本発明に係る暗号方式の特徴をストリーム暗号を用いて示した概念図である。図1に示すように、本発明の暗号方式は、
(1) 秘密の擬似乱数発生器Gで第一の擬似乱数列rと第ニの擬似乱数列Rとを生成するステップと、
(2) 第一の擬似乱数列rを初期値として公開可能な擬似乱数発生器Gで擬似乱数列rを生成するステップと、
(3) 平文xと擬似乱数列rとの排他的論理和をとり平文xを暗号化するステップと、
(4) 第一の擬似乱数列rをヘッダとして暗号文cに付加したデータ(r,c)をS-BOX(Substitution Box)などを用いて変換(一体化)処理するステップと、
(5) 変換されたデータdをn個のブロックB(i=0,1,・・・,n-1)に分割するステップと、
(6) 第二の擬似乱数列Rに基づき生成された再配置表Kを秘密鍵として用いることによりn個のブロックb(i=0,1,・・・,n-1)を重複することなく再配置させたデータを最終的な暗号文fcとして生成するステップと、
を備える。
【0016】
さらに、この暗号方式では、必要に応じて、ステップ(4)~(6)における変換処理から再配置処理までの処理を数回繰り返すステップを含めてもよい。
【0017】
なお、再配置表Kは、0,1,・・・,n-1までのn個の整数の重複のない十分にランダムな並び替えを表す表(再配置表)のことであり、以降では、K=(k[0],k[1],・・・,k[n-1])と表すことにする。再配置表Kは、暗号化処理を行うたびに、秘密の擬似乱数生成器Gが生成する第二の擬似乱数に基づき作成されるものであり、n!通りの可能性の中から一つが秘密鍵として選ばれる。
【0018】
また、上記(3)では、平文xと疑似乱数rとの排他的論理和をとったが、正確には、図1に示すように、疑似乱数rとの排他的論理和をとる対象は、平文xと、平文xのデータ長などの情報を含んだヘッダ情報と、必要に応じてパディングpとを合わせたものである。以降の実施例においては、ヘッダ情報uと平文xと必要に応じてパディングpとを合わせたデータを改めて平文xと見なす。
【0019】
本発明においては、この暗号方式を“再配置暗号”と称する。
【0020】
以下に、本発明の実施形態を、図面を用いて詳細に説明する。
【0021】
[暗号装置]
図2は、本発明に係る暗号装置の概略的な構成を示したブロック図である。暗号装置10は、入力部20と、第一擬似乱数生成部30と、第二擬似乱数生成部40と、変換処理部50と、再配置処理部60と、出力部70と、記憶部80と、制御部90とを備える。このうち、記憶部80と制御部90とを除く部分を暗号文生成部10Aと称することにする。
【0022】
入力部20は、送信者が平文xを入力するための入力インターフェースである。
【0023】
第一擬似乱数生成部30は、予測困難な擬似乱数列を生成する擬似乱数生成器であり、暗号装置10のシステムクロックや入力部20からの入力タイミングなどを利用することができるが、より乱数に近いものとして熱雑音などを用いることもできる。第一擬似乱数生成部30として熱雑音による擬似乱数生成器を用いた場合、その他の場合と比べてコストを低減できる。第一擬似乱数生成部30としては、毎回異なる擬似乱数を生成することが重要であるので、使い捨て擬似乱数生成器を用いてもよい。第一擬似乱数生成部30に使用される擬似乱数生成器は送信者と受信者の間で秘密にされる。第一擬似乱数生成部が生成する擬似乱数については、送信者、受信者を含め誰も一切知っている必要がない。
【0024】
第二擬似乱数生成部40は、統計的に偏りのない擬似乱数列を生成する擬似乱数生成器であり、メルセンヌ・ツイスターを用いることができる。メルセンヌ・ツイスターは、統計学的に優れた擬似乱数列を生成できるが、暗号学的には安全ではない。しかし、本発明においては、第一擬似乱数生成部30で生成した第一の擬似乱数列rを後述する変換処理部50による非線形変換と後述する再配置処理部60による再配置により秘匿にすることができるので、メルセンヌ・ツイスターの使用が可能である。第二擬似乱数生成器40に使用される擬似乱数生成器は送信者と受信者以外に対して公開してもよい。
【0025】
もちろん、第一擬似乱数生成部30としてメルセンヌ・ツイスターを使用してもよい。
【0026】
変換処理部50は、データを非線形的に変換する処理を行うS-BOXなどを含めた関数系から構成されるものであり、後述する変換処理を行う。
【0027】
再配置処理部60は、データをブロックに分割し、当該ブロックを再配置するための再配置表を含めた関数系から構成されるものであり、後述する再配置処理を行う。
【0028】
出力部70は、最終的に生成された暗号文を受信者へ出力するための出力インターフェースである。
【0029】
記憶部80は、入力部20~出力部70から成る暗号生成部10Aが生成した各種のデータの格納を行うサブメモリと、後述する暗号化処理の各ステップを実行するためのコンピュータに読み取り可能な暗号プログラムを格納するメインメモリとから構成される。記憶手段80は、RAM(Random Access Memory)やROM(Read Only Memory)などから構成される。さらに、記憶部80のサブメモリとメインメモリとを別体として構成し、メインメモリ部分を磁気ハードディスク、フロッピー(登録商標)ディスク、CD-ROMなどの光ディスク、磁気テープ、メモリチップ等に記憶させてもよい。
【0030】
制御部90は、記憶部80から読み出した暗号プログラムに従って、入力部20~記憶部80を制御するCPU(Central Processing Unit)を備える。
【0031】
本実施例では、暗号装置10を、暗号文生成部10A及び制御部90と、記憶部80とを一体化した構成としたが、記憶部80を独立した記憶装置として暗号文生成部10A及び制御部90とから切り離した構成としてもよい。いずれの構成においても、暗号装置10はコンピュータによって実現されるものであり、入力部20~出力部70は、制御部90により記憶部80から読み出された暗号プログラムに従って制御される。
【0032】
ここで、コンピュータとは、構造化された入力を所定の規則に従って処理し、処理した結果を構造化して出力する装置のことを指し、例えば、汎用コンピュータ、スーパーコンピュータ、メインフレーム、ワークステーション、マイクロコンピュータ、サーバ等が含まれる。また、通信ネットワーク(例えば、イントラネット、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、及びこれらの組み合わせから成る通信ネットワーク)を介して接続された2つ以上のコンピュータから成る構成(例えば、分散コンピュータシステム)であってもよい。
【0033】
また、ここでのコンピュータには、携帯電話やモバイル端末、家電製品や自動車などの制御チップ、コントローラ、ICカードに組み込まれた演算装置なども含まれる。
【0034】
[暗号化処理]
以上を前提として、図2に示した暗号装置10によって行われる再配置暗号について詳細に説明する。図3は、図2に示した暗号装置10によって行われる再配置暗号の処理手順を示したフローチャートである。
【0035】
送信者により入力部20から平文x(長さ:gワード)が入力されると、制御部90は、これを記憶部80に記憶させ、記憶部80に格納された暗号プログラムに従い、第一擬似乱数生成部30~生成部70に対して以下に示す処理を行うように促す。
【0036】
ステップS10において、制御部90は、第一擬似乱数生成部30に対して、第一の擬似乱数列r(長さ:aワード)を生成させ、これを記憶部80に記憶させる。なお、第一の擬似乱数列rの長さaは任意に設定することができる。
【0037】
<ヘッダrの生成アルゴリズムの実施例>
ステップS10における第一擬似乱数生成部30によるヘッダrの生成アルゴリズムは、以下のように記述される。
r: array[0..a-1] of the word;
Randomize; //initialize G0 by the clock;
for i:=0 to a-1 do
r[i]:=G0;
【0038】
次に、ステップS20において、制御部90は、記憶部80から予め格納された分割数nを読み出し、第一擬似乱数生成部30に対して、0,1,・・・,n-1までのn個の整数の疑似乱数列(第二の擬似乱数列)を生成させ、これを再配置表K=(k[0],k[1],・・・,k[n-1])として記憶部80に記憶させる。
【0039】
<再配置表Kの生成アルゴリズムの実施例>
ステップS20における第一擬似乱数生成部30による再配置表Kの生成アルゴリズムは、以下のように記述される。
k: array[0..n-1] of the word;
Randomize; //initialize G0 by the clock;
for i:=0 to a-1 do
k[i]:=i;
for i:=0 to N do
begin
s:=G0 mod n;
t:=G0 mod n;
x:=k[s];
k[s]:=k[t];
k[t]:=x;
end;
ここで、1ワードは8ビット、16ビット、または32ビットの符号なし整数を表す。また、ここでは、第一擬似乱数生成部30は、毎回1ワードの擬似乱数を出力するものとしている。
【0040】
なお、一般には、第一擬似乱数部30が生成する擬似乱数列は同じ数字の重複を含む。このとき、第二の擬似乱数列から生成される再配置表Kにおけるn個の数字(0,1,・・・,n-1)の並びには同じ数字の重複が生じてしまう。具体的には、分割数nが十分に大きければ、第一擬似乱数生成部30が生成する第二の擬似乱数列には同じ数字の重複が存在することはないと考えられるが、分割数nが小さい場合には、その可能性が生じる。そのような場合には、n個の数字の並びが重複せず、かつ十分ランダムに配列されるように工夫して再配置表Kを作成する必要がある。
【0041】
その場合、後述する[具体的な実装]における擬似乱数生成器G1を使い、生成した擬似乱数列を用いて数万回並べ替えることが考えられる。しかしながら、それよりも効率的な方法として、第一擬似乱数生成部30が生成する擬似乱数列を周期的に拡張して、拡張した擬似乱数列から再配置表Kを生成し、さらに、生成された再配置表Kの統計的な偏りを補正することにより最終的に所望の再配置表Kを得るという方法が考えられる。
【0042】
この方法は、次の3つのステップから構成される。
【0043】
{ステップ1}
第一擬似乱数生成部30において、短い擬似乱数列から256バイトの擬似乱数列を作成する。例えば、32バイトの擬似乱数列を256バイトの擬似乱数列に拡張するアルゴリズムは、以下のように記述される。
<実施例>
procedure set32byte;
var
i, j, a: integer
d: array[0..255] of byte;
begin
Randomize;
for i:=0 to 31 do
begin
j:=random(256);
d[i]:=j;
end;
for i:=32 to 255 do
begin
a:= i mod 32;
d[i]:=d[a];
end;
end;
{ステップ2}
【0044】
次に、記憶部80の擬似乱数列のメモリ領域に256バイトの擬似乱数列を順次格納していき、同じ数字が出たら次のメモリに格納するといった処理を繰り返すことにより再配置表Kを生成する。例えば、256バイトの擬似乱数列から256バイトの再配置表Kを生成するアルゴリズムは、以下のように記述される。
<実施例>
procedure generate256k;
var
d, st, k: array[0..255] of byte;
i: integer;
procedure seti; //dからkを作成する。
var
j: integer;
begin
if st[d[i]]=0 then
begin
k[d[i]]:=i;
st[d[i]]:=1;
end
else
begin
j:=(d[i]+19) and 255;
while st[j]=1 do
begin
j:=(j+67) and 255;
end;
k[j]:=i;
st[j]:=1;
end;
end;
begin
read_d;
clear_st;
for i:=0 to 255 do
begin
seti;
end;
end;
{ステップ3}
【0045】
次に、ステップ2で作成された再配置表Kの統計的な偏りを、例えば、以下に示すようなアルゴリズムを用いて補正する。
<実施例>
procedure revise;
var
k, k2: array[0..255] of byte;
i: integer;
begin
read_k;
for I:=0 to 255 do
begin
k2[i]:=k[255-k[i]];
end;
end;
【0046】
次に、ステップS30において、制御部90は、送信者により入力部20から入力された平文xを読み込み、これを平文xのデータ長gなどの情報を含んだヘッダ情報u(長さ:qワード)と共にこれを記憶部80に記憶させる。ここで、ヘッダ情報uの長さqは4ワードの符号なし整数として設定することができる。
【0047】
次に、ステップS40において、制御部90は、第一の擬似乱数列rを記憶部80から読み出し、第二擬似乱数生成部40に対して、第一の擬似乱数列rを初期値として、平文xと同じ長さ(nm-a-1ワード)の第二の擬似乱数列r=(r,r,・・・,rnm-a-1)を生成させ、これを記憶部80に記憶させる。
【0048】
なお、このステップにおいて、入力部20から入力される平文xの長さgが分割数nの倍数ではない場合には、制御部90は、v≡-a-q-g(mod n)となるような最小の非負整数vを算出し、パディングpとしてvワードの長さの擬似乱数列zを第一擬似乱数生成部30に生成させ、平文xの最後に付加する処理を行う。そして、制御部90は、ヘッダ情報u、平文x、パディングpを合わせたデータを改めて平文x=(u、x、z)=(x,x,・・・,xnm-a-1)として記憶部80に記憶させる。また、この場合、再配置処理において分割される各ブロックの長さを表す整数“m”は、m=(a+q+g+v)/nとして算出される。
【0049】
次に、ステップS50において、制御部90は、記憶部80から平文x=(x,x,・・・,xnm-a-1)と第二の擬似乱数列r=(r,r,・・・,rnm-a-1)とを読み出し、両者の排他的論理和をとる(c=x XOR r(i=0,1,・・・,nm-a-1))ことにより暗号文c=(c,c,・・・,cnm-a-1)を生成し、これを記憶部80に記憶させる。
【0050】
なお、本実施例では、このステップにおいて第二の擬似乱数列rと平文xとの間で一度に排他的論理和する構成としたが、その代わりに、制御部90は、ステップS40において第二の擬似乱数生成部40に対して1ワードづつ擬似乱数を生成させ、そのつど、ステップS50において平文xの1ワードと逐次的に排他的論理和する構成としてもよい。
【0051】
次に、ステップS60において、制御部90は、記憶部80から第一の擬似乱数列rと暗号文c=(c,c,・・・,cnm-a-1)とを読み出し、第一の擬似乱数列rを暗号文cのヘッダとして付加したデータ(r,c)=(c,c,・・・,cnm-1)を生成させ、これを改めてc=(r,c)=(c,c,・・・,cnm-1)として記憶部80に記憶させる。
【0052】
次に、ステップS70において、制御部90は、ステップS80~S100で行われる変換処理と分割処理と再配置処理とを1セットとした処理のラウンド数を表すCtを立て(Ct=1)、ステップS80へ処理を進める。
【0053】
ステップS80において、制御部90は、記憶部80からデータc=(c,c,・・・,cnm-1)を読み出し、変換処理部50に対して、例えば、図4に示すように、c(dm+i)mod nm=c(dm+i)mod nm+ci mod nm(i=0,1,・・・,nm-1)として加算した値(左辺のc(dm+i)mod nm)をS-BOXを用いてバイト単位で変換する変換処理を行わせ、変換されたデータをd=F(r、c)=(d,d,・・・,dnm-1)として記憶部80に記憶させる。ここで、“d”はブロック差分と呼ばれる整数であり、0<d<nの範囲で予め決められているものとする。また、図4に示した変換処理のフローチャートの中の関数wは、ワードとバイト配列の共用体であり、次の形式で記憶部80に記憶される。
Tunion=record
case integer of
1: (d:Word);
2: (h:array[0..3] of byte);
end;
w: Tunion;
ここでは、1ワードを4バイトとして扱っている。
【0054】
図6は、図4に示した変換処理のフローチャートにおいて、n=3,m=2,d=1の場合を視覚化したものである。この例では、記号A1~A3の処理で示したように、長さ2ワードのブロックデータを縦方向に順次積層し、記号A4の処理において積層した値をブロック単位で足し合わせ、最後に記号A5の処理において、ブロック単位でS-BOXを用いて変換することにより変換処理を行っている。
【0055】
なお、この変換処理は、可逆な変換(1対1対応の変換)であればどのような処理を行ってもよい。例えば、ここで用いた加算の変わりに減算を用いてよい。また、S-BOXについても、非線形な変換であればどのような関数系を用いてもよい。しかしながら、本発明の主旨からは、再配置表K=(k[0],k[1],・・・,k[n-1])から次のようにして生成されるS-BOXを用いることが好ましい。
【0056】
<再配置表KによるS-BOXの生成アルゴリズムの実施例>
再配置表K=(k[0],k[1],・・・,k[n-1])からは様々な方法でS-BOXを生成することができるが、ここでは簡単な実施例をあげる。
(n<=256のとき) for i:=0 to e-1 do
s[i]:=n+i;
for i:=e to 255 do
s[i]:=k[i-e];
(n>256のとき)
n-256≧e≧0となる整数eを一つ決める。
ct:=0;
for i:=0 to n-1 do
begin
if (k[i]-e>=0) and (k[i]-e<256) then do s[ct]:=k[i]-e;
ct:=ct+1
end;
end;
ここで、n=256のときはs=Kになり、変換処理における非線形な変換を施すために、再配置表Kそのものが利用できる。つまり、このときには、S-BOXは、0,1,・・・,255をランダムに並び替えたs=(k[0],k[1],・・・,k[255])となる。
【0057】
次に、ステップS90において、制御部90は、記憶部80から変換されたデータd=(d,d,・・・,dnm-1)を読み出し、再配置処理部60に対して、これを長さmワードのn個のブロックデータb=(dmi,dmi+1,・・・,dmi+m-1)(i=0,1,・・・,n-1)に分割させ、分割されたデータをd=(b,b,・・・,bn-1)として記憶部80に記憶させる。
【0058】
次に、ステップS100において、制御部90は、記憶部80から分割されたデータd=(b,b,・・・,bn-1)と再配置表K=(k[0],k[1],・・・,k[n-1])とを読み出し、再配置処理部60に対して、図5に示すように、分割されたデータd=(b,b,・・・,bn-1)を、再配置表K=(k[0],k[1],・・・,k[n-1])に基づき、d=(bk[0],bk[1],・・・,bk[n-1])のように再配置させ、これを記憶部80に記憶させる。なお、図5において、命令Move(x[i],y[j],z)は、x[i]のアドレスからy[j]のアドレスへzバイトの記憶内容をコピーする処理を表す。
【0059】
次に、ステップS110において、制御部90は、フラグCtの値をインクリメントし(Ct=2)、ステップS120において、インクリメントされた値が所定のラウンド回数hを越えたか否かを判定する。
【0060】
ステップS120において、制御部90によりインクリメントされた値が所定のラウンド回数hを越えたと判定された場合は、ステップS130に処理を進める。この場合、制御部90は、記憶部80から再配置されたデータd=(bk[0],bk[1],・・・,bk[n-1])を読み出し、最終的な暗号文fc=(bk[0],bk[1],・・・,bk[n-1])として出力部70に出力する。そして、出力部70は、後述する復号装置に対して暗号文fc=(bk[0],bk[1],・・・,bk[n-1])を送信してすべての処理を終了する。
【0061】
一方、ステップS120において、制御部90によりインクリメントされた値が所定のラウンド回数hを越えていないと判定された場合は、ステップS80に戻って、インクリメントされた値が所定のラウンド回数hを越えるまで、ステップS90~S100までの処理を繰り返した後、すべての処理を終了する。
【0062】
[暗号装置10の効果]
暗号装置10は、実質的に二つの鍵を用いて平文xを暗号化処理している。第一の鍵は、第一擬似乱数生成部(秘密の擬似乱数生成器)30により生成され、平文xにヘッダとして付加される第一の擬似乱数列rである。第二の鍵は、同じく第一擬似乱数生成部30により生成され、再配置処理の際に使用される第二の疑似乱数列から生成される再配置表Kである。これらの鍵を用いることによって、暗号装置10は、以下のような効果をもたらす。
【0063】
(1)第一擬似乱数生成部30は、平文を暗号化するたびに異なる第一の擬似乱数列を生成することができる。異なる第一の擬似乱数列を初期値として第二擬似乱数生成部(公開可能な擬似乱数生成器)40で生成される第の擬似乱数列の間には相関がほとんどないので、本暗号を既知平文攻撃することは極めて難しい。
【0064】
(2)第一擬似乱数生成部30が生成する第二の擬似乱数列に同じ数の重複する配列がない場合、第一擬似乱数生成部30はn!通りの可能性の中から秘密鍵として一つの再配列表Kを生成することができる。例えば、n>40の場合、その組み合わせは2159よりも大きくなり、さらに、最も実用的なn=256の場合、その組み合わせの数は21683を越えることになるので、鍵の全探索は事実上不可能になる。
【0065】
(3)分割数nを大きくすることに計算上のコストはかからない。また、本暗号は、擬似乱数の生成、整数の加算、メモリ内容のコピーといった高速処理が可能な演算のみから構成されているので、暗号化の実現速度は、現在標準の共通鍵方式であるAESと比較して極めて高速である。また、全体の演算回数も十分の一程度以下になる。
【0066】
(4)上記(2)で述べたように、本暗号の安全性は、データを分割し再配置したものを元に戻すことの計算量的困難さに基づいている。このことを考慮すると、本発明は長期間同じ鍵を使用しても高いセキュリティレベルが維持できる。
【0067】
(5)上記(4)の利点は、本暗号が長期間のデータ保存に適していることを意味する。このことから、本暗号は、従来の暗号化方式では対応できなかった分野、例えば、医療データ等の個人情報の長期保存、にも適用できる。
【0068】
(6)また、暗号装置10は、再配置処理部60を設けたことにより、同じ平文xと同じ第一の鍵(第一の擬似乱数列)r(長さ:kビット)とから、2通りの暗号文を生成できる。このことは、同じ平文xと同じ第一の鍵rとから、kの値を不定とした場合には毎回異なる暗号文が無数にできることを意味する。


【0069】
(7)さらに、暗号装置10においては、変換処理部50で用いられるS-BOXとして再配置表Kを利用することにより、その構成は0,1,・・・,n-1のn個の整数をランダムに配置するだけのものになるので、従来の暗号化方式におけるS-BOXの構成よりも簡単であり、S-BOXの研究開発にコストがかからない。
【0070】
[復号装置]
図7は、本発明に係る復号装置の概略的な構成を示したブロック図である。復号装置100は、入力部120と、公開可能な第二擬似乱数生成部140と、逆変換処理部150と、逆再配置処理部160と、出力部170と、記憶部180と、制御部190とを備える。このうち、記憶部180と制御部190とを除く部分を復号文生成部100Aと称することにする。
【0071】
入力部120は、送信者から送られてきた暗号文fcxを受信者が受け取るための入力インターフェースである。第二擬似乱数生成部140は、暗号装置10の第二疑似乱数生成部40と同様の構成を有する。逆再配置処理部160は、暗号装置10の再配置処理部60と同様の構成を有し、後述する逆再配置処理を行う。逆変換処理部150は、暗号装置10の変換処理部50と同様の構成を有し、後述する逆変換処理を行う。出力部170は、最終的に復号された復号文(平文x)を出力するための出力インターフェースである。
【0072】
記憶部180は、入力部120~出力部170から成る復号文生成部100Aが生成した各種のデータの格納を行うサブメモリと、後述する復号化処理の各ステップを実行するためのコンピュータに読み取り可能な暗号プログラムを格納するメインメモリとから構成される。
【0073】
制御部190は、記憶部180から読み出した復号プログラムに従って、入力部120~記憶部180を制御するCPUを備える。
【0074】
本実施例では、復号装置100を、復号文生成部100A及び制御部190と、記憶部180とを一体化した構成としたが、記憶部180を独立した記憶装置として復号文生成部100A及び制御部190とから切り離した構成としてもよい。いずれの構成においても、復号装置100はコンピュータによって実現されるものであり、入力部120~出力部170は、制御部190により記憶部180から読み出された暗号プログラムに従って制御される。
【0075】
[復号化処理]
以上を前提として、図7に示した復号装置100によって行われる復号化処理について詳細に説明する。図8は、図7に示した復号装置100によって行われる復号化の処理手順を示したフローチャートである。
【0076】
暗号装置10から送信された暗号文fc=(f,f,・・・,fnm-1)が入力部120から入力されると、制御部190は、これを記憶部180に記憶させ、記憶部180に格納された暗号プログラムに従い、第ニ擬似乱数生成部140~出力部170に対して以下に示す処理を行うように促す。
【0077】
ステップS200において、制御部190は、暗号装置10から送信された暗号文の長さnmを入力部120から読み込ませ、これを記憶部180に記憶させる。
【0078】
次に、ステップS210において、制御部190は、記憶部180から暗号文fcの長さnmと予め格納された分割数nとを読み出す。
【0079】
次に、ステップS220において、制御部190は、読み出した暗号文fcxの長さnmと分割数nとから、ブロックデータの長さmをm=nm/nとして算出する。
【0080】
次に、ステップS230において、制御部190は、ステップS240~S260で行われる分割処理と逆再配置処理と逆変換処理とを1セットとした処理のラウンド数を表すフラグCtを立て(Ct=1)、ステップS240へ処理を進める。
【0081】
ステップS240において、制御部190は、記憶部180から暗号文fc=(f,f,・・・,fnm-1)を読み出し、これをn個のブロックデータに分割して、分割されたデータをd=(bk[0],bk[1],・・・,bk[n-1])として記憶部180に記憶させる。
【0082】
次に、ステップS250において、制御部190は、記憶部180からデータd=(bk[0],bk[1],・・・,bk[n-1])と秘密鍵K=(k[0],k[1],・・・,k[n-1])とを読み出し、逆再配置処理160に対して、図9に示すように、k[i]番目のブロックデータbk[i]をbへと逆配置させ、逆配置されたデータをd=(b,b,・・・,bn-1)として記憶部180に記憶させる。
【0083】
次に、ステップS260において、制御部190は、記憶部180から逆配置されたデータd=(b,b,・・・,bn-1)を読み出し、逆変換処理部150に対して、例えば、図10に示すように、これをS-BOXを用いて逆変換させ、さらに、逆変換されたデータをd=(d,d,・・・,dnm-1)をc(dm+i)mod nm=c(dm+i)mod nm-ci mod nm(i=nm-1,nm-2,・・・,1,0)として減算する逆変換処理を行わせ、逆変換されたデータをc=(c,c,・・・,cnm-1)として記憶部180に記憶させる。
【0084】
ここで、逆変換とは、暗号装置10のS-BOXの非線形変換を表す関数sの逆関数isを用いた逆変換のことであり、次のプログラムで実現される。
for i:=0 to 255 do
is[s[i]]:=i;
【0085】
次に、ステップS270において、制御部190は、フラグCtの値をインクリメントし(Ct=2)、ステップS280において、インクリメントされた値が所定のラウンド数hを越えたか否かを判定する。
【0086】
ステップS280において、制御部190によりインクリメントされた値が所定のラウンド数hを越えたと判定された場合には、ステップS290に処理を進める。
【0087】
ステップS290において、制御部190は、記憶部180から逆変換されたデータc=(c,c,・・・,cnm-1)と予め格納された数値“a”とを読み出し、逆変換されたデ-タc=(c,c,・・・,cnm-1)の先頭からaワードをヘッダrとして規定し、逆変換されたデータcxを改めてc=(r(ヘッダ),c(残りのデータ))として記憶部180に記憶させる。
【0088】
次に、ステップS300において、制御部190は、記憶部180から逆一体化されたc=(r,c)を読み出し、第二擬似乱数生成部140に対して、ヘッダrを初期値としたnm-aワードの擬似乱数列r=(r,r,・・・,rnm-a-1)を生成させる。
【0089】
そして、ステップS310において、制御部190は、逆一体化された残りのデータc=(ca+1,ca+2,・・・,cnm-a-1)と生成された擬似乱数列r=(r,r,・・・,rnm-a-1)とを排他的論理和する(xa+i=ca+i XOR r(i=0,1,・・・,nm-a-1))ことにより、データx=(x,xa+1,・・・,xnm-1)を算出し、次いで、データxの先頭からqワードを平文xのデータ長gなどの情報を含んだヘッダ情報uとして切り取り、さらに、残りのデータの先頭からgワードのみを平文xとして復号し、これを記憶部180に記憶させる。
【0090】
なお、最後に切り捨てられたnm-q-gワードのデータはパディングである。
【0091】
そして最後に、ステップS320において、制御部190は、記憶部180から平文xを読み出し、出力部170に出力させて、全ての処理を終了する。
【0092】
一方、ステップS280において、制御部190によりインクリメントされた値が所定のラウンド数hを越えていないと判定された場合には、ステップS240に戻って、インクリメントされた値が所定のラウンド回数hを越えるまで、ステップS240~S260までの処理を繰り返した後、すべての処理を終了する。
【0093】
このように、復号装置100は、暗号装置10から送信されてきた暗号文fcxを復号するための情報として、秘密鍵としての再配置表K=(k[0],k[1],・・・,k[n-1])と、分割数nと、ヘッダの長さaと、ブロック差分dとを暗号装置10と共有している。これにより、復号装置100は、復号の過程で暗号文cfの本当の鍵とも言える擬似乱数列のヘッダrが入手でき、平文xの長さgも同様に入手できるので、擬似乱数列のパディングpを切り捨てることができる。
【0094】
[暗号装置と復号装置のその他の構成]
上記においては暗号装置と復号装置とを別体として説明したが、これはあくまで各装置の構成及び機能の説明を容易にするためである。上記の説明から明らかなように、本発明においても、従来の共通鍵方式と同様、暗号化処理と復号化処理とは可逆の関係にあるので、暗号装置と復号装置とを一体の構成とした装置に適用できることは明らかである。
【0095】
[具体的な実装]
本発明に係る暗号装置及び復号装置のプログラム上の実装例を示す。ここでは、1 ワードを1バイトとし、疑似乱数のヘッダrは256ビットを使用する。従って、a=32である。第一疑似乱数生成部30で生成する疑似乱数としては、コンピュータプログラミング環境で使用できる疑似乱数を用いる。具体的には、暗号装置のシステムクロックや送信者による入力部からの入力のタイミングなどを使用して再現しにくい疑似乱数をヘッダrとして使用する。また、分割数nはn=256、平文のデータ長gなどの情報を含むヘッダ情報uはu=4、ブロック差分d=1とする。このとき、秘密鍵KはK=(k[0],k[1],・・・,k[255])として表される再配置表であり、k[i](i=0,1,・・・,255)には、0,1,・・・,255を並べ替えた値が格納されている。
【0096】
平文x、ヘッダ情報u、疑似乱数のヘッダrをあわせた全データが1024バイトの倍数になるように、平文xの末尾に適当な長さvの疑似乱数をパディングする。そして、これを改めてx=(x,x,・・・,x256m-1)とする。ここで、x(i=0,1,・・・,255)は、LongWord(32ビット符号なし整数)である。
【0097】
なお、以降のプログラムの変数の中には、上記の実施例で使用した変数名が異なるものもあるが、混乱することはないはずである。
【0098】
<公開可能な疑似乱数生成部40の実装例>
d: array[0..7] of LongWord;
i; integer;
i:=0;
function g1: LongWord;
begin
w.d:=d[i and 7]+d[(i-1) and 7];
d[i and 7]:=w.d;
w.b[0]:=k[w,b[0]]; w.b[1]:=k[w.b[1]];
w.b[2]:=k[w,b[2]]; w.b[3]:=k[w.b[3]];
g1:=w.d; //va;ue of g1
i:=(i+1) and 7;
end;
ここで、wはLongWord(32ビット符号なし整数)dと4バイトの配列b[0],b[1],b[3]の共用体である。
【0099】
このような疑似乱数生成部40から生成される疑似乱数rと平文の疑似乱数のヘッダr以降の部分を排他的論理和して暗号化したものを、LongWordの配列として、改めてx=(x[0],x[1],・・・,x[v-1])(v=256m)とする。ここで、mは、ブロックデータの長さをLongWordの個数で表したものである。
【0100】
<変換処理の実装例>
i; integer;
begin
for i:=0 to v-m-1 do
begin
x[i+m]:=x[i+m];x[i];
w.d:=x[i+m];
w.b[0]:=k[w,b[0]]; w.b[1]:=k[w.b[1]];
w.b[2]:=k[w,b[2]]; w.b[3]:=k[w.b[3]];
x[i+m]:=w.d;
end;
for i:=v-m to v-1 do
begin
x[i+m-v]:=x[i+m-v]+x[i];
w.d:=x[i+m-v];
w.b[0]:=k[w,b[0]]; w.b[1]:=k[w.b[1]];
w.b[2]:=k[w,b[2]]; w.b[3]:=k[w.b[3]];
x[i+m-v]:=w.d;
end;
end;
【0101】
この処理の後、xをx=(y,y,・・・,y255)と256分割する。ここで、y=(x[mi],x[mi+1],・・・,x[mi+m-1])(i=0,1,・・・,255)である。
【0102】
<逆変換処理の実装例>
まず、逆置換ikを次のように計算しておく。
for i:=0 to 255 do
ik[k[i]]:=i;
逆置換ikを用いて逆変換を次のように計算する。
i; integer;
begin
for i:=v-1 downto v-m do
begin
w.d:=x[i+m-v];
w.b[0]:=k[w,b[0]]; w.b[1]:=k[w.b[1]];
w.b[2]:=k[w,b[2]]; w.b[3]:=k[w.b[3]];
x[i+m-v]:=w.d;
x[i+m-v]:=x[i+m-v]-x[i];
end;
for i:=v-m-1 downto 0 do
begin
w.d:=x[i+m]
w.b[0]:=k[w,b[0]]; w.b[1]:=k[w.b[1]];
w.b[2]:=k[w,b[2]]; w.b[3]:=k[w.b[3]];
x[i+m]:=w.d;
x[i+m]:=x[i+m]-x[i];
end;
end;
【0103】
この処理の後、xをx=(y,y,・・・,y255)と256分割する。ここで、y=(x[mi],x[mi+1],・・・,x[mi+m-1])(i=0,1,・・・,255)である。
【0104】
<再配置処理の実装例>
xと同じ長さの配列yを準備し、以下のように再配置処理する。ここで、命令Move(x[i],y[j],z)は、x[i]のアドレスからy[j]のアドレスへzバイトの記憶内容をコピーする処理を表す。この処理によって、配列xの内容を再配置表Kによってブロック単位で並べ替えることができる。
i; integer;
begin
for i:=0 to 255 do
begin
Move(x[i*m], y[k[i]*m], m);
end;
Move(y[0], x[0], 4*v);
end;
【0105】
なお、復号時に使用する逆再配置処理は以下のようにすればよい。
i; integer;
begin
for i:=0 to 255 do
begin
Move(x[k[i]*m], y[i*m], m);
end;
Move(y[0], x[0], 4);
end;
【0106】
この実装例は、1683ビットの鍵長のブロック暗号程度の安全性を持ち、AESの10倍程度の暗号化の実行速度が達成できる。
【0107】
[その他の実施例]
上記の実施例では、第二擬似乱数生成部40を用いたストリーム暗号によって高速な暗号装置10をデザインした。その他の実施例として、ストリーム暗号をブロック暗号に変えた構成を有する暗号装置が考えられる。
【0108】
図11は、その他の暗号装置の概略的な構成を示したブロック図である。暗号装置200は、入力部220と、第一擬似乱数生成部230と、ブロック暗号文生成部290と、変換処理部250と、再配置処理部260と、出力部270と、記憶部280と、制御部300とを備える。このうち、記憶部280と制御部300とを除く部分を暗号文生成部200Aと称することにする。
【0109】
このうち、入力部220と、第一擬似乱数生成部230と、変換処理部250と、再配置処理部260と、出力部270とは、それぞれ、入力部20と、第一擬似乱数生成部30と、変換処理部50と、再配置処理部60と、出力部70と同様の機能を有するので、説明を省略する。
【0110】
記憶部280は、入力部220~出力部270から成る暗号生成部200Aが生成した各種のデータの格納を行うサブメモリと、後述する暗号化処理の各ステップを実行するためのコンピュータに読み取り可能な暗号プログラムを格納するメインメモリとから構成される。
【0111】
また、制御部300は、記憶部280から読み出した暗号プログラムに従って、入力部220~記憶部280を制御するCPUを備える。
【0112】
なお、記憶部280及び制御部300のハードとして構成は、上記実施例と同様の構成なので、説明を省略する。
【0113】
[暗号化処理]
以上を前提として、図11に示した暗号装置200によって行われる再配置暗号について上記の実施例と異なる部分のみ説明する。図12は、図11に示した暗号装置200によって行われる再配置暗号の処理手順を示した概念図である。
【0114】
暗号装置200は、上記の実施例におけるストリーム暗号の代わりにブロック暗号を用いて本発明の再配置暗号を実現するものである。
【0115】
従って、ブロック暗号文生成部290において平文xをブロック暗号化する際に、平文xの長さがブロック長の倍数とならない場合には平文の最後にパディングをする必要が生じる。このとき、制御部300は、v≡-a-g-q(mod n)となるような最小の非負整数vを算出し、パディングpとしてvワードの長さの擬似乱数列zを第一擬似乱数生成部230に生成させ、平文xの最後に付加する処理を行う。そして、平文xのデータ長gなどの情報を含んだヘッダ情報u(長さ:qワード)、平文x、パディングqを合わせたデータを改めて平文x=(x、z)とした後、ブロック暗号化のステップへと処理を進める。この場合、再配置処理において分割される各ブロックの長さを表す整数“m”は、m=(a+q+g+p)/nとして算出される。
【0116】
次のステップとして、制御部300は、記憶部280から平文x(gワード)、平文xのデータ長などの情報を含んだヘッダ情報(qワード)、パディング(pワード)を読み出し、ブロック暗号文生成部290に対して、これらのデータを第一の擬似乱数列rを鍵として、公知のブロック暗号化を行わせる。
【0117】
以降の処理は、ストリーム暗号を用いた上記の実施例と同様なので、説明を省略する。
【0118】
このように、本発明の暗号をブロック暗号に用いた場合、ストリーム暗号に用いた場合よりも暗号化の実行速度は遅くなるが、その代わりに、従来使用されているAESなどの共通鍵方式を用いた暗号装置への実装が容易であるといった利点がある。
【0119】
[再配置暗号のNP完全性]
現在、世界標準の暗号として公開鍵暗号が広く採用されている。公開鍵暗号は、巨大数の素因数分解が現在のコンピュータ(ノイマン型コンピュータ)の能力では現実的な時間では行えないこと(素因数分解問題)などを安全性の根拠としている。しかし、近年急速に研究開発が進められている量子コンピュータを使うと、公開鍵暗号を解くために必要な素因数分解問題と離散対数問題を高速に解くことができることが証明されている(Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", In Proceeding of 35th IEEE FOCS, pp.124-134, Santa Fe, NM, Nov 20-22, 1994.)。このことは、将来、量子コンピュータが実用化されると、公開鍵暗号は、標準的な暗号方式としては実質的に使用できなくなることを意味する。
【0120】
しかし、当業者の間では、NP完全性を有する問題であれば量子コンピュータでも解く事ができないと考えられている。これに関し、本発明の再配置暗号による暗号文の解読問題はNP完全であることが以下のようにして示される。
【0121】
証明に当たって、まず次の3つの問題を設定する。
【0122】
(P1)ナップサック問題(部分和問題)Z:決定問題としてのナップサック問題とは、容量CのナップサックとN個の品物A(容量c,価値v)がある場合(i=1,2,・・・,N)に、このナップサックに詰め込める品物の組み合わせの中で価値の総計が所定値Vとなる組み合わせがあるか否かを判定する問題である。ここで、C,N,c,v,Vはすべて自然数である。この問題において、すべての品物についてc=vが成り立つ場合、これを部分和問題といい、以下のように定式化できる。
<部分和問題>
与えられた自然数x,x,・・・,x,yに対し、ある部分集合I⊂{1,2,・・・,N}が存在し、y=Σi∈Iとできるか?
【0123】
(P2)和ジグソーパズル問題Z:和ジグソーパズル問題と称する問題を新たに設定する。
<和ジグソーパズル問題>
与えられた自然数x,x,・・・,x,yに対し、ある置換(S-BOX)s∈Sと自然数mが存在し、y=Σi=Is(i)とできるか?
【0124】
(P3)再配置暗号ジグソーパズル問題Z:再配置暗号ジグソーパズル問題と称する問題を新たに設定する。
<再配置暗号ジグソーパズル問題>
与えられた自然数の配列X=(x,x,・・・,x)と自然数(平文)Wに対して、再配置暗号のある秘密鍵K(S-BOX又は再配置表)が存在し、D(X)=Wとできるか?ここで、Dは秘密鍵Kを用いた再配置暗号の復号化関数である。
【0125】
このとき、本願発明の再配置暗号による暗号文の解読問題がNP完全であることは、上記の3つの問題を多項式時間に帰着させることで次のように証明される。
【0126】
まず、ナップサック問題(部分和問題)ZはNP完全であることが既に知られている。そして、明らかに、ZはZに多項式時間帰着できる。つまり、
JP0004737334B2_000002t.gif
【0127】
次に、関数f(X,y,s,m)=(E(X,y,m),(X,Σi=1s(i),m),s)を定義する。ここで、Eは、sを用いた再配置暗号の暗号化関数である。関数fは、再配置関数sと暗号化関数Eで計算されるわけだが、その計算時間はO(n)程度であるので、ZはZに多項式時間帰着されることになる。つまり、関数fは多項式時間計算可能関数であり、
JP0004737334B2_000003t.gif。ここで、X=(x,x,・・・,x)へのsの作用をs(X)=(xs(1),xs(2),・・・,xs(N))とし、nを入力のサイズ(バイト数)とする(N≪n)。
【0128】
以上のことより、Z,Z,Zの各問題は、
JP0004737334B2_000004t.gifの順番に多項式時間帰着させることできることがわかる。上述したように、Z及びZはNP完全であるので、結論として、ZもNP完全であることが示されたことになる。
【0129】
このことより、統計的に偏りのない擬似乱数発生器を用いた場合、本発明の再配置暗号は量子コンピュータに対する耐性を持つと考えられる。実際に使用される擬似乱数発生器は統計的な偏りを持つわけだが、例えば、256個に分割された再配置暗号のブロックの順番を統計的に割り出すことは困難であると考えられる。
【0130】
[再配置暗号を用いたメッセージ認証]
上記で説明した実施形態においては、暗号文が改竄された場合、復号した平文から改竄を検知する機能は高くない。しかし、本暗号をハッシュ関数と組み合わせて使用することにより、この機能を補完することができる。
【0131】
これに関し、上述したように公開鍵暗号が量子コンピュータによって攻撃されるのと同様に、メッセージ認証に使われる鍵付きハッシュ関数(MAC:Message Authentication Code)も攻撃されると考えられる。
【0132】
これに対抗するために、本発明においては、次に示すように幾つかの応用例が考えられる。
【0133】
<応用例1>
hをMD5やSHA1などのハッシュ関数とし、送信するメッセージmをnバイトの配列X=(x,x,・・・,xn-1)に格納することを考える。このとき、次の手順で認証機能付きメッセージMを作成する。
【0134】
(S1)再配置暗号の秘密鍵K(S-BOX又は再配置表)を用いて、配列X=(x,x,・・・,xn-1)を(K[x],K[x],・・・,K[xn-1])と置換する。
【0135】
(S2)m’=E(h(X))=h(m)を計算する。
【0136】
(S3)オリジナルのメッセージmに対して、認証機能付きメッセージMをM=(m,m’)とする。
【0137】
このようにして作成された認証機能付きメッセージMが、共通鍵として秘密鍵Kを共有する通信において、攻撃者によって改竄されたか否かを、次のようにして確認することができる。
【0138】
メッセージMを受信した受信者は、h(X)とD(m’)を計算して、それらが一致するか否かを調べる。このとき、一致すればメッセージMは改竄されていないことが分かる。
【0139】
この応用例の利点として、通常、ハッシュ関数は必ず衝突があるので、小さい確率ではあるが,メッセージを改竄することができる。しかし、本応用例では、オリジナルのメッセージm及び秘密鍵Kが同じでも、それから作成されたm’は無数にあるので、攻撃者はメッセージの改竄に成功したか否かを確認することはできない。
【0140】
<応用例2>
応用例1の方向とは異なり、本発明の再配置暗号を利用して全く新しいMACを作成することも可能である。いま、再配置暗号の秘密鍵Kを、0,1,2,・・・,255を並べ替えた256バイトのS-BOXとする。そして、メッセージmをnバイトの配列X=(x,x,・・・,xn-1)に格納することを考える。このとき、次の手順で認証機能付きメッセージMを作成する。
【0141】
(S1)i=0,j=0とする。
【0142】
(S2)秘密鍵Kを用いて、配列X=(x,x,・・・,xn-1)を(K[x],K[x],・・・,K[xn-1])と置換する。
【0143】
(S3)x(j+1)mod n=x(j+i)mod n+xとし、その後、jをインクリメントする。
【0144】
(S4)j<nならば、(S3)へ行く。
【0145】
(S5)iをインクリメントする。
【0146】
(S6)i<Rならば、j=0として(S3)へ行く。ここで、Rは攪拌の回数を表す所定値であり、通常3回ぐらいに設定する。
【0147】
(S7)m’=E(x,x,・・・,xn’-1)=h(m)を計算する。
【0148】
ここで、n’はnよりも小さい自然数である。つまり、本応用例においては、一体化されたデータの一部を暗号化し、ハッシュ表として使用するので、このハッシュ表は平文の長さよりもずっと短い。
【0149】
この場合も、秘密鍵Kを共有する通信で、メッセージM=(m,m’)を受信した受信者は、(S1)~(S6)を実行し、(x,x,・・・,xn-1)とD(m’)が一致するか否かを調べることでメッセージ認証を行うことができる。この応用例はかなり高速で行うことができ、やはり、攻撃者がメッセージの改竄に成功したか否かを確認することはできない。
【0150】
<応用例3>
また、別の応用例として、メッセージの受信者は、ランダムな再配置暗号の秘密鍵K’を用いて、次の手順に従うことによって、送信者が送信内容を否認できないメッセージ認証を行うことができる。
【0151】
(S1)送信者は、<応用例2>のMACを計算し、M=(m,m’)を受信者に送信する。
【0152】
(S2)受信者は、ランダムな再配置暗号の秘密鍵K’を作成し、y=E(m,hK’(m))を作成して、送信者に送り返す。
【0153】
(S3)送信者は、D(y)=(m,hK’(m))を計算し、正当な通信であることを確認した後、m”=E(hK’(m))を計算し、(m,m”)を受信者に送り返す。
【0154】
(S4)受信者は、D(m”)を計算し、hK’(m)と一致するか否かを調べ、一致した場合には(m,K’,m”)を保存する。
【0155】
この応用例におけるMACの衝突は秘密鍵K’に依存する。送信者は、K’を知らないので、m”の衝突を計算できない。従って、送信者は、メッセージmの送信を否認できない。もちろん、第三者がこの通信内容を改竄することもできない。
【0156】
以上、幾つかの例を挙げて説明したように、本発明の再配置暗号を用いると、量子コンピュータによっても攻撃されないメッセージ認証を行うことができるので、これを電子決済の基本として電子商取引システムに適用すれば、将来的に量子コンピュータに対して耐性を有する電子商取引システムを開発することができる。その意味において、本発明の再配置暗号は、今後さらに活発化するであろう電子商取引システムの基盤と十分に成り得る暗号方式であると考えられる。
【0157】
なお、本発明は、上述した実施形態に限定されるものではなく、その要旨を逸脱しない範囲で構成要素を変形して具現化することができる。また、上記した実施形態に開示された構成要素を適宜組み合わせることにより各種の発明を形成することができる。例えば、各実施形態に示される構成要素から幾つかの構成要素を削除してもよい。また、ある実施形態に示される構成要素を別の実施形態に追加してもよい。さらに、異なる実施形態に亘って構成要素を適宜組み合わせてもよい。
【産業上の利用可能性】
【0158】
本発明によれば、既知平文攻撃を極めて困難にすると共に、暗号化の実行速度を極めて速くすることができる暗号装置及び暗号プログラム、これらの暗号装置及び暗号プログラムによって作成された暗号文を復号化する復号装置及び復号プログラム、及びこれらのプログラムを記憶する記憶媒体を提供することができる。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11