Research

過去５回の学会発表の及び論文の概要です。うーんよく頑張ったもんだ…

タイトル	発表・提出年月日	学会名
IDに基づく暗号方式の評価に関する研究	1997 年 2 月 提出	卒業論文
特殊な素数の分布に関する 2, 3 の考察	1997 年 7 月 発表	情報理論研究会
素数生成に関する考察	1997 年 12 月 発表	第 20 回情報理論とその応用シンポジウム
P-1 法に強い合成数の提案	1998 年 1 月 発表	暗号と情報セキュリティシンポシウム
素因数分解に強い素数の生成法に関する 二，三 の考察	1998 年 7 月 発表	情報セキュリティ研究会
２、３の IDーNIKS の安全性に関する考察	1998 年 7 月 第２著者	情報セキュリティ研究会
P±１ 法に強い素数の効率的生成法	1998 年 12 月 発表	第 21 回情報理論とその応用シンポジウム
New Methods of Generating Primes Strong Against P-1 Method and P+1 Method	1999 年度論文誌採録予定	SITA 英文論文
暗号システムに用いる素数の応用に関する研究	1999年 2 月	修士論文
高速素数生成法の提案	1999年 3 月	研究速報

IDに基づく暗号方式の評価に関する研究

卒業論文 (1997 年 2 月 提出)
FMK-NIKS に用いる特殊な素数を中心に, それに類似した素数に ついて調査を行う. まず, 2pq+1 ( PP 素数) の形の素数が十分多く存在することを確認する ために, 1〜28 [bit]の範囲で全数探索を行う. p, q を 32〜128 [bit]の範囲でランダムに発生させた場合に 2pq+1 が素数になる確率を調査し, 分布を推測する. また, 2pq+1 に類似したタイプのものとして, 2AB+1 の素数について, A が奇数, B が素数のもの( OP 素数)と, A, Bが共に奇数のもの( OO 素数) , そして Sophie Germain 素数 (2p+1 の形をした素数)についても分布を調べる. それぞれの結果を, 同程度の大きさの奇数をランダムに 発生した場合の素数の出現確率と比較すると, OP 素数の出現率はラン ダムに発生した場合に等しく, OO 素数 はそれより 30% 程 多く, SG 素数と PP 素数はいずれも 35% 前後少ない確率を示すことを が判明した. 理論的に予測値を導出してこの結果と比較し, 実験値と一致する ことを確認した.
表へ


特殊な素数の分布に関する 2, 3 の考察

情報理論研究会 IT (1997 年 7 月 発表)
現代暗号では,素因数分解問題や離散対数問題を利用したものが多く, 素数に関する研究が重要である. ここでは, Sophie Germain 素数に代表される ２Π Pi + 1 (P_i は素数) の形の P-1 法に強い素数の存在確率について考察を行い, この形の素数が一般の素数に対して0.660 程度の比率で存在することを数学的に導出した. 更に実際に計算機で数値実験を行い, P-1 法に強い素数の出現確率と今回導出した理論値が一致することを 実証した.
表へ



素数生成に関する考察

第 20 回情報理論とその応用シンポジウム SITA(1997 年 12 月 発表)
前回の研究で特殊な素数の分布を調査したが, ここではその際理論の導出に用いた 発想を応用して効率的に素数を生成する手法を提案した. 具体的には素数候補が小さな素数で割り切れないように工夫することによって, 素数を生成し, 従来の生成法と比べて約 5 倍の素数生成率を実現した. 更に, 暗号に使用する場合を念頭に置いて, 実用に十分使用可能であることを 素因数分解による強度の調査と素数の多様性を調べることで実証した.
表へ



P-1 法に強い合成数の提案

暗号と情報セキュリティシンポシウム SCIS(1998 年 1 月 発表)
有効な素因数分解法の一つに P-1 法があげられるが, 従来より P-1 法に強い素数に対する 考察は行なわれているものの, 合成数に着目した 考察はほとんど行なわれていない. ここでは, まず, P-1 法について考察し, P-1 法に対する合成数の強度を 定量的に評価できる強度指標を提案した. 更に, 従来 P-1 法に対する評価は素数についてのみ行われてきたにのに対し, 新たに合成数に着目して 3 つのタイプの P-1 法に強い合成数を提案し, 強度の検討を行った.
表へ



