パスワードを忘れた? アカウント作成
7839623 journal
日記

wasabifurikakeの日記: 数独の記事を読んでいてふと思った 3

日記 by wasabifurikake

数独の答えを公開鍵に
問題を秘密鍵にして
公開暗号鍵をつくれないか?みたいなことを

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by je1ocv (46043) on 2013年03月13日 21時48分 (#2342816) 日記

    いいですね。それ。

    --
    640GBはすべての人にとって未来永劫充分なメモリだ。
  • by Anonymous Coward on 2013年03月14日 3時22分 (#2342990)

    81digitsは短すぎる

    あとね、あとね。同じ答えから二つの問題が構成されたらどうするの?<ここまでは既に存在する。
    答えは公開鍵になれるの?
    問題は秘密鍵になれるの?
    秘密鍵が9digitsぐらいって、そっちを攻撃した方が早いんじゃない?

    • > 秘密鍵が9digitsぐらいって、そっちを攻撃した方が早いんじゃない?

      秘密鍵が、「81マス中9マスだけ数字が埋まった問題」だとしても、
      その9マスの場所だけで、81C9 = 260887834350通りのパターンがあります。その9マスの数値は回答から自明なので、この数値がそのまま攻撃の試行パターン数。ビット数にしてlog2(81C9) ≒38bitの秘密鍵情報になります。

      まあ、ある程度のブルートフォース攻撃に耐えられる感じですが、ちょっと短すぎですね。

      でも、数独は9x9にしないといけないというものでもないので、たとえば16x16の数独にすれば、log2(256C16)=83bit [wolframalpha.com]になりますし、
      25x25の数独ならlog2(252 C25)=147bit [wolframalpha.com]になります。

      最大の問題は、
      > 同じ答えから二つの問題が構成されたら
      こっちの方ですよね。
      こうならないようにするためには、何らかの条件(例えば、「81マス中9マスのみ分かっている問題で、同じ解答になる別問は存在しない」)といった条件を付け加えるしかないですが、「同じ解答になる別問が存在しない」ことをチェックするには、攻撃するのと同じ手間がかかるので、それが出来るならもはや鍵として意味がないという…

      親コメント
typodupeerror

身近な人の偉大さは半減する -- あるアレゲ人

読み込み中...