中ボスのページ

	中ボスのページ

名前
メールアドレス
ホームページ

ＲＥＳメール

ＯＮ　ＯＦＦ

削除キー


前へ	1　2　3　4　5　6　7　8　9　10 　11 12	次へ

　[No.94 - 1]　Re: 初
　zinn　2006/02/08 19:42:32

兄貴がキャンセル押しちゃったよ（´Д｀；）
もっかいおねがいします。

削除キー

　[No.93]　指数関数
　J　2006/02/05 01:11:53

\section{指数関数時間}
計算理論において指数関数を用いてあらわされる計算時間であることを指数関数
時間という．一般に指数関数時間やその以上のアルゴリズムは時間がかかりすぎるので実用には適さない．そのようなアルゴリズムは特殊な場合にしか使われない．

\begin{teigi}\label{sisuukansuu}
計算量の問題で指数関数時間のアルゴリズムという場合には，解くべき問題のサ
イズnに対して処理時間が多項式時間では収まらず指数関数的に増加してしまう
計算方法を指す．
ある問題について，その問題を解くためのあるアルゴリズムが計算を終えるまで
の時間が，問題のサイズ $n$ に対して $m(n)$ であったとする．

・$m(n)$ = $Ω(cn)$ を満たす $c > 1$

・$m(n)$ = $O(dn)$ を満たす $d$

この2つが存在するとき，このアルゴリズムは指数関数時間のアルゴリズムであ
るという．
ただし $Ω$ や $O$ は $O$ 記法である．
\end{teigi}

削除キー

　[No.92]　原始元
　J　2006/02/05 01:09:08

\section{原始元}
$y = g^{x}$ mod $P$ の式よりべき乗結果素数 $P$ を法とする世界には，べき
乗された $y$ が 1 から（$P - 1$）の全ての数に変化できる原始元という数字が存在
する．例として $P$ = 11 の場合のべき乗法を表~\ref{genshi}に示した．\cite{riron}

\begin{table}[hhhh]
\begin{center}
\caption{$P = 11$ を法とする場合のべき乗}\label{genshi}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
\multicolumn{2}{|c|}{}&\multicolumn{10}{|c|}{$\bm{x}$}\\\cline{3-12}
\multicolumn{2}{|c|}{}&$\bm1$&$\bm2$&$\bm3$&$\bm4$&$\bm5$&$\bm6$&$\bm7$&$\bm8$&$\bm9$&$\bm1\bm0$\\\hline
&$\bm1$&1&1&1&1&1&1&1&1&1&1\\\cline{2-12}
&\bm{\fbox{2}}&2&4&8&5&10&9&7&3&6&1\\\cline{2-12}
&$\bm3$&3&9&5&4&1&3&9&5&4&1\\\cline{2-12}
&$\bm4$&4&5&9&3&1&4&5&9&3&1\\\cline{2-12}
$\bm{g}$&$\bm5$&5&3&4&9&1&5&3&4&9&1\\\cline{2-12}
&\bm{\fbox{6}}&6&3&7&9&10&4&6&9&8&1\\\cline{2-12}
&\bm{\fbox{7}}&7&5&2&3&10&5&8&4&2&1\\\cline{2-12}
&$\bm8$&8&9&6&4&10&5&8&4&3&1\\\cline{2-12}
&$\bm9$&9&4&3&5&1&9&4&3&5&1\\\cline{2-12}
&$\bm1\bm0$&10&1&10&1&10&1&10&1&10&1\\\hline
\end{tabular}
\end{center}
\end{table}

この場合 $g$ が 2，6，7 のとき，原始元である．

削除キー

　[No.91]　中国
　J　2006/02/05 00:43:26

\section{中国人剰余定理}
与えられた二つの整数 $m_1, m_2$ が互いに素ならば，
任意に与えられる整数 $a$, $b$ に対し，
以下の連立合同式を満たす
整数 $x$ が $m_1m_2$ を法として唯一つ存在する．
\begin{eqnarray}
x &\equiv& a \pmod{m_1} \\
x &\equiv& b \pmod{m_2}
\label{def:chinese}
\end{eqnarray}
\begin{eqnarray}
x &\equiv& c \pmod{m_1m_2}
\end{eqnarray}

削除キー

　[No.90]　じかんくれ
　ともひこ　2006/02/04 15:20:03

kai=(y,P)=
{
y=Mod(y,P);
g=znprimroot(P);
f=factor(P-1);
k=f[1,2];
X=0;
e=1;
sosuu=f[1,1];
G=g^((P-1)/sosuu);
Y1=y^((P-1)/(sosuu^e));
for(i=0,sosuu,
if(Y1==G^i,
a=i;
break;
);
);
H=y/(g^(a*(sosuu^(e-1))));
X1=a;
e=2;
while(e<=k,
Y2=H^((P-1)/(sosuu^e));
for(i=0,sosuu,
if(Y2==G^i,
a=i;
break;
);
);
H=H/(g^(a*(sosuu^(e-1))));
X1=X1+a*(sosuu^(e-1));
e++;
);
return(X1);
}

