RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号とデジタル署名を実現できる方式として最初に公開されたものである。発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの頭文字をつなげてこのように呼ばれる。(By wikipedia)
簡潔に言うと「桁数が大きい合成数の素因数分解を用いた公開鍵暗号」ってことになります。
公開鍵→暗号化するための鍵
秘密鍵→復号化するための鍵
この公開鍵で暗号化し、秘密鍵で複号化します。なので秘密鍵が分かれば復号できることになります。
実践
とりあえず「PENGUIN」を暗号にしてみます。
この変換表を使って、P→16、E→05、N→14、G→07、U→21、I→09、N→14、繋げると16051407210914。。。。。長いｗ
ってことで、1文字ずつ暗号化します。
２つ素数を決める。今回はp＝3、q=11にしました。(理由はエクセルで計算するときに大きい数では桁数が大きくなりすぎるから。)
PQ=(p-1)(q-1)+1 を満たす整数P、Q見つけ鍵とする。
PQ=(3-1)(11-1)+1=21 なのでP＝7、Q＝3
暗号化する文字をXとして、XのP乗 mod pq で暗号化。
エクセルでは =MOD(X^P,pq) で計算。なので1文字目はP→16なので、=MOD(16^7,33) ＝25
同じように、E→05→14、N→14→20、G→07→28、U→21→21、I→09→15、N→14→20繋げると25142028211520になります。
これをX’のQ乗 mod pq で復号化すると、=MOD(25^3,33) ＝16 になります。
全部繋げて16051407210914を変換表でアルファベットに戻すと、PENGUINにちゃんと戻ります。
おまけ
サマーウォーズでケンジ君が解いた暗号がこちら。
814381625757888867669235779923577997614666120182967212423625362561842935706935245733897830597123563958705058989075149759929002687954354162959592635382962929999373527393893015272028273730979383739039731352452762289782738269898221546122131360619421303021411333103461918121612113166613120121314764123131664436383883993965356373934846376383933154328878976238398563738365433423534644888463839384643839396476573748938457345564245126348446687582487268268599929226493922762658492645161381238929910492254753685216544526687633169497562621466262164751662165496216233621461156486215622262254897462256624662062148316547254564902302454621245456232245162312424565124345181640126512518124243216518454246124324649155489615622654043145149481612161465225465454643245189159164648464546424211515912121512512462155666156124173641635467148361593823787985896185613764728526928789895656425257381651935613893981991374836873823541837167837898784e765434576345637173823138479813768765238613741311236937264827654778277325473898928152422542515522536131313315113131436465191945461216494600604573790464767487277872182954748299792393745245635321521251762851642417215462185215216524128156631535133635135624373234146484945914624245144655937545243151552364728646254632586421653765268752146364216452966051582166316165298691556167867525411656512513466425667026216616514563466741256352312000214153442514256547456176523156416857441156514555136515571345216351461342355314575145551352534665275245434123524164512514854135513552515115617195661675681735681361373613725382416248275264278352381658327184562416554631567452166375415676516659156451553145235234613252553232516852127126451621572321315221367251321433642212341623226546564323221637261423214278263167424542351254254143654215461524423554259418149422453565065652624639606225635206461462565251661258214063232062267640333141325426372633225334823727365243212325634253834253324362370285630743325310023223052360452321456631647857143521514557163023223522423243624702260270285607962516432235723674724715613526215523165518237142314221623715637261634153471
(もう意味が分かりませんｗｗｗ)
そして答えがこちら。
the magic words are squeamish ossifrage To know is to know that you know nothing That is the true meaning of knowledge
これは前半の「the magic words are squeamish ossifrage」魔法の言葉は気難しいヒゲワシと、後半の「To know is to know that you know nothing That is the true meaning of knowledge」知るを知るとなし、知らざるを知らずとなす。これ知なり に分けられる。
前半はヒゲワシは骨折りという感じらしいので、骨折り損みたいな感じになるのかな。「はい、おつかれ。」みたいなニュアンスですかね。
後半は論語の一説で、「子曰、由誨汝知之乎、知之為知之、不知為不知、是知也」子曰く、由や、汝に知ることを誨えん乎、之れを知るを知ると為し、知らざるを知らずと為す、是れ知る也。
これをメールで送られてきたから”つい”で解いてしまうケンジ君は計算力オバケですね。生年月日聞いて曜日を即答できる時点で？？？ですけどね。モジュロ演算で・・・って。
僕、高校時代モジュロ演算って言葉すら知りませんでしたが？ｗｗ
今なら、「OK、Google。平成4年7月19日は何曜日？」で解決です。
ではまたー。
コメント