素因数分解に強い素数の生成法に関する 二，三 の考察

情報セキュリティ研究会 ISEC(1998 年 7 月 発表)
これまでに行ってきた素数の分布及び効率的素数生成法に関する 研究について 素数の分布と素数の生成確率の相関について考察を 行う. また, P-1 法 と P+1 法 の 2 つの素因数分解法の両方に 同時に強化する手法は従来考えられていなかったが, 双子素数を利用することでこの両者に強い素数を生成可能である ことを示し, さらにその素数は効率的に生成することが可能である ことを理論および数値実験の両方で証明する.
表へ


２、３の IDーNIKS の安全性に関する考察

情報セキュリティ研究会 ISEC(1998 年 7 月 第２著者)
安全かつ簡単な ID 情報に基づく予備通信不要な鍵共有方式(ID-NIKS) の実現は、理論および実用の両方の観点から、非常に重要な問題である. 本稿では、安全な IDーNIKS に必要な条件を提示し、 一般的な立場から IDーNIKS に対する攻撃法について考察. 次に代表的な IDーNIKS である冪積型 IDーNIKS に対する攻撃法を 示し、最後に提案された ２、３の IDーNIKS に対して実際に攻撃を 行う.
表へ


P±１ 法に強い素数の効率的生成法

第 21 回情報理論とその応用シンポジウム SITA(1998 年 12 月 発表)
P±１法 双方に最も強い素数 (最強素数) 及びそれに準ずる強度を持つ素数(準強素数)についてその存在確率を ゼータ関数による近似を用いて巧妙に算出する手法を 考案し、その手法による算出結果が適切な数値を示すことを数値実験により検証。 また、素数生成の高速化に非常に有効である 試行割算を応用することにより，最強素数及び強素数を 効率的に生成する手法を提案する．
(＊ 尚、この研究内容で企業から 特許をとっていただくことになりました。)
表へ


New Methods of Generating Primes Strong Against P-1 Method and P+1 Method

SITA 英文論文(1999 年度論文誌採録予定)
Security of many modern cryptosystems are based on the difficulty of factoring problem or discrete logarithm problem. It is important to research about primes sufficiently because these problems need laege primes. Before we researched on the distribution of Sophie Germain prime and twin primes, sugest a few generating prime method and make it strong against factoring problem by availing special primes On the other hand, trial division method is well known as efficient generating prime method. But most of primes by the method is vulnerable for P-1 method and P+1 method. In this paper, first, we consider the distribution of secure primes against P-1 and P+1 method. Second, we apply trial division method and suggest a new prime-generating algorithm, which is able to generate secure primes against P-1 and P+1 method effectively.
表へ


高速素数生成法の提案

1999年度研究速報 採録予定
本稿では，過去の学会発表の効率的素数生成の部分を抜粋し、 体系的に理論を構築する。 高速生成の理論は SITA20、ISEC の理論と同様であり、 素数候補の生成法により効率化を計る。
表へ


暗号システムに用いる素数の応用に関する研究

修士論文 提出(1999年 2 月)
現代暗号の多くは，素因数分解問題や離散対数問題に安全性の根拠 を置いている．これらの問題においては大きな素数が重要な役割を 演じるため，素数に関する研究が十分に行われる必要がある．本論 文では素数の分布の調査及び効率的素数生成法について考察を行う． 本論文ではまず，暗号システムや素数生成に応用される特殊な素数 として双子素数及び Sophie Germain について，理論的に存在確率を 導出し，数値実験により分布を調査する． 次に， P-1 法 と P+1 法に最も強い形状の素数について新たに定義を与え，理論及び数値 実験により分布を調査する． 更に効率的素数生成法として，高確率で素数となる素数候補を生成する 手法及び，試行割算を拡張して無駄な素数判定回数を減らす手法を 提案し，数値実験により有効性を検証する．
表へ