削除キー

　[No.89]　せっこいっ図
　きっしのひいげ　2006/01/31 15:22:35

%図の挿入方法
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=70mm]{./+1201.eps}
\end{center}
\caption{ログイン画面}
\label{fig:one}
\end{figure}

削除キー

　[No.87]　とまった
　たつたつ　2006/01/27 18:03:26

とまったら死んだ（ノ＿・、）クスン

削除キー

　[No.87 - 1]　Re: とまった
　ともひこ　2006/01/31 11:16:41

なむ

削除キー

　[No.88]　いまさらだけど7/19みて
　ともひこ　2006/01/31 11:16:07

http://ruisama.exblog.jp/m2005-07-01/

削除キー

　[No.86]　Wizとアサシンまだ89
　ともひこ　2006/01/20 13:22:03

{
random(i)= %「i」bitの素数をランダムで選ぶ%
p=nextprime(random(2^(i+1)));
if(p<2^i,
until(p>2^i,p=nextprime(random(2^(i+1)));
);
,p=p;
);
f=factor(p-1); %素因数分解%
s=matsize(f)[1];
pk=f[s,1]; %最大素因数pkをだす%
bit=0; %最大素因数pkのbit数を出す%
until(d==1||d==0,e=j%2; %pkが0か1になるまで2で割っていく%
if(e==1,pk=pk-1;,pk=pk;
); %もし奇数なら1引く%
d=pk/2; %そして2で割っていく%
bit=bit+1; %割った数を足していき最終的にbit数を決める%
pk=d;
);
print(bit);
return(bit);
}

削除キー

　[No.85]　っっっっっっっっっっっゑ
　ぽなが　2006/01/12 19:55:28

\section{ウェーブレット変換( Waveret Transform )}\label{chap:wt}
ウェーブレット理論は1980年代初頭にMorlretが考えた新しい時間周波数解析に
始まるとされている．時間周波数解析とはフーリエ解析のように三角関数の波の
重ね合わせで関数を表現するのではなく，短い波（waveret）の重ね合わせで
関数を表現するというものである．Morlretは改良を加えていった結果，
ひとつの波を拡大縮小して時間周波数解析の，短い波（waveret)に使った．
これがウェーブレット変換の誕生といわれている．ウェーブレット変換は
１変数関数が２変数関数に変換されるので，解析する信号の情報を過剰に含んで
いる．この情報の繰返しによってデータが解析しやすくなったり，
パターンを認識しやすくなる利点がある．本研究では，この変換法を用いた
ウェーブレットツールボックス( Waveret toolbox )を使い前処理を行う．\cite{doc3}

削除キー

　[No.84]　a
　ともひこ　2006/01/05 14:23:04

これまでに提案されている離散対数問題の解を求めるアルゴリズムは，素数 $P$ を法とする乗法群上での離散対数の計算量が，$P - 1$ の最大素因数のサイズに依存するアルゴリズムと，素数 $P$ を法とする乗法群上での離散対数の計算量が $P$ のサイズに依存する指数計算法と呼ばれるアルゴリズムに大別する．前者のアルゴリズムとして代表的に，Shanks，Pohlig–Hellman，Pollard のアルゴリズムなどが知られており，これらの計算量は $P - 1$ における最大素因数のサイズの指数関数時間となる．後者のアルゴリズムとして代表的に，Adleman，Coppersmith，ElGamal，Coppersmith–Odlyzkyo–Schroeppel，Gordon，Schirokauer，Adleman などのアルゴリズムが知られており，これらの計算量は $P$ のサイズに対する準指数関数時間となる．
しかし現地点では，すべての有限体に対して最高速となるアルゴリズムは提案されておらず，適用する有限体に依存して最高速となるアルゴリズムが変わる．そこで本研究では，離散対数問題を法 $P$ による乗法群の要素の個数 $P-1$ における最大素因数が log $P$ 以下の場合において最高速と言われているPohlig–Hellman 法を用いて，大きな法 $P$ の場合でも計算が可能かどうかをPohlig-Hellman法の有効性について評価していく．

削除キー

　[No.83]　ko
　ab　2006/01/05 13:30:32

エニグマ暗号というのは，第二次世界大戦でドイツ軍が使用した暗号シス
テムである．簡単な暗号器で極めて複雑な暗号を作ることができたため，
ドイツ軍の無線通信に使用され，対戦初期の快進撃に貢献した．ドイツ軍
のUボートと呼ばれた潜水艦は，連合国軍の船団に壊滅的ともいえる損害
を与えた．こういった歴史を映しだした，映画”U-571”も有名である．
　今回，比較的小規模なFPGAボードへの実装を試みるため，アルゴリズムが
容易なエニグマ暗号を採用した．

