(57)【要約】  MISTY構造のデータ変換関数、例えば、ＭＩＳＴＹ１のＦＯ関数の処理において、２段目のMISTY構造内のＦＩ関数６０２の処理結果と１段目のMISTY構造内の排他的論理和６１２の論理演算結果ｔ１との排他的論理和６１４の論理演算結果ｔ３をレジスタに格納しない。その論理演算結果ｔ３は、排他的論理和６４３、６４４により、排他的論理和６４２、６４３の論理演算結果と、直接に、排他的論理和する。
2009090689.tif 000002
【特許請求の範囲】
【請求項１】
２ｎビットのデータＬをデータ変換するデータ処理手段と、該データ処理手段の処理結果と２ｎビットのデータＲとを排他的論理和する排他的論理和演算器を備える暗号化装置において、
ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲ、ｎビットのデータ“０”または前記第１のレジスタに格納されているｎビットのデータのいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、該第２の排他的論理和演算器の出力を前記第１のレジスタに出力するデマルチプレクサと、前記第２の排他的論理和演算器の出力またはラウンド鍵ＫＯim（ｍは自然数）を選択出力する第３のマルチプレクサと、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記第３のマルチプレクサの出力とを排他的論理和する第３の排他的論理和演算器と、前記第２のマルチプレクサの出力と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備え、
前記第１のマルチプレクサ、前記第２のマルチプレクサ、前記第３のマルチプレクサ及び前記デマルチプレクサは外部から制御され、前記第１のレジスタは前記デマルチプレクサの出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納することを特徴とする暗号化装置。
【請求項２】
２ｎビットのデータＬをデータ変換するデータ処理手段と、該データ処理手段の処理結果と２ｎビットのデータＲとを排他的論理和する排他的論理和演算器を備える暗号化装置において、
ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲまたはｎビットのデータ“０”のいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、前記第２の排他的論理和演算器の出力またはラウンド鍵ＫＯimを選択出力する第３のマルチプレクサと、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記第３のマルチプレクサの出力とを排他的論理和する第３の排他的論理和演算器と、前記第２の排他的論理和演算器と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備え、
前記第１のマルチプレクサ、前記第２のマルチプレクサ及び前記第３のマルチプレクサは外部から制御され、前記第１のレジスタは前記第２の排他的論理和演算器の出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納することを特徴とする暗号化装置。
【請求項３】
２ｎビットのデータＬをデータ変換するデータ処理手段と、該データ処理手段の処理結果と２ｎビットのデータＲとを排他的論理和する排他的論理和演算器を備える暗号化装置において、
ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲまたはｎビットのラウンド鍵ＫＯim（ｍは自然数）のいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、該第２の排他的論理和演算器の出力を入力し、その入力を適切なタイミングで出力する出力手段と、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記スイッチ手段の出力とを排他的論理和する第３の排他的論理和演算器と、前記第２の排他的論理和演算器と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備え、
前記第１のマルチプレクサ、前記第２のマルチプレクサ及び前記出力手段は外部から制御され、前記第１のレジスタは前記第２の排他的論理和演算器の出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納することを特徴とする暗号化装置。
【請求項４】
請求項３記載の暗号化装置であって、
前記出力手段は、ｎビットの“０”データまたは前記第２の排他的論理和演算器の出力を選択出力する第３のマルチプレクサであることを特徴とする。
【請求項５】
請求項１乃至３のいずれか１項に記載の暗号化装置であって、
さらに、前記データＬを入力・保持し、出力する第３のレジスタを備えていることを特徴とする。
【請求項６】
２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータＲの他的論理和を演算した後、その論理演算結果を出力する暗号処理方法において、
前記データＬの上位ｎビットＬＬを拡大鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を出力するサイクル１のステップと、
前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果を前記サイクル１のステップで出力される論理演算結果ｔ１と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記データＲの下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル２のステップと、
前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果をラウンド鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル２で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとすると共に、前記サイクル２のステップで出力される上位ｎビットＲＬをラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップと、
を備えることを特徴とする暗号処理方法。
【請求項７】
２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータの排他的論理和を演算した後、その排他的論理和の論理演算結果を出力する暗号処理方法において、
前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を前記データRの下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ１を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル１のステップと、
前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果ｔ３を前記サイクル１のステップで出力されるＲＬと排他的論理和してＲＬとして出力し、さらにｔ３をサイクル１のステップで出力されるＲＲと排他的論理和してＲＲとして出力するサイクル２のステップと、
前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル２で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとすると共に、前記サイクル２のステップで出力される上位ｎビットＲＬをラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップと、
を備えることを特徴とする暗号処理方法。
【請求項８】
２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータＲの排他的論理和を演算した後、その排他的論理和の論理演算結果を出力する暗号処理方法において、
前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を前記データRの下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ１を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル１のステップと、
前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果をラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記データＲの下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル２のステップと、
前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル２で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果をラウンド鍵KOi4と排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記サイクル２のステップで出力される上位ｎビットＲＬを出力するサイクル３のステップと、
を備えることを特徴とする暗号処理方法。
【請求項９】
コンピュータに、２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータＲの排他的論理和を演算した後、その排他的論理和の論理演算結果を出力する暗号処理を実行させるプログラムであって、
前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を出力するサイクル１のステップと、
前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果を前記データＲの下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとすると共に、前記データＲの上位ｎビットＲＬをラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル２のステップと、
前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果を前記サイクル１のステップで出力される論理演算結果ｔ１と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記サイクル２で出力された下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記サイクル２で出力された上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップと、
から構成される処理を、コンピュータに実行させるプログラム。
【請求項１０】
コンピュータに、２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータＲの排他的論理和を演算した後、その排他的論理和の論理演算結果を出力する暗号処理を実行させるプログラムであって、
前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を出力すると共に、前記論理演算結果ｔ１を前記データRの下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ１を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル１のステップと、
前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル１で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとすると共に、前記サイクル１のステップで出力される上位ｎビットＲＬをラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル２のステップと、
前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果をラウンド鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果を前記サイクル１のステップで出力される論理演算結果ｔ１と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記データＲの下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップと、
から構成される処理をコンピュータに実行させるプログラム。
【請求項１１】
コンピュータに、２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータＲの排他的論理和を演算した後、その排他的論理和の論理演算結果を出力する暗号処理を実行させるプログラムであって、
前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果をｔ１として出力し、前記論理演算結果ｔ１を前記データRの下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ１を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル１のステップと、
前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果をラウンド鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル２で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果をサイクル２で出力された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記サイクル２のステップで出力される上位ｎビットＲＬを出力するサイクル３のステップと、
前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果をラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記データＲの下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップと、
から構成される処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通暗号鍵方式を適用した暗号化装置、暗号化方法及びプログラムに係り、特にMISTY構造のデータ変換関数を利用する暗号化装置、暗号化方法及びプログラムに関する。
【背景技術】
【０００２】
暗号方式は、公開鍵方式と共通鍵方式に大別される。公開鍵方式は、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うために鍵（公開鍵）を一般に公開する代わりに、暗号文を復号するための鍵（秘密鍵）を受信者のみの秘密情報とすることで送信情報の安全性を保つ方式である。これに対し、共通鍵方式は、暗号化と復号で同一の鍵（秘密鍵）を用いる方式であり、秘密鍵を送信者と受信者以外の第三者に分からない情報とすることで、送信情報の安全性保つ方式である。
共通鍵方式の暗号（以下、共通鍵暗号と呼ぶ）は、公開鍵方式の暗号（以下、公開鍵暗号と呼ぶ）と比較した場合、処理速度が速くコンパクトに実装できるという利点がある。このため、携帯電話やＩＣカードなどの小型機器に暗号化機能を付加する場合には、共通鍵暗号が利用される。また、処理速度が高速であり、情報をリアルタイムで暗号化／復号化できるので、放送や通信分野における情報通信にも利用されている。【０００３】
共通鍵暗号には、ストリーム暗号とブロック暗号がある。ブロック暗号は、平文（暗号化の対象となる文）を一定のビット長のまとまり（これを、ブロックと呼ぶ）に分割し、ブロック単位で暗号化を行う。尚、暗号化の処理単位であるブロックのビット長は“ブロック長”と呼ばれる。【０００４】
共通鍵暗号方式のブロック暗号は、ブロック長に応じて様々なアルゴリズムが知られている。代表的なものとしては、ＤＥＳ、ＡＥＳ、ＳＣ２０００、ＭＩＳＴＹ１、ＭＩＳＴＹ１２、ＫＡＳＵＭＩなどがある。これらの共通鍵暗号のアルゴリズムは、ソフトウェアもしくはハードウェアにより実装される。【０００５】
ここで、共通鍵暗号の一つであるＭＩＳＴＹ１について説明する。ＭＩＳＴＹ１は、ブロック長６４ビット、鍵長１２８ビットの共通鍵暗号である。尚、ＭＩＳＴＹ１は、例えば、ＩＰＡ（Information-technology Promotion Agency）のホームページ(http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/5_02jspec.pdf)に公開されている（非特許文献１参照）。【０００６】
図１は、ＭＩＳＴＹ１の暗号化処理の基本構造を示す図である。この図１は、非特許文献１の図１ａを簡略化したものである。
図１に示すように、ＭＩＳＴＹ１はFeistel型暗号である。ＭＩＳＴＹ１は、ＦＬ関数１０、ＦＯ関数２０及び排他的論理和３０を構成要素とし、これらの構成要素を組み合わせて構成されている。ＭＩＳＴＹ１は、２つのＦＬ関数１０、１つのＦＯ関数２０及び１つの排他的論理和３０から構成される第１のFeistel構造１００と、１つのＦＯ関数２０と１つの排他的論理和３０から構成される第２のFeistel構造２００を交互に縦方向に多段接続した構成となっている。ＭＩＳＴＹ１では、段数ｎは４の倍数と規定されており、ｎ＝８が推奨されている。【０００７】
図１に示すように、ＭＩＳＴＹ１においては、奇数段が第１のFeistel構造１００、偶数段が第２のFeistel構造２００となっている。第１のFeistel構造１００と第２のFeistel構造２００は共にＦＯ関数２０を備えている。【０００８】
ここで、Feistel構造について簡単に説明する。Feistel構造は、入力を左右２つのブロックに分割し、一方のＬ側のブロック（以後、ブロックＬと呼ぶ）をＦ関数（ＭＩＳＴＹ１の場合はＦＯ関数２０）に入力し、そのＦ関数の出力と他方のＲ側のブロック（以後、ブロックＲと呼ぶ）との排他的論理和をとり、その論理演算処理終了後に、ブロックＬとブロックＲの入れ替えを行う構成を持った構造である。【０００９】
ＭＩＳＴＹ１の場合、第１のFeistel構造１００は、ブロックＬ（３２ビット）にＦＬ関数１０Ｌ（ＦＬ１）の処理を施し、その処理結果を排他的論理和３０に入力し、ブロックＲ（３２ビット）にＦＬ関数１０Ｒ（ＦＬ２）の処理を施し、その処理結果を前記排他的論理和３０に入力する。そして、ＦＬ関数１０Ｌの処理結果と排他的論理和３０の論理演算結果を、次段のFeistel構造２００に、それぞれブロックＲ、ブロックＬとして出力する。【００１０】
第２のFeistel構造２００は、ブロックＬをＦＯ関数２０に入力し、ブロックＲを排他的論理和３０に入力する。そして、上記ＦＯ関数２０の処理結果と上記ブロックＲを排他的論理和３０により排他的論理和し、その論理演算結果と上記ブロックＬを外部に出力する。このとき、上記ブロックＬはブロックＲとして、上記論理演算結果はブロックＬとして、次段のFeistel構造１００に入力する。【００１１】
ＦＬ関数１０は鍵依存型の線形関数であり、ＦＯ関数２０は非線形関数である。ＦＬ関数１０は、３２ビットの入力データを３２ビットの拡大鍵ＫＬ（不図示）を用いて３２ビットのデータに変換して出力するFeistel構造の関数である。ＦＯ関数２０は、３２ビットの入力データを、６４ビットの拡大鍵ＫＯ（不図示）と４２ビットの拡大鍵ＫＩ（不図示）を用いて３２ビットのデータに変換して出力するMISTY構造の関数である。後述するように、ＦＯ関数２０は、内部にＦＩ関数を含んでいる。このＦＩ関数は非線形関数である。【００１２】
小型機器に搭載する暗号処理装置（暗号化装置）は、回路規模が小さいことが重要である。特に、組み込み用途の暗号機能付きマイクロコントローラや暗号ハードアクセラレータなどでは回路規模が重視される。したがって、ＭＩＳＴＹ１やＫＡＳＵＭＩなどのようにMISTY構造が多用される共通鍵暗号アルゴリズムをハードウェア実装する場合、そのハードウェアの回路規模を小さくするためには、ＦＯ関数の回路規模を小さくすることが非常に有効となる。【００１３】
図２Ａは、図１に示すＭＩＳＴＹ１の構造から抽出した、「ＦＯ関数２０とそれに接続された排他的論理和３０から構成される構造３００」を示す図である。図２Ａに示す構造３００は、第１のFeistel構造１００と第２のFeistel構造２００が共に備える構成要素である。【００１４】
構造３００の構成・動作を説明する。構造３００は、３２ビットのブロックＬのデータと３２ビットのブロックＲのデータを入力する。ブロックＬのデータは、そのまま外部に出力されると共に、ＦＯ関数２０に入力する。ＦＯ関数２０は、ブロックＬのデータを、６４ビットの拡大鍵ＫＯ（不図示）と４８ビットの拡大鍵ＫＩ（不図示）を用いて３２ビットのデータに変換し、その変換結果を排他的論理和３０に出力する。排他的論理和３０は、ブロックＲのデータとＦＯ関数２０の出力の排他的論理和をとり、その論理演算結果（３２ビットのデータ）を外部に出力する。また、構造３００は、入力したブロックＬのデータを、そのまま、外部に出力する。【００１５】
図２Ｂは、図２Ａに示す構造３００を時計回りに１８０度回転することによって得られる構造である。図２Ｂに示す構造３１０は、その内部のＦＯ関数２０を展開すると、図２Ｃに示すような構造となる。【００１６】
図２Ｃに示す構造３２０の概要は、非特許文献１の図２にＦＯｉとして開示されている。構造３２０は、一方の入力データである３２ビットのブロックＬのデータを、上位１６ビットのデータＬＬと下位１６ビットのデータＬＲに分割する。また、他方の入力データである３２ビットのブロックＲのデータを、上位１６ビットのデータＲＬと下位１６ビットのデータＲＲに分割する。ＦＯ関数２０は、秘密鍵Ｋ（１２８ビット）の一部のビットである鍵ＫＯi1〜ＫＯi4（各１６ビット）をＦＩ関数の前段に設けられた排他的論理和３２１の一方の入力に用いる。また、秘密鍵Ｋから一部のビットを取り出し、そのビットに対して拡大鍵生成処理を施すことで得られる拡大鍵ＫＩi1〜ＫＩi3（各１６ビット）を、ＦＩ関数（ＦＩi1〜ＦＩi3）の鍵に用いる。拡大鍵ＫＯi1〜ＫＯi4及び拡大鍵Ｋｌi1〜ＫＩi3の生成方法は、非特許文献１に説明されている。尚、ＦＯ関数はMISTY構造の関数である。以下の説明では、拡大鍵ＫＯi1〜ＫＯi4、ＫＩi1〜ＫＩi3のそれぞれを単に鍵と記載する場合もある。【００１７】
図２Ｃに示す構造３２０を、処理アルゴリズムの観点から解析すると、図３に示すような構成となる。図３に示す構造３３０においては、入力データであるブロックＬ、Ｒのデータ（３２ビット）は、それぞれ、レジスタＲｅｇ−Ｌ、Ｒｅｇ−Ｒに保持されるものとする。【００１８】
ＦＯ関数２０の全体処理は、図３において横方向の太い破線で区切られた３サイクルの処理に分割できる。これら３つのサイクルを、ここでは、処理順に、サイクル１、サイクル２、サイクル３と呼ぶことにする。サイクル１〜３の処理手順はほぼ同一であるので、図３において破線の矩形枠で囲んで示す部分（サイクル１の処理部）をハードウェアとしてユニット化し、そのユニット５００を各サイクルの処理で共用することが可能である。すなわち、上記ユニット５００を３回逐次実行することで、サイクル１〜３の処理を実行できる。厳密に述べると、サイクル１とサイクル２の処理手順は同じである。サイクル３は、他のサイクル（サイクル１、２）の処理に加え、サイクル２の処理結果と鍵ＫＯi4を排他的論理和３２１により排他的論理和をとる論理演算を行う。ところで、ユニット５００の構造は、一般にMISTY構造と呼ばれる。MISTY構造の基本構成は、左系のデータパスにＦ関数（ユニット５００の場合はＦＩ関数）と排他的論理和を順に配置した構成となっており、上記排他的論理和はＦ関数の出力と右系のデータパスから分岐入力するデータとの排他的論理和を演算する。上記排他的論理和の出力は次段の右系のデータパスの入力となり、上記排他的論理和に入力する右系のデータパスのデータは次段の左系のデータパスの入力となる。ＦＯ関数におけるMISTY構造は、左系のデータパス上にラウンド鍵ＫＯij(j=1〜3)が入力する第1の排他的論理和、その下部にラウンド鍵ＫＩij(j=1〜3)が入力するＦＩ関数、その下部に第２の排他的論理和を配置し、該第２の排他的論理和により、ＦＩ関数の出力と右系のデータパスから分岐入力するデータの排他的論理和を演算する。そして、その第２の排他的論理和の演算結果を次段の右系のデータパスの入力とする。また、前段の右系のデータパスを流れるデータを次段の左系のデータパスの入力とする。尚、以上の説明では、ＦＯ関数のMISTY構造を取り上げて、MISTY構造の構成を説明したが、ＦＩ関数などのＦＯ関数以外のデータ変換関数においても、上記基本構成を変形した各種形態のMISTY構造がある。図４は、図３に示すユニット５００の機能を備えた従来の回路を示す図である。【００１９】
図４に示す回路５１０は、図２Ｃに示すアルゴリズムの処理を実行可能である。すなわち、ＦＯ関数の処理と、ＦＯ関数の処理結果とデータＲとの排他的論理和をとる処理も可能である。【００２０】
回路５１０は、４個のレジスタＲｅｇ−Ｌ、Ｒｅｇ−ＦＯＬ、Ｒｅｇ−ＦＯＲ、Ｒｅｇ−Ｒ、２個のマルチプレクサ５１１Ｌ、５１１Ｒ、２個のデマルチプレクサ５１２Ｌ、５１２Ｒ、５個の他的論理和演算機器５２１〜５２５を備えている。【００２１】
レジスタＲｅｇ−Ｌは３２ビットのレジスタであり、ＦＯ関数２０が処理する３２ビットの入力データＬを保持する。レジスタＲｅｇ−Ｌに保持されたデータＬの上位１６ビット（ＬＬ）と下位１６ビット（ＬＲ）は、それぞれ、マルチプレクサ５１１Ｌとマルチプレクサ５１１Ｒに入力する。マルチプレクサ５１１Ｌには、レジスタＲｅｇ−ＦＯＬに保持されている１６ビットのデータも入力する。マルチプレクサ５１１Ｌは、レジスタＲｅｇ−ＬまたはレジスタＲｅｇ−ＦＯＬのいずれか一方から入力される１６ビットデータを排他的論理和演算器５２１に選択出力する。排他的論理和演算器５２１は、マルチプレクサ５１１Ｌから入力される１６ビットデータと外部入力される１６ビットの鍵ＫＯij(ｊ＝１〜３)の排他的論理和を演算し、その演算結果をＦＩ関数処理部５３０に出力する。ＦＩ関数処理部５３０は処理結果（１６ビットのデータ）を排他的論理和演算器５２２に出力する。マルチプレクサ５１１Ｒは、レジスタＲｅｇ−ＦＯＲが保持している１６ビットのデータも入力し、レジスタＲｅｇ−ＬまたはレジスタＲｅｇ−ＦＯＲのいずれか一方から入力される１６ビットのデータを排他的論理和演算器５２２とデマルチプレクサ５１２Ｌに選択出力する。排他的論理和演算器５２２は、ＦＩ関数処理部５３０の出力データ（１６ビット）とマルチプレクサ５１１Ｒから入力される１６ビットのデータの排他的論理和を演算し、その演算結果をデマルチプレクサ５１２Ｒに出力する。【００２２】
このように、マルチプレクサ５１１Ｌ、５１１Ｒとデマルチプレクサ５１２Ｌ、５１２Ｒの間に設けられた排他的論理和演算器５２１、５２２とＦＩ関数処理部５３０で構成される回路（図４において破線の矩形枠で囲まれた回路６００）はMISTY構造となっている。したがって、デマルチプレクサ５１２Ｌから出力されるＬ側（左側）の１６ビットデータとマルチプレクサ５１１Ｒから選択出力されるＲ側（右側）の１６ビットデータは、MISTY構造の回路６００によって、Ｒ側とＬ側の１６ビットデータに入れ替えられる。【００２３】
デマルチプレクサ５１２Ｌは、マルチプレクサ５１１Ｒから入力する１６ビットのデータを、レジスタＲｅｇ−ＦＯＬまたは排他的論理和演算器５２３のいずれか一方に選択出力する。レジスタＲｅｇ−ＦＯＬは、デマルチプレクサ５１２Ｌから入力する１６ビットデータを保持し、そのデータをマルチプレクサ５１１Ｌに出力する。排他的論理和演算器５２３は、サイクル３の処理における拡大鍵ＫＯi4とサイクル２における排他的論理和演算結果ｔ３（図２Ｃ参照）との排他的論理和を演算するために設けられている。排他的論理和演算器５２３の論理演算結果は排他的論理和演算器５２４に出力される。排他的論理和演算器５２４には、レジスタＲｅｇ−Ｒに保持されている３２ビットデータＲの上位１６ビット（ＲＬ）も入力する。排他的論理和演算器５２４の演算結果（１６ビット）はレジスタＲｅｇ−Ｒに上位１６ビットデータ（ＲＲ）として格納される。【００２４】
デマルチプレクサ５１２Ｒは、排他的論理和演算器５２２の論理演算結果（１６ビットデータ）をレジスタＲｅｇ−ＦＯＲまたは排他的論理和演算器５２５のいずれか一方に出力する。レジスタＲｅｇ−ＦＯＲは、デマルチプレクサ５１２Ｒから入力する１６ビットデータを保持し、そのデータをマルチプレクサ５１１Ｒに出力する。排他的論理和演算器５２５は、レジスタＲｅｇ−Ｒに保持されている３２ビットデータの下位１６ビット（ＲＲ）とデマルチプレクサ５１２Ｒからの入力データの排他的論理和を演算し、その演算結果（１６ビットデータ）をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、排他的論理和演算器５２５から入力される１６ビットデータを３２ビットデータの下位１６ビットのデータ（ＲＲ）として保持し、そのデータＲＲを排他的論理和演算器５２５に出力する。【００２５】
このように、従来のＦＯ関数及びその周辺回路（ＦＯ関数の出力とデータＲの排他的論理和をとる回路）用の回路は、ＦＯ関数の処理のために、２個の１６ビットデータ保持用のレジスタＲｅｇ−ＦＯＬ、レジスタＲｅｇ−ＦＯＲが必要であった。すなわち、ＦＯ関数及びその周辺回路用の回路（以後、便宜上、この回路をＦＯ関数関連処理回路と呼ぶ）は、ＦＯ関数用に合計３２ビットのレジスタが必要であった。
｛ＭＩＳＴＹ１のアルゴリズム｝
ＭＩＳＴＹ１においては、平文１（６４ビット）は３２ビットに２分割される。ここで、ＭＳＢ(Most Significant Bit)側の３２ビットをＬ、ＬＳＢ(Least Significant Bit)側の３２ビットをＲと呼ぶことにする。各分割データＬ、Ｒは、それぞれ、左側の初段のＦＬ関数１０と右側の初段のＦＬ関数１０に入力される。そして、前記左側のＦＬ関数１０の出力（３２ビット）が初段のＦＯ関数２０に入力され、前記右側のＦＬ関数１０の出力が（３２ビット）が初段の排他的論理和３０の一方の入力となる。前記初段のＦＯ関数２０の出力（３２ビット）は、該初段の排他的論理和３０の他方の入力となる。初段の排他的論理和３０の結果（３２ビット）は、左側の２段目のＦＬ関数１０と２段目のＦＯ関数２０の入力となる。また、左側の初段のＦＬ関数１０の出力（３２ビット）は、２段目の排他的論理和３０の一方の入力となる。この２段目の排他的論理和３０の他方の入力は、前記２段目のＦＯ関数２０の出力となる。
｛ＦＯ関数関連処理回路の従来の処理アルゴリズムＡＬp｝
ここで、図４に示す回路５１０を用いたＦＯ関数関連処理回路の処理アルゴリズムを、図２Ｃを参照しながら説明する。尚、各サイクルの右辺の式における【００２６】
【数１】
2009090689.tif 000003
は、排他的論理和の演算を示す記号である。これは、以降の論理演算式においても同様である。
ＦＩ（ａ，ＫＩij）は、入力データａを拡大鍵ＫＩij（ｊ＝１〜３）により変換するＦＩ関数の処理を示す。
［サイクル１］【００２７】
【数２】
2009090689.tif 000004
［サイクル２］【００２８】
【数３】
2009090689.tif 000005
［サイクル３］【００２９】
【数４】
2009090689.tif 000006
【００３０】
【数５】
2009090689.tif 000007
上記に示すように、従来の回路５１０は、サイクル１、２の処理結果ｔ2i-1、ｔ2i（ｉ＝１〜２）を、それぞれ、レジスタＲｅｇ−ＦＯＲ、レジスタＲｅｇ−ＦＯＬに格納する必要があった。しかしながら、レジスタは他の素子に比べて１ビット当たりのゲート規模が大きいため、ＭＩＳＴＹ１を適用した暗号処理装置の回路全体の規模を小さくするためには、レジスタのサイズを極力削減することが望ましい。このことは、ＭＩＳＴＹ１のみならず、ＫＡＳＵＭＩなどのようなＭＩＳＴＹ１と類似した回路構造を有する共通鍵暗号系のブロック暗号の処理装置の回路にも同様にあてはまる。【００３１】
図５は、上記処理アルゴリズムＡＬpのソフトウェア処理を示すフローチャートである。このソフトウェア処理は、組み込みシステムのマイコン（マイクロコンピュータ）が備えるＣＰＵなどにより実行される。尚、以下のフローチャートの処理で使用されるデータＬＲ，ＬＬ，ＲＲ，ＲＬ，鍵ＫＯi1〜ＫＯi4，鍵ＫＩi1〜ＫＩi3は、ＣＰＵ内のレジスタまたはメモリなどに格納されている。【００３２】
図５のフローチャートの処理を説明する。
まず、前記処理アルゴリズムＡＬpのサイクル１の処理【００３３】
【数６】
2009090689.tif 000008
を実行し、その処理結果をレジスタＡに格納する（Ｓ１）。尚、レジスタＡはＣＰＵが備える汎用レジスタの一つである。【００３４】
次に、前記処理アルゴリズムＡＬpのサイクル２の処理【００３５】
【数７】
2009090689.tif 000009
を実行し、その処理結果をレジスタＢに格納する（Ｓ２）。【００３６】
そして、最後に、前記処理アルゴリズムＡＬpのサイクル３の最初の処理【００３７】
【数８】
2009090689.tif 000010
を実行し、その処理結果を「ＲＲが格納されているレジスタ」に格納する。【００３８】
続いて、前記処理アルゴリズムＡＬpのサイクル３の２番目の処理【００３９】
【数９】
2009090689.tif 000011
を実行し、その処理結果を「ＲＬが格納されているレジスタ」に格納する。【００４０】
以上の処理により、６４ビットの平文データが６４ビットの暗号文に暗号化される。
図６は、図５のフローチャートの処理をアセンブリ言語で表現したプログラムの例である。図６に示すプログラムにおいては、ＦＩ関数の処理をプログラム（ＦＩ関数処理関数）で実現している。このＦＩ関数処理関数は、図６に示すメインプログラム（メインルーチン）からサブルーチンとして呼び出さされる。このサブルーチン呼び出しは、図６において、
Call FI(a，ＫＩij)
ｊ＝１〜３
という記述のステートメントで表現されている。【００４１】
Call FI(a，ＫＩij)は、「ａを入力データ（変換対象データ）、ＫＩijをデータ変換用の鍵として、ＦＩ関数（ＦＩ関数処理関数）を実行する処理であり、そのＦＩ関数の処理結果はａに格納される」。【００４２】
尚、図６に示すプログラム記述において、「ＭＯＶ」はデータ転送命令、「ＸＯＲ」は排他的論理和の演算命令を示す。また、それらの命令のオペランドａや、Ｃａｌｌ命令の引数ａはレジスタＡを示す。ＭＯＶ命令は、第1オペランドのレジスタに、第２オペランドで指定されるデータを転送する命令である。例えば、、「ＭＯＶ  ａ，ＬＬ」は、レジスタＬＬに格納されているデータを、レジスタＡに転送する命令である。また、「ＭＯＶ  ａ，［ＬＬ］」は、データＬＬが格納されているメモリアドレスをアクセスして、メモリからレジスタＡにデータＬＬを転送する命令である。【００４３】
図６に示すプログラム記述から分かるように、従来のＦＯ関数関連処理のプログラム（ソフトウェア）は、ＣＰＵが備える汎用レジスタの内、データ変換処理過程における中間データの保持のために２個のレジスタ（レジスタＡ、Ｂ）を使用していた。
【特許文献１】特開２００４−２４０４２７号公報
【特許文献２】特許３０８８３３７号
【非特許文献１】暗号技術仕様書  ＭＩＳＴＹ１(http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/5_02jspec.pdf)
【非特許文献２】松井  充  「ブロック暗号アルゴリズム  ＭＩＳＴＹ」、信学技報、ＩＳＥＣ９６−１１、１９９６−０７
【発明の開示】
【００４４】
本発明の目的は、ブロック暗号で使用されるMISTY構造を有するデータ変換関数の処理装置の回路規模を従来よりも小さくすることである。
本発明の暗号化装置は、２ｎビットのデータＬをデータ変換するデータ処理手段と、該データ処理手段の処理結果と２ｎビットのデータＲとを排他的論理和する排他的論理和演算器を備える暗号化装置を前提とする。
【００４５】
暗号化装置の第１の態様は、ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲ、ｎビットのデータ“０”または前記第１のレジスタに格納されているｎビットのデータのいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、該第２の排他的論理和演算器の出力を前記第１のレジスタに出力するデマルチプレクサと、前記第２の排他的論理和演算器の出力またはラウンド鍵ＫＯim（ｍは自然数）を選択出力する第３のマルチプレクサと、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記第３のマルチプレクサの出力とを排他的論理和する第３の排他的論理和演算器と、前記第２のマルチプレクサの出力と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備える。そして、
前記第１のマルチプレクサ、前記第２のマルチプレクサ、前記第３のマルチプレクサ及び前記デマルチプレクサは外部から制御され、前記第１のレジスタは前記デマルチプレクサの出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納する。
【００４６】
暗号化装置の第２の態様は、ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲまたはｎビットのデータ“０”のいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、前記第２の排他的論理和演算器の出力またはラウンド鍵ＫＯimを選択出力する第３のマルチプレクサと、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記第３のマルチプレクサの出力とを排他的論理和する第３の排他的論理和演算器と、前記第２の排他的論理和演算器と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備える。そして、前記第１のマルチプレクサ、前記第２のマルチプレクサ及び前記第３のマルチプレクサは外部から制御され、前記第１のレジスタは前記第２の排他的論理和演算器の出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納する。
【００４７】
暗号化装置の第３の態様は、ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲまたはｎビットのラウンド鍵ＫＯim（ｍは自然数）のいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、該第２の排他的論理和演算器の出力を入力し、その入力を適切なタイミングで出力する出力手段と、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記スイッチ手段の出力とを排他的論理和する第３の排他的論理和演算器と、前記第２の排他的論理和演算器と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備える。そして、前記第１のマルチプレクサ、前記第２のマルチプレクサ及び前記出力手段は外部から制御され、前記第１のレジスタは前記第２の排他的論理和演算器の出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納する。
【００４８】
上記暗号化装置の第３の態様において、例えば、前記出力手段は、ｎビットの“０”データまたは前記第２の排他的論理和演算器の出力を選択出力する第３のマルチプレクサである。
【００４９】
暗号化装置の第４の態様は、上記暗号化装置の第１乃至第３の態様のいずれか一つの暗号化装置において、さらに、前記データＬを入力・保持し、出力する第３のレジスタを備えている。
【００５０】
本発明の暗号化装置によれば、マルチプレクサやデマルチプレクサを制御することで、従来はレジスタに格納する必要があったデータ処理手段のｎビットの処理結果を、第１のレジスタに格納せずに、第２のレジスタに格納されている２ｎビットのデータＲの上位１６ビットＲＬと下位１６ビットＲＲと、それぞれ、排他的論理和する。このため、第１のレジスタのサイズ（レジスタ長）をｎビットにすることができる。したがって、従来の暗号化装置と比較して、レジスタサイズを半減でき、回路規模の削減が可能になる。
【００５１】
本発明の暗号処理方法は、２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータＲの排他的論理和を演算した後、その排他的論理和の論理演算結果を出力する暗号処理方法を前提にする。
【００５２】
暗号処理方法の第１の態様は、前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を出力するサイクル１のステップと、前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果を前記サイクル１のステップで出力される論理演算結果ｔ１と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記データＲの下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル２のステップと、前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル２で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとすると共に、前記サイクル２のステップで出力される上位ｎビットＲＬをラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップとを備える。
【００５３】
暗号処理方法の第２の態様は、前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を前記データRの下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ１を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル１のステップと、前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果ｔ３をサイクル１のステップで出力されるＲＬと排他的論理和してＲＬとして出力し、さらにｔ３をサイクル１のステップで出力されるＲＲと排他的論理和してＲＲとして出力するサイクル２のステップと、前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル２で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとすると共に、前記サイクル２のステップで出力される上位ｎビットＲＬを拡大鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップとを備える。
【００５４】
暗号処理方法の第３の態様は、前記データＬの上位ｎビットＬＬをラウンド鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を前記データRの下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ１を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル１のステップと、前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果をラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記データＲの下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル２のステップと、前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果を鍵ＫＯｉ４と排他的論理和し、その論理演算結果をラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果をサイクル２で出力された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記サイクル２のステップで出力される上位ｎビットＲＬを出力するサイクル３のステップとを備える。
【００５５】
本発明の暗号処理方法によれば、前記論理演算結果ｔ３をレジスタに格納する処理が不要になる。したがって、従来の暗号処理方法と比較して、回路規模を削減できる。
尚、MISTY構造はFeistel構造の一種である。
【図面の簡単な説明】
【００５６】
【図１】ＭＩＳＴＹ１の暗号化処理の基本構造を示す図である。
【図２Ａ】図１に示すＭＩＳＴＹ１の構造から抽出したＦＯ関数の周辺の構造を示す図である。
【図２Ｂ】図２Ａに示す上記ＦＯ関数の周辺の構造を時計回りに１８０度回転することによって得られる構造である。
【図２Ｃ】図２Ｂに示す構造において、その内部のＦＯ関数を展開することによって得られる図である。
【図３】図２Ｃに示す構造を、ハードウェア処理の観点から解析した図である。
【図４】図３に示すユニットの従来のハードウェア構成を示す図である。
【図５】従来のＦＯ関数関連処理のアルゴリズムのソフトウェア処理を示すフローチャートである。
【図６】図５のフローチャートの処理をアセンブリ言語で表現したプログラムの例である。
【図７Ａ】従来のＦＯ関数関連処理回路の処理アルゴリズムを示す図である。
【図７Ｂ】本発明の第１の実施形態であるＦＯ関数関連処理回路の処理アルゴリズムを示す図である。
【図８Ａ】図７Ｂを、本発明の第１の実施形態の処理アルゴリズムのサイクル１〜３に対応させて分割した図である。
【図８Ｂ】本発明の第２実施形態であるＦＯ関数関連処理回路の構成例を示す図である。
【図９Ａ】従来のＦＯ関数関連処理回路の処理アルゴリズムを示す図である。
【図９Ｂ】図９Ａに示す処理アルゴリズムを等価変換することによって得られる、本発明の第２実施形態の処理アルゴリズムを示す図である。
【図１０Ａ】図９Ｂを、本発明の第２実施形態の処理アルゴリズムのサイクル１〜３に対応させて分割した図である。
【図１０Ｂ】本発明の第２実施形態であるＦＯ関数関連処理回路の構成例を示す図である。
【図１１Ａ】本発明の第２実施形態であるＦＯ関数関連処理回路の処理アルゴリズムを示す図である。
【図１１Ｂ】本発明の第３の実施形態であるＦＯ関数関連処理の処理アルゴリズムを示す図である。
【図１２】本発明の第３の実施形態であるＦＯ関数関連処理回路の構成例を示す図である。
【図１３】本発明の実施形態である組み込み機器の第１の構成を示す図である。
【図１４】本発明の実施形態である組み込み機器の第２の構成を示す図である。
【図１５】本発明の実施形態である組み込み機器の第３の構成を示す図である。
【図１６】本発明の第１の実施形態のＦＯ関数関連処理回路の機能を実現するために、上記第１の構成の組み込み機器に実装されるソフトウェア（プログラム）のアルゴリズムを示すフローチャートである。
【図１７】図１６に示すアルゴリズムで動作するプログラムの実施例を示す図である。
【図１８】本発明の第２の実施形態のＦＯ関数関連処理回路の機能を実現するために、上記第１の構成の組み込み機器に実装されるソフトウェア（プログラム）のアルゴリズムを示すフローチャートである。
【図１９】図１８に示すアルゴリズムのプログラムで動作するプログラムの実施例を示す図である。
【図２０】本発明の第３の実施形態のＦＯ関数関連処理回路の機能を実現するために、上記第１の構成の組み込み機器に実装されるソフトウェア（プログラム）のアルゴリズムを示すフローチャートである。
【図２１】図２０に示すアルゴリズムのプログラムで動作するプログラムの実施例を示す図である。
【発明を実施するための最良の形態】
【００５７】
本実施形態は、排他的論理和演算が演算順序が入れ替え可能であるという法則を利用して、図２Ｃに示すようなMISTY構造を有する関数の回路（装置）で使用されるレジスタのサイズの削減を図るものである。【００５８】
以下、図面を参照しながら本発明の実施形態について説明する。尚、以下に述べる実施形態は、いずれも本発明をＦＯ関数関連処理回路に適用した例であるが、本発明はＦＯ関数関連処理回路に限定されるものではなく、ＦＯ関数以外のＦ関数を含むMISTY構造の回路にも適用可能である。また、ブロック長も６４ビットに限定されるものではない。また、秘密鍵や拡大鍵のビット長も本実施形態に限定されるものではない。
［第１の実施形態］
｛手法｝
図７Ａ、７Ｂは、本発明の第１の実施形態の手法を説明する図である。図７Ａは図２Ｃと同様な図であり、従来のＦＯ関数関連処理回路の処理アルゴリズムを示す図である。【００５９】
本実施形態においては、図７Ａに示すＦＯ関数関連処理回路の従来構造を、図７Ｂに示す構造に等価変換する。具体的には、図７Ａにおいて２つの楕円枠で囲まれている構成を、図９Ｂにおいて２つの楕円枠で囲まれた構成に等価変換する。【００６０】
図７Ａに示すように、ＦＯ関数は３段のMISTY構造を有しており、１段目は排他的論理和６１１、ＦＩ関数６０１及び排他的論理和６１２から構成されている。また、２段目は、排他的論理和６２１、ＦＩ関数６０２及び排他的論理和６２２から構成されている。３段目は、排他的論理和６３１、ＦＩ関数６０３及び排他的論理和６３２ａから構成されている。ＦＯ関数は、さらに、２段目内の排他的論理和６２２の出力ｔ３と鍵ＫＯi4の排他的論理和を演算する排他的論理和６４２ａを備えている。【００６１】
図７Ｂに示す等価変換においては、まず、３段目（サイクル３）のＦＩ関数６０３の出力を、２段目（サイクル２）の出力ｔ３（２番目の排他的論理和６２２の出力）と排他的論理和させずに、“０”と排他的論理和させる（排他的論理和６３２）。排他的論理和６３２の出力はＲＲと排他的論理和させる（排他的論理和６４１）。また、鍵ＫＯi4をＲＬと排他的論理和させる（排他的論理和６４２）。さらに、ｔ３を単純分岐させ、ｔ３を排他的論理和６４２の出力と排他的論理和させる（排他的論理和６４３）と共に、排他的論理和６４１の出力とも排他的論理和させる（排他的論理和６４４）。【００６２】
尚、排他的論理和６３２を行っても、ＦＩ関数処理部６０３の結果がそのまま出力されるだけなので、排他的論理和６３２は省略してもよい。
上記のようにして、ＦＯ関数関連処理回路の処理アルゴリズムを図７Ｂに示す構成にすることで、ＦＯ関数関連処理回路をハードウェア化した場合、その回路で使用するレジスタサイズを従来の半分とすることができる。このようなハードウェアの実施形態については後述する。
｛第1の実施形態のＦＯ関数関連処理回路の処理アルゴリズムＡＬ１｝
図７Ｂに示す処理アルゴリズムＡＬ１は、下記のサイクル１〜３から構成される。【００６３】
［サイクル１］【００６４】
【数１０】
2009090689.tif 000012
（t1をレジスタに格納）
［サイクル２］【００６５】
【数１１】
2009090689.tif 000013
（t3はレジスタに格納せず、直接RR,RLと排他的論理和する）
［サイクル３］【００６６】
【数１２】
2009090689.tif 000014
｛ＦＯ関数関連処理回路の第1の実施形態のハードウェア構成｝
図８Ａは、図７Ｂを、前記処理アルゴリズムＡＬ１のサイクル１〜３に対応させて分割した図である。図８Ｂは、図８Ａに示す処理アルゴリズムをハードウェア化したＦＯ関数関連処理回路の構成例を示す図である。尚、図８Ｂにおいて、図４に示す回路の構成要素と同じ構成要素には同一の符号を付与している。【００６７】
図８Ａに示すように、図７Ｂに示す処理アルゴリズムはサイクル１（１サイクル目）〜サイクル３（３サイクル目）の３つのサイクルに分割できる。これら３つのサイクルにおいて、図８Ａの上方に示す処理ブロック７１０の処理は、サイクル１〜３の全てで共通な処理である。したがって、この処理ブロック７１０を、図８Ｂに示すように回路要素８１０としてハードウェア化する。回路要素８１０は、排他的論理和演算器８１１、ＦＩ関数処理部８１２及び排他的論理和演算器８１３から構成される。【００６８】
また、図８Ａに示す処理ブロック７３０の処理は、サイクル２に特有な処理である。したがって、この処理ブロック７３０を、図８Ｂに示すように回路要素８３０としてハードウェア化する。回路要素８３０は、２つの排他的論理和演算器５２４、５２５と１つのレジスタＲｅｇ−Ｒから構成される。レジスタＲｅｇ−Ｒは３２ビット構成のレジスタである。回路要素８３０は、図４に示す回路にも含まれており新規な構成ではない。図８Ｂに示す回路は、上記構成要素以外に、３２ビット構成のレジスタＲｅｇ−Ｌ、２つの３入力１出力のマルチプレクサ８０１Ｒ、８０１Ｌ、デマルチプレクサ８２１、マルチプレクサ８２３及び１６ビット構成のレジスタＲｅｇ−ＦＯを備える。【００６９】
図８Ｂに示す本実施形態のＦＯ関数関連処理回路（暗号化装置）８００が備えるレジスタは、２個の３２ビット構成のレジスタＲｅｇ−Ｌ、Ｒｅｇ−Ｒと１個の１６ビット構成のレジスタＲｅｇ−ＦＯであり、回路全体のレジスタサイズは８０ビットである。したがって、図４に示す従来のＦＯ関数関連処理回路５１０よりも、レジスタサイズが１６ビット小さい。これは、従来のＦＯ関数関連処理回路５１０が備えていた２個のレジスタＲｅｇ−ＦＯＬ、Ｒｅｇ−ＦＯＲを、１個のレジスタＲｅｇ−ＦＯに代替したためである。また、本実施形態のＦＯ関数関連処理回路８００においては、従来のＦＯ関数関連処理回路５１０が備えていた鍵ＫＯi4専用の排他的論理和演算器も削減されている。【００７０】
レジスタＲｅｇ−Ｌは、３２ビットの入力データＬを格納するレジスタである。ここで、レジスタＲｅｇ−Ｌに格納される３２ビットデータＬの上位１６ビットデータをＬＬ、下位１６ビットデータをＬＲと表現する。レジスタＲｅｇ−Ｌに保持されている３２ビットデータＬは、上位１６ビットデータＬＬと下位１６ビットデータに分岐してマルチプレクサ８０１Ｌに入力する。レジスタＲｅｇ−Ｌに保持されている３２ビットデータＬの下位１６ビットデータＬＲは、マルチプレクサ８０１Ｒにも入力される。【００７１】
マルチプレクサ８０１Ｌには、レジスタＲｅｇ−ＦＯに格納されている１６ビットデータも入力する。マルチプレクサ８０１Ｌは、上記した３つの１６ビットデータの中からいずれか１つを選択し、その選択した１６ビットデータを排他的論理和演算器８１１に出力する。マルチプレクサ８０１Ｒには、上記１６ビットデータＬＲ以外に、“０”の１６ビットデータとレジスタＲｅｇ−ＦＯに格納されている１６ビットデータが入力する。マルチプレクサ８０１Ｒは、それら３つの１６ビットデータの中からいずれか１つを選択し、その選択した１６ビットデータを排他的論理和演算器８１３に出力する。【００７２】
排他的論理和演算器８１１は、マルチプレクサ８０１Ｌから入力する１６ビットデータと外部入力される鍵ＫＯiｊ（ｊ＝１〜３）の排他的論理和を演算し、その演算結果（１６ビットデータ）をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、排他的論理和演算器８１１から入力される１６ビットデータを、外部入力される鍵ＫＩij（ｊ＝１〜３）を用いて変換し、その変換結果（１６ビットデータ）を排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２から入力される１６ビットデータとマルチプレクサ８０１Ｒから入力される１６ビットデータの排他的論理和を演算し、その演算結果をデマルチプレクサ８２１に出力する。【００７３】
デマルチプレクサ８２１は、排他的論理和演算器８１３から入力する１６ビットデータを、レジスタＲｅｇ−ＦＯ、マルチプレクサ８２３及び排他的論理和演算器５２５に出力する。尚、デマルチプレクサ８２１は、排他的論理和演算器８１３からの入力を開閉するスイッチに代替することも可能である。マルチプレクサ８２３には、鍵ＫＯi4も外部入力する。マルチプレクサ８２３は、デマルチプレクサ８２１の出力または鍵ＫＯi4のいずれか一方を選択し、その選択した１６ビットデータを排他的論理和演算器５２４に出力する。排他的論理和演算器５２４は、マルチプレクサ８２３の出力（１６ビットデータ）とレジスタＲｅｇ−Ｒに格納されている３２ビットデータの上位１６ビットデータを排他的論理和し、その論理演算結果（１６ビットデータ）をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、排他的論理和演算器５２４が出力する１６ビットデータを３２ビットデータの上位１６ビットとして格納する。このように、レジスタＲｅｇ−Ｒは、排他的論理和演算器５２４の最新の論理演算結果（１６ビットデータ）を、３２ビットデータの上位１６ビットとして格納する機能を有する。換言すれば、レジスタＲｅｇ−Ｒが保持する３２ビットデータの上位１６ビットは排他的論理和演算器５２４の論理演算結果によって更新される。【００７４】
排他的論理和演算器５２５は、デマルチプレクサ８２１の出力（１６ビットデータ）とレジスタＲｅｇ−Ｒに格納されている下位１６ビットデータを排他的論理和し、その論理演算結果（１６ビットデータ）をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、排他的論理和演算器５２５が出力する１６ビットデータを３２ビットデータの下位１６ビットとして格納する。このように、レジスタＲｅｇ−Ｒは、排他的論理和演算器５２５の最新の論理演算結果（１６ビットデータ）を、３２ビットデータの下位１６ビットとして格納する機能を有する。換言すれば、レジスタＲｅｇ−Ｒが保持する３２ビットデータの下位１６ビットは排他的論理和演算器５２５の論理演算結果によって更新される。尚、レジスタＲｅｇ−Ｒの上位１６ビットＲＬと下位１６ビットＲＲの更新処理は並列処理することが可能である。【００７５】
図８Ｂに示すＦＯ関数関連処理回路８００の各構成要素は不図示の制御部から出力される制御信号によって動作やそのタイミングが制御される。また、レジスタＲｅｇ−ＬとレジスタＲｅｇ−Ｒの役割（機能）は、各段のＦＯ関数毎に交換させる。具体的には、図８Ｂに示す回路は、奇数段（１段目、３段目、５段目、・・・）のＦＯ関数の回路構成である。偶数段（２段目、４段目、６段目、・・・）のＦＯ関数においては、レジスタＲｅｇ−ＬとレジスタＲｅｇ−Ｒの配置が交換される。これは、上述したように、Feistel構造においては、段が切り替わる毎にＬ（６４ビットデータの上位３２ビット）とＲ（６４ビットデータの下位３２ビット）を交互に入れ替えるからである。これは、以下に述べる第２及び第３実施形態についても同様である。【００７６】
ところで、上記処理アルゴリズムＡＬ1におけるサイクル２とサイクル３の順序を交換して処理を実行することも可能である。すなわち、サイクル１、サイクル３、サイクル２の順で処理を実行するようにしてもよい。また、ＲＬに拡大鍵ＫＯi4を排他的論理和する処理は、サイクル１のタイミングであっても問題ない。このようにすれば、上記ＦＯ関数関連処理回路８００から拡大鍵ＫＯi4を選択するマルチプレクサ８２３を除去することが可能となる。この場合、ＲＬと拡大鍵ＫＯi4の排他的論理和は、回路８００の外部で実行するようにしてもよい。
｛ＦＯ関数関連処理回路の第1の実施形態の動作｝
図８Ｂに示すＦＯ関数関連処理回路８００は、上記処理アルゴリズムＡＬ１の処理を実行する。以下、ＦＯ関数関連処理回路８００の動作を処理アルゴリズムＡＬ１の各サイクル毎に説明する。
｛サイクル１｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−Ｌから入力する１６ビットデータＬＬを排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータＬＬと外部入力する鍵ＫＯi1の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、上記演算結果を外部入力する鍵ＫＩi1を用いて変換し、その変換結果を排他的論理和演算器８１３に出力する。一方、マルチプレクサ８０１Ｒは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータの下位１６ビットＬＲを排他的論理和演算器８１３に選択出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２からの入力データとマルチプレクサ８０１Ｒからの入力データ（ＬＲ）の排他的論理和を演算し、その演算結果ｔ１をデマルチプレクサ８２１に出力する。デマルチプレクサ８２１は、その１６ビットデータｔ１をレジスタＲｅｇ−ＦＯに出力する。レジスタＲｅｇ−ＦＯは、入力する１６ビットデータｔ１を格納する。
｛サイクル２｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータの下位１６ビットＬＲを排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータＬＲと外部入力される鍵ＫＯi2の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、その演算結果を外部入力される鍵ＫＩi2を用いて変換し、その変換結果を排他的論理和演算器８１３に出力する。マルチプレクサ８０１Ｒは、レジスタＲｅｇ−ＦＯに保持されている１６ビットデータｔ１を排他的論理和演算器８１３に選択出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２の変換結果と１６ビットデータｔ１の排他的論理和を演算し、その演算結果（１６ビットデータ）ｔ３をデマルチプレクサ８２１に出力する。デマルチプレクサ８２１は、その１６ビットデータｔ３をマルチプレクサ８２３と排他的論理和演算器５２５に出力する。排他的論理和演算器５２５は、レジスタＲｅｇ−Ｒに保持されている３２ビットデータの下位１６ビットＲＲと１６ビットデータｔ３の排他的論理和を演算し、その演算結果（１６ビットデータ）をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を３２ビットデータの下位１６ビットＲＲとして格納する。【００７７】
マルチプレクサ８２３は、上記１６ビットデータｔ３を排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、その１６ビットデータｔ３とレジスタＲｅｇ−Ｒに保持されている３２ビットデータの上位１６ビットＲＬの排他的論理和を演算し、その演算結果（１６ビットデータ）をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を３２ビットデータの上位１６ビットＲＬとして格納する。【００７８】
このように、サイクル２においては、排他的論理和演算器８１３の出力ｔ３は、レジスタＲｅｇ−ＦＯに格納されない。ｔ３は、レジスタＲｅｇ−Ｒに保持されている１６ビットデータＲＲ及び１６ビットデータＲＬと直接に排他的論理和がとられる。
｛サイクル３｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−ＦＯに格納されている１６ビットデータｔ１を排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータｔ１と外部入力する鍵ＫＯi3の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、その演算結果を外部入力する鍵ＫＩi3を用いて変換し、その変換結果を排他的論理和演算器８１３に出力する。マルチプレクサ８０１Ｒは、１６ビットデータ“０”（１６ビットが全て“０”のデータ）を排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２からの入力と上記１６ビットデータ“０”の排他的論理和を演算し、その演算結果をデマルチプレクサ８２１に出力する。したがって、この場合、ＦＩ関数処理部８１２の出力データ（１６ビットデータ）がそのままデマルチプレクサ８２１に入力する。デマルチプレクサ８２１は、ＦＩ関数処理部８１２の出力データを排他的論理和演算器５２５に出力する。排他的論理和演算器５２５は、そのＦＩ関数処理部８１２の出力データとレジスタＲｅｇ−Ｒに保持されている３２ビットデータの下位１６ビットＲＲの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、排他的論理和演算器５２５から入力される１６ビットデータを、３２ビットデータの下位１６ビットＲＲとして格納する。マルチプレクサ８２３は、外部入力する鍵ＫＯi4を排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、鍵ＫＯi4とレジスタＲｅｇ−Ｒに保持されている３２ビットデータの上位１６ビットＲＬの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、上記演算結果を３２ビットデータの上位１６ビットＲＬとして格納する。
［第２の実施形態］
｛手法｝
本発明の第２実施形態のＦＯ関数関連処理回路の処理アルゴリズムは、上述した図８Ｂに示すＦＯ関数関連処理回路の処理アルゴリズムを、さらに等価変換したものである。【００７９】
この等価変換を、図９Ａ、９Ｂを参照して説明する。図９Ａに示すＦＯ関数関連処理回路の処理アルゴリズムは、図５Ａに示す従来の処理アルゴリズムと同じものである。
上述した第1の実施形態のＦＯ関数関連処理回路の処理アルゴリズムは、図９Ａにおいて楕円形の枠６６０、６７０で囲んだ部分を等価変換したものであった。第２の実施形態のＦＯ関数関連処理回路の処理アルゴリズムは、上記２つの部分に加え、図９Ａにおいて楕円形の枠６８０で囲まれた部分についても等価変換を行い、図９Ａに示す構成の処理アルゴリズムを図９Ｂに示す構成の処理アルゴリズムに変形する。【００８０】
図９Ｂにおいて、楕円形の枠９６０、９７０で囲まれた部分は第１の実施形態のＦＯ関数関連処理回路の処理アルゴリズムと同様な構成である。第２の実施形態においては、図９Ｂにおいて楕円形の枠９８０で囲んで示すように、３２ビットデータＲの上位１６ビットＲＬを処理する経路（以後、上位１６ビットＲＬ下位処理経路と呼ぶ）に排他的論理和９４５を追加する。この排他的論理和９４５は、上位１６ビットＲＬ下位処理経路において排他的論理和６４３の後段に配置する。さらに、３２ビットデータＲの下位１６ビットＲＲを処理する経路（以後、下位１６ビットＲＲ処理経路と呼ぶ）に排他的論理和９４６を追加する。この排他的論理和９４６は、下位１６ビットＲＲ処理経路において排他的論理和６４４の後段に配置する。排他的論理和９４６には、排他的論理和演算器６４４の出力と排他的論理和６１２の出力を入力させる。排他的論理和９４５には、排他的論理和６４３の出力と排他的論理和６１２の出力を入力させる。また、２段目のMISTY構造のＦＩ関数６０２の出力が入力する排他的論理和９１４には“０”の１６ビットデータを入力させる。この排他的論理和９１４の論理演算結果は、排他的論理和６４３、６４４の入力となる。
｛ＦＯ関数関連処理回路の第２の実施形態の処理アルゴリズムＡＬ２｝
図９Ｂに示す処理アルゴリズムＡＬ２は、下記のサイクル１〜３から構成される。【００８１】
［サイクル１］【００８２】
【数１３】
2009090689.tif 000015
(t1はレジスタに格納する)
［サイクル２］【００８３】
【数１４】
2009090689.tif 000016
（t3はレジスタに格納せず、RR,RLに直接排他的論理和する）
［サイクル３］【００８４】
【数１５】
2009090689.tif 000017
｛ＦＯ関数関連処理回路の第２の実施形態のハードウェア構成｝
図１０Ａは、図９Ｂを、前記処理アルゴリズムＡＬ２のサイクル１〜３に対応させて分割した図である。図１０Ｂは、図１０Ａに示す処理アルゴリズムをハードウェア化したＦＯ関数関連処理回路の構成例を示す図である。尚、図１０Ｂにおいて、図８Ｂに示すＦＯ関数関連処理回路８００の構成要素と同じ構成要素には同じ符号を付与している。【００８５】
図１０Ａに示すように、図９Ｂに示す処理アルゴリズムはサイクル１（１サイクル目）〜サイクル３（３サイクル目）の３つのサイクルに分割できる。これら３つのサイクルにおいて、図１０Ａの上方に示す処理ブロック７１０の処理は、サイクル１〜３の全てで共通な処理である。したがって、この処理ブロック７１０を、上述した第1の実施形態と同様に、図１０Ｂに示すように回路要素８１０としてハードウェア化する。この回路要素８１０は、排他的論理和演算器８１１、ＦＩ関数処理部８１２及び排他的論理和演算器８１３から構成される。【００８６】
上述した処理アルゴリズムＡＬ２は、サイクル２とサイクル３の順序を交換しても処理結果としては問題ない。以下に述べる図1０に示すＦＯ関数関連処理回路は、上記処理アルゴリズムＡＬ２を、サイクル１、サイクル３、サイクル２の順に実行するものである。【００８７】
図１０Ｂに示すＦＯ関数関連処理回路１０００の構成について説明する。以下の説明では、ＦＯ関数関連処理回路８００と相違する構成について述べ、ＦＯ関数関連処理回路８００と同一な構成については、その説明を省略する。【００８８】
図１０Ｂに示すＦＯ関数関連処理回路１０００は、ＦＯ関数関連処理回路８００が備えているマルチプレクサ８０１Ｒの代わりに、マルチプレクサ１００１Ｒを備えている。また、ＦＯ関数関連処理回路１０００は、ＦＯ関数関連処理回路８００が備えていたデマルチプレクサ８２１を備えていない。【００８９】
マルチプレクサ８０１Ｒは３入力１出力のマルチプレクサであるが、マルチプレクサ１００１Ｒは２入力１出力のマルチプレクサである。したがって、ＦＯ関数関連処理回路１０００は、ＦＯ関数関連処理回路８００よりも回路サイズを小さくできる。マルチプレクサ１００１Ｒは、レジスタＲｅｇ−Ｌに格納された３２ビットデータＬの下位１６ビットＬＲと“０”の１６ビットデータを入力し、これらを排他的論理和演算器８１３に選択出力する。排他的論理和演算器８１３の出力は、レジスタＲｅｇ−ＦＯ、マルチプレクサ８２３及び排他的論理和演算器５２５に入力する。
｛ＦＯ関数関連処理回路の第２の実施形態の動作｝
図１０Ｂに示すＦＯ関数関連処理回路１０００は、上記処理アルゴリズムＡＬ２の処理を、サイクル１、サイクル３、サイクル２の順に実行する。以下、ＦＯ関数関連処理回路１０００の動作を、処理アルゴリズムＡＬ２の各サイクル毎に説明する。
｛サイクル１ａ（処理アルゴリズムＡＬ２のサイクル１）｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−Ｌから入力する１６ビットデータＬＬを排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータＬＬと外部入力する鍵ＫＯi1の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、上記演算結果を外部入力する鍵ＫＩi1を用いて変換し、その変換結果を排他的論理和演算器８１３に出力する。一方、マルチプレクサ１００１Ｒは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータの下位１６ビットＬＲを排他的論理和演算器８１３に選択出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２からの入力データとマルチプレクサ１００１Ｒからの入力データ（ＬＲ）の排他的論理和を演算し、その演算結果ｔ１をレジスタＲｅｇ−ＦＯ、マルチプレクサ８２３及び排他的論理和演算器５２５に出力する。レジスタＲｅｇ−ＦＯは、入力する１６ビットデータｔ１を格納する。【００９０】
排他的論理和演算器５２５は、上記１６ビットデータｔ１とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの下位１６ビットＲＲの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータの下位１６ビットＲＲとして格納する。【００９１】
マルチプレクサ８２３は、上記１６ビットデータｔ１を排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、その１６ビットデータｔ１とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの上位１６ビットＲＬの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの上位１６ビットＲＬとして格納する。
｛サイクル２ａ（処理アルゴリズムＡＬ２のサイクル３）｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−ＦＯに格納されている１６ビットデータｔ１を排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータｔ１と外部入力する鍵ＫＯi3の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、その演算結果を外部入力する鍵ＫＩi3を用いて変換し、その変換結果を排他的論理和演算器８１３に出力する。マルチプレクサ１００１Ｒは、１６ビットデータ“０”（１６ビットが全て“０”のデータ）を排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２からの入力と上記１６ビットデータ“０”の排他的論理和を演算し、その演算結果（１６ビットデータ）を、レジスタＲｅｇ−Ｒ、マルチプレクサ８２３及び排他的論理和演算器５２５に出力する。したがって、サイクル２の場合と同様に、レジスタＲｅｇ−ＦＯ、マルチプレクサ８２３及び排他的論理和演算器５２５には、ＦＩ関数処理部８１２の処理結果がそのまま入力する。排他的論理和演算器５２５は、そのＦＩ関数処理部８１２の処理結果とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの下位１６ビットＲＲの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの下位１６ビットＲＲとして格納する。【００９２】
マルチプレクサ８２３は、鍵ＫＯi4を排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、その鍵ＫＯi4とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの上位１６ビットＲＬの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を３２ビットデータＲの上位１６ビットＲＬとして格納する。
｛サイクル３ａ（処理アルゴリズムＡＬ２のサイクル２）｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータの下位１６ビットＬＲを排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータＬＲと外部入力される鍵ＫＯi2を排他的論理和し、その論理演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、その論理演算結果を外部入力される鍵ＫＩi2を用いて変換し、その変換結果（１６ビットデータｔ３）を排他的論理和演算器８１３に出力する。【００９３】
マルチプレクサ１００１Ｒは、“０”の１６ビットデータを排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２から入力する上記１６ビットデータｔ３と上記“０”の１６ビットデータの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−ＦＯ、マルチプレクサ８２３及び排他的論理和演算器５２５に出力する。したがって、この場合、ＦＩ関数処理部８１２の出力（１６ビットデータｔ３）は、レジスタＲｅｇ−ＦＯ、マルチプレクサ８２３及び排他的論理和演算器５２５に入力する。【００９４】
排他的論理和演算器５２５は、上記１６ビットデータｔ３とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの下位１６ビットＲＲの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの下位１６ビットＲＲとして格納する。【００９５】
マルチプレクサ１００１Ｒは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータＬの下位１６ビットＬＲを排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２から入力する上記１６ビットデータｔ３とマルチプレクサ１００１Ｒから入力する上記１６ビットデータＬＲの排他的論理和を演算し、その演算結果を、レジスタＲｅｇ−ＦＯ、マルチプレクサ８２３及び排他的論理和演算器５２５に出力する。マルチプレクサ８２３は、上記１６ビットデータｔ３を排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、その１６ビットデータｔ３とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの上位１６ビットＲＬの排他的論理和を演算し、その演算結果（１６ビットデータ）をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの上位１６ビットＲＬとして格納する。【００９６】
このように、サイクル２においては、排他的論理和演算器８１３の出力ｔ３はレジスタＲｅｇ−ＦＯに格納しない。ｔ３は、レジスタＲｅｇ−Ｒに保持されている１６ビットデータＲＲ及び１６ビットデータＲＬと直接に排他的論理和される。【００９７】
ところで、前記処理アルゴリズムＡＬ２は、サイクル２相当の処理をサイクル１の前に実行することができる。この場合の処理アルゴリズムを以下に示す。
｛処理アルゴリズムＡＬ２の変形例（処理アルゴリズムＡＬ２ｖ）｝
［サイクル１］【００９８】
【数１６】
2009090689.tif 000018
（t3はレジスタに格納せず、RR,RLに直接排他的論理和する）
［サイクル２］【００９９】
【数１７】
2009090689.tif 000019
(t1はレジスタに格納する)
［サイクル３］【０１００】
【数１８】
2009090689.tif 000020
処理アルゴリズムＡＬ２と処理アルゴリズムＡＬ２ｖは、サイクル１とサイクル２の実行順序が異なるだけなので、上記処理アルゴリズムＡＬ２ｖを実行する装置として、図１０Ｂに示すＦＯ関数関連処理回路１０００を利用できる。但し、この場合、ＦＯ関数関連処理回路１０００の実行制御は処理アルゴリズムＡＬ２ｖに従う必要があるため、ＦＯ関数関連処理回路１０００の実行を制御する制御部は変更が必要である。この制御部の変更は、ハードウェアまたはソフトウェアのいずれの変更によっても可能である。【０１０１】
尚、上記ＦＯ関数関連処理回路１０００を、処理アルゴリズムＡＬ２をサイクル１、サイクル２、サイクル３の順に実行するような構成に変更することも可能である。この場合、サイクル２においては、排他的論理和演算器８１３の演算結果がレジスタＲｅｇ−ＦＯに格納されないようにする必要がある。例えば、レジスタＲｅｇ−ＦＯの入力に対して、サイクル２の処理期間中だけオフにするスイッチを設ける。または、排他的論理和演算器８１３とレジスタＲｅｇ−ＦＯの間の単純分岐の箇所のマルチプレクサを配置する。このマルチプレクサは、サイクル１においては左右の両方向に出力し、サイクル２においては右方向だけに出力する。また、サイクル３においては、左右両方向または右方向だけに出力する。
［第３の実施形態］
｛手法｝
本発明の第３実施形態のＦＯ関数関連処理回路の処理アルゴリズムは、上述した図１０Ａに示すＦＯ関数関連処理回路の処理アルゴリズムを、さらに等価変換したものである。【０１０２】
この等価変換を、図１１Ａ、１１Ｂを参照して説明する。図１１Ａは、図１０Ａに示す第２実施形態のＦＯ関数関連処理回路の処理アルゴリズムと同様な図である。
図１１Ｂに示す第３の実施形態のＦＯ関数関連処理回路は、図１１Ａに示す処理アルゴリズムにおいて、“０”の１６ビットデータが入力していた排他的論理和９１４、６３２を、鍵ＫＯi4が入力する排他的論理和１１１４、１１３２に変更する。そして、この変更に伴い、鍵ＫＯi4が入力していた排他的論理和６４２を削除する。これにより、排他的論理和の論理演算が１つ削減される。
｛ＦＯ関数関連処理回路の第３の実施形態の処理アルゴリズムＡＬ３｝
図１１Ｂに示す処理アルゴリズムＡＬ３は、下記のサイクル１〜３から構成される。【０１０３】
［サイクル１］【０１０４】
【数１９】
2009090689.tif 000021
（t1はレジスタに格納する）
［サイクル２］【０１０５】
【数２０】
2009090689.tif 000022
（t3はレジスタに格納せず、RR,RLに直接排他的論理和する）
［サイクル３］【０１０６】
【数２１】
2009090689.tif 000023
｛ＦＯ関数関連処理回路の第３の実施形態のハードウェア構成｝
図１２は、図１１Ｂに示す処理アルゴリズムをハードウェア化したＦＯ関数関連処理回路の構成例を示す図である。尚、図１２において、図１０Ｂに示す回路の構成要素と同じ構成要素には同じ符号を付与している。【０１０７】
図１２に示すＦＯ関数関連処理回路１２００の構成について説明する。以下に述べる説明では、上述したＦＯ関数関連処理回路１０００が備える構成の説明は省略し、ＦＯ関数関連処理回路１０００と異なる構成要素について説明する。上記処理アルゴリズムＡＬ３は、サイクル２とサイクル３の順序を入れ替えて実行しても最終的な処理結果は変わらない。ＦＯ関数関連処理回路１２００は、上記処理アルゴリズムＡＬ３を、サイクル１、サイクル３、サイクル２の順に実行するものである。【０１０８】
ＦＯ関数関連処理回路１２００は、ＦＯ関数関連処理回路１０００が備えるマルチプレクサ１００１Ｒの代わりに、マルチプレクサ１２０１Ｒを備える。マルチプレクサ１２０１Ｒは、レジスタＲｅｇ−Ｒに格納されている３２ビットデータＬの下位１６ビットＬＲと外部入力する１６ビットの鍵ＫＯi4を入力し、いずれか一方を排他的論理和演算器８１３に選択出力する。また、ＦＯ関数関連処理回路１２００は、ＦＯ関数関連処理回路１０００が備えるマルチプレクサ８２３の代わりに、マルチプレクサ１２２３を備える。マルチプレクサ１２２３は、排他的論理和演算器８１３の出力（１６ビットの論理演算結果）と“０”の１６ビットデータを入力し、いずれか一方を排他的論理和演算器５２４に出力する。
｛ＦＯ関数関連処理回路の第３の実施形態の動作｝
図１２に示すＦＯ関数関連処理回路１０００は、上記処理アルゴリズムＡＬ３の処理をサイクル１、サイクル３、サイクル２の順に実行する。以下、ＦＯ関数関連処理回路１０００の動作を処理アルゴリズムＡＬ３の各サイクル毎に説明する。
｛サイクル１ｂ（処理アルゴリズムＡＬ３のサイクル１）｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−Ｌから入力する１６ビットデータＬＬを排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータＬＬと外部入力する鍵ＫＯi1の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、上記演算結果を外部入力する鍵ＫＩi1を用いて変換し、その変換結果を排他的論理和演算器８１３に出力する。一方、マルチプレクサ１２０１Ｒは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータの下位１６ビットＬＲを排他的論理和演算器８１３に選択出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２からの入力データとマルチプレクサ８０１Ｒからの入力データ（ＬＲ）の排他的論理和を演算し、その演算結果ｔ１をレジスタＲｅｇ−ＦＯ、マルチプレクサ１２２３及び排他的論理和演算器５２５に出力する。レジスタＲｅｇ−ＦＯは、入力する１６ビットデータｔ１を格納する。【０１０９】
排他的論理和演算器５２５は、上記１６ビットデータｔ１とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの下位１６ビットＲＲの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータの下位１６ビットＲＲとして格納する。【０１１０】
マルチプレクサ１２２３は、上記１６ビットデータｔ１を排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、その１６ビットデータｔ１とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの上位１６ビットＲＬの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その論理演算結果を、３２ビットデータＲの上位１６ビットＲＬとして格納する。
｛サイクル２ｂ（処理アルゴリズムＡＬ３のサイクル３）｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−ＦＯに格納されている１６ビットデータｔ１を排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータｔ１と外部入力する鍵ＫＯi3の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、その論理演算結果を外部入力する鍵ＫＩi3を用いて変換し、その変換結果を排他的論理和演算器８１３に出力する。マルチプレクサ１２０１Ｒは、１６ビットの鍵ＫＯｉ４を排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２からの入力と上記鍵ＫＯi4の排他的論理和を演算し、その演算結果（１６ビットデータ）を、レジスタＲｅｇ−Ｒ、マルチプレクサ１２２３及び排他的論理和演算器５２５に出力する。排他的論理和演算器５２５は、排他的論理和演算器８１３からの入力（上記論理演算結果）とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの下位１６ビットＲＲの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの下位１６ビットＲＲとして格納する。【０１１１】
マルチプレクサ１２２３は、“０”の１６ビットデータを排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、レジスタＲｅｇ−Ｒに格納されている上位１６ビットＲＬと上記“０”の１６ビットデータの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの上位１６ビットＲＬとして格納する。
｛サイクル３ｂ（処理アルゴリズムＡＬ１３のサイクル２）｝
マルチプレクサ８０１Ｌは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータの下位１６ビットＬＲを排他的論理和演算器８１１に選択出力する。排他的論理和演算器８１１は、その１６ビットデータＬＲと外部入力される鍵ＫＯi2の排他的論理和を演算し、その演算結果をＦＩ関数処理部８１２に出力する。ＦＩ関数処理部８１２は、その演算結果を外部入力される鍵ＫＩi2を用いて変換し、その変換結果（１６ビットデータｔ３）を排他的論理和演算器８１３に出力する。【０１１２】
マルチプレクサ１２０１Ｒは、“１６ビットの鍵ＫＯi4を排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２から入力する上記１６ビットデータｔ３と上記１６ビットの鍵ＫＯi4の排他的論理和を演算し、その演算結果をレジスタＲｅｇ−ＦＯ、マルチプレクサ１２２３及び排他的論理和演算器５２５に出力する。したがって、この場合、ＦＩ関数処理部８１２の出力（１６ビットデータｔ３）は、レジスタＲｅｇ−ＦＯ、マルチプレクサ１２２３及び排他的論理和演算器５２５に入力する。【０１１３】
排他的論理和演算器５２５は、上記１６ビットデータｔ３とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの下位１６ビットＲＲの排他的論理和を演算し、その演算結果をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの下位１６ビットＲＲとして格納する。【０１１４】
マルチプレクサ１２０１Ｒは、レジスタＲｅｇ−Ｌに格納されている３２ビットデータＬの下位１６ビットＬＲを排他的論理和演算器８１３に出力する。排他的論理和演算器８１３は、ＦＩ関数処理部８１２から入力する上記１６ビットデータｔ３とマルチプレクサ１２０１Ｒから入力する上記１６ビットデータＬＲの排他的論理和を演算し、その演算結果を、レジスタＲｅｇ−ＦＯ、マルチプレクサ１２２３及び排他的論理和演算器５２５に出力する。マルチプレクサ１２２３は、上記１６ビットデータｔ３を排他的論理和演算器５２４に選択出力する。排他的論理和演算器５２４は、その１６ビットデータｔ３とレジスタＲｅｇ−Ｒに格納されている３２ビットデータＲの上位１６ビットＲＬの排他的論理和を演算し、その演算結果（１６ビットデータ）をレジスタＲｅｇ−Ｒに出力する。レジスタＲｅｇ−Ｒは、その演算結果を、３２ビットデータＲの上位１６ビットＲＬとして格納する。【０１１５】
ｔ３は、レジスタＲｅｇ−Ｒに保持されている１６ビットデータＲＲ及び１６ビットデータＲＬと直接に排他的論理和される。
上述したように、サイクル３においては、レジスタＲｅｇ−Ｒに格納される３２ビットデータＲの更新は、下位１６ビットＲＲのみであり上位１６ビットＲＬの更新は行われない。このため、サイクル３においては、レジスタＲｅｇ−Ｒの更新は下位１６ビットＲＲのみでよい。この場合、マルチプレクサ１２２３は、“０”の下位１６ビットＲＲを排他的論理和演算器５２４に選択出力する必要はない。したがって、ＦＯ関数関連処理回路１２００において、マルチプレクサ１２２３をスイッチに代替する構成も可能である。【０１１６】
処理アルゴリズムＡＬ３のサイクル１は、処理アルゴリズムＡＬ２のサイクル１と同様である。処理アルゴリズムＡＬ３は、サイクル１とサイクル２の実行順序を交換することが可能である。この場合の処理アルゴリズムを以下に示す。
｛処理アルゴリズムＡＬ３の変形例（処理アルゴリズムＡＬ３ｖ）｝
［サイクル１］【０１１７】
【数２２】
2009090689.tif 000024
［サイクル２］【０１１８】
【数２３】
2009090689.tif 000025
（t1はレジスタに格納する）
［サイクル３］【０１１９】
【数２４】
2009090689.tif 000026
処理アルゴリズムＡＬ３ｖは、サイクル１とサイクル２の実行順序が異なるだけなので、上記処理アルゴリズムＡＬ３ｖを実行する装置として、図１２に示すＦＯ関数関連処理回路１２００を利用できる。但し、この場合、ＦＯ関数関連処理回路１２００の実行制御は処理アルゴリズムＡＬ３ｖに従う必要があるため、ＦＯ関数関連処理回路１２００の実行を制御する制御部の変更は必要である。この制御部の変更は、ハードウェアまたはソフトウェアのいずれでも可能である。【０１２０】
尚、上記ＦＯ関数関連処理回路１２００を、処理アルゴリズムＡＬ３をサイクル１、サイクル２、サイクル３の順に実行するような構成に変更することも可能である。この場合、サイクル２においては、排他的論理和演算器８１３の演算結果がレジスタＲｅｇ−ＦＯに格納されないようにする必要がある。例えば、レジスタＲｅｇ−ＦＯの入力に対して、サイクル２の処理期間中だけオフにするスイッチを設ける。または、排他的論理和演算器８１３とレジスタＲｅｇ−ＦＯの間の単純分岐の箇所のマルチプレクサを配置する。このマルチプレクサは、サイクル１においては左右の両方向に出力し、サイクル２においては右方向だけに出力する。また、サイクル３においては、左右両方向または右方向だけに出力する。【０１２１】
上述した本発明の第1〜第３実施形態のＦＯ関数関連処理回路（８００、１０００、１２００）による回路規模の削減効果を下記の表１に示す。尚、表１では、便宜上、デマルチプレクサもマルチプレクサに含めている。この場合、デマルチプレクサは「2 in 1マルチプレクサ」に含める。 また、レジスタには、レジスタＲｅｇ−Ｌ、Ｒｅｇ−Ｒは含まれていない。尚、「2 in 1  マルチプレクサ」は２入力１出力のマルチプレクサを、「3 in 1 マルチプレクサ」は３入力１出力のマルチプレクサを意味する。
【０１２２】
【表１】
2009090689.tif 000027
上記表１に示すように、本発明の各実施形態によれば、レジスタサイズを半減できる。さらに、マルチプレクサのサイズも削減できる。
［第４の実施形態］
上述した第１〜第３の実施形態の機能は、コンピュータによって実行されるプログラムによっても実現可能である。以下に、それらの実施形態について説明する。以下に述べる実施形態は、本発明を、携帯電話やネットワーク対応の家電機器などの組み込み機器に適用したものである。
｛組み込み機器の第１の構成｝
図１３は、本発明の実施形態である組み込み機器の第１の構成を示す図である。図１３に示す組み込み機器２０００Ａは、ＣＰＵ２１００Ａ、不揮発性メモリ２２００及び揮発性メモリ２３００Ａから構成される。ＣＰＵ２１００Ａは、不揮発性メモリ２２００及び揮発性メモリ２３００Ａとバス（不図示）によって接続されている。【０１２３】
ＣＰＵ２１００Ａは、ＡＬＵ(Arithmetic Logic Unit)２１０１、命令レジスタ（不図示）、デコーダ（命令デコーダ）２１０３、制御信号生成回路２１０４、プログラムカウンタ２１０５、複数のレジスタ（レジスタＬＬ、レジスタＬＲ、レジスタＲＬ、レジスタＲＲ、レジスタａ、レジスタｂ、レジスタＸ、・・・、レジスタＹ）及びアドレス制御回路２１０６を備える。これら複数のレジスタのビット幅は１６ビットである。【０１２４】
不揮発性メモリ２２００は、例えばフラッシュメモリやＲＯＭ(Read On Memory)であり、上述した第１〜第３の実施形態の処理アルゴリズムをＣＰＵ２１００Ａが実行するための命令が記述されたプログラム（ファームウェア）２２０１を格納している。【０１２５】
ＣＰＵ２１００Ａは、不揮発性メモリ２２００からファームウェア２２０１内の命令を先頭から順次読み出し、その命令を命令レジスタに格納する、デコーダ２１０３は、命令レジスタに格納されている命令を解読し、命令内容を制御信号生成回路２１０４に出力する。制御信号生成回路２１０４は、その命令内容を基に、前記命令で指定された演算に対応する命令指示信号をＡＬＵ２１０１に出力する。ＡＬＵ２１０１は、制御信号生成回路２１０４から入力する命令指示信号にしたがって算術演算や論理演算を実行する。これらの演算で使用されるデータはレジスタに格納されている。ＡＬＵ２１０１は、演算で使用するデータを、そのデータが格納されているレジスタから読み出し、それらを用いて演算を実行する。そして、その演算結果を該当するレジスタに書き込む。プログラムカウンタ２１０５は、ＣＰＵ２１００Ａが実行中のファームウェア２２０１の命令の格納アドレスを格納する。プログラムカウンタ２１０５は、ＣＰＵ２１００Ａが現在実行中の命令のアドレスを格納し、その命令の実行が終了する毎にカウントアップされる。アドレス制御回路２１０６は、ＣＰＵ２１００Ａが実行する命令の格納アドレスや読み出し／書き込みを行うデータの格納アドレスを不揮発性メモリ２２００や揮発性メモリ２３００Ａに出力する。また、揮発性メモリ３３００から読み出すべきデータの格納アドレスを揮発性メモリ３３００に出力する。このアドレス出力により、ファームウェア２２０１の命令が不揮発性メモリ２２００から読み出され、命令レジスタに格納される。また、平文データや鍵データが、揮発性メモリ３３００から読み出され、ＣＰＵ２１００Ａ内のレジスタに格納される。【０１２６】
揮発性メモリ２３００Ａは、ＲＡＭ(Random Access Memory)等の半導体メモリであり、平文データ２３０１、暗号文データ２３０２、鍵データ２３０３を格納する記憶域を備えている。【０１２７】
平文データ２３０１は、暗号化の対象となるデータである。平文データ２３０１は、その先頭から６４ビット単位でブロック分割され、ブロック単位で暗号化される。６４ビットのブロックデータは、上位３２ビットのデータＬと下位３２ビットのデータＲに分割される。そして、さらに、上位３２ビットデータＬは、上位１６ビットのデータＬＬと下位１６ビットのデータＬＲに分割される。また、下位３２ビットデータＲは、上位１６ビットのデータＲＬと下位１６ビットのデータＲＲに分割される。ＦＩ関数処理においては、上位３２ビットデータＬＬまたは下位１６ビットデータＬＲと鍵ＫＯik（ｋ＝１，２）との排他的論理和と、鍵ＫＩik（ｋ＝１，２）を用いてデータ処理が行われる。平文データ２３０１の個々のブロックデータ（６４ビットデータ）は、本実施形態のプログラム（ファームウェア）をＣＰＵ２１００Ａが実行することによって、６４ビット単位の暗号データに暗号化される。この暗号データは、上記プログラムの実行終了直前に暗号文データ２３０２として揮発性メモリ２３００Ａに格納される。【０１２８】
平文データ２３０１の暗号化は１２８ビットの秘密鍵Ｋを用いて行われる。本実施形態が平文データ２３０１を暗号化するために使用する鍵（ラウンド鍵）ＫＯi1〜ＫＯi4、ＫＩi1〜ＫＩi3、ＫＬi1、ＫＬi2は、上記秘密鍵Ｋから生成される。より詳細に説明すると、まず、秘密鍵Ｋを、ＭＳＢ側から、８個の１６ビットの部分鍵Ｋ１，Ｋ２，・・・、Ｋ８に分割する。そして、これら８個の部分鍵Ｋ１〜Ｋ８を用いた鍵スケジューリング処理（鍵拡張処理）を行うことによって、拡大鍵ＫＯi1〜ＫＯi4、ＫＩi1〜ＫＩi3、ＫＬi1、ＫＬi2を生成する。ＦＯ関数１個につき拡大鍵ＫＯij（ｊ＝１〜４）は６４ビット、拡大鍵ＫＩik（ｋ＝１〜３）は４８ビットである。また、ＦＬ関数１個につき、拡大鍵ＫＬim（ｍ＝１、２）は３２ビットである。拡大鍵ＫＯijと拡大鍵ＫＩikはＦＯ関数で使用され、拡大鍵ＫＩikはＦＩ関数で使用される。また、拡大鍵ＫＬimはＦＬ関数で使用される。尚、拡大鍵ＫＯi1〜ＫＯi4は、ＭＩＳＴＹ１の場合には、１２８ビットの秘密鍵Ｋを１６ビット単位で分割して得られる鍵Ｋ１、Ｋ２、Ｋ３、Ｋ４、Ｋ５、Ｋ６、Ｋ７、Ｋ８の内の４個である。【０１２９】
鍵データ２３０３は、平文データ２３０１を暗号化するために使用する鍵に関するデータであり、秘密鍵Ｋ（Ｋ１〜Ｋ８）及び拡大鍵Ｋ´１〜Ｋ´８を含むデータである。尚、秘密鍵Ｋ１〜Ｋ８、拡大鍵Ｋ´１〜Ｋ´８と、拡大鍵ＫＯi1〜ＫＯi4、ＫＩi1〜ＫＩi3、ＫＬi1、ＫＬi2との対応関係は前記「暗号記述仕様書  ＭＩＳＴＹ１」に記述されている通りである。【０１３０】
ＣＰＵ２１００Ａは、平文データ２３０１を鍵データ２３０３を用いて暗号文データ２３０２に変換するが、このデータ変換処理過程における中間結果はレジスタａのみ、またはレジスタａ、ｂに保持される。平文データ２３０１をデータ変換して得られる暗号データ（６４ビット）は、ＡＬＵ２１０１によりレジスタＬＬ、ＬＲ、ＲＬ、ＲＲに格納される。ＣＰＵ２１００Ａ内のレジスタと不揮発性メモリ２２００間でのデータの入出力（平文データ２３０１の入力、暗号文データ２３０２の出力、鍵データ２３０３の入力等）は、ネットワークやバス等を介して行われる。【０１３１】
第１の構成の組み込み機器２０００Ａにおいては、平文データ２３０１と鍵データ２３０３をＣＰＵ２１００Ａ内のレジスタに格納した後、平文データ２３０１をＦＯ関数処理と排他的論理和によりブロック単位で暗号化する。平文データ２３０１は、ＣＰＵ２１００Ａにより、ブロック単位で揮発性メモリ３３００から読み出され、レジスタＬＬ、ＬＲ、ＲＬ、ＲＲに格納される。レジスタＬＬ、ＬＲ、ＲＬ、ＲＲには、それぞれ、データＬＬ、ＬＲ、ＲＬ、ＲＲが格納される。鍵データ２３０３は、ＣＰＵ２１００Ａにより、揮発性メモリ３３００から読み出され、レジスタＸなどのレジスタに格納される。
｛組み込み機器の第２の構成｝
図１４は、本発明の実施形態である組み込み機器の第２の構成を示す図である。図１４において、図１３に示す組み込み機器が備える構成要素と同一な構成要素には同じ符号を付与している。【０１３２】
図１４に示す組み込み機器２０００Ｂが図１３に示す組み込み機器２０００Ａと構成が異なる点は、まず、ＣＰＵのレジスタ構成である。組み込み機器２０００ＢのＣＰＵ２１００Ｂは、レジスタＸ、・・・、Ｙを備えているが、レジスタＬＬ、ＬＲ、ＲＬ、ＲＲ、ａ、ｂは備えていない。また、揮発性メモリ２３００Ｂは、中間結果２３０４を格納する領域を備えている。中間結果２３０４は、ＣＰＵ２１００Ｂが平文データ２３０１を暗号文データ２３０２に変換する処理過程において一時的に記憶する必要があるデータ（中間結果）であり、本実施形態においては、データＬＬ、ＬＲ、ＲＬ、ＲＲなどが該当する。【０１３３】
組み込み機器２０００Ｂにおいては、揮発性メモリ２３００Ｂ内の平文データ２３０１は、ＣＰＵ２１００Ｂ内のレジスタＸ、・・・、Ｙに格納される。また、鍵データ２３０３も、揮発性メモリ２３００ＢからレジスタＸ、・・・、Ｙに格納される。ＣＰＵ２１００Ｂは、レジスタＸ、・・・、Ｙに格納されている平文データ２３０１と鍵データ２３０３を用いて、ＡＬＵ２１０１により、平文データ２３０１を暗号文データに変換する。この暗号文データは、レジスタＸ、・・・、Ｙに格納された後、揮発性メモリ２３００Ｂに暗号文データ２３０２として書き込まれる。平文データ２３０１を暗号文データ２３０２に変換する処理過程において、中間結果２３０４は、レジスタＸ、・・・、Ｙを介して、揮発性メモリ２３００ＢとＡＬＵ２１０１の間で授受される。
｛組み込み機器の第３の構成｝
図１５は、本発明の実施形態である組み込み機器の第３の構成を示す図である。図１５において、図１３に示す組み込み機器２０００Ａが備える構成要素と同一な構成要素には同じ符号を付与している。【０１３４】
図１５に示す組み込み機器２０００Ｃと組み込み機器２０００Ａとの構成の相違は、揮発性メモリの構成である。組み込み機器２０００Ｃの揮発性メモリ２３００Ｃは、平文データ２３０１、暗号文データ２３０２、鍵データ２３０３を格納する領域に加え、拡大鍵２３０５を格納する領域も備えている。拡大鍵２３０５は、拡大鍵Ｋ１´〜Ｋ８´などである。これらの拡大鍵の内、ＦＯ関数以外で使用される拡大鍵は、ＣＰＵ２１００Ｃが処理を実行する際には、揮発性メモリ２３００Ｃから読み出されてＡＬＵ２１０１に入力する。また、上述したように、拡大鍵Ｋ１´〜Ｋ８´は、ＦＩ関数を用いて秘密鍵Ｋ（Ｋ１〜Ｋ８）から生成されるので、組み込み機器２０００Ｃが秘密鍵Ｋから拡大鍵Ｋ１´〜Ｋ８´を生成するような構成にした場合、ＣＰＵ２１００により生成された拡大鍵Ｋ１´〜Ｋ８´は、ＡＬＵ２１０１からレジスタＸ、・・・、Ｙに格納された後、揮発性メモリ２３００Ｃに拡大鍵２３０５として書き込まれる。
［ソフトウェア実装形態］
次に、上記第１の構成の組み込み機器２０００Ａにおいて、上記第１〜第３の実施形態のＦＯ関数関連処理回路の機能をソフトウェア処理により実現するプログラムの実装形態について説明する。
｛第１の実施形態のＦＯ関数関連処理回路のソフトウェア実装形態｝
図１６は、上記第１の実施形態のＦＯ関数関連処理回路の機能を実現するために、上記第１の構成の組み込み機器２０００Ａに実装されるファームウェア２２０１のアルゴリズムを示すフローチャートである。図１６のフローチャートに示すアルゴリズムは、上記処理アルゴリズムＡＬ1のサイクル実行順序を変更したものとなっている。すなわち、図１６のフローチャートに示すアルゴリズムは、上記処理アルゴリズムＡＬ1の各サイクルを、サイクル１、サイクル３、サイクル２の順序で実行するようになっている。【０１３５】
図１６のフローチャートに示すアルゴリズムを説明する。
ステップＳ１１において、上記第１の実施形態の処理アルゴリズムＡＲ1のサイクル１に相当する処理、【０１３６】
【数２５】
2009090689.tif 000028
を実行し、この処理の実行結果（＝ｔ１）をレジスタＡに格納する。
次に、ステップＳ１２において、上記処理アルゴリズムＡＲ1のサイクル３に相当する処理を実行する。ステップＳ１２においおては、まず、【０１３７】
【数２６】
2009090689.tif 000029
の処理を実行し、その実行結果を「ＲＲが格納されているレジスタ」に格納する。
続いて、【０１３８】
【数２７】
2009090689.tif 000030
の処理を実行し、その実行結果を「ＲＬが格納されているレジスタ」に格納する。【０１３９】
次に、ステップＳ１３において、上記処理アルゴリズムＡＲ1のサイクル２に相当する処理を実行する。
ステップＳ１３においては、【０１４０】
【数２８】
2009090689.tif 000031
の処理を実行し、その実行結果（＝ｔ３）をレジスタＡに格納する。【０１４１】
そして、最後に、ステップＳ１４の処理を実行する。
ステップＳ１４においては、まず、【０１４２】
【数２９】
2009090689.tif 000032
の処理を実行し、その実行結果を「ＲＲが格納されているレジスタ」に格納する。
続いて、【０１４３】
【数３０】
2009090689.tif 000033
の処理を実行し、その実行結果を「ＲＬが格納されているレジスタ」に格納する。
図１７は、図１６のアルゴリズムで動作するプログラムの実施例を示す図である。【０１４４】
図１７に示すプログラム３０００Ａは、アセンブリ言語で記述されたソースプログラムである。尚、このプログラム３０００Ａの実行前に、データＬ、Ｒ、秘密鍵Ｋ及び拡大鍵Ｋ１´〜Ｋ８´は、ＣＰＵ２１００内のレジスタに格納される。より詳細に説明すると、データＬの上位１６ビットＬＬはレジスタＬＬに、下位１６ビットＬＲはレジスタＬＲに格納される。また、データＲの上位１６ビットＲＬはレジスタＲＬに、下位１６ビットＲＲはレジスタＲＲに格納される。また、拡大鍵ＫＯi1、ＫＯi2、ＫＯi3、ＫＯi4は揮発性メモリに格納された秘密鍵から、処理対象のＦＯ関数に応じて適切なものが選択されてレジスタＸに格納される。これは、後述するプログラム３０００Ｂ、Ｃについても同様である。【０１４５】
プログラム３０００Ａにおいて、レジスタａは図１６のフローチャートのレジスタＡに相当する。プログラム３０００Ａにおいて、ＭＯＶ命令、ＸＯＲ命令は、全て、レジスタに格納されているデータを使用している。このため、ＣＰＵ２１００Ａは、プログラム３０００Ａを高速で実行可能である。
｛第２の実施形態のＦＯ関数関連処理回路のソフトウェア実装形態｝
図１８は、上記第２の実施形態のＦＯ関数関連処理回路の機能を実現するために、上記第１の構成の組み込み機器２０００Ａに実装されるファームウェア２２０１のアルゴリズムを示すフローチャートである。図１８のフローチャートに示すアルゴリズムは、ＣＰＵ２１００が、なるべく使用レジスタ数を少なくしてプログラムを実行できるように、上記処理アルゴリズムＡＬ２のサイクル実行順序を変更したものとなっている。すなわち、図１８のフローチャートに示すアルゴリズムは、上記処理アルゴリズムＡＬ２の各サイクルを、サイクル１、サイクル３、サイクル２の順序で実行するようになっている。このように、サイクル１に続けてサイクル３を実行することにより、サイクル３の処理終了後に、ＣＰＵ２１００はレジスタＡを自由に使用できるようになる。【０１４６】
図１８のフローチャートのアルゴリズムを説明する。
ステップＳ２１、Ｓ２２において、上記第２の実施形態の処理アルゴリズムＡＬ２のサイクル１に相当する処理を実行する。ステップＳ２１においては、【０１４７】
【数３１】
2009090689.tif 000034
の処理を実行し、この処理の実行結果（＝ｔ１）をレジスタＡに格納する。
ステップＳ２２においては、まず、【０１４８】
【数３２】
2009090689.tif 000035
の処理を実行し、この実行結果を「ＲＲが格納されているレジスタ」に格納する。
次に、【０１４９】
【数３３】
2009090689.tif 000036
の処理を実行し、その実行結果を「ＲＬが格納されているレジスタ」に格納する。【０１５０】
次に、ステップＳ２３において、上記処理アルゴリズムＡＬ２のサイクル３に相当する処理を実行する。ステップＳ２３においては、まず、【０１５１】
【数３４】
2009090689.tif 000037
の処理を実行し、その実行結果を「ＲＲが格納されているレジスタ」に格納する。
続いて、【０１５２】
【数３５】
2009090689.tif 000038
の処理を実行し、その実行結果を「ＲＬが格納されているレジスタ」に格納する。【０１５３】
そして、最後に、ステップＳ２４、２５において、上記処理アルゴリズムＡＬ２のサイクル２に相当する処理を実行する。
ステップＳ２４においては、【０１５４】
【数３６】
2009090689.tif 000039
の処理を実行し、その実行結果（＝ｔ３）をレジスタＡに格納する。【０１５５】
続いて、ステップＳ２５において、まず、【０１５６】
【数３７】
2009090689.tif 000040
の処理を実行し、その実行結果を「ＲＲが格納されているレジスタ」に格納する。
次に、【０１５７】
【数３８】
2009090689.tif 000041
の処理を実行し、その実行結果を「ＲＬが格納されているレジスタ」に格納する。
図１９は、図１８に示すアルゴリズムで動作するプログラムの実施例を示す図である。【０１５８】
図１８に示すプログラム３０００ＢのＭＯＶ命令、ＸＯＲ命令、ＣＡＬＬ命令は、図１７に示すプログラム３０００Ａの同一表記の命令と同様な命令である。プログラム３０００Ｂの命令はレジスタに格納されたデータを使用するため、プログラム３０００Ｂも処理の高速化が可能である。
｛第３の実施形態のＦＯ関数関連処理回路のソフトウェア実装形態｝
図２０は、上記第３の実施形態のＦＯ関数関連処理回路の機能を実現するために、上記第１の構成の組み込み機器に実装されるファームウェア２２０１のアルゴリズムを示すフローチャートである。図２０のフローチャートに示すアルゴリズムは、ＣＰＵ２１００Ａが、なるべく使用レジスタ数を少なくしてプログラムを実行できるように、上記処理アルゴリズムＡＬ３のサイクル実行順序を変更したものとなっている。すなわち、図１６のフローチャートに示すアルゴリズムは、上記処理アルゴリズムＡＬ３の各サイクルを、サイクル１、サイクル３、サイクル２の順序で実行するアルゴリズムとなっている。このように、サイクル１に続けてサイクル３を実行することにより、サイクル３の処理終了後に、ＣＰＵ２１００ＡはレジスタＡを自由に使用できるようになる。【０１５９】
図２０のフローチャートのアルゴリズムを説明する。
ステップＳ３１、Ｓ３２において、上記第３の実施形態の処理アルゴリズムＡＬ３のサイクル１に相当する処理を実行する。ステップＳ３１においては、【０１６０】
【数３９】
2009090689.tif 000042
の処理を実行し、この処理の実行結果（＝ｔ１）をレジスタＡに格納する。【０１６１】
ステップＳ３２においては、まず、【０１６２】
【数４０】
2009090689.tif 000043
の処理を実行し、この実行結果を「ＲＲが格納されているレジスタ」に格納する。【０１６３】
続いて、【０１６４】
【数４１】
2009090689.tif 000044
の処理を実行し、その実行結果を「ＲＬが格納されているレジスタ」に格納する。
次に、ステップＳ３３において、上記処理アルゴリズムＡＬ３のサイクル３に相当する処理を実行する。ステップＳ３３においては、まず、【０１６５】
【数４２】
2009090689.tif 000045
の処理を実行し、その実行結果を「ＲＲが格納されているレジスタ」に格納する。
続いて、ステップＳ３４、Ｓ３５において、上記処理アルゴリズムＡＬ３のサイクル２に相当する処理を実行する。ステップＳ３４においては、【０１６６】
【数４３】
2009090689.tif 000046
の処理を実行し、その実行結果をレジスタＡに格納する。【０１６７】
そして、最後に、ステップＳ３５において、まず、【０１６８】
【数４４】
2009090689.tif 000047
の処理を実行し、その実行結果を「ＲＲが格納されているレジスタ」に格納する。【０１６９】
続いて、【０１７０】
【数４５】
2009090689.tif 000048
の処理を実行し、その実行結果を「ＲＬが格納されているレジスタ」に格納する。
図２１は、図２０に示すアルゴリズムで動作するプログラムの実施例を示す図である。【０１７１】
図２１に示すプログラム３０００ＣのＭＯＶ命令、ＸＯＲ命令、ＣＡＬＬ命令は、図１７に示すプログラム３０００Ａの同一表記の命令と同様な命令である。プログラム３０００Ｃの命令はレジスタに格納されたデータを使用するため、プログラム３０００Ｃも処理の高速化が可能である。【０１７２】
本発明は、上述した実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲内で種々に変形して実施することができる。例えば、上記実施形態は、本発明をＭＩＳＴＹ１に適用したものであるが、本発明はＭＩＳＴＹ１に限定されるものではない。本発明は、ＭＩＳＴＹ２、ＫＡＳＵＭＩなどFeistel構造の暗号アルゴリズムの全てに適用可能である。
【産業所の利用可能性】
【０１７３】
本発明は、セキュリティ機能が必要とされる小型電子機器の組み込みシステムとして非常に有用である。
【図１】
2009090689.tif 000049
【図２Ａ】
2009090689.tif 000050
【図２Ｂ】
2009090689.tif 000051
【図２Ｃ】
2009090689.tif 000052
【図３】
2009090689.tif 000053
【図４】
2009090689.tif 000054
【図５】
2009090689.tif 000055
【図６】
2009090689.tif 000056
【図７Ａ】
2009090689.tif 000057
【図７Ｂ】
2009090689.tif 000058
【図８Ａ】
2009090689.tif 000059
【図８Ｂ】
2009090689.tif 000060
【図９Ａ】
2009090689.tif 000061
【図９Ｂ】
2009090689.tif 000062
【図１０Ａ】
2009090689.tif 000063
【図１０Ｂ】
2009090689.tif 000064
【図１１Ａ】
2009090689.tif 000065
【図１１Ｂ】
2009090689.tif 000066
【図１２】
2009090689.tif 000067
【図１３】
2009090689.tif 000068
【図１４】
2009090689.tif 000069
【図１５】
2009090689.tif 000070
【図１６】
2009090689.tif 000071
【図１７】
2009090689.tif 000072
【図１８】
2009090689.tif 000073
【図１９】
2009090689.tif 000074
【図２０】
2009090689.tif 000075
【図２１】
2009090689.tif 000076
【手続補正書】
【提出日】平成22年5月12日(2010.5.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
２ｎビットのデータＬをデータ変換するデータ処理手段と、該データ処理手段の処理結果と２ｎビットのデータＲとを排他的論理和する排他的論理和演算器を備える暗号化装置において、
ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲ、ｎビットのデータ“０”または前記第１のレジスタに格納されているｎビットのデータのいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、該第２の排他的論理和演算器の出力を前記第１のレジスタに出力するデマルチプレクサと、前記第２の排他的論理和演算器の出力またはラウンド鍵ＫＯim（ｍは自然数）を選択出力する第３のマルチプレクサと、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記第３のマルチプレクサの出力とを排他的論理和する第３の排他的論理和演算器と、前記第２のマルチプレクサの出力と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備え、
前記第１のマルチプレクサ、前記第２のマルチプレクサ、前記第３のマルチプレクサ及び前記デマルチプレクサは外部から制御され、前記第１のレジスタは前記デマルチプレクサの出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納することを特徴とする暗号化装置。
【請求項２】
２ｎビットのデータＬをデータ変換するデータ処理手段と、該データ処理手段の処理結果と２ｎビットのデータＲとを排他的論理和する排他的論理和演算器を備える暗号化装置において、
ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲまたはｎビットのデータ“０”のいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、前記第２の排他的論理和演算器の出力またはラウンド鍵ＫＯimを選択出力する第３のマルチプレクサと、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記第３のマルチプレクサの出力とを排他的論理和する第３の排他的論理和演算器と、前記第２の排他的論理和演算器と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備え、
前記第１のマルチプレクサ、前記第２のマルチプレクサ及び前記第３のマルチプレクサは外部から制御され、前記第１のレジスタは前記第２の排他的論理和演算器の出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納することを特徴とする暗号化装置。
【請求項３】
２ｎビットのデータＬをデータ変換するデータ処理手段と、該データ処理手段の処理結果と２ｎビットのデータＲとを排他的論理和する排他的論理和演算器を備える暗号化装置において、
ｎビットのデータを保持する第１のレジスタと、該第１のレジスタに格納されているｎビットのデータ、前記データＬの上位ｎビットＬＬ、前記データＬの下位ｎビットＬＲのいずれか一つを選択出力する第１のマルチプレクサと、該第１のマルチプレクサの出力をラウンド鍵ＫＯij（ｊは自然数）と排他的論理和する第1の排他的論理和演算器と、該第1の排他的論理和演算器の出力を拡大鍵ＫＩik（ｋは自然数）を用いてｎビットデータに変換する第1のデータ処理手段と、前記データＬの下位ｎビットＬＲまたはｎビットのラウンド鍵ＫＯim（ｍは自然数）のいずれか一つを選択出力する第２のマルチプレクサと、該第２のマルチプレクサの出力と前記第1のデータ処理手段の出力を排他的論理和する第２の排他的論理和演算器と、該第２の排他的論理和演算器の出力を入力し、その入力を適切なタイミングで出力する出力手段と、前記データＲを保持する第２のレジスタと、該第２のレジスタに格納されているデータＲの上位ｎビットＲＬと前記スイッチ手段の出力とを排他的論理和する第３の排他的論理和演算器と、前記第２の排他的論理和演算器と前記第２のレジスタに格納されているデータＲの下位ｎビットＲＲを排他的論理和する第４の排他的論理和演算器とを備え、
前記第１のマルチプレクサ、前記第２のマルチプレクサ及び前記出力手段は外部から制御され、前記第１のレジスタは前記第２の排他的論理和演算器の出力を入力して保持し、前記第２のレジスタは、前記第３の排他的論理和演算器の出力をデータＲの上位ｎビットＲＬとして格納すると共に、前記第４の排他的論理和演算器の出力をデータＲの下位ｎビットＲＲとして格納することを特徴とする暗号化装置。
【請求項４】
請求項３記載の暗号化装置であって、
前記出力手段は、ｎビットの“０”データまたは前記第２の排他的論理和演算器の出力を選択出力する第３のマルチプレクサであることを特徴とする。
【請求項５】
請求項１乃至３のいずれか１項に記載の暗号化装置であって、
さらに、前記データＬを入力・保持し、出力する第３のレジスタを備えていることを特徴とする。
【請求項６】
２ｎビットのデータＬをデータ変換し、そのデータ変換結果と２ｎビットのデータＲの他的論理和を演算した後、その論理演算結果を出力する暗号処理方法において、
前記データＬの上位ｎビットＬＬを拡大鍵ＫＯi1と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi1を用いてデータ変換し、そのデータ変換結果を前記データＬの下位ｎビットＬＲと排他的論理和し、その排他的論理和の論理演算結果ｔ１を出力するサイクル１のステップと、
前記データＬの下位ｎビットＬＲをラウンド鍵ＫＯi2と排他的論理和し、その排他的論理和の論理演算結果を拡大鍵ＫＩi2を用いてデータ変換し、そのデータ変換結果を前記サイクル１のステップで出力される論理演算結果ｔ１と排他的論理和し、その排他的論理和の論理演算結果ｔ３を前記データＲの下位ｎビットＲＲと排他的論理和して、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとして出力すると共に、前記論理演算結果ｔ３を前記データＲの上位ｎビットＲＬと排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル２のステップと、
前記論理演算結果ｔ１をラウンド鍵ＫＯi3と排他的論理和し、その排他的論理和の論理演算結果をラウンド鍵ＫＩi3を用いてデータ変換し、そのデータ変換結果をサイクル２で生成された下位ｎビットＲＲと排他的論理和し、その排他的論理和の論理演算結果を新たな下位ｎビットＲＲとすると共に、前記サイクル２のステップで出力される上位ｎビットＲＬをラウンド鍵ＫＯi4と排他的論理和し、その排他的論理和の論理演算結果を新たな上位ｎビットＲＬとして出力するサイクル３のステップと、
を備えることを特徴とする暗号処理方法。
【国際調査報告】
2009090689.tif 000077
2009090689.tif 000078