【数学】RSA-640陥落【暗号】

ソース
http://mathworld.wolfram.com/news/2005-11-08/rsa-640/
（英語でスマン）

RSAセキュリティー社が一般人にも提出してたRSAチャレンジ問題のうちの一つ、RSA-640が陥落した
この問題には賞金2万ドル（200万円強）がかけられていた

RSA暗号は、現在PCの暗号理論の中でも最もポピュラーな暗号形式
その理論は極めて単純で、素数を二つ掛け合わせた数字を暗号の鍵とし、その数をもう一度二つの素数に戻す事が出来れば暗号を破る事ができる
このRSAチャレンジには最高20万ドル（2000万円強）の賞金をかけられている問題もある

あっそれ知ってる、ほんと>>1って馬鹿だよね。

クリックしても開きませんでした

http://nuke.s8.x-beat.com/bbs_pic/img/319.jpg

ああ、俺だよ、俺。

暗号理論って面白そうだよね

そんなことより>>4の画像の詳細が気になる

RSAって解ってれば時間使えば復号できるだろ

気合で多倍長演算やるだけ

>>8
その「時間」が問題。

P=NPだっけ？それも素因数分解の公式化だよな？

http://nuke.s8.x-beat.com/bbs_pic/img/318.jpg

コピワン破れるの？

>>13
ま、力ずくでやればな

この問題を解いたおっさんも、力技で解いたんだろうし

大学生活板の固定の乱交パーティー
http://news19.2ch.net/test/read.cgi/news/1131980701/

1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579
x
1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571
=
310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967
1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

ってことですわ
まさに天文学的数字

RSAなんて暗算で解ける

$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579\
*\
1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571

31074182404900437213507500358885679300373460228427275457201619488232\
06440518081504556346829671723286782437916272838033415471073108501919\
548529007337724822783525742386454014691736602477652346609

ちゃんと計算しよる

反抗期の妹に弱味を握られた
http://ex10.2ch.net/test/read.cgi/news4vip/1131892219/

>>18
それを逆に計算できるソフトを作れば歴史に名前が残るんだけどな・・

C:\Program Files\Wolfram Research\Mathematica\5.2>math
Mathematica 5.2 for Microsoft Windows
Copyright 1988-2005 Wolfram Research, Inc.
-- Terminal graphics initialized --

In[1]:= 16347336458092538484431338838650908598417836700330923010450
8151212118167511579*19008712816648221131268515739354139754718967899
6851543802104498957191261465571

Out[1]= 31074182404900437213507500358885679300373460228427275644051
8081504556346829671723286782437916272838033415471090073377248227835
25742386454014691736602477652346609

明らかに合っています。ありがとうございました。

>>17
数学の天才来たー

割れソフト使って計算すんなー！！

手動保守

要するに暗号のセミプロみたいな連中が解いて喜んでるだけだろ？

>>25
ちゃんと賞金は出るけどな
それにこの問題に挑んでいるのは数多くのプロの数学者だし

このスレは何て言う暗号で書かれているの？

すごい

ちょ、ちょっと待て。力技で解いても賞金出るの？
それで暗号を解いたって事になってるの？

力技でおｋならあとは設備と運の問題だろ

何がどう難しいのか分からないので、すごいのすごくないのかすら分からない

RSAチャレンジってのは、要するに

「33を分解しなさい」
「はい！3×11です！」

これで終わり
ただ、これだけの事をやってるだけ
でもこの数字のケタがアホほど大きい

PCを使えば楽勝を思っているそこの君
この問題は、この世の中に存在する「いかなる手段」を用いて解いてもいい
反則はいっさい無し
手段を選ばすに解けばいい
誰も文句は言わないどころか賞賛を得られる

それにまだ、残りの問題にかけられてる総賞金は4000万はある
小金持ちになるチャンスだ

じゃあ今度はRSA1024bit解いてくれ
同じマシンで同じアルゴリズムでやったら
274877906944倍の時間かかるけど

