投稿

6/21 マルレク・サブゼミ 「3時間で学ぶ Shorのアルゴリズム入門」について

6/3 マルレク「暗号技術の現在」のフォロー・アップのセミナーとして、6月21日次のセミナーを開催します。  日時; 2019年6月21日 19:00~22:00  場所: 五番町グランドビル 7F / KADOKAWA セミナールーム  テーマ:「3時間で学ぶ Shorのアルゴリズム入門」  申し込みページ: https://shor.peatix.com/view 講演概要 6/3のマルレク「暗号技術の現在」では、暗号技術が現在の「公開キー暗号/RSA暗号」から「ポスト量子暗号」に大きく変わろうとしているという話をしました。こうした変化を引き起こした最大の原因は、25年前に発見された「Shorの素因数分解アルゴリズム」です。 RSA暗号は、大きな素数p,q 二つの積である大きな数Nが、たとえNを知っていても、現在のコンピュータでは、その素因数p,qを求めることがとても難しいという事実をその基礎にしています。公開キー暗号は、コンピュータでも分解できないこのNを、事実上、皆の前に公開するという暗号方式です。Shorは「量子コンピュータを使えば」、Nの素因数分解が極めて高速に可能になることを発見しました。それは、「公開キー暗号/RSA暗号」が、簡単に破られるということを意味しています。 ではなぜ、こうした発見が25年間も「暗号技術に対する脅威」とは見なさなかったのでしょうか? その理由は簡単なものです。それは、「量子コンピュータ」が、すぐにも実現する技術とは見なされなかったからです。現時点でも、大きなNに対して、Shorのアルゴリズムでその素因数を求められる量子コンピュータは存在しません。 ただ、20年後40年後は、どうなっているでしょう?  近年になって、量子コンピュータの「実現可能性」について、大きな認識の変化があります。基本的には、いままでよりかつてなく多くの人が「いつか、確実な時期はわからないが、量子コンピュータは実現するだろう」と考えるようになってきました。Shorのアルゴリズムに対する関心が、新たに高まっているのは、そうした背景があります。NSAやNISTが、「ポスト量子暗号」への動きを本格化しているのは、当然のことだと思います。 1. 量子コンピュータではなぜ高速な計算ができるのか?  量子コンピュータでは

6/3 マルレク「暗号技術の現在」の講演資料です。

イメージ
6/3 マルレク「暗号技術の現在」の講演資料です。ご利用ください。 http://bit.ly/30YB8gP お申し込みは、次のサイトからお願いします。残席わずかです。 https://qcrypt.peatix.com/   --------------------------------   「暗号技術の現在」 はじめにから   -------------------------------- 暗号には「秘密」がつきものであった。1955年、数学者のJohn Nashは、 NSAに対して「鍵の計算に指数関数的時間のかかる」方法を使えば、「誰にも破れない暗号を簡単に作れるようになる」という手紙を送っている。1970年代の初めには、イギリスの情報機関GCHQの科学者たちが、今日の公開キー暗号と同じものを作り上げていた。それはNSAも知っていた。ただ、それらは全て「機密」とされ、世に知られることはなかった。 なぜ、「機密」にされたかといえば、securityの問題は、第一義的に”National Security”の問題だからということなのだが、なぜそうした技術が、広く実用化されなかったという点に関して言えば、別の問題があったことに気づく。それは、当時のコンピュータには、少なくとも経済的には、こうした複雑な計算を実行する計算能力が十分ではなかったのである。 現在の暗号化技術の基本が出来上がるのは、1976/1977年のことである。その技術の真価は、80年代のコンピュータのコンシューマライゼーション(PC-AT, Windows, …)を経て、90年代半ばのインターネットのグローバルな拡大、経済活動のグローバル・ネットワーク化、個人のネットワークへの登場を通じて、全面的に開花する。この技術なしでは、今日のネットワークの成功はなかったろう。 このことは、同時に、暗号化技術が、もはや、もっぱら ”National Security”のみにかかわる技術ではなくなったことを意味する。今では、誰もが暗号化技術を必要とし、誰もがそれを、オープンな「標準技術」として利用できる。それは、大きな変化である。 暗号化技術は、その時代で利用可能なコンピュータの計算能力、その時代で利用可能な通信基盤に大きく依存している。それは歴史的に変化するものだと僕は考え

