2008年7月28日 17時12分終了#25067 [学問] しRSA暗号の解読

ID:jCCd6dPs-Q (・∀・)ｲｲ!! (2)

「スコア調査」#81で「50〜99、100〜499、500〜999、1000〜4999、5000以上」と答えた方への質問でした。

　ここにインターネットで広く使われているRSA暗号を使って、暗号化された5つの数字がある。
「32　8　13　4　5」
この数字は、91を法とした世界で、元の数字を5乗にした値である。
この暗号化された数字をさらにx乗することで元の数字に戻すことができる。
暗号化される前の元の数字は、それぞれいくつになるか。最初に正解された方には、1000モリタポを進呈。
（尚、計算しやすくするため、実用で使われる桁数と比べて大幅に小さい数字を使っています。高校数学レベルの四則演算のみで求められます。）

追記

91を法とした世界とは、簡潔に言うと、0〜90までしか数字が存在しないことで、それ以上の数は、91で割り算した余りで表す。mod(モジュロ)91をとるとも言います。
例　100の場合、　100mod91＝9
また、91は素数同士を掛けた積であり、91をNとして、N=p×qとする。
xを求めるには、
{(p−1)と(q−1)の最小公倍数×n(1,2,3,…)＋1}÷5
で求められる。

既に正解者にはモリタポ配布しました。

1	分からない	129	(43%)
2	コメント欄に書く	41	(13.7%)
3	面倒くさい	87	(29%)
4	任意	43	(14.3%)
無視		1

棒グラフまたは左の番号をクリックするとその項目を元にしたしっかりアンケートが作れます。

多い順に並べる

「任意」の内容、回答頻度、省略された選択肢の全表示、などの詳細表示

この円グラフをブログに貼れます→

合計回答数: 300人 / 300個

このアンケートにはNGワード「水樹」「ルイズ」「ぬるぽ」「nothing is」「アウディ」が設定されていて、部分的に一致しても回答が無効な設定になっているので結果が偏っている可能性があります。

このアンケートと年齢、性別、出身都道府県、居住都道府県でのクロス集計を見る Tweet

このアンケートへは現在トラックバックできません。

13 :名無しさん 08/07/28 14:48 ID:acFJRkCgp8 (・∀・)ｲｲ!! (0)

2 8 13 23 31
正直わからん

14 :名無しさん 08/07/28 14:49 ID:9Q4RJijrrH (・∀・)ｲｲ!! (1)

ある数字aを5乗し、91で割った余りが32である。
32をx乗し、91で割った余りはaである。

という理解で合ってる？

15 :名無しさん 08/07/28 14:50 ID:75_5RrV5Rz (・∀・)ｲｲ!! (0)

取り合えず91が3以上の素数を掛け合わせた数
というのはかわったがそっから先がわけわかめ

16 :名無しさん 08/07/28 14:56 ID:KzDI_YCbmq (・∀・)ｲｲ!! (3)

RSA暗号ですらなんの事やら分からない。
ここの書き込み読んでると異世界に来た様な気がしてくる。

17 :名無しさん 08/07/28 14:57 ID:.y1PV5JsS8 (・∀・)ｲｲ!! (0)

2　8　 13　 23　 31
>>13
同じになったけど、正直俺もわからん。

18 :名無しさん 08/07/28 15:00 ID:AB_0XzUmUY (・∀・)ｲｲ!! (1)

解けたーと思ったらすでに14時28分には任意欄に出てるという･･･
>>13,17
俺もさっきそれになった。

19 :名無しさん 08/07/28 15:01 ID:zDAK_W.hh4 (・∀・)ｲｲ!! (0)

32　8　13　4　5で元の数字と同じ。

20 :名無しさん 08/07/28 15:11 ID:T1-RlXxViI (・∀・)ｲｲ!! (1)

数学なんて大嫌い
１０森ありがとう！

