プチコン 非公式コミュニティ
トピック
こういち
◆.Id/aHiU36hu
2021/3/18 18:20
2021/3/18 18:20
協力
暗号
(答えを知ってる問題ではなく、一緒に考えてほしいです)
2×5進法でk桁のパスワードがあり、これを暗号化するプログラムを書きたいです。
N人の人がいて、それぞれが2×5進法でk+1桁以上の素数を持っています。
暗号化された数と各々が持つ素数で簡単な計算(modなど)を行うことで、ある特定の数人のみが正しいパスワードを復元できるようにしたいです。(逆に言えばその数人以外は必ず間違ったパスワードになるようにしたい)
どのような暗号化をすればいいでしょうか。
2×5進法でk桁のパスワードがあり、これを暗号化するプログラムを書きたいです。
N人の人がいて、それぞれが2×5進法でk+1桁以上の素数を持っています。
暗号化された数と各々が持つ素数で簡単な計算(modなど)を行うことで、ある特定の数人のみが正しいパスワードを復元できるようにしたいです。(逆に言えばその数人以外は必ず間違ったパスワードになるようにしたい)
どのような暗号化をすればいいでしょうか。
コメント
こういち
2021/3/18 18:25
◆.Id/aHiU36hu
案1
その数人が持つ素数(P_0,P_1,…とする)で割ったあまりが暗号化前のパスワード(passとする)となるような最小のG
復元はG MOD Pで比較的簡単に出来ると思います。
これはGarnerのアルゴリズムを使うことで求めることが出来るらしいですが、この暗号化で他の素数は必ず間違ったパスワードになるでしょうか。
その数人が持つ素数(P_0,P_1,…とする)で割ったあまりが暗号化前のパスワード(passとする)となるような最小のG
復元はG MOD Pで比較的簡単に出来ると思います。
これはGarnerのアルゴリズムを使うことで求めることが出来るらしいですが、この暗号化で他の素数は必ず間違ったパスワードになるでしょうか。
こういち
2021/3/18 19:20
◆.Id/aHiU36hu
案1
G=passが最小ですね。
これは任意の素数で正しいパスワードを復元できるのでダメですね。
案2
二番目に小さなG
P1で割ったあまりがpassになるような数は
pass+n*P1
と表すことが出来る。
P1で割った余りP2で割った余りがpassになるような数は
pass+n*lcm(P1,P2)
(lcmは最小公倍数)
P1,P2は共に素数なので、lcm(P1,P2)=P1*P2
P3以降も同様。
n=0が最小でn=1が2番目なので、
G=pass+P1*P2*P3*…
ただ、このGってm人選ぶ場合m(k+1)桁になるのよね。
想定してる環境だとm=3,k=6なので、28桁。
これのmodが簡単な計算かと言われると微妙な気がする。多分28桁計算できる電卓もそう多くはなさそう(とはいえ、高精度計算サイト https://keisan.casio.jp:443/exec/system/1510710795 を使えば計算できなくはないので、許容範囲ではある)
G=passが最小ですね。
これは任意の素数で正しいパスワードを復元できるのでダメですね。
案2
二番目に小さなG
P1で割ったあまりがpassになるような数は
pass+n*P1
と表すことが出来る。
P1で割った余りP2で割った余りがpassになるような数は
pass+n*lcm(P1,P2)
(lcmは最小公倍数)
P1,P2は共に素数なので、lcm(P1,P2)=P1*P2
P3以降も同様。
n=0が最小でn=1が2番目なので、
G=pass+P1*P2*P3*…
ただ、このGってm人選ぶ場合m(k+1)桁になるのよね。
想定してる環境だとm=3,k=6なので、28桁。
これのmodが簡単な計算かと言われると微妙な気がする。多分28桁計算できる電卓もそう多くはなさそう(とはいえ、高精度計算サイト https://keisan.casio.jp:443/exec/system/1510710795 を使えば計算できなくはないので、許容範囲ではある)
Na
2021/3/18 23:48 ネタバレ
◆QoELVrBXBQCI
SatoshiMcCloud
2021/3/19 1:21
◆Z1qfV11i63Jr
「逆に言えばその数人以外は必ず間違ったパスワードになるようにしたい」という要件について、もしその数人とその数人以外の人の中に同じ素数を持つ人がいたら、どう頑張っても要件を満たせないような気がするのですが、そういう話ではない？
さすらいの名無し
2021/3/19 10:33
◆LWMA5UzCJb3e
高精度計算サイトっててっきりこれかと。
http://www.wolframalpha.com/
http://www.wolframalpha.com/
こういち
2021/3/19 10:35
◆.Id/aHiU36hu
SatoshiMcCloudさん
各々が持つ素数は全て異なるものと考えてもらって大丈夫です。
素数は配布することを想定しています。
各々が持つ素数は全て異なるものと考えてもらって大丈夫です。
素数は配布することを想定しています。
こういち
2021/3/19 10:51
◆.Id/aHiU36hu
Naさん
a_0=Gですかね。
確かに7*3なので21桁ですね。それでもlong型に収まらない程度には大きいですね…
そもそも配る数を素数に限定しなければ桁数も小さくなりますが…安全性が心配。
さすらいの名無しさん
そんなのあるんですね。初めて見た。
高精度計算サイト。ちょっと計算がしたいときに検索したらヒットしてくれるので便利。
a_0=Gですかね。
確かに7*3なので21桁ですね。それでもlong型に収まらない程度には大きいですね…
そもそも配る数を素数に限定しなければ桁数も小さくなりますが…安全性が心配。
さすらいの名無しさん
そんなのあるんですね。初めて見た。
高精度計算サイト。ちょっと計算がしたいときに検索したらヒットしてくれるので便利。
こういち
2021/3/19 14:42
◆.Id/aHiU36hu
案2の安全性について
あるPで正しいパスワードを復元できるかどうかは
G-pass=nP
となる整数nが存在するかどうかと言い換えることが出来る。
これはPがlcm(P1,P2,P3…)の約数である場合と言うことが出来て、P1,P2,P3…は素数であるためlcm(P1,P2,P3…)の約数はP1,P2,P3…とそれらの積のみ。他の素数は素因数に含まれないため、約数になり得ない。そのため、必ず間違った答えになる。
あるPで正しいパスワードを復元できるかどうかは
G-pass=nP
となる整数nが存在するかどうかと言い換えることが出来る。
これはPがlcm(P1,P2,P3…)の約数である場合と言うことが出来て、P1,P2,P3…は素数であるためlcm(P1,P2,P3…)の約数はP1,P2,P3…とそれらの積のみ。他の素数は素因数に含まれないため、約数になり得ない。そのため、必ず間違った答えになる。
ツララ
2021/3/20 16:50 ネタバレ
◆ArUdBYOYME1V
こういち
2021/3/20 20:53
◆.Id/aHiU36hu
10進法だと10が何進法で書かれてるかはっきりしないので…(まぁ実際には十だと思って問題ないんですけど)2×5だと一意に定まるのでこの表記です。
まぁ別にこの問題の場合法は何でも良くて、想定してるパスワードが2×5進法だったので書きました。
https://youtu.be/8K_0Re32GAs
想定した環境はこの配信で、どうやら同じ部屋に多数のアクセスがあるとうまく入れないらしいので、暗号で分散するのが目的でした。
まぁ別にこの問題の場合法は何でも良くて、想定してるパスワードが2×5進法だったので書きました。
https://youtu.be/8K_0Re32GAs
想定した環境はこの配信で、どうやら同じ部屋に多数のアクセスがあるとうまく入れないらしいので、暗号で分散するのが目的でした。
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります