(57)【要約】本発明による暗号化及び復号化方法は、第１非可換群の生成源及び第１元素を各々選択して、第１公開鍵として用いられる第１内部自己同型写像を計算し、第１整数である秘密鍵及び上記第１公開鍵を用いて第２公開鍵を生成する段階と、平文を第２非可換群の生成源の積により表現し、任意の第２整数及び上記第１公開鍵を用いて第２内部自己同型写像を計算し、上記第２整数及び第２公開鍵を用いて第３内部自己同型写像を計算し、上記第３内部自己同型写像を用いて暗号文を生成する段階と、上記秘密鍵及び上記第２内部自己同型写像を用いて第４内部自己同型写像を生成し、上記第４内部自己同型写像を用いて上記暗号文を復号化する段階と、を備えているものである。
2004534971.tif 000002
【特許請求の範囲】
【請求項１】
第１非可換群の生成源及び第１元素を各々選択して、第１公開鍵として用いられる第１内部自己同型写像を計算し、第１整数である秘密鍵及び前記第１公開鍵を用いて第２公開鍵を生成する段階と、
平文を第２非可換群の生成源の積により表現し、任意の第２整数及び前記第１公開鍵を用いて第２内部自己同型写像を計算し、前記第２整数及び第２公開鍵を用いて第３内部自己同型写像を計算し、前記第３内部自己同型写像を用いて暗号文を生成する段階と、
前記秘密鍵及び前記第２内部自己同型写像を用いて第４内部自己同型写像を生成し、前記第４内部自己同型写像を用いて前記暗号文を復号化する段階と、
を備えていることを特徴とする有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項２】
ＳＬ（２、Ｚｐ）を非可換群、θをＺｐからＳＬ（２、Ｚｐ）の自己同型写像群への単射である準同型写像とすると、前記第１非可換群Ｇは、下記数式
【数１】
2004534971.tif 000046
により表現されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項３】
前記第２非可換群は、前記第１非可換群と同一であるか、又は、前記第１非可換群の部分集合であることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項４】
前記第２非可換群は、ＳＬ（２、Ｚｐ）により表現されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項５】
前記第１元素は、前記第１非可換群の中心の元素でなく、位数が大きい素数であることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項６】
Ｔ、Ｓを第２非可換群ＳＬ（２、Ｚｐ）の生成源、ｇを第１元素とすると、前記第１内部自己同型写像Ｉｎｎ（ｇ）は、下記数式
【数２】
2004534971.tif 000047
により計算されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項７】
前記秘密鍵は、所定の素数値ｐより小さい第１整数であることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項８】
ｊｎ＝±１、±２・・・、ｎは整数、
【数３】
2004534971.tif 000048
とすると、前記第２元素ｍは、下記数式
【数４】
2004534971.tif 000049
によって示される生成源（Ｔ及びＳ）の積により表現されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項９】
前記生成源Ｔの内部自己同型写像Ｉｎｎ（ｇ）（Ｔ）が下記数式
【数５】
2004534971.tif 000050
により表現される場合、ｊを整数とすると、（Ｉｎｎ（ｇ）（Ｔ））ｊ は、下記数式
【数６】
2004534971.tif 000051
により計算されることを特徴とする請求項８に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１０】
前記第２整数ｂは、高速の暗復号化が可能なように、前記暗号文Ｅを生成する度に変更されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１１】
前記第２整数ｂは、高速の暗復号化が可能なように、前記暗号文Ｅを生成する度に固定されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１２】
前記第２内部自己同型写像は、Ｉｎｎ（ｇｂ）により表現されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１３】
前記第３内部自己同型写像は、Ｉｎｎ（ｇａｂ）により表現されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１４】
Ｉｎｎ（ｇａｂ）を第３内部自己同型写像、ｍを第２元素とすると、前記暗号文Ｅは、下記数式
【数７】
2004534971.tif 000052
により計算されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１５】
Ｉｎｎ（ｇｂ）を第２内部自己同型写像、ａを第１整数とすると、前記第４内部自己同型写像は、下記数式
【数８】
2004534971.tif 000053
により表現されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１６】
ｍを第２元素、Ｉｎｎ（ｇ−ａｂ）を第４内部自己同型写像とすると、前記暗号文Ｅは、下記数式
【数９】
2004534971.tif 000054
により復号化されることを特徴とする請求項１に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項１７】
非可換群の生成源及び元素を各々選択して、第１公開鍵として用いられる第１内部自己同型写像を計算し、整数である秘密鍵及び前記第１公開鍵を用いて第２公開鍵を生成する段階と、
前記第１公開鍵及び任意の乱数を用いて第２内部自己同型写像を計算し、前記第２内部自己同型写像を用いて対称鍵を生成し、前記対称鍵を用いて付加文を含む平文を暗号化して暗号文を計算し、前記暗号文を用いてハッシュ関数を計算し、前記整数、前記乱数及びハッシュ関数を用いて署名する段階と、
前記署名が所定の範囲に存在するか否かを確認し、前記ハッシュ関数を計算し、前記署名、前記整数及び前記ハッシュ関数を用いて第３内部自己同型写像を計算し、前記第３内部自己同型写像を用いて前記対称鍵を復旧し、前記対称鍵を用いて前記暗号文を復号化して復号文を求め、前記復号文から前記付加文を確認して前記署名が正しい署名なのか否かを確認する段階と、
を備えていることを特徴とする有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項１８】
ＳＬ（２、Ｚｐ）を非可換群、θをＺｐからＳＬ（２、Ｚｐ）の自己同型写像群への単射である準同型写像とすると、前記非可換群Ｇは、下記数式
【数１０】
2004534971.tif 000055
により表現されることを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項１９】
前記元素は、前記非可換群の中心の元素でなく、位数が大きい素数であることを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項２０】
Ｔ、Ｓを非可換群ＳＬ（２、Ｚｐ）の生成源、ｇを元素とすると、前記第１内部自己同型写像Ｉｎｎ（ｇ）は、下記数式
【数１１】
2004534971.tif 000056
により計算されることを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項２１】
前記第２内部自己同型写像は、Ｉｎｎ（ｇｂ）により表現され、ｂは、乱数であることを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項２２】
Ｅを暗号文とすると、前記ハッシュ関数ｈは、下記数式
【数１２】
2004534971.tif 000057
に示されるようにＳＬ（２、Ｚｐ）からＺｐへ至り、ＳＬ（２、Ｚｐ）は、非可換群であることを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項２３】
ａを秘密鍵、ｈをハッシュ関数、ｂを乱数、ｐを素数とすると、前記署名ｓは、下記数式
【数１３】
2004534971.tif 000058
により計算されることを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項２４】
前記署名は、０≦ｓ＜ｐの範囲内に存在することを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項２５】
前記第３内部自己同型写像は、Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ）により表現され、ａは秘密鍵であり、ｈはハッシュ関数であることを特徴とする請求項１７に記載の有限非可換群を用いた公開鍵暗号システムの署名方法。
【請求項２６】
非可換群の生成源及び元素を各々選択して、公開鍵として用いられる第１内部自己同型写像を計算する段階と、
第１ユーザが、任意の第１乱数及び前記公開鍵を用いて第２内部自己同型写像を計算し、前記第２内部自己同型写像を第２ユーザに提供する段階と、
前記第２ユーザが、任意の第２乱数及び前記第２内部自己同型写像を用いて第３内部自己同型写像を計算し、対称鍵を生成する段階と、
前記第２ユーザが、前記第２乱数を用いて第４内部自己同型写像を計算して、前記第１ユーザに提供する段階と、
前記第１ユーザが、前記第４内部自己同型写像及び前記第１乱数を用いて前記第３内部自己同型写像を計算し、前記第３内部自己同型写像を用いて前記対称鍵を求める段階と、
を備えていることを特徴とする有限非可換群を用いた公開鍵暗号システムの鍵交換方法。
【請求項２７】
ＳＬ（２、Ｚｐ）を非可換群、θをＺｐからＳＬ（２、Ｚｐ）の自己同型写像群への単射である準同型写像とすると、前記非可換群Ｇは、下記数式
【数１４】
2004534971.tif 000059
により表現されることを特徴とする請求項２６に記載の有限非可換群を用いた公開鍵暗号システムの鍵交換方法。
【請求項２８】
前記元素は、前記非可換群の中心の元素でなく、位数が大きい素数であることを特徴とする請求項２６に記載の有限非可換群を用いた公開鍵暗号システムの鍵交換方法。
【請求項２９】
Ｔ、Ｓを非可換群ＳＬ（２、Ｚｐ）の生成源、ｇを元素とすると、前記第１内部自己同型写像Ｉｎｎ（ｇ）は、下記数式
【数１５】
2004534971.tif 000060
により計算されることを特徴とする請求項２６に記載の有限非可換群を用いた公開鍵暗号システムの鍵交換方法。
【請求項３０】
前記第２内部自己同型写像は、Ｉｎｎ（ｇａ）により表現され、ａは、第１乱数であることを特徴とする請求項２６に記載の有限有限非可換群を用いた公開鍵暗号システムの鍵交換方法。
【請求項３１】
前記第３内部自己同型写像は、Ｉｎｎ（ｇａｂ）により表現され、ａは、第１乱数であり、ｂは、第２乱数であることを特徴とする請求項２６に記載の有限非可換群を用いた公開鍵暗号システムの鍵交換方法。
【請求項３２】
前記第４内部自己同型写像は、Ｉｎｎ（ｇｂ）により表現され、ｂは、第２乱数であることを特徴とする請求項２６に記載の有限非可換群を用いた公開鍵暗号システムの鍵交換方法。
【請求項３３】
第１群の第１元素を選択して、第１公開鍵として用いられる第２群の第１自己同型写像を計算し、第１整数である秘密鍵及び前記第１公開鍵を用いて第２公開鍵を生成する段階と、
平文を前記第２群の生成源の積により表現し、任意の第２整数及び前記第１公開鍵を用いて第２自己同型写像を計算し、前記第２整数及び第２公開鍵を用いて第３自己同型写像を計算し、前記第３自己同型写像を用いて暗号文を生成する段階と、
前記秘密鍵及び前記第２自己同型写像を用いて第４自己同型写像を生成し、前記第４自己同型写像を用いて前記暗号文を復号化する段階と、
を備えていることを特徴とする有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項３４】
準同型写像を、
【数１６】
2004534971.tif 000061
とし、かつ、準同型写像を、
【数１７】
2004534971.tif 000062
を満足するｓ、ｔに対して
【数１８】
2004534971.tif 000063
とすると、前記第１群Ｇは、下記数式
【数１９】
2004534971.tif 000064
により表現されることを特徴とする請求項３３に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項３５】
前記数式においてｒ１＝｜α｜であるときはｌｃｍ（ｍ／ｔ−ｌ、ｒ１）＞＞ｍ／ｔ−ｌを満足するｒ１、ｍ、ｔを選択して安全性を高め、｜ｓ｜及び｜ｔ｜を小さく選択してＧの特殊な共役演算問題が容易に解かれるようにして、Ｉｎｎ（Ｇ）の元素が容易に生成源の積により表現されるようにすることを特徴とする請求項３４に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【請求項３６】
前記第２群は、Ｉｎｎ（Ｇ）により表現されることを特徴とする請求項３３に記載の有限非可換群を用いた公開鍵暗号システムの暗号化及び復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限非可換群を用いた公開鍵暗号システムに関し、特に、有限非可換群を生成する方法、並びに、その非可換群を用いた有効な公開鍵暗号システムの実現及びその応用方法に関する。
【背景技術】
【０００２】
慣用（又は対称形）暗号システム（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）であると仮定する。
【００１８】
ここで、
【数１】
2004534971.tif 000003
【００１９】
であるとき、
【数２】
2004534971.tif 000004
【００２０】
が既知であれば、同型写像（isomorphism）Ｉｎｎ（ｇ）を得ることができる。即ち、ｍを
【数３】
2004534971.tif 000005
【００２１】
によって表現すると、
【数４】
2004534971.tif 000006
【００２２】
となる。Ｉｎｎ（ｇ）は、
【数５】
2004534971.tif 000007
【００２３】
で表すことができる。
【００２４】
これにより、図１に示したように、平文Ｍを暗号化するために使われる公開鍵の生成過程は、次の通りである。
【００２５】
素数値ｐを選択し（ステップＳ１）、上述の特徴を有する有限非可換群Ｇを選択する（ステップＳ２）。上記有限非可換群Ｇの元素の生成源｛ｅｉ｝が選択され、中心の元素でなく、位数が大きい素数ｐを有する元素ｇが選択される（ステップＳ３）。上記で与えられたｇに対して内部自己同型写像Ｉｎｎ（ｇ）が下記の数式（１）により計算される（ステップＳ４）。
【数６】
2004534971.tif 000008
【００２６】
その後、上記素数ｐより小さい任意の第１整数ａを選択して、秘密鍵として設定し、公開鍵は、内部自己同型写像Ｉｎｎ（ｇ）（以下では「第１公開鍵」という。）と上記秘密鍵ａを用いてＩｎｎ（ｇａ）（以下では「第２公開鍵」という。）として設定する（ステップＳ５及びＳ６）。
【００２７】
上記のように設定された秘密鍵と公開鍵とを用いて平文Ｍを暗号化及び復号化する過程を、図２を参照して説明する。
【００２８】
上記平文Ｍは、非可換群Ｇの元素ｍ（即ち、ｍ∈Ｇ）に変換され、上記元素ｍは、生成源の積（ｐｒｏｄｕｃｔ  ｏｆ  ｅｉ）により表現される（ステップＳ７及びステップＳ８）。また、任意の第２整数ｂが選択されると、上記ｂと上記第１公開鍵及び第２公開鍵を用いて各々第２内部自己同型写像Ｉｎｎ（ｇｂ）及び第３内部自己同型写像Ｉｎｎ（ｇａｂ）を計算する（ステップＳ９及びステップＳ１０）。上記第２内部自己同型写像Ｉｎｎ（ｇｂ）及び第３内部自己同型写像Ｉｎｎ（ｇａｂ）を用いて暗号文Ｅを下記の数式（２）により計算して受信側に伝送する（ステップＳ１１）。また、上記第２内部自己同型写像Ｉｎｎ（ｇｂ）は、上記暗号文Ｅとともに受信側に伝送される。
【数７】
2004534971.tif 000009
【００２９】
また、上記のように伝送された暗号文Ｅは、次のように復号化される。伝送された上記暗号文Ｅは、生成源の積により表現される（ステップＳ１２）。
【００３０】
その後、秘密鍵ａと上記第２内部自己同型写像Ｉｎｎ（ｇｂ）を用いて第４内部自己同型写像Ｉｎｎ（ｇ−ａｂ）＝Ｉｎｎ（ｇｂ）-ａを計算する（ステップＳ１３）。上記計算された値を利用すれば、ｍが下記の数式（３）により計算されるので、復号化がなされる（ステップＳ１４）。
【数８】
2004534971.tif 000010
【００３１】
上述したようなメッセージ暗復号方法を具現するための上記非可換群Ｇは、下記の数式（４）のように半直積（semi-direct product）により生成されることができる。
【数９】
2004534971.tif 000011
【００３２】
ここで、ＳＬ（２、Ｚｐ）は、非可換群Ｇの部分群であり、Ｇには、ＳＬ（２、Ｚｐ）の位数ｐを有する巡回部分群（cyclic subgroup）αが存在し、θは、下記の数式（５）のように定義される。
【数１０】
2004534971.tif 000012
【００３３】
ここで、
【数１１】
2004534971.tif 000013
【００３４】
は、Ｚｐから上記巡回部分群への同型写像（isomorphism）である。
【数１２】
2004534971.tif 000014
【００３５】
が成立し、これを用いて（ａ、ｂ）の共役演算を計算すれば、下記の数式（６）のようになるが、このとき、ｇ＝（ｘ、ｙ）とする。
【数１３】
2004534971.tif 000015
【００３６】
ここで、ｂ＝０に固定されると、下記の数式（７）が得られる。
【数１４】
2004534971.tif 000016
【００３７】
ここで、ＳＬ（２、Ｚｐ）の特殊な共役演算問題を解くと、
【数１５】
2004534971.tif 000017
【００３８】
が得られる。上記の特殊な共役演算問題というのは、Ｉｎｎ（ｘ）が与えられたとき、Ｉｎｎ（ｘ′）＝Ｉｎｎ（ｘ）を満足するｘ′を求める問題である。
【００３９】
また、（ｘ１、ｙ１）∈Ｇが
【数１６】
2004534971.tif 000018
【００４０】
を満足すると仮定すれば、ｂ≠０に対して、Ｚｐが可換群であり、
【数１７】
2004534971.tif 000019
【００４１】
が準同型写像（homomorphism）であるという事実を利用して容易に下記の数式（８）を得ることができる。
【数１８】
2004534971.tif 000020
【００４２】
即ち、特殊な共役演算問題に対する解の集合は、下記の数式（９）により表現することができる。
【数１９】
2004534971.tif 000021
【００４３】
ここで、Ｓは、元素の個数であり、｜Ｓ｜は、２ｐである。
【００４４】
もしＩｎｎ（ｇ）＝Ｉｎｎ（ｇ１）ならば、Ｉｎｎ（ｇ−１ｇ１）＝Ｉｄが成立する。これは、ｇ−１ｇ１がＧの中心にある１つの元素であることを意味する。また、ある中心元素ｇ０に対してＩｎｎ（ｇｇ０）＝Ｉｎｎ（ｇ）となる。従って、Ｇの中心の元素の個数は、２ｐになることが分かる。また、中心でｍとｇとを選択する確率は、２ｐ／ｐ３＝１／ｐ２≒０、２ｐ／ｐ４＝２／ｐ３≒０であることに注目すべきである。また、ｍは、Ｇの部分群であるＳＬ（２、Ｚｐ）から選択する。
【００４５】
上記数式（４）により非可換群Ｇが生成されると、ＳＬ（２、Ｚｐ）の生成源の集合は、｛Ｔ、Ｓ｝になる。これを表現すれば次の通りである。
【数２０】
2004534971.tif 000022
【００４６】
そして、ここには、ＳＬ（２、Ｚｐ）の元素（ｇ∈ＳＬ（２、Ｚｐ））の各々の分解（decomposition）を知ることができるアルゴリズムが存在する。即ち、ＳＬ（２、Ｚｐ）の任意の元素ｇは、下記の数式（１０）により計算される。
【数２１】
2004534971.tif 000023
【００４７】
ここで、ｉ０、ｉｎ＋１は、０又は１であり、ｊｎ＝±１、±２・・・である。
【００４８】
もしｍ∈ＳＬ（２、Ｚｐ）ならば、ｍは、下記の数式（１１）により表現することができる（以下では「第１定理」という）。
【数２２】
2004534971.tif 000024
【００４９】
これを証明するために、
【数２３】
2004534971.tif 000025
【００５０】
を計算すれば、下記の数式（１２）を得ることができる。
【数２４】
2004534971.tif 000026
【００５１】
上記数式（１２）及びＺｐが体（field）であるという事実から、ある与えられたｍ∈ＳＬ（２、Ｚｐ）に対して
【数２５】
2004534971.tif 000027
【００５２】
を満足するj1, j2, j3 を求めることができる。即ち、上記３つの値 j1, j2, j3 が決定されれば、ＳＬ（２、Ｚｐ）の総ての元素が決定される。
【００５３】
｛（Ｔ、０）、（Ｓ、０）、（Ｉ、０）｝がＧの生成源の集合であるから、ｇＴｇ−１、ｇＳｇ−１及びｇ（Ｉ、１）ｇ−１が既知であれば、Ｉｎｎ（ｇ）を求めることができる。また、ｍ∈ＳＬ（２、Ｚｐ）であり、ＳＬ（２、Ｚｐ）がＧの正規部分群（normal subgroup）であるから、Ｉｎｎ（ｇ）は、ＳＬ（２、Ｚｐ）に制限（restriction）して考えることができ、Ｉｎｎ（ｇ）｜ＳＬ（２、Ｚｐ）は、ＳＬ（２、Ｚｐ）の自己同型写像（automorphism）となる。即ち、公開鍵は、Ｉｎｎ（ｇ）｜ＳＬ（２、Ｚｐ）とＩｎｎ（ｇａ）｜ＳＬ（２、Ｚｐ）となる。従って、｛ｇＴｇ−１、ｇＳｇ−１｝が既知であれば、Ｉｎｎ（ｇ）｜ＳＬ（２、Ｚｐ）を表現することができる。
【００５４】
位数がｐであるＳＬ（２、Ｚｐ）の元素のうち、例えば、Ｉ＋δ１２が
【数２６】
2004534971.tif 000028
【００５５】
に選択される。
【００５６】
また、上記Ｉｎｎ（ｇ）で非可換群Ｇの元素ｇを選択する方法は、次の通りである。
【００５７】
（ｘ、ｙ）∈Ｇである条件に対して、
【数２７】
2004534971.tif 000029
【００５８】
となる（以下では「第２定理」という）。これを証明するために、帰納法及び下記の数式（１３）を利用する。
【数２８】
2004534971.tif 000030
【００５９】
ここで、
【数２９】
2004534971.tif 000031
【００６０】
をある固定されたｃ∈ＺｐとＡ∈ＳＬ（２、Ｚｐ）に対して
【数３０】
2004534971.tif 000032
【００６１】
になるように定めると、位数がｐであるｇを選択でき、上記第２定理によりＩｎｎ（ｇ）の位数がｐであることを知ることができる。もし、無作為にｇを選択し、ｇの位数が固定されていなければ、離散対数問題に対する周知のアルゴリズムを適用するために、与えられた巡回群（cyclic group）の位数を知らなければならないので、安全性を増加させることができる。即ち、ｄ｜（ｐ＋１）（ｐ−１）各々に対してｇの位数がｐであるという仮定下に、離散対数問題を解かなければならない。
【００６２】
上述した本発明は、Ｉｎｎ（ｇ）から離散対数問題を解決できないため、安全性が維持されるが、これを詳細に説明すれば、次の通りである。
【００６３】
公開鍵Ｉｎｎ（ｇ）及びＩｎｎ（ｇ）ａから離散対数問題を解き、秘密鍵ａを得る場合、離散対数問題を解くための最も早いアルゴリズム（例えば、指数計算法）は適用されることができない。従って、ｇの位数がｐならば、離散対数問題を解決するに要する予想実行時間（run time）がＯ（ｐ）１／２−群演算（operations）になる。
【００６４】
また、秘密鍵を求める他の方法は、次の通りである。Ｇでの特殊な共役演算子問題（special conjugacy problem）は、難しい問題でなく、Ｇでの離散対数問題も下記の数式（１４）から明らかなように難しくない。
【数３１】
2004534971.tif 000033
【００６５】
ｇ及びｇａに対する離散対数問題を解くためには、ａｙ＝Ｙを解くことが必要である。しかし、Ｉｎｎ（ｇａ）だけが与えられた場合、Ｓ＝｛ｇ１｜Ｉｎｎ（ｇ１）＝Ｉｎｎ（ｇａ）｝の元素の個数は、２ｐであるから、Ｓからｇａを求めるためには、Ｏ（ｐ）回の試みが必要である。従って、この方法は、Ｉｎｎ（ｇ）及びＩｎｎ（ｇａ）から直接ａを求めることより非効率的であることが分かる。
【００６６】
１６０ビット素数ｐを選択すれば、本発明の安全性は、１０２４ビットＲＳＡと類似になる（即ち、Ｉｎｎ（ｇ）で離散対数問題を解き、１０２４ビットＲＳＡを因数分解するに要する予想実行時間は各々約２８７及び２８０になる）。また、Ｉｎｎ（ｇ）は、Ａｕｔ（Ｇ）⊂Ｅｎｄ（Ｇ）⊂ＧＧに含まれ、ここで、Ｅｎｄ（Ｇ）は、Ｇの自己準同型（ｅｎｄｏｍｏｒｐｈｉｓｍ）群であり、ＧＧは、ＧからＧまでの総ての関数の集合である。これらは、甚だしくは、行列群でも表現されないため、これらのいずれにも指数計算法を適用できない。
【００６７】
ここで、本発明をＲＳＡ及びＸＴＲと比較すると、次のような利点があることが分かる。即ち、ＲＳＡ及びＸＴＲで公開鍵から秘密鍵を探すために必要とする予想実行時間は、準指数時間であるのに対し、本発明では、指数実行時間Ｏ（ｐ）１／２が必要である。
【００６８】
ここで、Ｉｎｎ（ｇ）からＩｎｎ（ｇｂ）を計算する方法を説明する。Ｉｎｎ（ｇ２）の計算は、下記の数式（１５）及び数式（１６）に示される通りである。
【数３２】
2004534971.tif 000034
【数３３】
2004534971.tif 000035
【００６９】
また、４回の乗算を用いて下記の数式（１７）によりＩｎｎ（ｇ）（Ｔ）から（Ｉｎｎ（ｇ）（Ｔ））ｊを得ることができる。
【数３４】
2004534971.tif 000036
【００７０】
となる。
【００７１】
従って、Ｉｎｎ（ｇ２）（Ｓ）及びＩｎｎ（ｇ２）（Ｔ）を計算するためには、９２の乗算が必要である。従って、Ｉｎｎ（ｇ）からＩｎｎ（ｇｂ）を計算するためには、約９２ｌｏｇ２ｐの乗算が必要であり、Ｉｎｎ（ｇａ）からＩｎｎ（ｇａｂ）を計算するためには、９２ｌｏｇ２ｐの乗算が必要である。従って、暗号化のための乗算の数は、約１８４ｌｏｇ２ｐとなる。１つの乗算が０（（ｌｏｇ２ｐ）２）ビット演算を必要とするので、暗号化は、ある定数ｃに対して約１８４（ｌｏｇ２ｐ）３Ｃ≒８×１０８Ｃビットの演算を必要とする。１０２４ビットＲＳＡでは、（ｌｏｇ２ｎ）３Ｃ≒（１０２４）３Ｃ≒１０９Ｃビットの演算が必要である。ＲＳＡ暗号化設計で、公開指数が３２ビットになれば、３．２×１０７Ｃビット演算が必要である。
【００７２】
本発明によれば、高速の暗号化及び復号化が可能なように変形が可能であるが、これを詳細に説明すれば、次の通りである。
【００７３】
例えば、「甲」が「乙」に暗号化したメッセージを送ろうとする場合、「甲」は、最初の通信時だけにＩｎｎ（ｇａ）ｂとＩｎｎ（ｇｂ）を計算して、Ｉｎｎ（ｇｂ）を「乙」に送る。「乙」は、受信したＩｎｎ（ｇｂ）を用いてＩｎｎ（ｇｂ）−ａを計算する。「甲」は、メッセージｍを最初の通信後に固定されたｂに対して暗号文Ｅ＝Ｉｎｎ（ｇａ）ｂ（ｍ）で暗号化した後、上記暗号文Ｅを「乙」に送る。「乙」はＩｎｎ（ｇｂ）−ａ（Ｅ）を計算することによってＥを復号化できる。
【００７４】
即ち、与えられたＩｎｎ（ｇａ）ｂとｍからＩｎｎ（ｇａ）ｂ（ｍ）を計算するために、４６回の乗算が必要なので、暗号化に約１．２×１０６Ｃビットの演算が必要である。３２ビット公開指数がＲＳＡに使われても、暗号化に３.２×１０７Ｃビットの演算が必要である。本発明により暗号化を行うと、１０２４ビットＲＳＡより約３０倍程度早い暗号化がなされる。
【００７５】
また、復号化のためには、暗号化するために必要な分の乗算が必要である。ＲＳＡの復号化に際して、「中国余剰定理」（‘Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｏｒｅｍ’）を適用しても、約２．５×１０８Ｃビットの演算が必要である。従って、本発明の復号化は、ＲＳＡの解読より２００倍速い。
【００７６】
ＥＣＣでは、ｂが固定されてはならないため、ｇｂの事前計算が不可能になる。従って、１７０ビットＥＣＣでの復号化のための乗算の数は、各々１９００になる。従って、ＥＣＣより約４０倍程度速い復号化速度を有する。
【００７７】
また、ＥＣＣでは、復号化にＯ（ｌｏｇ２ｐ）の乗算が必要なので、乗算の数は、ビットｌｏｇ２ｐの個数に比べて線形的に増加するであろう。これに対し、本発明の復号化には、ｐのサイズとは関係なく４６回の乗算が必要である。下記の表１は、本発明及びＥＣＣの復号化に要する乗算の数を比較したデータである。
【表１】
2004534971.tif 000037
【００７８】
上記表で、同じ行での暗号システムは、略同じ安全性を有する。
【００７９】
本発明は、鍵の表現及び鍵のサイズにおいて、Ｉｎｎ（ｇａ）（Ｔ）とＩｎｎ（ｇａ）（Ｓ）は、ＳＬ（２、Ｚｐ）の元素として見なされ得るため、各々を３つの項により表現できる。Ｉｎｎ（ｇａ）（Ｔ）が３ｌｏｇ２ｐビットで表現されるので、Ｉｎｎ（ｇａ）を表現するためには、６ｌｏｇ２ｐビットが必要である。ｐが１６０ビット素数である場合、Ｉｎｎ（ｇａ）を表現するためには、９６０ビットが必要である。従って、公開鍵は、ＲＳＡより小さいサイズで表現され得る。秘密鍵のサイズは、ｌｏｇ２ｐ≒１６０ビットであるから、１０２４ビットＲＳＡよりかなり小さくなる。
【００８０】
上述したように、本発明は、有限非可換群を用いた新しい公開鍵暗号システムを提供し、上記暗号化方式に使用され得る有限非可換群の一例を提示する。上記のような暗号化方式は、有限非可換群にのみ限定されるものでなく、他の非可換群を利用する場合にも適用されることができる。しかし、暗号化の安全性のためには、非可換群を選択することに注意すべきである。
【００８１】
即ち、中心でない可換正規部分群の存在は、安全性を減少させる。従って、任意の可換正規部分群は小さくなければならないし、Ｇの元素を生成源の積により表現するアルゴリズムは、効率的でなければならない。また、Ｉｎｎ（ｇ）は、｛Ｉｎｎ（ｇ）（ｅｉ）∈Ｇ｜ｅｉは生成源｝により表現されるので、生成源の個数が小さくなければならない。また、内部自己同型写像の代わりに、ＧからＡｕｔ（Ｇ）までの他の準同型写像を使用することができる。
【００８２】
一方、上述した公開鍵暗号システムは、電子署名、鍵交換などいろいろな分野に適用することができる。上記公開鍵暗号システムを用いた電子署名及び鍵交換方式を説明すると、次の通りである。
【００８３】
上記公開鍵暗号システムを用いた電子署名方式は、図３及び図４に図示されている。例えば、「甲」が「乙」に平文Ｍを伝送しながら電子署名をすると仮定する。上記電子署名方式は、図１で説明された段階を通じて生成された公開鍵Ｉｎｎ（ｇ）、Ｉｎｎ（ｇａ）及び秘密鍵ａを用いて行われるが、その署名過程は、図３に示す通りである。「甲」は、乱数ｂ（任意の整数から無作為に抽出された整数）を選択した後（ステップＳ３１）、上記乱数ｂを用いてＩｎｎ（ｇｂ）を計算する（ステップＳ３２）。上記Ｉｎｎ（ｇｂ）を用いて対称鍵Ｋを生成し（ステップＳ３３）、上記対称鍵Ｋを用いて付加文を含む平文（メッセージ）Ｍを暗号化して暗号文Ｅを求める（ステップＳ３４）。
【００８４】
その後、上記暗号文Ｅを用いてハッシュ関数ｈ＝ｈ（Ｅ）を計算し（ステップＳ３５）、電子署名ｓは、下記の数式（１８）により計算される（ステップＳ３６）。
【数３５】
2004534971.tif 000038
【００８５】
「甲」は、上記暗号文Ｅと電子署名ｓを「乙」に伝送する。
【００８６】
上述したような電子署名の確認過程は、図４に示す通りである。「乙」は、伝送された電子署名ｓが０≦ｓ＜ｐの範囲内に存在するか否かを確認する（ステップＳ４１）。「甲」は、ハッシュ関数ｈ＝ｈ（Ｅ）を計算した後（ステップＳ４２）、Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ）を計算する（ステップＳ４３）。その後、上記Ｉｎｎ（ｇｓ）Ｉｎｎ（ｇ−ｈａ）を用いて対称鍵Ｋを復旧した後（ステップＳ４４）、上記対称鍵Ｋを用いて暗号化された付加文を含む暗号文Ｅを復号化して、上記付加文が適切か否かを確認し、正しい署名なのか否かを確認する（ステップＳ４５及びステップＳ４６）。上記署名が正しい場合、平文（メッセージ）Ｍを正しいメッセージとして受け入れる。
【００８７】
上記電子署名方式で、対称鍵Ｋの代わりに、Ｉｎｎ（ｇａｂ）（ｍ）で暗号化してもよい。これにより、乱数ｂを固定して使用しても、暗号化及び復号化時と同様に、安全性には問題がない。
【００８８】
上記公開鍵暗号システムを用いた鍵交換方式は、図５に図示されている。例えば、「甲」と「乙」が互いに鍵を交換する場合、上記鍵交換方式は、図１で説明された段階を通じて生成された公開鍵Ｉｎｎ（ｇ）を用いて行われるが、その鍵交換過程は、図５に示す通りである。
【００８９】
「甲」は、乱数ａを選択した後（ステップＳ５１）、上記乱数ａを用いてＩｎｎ（ｇａ）を計算する（ステップＳ５２）。その後、「甲」は、Ｉｎｎ（ｇａ）を「乙」に伝送する。「乙」は、乱数ｂを選択した後（ステップＳ５３）、上記乱数ｂを用いてＩｎｎ（ｇａｂ）を計算し（ステップＳ５４）、上記Ｉｎｎ（ｇａｂ）を用いて対称鍵Ｋを生成する（ステップＳ５５）。
【００９０】
その後、「乙」は、Ｉｎｎ（ｇｂ）を計算して「甲」に伝送し（ステップＳ５６）、「乙」は、Ｉｎｎ（ｇｂ）及び乱数ａを用いてＩｎｎ（ｇａｂ）を計算する（ステップＳ５７）。その後、「甲」は、Ｉｎｎ（ｇａｂ）から対称鍵Ｋを求める（ステップＳ５８）。
【００９１】
上記で説明した暗号システムは、次のように一般化することができる。上記で内部自己同型写像群を使用した理由は、一般的に自己同型写像群を知ることは容易でないが、部分群である内部自己同型写像群は容易に知ることができるからである。しかし、ある群の自己同型写像の他の部分群を知ることができれば、上記暗号システムの一般化を図ることができる。これを詳細に説明すると、次の通りである。群Ｇ及びＧ′に対して準同型写像Ф：Ｇ→Ａｕｔ（Ｇ′）が与えられたとき、Ф（Ｇ）での離散対数問題を利用した暗号システムを、Ｉｎｎ（Ｇ）での離散対数問題を利用した上記暗号システムと同じ方法で作る。即ち、上記で使われたＩｎｎの代わりに、Фをそのまま適用する。この場合、メッセージｍは、Ｇ′から選択され、Ｅ＝Ф（ｇ）ａｂ（ｍ）になる。内部自己同型写像群Ｉｎｎ（Ｇ）を使用した場合、安全性が、Ｋｅｒ（Ｉｎｎ）である中心のサイズと密接な関連があったことと同様に、この場合にも、安全性は、Ｋｅｒ（Ф）のサイズと密接な関係がある。
【００９２】
上記の一般化した暗号システムは、エルガマル暗号を含む大きなシステムである。エルガマル方式は、Ｇ＝Ｇ′＝Ｚｐのとき、上記の特殊な場合である。詳細に説明すれば、次の通りである。
【数３６】
2004534971.tif 000039
【００９３】
であるとき、
【数３７】
2004534971.tif 000040
【００９４】
を作ることができる。ここで、αの
【数３８】
2004534971.tif 000041
【００９５】
での位数を｜α｜とする。
【数３９】
2004534971.tif 000042
【００９６】
を満足するｓ、ｔに対して
【数４０】
2004534971.tif 000043
【００９７】
である同型写像を定義することができ、これから、可解群（solvable group）
【数４１】
2004534971.tif 000044
【００９８】
を作ることができる。このように定義されたＧに対してＩｎｎ（Ｇ）での離散対数を用いた基本的なシステムは、可換正規群の存在に起因して弱点を有する。しかし、
【数４２】
2004534971.tif 000045
【００９９】
とし、上記の一般化したシステムを使用すれば、弱点を補完することができる。
【０１００】
また、Ｇの特殊な共役演算問題を解くと、任意のＩｎｎ（Ｇ）の元素を生成源の積で容易に表現することができる。｜ｔ｜と｜ｓ｜を十分に小さく取れば、Ｇの特殊な共役演算問題を容易に解くことができるので、任意の元素を生成源の積で容易に表現することができる。また、ｒ１＝｜α｜であるとき、ｌｃｍ（ｍ／ｔ−ｌ、ｒ１）＞＞ｍ／ｔ−ｌであるｒ１、ｍ、ｔを選択する。
【図面の簡単な説明】
【０１０１】
【図１】本発明による有限非可換群を用いた公開鍵の生成方法を説明するためのフローチャートである。
【図２】図１に示された公開鍵を用いてメッセージを暗号化及び復号化する方法を説明するためのフローチャートである。
【図３】図１に示された公開鍵を用いた電子署名方法を説明するためのフローチャートである。
【図４】図１に示された公開鍵を用いた電子署名確認方法を説明するためのフローチャートである。
【図５】図１に示された公開鍵を用いた鍵交換方法を説明するためのフローチャートである。
【図１】
2004534971.tif 000065
【図２】
2004534971.tif 000066
【図３】
2004534971.tif 000067
【図４】
2004534971.tif 000068
【図５】
2004534971.tif 000069
【国際公開パンフレット】
2004534971.tif 000070
2004534971.tif 000071
2004534971.tif 000072
2004534971.tif 000073
2004534971.tif 000074
2004534971.tif 000075
2004534971.tif 000076
2004534971.tif 000077
2004534971.tif 000078
2004534971.tif 000079
2004534971.tif 000080
2004534971.tif 000081
2004534971.tif 000082
2004534971.tif 000083
2004534971.tif 000084
2004534971.tif 000085
2004534971.tif 000086
2004534971.tif 000087
2004534971.tif 000088
2004534971.tif 000089
2004534971.tif 000090
2004534971.tif 000091
2004534971.tif 000092
2004534971.tif 000093
2004534971.tif 000094
2004534971.tif 000095
2004534971.tif 000096
2004534971.tif 000097
【国際調査報告】
2004534971.tif 000098
2004534971.tif 000099