自然

この前、5月なのに、サロマで39.5度になったりして、北海道のこと、ちょっと心配している。 6月末には、サロベツ原野にいっせいにエゾカンゾウの花が咲く。見事なものだったのだが、このところパッとしない。湿原が乾燥化して、ササが侵入しているのだ。 乾燥化は、異常気象のせいというより、牧草地が拡大し用水路が整備されて水の流れが変わり、湿原の水位が下がったことが影響しているらしい。 都会から来た人は、どこまでも続く緑の牧草地をみて、「すごい、大自然!」と感激する人も多いのだが、花いっぱいのサロベツ原野をみて欲しかったと思う。牧草地は、本当は「自然」ではないのだから。 まあ、それでも、「全部が、ゴルフ場みたいだ!」といわれるよりは、ましだと思う。(意外と多い。ビジネスマンに。) 連休中に、稚内に帰って、ペンケ・パンケで、数万羽の(ごめん。数えてはいません)鳥の群れを見て、すごい! みんなにも見せたいと思った。一瞬、観光資源になると思ったのだが、多分、無理だと気が付いた。だって、僕一人が近づいても、何千羽が逃げ出すのだから。    地元紙の記事で、僕の家の近くの「大沼」にも、今年は白鳥が三万数千羽飛来したことを知った。昔はここに白鳥なんかこなかった。「白鳥おじさん」という人がいて、彼が大沼で地道に餌付けをしていた。 でも、「白鳥おじさん」の努力のせいだけでないと僕は思う。 かつて稚内市は人口6万を超えていた。今は、三万数千に減少している。今に、人口が飛来する白鳥の数より少なくなるのかもしれない。(昔から、牛の数には負けていたのだが。) 過疎が進むと、自然が戻るのだと思う。 サロベツを脅かすササの話に戻ろう(牧草地のことはおいておいて)。宗谷地方には、高い木がない。100年ぐらい前に、大きな山火事があって、森が全て失われ、ササが跋扈するようになったらしい。 昔、稚内の大学にいた頃、北大の演習林の人たちと仲良くなって、シュマリナイの演習林の施設で講演をしたことがある。そこで聞いた話が面白かった。(そこでご馳走になったコイ料理もうまかった。シュマリナイ湖は人造湖で、コイも養殖している) 「先生、今は、ササが圧倒的に勝っているように見えますが、時間が経てば、ササは木には負けるんです。300年もすれば、鬱蒼とした森林が復活します。」 そ

Moscaの定理