なんか暗号を計算じゃなくて、見て閃きだけで解いた少年が
でてくる映画なかったっけ？あーゆーのって実際はいないの？

>>32
普通にとくのはめんどくさいから

正解の答案を盗めばいいんじゃね？

PC使えばとけると思ってるヤツはやってみれば?
リナックスインストールしたらGCC付いてくるから簡単なプログラムならすぐ組めるよ。

>>13
そういや2chの力でコピワン破りとか言って、何人かで計算していたあれはどうなったんだろうか。

どうやって解いたかが問題だろ

誰か地球シミュレータ無料で貸してくれ

ちなみに全ての問題はここに載ってる
http://www.rsasecurity.com/rsalabs/node.asp?id=2093

そして・・・・

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

これを二つの素数に分解できたら2000万以上の金がもらえる
今のところ、これが最も難しい問題

因数分解を効率的に解くアルゴリズムを考え出したとか、そういうのでは無いんでしょ？
何が凄いのかｲﾏｲﾁ理解できん

量子コンピュータﾏﾀﾞｧ-? （･∀･ ）っ/凵⌒☆ﾁﾝﾁﾝ

>>23
割れじゃねー。

ちゃんと個人で Mathematica 買ったぞ。

日本語おかしかった

>>40
2159まで読んだ

サヴァンに見せたら一瞬で・・・
とかないのかな

>>40
251959まで覚えた

その問題が解けただけであって、同じ桁数の問題を効率的に解けるようになったわけでは無いんでしょ
何が凄いの？

640じゃな〜
最低でも1024、安全を求めるなら2048使いなさい、とか言われてるのに・・・

>>37
ｱﾚは駄目だった

>>48
640は安全でないと証明されただけでも十分

>>42
まだ20qbitぐらいしか実現できてないんじゃなかったっけ？

RSAって色々使われている気がしますけど、
これは毀損の製品、サービスのセキュリティーには影響が無いの？

>>53
全く無い

>>48
効率的な方法を使わなくても、力業でも解ける時代になった
ということがすごいんじゃないかと。

桁を幾つかに分ければwindows付属の電卓でも確かめられる程度なのに
解くのはエラく難しい。というのは面白いの

ブルートフォースで鍵を総当りしたと思ってるアホﾜﾛｽ

グローバーのアルゴリズムってこういうのが線形オーダーになるんだっけ？

やっぱりこれからはRCAですよ

これを一瞬で解いちゃうようなアルゴリズムが出来ちゃうことはありうるの？

たまにダウン症ぽいキチガイが難解な数式を
一瞬で計算したりする症状あるじゃん。
こういうひと探したらええんちゃうん

こういうのUDとかSETIみたいに分散処理させてグループで解くとかやってないの？

力技でおｋならあとは設備、時間、運の問題でしょ
しかもこの中で設備という要素は常に上昇している

力技でRSA640bitが解けました
で？って感じ

>>62
つhttp://distributed.net/

というか、不特定多数のコンピュータで分散処理させて
問題を解く手法は、まさにここから始まったわけで。

こんなのgoogle計算機でやれば0.01秒で出るじゃん

>>60
量子コンピュータができたら一瞬らしい。

>>63
でも、10の500乗とかの数字って、現在最速のコンピュータで数字をカウントさせるだけでも
銀河系が終わるだけの時間かけてもムリってどっかで聞いた希ガス

要するに掛け算なのに、こんぷーたーで計算してもめちゃ時間がかかるのか
すげーな・・・

>>60
無いとは言い切れないが、たぶんないだろう。

>>63
設備さえかければ解ける問題があるというのにわくわくしないかなあ。

もちろん、今回だって総当たりで解いたわけじゃないけど。

>>>60
確かO(n)だか、O(n*log(n))だかにできた希ガス。なんか量子状態をユニタリ変換でぐりんぐりんやると解に収束するみたいな？

ちなみに、今現在もっとも効率よくとくアルゴリズムってどんなやつ？
まさか１から順に掛け合わせるとか

