(57)【特許請求の範囲】
【請求項１】
第１非可換群（Ｇ）の生成元及び第１元（ｐ）を各々選択して、第１公開鍵（Ｉｎｎ（ｇ））として用いられる第１内部自己同型写像（Ｉｎｎ（ｇ））を計算し、第１整数である秘密鍵（ａ）及び前記第１公開鍵（Ｉｎｎ（ｇ））を用いて第２公開鍵（Ｉｎｎ（ｇａ））を生成するための公開鍵生成手段と、
平文を第２非可換群の生成元の積により表現し、任意の第２整数（ｂ）及び前記第１公開鍵（Ｉｎｎ（ｇ））を用いて第２内部自己同型写像（Ｉｎｎ（ｇｂ））を計算し、前記第２整数（ｂ）及び第２公開鍵（Ｉｎｎ（ｇａ））を用いて第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を計算し、前記第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を用いて暗号文を生成するための暗号化手段と、
前記秘密鍵（ａ）及び前記第２内部自己同型写像（Ｉｎｎ（ｇｂ））を用いて第４内部自己同型写像（Ｉｎｎ（ｇ−ａｂ））を生成し、前記第４内部自己同型写像（Ｉｎｎ（ｇ−ａｂ））を用いて前記暗号文（Ｅ）を復号化するための復号化手段と、
を備えていることを特徴とする有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項２】
ＳＬ（２、Ｚｐ）を非可換群、θをＺｐからＳＬ（２、Ｚｐ）の自己同型写像群への単射である準同型写像とすると、前記第１非可換群（Ｇ）は、下記数式
【数１】
0003955567.tif 000045
により表現されることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項３】
前記第２非可換群は、前記第１非可換群（Ｇ）と同一であるか、又は、前記第１非可換群（Ｇ）の部分集合であることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項４】
前記第１元（ｐ）は、前記第１非可換群（Ｇ）の中心の元でなく、位数が大きい素数であることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項５】
Ｔ、Ｓを第２非可換群ＳＬ（２、Ｚｐ）の生成元、ｇを第１元とすると、前記第１内部自己同型写像Ｉｎｎ（ｇ）は、下記数式
【数２】
0003955567.tif 000046
により計算されることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項６】
前記秘密鍵（ａ）は、前記元（ｐ）より小さい第１整数であることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項７】
前記第２整数（ｂ）は、高速の暗復号化が可能なように、前記暗号文（Ｅ）を生成する度に固定されることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項８】
Ｉｎｎ（ｇａｂ）を第３内部自己同型写像、ｍを第２元とすると、前記暗号文（Ｅ）は、下記数式
【数７】
0003955567.tif 000047
により計算されることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項９】
ｍを第２元、Ｉｎｎ（ｇ−ａｂ）を第４内部自己同型写像とすると、前記暗号文（Ｅ）は、下記数式
【数９】
0003955567.tif 000048
により復号化されることを特徴とする請求項１に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項１０】
非可換群（Ｇ）の生成元及び元（ｐ）を各々選択して、第１公開鍵（Ｉｎｎ（ｇ））として用いられる第１内部自己同型写像（Ｉｎｎ（ｇ））を計算し、整数である秘密鍵（ａ）及び前記第１公開鍵（Ｉｎｎ（ｇ））を用いて第２公開鍵（Ｉｎｎ（ｇａ））を生成するための公開鍵生成手段と、
前記第１公開鍵（Ｉｎｎ（ｇ））及び任意の乱数（ｂ）を用いて第２内部自己同型写像（Ｉｎｎ（ｇｂ））を計算し、前記第２内部自己同型写像（Ｉｎｎ（ｇｂ））を用いて対称鍵（Ｋ）を生成するための手段と、
前記対称鍵（Ｋ）を用いて付加文を含む平文を暗号化して暗号文（Ｅ）を生成するための暗号文生成手段と、
前記暗号文（Ｅ）を用いてハッシュ関数（ｈ（Ｅ））を計算し、前記秘密鍵（ａ）、前記乱数（ｂ）及び前記ハッシュ関数（ｈ（Ｅ））を用いて電子署名（ｓ）を生成するための電子署名生成手段と、
前記電子署名（ｓ）が所定の範囲に存在するか否かを確認し、前記ハッシュ関数（ｈ（Ｅ））を計算し、前記電子署名（ｓ）、前記整数（ａ）及び前記ハッシュ関数（ｈ（Ｅ））を用いて第３内部自己同型写像（Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ））を計算し、前記第３内部自己同型写像（Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ））を用いて前記対称鍵（Ｋ）を復旧するための対称鍵復旧手段と、
前記対称鍵（Ｋ）を用いて前記暗号文（Ｅ）を復号化して復号文を求め、前記復号文から前記付加文を確認して前記電子署名が正しい署名なのか否かを確認するための署名確認手段と、
を備えていることを特徴とする有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項１１】
ＳＬ（２、Ｚｐ）を非可換群、θをＺｐからＳＬ（２、Ｚｐ）の自己同型写像群への単射である準同型写像とすると、前記非可換群（Ｇ）は、下記数式
【数１０】
0003955567.tif 000049
により表現されることを特徴とする請求項１０に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項１２】
前記元（ｐ）は、前記非可換群の中心の元でなく、位数が大きい素数であることを特徴とする請求項１０に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項１３】
Ｔ、Ｓを非可換群ＳＬ（２、Ｚｐ）の生成元、ｇを元とすると、前記第１内部自己同型写像（Ｉｎｎ（ｇ））は、下記数式
【数１１】
0003955567.tif 000050
により計算されることを特徴とする請求項１０に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項１４】
ａを秘密鍵、ｈをハッシュ関数、ｂを乱数、ｐを素数とすると、前記電子署名（ｓ）は、下記数式
【数１３】
0003955567.tif 000051
により計算されることを特徴とする請求項１０に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項１５】
前記署名は、０≦ｓ＜ｐの範囲内に存在することを特徴とする請求項１０に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム。
【請求項１６】
非可換群（Ｇ）の生成元及び元（ｐ）を各々選択して、公開鍵（Ｉｎｎ（ｇ））として用いられる第１内部自己同型写像（Ｉｎｎ（ｇ））を計算するための公開鍵生成手段と、
第１ユーザによって選択された第１乱数（ａ）及び前記公開鍵（Ｉｎｎ（ｇ））を用いて第２内部自己同型写像（Ｉｎｎ（ｇａ））を計算し、前記第２内部自己同型写像（Ｉｎｎ（ｇａ））を第２ユーザに提供するための手段と、
前記第２ユーザによって選択された第２乱数（ｂ）及び前記第２内部自己同型写像（Ｉｎｎ（ｇａ））を用いて第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を計算し、前記第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を利用して対称鍵（Ｋ）を計算するための対称鍵計算手段と、
前記第２ユーザによって選択された前記第２乱数（ｂ）を用いて第４内部自己同型写像（Ｉｎｎ（ｇｂ））を計算して、前記第４内部自己同型写像（Ｉｎｎ（ｇｂ））を前記第１ユーザに提供するための手段と、
前記第２ユーザによって提供された前記第４内部自己同型写像（Ｉｎｎ（ｇｂ））及び前記第１乱数（ａ）を利用して前記第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を計算し、前記第３内部自己同型写像を利用して、前記対称鍵（Ｋ）を再計算するための対称鍵再計算手段と、
を備え、
前記再計算された対称鍵（Ｋ）は、前記第１ユーザに提供されることを特徴とする有限非可換群の自己同型写像を用いた離散対数問題に基づく対称鍵交換システム。
【請求項１７】
ＳＬ（２、Ｚｐ）を非可換群、θをＺｐからＳＬ（２、Ｚｐ）の自己同型写像群への単射である準同型写像とすると、前記非可換群（Ｇ）は、下記数式
【数１４】
0003955567.tif 000052
により表現されることを特徴とする請求項１６に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく対称鍵交換システム。
【請求項１８】
前記元（ｐ）は、前記非可換群の中心の元でなく、位数が大きい素数であることを特徴とする請求項１６に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく対称鍵交換システム。
【請求項１９】
Ｔ、Ｓを非可換群ＳＬ（２、Ｚｐ）の生成元、ｇを元とすると、前記第１内部自己同型写像（Ｉｎｎ（ｇ））は、下記数式
【数１５】
0003955567.tif 000053
により計算されることを特徴とする請求項１６に記載の有限非可換群の自己同型写像を用いた離散対数問題に基づく対称鍵交換システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限非可換群を用いた公開鍵暗号システムに関し、特に、有限非可換群を生成する方法、並びに、その非可換群を用いた有効な公開鍵暗号システムの実現及びその応用方法に関する。
【背景技術】
【０００２】
慣用（又は対称形）暗号システム（conventional or symmetric cryptosystem）は、秘密鍵を用いて文書を暗号化及び復号化させるシステムであって、ユーザが同じ秘密鍵（secret key）を各々所有しなければならないため、秘密鍵を管理することが困難であり、伝達しようとするメッセージにデジタル署名（digital signature）を添付させられないという短所を有する。
【０００３】
１９７６年にＤｉｆｆｉｅとＨｅｌｌｍａｎにより紹介されて以来、現代暗号学の新しい転機を設けるようになった公開鍵暗号システム（Public Key Cryptosystem）は、公開鍵及び秘密鍵を用いたシステムであって、公開鍵を誰でも利用できるように公開し、秘密鍵をユーザが保管することによって、公開鍵を有するユーザ間の非公開的なメッセージの交換が可能なようにする。
【０００４】
従来、合成数の難しい因数分解問題（factorization problem）を用いたＲＳＡ暗号システムと、離散対数問題（Discrete Logarithm Problem；ＤＬＰ）を用いたエルガマル（ElGamal）方式の暗号システムとが使用されていた。また、最近、非可換群（non abelian groups）での難しい共役演算問題（conjugacy problem）を用いたブレイド（braid）演算暗号システムが開発された。
【０００５】
楕円曲線を用いた公開鍵暗号システムは、１９９３年１２月２１日付で登録された米国特許第５，２７２，７５５号の「楕円曲線を用いた公開鍵暗号システム」（“Public key cryptosystem with an elliptic cuve”）に開示されており、共役演算問題を利用したブレイド演算暗号システムは、２０００年８月に‘Ｋ．Ｈ．Ｋｏら’により論文集［Advances in Cryptology Crypto 2000］に発表された「組糸群を用いた新公開鍵暗号システム」“New public-key cryptosystem using braid group”に開示されている。
【０００６】
Ｚｐでのエルガマル暗号のような離散対数問題を利用する場合、指数計算法（index calculus）のような効果的なアルゴリズムの開発により、可換群である有限体において群及び鍵のサイズが増加する。従って、このような問題を解決するために、離散対数問題を解く既存のアルゴリズムを回避しながら、群と鍵とを十分に安定的に維持できる公開鍵暗号システムが提示されなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従って、本発明の目的は、有限非可換群の自己同型写像を用いた離散対数問題を利用することによって、上述の短所を解消できる、有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システム、及び、有限非可換群の自己同型写像を用いた離散対数問題に基づく対称鍵交換システムを提供することにある。
【０００８】
また、非可換群を用いるとき、与えられた元の表現が約束されていなければ、平文と復号化した平文とが異なって認識され得るという問題点があるので、任意の元を選択して、与えられた表現方法により表現しなければならない。従って、非可換群を用いた暗号システムは、任意の元を与えられた表現方法により有効に表現できるかが非常に重要になる。
【課題を解決するための手段】
【０００９】
本発明に係る有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システムの一態様は、
第１非可換群（Ｇ）の生成元及び第１元（ｐ）を各々選択して、第１公開鍵（Ｉｎｎ（ｇ））として用いられる第１内部自己同型写像（Ｉｎｎ（ｇ））を計算し、第１整数である秘密鍵（ａ）及び上記第１公開鍵（Ｉｎｎ（ｇ））を用いて第２公開鍵（Ｉｎｎ（ｇａ））を生成するための公開鍵生成手段と、
平文を第２非可換群の生成元の積により表現し、任意の第２整数（ｂ）及び上記第１公開鍵（Ｉｎｎ（ｇ））を用いて第２内部自己同型写像（Ｉｎｎ（ｇｂ））を計算し、上記第２整数（ｂ）及び第２公開鍵（Ｉｎｎ（ｇａ））を用いて第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を計算し、上記第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を用いて暗号文を生成するための暗号化手段と、
上記秘密鍵（ａ）及び上記第２内部自己同型写像（Ｉｎｎ（ｇｂ））を用いて第４内部自己同型写像（Ｉｎｎ（ｇ−ａｂ））を生成し、上記第４内部自己同型写像（Ｉｎｎ（ｇ−ａｂ））を用いて上記暗号文（Ｅ）を復号化するための復号化手段と、
を備えていることを特徴とする。
【００１０】
本発明に係る有限非可換群の自己同型写像を用いた離散対数問題に基づく公開鍵方式の暗号化システムの他の態様は、
非可換群（Ｇ）の生成元及び元（ｐ）を各々選択して、第１公開鍵（Ｉｎｎ（ｇ））として用いられる第１内部自己同型写像（Ｉｎｎ（ｇ））を計算し、整数である秘密鍵（ａ）及び上記第１公開鍵（Ｉｎｎ（ｇ））を用いて第２公開鍵（Ｉｎｎ（ｇａ））を生成するための公開鍵生成手段と、
上記第１公開鍵（Ｉｎｎ（ｇ））及び任意の乱数（ｂ）を用いて第２内部自己同型写像（Ｉｎｎ（ｇｂ））を計算し、上記第２内部自己同型写像（Ｉｎｎ（ｇｂ））を用いて対称鍵（Ｋ）を生成するための手段と、
上記対称鍵（Ｋ）を用いて付加文を含む平文を暗号化して暗号文（Ｅ）を生成するための暗号文生成手段と、
上記暗号文（Ｅ）を用いてハッシュ関数（ｈ（Ｅ））を計算し、上記秘密鍵（ａ）、上記乱数（ｂ）及び上記ハッシュ関数（ｈ（Ｅ））を用いて電子署名（ｓ）を生成するための電子署名生成手段と、
上記電子署名（ｓ）が所定の範囲に存在するか否かを確認し、上記ハッシュ関数（ｈ（Ｅ））を計算し、上記電子署名（ｓ）、上記整数（ａ）及び上記ハッシュ関数（ｈ（Ｅ））を用いて第３内部自己同型写像（Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ））を計算し、上記第３内部自己同型写像（Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ））を用いて上記対称鍵（Ｋ）を復旧するための対称鍵復旧手段と、
上記対称鍵（Ｋ）を用いて上記暗号文（Ｅ）を復号化して復号文を求め、上記復号文から上記付加文を確認して上記電子署名が正しい署名なのか否かを確認するための署名確認手段と、
を備えていることを特徴とする。
【００１１】
【００１２】
また、本発明に係る有限非可換群の自己同型写像を用いた離散対数問題に基づく対称鍵交換システムの一態様は、
非可換群（Ｇ）の生成元及び元（ｐ）を各々選択して、公開鍵（Ｉｎｎ（ｇ））として用いられる第１内部自己同型写像（Ｉｎｎ（ｇ））を計算するための公開鍵生成手段と、
第１ユーザによって選択された第１乱数（ａ）及び上記公開鍵（Ｉｎｎ（ｇ））を用いて第２内部自己同型写像（Ｉｎｎ（ｇａ））を計算し、上記第２内部自己同型写像（Ｉｎｎ（ｇａ））を第２ユーザに提供するための手段と、
上記第２ユーザによって選択された第２乱数（ｂ）及び上記第２内部自己同型写像（Ｉｎｎ（ｇａ））を用いて第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を計算し、上記第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を利用して対称鍵（Ｋ）を計算するための対称鍵計算手段と、
上記第２ユーザによって選択された上記第２乱数（ｂ）を用いて第４内部自己同型写像（Ｉｎｎ（ｇｂ））を計算して、上記第４内部自己同型写像（Ｉｎｎ（ｇｂ））を上記第１ユーザに提供するための手段と、
上記第２ユーザによって提供された上記第４内部自己同型写像（Ｉｎｎ（ｇｂ））及び上記第１乱数（ａ）を利用して上記第３内部自己同型写像（Ｉｎｎ（ｇａｂ））を計算し、上記第３内部自己同型写像を利用して、上記対称鍵（Ｋ）を再計算するための対称鍵再計算手段と、
を備え、
上記再計算された対称鍵（Ｋ）は、上記第１ユーザに提供されることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、有限非可換群の内部自己同型写像を用いた離散対数問題を利用することによって、次のような効果を得ることができる。
【００１４】
第一に、離散対数問題を速く解くための準指数時間アルゴリズムの適用を回避することができる。第二に、中心が大きい非可換群を使用することによって、共役演算問題に依存せずに、安全性を維持することができる。第三に、変形したエルガマル方式を適用することによって、メッセージを暗号化する度に異なる乱数を発生するので、暗号化する必要がなく、暗復号化の高速化を図ることができる。第四に、既存の非可換群を用いた公開鍵暗号化方法を署名に使用するのが困難であったのとは異なり、署名に容易に利用することができる。
【発明を実施するための最良の形態】
【００１５】
以下、添付の図面を参照して本発明を詳細に説明する。
【００１６】
図１乃至図５は、本発明の実施の一形態における有限非可換群を用いた公開鍵暗号システムを説明するためのフローチャートであり、括弧中の内容は、一般化した有限非可換群の暗号システムに関する内容で、これについては後述する。
【００１７】
本発明は、特殊な共役演算問題及び離散対数問題に基づく新しい暗号化方法を提案する。ｐは、大きい素数であり、Ｇは、中心の元の個数が１個でない非可換群であり、第１元ｇは、Ｇの元であり、位数がｐであり、Ｇの中心に入っていないものであり、｛ｅｉ｝は、Ｇの生成元集合（generator set）であると仮定する。
【００１８】
ここで、
【数１】
0003955567.tif 000002
【００１９】
であるとき、
【数２】
0003955567.tif 000003
【００２０】
が既知であれば、同型写像（isomorphism）Ｉｎｎ（ｇ）を得ることができる。即ち、ｍを
【数３】
0003955567.tif 000004
【００２１】
によって表現すると、
【数４】
0003955567.tif 000005
【００２２】
となる。Ｉｎｎ（ｇ）は、
【数５】
0003955567.tif 000006
【００２３】
で表すことができる。
【００２４】
これにより、図１に示したように、平文Ｍを暗号化するために使われる公開鍵の生成過程は、次の通りである。
【００２５】
素数値ｐを選択し（ステップＳ１）、上述の特徴を有する有限非可換群Ｇを選択する（ステップＳ２）。上記有限非可換群Ｇの元の生成元｛ｅｉ｝が選択され、中心の元でなく、位数が大きい素数ｐを有する元ｇが選択される（ステップＳ３）。上記で与えられたｇに対して内部自己同型写像Ｉｎｎ（ｇ）が下記の数式（１）により計算される（ステップＳ４）。
【数６】
0003955567.tif 000007
【００２６】
その後、上記素数ｐより小さい任意の第１整数ａを選択して、秘密鍵として設定し、公開鍵は、内部自己同型写像Ｉｎｎ（ｇ）（以下では「第１公開鍵」という。）と上記秘密鍵ａを用いてＩｎｎ（ｇａ）（以下では「第２公開鍵」という。）として設定する（ステップＳ５及びＳ６）。
【００２７】
上記のように設定された秘密鍵と公開鍵とを用いて平文Ｍを暗号化及び復号化する過程を、図２を参照して説明する。
【００２８】
上記平文Ｍは、非可換群Ｇの元ｍ（即ち、ｍ∈Ｇ）に変換され、上記元ｍは、生成元の積（ｐｒｏｄｕｃｔ  ｏｆ  ｅｉ）により表現される（ステップＳ７及びステップＳ８）。また、任意の第２整数ｂが選択されると、上記ｂと上記第１公開鍵及び第２公開鍵を用いて各々第２内部自己同型写像Ｉｎｎ（ｇｂ）及び第３内部自己同型写像Ｉｎｎ（ｇａｂ）を計算する（ステップＳ９及びステップＳ１０）。上記第２内部自己同型写像Ｉｎｎ（ｇｂ）及び第３内部自己同型写像Ｉｎｎ（ｇａｂ）を用いて暗号文Ｅを下記の数式（２）により計算して受信側に伝送する（ステップＳ１１）。また、上記第２内部自己同型写像Ｉｎｎ（ｇｂ）は、上記暗号文Ｅとともに受信側に伝送される。
【数７】
0003955567.tif 000008
【００２９】
また、上記のように伝送された暗号文Ｅは、次のように復号化される。伝送された上記暗号文Ｅは、生成元の積により表現される（ステップＳ１２）。
【００３０】
その後、秘密鍵ａと上記第２内部自己同型写像Ｉｎｎ（ｇｂ）を用いて第４内部自己同型写像Ｉｎｎ（ｇ−ａｂ）＝Ｉｎｎ（ｇｂ）-ａを計算する（ステップＳ１３）。上記計算された値を利用すれば、ｍが下記の数式（３）により計算されるので、復号化がなされる（ステップＳ１４）。
【数８】
0003955567.tif 000009
【００３１】
上述したようなメッセージ暗復号方法を具現するための上記非可換群Ｇは、下記の数式（４）のように半直積（semi-direct product）により生成されることができる。
【数９】
0003955567.tif 000010
【００３２】
ここで、ＳＬ（２、Ｚｐ）は、非可換群Ｇの部分群であり、Ｇには、ＳＬ（２、Ｚｐ）の位数ｐを有する巡回部分群（cyclic subgroup）αが存在し、θは、下記の数式（５）のように定義される。
【数１０】
0003955567.tif 000011
【００３３】
ここで、
【数１１】
0003955567.tif 000012
【００３４】
は、Ｚｐから上記巡回部分群への同型写像（isomorphism）である。
【数１２】
0003955567.tif 000013
【００３５】
が成立し、これを用いて（ａ、ｂ）の共役演算を計算すれば、下記の数式（６）のようになるが、このとき、ｇ＝（ｘ、ｙ）とする。
【数１３】
0003955567.tif 000014
【００３６】
ここで、ｂ＝０に固定されると、下記の数式（７）が得られる。
【数１４】
0003955567.tif 000015
【００３７】
ここで、ＳＬ（２、Ｚｐ）の特殊な共役演算問題を解くと、
【数１５】
0003955567.tif 000016
【００３８】
が得られる。上記の特殊な共役演算問題というのは、Ｉｎｎ（ｘ）が与えられたとき、Ｉｎｎ（ｘ′）＝Ｉｎｎ（ｘ）を満足するｘ′を求める問題である。
【００３９】
また、（ｘ１、ｙ１）∈Ｇが
【数１６】
0003955567.tif 000017
【００４０】
を満足すると仮定すれば、ｂ≠０に対して、Ｚｐが可換群であり、
【数１７】
0003955567.tif 000018
【００４１】
が準同型写像（homomorphism）であるという事実を利用して容易に下記の数式（８）を得ることができる。
【数１８】
0003955567.tif 000019
【００４２】
即ち、特殊な共役演算問題に対する解の集合は、下記の数式（９）により表現することができる。
【数１９】
0003955567.tif 000020
【００４３】
ここで、Ｓは、元の個数であり、｜Ｓ｜は、２ｐである。
【００４４】
もしＩｎｎ（ｇ）＝Ｉｎｎ（ｇ１）ならば、Ｉｎｎ（ｇ−１ｇ１）＝Ｉｄが成立する。これは、ｇ−１ｇ１がＧの中心にある１つの元であることを意味する。また、ある中心元ｇ０に対してＩｎｎ（ｇｇ０）＝Ｉｎｎ（ｇ）となる。従って、Ｇの中心の元の個数は、２ｐになることが分かる。また、中心でｍとｇとを選択する確率は、２ｐ／ｐ３＝１／ｐ２≒０、２ｐ／ｐ４＝２／ｐ３≒０であることに注目すべきである。また、ｍは、Ｇの部分群であるＳＬ（２、Ｚｐ）から選択する。
【００４５】
上記数式（４）により非可換群Ｇが生成されると、ＳＬ（２、Ｚｐ）の生成元の集合は、｛Ｔ、Ｓ｝になる。これを表現すれば次の通りである。
【数２０】
0003955567.tif 000021
【００４６】
そして、ここには、ＳＬ（２、Ｚｐ）の元（ｇ∈ＳＬ（２、Ｚｐ））の各々の分解（decomposition）を知ることができるアルゴリズムが存在する。即ち、ＳＬ（２、Ｚｐ）の任意の元ｇは、下記の数式（１０）により計算される。
【数２１】
0003955567.tif 000022
【００４７】
ここで、ｉ０、ｉｎ＋１は、０又は１であり、ｊｎ＝±１、±２・・・である。
【００４８】
もしｍ∈ＳＬ（２、Ｚｐ）ならば、ｍは、下記の数式（１１）により表現することができる（以下では「第１定理」という）。
【数２２】
0003955567.tif 000023
【００４９】
これを証明するために、
【数２３】
0003955567.tif 000024
【００５０】
を計算すれば、下記の数式（１２）を得ることができる。
【数２４】
0003955567.tif 000025
【００５１】
上記数式（１２）及びＺｐが体（field）であるという事実から、ある与えられたｍ∈ＳＬ（２、Ｚｐ）に対して
【数２５】
0003955567.tif 000026
【００５２】
を満足するj1, j2, j3 を求めることができる。即ち、上記３つの値 j1, j2, j3 が決定されれば、ＳＬ（２、Ｚｐ）の総ての元が決定される。
【００５３】
｛（Ｔ、０）、（Ｓ、０）、（Ｉ、０）｝がＧの生成元の集合であるから、ｇＴｇ−１、ｇＳｇ−１及びｇ（Ｉ、１）ｇ−１が既知であれば、Ｉｎｎ（ｇ）を求めることができる。また、ｍ∈ＳＬ（２、Ｚｐ）であり、ＳＬ（２、Ｚｐ）がＧの正規部分群（normal subgroup）であるから、Ｉｎｎ（ｇ）は、ＳＬ（２、Ｚｐ）に制限（restriction）して考えることができ、Ｉｎｎ（ｇ）｜ＳＬ（２、Ｚｐ）は、ＳＬ（２、Ｚｐ）の自己同型写像（automorphism）となる。即ち、公開鍵は、Ｉｎｎ（ｇ）｜ＳＬ（２、Ｚｐ）とＩｎｎ（ｇａ）｜ＳＬ（２、Ｚｐ）となる。従って、｛ｇＴｇ−１、ｇＳｇ−１｝が既知であれば、Ｉｎｎ（ｇ）｜ＳＬ（２、Ｚｐ）を表現することができる。
【００５４】
位数がｐであるＳＬ（２、Ｚｐ）の元のうち、例えば、Ｉ＋δ１２が
【数２６】
0003955567.tif 000027
【００５５】
に選択される。
【００５６】
また、上記Ｉｎｎ（ｇ）で非可換群Ｇの元ｇを選択する方法は、次の通りである。
【００５７】
（ｘ、ｙ）∈Ｇである条件に対して、
【数２７】
0003955567.tif 000028
【００５８】
となる（以下では「第２定理」という）。これを証明するために、帰納法及び下記の数式（１３）を利用する。
【数２８】
0003955567.tif 000029
【００５９】
ここで、
【数２９】
0003955567.tif 000030
【００６０】
をある固定されたｃ∈ＺｐとＡ∈ＳＬ（２、Ｚｐ）に対して
【数３０】
0003955567.tif 000031
【００６１】
になるように定めると、位数がｐであるｇを選択でき、上記第２定理によりＩｎｎ（ｇ）の位数がｐであることを知ることができる。もし、無作為にｇを選択し、ｇの位数が固定されていなければ、離散対数問題に対する周知のアルゴリズムを適用するために、与えられた巡回群（cyclic group）の位数を知らなければならないので、安全性を増加させることができる。即ち、ｄ｜（ｐ＋１）（ｐ−１）各々に対してｇの位数がｐであるという仮定下に、離散対数問題を解かなければならない。
【００６２】
上述した本発明は、Ｉｎｎ（ｇ）から離散対数問題を解決できないため、安全性が維持されるが、これを詳細に説明すれば、次の通りである。
【００６３】
公開鍵Ｉｎｎ（ｇ）及びＩｎｎ（ｇ）ａから離散対数問題を解き、秘密鍵ａを得る場合、離散対数問題を解くための最も早いアルゴリズム（例えば、指数計算法）は適用されることができない。従って、ｇの位数がｐならば、離散対数問題を解決するに要する予想実行時間（run time）がＯ（ｐ）１／２−群演算（operations）になる。
【００６４】
また、秘密鍵を求める他の方法は、次の通りである。Ｇでの特殊な共役演算子問題（special conjugacy problem）は、難しい問題でなく、Ｇでの離散対数問題も下記の数式（１４）から明らかなように難しくない。
【数３１】
0003955567.tif 000032
【００６５】
ｇ及びｇａに対する離散対数問題を解くためには、ａｙ＝Ｙを解くことが必要である。しかし、Ｉｎｎ（ｇａ）だけが与えられた場合、Ｓ＝｛ｇ１｜Ｉｎｎ（ｇ１）＝Ｉｎｎ（ｇａ）｝の元の個数は、２ｐであるから、Ｓからｇａを求めるためには、Ｏ（ｐ）回の試みが必要である。従って、この方法は、Ｉｎｎ（ｇ）及びＩｎｎ（ｇａ）から直接ａを求めることより非効率的であることが分かる。
【００６６】
１６０ビット素数ｐを選択すれば、本発明の安全性は、１０２４ビットＲＳＡと類似になる（即ち、Ｉｎｎ（ｇ）で離散対数問題を解き、１０２４ビットＲＳＡを因数分解するに要する予想実行時間は各々約２８７及び２８０になる）。また、Ｉｎｎ（ｇ）は、Ａｕｔ（Ｇ）⊂Ｅｎｄ（Ｇ）⊂ＧＧに含まれ、ここで、Ｅｎｄ（Ｇ）は、Ｇの自己準同型（ｅｎｄｏｍｏｒｐｈｉｓｍ）群であり、ＧＧは、ＧからＧまでの総ての関数の集合である。これらは、甚だしくは、行列群でも表現されないため、これらのいずれにも指数計算法を適用できない。
【００６７】
ここで、本発明をＲＳＡ及びＸＴＲと比較すると、次のような利点があることが分かる。即ち、ＲＳＡ及びＸＴＲで公開鍵から秘密鍵を探すために必要とする予想実行時間は、準指数時間であるのに対し、本発明では、指数実行時間Ｏ（ｐ）１／２が必要である。
【００６８】
ここで、Ｉｎｎ（ｇ）からＩｎｎ（ｇｂ）を計算する方法を説明する。Ｉｎｎ（ｇ２）の計算は、下記の数式（１５）及び数式（１６）に示される通りである。
【数３２】
0003955567.tif 000033
【数３３】
0003955567.tif 000034
【００６９】
また、４回の乗算を用いて下記の数式（１７）によりＩｎｎ（ｇ）（Ｔ）から（Ｉｎｎ（ｇ）（Ｔ））ｊを得ることができる。
【数３４】
0003955567.tif 000035
【００７０】
となる。
【００７１】
従って、Ｉｎｎ（ｇ２）（Ｓ）及びＩｎｎ（ｇ２）（Ｔ）を計算するためには、９２の乗算が必要である。従って、Ｉｎｎ（ｇ）からＩｎｎ（ｇｂ）を計算するためには、約９２ｌｏｇ２ｐの乗算が必要であり、Ｉｎｎ（ｇａ）からＩｎｎ（ｇａｂ）を計算するためには、９２ｌｏｇ２ｐの乗算が必要である。従って、暗号化のための乗算の数は、約１８４ｌｏｇ２ｐとなる。１つの乗算が０（（ｌｏｇ２ｐ）２）ビット演算を必要とするので、暗号化は、ある定数ｃに対して約１８４（ｌｏｇ２ｐ）３Ｃ≒８×１０８Ｃビットの演算を必要とする。１０２４ビットＲＳＡでは、（ｌｏｇ２ｎ）３Ｃ≒（１０２４）３Ｃ≒１０９Ｃビットの演算が必要である。ＲＳＡ暗号化設計で、公開指数が３２ビットになれば、３．２×１０７Ｃビット演算が必要である。
【００７２】
本発明によれば、高速の暗号化及び復号化が可能なように変形が可能であるが、これを詳細に説明すれば、次の通りである。
【００７３】
例えば、「甲」が「乙」に暗号化したメッセージを送ろうとする場合、「甲」は、最初の通信時だけにＩｎｎ（ｇａ）ｂとＩｎｎ（ｇｂ）を計算して、Ｉｎｎ（ｇｂ）を「乙」に送る。「乙」は、受信したＩｎｎ（ｇｂ）を用いてＩｎｎ（ｇｂ）−ａを計算する。「甲」は、メッセージｍを最初の通信後に固定されたｂに対して暗号文Ｅ＝Ｉｎｎ（ｇａ）ｂ（ｍ）で暗号化した後、上記暗号文Ｅを「乙」に送る。「乙」はＩｎｎ（ｇｂ）−ａ（Ｅ）を計算することによってＥを復号化できる。
【００７４】
即ち、与えられたＩｎｎ（ｇａ）ｂとｍからＩｎｎ（ｇａ）ｂ（ｍ）を計算するために、４６回の乗算が必要なので、暗号化に約１．２×１０６Ｃビットの演算が必要である。３２ビット公開指数がＲＳＡに使われても、暗号化に３.２×１０７Ｃビットの演算が必要である。本発明により暗号化を行うと、１０２４ビットＲＳＡより約３０倍程度早い暗号化がなされる。
【００７５】
また、復号化のためには、暗号化するために必要な分の乗算が必要である。ＲＳＡの復号化に際して、「中国余剰定理」（‘Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｏｒｅｍ’）を適用しても、約２．５×１０８Ｃビットの演算が必要である。従って、本発明の復号化は、ＲＳＡの解読より２００倍速い。
【００７６】
ＥＣＣでは、ｂが固定されてはならないため、ｇｂの事前計算が不可能になる。従って、１７０ビットＥＣＣでの復号化のための乗算の数は、各々１９００になる。従って、ＥＣＣより約４０倍程度速い復号化速度を有する。
【００７７】
また、ＥＣＣでは、復号化にＯ（ｌｏｇ２ｐ）の乗算が必要なので、乗算の数は、ビットｌｏｇ２ｐの個数に比べて線形的に増加するであろう。これに対し、本発明の復号化には、ｐのサイズとは関係なく４６回の乗算が必要である。下記の表１は、本発明及びＥＣＣの復号化に要する乗算の数を比較したデータである。
【表１】
0003955567.tif 000036
【００７８】
上記表で、同じ行での暗号システムは、略同じ安全性を有する。
【００７９】
本発明は、鍵の表現及び鍵のサイズにおいて、Ｉｎｎ（ｇａ）（Ｔ）とＩｎｎ（ｇａ）（Ｓ）は、ＳＬ（２、Ｚｐ）の元として見なされ得るため、各々を３つの項により表現できる。Ｉｎｎ（ｇａ）（Ｔ）が３ｌｏｇ２ｐビットで表現されるので、Ｉｎｎ（ｇａ）を表現するためには、６ｌｏｇ２ｐビットが必要である。ｐが１６０ビット素数である場合、Ｉｎｎ（ｇａ）を表現するためには、９６０ビットが必要である。従って、公開鍵は、ＲＳＡより小さいサイズで表現され得る。秘密鍵のサイズは、ｌｏｇ２ｐ≒１６０ビットであるから、１０２４ビットＲＳＡよりかなり小さくなる。
【００８０】
上述したように、本発明は、有限非可換群を用いた新しい公開鍵暗号システムを提供し、上記暗号化方式に使用され得る有限非可換群の一例を提示する。上記のような暗号化方式は、有限非可換群にのみ限定されるものでなく、他の非可換群を利用する場合にも適用されることができる。しかし、暗号化の安全性のためには、非可換群を選択することに注意すべきである。
【００８１】
即ち、中心でない可換正規部分群の存在は、安全性を減少させる。従って、任意の可換正規部分群は小さくなければならないし、Ｇの元を生成元の積により表現するアルゴリズムは、効率的でなければならない。また、Ｉｎｎ（ｇ）は、｛Ｉｎｎ（ｇ）（ｅｉ）∈Ｇ｜ｅｉは生成元｝により表現されるので、生成元の個数が小さくなければならない。また、内部自己同型写像の代わりに、ＧからＡｕｔ（Ｇ）までの他の準同型写像を使用することができる。
【００８２】
一方、上述した公開鍵暗号システムは、電子署名、鍵交換などいろいろな分野に適用することができる。上記公開鍵暗号システムを用いた電子署名及び鍵交換方式を説明すると、次の通りである。
【００８３】
上記公開鍵暗号システムを用いた電子署名方式は、図３及び図４に図示されている。例えば、「甲」が「乙」に平文Ｍを伝送しながら電子署名をすると仮定する。上記電子署名方式は、図１で説明された段階を通じて生成された公開鍵Ｉｎｎ（ｇ）、Ｉｎｎ（ｇａ）及び秘密鍵ａを用いて行われるが、その署名過程は、図３に示す通りである。「甲」は、乱数ｂ（任意の整数から無作為に抽出された整数）を選択した後（ステップＳ３１）、上記乱数ｂを用いてＩｎｎ（ｇｂ）を計算する（ステップＳ３２）。上記Ｉｎｎ（ｇｂ）を用いて対称鍵Ｋを生成し（ステップＳ３３）、上記対称鍵Ｋを用いて付加文を含む平文（メッセージ）Ｍを暗号化して暗号文Ｅを求める（ステップＳ３４）。
【００８４】
その後、上記暗号文Ｅを用いてハッシュ関数ｈ＝ｈ（Ｅ）を計算し（ステップＳ３５）、電子署名ｓは、下記の数式（１８）により計算される（ステップＳ３６）。
【数３５】
0003955567.tif 000037
【００８５】
「甲」は、上記暗号文Ｅと電子署名ｓを「乙」に伝送する。
【００８６】
上述したような電子署名の確認過程は、図４に示す通りである。「乙」は、伝送された電子署名ｓが０≦ｓ＜ｐの範囲内に存在するか否かを確認する（ステップＳ４１）。「甲」は、ハッシュ関数ｈ＝ｈ（Ｅ）を計算した後（ステップＳ４２）、Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ）を計算する（ステップＳ４３）。その後、上記Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ）を用いて対称鍵Ｋを復旧した後（ステップＳ４４）、上記対称鍵Ｋを用いて暗号化された付加文を含む暗号文Ｅを復号化して、上記付加文が適切か否かを確認し、正しい署名なのか否かを確認する（ステップＳ４５及びステップＳ４６）。上記署名が正しい場合、平文（メッセージ）Ｍを正しいメッセージとして受け入れる。
【００８７】
上記電子署名方式で、対称鍵Ｋの代わりに、Ｉｎｎ（ｇａｂ）（ｍ）で暗号化してもよい。これにより、乱数ｂを固定して使用しても、暗号化及び復号化時と同様に、安全性には問題がない。
【００８８】
上記公開鍵暗号システムを用いた鍵交換方式は、図５に図示されている。例えば、「甲」と「乙」が互いに鍵を交換する場合、上記鍵交換方式は、図１で説明された段階を通じて生成された公開鍵Ｉｎｎ（ｇ）を用いて行われるが、その鍵交換過程は、図５に示す通りである。
【００８９】
「甲」は、乱数ａを選択した後（ステップＳ５１）、上記乱数ａを用いてＩｎｎ（ｇａ）を計算する（ステップＳ５２）。その後、「甲」は、Ｉｎｎ（ｇａ）を「乙」に伝送する。「乙」は、乱数ｂを選択した後（ステップＳ５３）、上記乱数ｂを用いてＩｎｎ（ｇａｂ）を計算し（ステップＳ５４）、上記Ｉｎｎ（ｇａｂ）を用いて対称鍵Ｋを生成する（ステップＳ５５）。
【００９０】
その後、「乙」は、Ｉｎｎ（ｇｂ）を計算して「甲」に伝送し（ステップＳ５６）、「乙」は、Ｉｎｎ（ｇｂ）及び乱数ａを用いてＩｎｎ（ｇａｂ）を計算する（ステップＳ５７）。その後、「甲」は、Ｉｎｎ（ｇａｂ）から対称鍵Ｋを求める（ステップＳ５８）。
【００９１】
上記で説明した暗号システムは、次のように一般化することができる。上記で内部自己同型写像群を使用した理由は、一般的に自己同型写像群を知ることは容易でないが、部分群である内部自己同型写像群は容易に知ることができるからである。しかし、ある群の自己同型写像の他の部分群を知ることができれば、上記暗号システムの一般化を図ることができる。これを詳細に説明すると、次の通りである。群Ｇ及びＧ′に対して準同型写像Ф：Ｇ→Ａｕｔ（Ｇ′）が与えられたとき、Ф（Ｇ）での離散対数問題を利用した暗号システムを、Ｉｎｎ（Ｇ）での離散対数問題を利用した上記暗号システムと同じ方法で作る。即ち、上記で使われたＩｎｎの代わりに、Фをそのまま適用する。この場合、メッセージｍは、Ｇ′から選択され、Ｅ＝Ф（ｇ）ａｂ（ｍ）になる。内部自己同型写像群Ｉｎｎ（Ｇ）を使用した場合、安全性が、Ｋｅｒ（Ｉｎｎ）である中心のサイズと密接な関連があったことと同様に、この場合にも、安全性は、Ｋｅｒ（Ф）のサイズと密接な関係がある。
【００９２】
上記の一般化した暗号システムは、エルガマル暗号を含む大きなシステムである。エルガマル方式は、Ｇ＝Ｇ′＝Ｚｐのとき、上記の特殊な場合である。詳細に説明すれば、次の通りである。
【数３６】
0003955567.tif 000038
【００９３】
であるとき、
【数３７】
0003955567.tif 000039
【００９４】
を作ることができる。ここで、αの
【数３８】
0003955567.tif 000040
【００９５】
での位数を｜α｜とする。
【数３９】
0003955567.tif 000041
【００９６】
を満足するｓ、ｔに対して
【数４０】
0003955567.tif 000042
【００９７】
である同型写像を定義することができ、これから、可解群（solvable group）
【数４１】
0003955567.tif 000043
【００９８】
を作ることができる。このように定義されたＧに対してＩｎｎ（Ｇ）での離散対数を用いた基本的なシステムは、可換正規群の存在に起因して弱点を有する。しかし、
【数４２】
0003955567.tif 000044
【００９９】
とし、上記の一般化したシステムを使用すれば、弱点を補完することができる。
【０１００】
また、Ｇの特殊な共役演算問題を解くと、任意のＩｎｎ（Ｇ）の元を生成元の積で容易に表現することができる。｜ｔ｜と｜ｓ｜を十分に小さく取れば、Ｇの特殊な共役演算問題を容易に解くことができるので、任意の元を生成元の積で容易に表現することができる。また、ｒ１＝｜α｜であるとき、ｌｃｍ（ｍ／ｔ−ｌ、ｒ１）＞＞ｍ／ｔ−ｌであるｒ１、ｍ、ｔを選択する。
【図面の簡単な説明】
【０１０１】
【図１】本発明による有限非可換群を用いた公開鍵の生成方法を説明するためのフローチャートである。
【図２】図１に示された公開鍵を用いてメッセージを暗号化及び復号化する方法を説明するためのフローチャートである。
【図３】図１に示された公開鍵を用いた電子署名方法を説明するためのフローチャートである。
【図４】図１に示された公開鍵を用いた電子署名確認方法を説明するためのフローチャートである。
【図５】図１に示された公開鍵を用いた鍵交換方法を説明するためのフローチャートである。
【図１】
0003955567.tif 000054
【図２】
0003955567.tif 000055
【図３】
0003955567.tif 000056
【図４】
0003955567.tif 000057
【図５】
0003955567.tif 000058