namdicul's blog

気ままに更新します. CTFと暗号理論について勉強中です.

"Cpaw CTF" Q29.[Crypto] Common World

Cpaw君は,以下の公開鍵を用いて暗号化された暗号文Cを受け取りました.しかしCpaw君は秘密鍵を忘れてしまいました.Cpaw君のために暗号文を解読してあげましょう. 

(e, N) = (11, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577) 

暗号文: 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904 

これは…? 

フラグは以下のシンタックスです. 
cpaw{復号した値} 

※復号した値はそのままで良いですが,実は意味があります,余力がある人は考えてみてください

Answer:

 

今回はRSA暗号を使って暗号化したものを復号するのが目的です. 

その前に, RSA暗号について理解が曖昧だったので, まずRSA暗号について説明したいと思います. 

 

以下, Wikipediaから引用.

RSA暗号は次のような方式である: 鍵ペア(公開鍵と秘密鍵)を作成して公開鍵を公開する。まず、適当な正整数 e(通常は小さな数。(65537 = 216 + 1) がよく使われる)を選択する。また、大きな2つの素数 {pq} を生成し、それらの積 n (=pq) を求めて、{en} を平文の暗号化に使用する鍵(公開鍵)とする。2つの素数 {pq} は、暗号文の復号に使用する鍵(秘密鍵d の生成にも使用し ()、秘密に保管する。

  • 暗号化(平文 m から暗号文 c を作成する): 
  • 復号(暗号文 c から元の平文 m を得る): 

ここで、暗号化(e 乗)は、{en } があれば容易に計算できるのに対して、復号(e 乗根)は、「n の素因数を知らないと難しい(大きい合成数素因数分解も難しい)」と考えられている。つまり秘密鍵を用いずに暗号文から平文を得ることは難しい、と信じられている。これがRSA暗号の安全性の根拠である。

 また, RSA暗号についてはここでも簡潔に説明されています.  

 

 RSA暗号については後々別の記事で説明したいと思いますが, こちらのプログラムとこちらの解説記事が参考になりそうですね.