>>68
掛け算じゃない。

割り算の繰り返し

>>40
２から順番に全ての素数を調べてたら、時間がかかりすぎてお話にならないな。
どうするんだろ・・。

>>67
100000000000000000000000000000000000000の349826831043304052899672779969867917149乗

ぐらい1秒以下で出来るけど？

9!!!!!!!!!!!!!!!
とかって、どれくらい時間がかかるかな。

>>75
あれ？そうなの？じゃあ、なんか勘違いしたのかもしれんわ。ｽﾏｿ。

いーっぽすすんでまえならえー　いーっぽすすんでえらいひとー
○　○
|ーく-
|_　 ）_

>>48
人類が今の設備で「解けた」っていう事実だけでもすごいんだよ
はっきり言って、運とかそんなレベルじゃありえないから

仮に1秒間に１京回の割り算をこなすスパコンがあったとする
1秒間に
10,000,000,000,000,000回だよな？

こんなPCはまず存在しないんだけど

これで
10,000,000,000,000,000,000,000,000,000
の桁の数字を計算するのに最悪どのくらいの時間がかかる？
1,000,000,000,000秒かかる
つまり、最悪3万年以上かかる

もしこれで、問題の桁がたった一つ増えるだけで30万年かかる問題の完成だ
で、それを考慮した上で>>16を見てみ

まともにやったら不可能なんだよ
でも、それを可能にするアルゴリズムが存在したってわけだ
これだけですごいだろ？

>>53
まったく問題ない

どころか、RSAセキュリティー社は、その安全性を証明する目的の一環として、この賞金をかけた問題を出してるわけだし
実際RSA暗号はアメリカの軍でも使われている
そのくらい今はまだ安全だってこった

ちなみにそれほど深い部分じゃないけど、Winnyにも使われてるぞ

文型の俺には楕円関数とかわけわかめ

>>79
すごいな。
アルゴリズムで本当の意味で仕事量を圧縮してるってことか。
ザル状態で適当に調べても、宝くじの一等当選より大幅に確率低そうだし。ｗ

>>79
詳しいな。どんなアルゴリズムなのか分かる？

>>79
それはすごいな、どういうアルゴリズムだか知りたいね。

こういう面白さを学校で教えてくれていたら俺の数学嫌いも多少直っていただろうに・・・。

それはカッコワルイ言い訳です

どんなアルゴリズムなのかが問題だろ。
例えば、2の倍数や3の倍数等の明らかに素数で無い数ははぶく。
この方法だと、全ての数を試すわけでは無いので効率的だと言えるが、
素因数分解を効率的に行うアルゴリズムだとは言えない。
だってこんなの当たり前だもの。

http://www.amazon.co.jp/exec/obidos/ASIN/4140806311/249-4569552-5916337

これおもしろかた

どうせ一般数体ふるい法だろ

どんなアルゴリズムなのか
ここで簡単に俺らに説明出来るくらいなら
2万ドルの賞金はかからんのだろうなあと思った

古典計算でオーダーが変わるようなアルゴリズムはないだろ。せいぜい係数がちょっと減るぐらい。

>>86
>素因数分解を効率的に行うアルゴリズムだとは言えない。

馬鹿？

ストラトストラテロテネス

>40
long int でも入りきりません （＞＜）

つﾓﾝﾃｶﾙﾛｼﾐｭﾚｰｼｮﾝ

>>86
＞この方法だと、全ての数を試すわけでは無いので効率的だと言えるが、
＞素因数分解を効率的に行うアルゴリズムだとは言えない。

どっちだよ（ｗ

なんかよく分からんけど１〜１００全部足すのに（１＋１００）×１００÷２すればいいじゃん！！
のと似たようなことだろ？大変だな

>>91
馬鹿なのでｋｗｓｋ

素数を図形で考えられるってのあったよな

>>95
わからんか

a×b=X（暗号文）且つ
aとbがともに素数である事

が条件でござんすか？


