## 非可換群に基づく公開鍵暗号

## 寺澤  善博（ Kryptism ）

概要 1999 年、当時 16 歳の高校生だった少女セアラ・フラナリーによって行列を用いた公開鍵暗号が考案され、一時 RSA 暗号をもしのぐ強度を持つのではないかとうわさされ、日本でも本が出版され話題になった。しかし、フラナリーの論文が公 開される前に攻撃法が見つかり新型暗号発見のニュースは消えた。本稿では、同じ非可換群である置換群から暗号化関数を構 成し、実装を通してこの暗号系の可能性を探る。

## 0. 動機

新しい暗号を巡る動きは後を絶たない。日本では 著名なセキュリティ会社がほかの企業に合併吸収 される中、 暗号化ビジネスはセキュリティブームを 追い風に大きくなり、市場規模を増しているという のがイメージである。日本でも暗号の研究がおろそ かになったわけではないようだ。年に何回か最新の 暗号方式がどのくらいの時間で解かれたという報 告があるし、研究発表会も盛んに行われている。そ して何より、新しい暗号化方式が外注されずにメー カーやキャリアの独自、 ないしは共同開発という形 で行われていることだ。 これは市場規模とは関係な しに、 企業内で開発圧力が存在することを意味する。 暗号が提供できる機能が同じなら、 なぜ新しい方式 を開発する必要があるのだろうか？それは純粋に 研究者の楽しみである以外に実用的な要請でもあ る。まず既存の暗号方式のうち、数論的計算問題に 基づく方式は量子計算機によりいずれ破られる運 命にあるということ。これはすばわちさまざまな種 類の計算問題から多様な暗号系が構成でき、 実用的 なシステムとして選択可能であることを求められ ていることを意味している。そして計算機の性能が 上がるにつれ、暗号化処理時間は、増大する鍵サイ ズに引きずられる形で増しているということ。この ことは、次世代の暗号を設計する一つの指針を示し ているように思われる。 量子計算機にも攻撃不可能 で、鍵の大きさに暗号化に要する全体の処理速度が 影響されないような暗号系。設計の指針としては、

まず大きな数を使わずベクトルのような小さな数 を使って暗号化することである。現在の候補として は、NTRUなど格子暗号があげられるが、今回は他の 可能性として置換群を用いた公開鍵暗号を示す。

## 1. 対称群

対称群とは、ｎ個の要素が入った配列の要素の位 置を入れ替えるという操作を演算に持つ群のこと である。一般に、ｎ個の要素を扱う対称群を Sn と 書きｎ次の置換群という。

## 2. 対称群上の計算問題

CP アルゴリズムに置換群を適用することを考え る。置換群の積は自明である。ここで置換群の離散 対数問題を考える。しかしながら、置換群の離散対 数問題は容易に解けることがわかる。

そこで、ランダムビットパターンとして適度なさ を持つ乱数をとり、それを2つの群の言で表すこと を考える。すると、2つの元をそれぞれ０と１に割 り当てることで新たな群の元を計算できる。2つの 元に対して、それとは異なる3つ目の元を取り、そ れを秘密として群の共益問題を考える。 此処で共役 元とはｘを秘密にしｙが公開されているとして、z =xyx^-1を計算すると、ｚとｙからｘを計算する問 題である。

## 3. 暗号および認証系

## ・暗号系その 1

（公開鍵） （秘密鍵）

鍵生成  置換 D=A^aXA^-a,X,A ,a 暗号化 C=A^rD^mA^-r 、 E=A^rXA^-r

復号化 A^aEA^-a=A^r+aXA^-(a+r)=C^-m と C より、サイ クルに関する 1 元連立一次合同式を解いて、秘密指数ｍ を得る。

## ・暗号系その 2

鍵生成 X を秘密鍵とし、 A,B,C=XAX^-1,D=XBX^-1 を公 開鍵とする。

暗号化 256 ビットランダムパターン R を A と B を用い て表したものを T,C と D を用いて表したものを U としｍ を暗号化すると、暗号文はｍ となる。ここで、 （ U T,mU ） を相手に送信する。

## 復号化

## XTX^-1=U

ｍ U*U^-1=

より、 ｍとして、任意のベクトルを得る。

## ４ 考察

この暗号化法は、置換群の離散対数問題と、共役 元の計算困難な問題の難しさを安全性の基礎にお いている。

この時のシステムパラメータは、公開鍵が2048 ビットである。この方式で暗号化できる平文のサイ ズは64*32ビットである。

メッセージ膨張率が小さく、鍵サイズも小さな公 開鍵暗号系の構成は難しいかもしれない。

## 寺澤 善博 （非会員） hgenko@ipsj.or.jp

1996 年  電気通信大学大学院情報工学科卒業、 1999 年電気通信大学大学院博士前期課程情報工学専攻卒業、 フリーのエンジニア。暗号技術を用いたオンライプライ バシー保護に関心がある。

## 参考文献

1) 小林雅人（著） あみだくじの数学 共立出版 : , (2011). 2) セアラの暗号 , http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/cp.pdf 3) 16 歳のセアラが挑んだ世界最強の暗号
Yoshihiro Terasawa
Publickey encryption by ordering
In 1999, public key cryptography using the matrix was devised by a hish
school student of 16 yesrs old girl Sarah Flannery. This cryptosystem seemed
faster than RSA, and it's having the strength to surpass even the encryption to
RSA. However, this encryption scheme was broken bfore har papers were
published. In this paper, We try to construct publickey encryption scheme from
permutation group that is equivalent to matrix as noncommutative group. And we
explore the potential of this cryptsystem through implementation.