イメージ
「ひとつ、ふたつ、みっつ、あとはたくさん。」 幼児は、数えることを学んでも、すぐに50まで数えられるわけではない。未来の技術予測に関しては、僕らも、それに似ているのかもしれない。 確かに、経済人には、もっと長い展望で物事を考えている人はいるのかもしれないのだが。ただ、その経済人が暗号通貨に興味を持っているなら、是非、知ってほしい「定理」がある。 それは「Moccaの定理」という定理だ。 NISTが「ポスト量子暗号」のインフラづくりの緊急性を訴える時、繰り返し強調している「定理」である。決して理解が難しい定理ではない。 ただ、それを理解するには、僕らの技術的日常に染み込んでいる「ひとつ、ふたつ、みっつ」の世界から、要するに数年先のことしか考えないという世界から、すうっとその先に時間感覚を広げないといけない。 こういう定理だ。 xを、我々の現在の暗号技術が、何年有効であってほしいか、その年数とする。 yを、量子コンピュータの攻撃に耐える暗号インフラを構築するのに必要な年数とする。 zを、大規模な量子コンピュータが構築されるまでの年数とする。 【 Moscaの定理】 この時、x+y>z なら、暗号は破られる。 yについては、NISTは、現在の公開キー暗号のインフラを作ってきた経験から、y=20年はかかるだろうと予測している。 もしも、僕の作った暗号通貨MaruCoinが、50年は安全でいてほしいと思ったとする。x=50だ。 一方で、僕は、大規模な量子コンピュータシステムは、あと30年ぐらいでできると考えている。z=30だ。 x+y = 50+20 > 30 (z) 要するに、僕のMaruCoinは、量子コンピュータが暗号破りに使えるようになった 30年後から、40年間も破られ続けるということになる。 それは、僕のコインが50年は安全でいてほしいという希望と、量子コンピュータが30年後には実現するかもしれないという予想が矛盾していることを示している。 もちろん、未来の予測と希望からできている式なので、x,y,zの値は、自由に選べる。 僕は、僕のコインがボロボロにされるのは嫌だから、zを80まで増やすことにする。要するに、21世紀中には量子コンピュータなんかできないと考えることにする。

僕は「採血」が苦手だ。

僕は「採血」が苦手だ。 医者になっていたらきっと「採血」下手だったろうと思うが、幸いなことに医者ではないので、人に迷惑をかけたことはない。僕は、「採血」されるのが苦手なのだ。 時々、病院に行くのだが、第一関門の「検査室」では、20人近くが並列に採血されていく。こんなに採血する人がいるのに、僕は、一度も「うまい」ひとに当たったことはない。 僕の場合、一回では血が取れず、平均すると三回くらい針を刺されることになる。 この前、同じ病院で人間ドックを受けたのだが、3人が入れ替わりで僕の採血に「挑戦」して、普通5分もかからない採血に、40分以上時間がかかった。 悪いと思ったのか「主任」さんらしい人(採血に失敗した二人目の人)が、人間ドック最後までエスコートしてくれた。VIP待遇で後の検査は割り込みありで待つことなくスムーズでありがたかったのだが、それは、グループに分かれて流れ作業で進むはずの検査の流れが乱れたから、現場で調整が必要になったからだと思う。 人の顔の作りがみな違うように、僕の腕の血管の流れ方もちょっと違うようだ。顔にたとえれば、きっと、ピカソの絵のように、鼻の位置がずれて、ひん曲がった不恰好な顔をしているのだろう。(でも、それは、僕のせいではない。いや、やはり、僕のせいかな?) 今日は、一回で、採血が終わった。 今日の彼女は、違っていた。 針を浅く刺す。血管に当たるまで、注射針の根元まで深く刺す。それでもダメなら、針を抜かずに、針の向きを変えて同じことをする。この針で「まさぐる」のは、これまでも経験がある。ただ、二度ぐらい「まさぐる」とたいていの人は諦めて針を抜くのだが。 今日の彼女は、諦めない。そして、針を抜かない。なんども浅く深く向きを変えて「まさぐる」。 そりゃ、僕の血管がいくら変なところを通っているかもしれないけど、血管がないわけではないので、このやりかたなら、いつか血管に当たって、血が出ますよ。 検査室の人は、採血が終わると、みなが「お大事に」という。それは、たいていは、検査の対象の病気と病人に対する気遣いの慣用句なのだが、僕の場合は、検査へのお詫びになっている。そう言われてもねとも思うのだが。 世が世ならば、僕の血管配置の「ドラキュラ耐性遺伝子」ともいうべきものが、人類を救うのだと思うこと

ビットコイン、イーサリウムと新一万円札は、どちらが長持ちするか?