削除キー

　[No.82]　l
　ab　2006/01/05 13:30:11

これまでにLSIを作るとなると莫大な費用を必要とした．しかし，FPG
AやCPLDの登場によりLSIが身近なものになってきている．近年，FPGA技
術は飛躍的に伸び，ASIC（Application Specific IC）にとってかわるま
での勢いを見せている．またプログラミングに用いる言語の開発も進ん
でおり，特にハードウェアの存在を気にすることなく，簡単にFPGAに実装
することができるようになってきている．これらの技術を使いこなすこと
ができれば，自分のアイデアをLSI化することができる時代となってきて
いる．事実，近年インターネット上でも注目を集めており，昔ながらの小
規模PIC（Peripheral Interface）\footnote｛メインのCPUの機能を分散
して，周辺機器の制御を行うために開発されたICのこと．｝マイコンを
使用した基板やプログラムから，FPGA自作基板の回路図など，実にさま
ざまなものが公開されており，これらの技術も身近なものになってきてい
る．

削除キー

　[No.81]　k
　ab　2006/01/05 13:29:52

一方，秘密鍵暗号方式とは暗号化と復号に同じ鍵を用いる暗号方式
である．暗号文の送信者と受信者で同じ鍵を共有する必要があるため，
「共有鍵暗号」「共通鍵暗号」とも呼ばれる．暗号文を送受信する前
に，あらかじめ安全な経路を使って秘密の鍵を共有する必要がある．
公開鍵暗号が発明されるまでは，暗号といえば秘密鍵暗号のことで
あった．代表的な秘密鍵暗号としては，アメリカ政府標準になっている
DES（Date Encryption Standard）\footnote｛米IBM社によって開発
された秘密鍵暗号化アルゴリズム．｝や，FEAL\footnote｛NTTが開発
した暗号方式｝，MISTY\footnote｛三菱電機が開発した秘密鍵型の暗
号方式．｝，IDEA\footnote｛1992年にスイス工科大学のJames　L.Ma
ssey氏とXuejia Lai氏によって発表された．｝などがある．
　中でも注目したのは秘密鍵暗号方式のひとつであるエニグマ暗号\fo
otnote｛詳細は第2章にてのべる．｝である．本研究ではエニグマ暗号
のアルゴリズムをFPGA（Field Programmable Gate Array）\footnote
｛詳細は第3章にて述べる．｝と呼ばれるLSI（Large Scale Integrat
ion:大規模集積回路）に実装する．

削除キー

　[No.80]　;
　ab　2006/01/05 13:29:26

一般家庭への急速なパソコンの普及に伴い，インターネット
ショッピングに代表される電子取引が，より身近なものになり，
電子メールも誰もが簡単にできる世の中になってきている．
しかし便利になってきている反面，盗聴やなりすまし，個人
情報の漏洩などの被害者が急増している．これらの脅威から大切な
情報を守るために注目されているのが，暗号技術である．暗号技術は
大きく公開鍵暗号方式と秘密鍵暗号方式の二つにわけることができる．
　公開鍵暗号方式とは，対になる2つの鍵を使ってデータの暗号化・
復号を行う方式であり，非対称暗号とも呼ばれる．片方の鍵は他人に
広く公開するため公開鍵と呼ばれ，もう一方の鍵は本人だけがわかる
ように厳重に管理されるため秘密鍵と呼ばれる．公開鍵暗号方式は，
暗号化と復号化を同じ鍵で行う秘密鍵暗号方式に比べ，鍵を安全な
経路で輸送する必要がないため，鍵の管理が楽であるという特徴を
有する．公開鍵暗号方式の原理は1970年代に考案された．ほぼ同時
に，具体的な暗号方式として，巨大な整数の素因数分解の困難さを
利用したRSA暗号が生まれた．現在では公開鍵暗号方式の標準として
RSA暗号が広く普及している．この分野の暗号方式にはRSA暗号の他に
楕円曲線暗号，ElGamal暗号などがある．

削除キー

　[No.79]　論文
　ともひこ　2006/01/04 12:49:49

近年におけるパソコンや携帯電話の普及，及び通信技術の向上により，誰でも容易にインターネット上で情報を送受信することができるようになった．しかし，容易に情報が送受信できる反面，個人情報など秘密にしておきたい情報が悪意のある第三者の手によって盗聴・改ざんされる危険性が出てきた．悪意のある第三者から秘密にしておきたい情報を守るために暗号技術がある．暗号技術の一つに公開鍵暗号方式がある．公開鍵暗号方式は暗号化には公開の暗号化鍵，復号には秘密の復号鍵を用いる方式で，暗号化鍵で暗号化されたものは復号鍵でしか復号できない特徴がある．この暗号方式は公開鍵を公開すればよいだけなので鍵の管理が容易で，不特定多数の通信に対して大きなメリットがある．

