パスワードを忘れた? アカウント作成
21542143 story
暗号

KDDI、世界で初めて1409次元の暗号を解読 18

ストーリー by nagazou
桁が違う 部門より

KDDI総合研究所は26日、暗号解読コンテスト「Challenges for code-based problems」で、Classic McElieceと呼ばれる次世代暗号の1409次元の暗号を解読し、これまでの世界記録を更新したそうだ。この1409次元の暗号は10の56乗(=100兆×100兆×100兆×100兆)通りの解の候補が存在する。このため、総当たりでは解読に1兆年以上かかるとされてきたが、KDDIは独自の解読アルゴリズムを用いて、2700万の解読処理を同時に実行できる並列コンピューティング環境を構築・活用することにより、29.6時間で解読に成功したとしている(KDDIASCII.jp)。

これにより、1409次元の暗号を解読するために必要な計算量が2の63乗であることを実証し、この次元を上回れば暗号の解読が困難という目安である暗号の強度を突き止めたとしている。この成果は、将来の量子コンピューターの台頭に備えた暗号の開発や標準化に向けた貴重な情報になるとしている。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • DJB御大の掌の上 (スコア:3, 参考になる)

    by Anonymous Coward on 2023年12月28日 14時26分 (#4587340)

    1つ前の世界記録見たらDJB先生だった

    15年前から解読アルゴリズムはぜんぜん進歩してない。その証拠に、この記録は2008年のソフトウェアを実行しただけ。
    記録更新とかいっても、単にハードウェアが進化しただけじゃないか。同じハードウェアなら、2022年のソフトウェアより2008年の自作ソフトウェアのほうが速い。

    的なことが書いてある
    https://isd.mceliece.org/1347.html [mceliece.org]

    KDDIには、DJB先生のコメントを踏まえた上での、解読の意義についても解説が欲しいところ

  • by Anonymous Coward on 2023年12月28日 14時17分 (#4587334)

    ①1409次元のClassic McElieceの解の候補は10^56あるが、10^20に絞り込むことが可能だと示した
    ②並列コンピューティング環境(とはいえPC10台らしいが)で30時間で解読できたというデモンストレーションを行い、実際に必要な計算量を示した

    標準候補として提案されているのは3488次元以上らしい。鍵のサイズがクソでかくなるな。

    • by Anonymous Coward

      公開鍵3.5MとかになるとTLSには向かないな

      • by Anonymous Coward

        3.5Kでは

        • by Anonymous Coward

          wikipedia を参考にしつつ
          n=3488, k=0.8n=~2791 とすると
          k * (n - k) = 1945327 bit
          だいたい 243k って事になるのかな。詳しくは判らんが

          • by Anonymous Coward

            古典コンピューターだけを考えるとちょっと鍵が大きすぎるな

            • by Anonymous Coward

              それを考慮すると、計算量とは一対一が理想なのかな。

  • by Anonymous Coward on 2023年12月28日 15時16分 (#4587380)

    世界で初めての1408次元での解読を目指そう。

  • by Anonymous Coward on 2023年12月28日 17時41分 (#4587460)

    これをクラックできるならNSAから雇用通知来るな

    https://github.com/Shadowsocks-NET/shadowsocks-specs/blob/main/2022-1-... [github.com]

  • by Anonymous Coward on 2023年12月28日 20時46分 (#4587534)

    一瞬で解く方法があるかもしれないから、
    だから量子暗号みたいな物理的な方法を使わないといけないとか暗号の専門家が言ってた気がする
    (ただし本物の量子コンピューターがあれば量子の状態も計算して求めることが可能だと思うが)

  • by Anonymous Coward on 2023年12月31日 20時09分 (#4588173)

    この宇宙は51次元じゃなかったっけ?

typodupeerror

人生の大半の問題はスルー力で解決する -- スルー力研究専門家

読み込み中...