(57)【特許請求の範囲】
【請求項１】
公開鍵方式の暗号化装置と復号装置からなる暗号化システムであって、
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、Ｈ１はＧ２の元をＧの元に変換するハッシュ関数、Ｈ２はＧ３の元をＺｐの元に変換するハッシュ関数、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
前記暗号化装置は、
平文ｍと、公開鍵として群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５を受け取る暗号化入力部と、
集合Ｚｐの元である乱数ｒを生成する乱数生成部と、
ｕ１＝ｐｋ１＾ｒ
ｕ２＝ｐｋ２＾ｒ
ｓ＝ｍ・（ｐｋ５）＾ｒ・Ｈ１（ｕ１，ｕ２）
α＝Ｈ２（ｕ１，ｕ２，ｓ）
ｖ＝ｐｋ３＾ｒ・ｐｋ４＾（ｒα）
を計算する暗号化計算部と、
ｕ１，ｓ，ｖをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力部と
を備え、
前記復号装置は、
集合Ｚｐの元である６つの乱数ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚを生成して秘密鍵とし、ｇ，ｇ＾ｗ，ｇ＾ｘ１・ｇ＾（ｗｘ２），ｇ＾ｙ１・ｇ＾（ｗｙ２），ｇ＾ｚを群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５からなる公開鍵として公開する鍵生成部と、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力部と、
α’＝Ｈ２（ｃ１，ｃ１＾ｗ，ｃ２）
ｍ＝ｓ・ｕ１＾（−ｚ）・Ｈ１（ｕ１，ｕ１＾ｗ）＾（−１）
を計算する復号計算部と、
ｃ１＾（ｘ１＋ｙ１α’）・ｃ１＾（ｗ（ｘ２＋ｙ２α’））とｃ３とが等しいことを検証する検証部と、
前記検証部の検証が成功した場合には平文ｍを出力し、前記検証部の検証が失敗した場合にはエラーを出力する復号出力部と
を備える
ことを特徴とする暗号化システム。
【請求項２】
公開鍵方式の暗号化装置と復号装置からなる暗号化システムであって、
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、ＨはＧ２の元をＧの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｇ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
前記暗号化装置は、
平文ｍと、公開鍵として群Ｇの元ｐｋと関数ｆ’を受け取る暗号化入力部と、
集合Ｚｐの元である乱数ｒを生成する乱数生成部と、
ｔａｇ＝Ｍａｃｐｋ＾ｒ（ｍ）
ｓ＝ｍ・Ｈ（ｇ＾ｒ，ｔａｇ）・ｐｋ＾ｒ
ｔ＝ｆ’（ｐｋ＾ｒ）
を計算する暗号化計算部と、
ｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力部と
を備え、
前記復号装置は、
集合Ｚｐの元である乱数ｘを生成し、群Ｇを定義域として落し戸付き一方向性置換（ｆ，ｆ−１）を選択し、ｘ，ｆ−１を秘密鍵とし、ｇ＾ｘ，ｆを群Ｇの元ｐｋと関数ｆ’からなる公開鍵として公開する鍵生成部と、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力部と、
ｖ＝ｆ−１（ｃ３）
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ｘ＾（−１）），ｔａｇ））＾（−１）
を計算する復号計算部と、
Ｍａｃｖ（ｍ）とｃ１とが等しいことを検証する検証部と、
前記検証部の検証が成功した場合には平文ｍを出力し、前記検証部の検証が失敗した場合にはエラーを出力する復号出力部と
を備える
ことを特徴とする暗号化システム。
【請求項３】
公開鍵方式の暗号化装置と復号装置からなる暗号化システムであって、
ｐ１，ｐ２は素数、ｎ＝ｐ１・ｐ２、Ｚｐ１は０からｐ１−１までの整数の集合、Ｚｐ２は０からｐ２−１までの整数の集合、Ｚｐ１−１は０からｐ１−２までの整数の集合、Ｚｐ２−１は０からｐ２−２までの整数の集合、Ｚｎは０からｎ−１までの整数の集合、α１はＺｐ１の生成元、α２はＺｐ２の生成元、ＨはＺｎ２の元をＺｎの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｚｎ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を意味する式、φはオイラー関数、ｍは平文として、
前記暗号化装置は、
平文ｍと、公開鍵として整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’を受け取る暗号化入力部と、
集合Ｚｐの元である乱数ｒを生成する乱数生成部と、
ｍｋ＝ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔａｇ＝Ｍａｃｍｋ（ｍ）
ｓ＝ｍ・Ｈ（ｐｋ２＾ｒ，ｔａｇ）・ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔ＝ｆ’（ｐｋ３＾ｒ）
を計算する暗号化計算部と、
ｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力部と
を備え、
前記復号装置は、
（ａ）ｇｃｄ（ｐ１−１，ｐ２−１）がａ１−ａ２の約数となるように、集合Ｚｐ１−１からａ１を集合Ｚｐ２−１からａ２をそれぞれ選択し、
（ｂ）ｔ＝（ｐ１−１）（ｐ２−１）／ｇｃｄ（ｐ１−１，ｐ２−１）とし、
（ｃ）
【数１０】
0005448801.tif 000011
を満たすａ  ｍｏｄ  ｔを計算し、
（ｄ）
【数１１】
0005448801.tif 000012
を満たすα  ｍｏｄ  ｎを計算し、
（ｅ）
【数１２】
0005448801.tif 000013
を満たすβ  ｍｏｄ  ｎを計算し、
（ｆ）ｇｃｄ（ｅ，φ（ｎ））＝１を満たすようにｅを選び、
（ｇ）
【数１３】
0005448801.tif 000014
を満たすｄを求め、
（ｈ）ｆ（ｘ）＝ｘ＾ｅ  ｍｏｄ  ｎ、ｆ−１（ｙ）＝ｙ＾ｄ  ｍｏｄ  ｎを満たす一方向性置換（ｆ，ｆ−１）を選択し、
（ｉ）ｐ１，ｐ２，ａ，ｆ−１を秘密鍵とし、ｎ，α，β，ｆを整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’からなる公開鍵として公開する鍵生成部と、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力部と、
ｖ＝ｆ−１（ｃ３）
ｍｋ＝ｖ  ｍｏｄ  ｎ
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ａ＾（−１）），ｔａｇ））＾（−１）  ｍｏｄ  ｎ
を計算する復号計算部と、
Ｍａｃｍｋ（ｍ）とｃ１とが等しいことを検証する検証部と、
前記検証部の検証が成功した場合には平文ｍを出力し、前記検証部の検証が失敗した場合にはエラーを出力する復号出力部と
を備える
ことを特徴とする暗号化システム。
【請求項４】
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、Ｈ１はＧ２の元をＧの元に変換するハッシュ関数、Ｈ２はＧ３の元をＺｐの元に変換するハッシュ関数、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
平文ｍと、公開鍵として群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５を受け取る暗号化入力部と、
集合Ｚｐの元である乱数ｒを生成する乱数生成部と、
ｕ１＝ｐｋ１＾ｒ
ｕ２＝ｐｋ２＾ｒ
ｓ＝ｍ・（ｐｋ５）＾ｒ・Ｈ１（ｕ１，ｕ２）
α＝Ｈ２（ｕ１，ｕ２，ｓ）
ｖ＝ｐｋ３＾ｒ・ｐｋ４＾（ｒα）
を計算する暗号化計算部と、
ｕ１，ｓ，ｖをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力部と
を備える暗号化装置。
【請求項５】
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、ＨはＧ２の元をＧの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｇ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
平文ｍと、公開鍵として群Ｇの元ｐｋと関数ｆ’を受け取る暗号化入力部と、
集合Ｚｐの元である乱数ｒを生成する乱数生成部と、
ｔａｇ＝Ｍａｃｐｋ＾ｒ（ｍ）
ｓ＝ｍ・Ｈ（ｇ＾ｒ，ｔａｇ）・ｐｋ＾ｒ
ｔ＝ｆ’（ｐｋ＾ｒ）
を計算する暗号化計算部と、
ｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力部と
を備える暗号化装置。
【請求項６】
ｐ１，ｐ２は素数、ｎ＝ｐ１・ｐ２、Ｚｐ１は０からｐ１−１までの整数の集合、Ｚｐ２は０からｐ２−１までの整数の集合、Ｚｐ１−１は０からｐ１−２までの整数の集合、Ｚｐ２−１は０からｐ２−２までの整数の集合、Ｚｎは０からｎ−１までの整数の集合、α１はＺｐ１の生成元、α２はＺｐ２の生成元、ＨはＺｎ２の元をＺｎの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｚｎ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を意味する式、φはオイラー関数、ｍは平文として、
平文ｍと、公開鍵として整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’を受け取る暗号化入力部と、
集合Ｚｐの元である乱数ｒを生成する乱数生成部と、
ｍｋ＝ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔａｇ＝Ｍａｃｍｋ（ｍ）
ｓ＝ｍ・Ｈ（ｐｋ２＾ｒ，ｔａｇ）・ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔ＝ｆ’（ｐｋ３＾ｒ）
を計算する暗号化計算部と、
ｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力部と
を備える暗号化装置。
【請求項７】
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、Ｈ１はＧ２の元をＧの元に変換するハッシュ関数、Ｈ２はＧ３の元をＺｐの元に変換するハッシュ関数、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
集合Ｚｐの元である６つの乱数ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚを生成して秘密鍵とし、ｇ，ｇ＾ｗ，ｇ＾ｘ１・ｇ＾（ｗｘ２），ｇ＾ｙ１・ｇ＾（ｗｙ２），ｇ＾ｚを群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５からなる公開鍵として公開する鍵生成部と、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力部と、
α’＝Ｈ２（ｃ１，ｃ１＾ｗ，ｃ２）
ｍ＝ｓ・ｕ１＾（−ｚ）・Ｈ１（ｕ１，ｕ１＾ｗ）＾（−１）
を計算する復号計算部と、
ｃ１＾（ｘ１＋ｙ１α’）・ｃ１＾（ｗ（ｘ２＋ｙ２α’））とｃ３とが等しいことを検証する検証部と、
前記検証部の検証が成功した場合には平文ｍを出力し、前記検証部の検証が失敗した場合にはエラーを出力する復号出力部と
を備える復号装置。
【請求項８】
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、ＨはＧ２の元をＧの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｇ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
集合Ｚｐの元である乱数ｘを生成し、群Ｇを定義域として落し戸付き一方向性置換（ｆ，ｆ−１）を選択し、ｘ，ｆ−１を秘密鍵とし、ｇ＾ｘ，ｆを群Ｇの元ｐｋと関数ｆ’からなる公開鍵として公開する鍵生成部と、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力部と、
ｖ＝ｆ−１（ｃ３）
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ｘ＾（−１）），ｔａｇ））＾（−１）
を計算する復号計算部と、
Ｍａｃｖ（ｍ）とｃ１とが等しいことを検証する検証部と、
前記検証部の検証が成功した場合には平文ｍを出力し、前記検証部の検証が失敗した場合にはエラーを出力する復号出力部と
を備える復号装置。
【請求項９】
ｐ１，ｐ２は素数、ｎ＝ｐ１・ｐ２、Ｚｐ１は０からｐ１−１までの整数の集合、Ｚｐ２は０からｐ２−１までの整数の集合、Ｚｐ１−１は０からｐ１−２までの整数の集合、Ｚｐ２−１は０からｐ２−２  までの整数の集合、Ｚｎは０からｎ−１までの整数の集合、α１はＺｐ１の生成元、α２はＺｐ２の生成元、ＨはＺｎ２の元をＺｎの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｚｎ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を意味する式、φはオイラー関数、ｍは平文として、
（ａ）ｇｃｄ（ｐ１−１，ｐ２−１）がａ１−ａ２の約数となるように、集合Ｚｐ１−１からａ１を集合Ｚｐ２−１からａ２をそれぞれ選択し、
（ｂ）ｔ＝（ｐ１−１）（ｐ２−１）／ｇｃｄ（ｐ１−１，ｐ２−１）とし、
（ｃ）
【数１４】
0005448801.tif 000015
を満たすａ  ｍｏｄ  ｔを計算し、
（ｄ）
【数１５】
0005448801.tif 000016
を満たすα  ｍｏｄ  ｎを計算し、
（ｅ）
【数１６】
0005448801.tif 000017
を満たすβ  ｍｏｄ  ｎを計算し、
（ｆ）ｇｃｄ（ｅ，φ（ｎ））＝１を満たすようにｅを選び、
（ｇ）
【数１７】
0005448801.tif 000018
を満たすｄを求め、
（ｈ）ｆ（ｘ）＝ｘ＾ｅ  ｍｏｄ  ｎ、ｆ−１（ｙ）＝ｙ＾ｄ  ｍｏｄ  ｎを満たす一方向性置換（ｆ，ｆ−１）を選択し、
（ｉ）ｐ１，ｐ２，ａ，ｆ−１を秘密鍵とし、ｎ，α，β，ｆを整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’からなる公開鍵として公開する鍵生成部と、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力部と、
ｖ＝ｆ−１（ｃ３）
ｍｋ＝ｖ  ｍｏｄ  ｎ
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ａ＾（−１）），ｔａｇ））＾（−１）  ｍｏｄ  ｎ
を計算する復号計算部と、
Ｍａｃｍｋ（ｍ）とｃ１とが等しいことを検証する検証部と、
前記検証部の検証が成功した場合には平文ｍを出力し、前記検証部の検証が失敗した場合にはエラーを出力する復号出力部と
を備える復号装置。
【請求項１０】
公開鍵方式の暗号化装置と復号装置を用いた暗号化方法であって、
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、Ｈ１はＧ２の元をＧの元に変換するハッシュ関数、Ｈ２はＧ３の元をＺｐの元に変換するハッシュ関数、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
前記復号装置が、
集合Ｚｐの元である６つの乱数ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚを生成して秘密鍵とし、ｇ，ｇ＾ｗ，ｇ＾ｘ１・ｇ＾（ｗｘ２），ｇ＾ｙ１・ｇ＾（ｗｙ２），ｇ＾ｚを群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５からなる公開鍵として公開する鍵生成ステップと、
前記暗号化装置が、
平文ｍと、公開鍵として群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５を受け取る暗号化入力ステップと、
集合Ｚｐの元である乱数ｒを生成する乱数生成ステップと、
ｕ１＝ｐｋ１＾ｒ
ｕ２＝ｐｋ２＾ｒ
ｓ＝ｍ・（ｐｋ５）＾ｒ・Ｈ１（ｕ１，ｕ２）
α＝Ｈ２（ｕ１，ｕ２，ｓ）
ｖ＝ｐｋ３＾ｒ・ｐｋ４＾（ｒα）
を計算する暗号化計算ステップと、
ｕ１，ｓ，ｖをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力ステップと、
前記復号装置が、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力ステップと、
α’＝Ｈ２（ｃ１，ｃ１＾ｗ，ｃ２）
ｍ＝ｓ・ｕ１＾（−ｚ）・Ｈ１（ｕ１，ｕ１＾ｗ）＾（−１）
を計算する復号計算ステップと、
ｃ１＾（ｘ１＋ｙ１α’）・ｃ１＾（ｗ（ｘ２＋ｙ２α’））とｃ３とが等しいことを検証する検証ステップと、
前記検証ステップの検証が成功した場合には平文ｍを出力し、前記検証ステップの検証が失敗した場合にはエラーを出力する復号出力ステップと
を有する暗号化方法。
【請求項１１】
公開鍵方式の暗号化装置と復号装置を用いた暗号化方法であって、
ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、ＨはＧ２の元をＧの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｇ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｍは平文として、
前記復号装置が、
集合Ｚｐの元である乱数ｘを生成し、群Ｇを定義域として落し戸付き一方向性置換（ｆ，ｆ−１）を選択し、ｘ，ｆ−１を秘密鍵とし、ｇ＾ｘ，ｆを群Ｇの元ｐｋと関数ｆ’からなる公開鍵として公開する鍵生成ステップと、
前記暗号化装置が、
平文ｍと、公開鍵として群Ｇの元ｐｋと関数ｆ’を受け取る暗号化入力ステップと、
集合Ｚｐの元である乱数ｒを生成する乱数生成ステップと、
ｔａｇ＝Ｍａｃｐｋ＾ｒ（ｍ）
ｓ＝ｍ・Ｈ（ｇ＾ｒ，ｔａｇ）・ｐｋ＾ｒ
ｔ＝ｆ’（ｐｋ＾ｒ）
を計算する暗号化計算ステップと、
ｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力ステップと、
前記復号装置が、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力ステップと、
ｖ＝ｆ−１（ｃ３）
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ｘ＾（−１）），ｔａｇ））＾（−１）
を計算する復号計算ステップと、
Ｍａｃｖ（ｍ）とｃ１とが等しいことを検証する検証ステップと、
前記検証ステップの検証が成功した場合には平文ｍを出力し、前記検証ステップの検証が失敗した場合にはエラーを出力する復号出力ステップと
を有する暗号化方法。
【請求項１２】
公開鍵方式の暗号化装置と復号装置を用いた暗号化方法であって、
ｐ１，ｐ２は素数、ｎ＝ｐ１・ｐ２、Ｚｐ１は０からｐ１−１までの整数の集合、Ｚｐ２は０からｐ２−１までの整数の集合、Ｚｐ１−１は０からｐ１−２までの整数の集合、Ｚｐ２−１は０からｐ２−２までの整数の集合、Ｚｎは０からｎ−１までの整数の集合、α１はＺｐ１の生成元、α２はＺｐ２の生成元、ＨはＺｎ２の元をＺｎの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｚｎ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を意味する式、φはオイラー関数、ｍは平文として、
前記復号装置が、
（ａ）ｇｃｄ（ｐ１−１，ｐ２−１）がａ１−ａ２の約数となるように、集合Ｚｐ１−１からａ１を集合Ｚｐ２−１からａ２をそれぞれ選択し、
（ｂ）ｔ＝（ｐ１−１）（ｐ２−１）／ｇｃｄ（ｐ１−１，ｐ２−１）とし、
（ｃ）
【数１８】
0005448801.tif 000019
を満たすａ  ｍｏｄ  ｔを計算し、
（ｄ）
【数１９】
0005448801.tif 000020
を満たすα  ｍｏｄ  ｎを計算し、
（ｅ）
【数２０】
0005448801.tif 000021
を満たすβ  ｍｏｄ  ｎを計算し、
（ｆ）ｇｃｄ（ｅ，φ（ｎ））＝１を満たすようにｅを選び、
（ｇ）
【数２１】
0005448801.tif 000022
を満たすｄを求め、
（ｈ）ｆ（ｘ）＝ｘ＾ｅ  ｍｏｄ  ｎ、ｆ−１（ｙ）＝ｙ＾ｄ  ｍｏｄ  ｎを満たす一方向性置換（ｆ，ｆ−１）を選択し、
（ｉ）ｐ１，ｐ２，ａ，ｆ−１を秘密鍵とし、ｎ，α，β，ｆを整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’からなる公開鍵として公開する鍵生成ステップと、
前記暗号化装置が、
平文ｍと、公開鍵として整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’を受け取る暗号化入力ステップと、
集合Ｚｐの元である乱数ｒを生成する乱数生成ステップと、
ｍｋ＝ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔａｇ＝Ｍａｃｍｋ（ｍ）
ｓ＝ｍ・Ｈ（ｐｋ２＾ｒ，ｔａｇ）・ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔ＝ｆ’（ｐｋ３＾ｒ）
を計算する暗号化計算ステップと、
ｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する暗号文出力ステップと、
前記復号装置が、
暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する復号入力ステップと、
ｖ＝ｆ−１（ｃ３）
ｍｋ＝ｖ  ｍｏｄ  ｎ
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ａ＾（−１）），ｔａｇ））＾（−１）  ｍｏｄ  ｎ
を計算する復号計算ステップと、
Ｍａｃｍｋ（ｍ）とｃ１とが等しいことを検証する検証ステップと、
前記検証ステップの検証が成功した場合には平文ｍを出力し、前記検証ステップの検証が失敗した場合にはエラーを出力する復号出力ステップと
を有する暗号化方法。
【請求項１３】
請求項４から６のいずれかに記載の暗号化装置、もしくは請求項７から９のいずれかに記載の復号装置としてコンピュータを動作させるためのプログラム。
【請求項１４】
請求項１３記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術の応用技術に関するものであり、平文の暗号化を公開鍵で行い、復号を秘密鍵で行う公開鍵暗号方式に関するものである。
【背景技術】
【０００２】
公開鍵暗号方式の従来技術には、非特許文献１のようなＲＳＡ−ＫＥＭを秘密鍵暗号と組み合わせて行う方法があった。この方法を実行する暗号化システムの機能構成例を図１、この方法の処理フローを図２に示す。暗号化システムは、暗号化装置７００、復号装置８００、ネットワーク９００を備えている。暗号化装置７００は、平文ｍと公開鍵を受け取る暗号化入力部７１０、乱数ｒを生成する乱数生成部７２０、暗号化計算部７３０、暗号文Ｃを出力する暗号文出力部７４０、暗号化記録部７９０を備える。復号装置８００は、秘密鍵と公開鍵とを求め公開鍵を公開する鍵生成部８１０、暗号文を受信する復号入力部８２０、復号計算部８３０、平文ｍを出力する復号出力部８５０、復号記録部８９０を備える。
【０００３】
次に、図２を参照しながら処理フローと各構成部の処理内容について説明する。この説明では、ｐ，ｑは素数、ｎとｋは整数、Ｚｎは０からｎ−１までの整数の集合、ＨはＺｎの元をｋ個の０，１で２進数表現される整数に変換するハッシュ関数、ＥＫは鍵Ｋを用いた秘密鍵暗号アルゴリズム、ＤＫは鍵Ｋを用いた復号アルゴリズム、ａ＾ｂはａのｂ乗を意味する式、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を意味する式、φはオイラー関数、ｍは平文、Ｋはセッション鍵とする。復号装置８００の鍵生成部８１０は、大きな素数ｐ、ｑを選択し、ｎ＝ｐｑとする。ｇｃｄ（ｅ，φ（ｎ））＝１を満たすようにｅを選び、
【０００４】
【数１】
0005448801.tif 000002
【０００５】
を満たすｄを求め、ｄを秘密鍵とし、ｎ，ｅを整数ｐｋ１，ｐｋ２からなる公開鍵として公開する（Ｓ８１０）。また、秘密鍵ｄ、公開鍵ｎ，ｅを復号記録部８９０に記録する。
【０００６】
暗号化装置７００の暗号化入力部７１０は、平文ｍと、公開鍵として整数ｐｋ１，ｐｋ２を受け取る（Ｓ７１０）。乱数生成部７２０は、集合Ｚｎの元である乱数ｒを生成する（Ｓ７２０）。暗号化計算部７３０は、
ｃ１＝ｒ＾ｐｋ２  ｍｏｄ  ｐｋ１
Ｋ＝Ｈ（ｒ）
ｃ２＝ＥＫ（ｍ）
を計算する（Ｓ７３０）。暗号文出力部７４０は、ｃ１，ｃ２からなる暗号文Ｃを出力する（Ｓ７４０）。
【０００７】
復号装置８００の復号入力部８２０は、暗号文Ｃとしてｃ１，ｃ２を受信する（Ｓ８２０）。復号計算部８３０は、
ｒ＝ｃ１＾ｄ  ｍｏｄ  ｎ
Ｋ＝Ｈ（ｒ）
ｍ＝ＤＫ（ｃ２）
を計算する（Ｓ８３０）。復号出力部８５０は、平文ｍを出力する（Ｓ８５０）。
【０００８】
ＲＳＡ−ＫＥＭと秘密鍵暗号を組み合わせる方法は、公開鍵暗号の最強の安全性（選択暗号文攻撃安全）を満たしていることが知られている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Victor Shoup, “A Proposal for an ISO Standard for Public Key Encryption (version 2.1)”, December 20, 2001,［平成２１年１２月２１日検索］、インターネット<URL: http://www.shoup.net/papers/iso-2_1.pdf>.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来のＲＳＡ−ＫＥＭと秘密鍵暗号を組み合わせる方法は、暗号化実行時のハッシュ関数への入出力情報が漏洩すると最低限の安全性（一方向安全）すら満たさないという問題があった。
【００１１】
例えば、攻撃者は次のように一方向攻撃を行うことができる。
（１）攻撃者は、暗号文Ｃ＝（ｃ１，ｃ２）と暗号化実行時に用いられたハッシュ値Ｈ（ｒ）をハッシュ関数への入出力情報から得る。
（２）攻撃者は、Ｋ＝Ｈ（ｒ）を用いて平文ｍをｍ＝ＤＫ（ｃ２）のように計算する。
このように、攻撃者は秘密鍵ｄを知らなくても平文ｍを求めることができる。
【００１２】
本発明は、ハッシュ関数の入出力情報が漏洩したとしても選択暗号文攻撃安全を満たす暗号化方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の暗号化システムは、暗号化装置と復号装置を備える。暗号化装置は、暗号化入力部、乱数生成部、暗号化計算部、暗号文出力部を備える。復号装置は、鍵生成部、復号入力部、復号計算部、検証部、復号出力部を備える。
【００１４】
本発明の第１の暗号化システムでは、ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、Ｈ１はＧ２の元をＧの元に変換するハッシュ関数、Ｈ２はＧ３の元をＺｐの元に変換するハッシュ関数、ａ＾ｂはａのｂ乗を意味する式、ｍは平文とする。そして、暗号化入力部は、平文ｍと、公開鍵として群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５を受け取る。乱数生成部は、集合Ｚｐの元である乱数ｒを生成する。暗号化計算部は、
ｕ１＝ｐｋ１＾ｒ
ｕ２＝ｐｋ２＾ｒ
ｓ＝ｍ・（ｐｋ５）＾ｒ・Ｈ１（ｕ１，ｕ２）
α＝Ｈ２（ｕ１，ｕ２，ｓ）、
ｖ＝ｐｋ３＾ｒ・ｐｋ４＾（ｒα）
を計算する。暗号文出力部は、ｕ１，ｓ，ｖをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する。鍵生成部は、集合Ｚｐの元である６つの乱数ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚを生成して秘密鍵とし、ｇ，ｇ＾ｗ，ｇ＾ｘ１・ｇ＾（ｗｘ２），ｇ＾ｙ１・ｇ＾（ｗｙ２），ｇ＾ｚを群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５からなる公開鍵として公開する。復号入力部は、暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する。復号計算部は、
α’＝Ｈ２（ｃ１，ｃ１＾ｗ，ｃ２）
ｍ＝ｓ・ｕ１＾（−ｚ）・Ｈ１（ｕ１，ｕ１＾ｗ）＾（−１）
を計算する。検証部は、ｃ１＾（ｘ１＋ｙ１α’）・ｃ１＾（ｗ（ｘ２＋ｙ２α’））とｃ３とが等しいことを検証する。復号出力部は、検証部の検証が成功した場合には平文ｍを出力し、検証部の検証が失敗した場合にはエラーを出力する。
【００１５】
本発明の第２の暗号化システムでは、ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、ＨはＧ２の元をＧの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｇ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｍは平文とする。そして、暗号化入力部は、平文ｍと、公開鍵として群Ｇの元ｐｋと関数ｆ’を受け取る。乱数生成部は、集合Ｚｐの元である乱数ｒを生成する。暗号化計算部は、
ｔａｇ＝Ｍａｃｐｋ＾ｒ（ｍ）
ｓ＝ｍ・Ｈ（ｇ＾ｒ，ｔａｇ）・ｐｋ＾ｒ
ｔ＝ｆ’（ｐｋ＾ｒ）
を計算する。暗号文出力部はｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する。鍵生成部は、集合Ｚｐの元である乱数ｘを生成し、群Ｇを定義域として落し戸付き一方向性置換（ｆ，ｆ−１）を選択し、ｘ，ｆ−１を秘密鍵とし、ｇ＾ｘ，ｆを群Ｇの元ｐｋと関数ｆ’からなる公開鍵として公開する。復号入力部は、暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する。復号計算部は、
ｖ＝ｆ−１（ｃ３）
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ｘ＾（−１）），ｔａｇ））＾（−１）
を計算する。検証部は、Ｍａｃｖ（ｍ）とｃ１とが等しいことを検証する。復号出力部は検証部の検証が成功した場合には平文ｍを出力し、検証部の検証が失敗した場合にはエラーを出力する。
【００１６】
本発明の第３の暗号化システムでは、ｐ１，ｐ２は素数、ｎ＝ｐ１・ｐ２、Ｚｐ１は０からｐ１−１までの整数の集合、Ｚｐ２は０からｐ２−１までの整数の集合、Ｚｐ１−１は０からｐ１−２までの整数の集合、Ｚｐ２−１は０からｐ２−２までの整数の集合、Ｚｎは０からｎ−１までの整数の集合、α１はＺｐ１の生成元、α２はＺｐ２の生成元、ＨはＺｎ２の元をＺｎの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｚｎ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を意味する式、φはオイラー関数、ｍは平文とする。そして、暗号化入力部は、平文ｍと、公開鍵として整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’を受け取る。乱数生成部は、集合Ｚｐの元である乱数ｒを生成する。暗号化計算部は、
ｍｋ＝ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔａｇ＝Ｍａｃｍｋ（ｍ）
ｓ＝ｍ・Ｈ（ｐｋ２＾ｒ，ｔａｇ）・ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔ＝ｆ’（ｐｋ３＾ｒ）
を計算する。暗号文出力部はｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する。鍵生成部は、
【００１７】
（ａ）ｇｃｄ（ｐ１−１，ｐ２−１）がａ１−ａ２の約数となるように、集合Ｚｐ１−１からａ１を集合Ｚｐ２−１からａ２をそれぞれ選択し、
【００１８】
（ｂ）ｔ＝（ｐ１−１）（ｐ２−１）／ｇｃｄ（ｐ１−１，ｐ２−１）とし、
【００１９】
（ｃ）
【数２】
0005448801.tif 000003
を満たすａ  ｍｏｄ  ｔを計算し、
【００２０】
（ｄ）
【数３】
0005448801.tif 000004
を満たすα  ｍｏｄ  ｎを計算し、
【００２１】
（ｅ）
【数４】
0005448801.tif 000005
を満たすβ  ｍｏｄ  ｎを計算し、
【００２２】
（ｆ）ｇｃｄ（ｅ，φ（ｎ））＝１を満たすようにｅを選び、
【００２３】
（ｇ）
【数５】
0005448801.tif 000006
を満たすｄを求め、
【００２４】
（ｈ）ｆ（ｘ）＝ｘ＾ｅ  ｍｏｄ  ｎ、ｆ−１（ｙ）＝ｙ＾ｄ  ｍｏｄ  ｎを満たす一方向性置換（ｆ，ｆ−１）を選択し、
【００２５】
（ｉ）ｐ１，ｐ２，ａ，ｆ−１を秘密鍵とし、ｎ，α，β，ｆを整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’からなる公開鍵として公開する。復号入力部は、暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信する。復号計算部は、
ｖ＝ｆ−１（ｃ３）
ｍｋ＝ｖ  ｍｏｄ  ｎ
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ａ＾（−１）），ｔａｇ））＾（−１）  ｍｏｄ  ｎ
を計算する。検証部は、Ｍａｃｍｋ（ｍ）とｃ１とが等しいことを検証する。復号出力部は、検証部の検証が成功した場合には平文ｍを出力し、検証部の検証が失敗した場合にはエラーを出力する。
【００２６】
上述の本発明の暗号化システムによれば、ハッシュ関数の入出力に直接平文を導出できる情報がない。また、ハッシュ関数の入出力情報だけから、攻撃者が秘密鍵なしで復号手続を行えない。
【発明の効果】
【００２７】
ハッシュ関数の入出力情報を攻撃者が入手できた場合、生成元を乱数乗した要素を知ることはできる。しかし、本発明の暗号化システムでは、暗号文から平文の情報を得るためには乱数自体を知る必要がある。したがって、ハッシュ関数の入出力情報を入手しただけでは、暗号文から平文の情報（平文全体、または平文の一部など）を得ることはできない。本発明の暗号化システムでは、このように、ハッシュ関数の入出力情報の中身を攻撃者にすべて開示したとしても選択暗号文攻撃安全を満たすことができる。
【図面の簡単な説明】
【００２８】
【図１】従来の暗号化システムの機能構成例を示す図。
【図２】従来の暗号化システムの処理フローを示す図。
【図３】実施例１の暗号化システムの機能構成例を示す図。
【図４】実施例１の暗号化システムの処理フローを示す図。
【図５】実施例２の暗号化システムの機能構成例を示す図。
【図６】実施例２の暗号化システムの処理フローを示す図。
【図７】実施例３の暗号化システムの機能構成例を示す図。
【図８】実施例３の暗号化システムの処理フローを示す図。
【発明を実施するための形態】
【００２９】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３０】
図３に実施例１の暗号化システムの構成例を、図４に実施例１の暗号化システムの処理フローを示す。暗号化システムは、暗号化装置１００、復号装置２００、ネットワーク９００を備えている。暗号化装置１００は、平文ｍと公開鍵を受け取る暗号化入力部１１０、乱数ｒを生成する乱数生成部１２０、暗号化計算部１３０、暗号文Ｃを出力する暗号文出力部１４０、暗号化記録部１９０を備える。復号装置２００は、秘密鍵と公開鍵とを求め公開鍵を公開する鍵生成部２１０、暗号文を受信する復号入力部２２０、復号計算部２３０、検証部２４０、平文ｍを出力する復号出力部２５０、復号記録部２９０を備える。
【００３１】
次に、図４を参照しながら処理フローと各構成部の処理内容について説明する。本実施例では、ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、Ｈ１はＧ２の元をＧの元に変換するハッシュ関数、Ｈ２はＧ３の元をＺｐの元に変換するハッシュ関数、ａ＾ｂはａのｂ乗を意味する式、ｍは平文とする。
【００３２】
復号装置２００の鍵生成部２１０は、集合Ｚｐの元である６つの乱数ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚを生成して秘密鍵とし、ｇ，ｇ＾ｗ，ｇ＾ｘ１・ｇ＾（ｗｘ２），ｇ＾ｙ１・ｇ＾（ｗｙ２），ｇ＾ｚを群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５からなる公開鍵として公開する（Ｓ２１０）。復号記録部２９０は、秘密鍵ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚと公開鍵ｇ（＝ｐｋ１），ｇ＾ｗ（＝ｐｋ２），ｇ＾ｘ１・ｇ＾（ｗｘ２）（＝ｐｋ３），ｇ＾ｙ１・ｇ＾（ｗｙ２）（＝ｐｋ４），ｇ＾ｚ（＝ｐｋ５）を記録する。
【００３３】
暗号化装置１００の暗号化入力部１１０は、平文ｍと、公開鍵として群Ｇの５つの元ｐｋ１，ｐｋ２，ｐｋ３，ｐｋ４，ｐｋ５を受け取り、暗号化記録部１９０に記録する（Ｓ１１０）。乱数生成部１２０は、集合Ｚｐの元である乱数ｒを生成する（Ｓ１２０）。暗号化計算部１３０は、
ｕ１＝ｐｋ１＾ｒ
ｕ２＝ｐｋ２＾ｒ
ｓ＝ｍ・（ｐｋ５）＾ｒ・Ｈ１（ｕ１，ｕ２）
α＝Ｈ２（ｕ１，ｕ２，ｓ）、
ｖ＝ｐｋ３＾ｒ・ｐｋ４＾（ｒα）
を計算する（Ｓ１３０）。ここで、ｐｋ１＝ｇ，ｐｋ２＝ｇ＾ｗ，ｐｋ３＝ｇ＾ｘ１・ｇ＾（ｗｘ２），ｐｋ４＝ｇ＾ｙ１・ｇ＾（ｗｙ２），ｐｋ５＝ｇ＾ｚであるから、これらの式は、
ｕ１＝ｇ＾ｒ
ｕ２＝（ｇ＾ｗ）＾ｒ
ｓ＝ｍ・（ｇ＾ｚ）＾ｒ・Ｈ１（ｕ１，ｕ２）
α＝Ｈ２（ｕ１，ｕ２，ｓ）
ｖ＝（ｇ＾ｘ１・ｇ＾（ｗｘ２））＾ｒ・（ｇ＾ｙ１・ｇ＾（ｗｙ２））＾（ｒα）
を計算していることと同じである。暗号文出力部１４０は、ｕ１，ｓ，ｖをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する（Ｓ１４０）。復号装置２００の復号入力部２２０は、暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信し、復号記録部２９０に記録する（Ｓ２２０）。
【００３４】
復号計算部２３０は、
α’＝Ｈ２（ｃ１，ｃ１＾ｗ，ｃ２）
ｍ＝ｓ・ｕ１＾（−ｚ）・Ｈ１（ｕ１，ｕ１＾ｗ）＾（−１）
を計算する（Ｓ２３０）。
【００３５】
検証部２４０は、ｃ１＾（ｘ１＋ｙ１α’）・ｃ１＾（ｗ（ｘ２＋ｙ２α’））とｃ３とが等しいことを検証する（Ｓ２４０）。ここで、暗号文Ｃが正しい暗号文であれば、ｃ１＝ｕ１，ｃ２＝ｓ，ｃ３＝ｖ、ｕ１＝ｇ＾ｒ、ｕ２＝（ｇ＾ｗ）＾ｒだから、
α’＝Ｈ２（ｕ１，ｕ１＾ｗ，ｓ）
＝Ｈ２（ｕ１，（ｇ＾ｒ）＾ｗ，ｓ）
＝Ｈ２（ｕ１，（ｇ＾ｗ）＾ｒ，ｓ）
＝Ｈ２（ｕ１，ｕ２，ｓ）
＝α
となり、
ｃ１＾（ｘ１＋ｙ１α’）・ｃ１＾（ｗ（ｘ２＋ｙ２α’））
＝ｕ１＾（ｘ１＋ｙ１α）・ｕ１＾（ｗ（ｘ２＋ｙ２α））
＝ｇ＾（ｒｘ１＋ｒｙ１α）・ｇ＾（ｒｗ（ｘ２＋ｙ２α））
＝（ｇ＾ｘ１・ｇ＾（ｗｘ２））＾ｒ・（ｇ＾ｙ１・ｇ＾（ｗｙ２））＾（ｒα）
＝ｖ  （＝ｃ３）
となる。つまり、暗号文Ｃが正しければ、検証は成功する。復号出力部２５０は、検証部２４０の検証が成功した場合には平文ｍを出力し、検証部２４０の検証が失敗した場合にはエラーを出力する（Ｓ２５０）。
【００３６】
実施例１の暗号化システムによれば、ハッシュ関数の入力（ｕ１＝ｐｋ１＾ｒ＝ｇ＾ｒ，ｕ２＝ｐｋ２＾ｒ＝（ｇ＾ｗ）＾ｒ，ｓ＝ｍ・（ｇ＾ｚ）＾ｒ・Ｈ１（ｕ１，ｕ２））と出力（Ｈ１（ｕ１，ｕ２），Ｈ２（ｕ１，ｕ２，ｓ））に直接平文を導出できる情報がない。また、ハッシュ関数の入出力情報だけから、攻撃者が秘密鍵なしで復号手続を行えない。したがって、本実施例の暗号化システムでは、ハッシュ関数の入出力情報から生成元を乱数乗した要素を知ることはできるが、暗号文から平文の情報を得るためにはそれだけでは計算できない。つまり、暗号文から平文の情報を得るためには乱数自体を知る必要がある。これにより、ハッシュ関数の入出力情報の中身を攻撃者にすべて開示したとしても選択暗号文攻撃安全を満たすことができる。
【実施例２】
【００３７】
図５に実施例２の暗号化システムの構成例を、図６に実施例２の暗号化システムの処理フローを示す。暗号化システムは、暗号化装置３００、復号装置４００、ネットワーク９００を備えている。暗号化装置３００は、平文ｍと公開鍵を受け取る暗号化入力部３１０、乱数ｒを生成する乱数生成部１２０、暗号化計算部３３０、暗号文Ｃを出力する暗号文出力部３４０、暗号化記録部３９０を備える。復号装置４００は、秘密鍵と公開鍵とを求め公開鍵を公開する鍵生成部４１０、暗号文を受信する復号入力部２２０、復号計算部４３０、検証部４４０、平文ｍを出力する復号出力部４５０、復号記録部４９０を備える。
【００３８】
次に、図６を参照しながら処理フローと各構成部の処理内容について説明する。本実施例では、ｐは素数、Ｚｐは０からｐ−１までの整数の集合、Ｇは位数ｐの有限巡回群、ｇは群Ｇの生成元、ＨはＧ２の元をＧの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｇ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｍは平文とする。
【００３９】
復号装置４００の鍵生成部４１０は、集合Ｚｐの元である乱数ｘを生成し、群Ｇを定義域として落し戸付き一方向性置換（ｆ，ｆ−１）を選択し、ｘ，ｆ−１を秘密鍵とし、ｇ＾ｘ，ｆを群Ｇの元ｐｋと関数ｆ’からなる公開鍵として公開する（Ｓ４１０）。復号記録部４９０は、秘密鍵ｘ，ｆ−１と公開鍵ｇ＾ｘ（＝ｐｋ），ｆ（＝ｆ’）を記録する。
【００４０】
暗号化装置３００の暗号化入力部３１０は、平文ｍと、公開鍵として群Ｇの元ｐｋと関数ｆ’を受け取り、暗号化記録部３９０に記録する（Ｓ３１０）。乱数生成部１２０は、集合Ｚｐの元である乱数ｒを生成する（Ｓ１２０）。暗号化計算部３３０は、
ｔａｇ＝Ｍａｃｐｋ＾ｒ（ｍ）
ｓ＝ｍ・Ｈ（ｇ＾ｒ，ｔａｇ）・ｐｋ＾ｒ
ｔ＝ｆ’（ｐｋ＾ｒ）
を計算する（Ｓ３３０）。ここで、ｐｋ＝ｇ＾ｘ、ｆ’＝ｆであるから、これらの式は、
ｔａｇ＝Ｍａｃｇ＾（ｘｒ）（ｍ）
ｓ＝ｍ・Ｈ（ｇ＾ｒ，ｔａｇ）・ｇ＾（ｘｒ）
ｔ＝ｆ（ｇ＾（ｘｒ））
を計算していることと同じとなる。
【００４１】
暗号文出力部３４０はｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する（Ｓ３４０）。復号装置４００の復号入力部２２０は、暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信し、復号記録部４９０に記録する（Ｓ２２０）。復号計算部４３０は、
ｖ＝ｆ−１（ｃ３）
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ｘ＾（−１）），ｔａｇ））＾（−１）
を計算する（Ｓ４３０）。検証部４４０は、Ｍａｃｖ（ｍ）とｃ１とが等しいことを検証する（Ｓ４４０）。ここで、暗号文Ｃが正しい暗号文であれば、ｃ１＝ｔａｇ，ｃ２＝ｓ，ｃ３＝ｔだから、
ｖ＝ｆ−１（ｃ３）
＝ｆ−１（ｔ）
＝ｆ−１（ｆ（ｇ＾（ｘｒ）））
＝ｇ＾（ｘｒ）
となり、
Ｍａｃｖ（ｍ）
＝Ｍａｃｇ＾（ｘｒ）（ｍ）
＝ｔａｇ  （＝ｃ１）
となる。つまり、暗号文Ｃが正しければ、検証は成功する。
【００４２】
復号出力部４５０は検証部４４０の検証が成功した場合には平文ｍを出力し、検証部４４０の検証が失敗した場合にはエラーを出力する（Ｓ４５０）。
【００４３】
実施例２の暗号化システムによれば、実施例１と同じように、ハッシュ関数の入力（ｇ＾ｒ，ｔａｇ）と出力（Ｈ（ｇ＾ｒ，ｔａｇ））に直接平文を導出できる情報がない。また、ハッシュ関数の入出力情報だけから、攻撃者が秘密鍵なしで復号手続を行えない。したがって、本実施例の暗号化システムでも、ハッシュ関数の入出力情報から生成元を乱数乗した要素を知ることはできるが、暗号文から平文の情報を得るためにはそれだけでは計算できない。つまり、暗号文から平文の情報を得るためには乱数自体を知る必要がある。これにより、ハッシュ関数の入出力情報の中身を攻撃者にすべて開示したとしても選択暗号文攻撃安全を満たすことができる。
【実施例３】
【００４４】
図７に実施例３の暗号化システムの構成例を、図８に実施例３の暗号化システムの処理フローを示す。暗号化システムは、暗号化装置５００、復号装置６００、ネットワーク９００を備えている。暗号化装置５００は、平文ｍと公開鍵を受け取る暗号化入力部５１０、乱数ｒを生成する乱数生成部５２０、暗号化計算部５３０、暗号文Ｃを出力する暗号文出力部５４０、暗号化記録部５９０を備える。復号装置６００は、秘密鍵と公開鍵とを求め公開鍵を公開する鍵生成部６１０、暗号文を受信する復号入力部２２０、復号計算部６３０、検証部６４０、平文ｍを出力する復号出力部６５０、復号記録部６９０を備える。
【００４５】
次に、図８を参照しながら処理フローと各構成部の処理内容について説明する。本実施例では、ｐ１，ｐ２は素数、ｎ＝ｐ１・ｐ２、Ｚｐ１は０からｐ１−１までの整数の集合、Ｚｐ２は０からｐ２−１までの整数の集合、Ｚｐ１−１は０からｐ１−２までの整数の集合、Ｚｐ２−１は０からｐ２−２までの整数の集合、Ｚｎは０からｎ−１までの整数の集合、α１はＺｐ１の生成元、α２はＺｐ２の生成元、ＨはＺｎ２の元をＺｎの元に変換するハッシュ関数、ＭａｃｍｋをＭａｃ鍵ｍｋの鍵長が｜Ｚｎ｜である長さ保存メッセージ認証コード、ａ＾ｂはａのｂ乗を意味する式、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を意味する式、φはオイラー関数、ｍは平文とする。
【００４６】
復号装置６００の鍵生成部６１０は、
【００４７】
（ａ）ｇｃｄ（ｐ１−１，ｐ２−１）がａ１−ａ２の約数となるように、集合Ｚｐ１−１からａ１を集合Ｚｐ２−１からａ２をそれぞれ選択し、
【００４８】
（ｂ）ｔ＝（ｐ１−１）（ｐ２−１）／ｇｃｄ（ｐ１−１，ｐ２−１）とし、
【００４９】
（ｃ）
【数６】
0005448801.tif 000007
を満たすａ  ｍｏｄ  ｔを計算し、
【００５０】
（ｄ）
【数７】
0005448801.tif 000008
を満たすα  ｍｏｄ  ｎを計算し、
【００５１】
（ｅ）
【数８】
0005448801.tif 000009
を満たすβ  ｍｏｄ  ｎを計算し、
【００５２】
（ｆ）ｇｃｄ（ｅ，φ（ｎ））＝１を満たすようにｅを選び、
【００５３】
（ｇ）
【数９】
0005448801.tif 000010
を満たすｄを求め、
【００５４】
（ｈ）ｆ（ｘ）＝ｘ＾ｅ  ｍｏｄ  ｎ、ｆ−１（ｙ）＝ｙ＾ｄ  ｍｏｄ  ｎを満たす一方向性置換（ｆ，ｆ−１）を選択し、
【００５５】
（ｉ）ｐ１，ｐ２，ａ，ｆ−１を秘密鍵とし、ｎ，α，β，ｆを整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’からなる公開鍵として公開する（Ｓ６１０）。復号記録部６９０は、秘密鍵ｐ１，ｐ２，ａ，ｆ−１と公開鍵ｎ（＝ｐｋ１），α（＝ｐｋ２），β（＝ｐｋ３），ｆ（＝ｆ’）を記録する。
【００５６】
暗号化装置５００の暗号化入力部５１０は、平文ｍと、公開鍵として整数ｐｋ１，ｐｋ２，ｐｋ３と関数ｆ’を受け取り、暗号化記録部５９０に記録する（Ｓ５１０）。乱数生成部５２０は、集合Ｚｐの元である乱数ｒを生成する（Ｓ５２０）。暗号化計算部５３０は、
ｍｋ＝ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔａｇ＝Ｍａｃｍｋ（ｍ）
ｓ＝ｍ・Ｈ（ｐｋ２＾ｒ，ｔａｇ）・ｐｋ３＾ｒ  ｍｏｄ  ｐｋ１
ｔ＝ｆ’（ｐｋ３＾ｒ）
を計算する（Ｓ５３０）。ここで、ｐｋ１＝ｎ，ｐｋ２＝α，ｐｋ３＝β、ｆ’＝ｆであるから、これらの式は、
ｍｋ＝β＾ｒ  ｍｏｄ  ｎ
ｔａｇ＝Ｍａｃｍｋ（ｍ）
ｓ＝ｍ・Ｈ（α＾ｒ，ｔａｇ）・β＾ｒ  ｍｏｄ  ｎ
ｔ＝ｆ（β＾ｒ）
を計算していることと同じとなる。
【００５７】
暗号文出力部５４０はｔａｇ，ｓ，ｔをｃ１，ｃ２，ｃ３からなる暗号文Ｃとして出力する（Ｓ５４０）。復号装置６００の復号入力部２２０は、暗号文Ｃとしてｃ１，ｃ２，ｃ３を受信し、復号記録部６９０に記録する（Ｓ２２０）。復号計算部６３０は、
ｖ＝ｆ−１（ｃ３）
ｍｋ＝ｖ  ｍｏｄ  ｎ
ｍ＝ｃ２・（ｖ・Ｈ（ｖ＾（ａ＾（−１）），ｔａｇ））＾（−１）  ｍｏｄ  ｎ
を計算する（Ｓ６３０）。検証部６４０は、Ｍａｃｍｋ（ｍ）とｃ１とが等しいことを検証する（Ｓ６４０）。ここで、暗号文Ｃが正しい暗号文であれば、ｃ１＝ｔａｇ，ｃ２＝ｓ，ｃ３＝ｔだから、
ｖ＝ｆ−１（ｃ３）
＝ｆ−１（ｔ）
＝ｆ−１（ｆ（β＾ｒ））
＝β＾ｒ
となり、
Ｍａｃｍｋ（ｍ）
＝Ｍａｃｖ（ｍ）
＝Ｍａｃβ＾ｒ（ｍ）
＝ｔａｇ  （＝ｃ１）
となる。つまり、暗号文Ｃが正しければ、検証は成功する。復号出力部６５０は、検証部の検証が成功した場合には平文ｍを出力し、検証部の検証が失敗した場合にはエラーを出力する（Ｓ６５０）。
【００５８】
実施例３の暗号化システムによれば、実施例１や実施例２同じように、ハッシュ関数の入力（ｐｋ２＾ｒ＝α＾ｒ，ｔａｇ）と出力（Ｈ（ｐｋ２＾ｒ，ｔａｇ）＝Ｈ（α＾ｒ，ｔａｇ））に直接平文を導出できる情報がない。また、ハッシュ関数の入出力情報だけから、攻撃者が秘密鍵なしで復号手続を行えない。したがって、本実施例の暗号化システムでも、ハッシュ関数の入出力情報から生成元を乱数乗した要素を知ることはできるが、暗号文から平文の情報を得るためにはそれだけでは計算できない。つまり、暗号文から平文の情報を得るためには乱数自体を知る必要がある。これにより、ハッシュ関数の入出力情報の中身を攻撃者にすべて開示したとしても選択暗号文攻撃安全を満たすことができる。
【００５９】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００６４】
本発明は、公開鍵暗号方式に利用することができる。
【符号の説明】
【００６５】
１００、３００、５００、７００  暗号化装置
１１０、３１０、５１０、７１０  暗号化入力部
１２０、５２０、７２０  乱数生成部
１３０、３３０、５３０、７３０  暗号化計算部
１４０、３４０、５４０、７４０  暗号文出力部
１９０、３９０、５９０、７９０  暗号化記録部
２００、４００、６００、８００  復号装置
２１０、４１０、６１０、８１０  鍵生成部
２２０、８２０  復号入力部
２３０、４３０、６３０、８３０  復号計算部
２４０、４４０、６４０  検証部
２５０、４５０、６５０、８５０  復号出力部
２９０、４９０、６９０、８９０  復号記録部
９００  ネットワーク
【図１】
0005448801.tif 000023
【図２】
0005448801.tif 000024
【図３】
0005448801.tif 000025
【図４】
0005448801.tif 000026
【図５】
0005448801.tif 000027
【図６】
0005448801.tif 000028
【図７】
0005448801.tif 000029
【図８】
0005448801.tif 000030