まず7が素数である事の証明が総当りでの結果でしか
言い表すことができん俺にとっちゃムリな話だ。

インド人と中国人を集めて分散処理させたら良くないか？

わからない人に噛み砕いて説明するには
自分がわかるよりも、数段上の知性が要求される

>>96
その例だと1-nを足すのにn-1回の足し算が3回の演算にまで
減らせるわけで、かなり効率的になったことになる。

それに対して今回の問題では、計算のオーダーは変わっていなくて、
n回の演算がn/a　(aは定数)回に減っただけ、と思う。

確かに総当たりよりはかなり速いけど、nが増えればあっという間に
現実的な時間内では計算できなくなる。

進歩の度合いが和漢ねー

On February 2, 1999, we found that

RSA-140 =
2129024631825875754749788201627151749780670396327721627823338321538194\
9984056495911366573853021918316783107387995317230889569230873441936471

3398717423028438554530123627613875835633986495969597423490929302771479
*
6264200187401285096151654948264442219302037178623509019111660653946049

ＵＤのような分散コンピュータでこの問題を解かせる
スパイウェアを作れば最強

Aを素数に分解する場合

まずA立方cmの水を用意する。
縦横のサイズを1cm刻みで自由に変えられる水槽を用意する。
その容器に水を入れて縦横の長さをズズズッと変えていき、水面の高さが丁度1cmになるところを見つける。
その時の縦横の長さが答え。

バカと天才とボケ担当がいい感じで存在するニュー速が好きだ

うーむ、今はUDの方が有名なのか。

UDが出始めた頃はシステムを説明するのに「RSAを解いているやつ
と同じような仕組みだよ」と言っていたのだが。

>>106
ええっと・・・

分散するって、この問題の子問題ってどうなんの？

>>106
その水槽１００個注文し・・・

それ、複数の組み合わせが出てこないか？

>>50
やっぱだめだったのか。

この問題、とりあえずlogとって、素数の足し算で桁数が近いのとかじゃだめか…

1/4

とりあえず今日はこの課題を脳みそに抱えて寝るか。
起きる頃には忘れてそうだけど。

>>96


あまりに馬鹿でワロタ

>>115
まぁ、問題の持つ数学構造をうまく利用するってことだから、基本は同じようなもんじゃねーの？

>>106
Ａが２つの素数の積になってるならそれでいいけど、
結局時間かかるじゃないか。ｗ
それに、Ａが大きくなると一ｃｍを超高精度で測らなきゃいけない。

＞その理論は極めて単純で、素数を二つ掛け合わせた数字を暗号の鍵とし

　　　　( ﾟдﾟ) 　　　　　　　　　 (ﾟдﾟ ) 　　　　　　　　　( ﾟдﾟ )
　　　　素数１　　　　×　　　　素数２　　　　＝　　　　　鍵

＞その数をもう一度二つの素数に戻す事が出来れば暗号を破る事ができる

　　　 ( ﾟдﾟ )　　　　　　　　　 ( ﾟдﾟ)ｲｪｱ 　　 　　ｫｩｲｪｱ(ﾟдﾟ )　　　
　　　　　鍵　　　　　 ＝　　　　素数？　　　　×　　　　素数？


と言うことは　何十桁もある　「鍵 ( ﾟдﾟ )」　だけで
「素数１( ﾟдﾟ)」と「素数２ (ﾟдﾟ )」 を求めろ　って事なの？

>>16の場合
310 7418240490 0437213507（ｒｙ
が　「鍵 ( ﾟдﾟ )」　で

「素数１( ﾟдﾟ)」が
1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579

「素数２ (ﾟдﾟ )」 が
1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571
になるって事？

( ﾟдﾟ)ｲｪｱ

>>118
感じるんだ

もう勉強してわかっちゃってる奴より、
わかんないなりに理解しようと出来る奴の方が、
個人的にはすげえなあと思うよ。

で、なんの役に立つわけ？

本当に数学好きだなwwww

気になるあのこの好きな子がわかっちゃったりする

