0. 動機
新しい暗号を巡る動きは後を絶たない。日本では
著名なセキュリティ会社がほかの企業に合併吸収
される中、暗号化ビジネスはセキュリティブームを
追い風に大きくなり、市場規模を増しているという
のがイメージである。日本でも暗号の研究がおろそ
かになったわけではないようだ。年に何回か最新の
暗号方式がどのくらいの時間で解かれたという報
告があるし、研究発表会も盛んに行われている。そ
して何より、新しい暗号化方式が外注されずにメー
カーやキャリアの独自、ないしは共同開発という形
で行われていることだ。これは市場規模とは関係な
しに、企業内で開発圧力が存在することを意味する。
暗号が提供できる機能が同じなら、なぜ新しい方式
を開発する必要があるのだろうか？それは純粋に
研究者の楽しみである以外に実用的な要請でもあ
る。まず既存の暗号方式のうち、数論的計算問題に
基づく方式は量子計算機によりいずれ破られる運
命にあるということ。これはすばわちさまざまな種
類の計算問題から多様な暗号系が構成でき、実用的
なシステムとして選択可能であることを求められ
ていることを意味している。そして計算機の性能が
上がるにつれ、暗号化処理時間は、増大する鍵サイ
ズに引きずられる形で増しているということ。この
ことは、次世代の暗号を設計する一つの指針を示し
ているように思われる。量子計算機にも攻撃不可能
で、鍵の大きさに暗号化に要する全体の処理速度が
影響されないような暗号系。設計の指針としては、
まず大きな数を使わずベクトルのような小さな数
を使って暗号化することである。現在の候補として
は、NTRUなど格子暗号があげられるが、今回は他の
可能性として置換群を用いた公開鍵暗号を示す。
1. 対称群
対称群とは、ｎ個の要素が入った配列の要素の位
置を入れ替えるという操作を演算に持つ群のこと
である。一般に、ｎ個の要素を扱う対称群を Sn と
書きｎ次の置換群という。
2. 対称群上の計算問題
CP アルゴリズムに置換群を適用することを考え
る。置換群の積は自明である。ここで置換群の離散
対数問題を考える。しかしながら、置換群の離散対
数問題は容易に解けることがわかる。
そこで、ランダムビットパターンとして適度なさ
を持つ乱数をとり、それを2つの群の言で表すこと
を考える。すると、2つの元をそれぞれ０と１に割
り当てることで新たな群の元を計算できる。2つの
元に対して、それとは異なる3つ目の元を取り、そ
れを秘密として群の共益問題を考える。此処で共役
元とはｘを秘密にしｙが公開されているとして、z
=xyx^-1を計算すると、ｚとｙからｘを計算する問
題である。
非可換群に基づく公開鍵暗号
寺澤 善博（Kryptism）
概要 1999 年、当時 16 歳の高校生だった少女セアラ・フラナリーによって行列を用いた公開鍵暗号が考案され、一時 RSA
暗号をもしのぐ強度を持つのではないかとうわさされ、日本でも本が出版され話題になった。しかし、フラナリーの論文が公
開される前に攻撃法が見つかり新型暗号発見のニュースは消えた。本稿では、同じ非可換群である置換群から暗号化関数を構
成し、実装を通してこの暗号系の可能性を探る。
2
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ビットである。
メッセージ膨張率が小さく、鍵サイズも小さな公
開鍵暗号系の構成は難しいかもしれない。
参考文献
1) 小林雅人（著）: あみだくじの数学, 共立出版 (2011).
2) セアラの暗号,
http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/cp.pdf
3) 16 歳のセアラが挑んだ世界最強の暗号 　

フォローアップ:

★登録無しでコメント可能。今すぐ反映　通常 ｜動画・ツイッター等 ｜htmltag可（熟練者向）
（タグCheck ｜タグに'だけを使っている場合のcheck ｜checkしない）（各説明）

（←ペンネーム新規登録ならチェック）
↓ペンネーム（2023/11/26から必須）

↓パスワード（ペンネームに必須）

（ペンネームとパスワードは初回使用で記録、次回以降にチェック。パスワードはメモすべし。）
↓画像認証
（ 上画像文字を入力）
ルール確認＆失敗対策
画像の URL (任意):

▲上へ　　　　　 ★阿修羅♪ > ペンネーム登録待ち板7掲示板　次へ 　前へ

★阿修羅♪　http://www.asyura2.com/ since 1995
スパムメールの中から見つけ出すためにメールのタイトルには必ず「阿修羅さんへ」と記述してください。
すべてのページの引用、転載、リンクを許可します。確認メールは不要です。引用元リンクを表示してください。