イメージ
楕円関数暗号への投資の抑制を訴え、楕円関数暗号が量子コンピュータの前には「多くの人がかってそうなるだろうと期待したような長期間にわたって有効なソリューションではない」というNSAの警告に耳を傾ける必要があると思う。  NSA "Commercial National Security Algorithm Suite"   http://bit.ly/2YExs1M 多くの人は、こうした警告を知らないか、あるいはその警告がビットコイン、イーサリウムといった暗号通貨の暗号技術の脆弱性に対する警告であることに気づいていないように思う。 誤解を避ける為に言っておきたいのだが、僕は何も、暗号通貨やブロックチェーン技術がダメだと言いたいわけではない。(実際、僕の友人の多くも、こうした技術にコミットしている) 確かに、現在実装されている暗号化が、現在のコンピュータの計算能力では解けないのは、確かだと思う。すぐにでも、暗号通貨に、破局が訪れるというつもりはない。しかし、問題なのは「現在のコンピュータ」の計算能力の問題ではなく、これから台頭するだろう「量子コンピュータ」の計算能力である。 もう一つ大事なことは、量子コンピュータの「攻撃」に耐える暗号化の標準を NSAもNISTも策定中だということである。こうした量子耐性を持つ暗号化アルゴリズムを利用すれば、暗号通貨もブロックチェーンも、そのアイデアの本質的な部分は、存続していくと思う。 ただ、その存続のためには、強い暗号が必要なのだ。 「RSA-2048暗号は、2026年までにはその1/7が破られ、2031年には1/2が破られるだろう」    https://eprint.iacr.org/2015/1075.pdf というMoscaの予想が正しいとすると、2024年に発行予定の新一万円札が登場して10年も経たないうちに、ビットコインもイーサリウムも、ボロボロに破られるということになる。 その時期がいつになるのかは、僕には正確にはわからない。僕は、Moscaより、もう少し先のことだろうと考えているのだが、それが2050年代だとしても、問題は深刻である。 注意しておきたいのは、現在では、量子コンピュータは、国家か大企業のプロジェクトのレベルでしか

ビットコイン、イーサリウムと楕円曲線暗号

イメージ
ビットコイン、イーサリウム等の暗号貨幣のほとんどは、暗号化に楕円曲線暗号を用いている。 多くの人は、大きな数の素因数分解の難しさを基礎とするRSA暗号より、離散対数問題を解くことの難しさを基礎とする楕円曲線暗号の方が、強い暗号(その上暗号化の鍵のビット数も減らせて効率的)だと信じているように見える。 ただ、量子コンピュータからの「攻撃」に対して、楕円曲線暗号の方がRSA暗号より強いかと言えば、答えはノーである。楕円曲線暗号を、量子コンピュータは破ることができるのである。 このことについては、今度のマルレクで触れたいと思う。暗号貨幣・ブロック・チェイン技術について関心のある方も、ぜひ今度のマルレクに参加してほしいと思う。 https://qcrypt.peatix.com/ NSAの楕円曲線暗号についての次のような重要な勧告は、明確にビットコイン、イーサリウム等の暗号通貨のセキュリティの現状についての警告なのだが、そのことに皆が気づいているわけではないように思う。 「Suit Bの楕円曲線アルゴリズムへの移行を、まだ行なっていないパートナーならびにベンダーは、現時点で、そのための大きな支出せずに、その代わりに、来るべき量子耐性アルゴリズムへの移行を準備することを、我々は勧めてきた。」 「不幸なことに、楕円曲線の利用の拡大は、量子コンピューティング研究の絶え間ない進歩の事実と衝突するものである。すなわち、量子コンピューティングの研究は、楕円曲線暗号化は、多くの人がかってそうなるだろうと期待したような長期間にわたって有効なソリューションではないことを明らかにした。こうして、我々は、戦略の見直しを余儀なくされてきた。 」  NSA "Commercial National Security Algorithm Suite" http://bit.ly/2YExs1M Shorのアルゴリズムは、多くの人は素因数分解の量子アルゴリズムと考えているようなのだが、それはコインの片面でしかない。重要なことは、同じアルゴリズムが離散対数問題も解くということである。 Shorの原論文のタイトルは、"Polynomial-Time Algorithms for Prime Factorization and Di