>>124
ｽｺﾞｽｗｗｗｗｗｗｗｗｗｗｗ

>>34
マーキュリーライジング？

>>122
２００万円もらえるぞ！

なんだこんなん１から探していけば楽勝じゃん

>128
多分計算完了前にお前かパソコンが寿命で死ぬ
あと出来れば2から計算してくれ

>>129
ﾜﾛﾁｗｗｗ

まあ、俺もそれほど賢いわけでもないし
ただ直感的にはわかる気がしてるし

ただ、>>79のは比喩的には正しいけど
本当の意味で言うなら

10,000,000,000,000,000,000,000
を割ろうと思えば、その1/2乗の桁までいけば、必ず答えは見つかるんだよ
つまり、(0がいくつあるのか数えるのも面倒だけど)その半分の桁までの計算で必ず答えは見つかる

でも、実際のRSAの数字は、例え桁が半減したところで手に負えないけどね

RSA-576とRSA-640はぱっと見ではそれほど違いはない
でもそのほんの数桁の違いが、片方は力ずくで1ヶ月で解けても、もう片方は同じ方法では10000ヶ月かかるという差になる

こんなに早くRSA-640が解けたってのは驚きだよ

良スレだな

今みたいになる前のVIPで
光や重力の事わかりやすく教えてもらったスレ思い出した

あの時の物理大好き高校生、どうしてるかな
年下だけど、師匠と呼びたくなる男だった

見事だな。しかし小僧、自分の力で勝ったのではないぞ。
そのコンピューターの性能のおかげだという事を忘れるな

ボカーン

ちょっと前にNHKで放送された海外番組に出てた、
異常に数字に強いｻｳﾞｧﾝ症候群の人なら解けたりするんかな

解けないから今でも暗号技術としてRSAが使われてるんじゃね？

>>126
ソードフィッシュじゃないか？ｗ

三菱電機の人が解いた暗号は何だっけ？

天才でも人間じゃあ19837019873059188273059182705981709の4091870918887098709876091870987乗

とか、計算できないだろ
紙が何枚あっても足りないよ

>>52
素因数分解を実行する実装については、Isaac Chuang[1]のグループが
NMRを用いて行った5qubit[2]が最高だと思う。NMR以外の実験装置を
用いた素因数分解の実装はないはず。

[1] http://feynman.media.mit.edu/ike/homepage/
[2] http://feynman.media.mit.edu/ike/homepage/papers/NMRQC-vandersypen-et-al-chuang-experimental-realization-of-an-order-finding-algorithm-with-an-nmr-quantum-computer-prl-v85-18dec00-p5452-2000.pdf

高額懸賞金が出るレベルのRSA暗号を解く量子計算機を死ぬまでに見たいが、
まあ無理だろうなぁ。

調理されたピザから、材料と調理法を調べるのが
今までは何十年も何百年もかかると言われていたのに、一瞬でできるようになったと言うことか。

もうどんな秘伝のレシピも無駄になってしまうな。

>>116に目からうろこ状態。

間違えた、>>106だ。

>137　日経エレかなんかにプロゼェクトXぽく連載してたな。名前は忘れたが

わかった！
42だ！

何年か前に聞いたけど
とんでもない大きな桁の素因数分解が難しいのは経験的なもので
数学的に証明されてないから、もしかするーとぱっと計算できる方法があるかもしれない
ってのは現在も変わらず？

sshアタックがうぜえええええええええええええええええええ

ヘタに宝くじとかを買うよりも、適当な乱数で暗号解読を試みるほうが
金も掛からずに夢を見られていいかもな。

こことか面白かった。
http://h2np.net/bit/aes-rep.html

>>137が言う、三菱電機の人が解いた暗号(DES)に代わる次世代の暗号(AES)
を決めるカンファレンスに参加した人のページ。

DESっていうのもぱっと見途方もない時間がかかるやつだったんだろ
そのうちどこかの天才がとくと思うよ

