(57)【特許請求の範囲】
【請求項１】
乱数を生成するステップと、
長さの異なる乱数列を要素とする配列から前記乱数をインデックスとしてひとつの乱数列を得るステップと、
前記得られたひとつの乱数列に基づいて第一の平文を第一の変換方法により変換するステップと、
前記乱数と前記変換後の第一の平文を連結して第二の平文を作成するステップと、
前記第二の平文を第二の変換方法により変換するステップとを
含むコンピューターにより実行される暗号文作成方法。
【請求項２】
前記乱数列を要素とする配列の要素である各乱数列の長さは互いに素である
請求項１に記載の暗号文作成方法。
【請求項３】
乱数を生成する手順と、
長さの異なる乱数列を要素とする配列から前記乱数をインデックスとしてひとつの乱数列を得る手順と、
前記得られたひとつの乱数列に基づいて第一の平文を第一の変換方法により変換する手順と、
前記乱数と前記変換後の第一の平文を連結して第二の平文を作成する手順と、
前記第二の平文を第二の変換方法により変換する手順とを
コンピューターに実行させる含む暗号文作成プログラム。
【請求項４】
前記乱数列を要素とする配列の要素である各乱数列の長さは互いに素である
請求項３に記載の暗号文作成プログラム。
【請求項５】
乱数を生成する手段と、
長さの異なる乱数列を要素とする配列から前記乱数をインデックスとしてひとつの乱数列を得る手段と、
前記得られたひとつの乱数列に基づいて第一の平文を第一の変換方法により変換する手段と、
前記乱数と前記変換後の第一の平文を連結して第二の平文を作成する手段と、
前記第二の平文を第二の変換方法により変換する手段とを
含む暗号文作成システム。
【請求項６】
前記乱数列を要素とする配列の要素である各乱数列の長さは互いに素である
請求項５に記載の暗号文作成システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピューターによる暗号化の方法、特に、既知平文攻撃に対して安全性が高い暗号化の方法に関する。
【背景技術】
【０００２】
今日の情報通信技術において暗号化技術はきわめて重要である。暗号化技術では、さまざまな暗号解読手法に対して安全であること、すなわち、暗号鍵の入手なしに現実的な計算時間で暗号文から平文を得られるようなことがないことが求められる。【０００３】
暗号解読手法のひとつに既知平文攻撃がある。これは、既知の特定の平文に対応する暗号文を入手できる場合に、その他の暗号文から対応する平文を求める攻撃である。通信プロトコルの標準等に基づいて平文データの最初の部分が固定、通番、あるいは、タイムスタンプ等である場合には、暗号文に対応する平文が推測しやすいため、既知平文攻撃に対する安全性は暗号化方式における重要な要件である。【０００４】
暗号化鍵の長さを単に長くするだけでは、既存の業界標準との整合性や計算量の点で課題がある。業界標準の暗号化方式に基づいて、既知平文攻撃に対する安全性を強化できることが望ましい。【０００５】
また、符号化率を極端に悪化させないこと、すなわち、平文と比較した暗号文の情報量が極端に大きくならないことも必要である。【０００６】
さらに、今日の情報通信技術の環境では、不定長のデータ（たとえば、デジタル化した電話音声）の暗号化も求められるため、ブロック暗号だけではなく、ストリーム暗号にも対応できることが望ましい。【０００７】
平文・初期化ベクトル・暗号化鍵などの外部入力とは独立した秘密情報を個々の暗号化の前処理として適用することにより、複数の平文暗号文ペアを情報源として用いる既知平文攻撃における計算量を増加させ、安全性を強化することが可能である。【０００８】
たとえば、特許文献１では、平文の全ビットを元にした秘密情報により平文を隠蔽する方法が開示されている。【０００９】
しかし、特許文献１に係る方法では、ストリーム暗号に適用する場合に、適用するメモリ領域を全てキャッシュとして保持して、それの領域全体を二回走査する必要があるため、膨大な記憶容量を必要とする可能性があるという課題がある。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許出願公開第２００３／０１９１９５０号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１１】
符号化率が良好であり、ストリーム暗号に適した、既知平文攻撃に対して安全性が高い暗号化方式、システム、および、プログラムを提供する。
【課題を解決するための手段】
【００１２】
本願発明は、乱数を生成するステップと、互いに相関関係にない長さの異なる乱数列の集合から、前記乱数に基づいてひとつの乱数列を選択するステップと、前記選択されたひとつの乱数列に基づいて第一の平文を第一の変換方法により変換するステップと、前記乱数と前記変換後の第一の平文を連結して第二の平文を作成するステップと、前記第二の平文を第二の変換方法により変換するステップとを含む暗号文作成方法を提供することで上記課題を解決する。【００１３】
また、本願発明は、前段に加えて、前記第一の変換方法は、前記選択されたひとつの乱数列をくり返し連結した乱数列と前記第一の平文との排他的論理和演算である暗号文作成方法を提供することで上記課題を解決する。【００１４】
また、本願発明は、乱数を生成する手順と、互いに相関関係にない長さの異なる乱数列の集合から、前記乱数に基づいてひとつの乱数列を選択する手順と、前記選択されたひとつの乱数列に基づいて第一の平文を第一の変換方法により変換する手順と、前記乱数と前記変換後の第一の平文を連結して第二の平文を作成する手順と、前記第二の平文を第二の変換方法により変換する手順とをコンピューターに実行させる暗号文作成プログラムを提供することで上記課題を解決する。【００１５】
また、本願発明は、前段に加えて、前記第一の変換方法は、前記選択されたひとつの乱数列をくり返し連結した乱数列と前記第一の平文との排他的論理和演算である暗号文作成プログラムを提供することで上記課題を解決する。【００１６】
また、本願発明は、乱数を生成する手段と、互いに相関関係にない長さの異なる乱数列の集合から、前記乱数に基づいてひとつの乱数列を選択する手段と、前記選択されたひとつの乱数列に基づいて第一の平文を第一の変換方法により変換する手段と、前記乱数と前記変換後の第一の平文を連結して第二の平文を作成する手段と、前記第二の平文を第二の変換方法により変換する手段とを含む暗号文作成システムを提供することで上記課題を解決する。【００１７】
また、本願発明は、前段に加えて、前記第一の変換方法は、前記選択されたひとつの乱数列をくり返し連結した乱数列と前記第一の平文との排他的論理和演算である暗号文作成システムを提供することで上記課題を解決する。
【発明の効果】
【００１８】
従来型の暗号化方式と組み合わせることで、符号化率が良好であり、ストリーム暗号に適した、既知平文攻撃に対して安全性が高い暗号化方式、システム、および、プログラムを提供することができる。
【図面の簡単な説明】
【００１９】
【図１】本願発明の一実施形態に係る情報システムの構成図である。
【図２】本願発明の一実施形態に係る乱数列マトリックスの例である。
【図３】本願発明の一実施形態に係る暗号化および復号化処理の全体を表わすフローチャートである。
【図４】本願発明の一実施形態に係る暗号化の前処理を表わすフローチャートである。
【図５】本願発明の一実施形態に係る復号の後処理を表わすフローチャートである。
【発明を実施するための形態】
【００２０】
以下、図を参照しながら、本願発明の実施形態の一例について説明する。
【００２１】
図１は、本願発明の一実施形態に係る情報システム（101）の機能構成図である。当該情報システム（101）、および、その各機能は、一般的なコンピューター機器を使用して実現可能である。コンピューター機器はクラウドサービス等によって提供される仮想コンピューティング資源であってよい。
【００２２】
暗号化前処理機能（102）は、従来型暗号化処理機能（103）に先だって変換処理を行なう機能である。当該処理の内容は図４に示されており、後述する。
【００２３】
従来型暗号化処理機能（103）は、一般的な暗号化方法（たとえば、DES）による暗号化（平文から暗号文への変換）を行なう機能である。当該機能は周知技術であるためこれ以上の説明は行なわない。
【００２４】
従来型復号処理機能（104）は、一般的な暗号化方法（たとえば、DES）による復号（暗号文から平文への変換）を行なう機能である。当該機能は周知技術であるためこれ以上の説明は行なわない。
【００２５】
復号後処理機能（105）は、従来型復号処理機能（104）の後の処理を行なう機能である。当該処理の内容は図５に示されており、後述する。
【００２６】
平文（106）は、本願発明に係る暗号化処理の入力、あるいは、復号処理の出力となるデータである。ハードディスクなどの不揮発性の記憶領域に保存されていてもよく、メインメモリ上の一時データであってもよい。また、本願発明に係る情報システム（101）の外部の情報システムから直接供給される形態でもよい。
【００２７】
暗号文（107）は、本願発明に係る暗号化処理の出力、あるいは、復号処理の入力となるデータである。ハードディスクなどの不揮発性の記憶領域に保存されていてもよく、メインメモリ上の一時データであってもよい。本願発明に係る情報システム（101）が外部の情報システムに直接供給する形態でもよい。
【００２８】
乱数列マトリックス（108）は、暗号化前処理機能（102）および復号後処理機能（105）で使用されるパラメーターである乱数列を保存する手段である。不揮発性の記憶領域に保存されていてもよく、メインメモリ上の一時データであってもよい。また、本願発明に係る情報システム（101）の外部のシステムから直接供給されてもよい。乱数列マトリックス（108）の内容は図２に示されており、後述する。
【００２９】
図２は、本願発明の一実施形態に係る乱数列マトリックス（108）の例である。2^n（ここで、nは自然数）種類の互いに独立した乱数列の集合を仕様として定める。当該仕様は、誰でも入手可能な公開仕様として定めてもよく、通信を行なう当事者間で事前に交換するようにしてもよい。乱数列インデックスを指定することで、乱数列マトリックス中の特定の乱数列を指定することができる。
【００３０】
なお、乱数列の長さが固定であると、その固定長に相当する周期に注目することで乱数性を排除できてしまう可能性があるため、それぞれの乱数列の長さは異なり、かつ、互いに素であることが望ましい。
【００３１】
図３は、本願発明の一実施形態に係る暗号化処理および復号処理をの全体像を表わすフローチャートである。各処理ステップを表わす長方形の左側に位置するデータ項目はその処理ステップの入力を表わし、右側に位置するデータ項目はその処理ステップの出力を表わす（以下同様）。本願発明に係る暗号化処理は、暗号化前処理（S301）と一般に使用されている暗号化処理（S302）（たとえば、DES）の組み合わせとして行なわれるものである。また、本願発明に係る復号処理は、一般に使用されている復号処理（S303）（たとえば、DES）と復号後処理（S304）の組み合わせとして行なわれるものである。
【００３２】
図４は、本願発明の一実施形態に係る暗号化前処理（S301）の詳細を表わすフローチャートである。以下、各処理ステップについて説明する。
【００３３】
（S401）
nビットの乱数を平文・初期化ベクトル・暗号鍵・時刻とは無関係に自動的に決定する。これにより、同じ条件下でも乱数は独立して決定され、2^-nの確率でしか偶然の一致はあり得なくなる。このような乱数は、たとえば、物理乱数により実現可能である。決定した乱数を乱数インデックスとして一時的に保存する。
【００３４】
（S402）
乱数列マトリックス（108）から、S401で求めた乱数列インデックスに対応する乱数列を求め、一時的に保存する。
【００３５】
（S403）
S402で求めた乱数列を使用して平文を変換し迷彩文を求める。この変換（難読化）アルゴリズムは、その逆変換が容易であること、および、データサイズを増加させないことが望ましい。たとえば、これらの条件を満足する方法として、乱数列を平文のデータ長に合うよう反復した上で、平文との排他的論理和演算を行なうことが望ましい。
【００３６】
（S404）
S403で得られた迷彩文と乱数列インデックスを連結して、従来型の暗号処理（S302）の対象となる平文（前処理済平文）とする。ここで、連結には、迷彩文の先頭に乱数インデックスを連結する処理、迷彩文の末尾に乱数インデックスを連結する処理、あるいは、迷彩文の所定の位置に乱数インデックスを埋め込む処理を含むものとする。前処理済平文は元々の平文と比較してデータ量が増すが、その増分は平文サイズの大小にかかわらず、乱数列インデックスのビット幅のみに限定され、符号化率を大きく悪化させることはない。
【００３７】
図５は、本願発明の一実施形態に係る復号後処理（S304）の詳細を表わすフローチャートである。以下、各処理ステップについて説明する。
【００３８】
（S501）
従来型復号処理方法（たとえば、DES）により復号された後処理対象平文を分離し、乱数列インデックスと迷彩文を得る。乱数列インデックスの長さ、および、挿入位置は仕様として定まっているため、この処理の内容は自明である。
【００３９】
（S502）
乱数列マトリックス（108）において、S501で求めた乱数列インデックスに対応する乱数列を求め一時的に保存する。
【００４０】
（S503）
S502で求めた乱数列を使用して迷彩文を変換し平文を求める。この変換処理は、S403で行なわれた処理の逆変換である。たとえば、S403で乱数列を必要な回数繰り返して、排他的論理和演算を行なったのであれば、同じ演算を再度行なえばよい。
【００４１】
（本方式による暗号化の安全性の説明）
以下に、本願発明に係る暗号化方式の既知平文攻撃に対する安全性の高さについて説明する。
【００４２】
乱数列インデックスは処理内における独自の乱数源から生成され、最終的に暗号化されることにより秘匿性が保証される。どの乱数列インデックスが使用されるかは推測も強制も不可能である。以下では、乱数列インデックスのビット幅をnとし、既知平文攻撃で必要な平文暗号文ペアの個数をmとし、暗号化で使用する鍵のビット幅をLとする。
【００４３】
既知平文攻撃による攻撃者が、複数の平文と暗号文ペアを所有している場合でも、各ペアは独立した乱数列インデックスを持つ。従って、複数の平文暗号文ペアを処理する場合には、(2^n)^m = 2^(n*m)種類の組み合わせを総当りする必要がある。一方、全数検索（総当たり方式）での処理回数は 2^L 回である。
【００４４】
全数検索における一回のチェック実行の処理内容は、復号して確認することのみである。一方、既知平文攻撃では、一回のチェック実行の処理内容は、上記の処理に加えて、組み合わせで得たペアで鍵を解読する処理から成る。ゆえに、全数検索での１回あたりのチェック処理時間をT1、既知平文攻撃での１回あたりのチェック処理時間をT2とすると、T1＜＝T2である。
【００４５】
既知平文攻撃が成功するということは、全数検索よりも速く鍵を特定できることを意味する。計算量の総計は、実行あたりの計算量に計算回数を掛けたものであることから、既知平文攻撃が成功するという条件は T1 * 2^L ＞ T2 * 2^(n*m) という不等式で表わされる。
【００４６】
T1 ＜＝ T2 により T1 * 2^L ＞ T2 * 2^(n*m) は、以下の通り、2^L ＞ 2^(n*m) に変形される。
T1 * 2^L ＞ T2 * 2^(n*m) 
→ T1/T2 * 2^L ＞ 2^(n*m) 
→ (1 ＞＝ T1/T2 なので) 1 * 2^L ＞＝ T1/T2 * 2^L ＞ 2^(n*m) 
→ 2^L ＞ 2^(n*m) 
そしてmの条件を掃き出すと、以下の通り、L/n ＞ m となる。
2^L ＞ 2^(n*m) 
→ (L＞0, n＞0, m＞0 なので) Log(2^L) ＞ Log(2^(n*m)) 
→ L * Log(2) ＞ n * m * Log(2) 
→ L ＞ n * m
→ L/n ＞ m
【００４７】
例えば乱数列インデックスが8ビットという取り決めの元に本発明に係る暗号化方法を適用すると、既知平文攻撃が成功したとみなされる条件は、鍵長が256ビットの暗号では、32個未満の平文暗号文ペアで解読できた場合であり、鍵長が56ビットの暗号では既知平文攻撃を行う場合、7個未満の平文暗号文ペアで解読できた場合である。
【００４８】
現状の既知平文攻撃において、平文暗号文ペアの個数は処理量とは相関しないと考えられているため、理論的な上限はないが、本発明は、平文暗号文ペアの個数に明確な制限を課すことができる点で有利である。
【００４９】
（本発明の技術的に顕著な効果）
本発明は、従来型の一般的暗号化方式との組み合わせにより容易に実現できる一方で、符号化率が良好であり、平文を複数回走査する必要がないためストリーム暗号においても利用しやすく、加えて、従来型暗号化方式の暗号鍵の長さが仕様により固定されている場合でも本発明に係る方式を追加することで、暗号化方式全体としての強度、とりわけ、既知平文攻撃に対する安全性を強化できる。
【図１】
0005992651.tif 000002
【図２】
0005992651.tif 000003
【図３】
0005992651.tif 000004
【図４】
0005992651.tif 000005
【図５】
0005992651.tif 000006