公開鍵暗号方式の安全性の証明可能性に関する評価に加え，その安全性が依拠している数学の問題がどの程度困難であるか評価する必要がある．これまでに様々な数学の問題の解法に関する研究が進められているが，最も研究が進んでおり，多くの実用的な暗号方式に利用されているものが，素因数分解や有限体上の乗法群における離散対数問題や楕円曲線によって定義された離散対数問題の解法に関する研究も盛んに行われている．以下では乗法群における離散対数問題について説明する．

1976 年に，Deffee と Hellman によって，有限体上の指数計算により安全でない通信路を通して暗号鍵を配送する公開鍵配送方式（ Deffee‐Hellman 鍵配送方式）が提案された．離散対数問題は古くから知られた難問であったが，この提案以来，離散対数問題が一躍注目を集めるようになり，離散対数問題に基づく公開鍵暗号や認証方式はその後数多く提案されている．

離散対数とは，素数 $P$ を定めたとき，$Z *_{P}$における原始元 $g$ に対して，$y= g^{x}$ mod $P$ ならば，$y$ の $g$ に対する離散対数といい，$x$ = log_${g} y$ と記すものである．つまり離散対数問題とは，$（ p，g，y ）$が与えられたとき，$x$ = log_${g } y$ を求める問題である．

削除キー

　[No.79 - 1]　Re: 論文
　ともひこ　2006/01/04 12:51:30

離散対数を求めるアルゴリズムは，次の 2 種類に大別することができる．

1 ．$Z *_{P}$ 上の離散対数の計算時間が，$Z *_{P}$ の位数 $P – 1$ の最大素因数のサイズ $N$ に依存するアルゴリズムで，その計算時間は $O （2 ^( N ) N ）$となる．つまり，$N$ に関して指数時間オーダの実行時間となる．
2 ．指数計算法と呼ばれる手法で，$Z *_{P}$ 上の離散対数の計算時間が，$P$ のサイズの準指数時間オーダの実行時間 $L _ {P}[ a，c ]$ となるものである．

前者のアルゴリズムとしては，Shanks，Pohlig–Hellman，Pollard のアルゴリズムなどが知られている．後者は，Adleman，Coppersmith，ElGamal，Coppersmith–Odlyzkyo–Schroeppel，Gordon，Schirokauer，Adleman などのアルゴリアルゴリズムが知られている．
　本研究では，離散対数問題をPohlig–Hellman 法で大きな法 $P$ の場合でも計算が可能かどうかをPohlig-Hellman法の有効性について評価していく．
本論文では，まず第 2 章で、基本事項について述べる．次に第 3 章で，Pohlig-Hellman
法について述べる．第 4 章で、実験の提案法を述べ，第5章で，測定した結果を出し，考察する．最後に第 6 章で，本論文を総括していく．

削除キー

　[No.78]　てふまにああね
　ともとも　2005/12/22 04:44:10

この記事は削除されました。

削除キー

　[No.77]　議事録
　琢一　2005/12/20 14:41:59

石井：実積幼稚園に検証に行った
予定 22 日の準備

伊藤：実績 22 日の準備と，プログラムの見直し．
予定エニグマロータープログラムの作成．

井上：実績べき乗の細かい計算の部分以外のところは完成．90 bit まで
計算時間を測った．
予定べき乗の計算部分をつくる．卒論の文章のやり直し．

大岡：実績会社の研修が 4 日間あったので，発表資料の編集だけ
予定引き続きプログラムの問題解決

岸本：実績 22日の準備とプログラムの修正，改善．
予定 22日の準備と学習のプログラムの修正，改善．マップ化するた
めのプログラム学習．

小池：実績 design のプログラムの完成．22 日の準備．
予定 design の改良型の作成．22 日の準備．

小長井：実績中間発表の用意をほぼ完成．
予定ツールボックスについて調べる．
相談〃わからなければ相談．

城念：実績中間発表の用意と調整．
予定プロトコルの完全解明と GP の最終調整．

杉尾：実績発表の資料作成．
予定発表の準備を終わらせる．図形認証について考える．

高森：実績 22 日の準備．
予定〃

中村：実績 MH 暗号のプログラムの製作，中間発表の準備．
予定〃

鳩本：実績中間発表の準備．
予定引き続き中間発表の準備．

削除キー


前へ	1　2　3　4　5　6　7　8　9　10 　11 12	次へ

上へ戻る

管理者メニュー