21 :名無しさん 08/07/28 15:14 ID:CI6a82cDP8 (・∀・)ｲｲ!! (0)

工学（電子系）の院生だけど91を法とした世界ってのが分からなかったし、
modは見たことはあるけど、使った計算はやったことないのでわけわかめ

22 :名無しさん 08/07/28 15:14 ID:I.lkKvxDzi (・∀・)ｲｲ!! (0)

数学屋とか暗号屋はおもしろいね。
俺は数学苦手だから無理だが、頑張って絶対に解けない暗号を考えてくれ。

23 :名無しさん 08/07/28 15:29 ID:32Cgp4NymY (・∀・)ｲｲ!! (1)

ttp://ruffnex.oc.to/kenji/xrea/rsa.txt
を読んでやってみた。

＞2つの大きな素数 p, q を選びます。
＞それらを掛けたものを n とします。
＞n = p*q

＞2. 暗号化
＞m = c^e ( n を法とする世界 )

と書いてあったから、多分nは91なんだろうと考えて、
91=13*7で
p=13
q=7
とした。

＞p, q それぞれから 1 減算した値同士のの最小公倍数を求めそれをMとします。
＞M = lcm( (p-1), (q-1) )

M=lcm(12,6)
M=12

＞d と M の最大公約数をとります。
＞( gcd(a, b) は a と b の最大公約数を表していると考えてください )

＞1 = gcd( d, M )

から
1=gcd(d,12)
1から一つずつ計算してみたらd=5だと思った。

＞e * d = 1 ( M を法とする世界 )
＞を満たす e を求めます。

e*5=1 (12を法とする世界)
これを
e=(12a+1)/5 　 　 [aは任意の実数]
でa=2のときに右辺が5になったから
e=5

ここまでで、
公開鍵 n=91、e=5、秘密鍵 d=5 を得た。



＞平文を c と置き、暗号文を m と置きます。

＞では 92 を秘密鍵で復号化してみましょう。
＞d = 19, n = 143 ですね。
＞n は公開鍵ですが暗号化にも復号化にも使用します。

＞c = m^d ( n を法とする世界 )

m=32 の平文を求めると、

c=m^d=32^5
…省略されました。全部(1,337文字)読むにはココをクリック。

24 :名無しさん 08/07/28 15:33 ID:32Cgp4NymY (・∀・)ｲｲ!! (0)

あ、でも"求められるね"なんていったけど、
>>23で答えあってるのかな？
誰か教えて！

25 :名無しさん 08/07/28 15:36 ID:28A8p0zY-N (・∀・)ｲｲ!! (0)

23 64 78 16 25

26 :名無しさん 08/07/28 15:38 ID:Avo,b_smjJ (・∀・)ｲｲ!! (1)

馬鹿だから、わからないんだ(´･ω･` )

27 :名無しさん 08/07/28 15:41 ID:28A8p0zY-N (・∀・)ｲｲ!! (1)

間違えた。俺も　2 8 13 23 31 だ

28 :名無しさん 08/07/28 15:45 ID:R5IootOLLG (・∀・)ｲｲ!! (0)

問題の意味がわかりませんでしたorz

29 :名無しさん 08/07/28 15:45 ID:8cbSumz8eY (・∀・)ｲｲ!! (0)

鶴亀算と時計算しかできない。

30 :名無しさん 08/07/28 15:46 ID:W4-OaB_iEH (・∀・)ｲｲ!! (0)

高校から文系選んで数学一切やってないからホントに呪文か何かにしか聞こえない・・・。

31 :名無しさん 08/07/28 15:55 ID:B8cinA6-KP (・∀・)ｲｲ!! (4)

解読できた暗号は
「既に正解者にはモリタポ配布しました。」
　　　　　　　↑この行のみ・・・orz

32 :名無しさん 08/07/28 15:57 ID:3K3mnGaFdM (・∀・)ｲｲ!! (0)

はああ〜久しぶりに頭使った。頭がこむら返りしそうだ。

33 :名無しさん 08/07/28 16:16 ID:rZ181Pg.zt (・∀・)ｲｲ!! (0)

91n+32=a^5
a=32^x

まで考えてくたびれた('A`)

