数独の答えを公開鍵に問題を秘密鍵にして公開暗号鍵をつくれないか?みたいなことを
7839623 journal wasabifurikakeの日記: 数独の記事を読んでいてふと思った 3 日記 by wasabifurikake 2013年03月13日 21時33分 数独の答えを公開鍵に問題を秘密鍵にして公開暗号鍵をつくれないか?みたいなことを
いいね (スコア:1)
いいですね。それ。
640GBはすべての人にとって未来永劫充分なメモリだ。
アイディアは良いが (スコア:0)
81digitsは短すぎる
あとね、あとね。同じ答えから二つの問題が構成されたらどうするの?<ここまでは既に存在する。
答えは公開鍵になれるの?
問題は秘密鍵になれるの?
秘密鍵が9digitsぐらいって、そっちを攻撃した方が早いんじゃない?
Re:アイディアは良いが (スコア:1)
> 秘密鍵が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マスのみ分かっている問題で、同じ解答になる別問は存在しない」)といった条件を付け加えるしかないですが、「同じ解答になる別問が存在しない」ことをチェックするには、攻撃するのと同じ手間がかかるので、それが出来るならもはや鍵として意味がないという…