>147　それそれ。連載も面白かったな。数人のプロジェクトが世界に認められていくさまが

>>146
宝くじのほうが確率高いよ、しかも金かかるし

解けるのに1万年として、電気代が1ヶ月1000円＊1万年で1億2000万円

もしくは性能2万倍のスパコンのリース料＋スパコンの電気代6か月分＝数億円

>>136
あー　暗号解く時にフェラしてもらえる映画ね

銭形零ならとけるな

読んでるが天才の人たちはすごいね
なにがなんだか

まあ、どれだけ大変かを示すために、俺様がちょっとCでコード書いて見た
暇な人はコンパイルして走らせてみ

main() {
　　　　int a, b, c;

　　　　c = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609;

　　　　for(a=2; a <= c; a++) {
　　　　　　　　for(b=2; b <= c; b++) {
　　　　　　　　　　　　if(a*b == c) {
　　　　　　　　　　　　　　　　printf("a=%d, b=%d\n", a, b);
　　　　　　　　　　　　　　　　exit(0);
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}

>>145
現在も変わらず。つまりP≠NPは未だ証明されていない。

>>154
2からはじめなくてもいいんじゃね？

>>154
それをコンパイルできるコンパイラが世の中に存在しない件

この方法でどう利用されてるのかよくわからん・・・。

解けないなら受け取る方はどうデータ復元すればいいんだ？

解けるなら暗号の意味ないし。

めちゃくちゃ馬鹿なこと言ってたらすまん。

>>158
受け取るほうが、相手にこの方法で暗号化してくださいと教えるんだよ

そして、そのためのRSA

>>159
なーるほどね。
じゃぁ受け取る方はある程度素数が絞れるわけか。

暗号化する鍵と、解読する鍵が別
暗号化した鍵では解読することが出来ない

暗号化する鍵だけを相手に送って、それで暗号化して送ってもらい
それを解読用鍵で解読する。

なので暗号化鍵（公開鍵）を第三者に傍受されて問題心なしと

秘密鍵暗号とか公開鍵暗号とか、暗号の基礎ってどういう学部で習うの？

>>162
漏れ工学部情報学科だけど、専門の講義で普通に習ったよ。

>>160
受け取る方は素数のペアを知っている。

>>161
>>164
あー。そういうことかー。
解読鍵がつまり二つの素数か。

>>165
もう少し正確に言うと、2つの素数を基に別の数を2つ作る。その一方が
秘密鍵で、もう一方が公開鍵となる。秘密鍵および公開鍵を作る計算式
については以下のページなどを読んでくだされ。
「http://ja.wikipedia.org/wiki/RSA暗号#.E9.8D.B5.E7.94.9F.E6.88.90」

>>156
7とか13が答えだったりするかもしれないっしょw

sizeof(int)=2048 くらいのPCでないと計算できないか？

>>166
俺、公開鍵の話さえ分かってなかったわ・・＾＾：
いやー勉強になった。

3*17=51

これをどう利用するんだ？

わかんねーよ
わかりやすーい数字で説明してくれよ

>>4
ｋｗｓｋ！！！！！！！！！！！！！！！！！！！！！！！

http://pgp.iijlab.net/crypt/rsa.html
ここが分かりやすそうだが…長い。厳しいｗｗ

ここも参照だ
http://x68000.q-e-d.net/~68user/net/rsa-1.html

すげーな、みんな数学得意なのか

もっと桁を縮めて説明してくれ
みづらい

素数3と17
3*17＝51(公開鍵の一部)　


４（平文）

4の7乗＝16384
16384÷51＝余り13

１３（暗号文）


(3-1)*(17-1)=32　秘密

n*7÷32　あまり1になる数字が秘密鍵　 23*7÷32＝あまり1なのでこの場合は23


13の23乗＝41753905413413116367045797

41753905413413116367045797÷51余り4


４が復号できた

http://www.segausers.gr.jp/sug/rc5/naze-rc5.html
なぜなに RC5

>>177
おお。
秘密鍵の部分がよくわからんな。
寝よっと。

http://www.maitou.gr.jp/rsa/
猿にも分かるRSA暗号

11を暗号化する

11の7乗÷51＝余り20　11が20に暗号化された

20の23乗÷51＝余り１１　20を11に解読した


７と５１＝公開鍵（暗号化用）
２３＝秘密鍵（解読用）

3をp、17をq、3*17=51をNとする。

まず L を求める。L は p-1 と p-1 の最小公倍数。
L = lcm(p-1、p-1) = 16

次に E を求める。E は L と互いに素でなければならない。
E = 5 とする。

★この、E=5 と N=51 が公開鍵。これを相手に教える。

次にDを求める。Dの条件として、 E*D を L で割った余りが1でなければならない。
D=13 とすると E*D = 5*13 = 65 となり、L=16 で割ると余りが1になる。

★この、D=13 と N=51 が秘密鍵。これは自分が保管する。

・公開鍵で暗号化
暗号化する平文は、Nより小さくなければならない。
Nより大きい場合は、分割して暗号化する。
ここでは例として、20という数字を暗号化する。

平文をE乗してNで割った余りが暗号文。
つまり、20^5=3200000 これを51で割ると商は62745で余りが5
20を暗号化すると5になる。

・秘密鍵で複合化
暗号化した平文をD乗してNで割った余りが平文になる。
つまり、5^13=1220703125 これを51で割ると商は23935355で余りが20
5を複合化すると元の20になった

こういう事をとんでもなくデカイ数字でやってる。
公開鍵も秘密鍵も、pとqとNから作られてるわけだから、
pとqとNが分かればいい。
Nは公開鍵として誰でも知る事が出来るので、
このNを作ったpとqが分かれば暗号は解ける。
でも、これ(Nの素因数分解)ができないからRSA暗号は安全。

RSA考えた３人（だったか？）はすげーな。真の天才

間違った＞＜

>>182
まず L を求める。L は p-1 と p-1 の最小公倍数。
L = lcm(p-1、p-1) = 16

↓↓↓↓
まず L を求める。L は p-1 と q-1 の最小公倍数。
L = lcm(p-1、q-1) = 16

>>181
暗号化するときの計算方法まで公開してるの？
なら公開鍵で復号できちゃうよね？
あーまたよくわからんくなってった

なんかわかった気がする！！
気がするだけかもしれないけど

>>187
公開鍵7と秘密鍵23は「7*23 = 32*5 + 1」という関係を持つ。
32は51=3*17から(3-1)*(17-1)を計算したもの。つまり、
公開鍵7から秘密鍵23を計算するには32を知る必要があり、
その32を知るには51を3と17に分解する必要がある。

そういう仕組みなんだ。ぼんやりと理解した。
おもしろいね。

うちのPentium130だとこの程度なら0.5秒かからないな

>>187
７乗じゃ失敗だったわ　

11乗で


６を暗号化する

６の11乗÷51＝余り３９　6が39に暗号化された

39の3乗÷51＝余り６　39を6に解読した

（公開鍵では解読できない　39の11乗÷51＝余り４５）



１１と５１＝公開鍵（暗号化用）
３＝秘密鍵（解読用） 秘密鍵の３は51の元の素数ふたつが分ってれば簡単にわかる

まぁでもRSAの仕組みそのものは理解しても何の役にも立たないね。
もし興味があるなら、一歩進んでSSLとかのネットワーク関連の仕組みを理解すべし。

>>193　
SSL？　機関車トーマスとか？

>>189

ｘの７乗≡１３　mod　51

みたいな感じでｘは出せないの？７と51は公開されてるんだよね？

>>192
同じように、

ｘの11乗≡39　mod 51

は解けないの？

この分野は中国が有力なんでしょ？

量子コンプーターで破られるとかなんとかはどうなの？現実的なの？

元の数を素数で割りまくったらいいんだろ？ｗ

そういえば一方向性関数とか習ったなぁ