著者

若月 祐介 築地 立家

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.9, pp.43-50, 2009-01-23

---

DNA コンピュータを用いれば,ナノスケールの計算素子として DNA 分子を利用することにより,超並列計算を実現することができる.実際, Adleman らは, DNA コンピュータが DES 暗号を効率的に解読できることを示した.そこで,本論文では, AES 暗号を効率的に解読するような,複数の DNA アルゴリズムを示す.ところで, AES は DES よりもはるかに解読が難しい暗号として知られている.実際, Adleman らの DES 解読アルゴリズムを単純に拡張した AES 解読アルゴリズムでは, DNA メモリコンプレックスの長さが 7 倍以上になってしまう.我々のアルゴリズムを用いれば, DNA を切り離すための制限酵素を使用することにより,高々 1.3 倍の長さのメモリコンプレックスで AES コードが解読できることが示される.DNA computer utilizes DNA molecules as nanoscale computational elements to provide efficient computations for currently intractable problems. Actually, Boneh, Dunworth, Lipton showed that a DNA computer can efficiently decrypt DES encryption codes. In this paper, we show a couple of algorithms decrypting given AES codes by a series of parallel DNA operations. Since AES is known as much harder than DES to be decrypted, e.g. AES uses 128 bits, while DES uses 64 bits, of the hidden key, a simple extension of their algorithm requires DNA memory complexes of 7 times longer than the previous ones. One of our results shows that, by inserting restriction enzyme DNA cutting operations, much shorter memory complex is enough to decrypt given AES codes.