34 :名無しさん 08/07/28 16:20 ID:i6Mf,_-wfE (・∀・)ｲｲ!! (0)

このアンケの意図は何だったんだろうな。
「セキュリティは意外に簡単に破られるものだから、もっと危機意識を持て」
って事かな？

35 :名無しさん 08/07/28 16:26 ID:mp2pjF6CY5 (・∀・)ｲｲ!! (0)

俺の頭じゃ正直よくわからん

……が、カキコがそこそこ活性化しているのを見るに
このアンケは良アンケだったのかな?

36 :名無しさん 08/07/28 16:29 ID:H7QGq9vK9f (・∀・)ｲｲ!! (1)

modはプログラムで普段から使ってるけど、「法とした世界」というのは初耳だった

37 :名無しさん 08/07/28 16:54 ID:Tu7GkJ,hi5 (・∀・)ｲｲ!! (0)

マジレスすると、RSA暗号とは言ってはいるが…
この問題の出し方じゃ、答えは一意に定まらないし暗号じゃないんだけどな…

たとえば…
32を復号化（暗号文を平文に戻すこと）すると
91×n+2（ただし，nは整数）も答えになるし…
だから、2だけじゃなくて93や457も答え…

38 :名無しさん 08/07/28 16:59 ID:g4H5m0lF0u (・∀・)ｲｲ!! (1)

91を法とした世界というのは>>91がスレで一番偉い人という世界のことじゃないんだね

39 :名無しさん 08/07/28 17:02 ID:-gxUSWwcU7 (・∀・)ｲｲ!! (0)

じゃあksk

40 :名無しさん 08/07/28 17:14 ID:SeLIdZ4abv (・∀・)ｲｲ!! (0)

>>8-9がかっこいいと思ってしまった。

41 :名無しさん 08/07/28 18:22 ID:fh9sT5lExZ (・∀・)ｲｲ!! (0)

>>37
復号することを前提にmod91に持ち込むということは
もともとの数字は90以下であると解釈してもいいんじゃないかね
もう少し問題文で定義してもよかったのかも知らんけど

42 :名無しさん 08/07/28 18:37 ID:DX-hWQnocz (・∀・)ｲｲ!! (0)

>>37
マジレスすると91を法とした世界では91より小さな自然数しか定義しない。
93や457は定義外だし答えは一意になる。

43 :名無しさん 08/07/28 18:38 ID:Tu7GkJ,hi5 (・∀・)ｲｲ!! (0)

>>41
「RSA暗号」を事前に知ってる人じゃないと
そう好意的には解釈はできないと思います。

>復号することを前提にmod91に持ち込むということ
は、正確には平文に対する条件にはなっていないので、
「平文は0以上91未満の整数」という前提は必要だったと思います。

44 :名無しさん 08/07/28 18:42 ID:Tu7GkJ,hi5 (・∀・)ｲｲ!! (0)

>>42
91を法とした世界というのは、あくまでも暗号文が属す世界であって、
平文がどこの「世界」に属しているのか問題文の中では明示されていないのです。

模式的に書くと、問題文では
暗号文∈「91を法とした世界」
平文∈「不明」

45 :名無しさん 08/07/28 18:43 ID:mo5KE24pZM (・∀・)ｲｲ!! (1)

あるいは「自然数での最小の解」とかか

46 :名無しさん 08/07/28 19:46 ID:CL5Fpg5PH, (・∀・)ｲｲ!! (0)

アンケ主は、このアンケで４０５０モリも消費しているのだが
どうしてなのか気になる。

板に戻る 全部 前100 最新50

現在このスレッドには書き込みできません。