Path: ccsf.homeunix.org!CALA-MUZIK!newsfeed.media.kyoto-u.ac.jp!newsfeed2.dti.ad.jp!taurus!not-for-mail From: manmos@stellar.co.jp (Hideo "Sir MaNMOS" Morishita) Newsgroups: fj.net.watch,fj.sci.misc Subject: Re: [crypt] Re: Time complexity of Encryption Algorithms Date: 25 Jun 2006 19:30:19 +0900 Organization: Stellar Craft Inc., Osaka, Japan Lines: 42 Message-ID: References: <1150480016.570142.193490@u72g2000cwu.googlegroups.com> <86psgzzf67.fsf@bsd2.4bn.ne.jp> NNTP-Posting-Host: leda.stellar.co.jp Mime-Version: 1.0 Content-Type: text/plain; charset=iso-2022-jp Content-Transfer-Encoding: 8bit X-Trace: taurus.stellar.co.jp 1151231421 3064 202.255.1.244 (25 Jun 2006 10:30:21 GMT) X-Complaints-To: news-admin@stellar.co.jp NNTP-Posting-Date: Sun, 25 Jun 2006 10:30:21 +0000 (UTC) User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4 Xref: ccsf.homeunix.org fj.net.watch:1757 fj.sci.misc:172 In article <86psgzzf67.fsf@bsd2.4bn.ne.jp>, Yoshitaka Ikeda writes: > "nipunshah" writes: > > > Hi guys, > > Can anyone tell me where to find the time complexity of algorithms > > like AES, DES, 3DES, RC4 and BlowFish? I need the complexity in Big O > > notation. > > Time complexity of breaking the algorithms will be useful too. > > ~Nipun > > さて、フォローはいくつかついているんですが、 > http://groups.google.co.jp/group/sci.crypt/browse_frm/thread/7ccf37eb3d9010bb/b5f775e3dc74d564?lnk=st&q=Time+complexity+of+Encryption+Algorithms+sci.crypt&rnum=1#b5f775e3dc74d564 > > なんか、微妙、 > っていうかO表記で計算量をあらわすってことは何らかのパラメータが > あるはずです。RSAの様な鍵が可変なものならば、鍵サイズがパラメー > タになるとは思うんですが... > DESは鍵サイズ唯一56bitだけだし、 > AESだって、3種類しか鍵サイズは存在しない。(そしてブロック長は一定) > > 実際のところ、暗号化計算量は「段数」依存で、これ別に比例関係が > あるわけでは無し、というわけで、どうO記法で書くんだろう　って > 思ってたら、O(2.718281828). とか、O(3.145928) とかそんなフォ > ローがついてます(w ま、なんとなく、permitationするときのbitの数だとか… でも、昔読んだ論文で、「途中のbitが0だからといって、計算を飛ばしちゃい けないよ」ってのがありました。 「計算速度で、鍵のパターンを読み取ることが可能になるかもしれない」って 話。 当時のRSAの実装が大分入れ替わりましたね。 -- ___ わしは、山吹色のかすてーらが大好きでのぅ [[o o]] ふぉっふぉっふぉ 'J' 森下 お代官様 ＭａＮＭＯＳ 英夫＠ステラクラフト PGP Finger = CD EA D5 A8 AD B2 FE 7D 02 74 87 52 7C B7 39 37