環境： Ubuntu 16.04.7 LTS
使用ソフト： VScode,Wireshark
使用言語： python3 ( pip3 list : pycryptodome )
$ pip3 install pycryptodomeでinstall可能です
参考URL：適宜記載します
できるだけ細かく書くので長くなると思います。

問題文

Decrypt it.
q33.pcap
Hint:Two certificates are similar.

１．pcapっていうのはWiresharkが作ったデータファイルのこと
　 →Wiresharkでファイルを開いてみる

２．データの流れを見てみる(表示フィルタ :tcp.port==443,レコード :No.4 ~ No.12 )

そもそもこれって何してるの？
　→HTTPS通信における、TLSハンドシェイクです
ハンドシェイクって？
　→TLS通信を開始する前にサーバとクライアントで暗号通信に必要な情報を交換すること

HTTPS通信のTLSハンドシェイクの流れ

1.(No.4)Client :Client Hello
    2.(No.6)Server :Server Hello
        3.(No.7)Server :Certificate,Sever Hello Done
            4.(No.9)Client :Client Key Exchange
                5.(No.9)Clinet :Change Cipher Spec,Encrypted Handshake Message
                    6.(No.11)Server :Change Cipher Spec,Encrypted Handshake Message

２-１.Client Hello

　Client「ハロー、TLS1.0でやりますよー、暗号化方式はこの中のどれかで頼むよー」

２-２.Server Hello

　Server「ハロー、TLS1.0了解～
　　　　　公開鍵暗号方式はRSA
　　　　　共通鍵暗号方式はRC4の128bit
　　　　　ハッシュはMD5にするよ～」

２-３.Certificate,Server Hello Done
　Server「証明書送っときます～」

２-４.Client Key Exchange

　Client「暗号化したプレマスターシークレット送りました」
　　※プレマスターシークレット・・・クライアントが生成した乱数、後のマスターシークレットになるもの。
　　※マスターシークレット・・・暗号化に使用するセッション鍵を生成するための情報。サーバがこれを検証した後、共通鍵を生成する。

２-５.Change Cipher Spec
　Client「それでは暗号化通信に切り替えます」

２-６.Chenge Cipher Spec
　Server「それでは暗号化通信に切り替えます」

３．実際にどうやって解いていく？
　　→重要なデータを復号すればよい

４．どこの情報を見たらよい？
　　→公開鍵
　　　step1 :２つの証明書を抽出する

No.7の証明書のパケットバイト列をエクスポート。No.76の証明書のパケットバイト列も同様にエクスポート（皆さんはわざわざエクスポートしなくてもよいです。同じ公開鍵ということが分かればokです）

まったく同じ証明書であることが判明、つまり秘密鍵１つで２つの暗号データを復号できる
　step2 :moduluの値を取得
　　
step3 :この値をコピーして１０進数に変換する。No.7(証明書１とする)のmoduluをx1とし、No.76(証明書２とする)のmoduluをx2とする。
変換サイト

５．秘密鍵生成します
その前に、、、

RSA暗号とは

この記事にお世話になったので、皆様にもお勧めします。
要約すると、以下の値を使って暗号化・復号するということ。

modulus           n = p*q
publicExponent    e = 65537 (=0x10001)
privateExponent   d == e^(-1) mod (p-1)*(q-1)
prime1            p
prime2            q

公開鍵 :modulus, publicExponent
秘密鍵 :modulus, privateExponent

定義：
>>>message = struct.unpack('>I', 'BEEF')[0]//BEEFという文言を暗号化する
>>>hex(message)
'0x42454546'
>>>modulus = 3243485389
>>>publicExponent = 65537
>>>privateExponent = 2834145457
暗号化：
>>>ciphertext = pow(message, publicExponent, modulus)//公開鍵で暗号化(m^e mod n)
>>>ciphertext
2545199955

>>> message2 = pow(ciphertext, privateExponent, modulus)//秘密鍵で復号(c^d mod n)
>>> hex(message2)
'0x42454546'
>>> struct.pack('>I', message2)
'BEEF'//BEEFという文言を受け取れた

　RSA暗号を解くために以下のステップを踏む
　($m$ : 平文,$c$ : 暗号文)
　

$c = m^e mod n $

$ m = c^d mod n $

この式を作るために$e$,$d$,$n$ を作る

-- step1.素数$q$を作ります。証明書１から得たx1、証明書２から得たx2、これらは以下の式で表せます $x1 = p1 * q1 $ $x2 = p2 * q2 $ >Hint:Two certificates are similar.

この問題文から、共通の因数を持っていると推測、共通の因数$q$として式を改めます
$x1 = p1 * q $
$x2 = p2 * q $
$q$の値を求めます

q.py

def gcd(x1, yx2):
    r = x1 % x2
    while r != 0:
        x1 = x2
        x2 = r
        r = x1 % x2
    return x2

def main():
    x1 = 209120684085715623297656905550611592896416292850824042101891010649543309533155932575572600775259151526410731063974315568756803936393019952315404096006330567904072176441094793758110259520605402767141198422919725322686868116484764![q.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/d492c8d3-c27b-7614-0576-ea4390bade41.png)
77127818267411283106601195166099848608860814911133056759210847640244371352294577674757844032344743192797680553522630615249481210459669536735468283778508143359159893770374788694416907786510825727199111604249000530550012491935109887922826382346971222271516625157446929215544796309806757863550058676780306722906895167581167203804721314732494889662194466565293268848629536070864750745494338531
    x2 = 20810915617344661448636429656557804394262814688853534649734586652859523797380885650024809244693377123486154907319690068259378744245911427062593140588104970879344505836367952513105241451799550533959908906245319537215140226739848280012005678383612764589285444929414256249733809498630880134204967826503346173071037885178145189051140796573786694250069189599080301164473268293037575740360272856085402928759232391893060067823996007021668671352199570084430112300612196486186252109596457909476374557998336186613887204545677563178904634941310201398366965571422359228917354256271527331840144577394174480450746748283277750230727

    q = gcd(x1, x2)
    print (q)

if __name__=="__main__":
    main()

q = 149964660518396798660782215517197000054264985822608779681144262791391323000835825727277636178043097046988857828384650158626906824855399961360412435818827649355003329726451846544435103030378220357694459358803967598155925736581896165952170564324730092516286266118841005062382011803493961966912439338500328959743

このqを使ってp1とp2を求めます。
$ x1 = p1 * q $だったので$x1$と$q$が分かっていれば
$ p1 = x1 / q $で$p1$が求まります。

p.py

p1 = x1 / q
p2 = x2 / q

p1 = 139446642537534304777628614240154046272434122794892522124374234093313897652592278876204620931659231555942782873768406065030569534203407105601097455479995730772421725109267044663491213232687718387909353507690622331780468229128999879032054673690005684809410661625656125511253714586807242182927209779610158700317
p2 = 138772131683595539379264396620735603425702925342291987755841498194704959931781364169698055070785331880014332847610595576230231417278730047109315439655930883451174914691703480278864120207968103099432047374677543229331540706277526947368767969434429565383119554767303697722958157645742281397722992120606265055289

これで$p$と$q$が求まりました
step2.$n$ = $p$ $×$ $q$
　　　ということで証明書１の$n$を$p1 * q$
　　　　　　　　　証明書２の$n$を$p2 * q$とします
これで$n$が求まりました
step3.$e = 65537$とします。一番計算しやすい値だからです。
６．秘密鍵生成します

cipher1.py

from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, long2str, long_to_bytes

p1 = 139446642537534304777628614240154046272434122794892522124374234093313897652592278876204620931659231555942782873768406065030569534203407105601097455479995730772421725109267044663491213232687718387909353507690622331780468229128999879032054673690005684809410661625656125511253714586807242182927209779610158700317
q = 149964660518396798660782215517197000054264985822608779681144262791391323000835825727277636178043097046988857828384650158626906824855399961360412435818827649355003329726451846544435103030378220357694459358803967598155925736581896165952170564324730092516286266118841005062382011803493961966912439338500328959743
e = 65537

n = p1*q
phi = (p1-1)*(q-1)
d = inverse(e,phi)

key = RSA.construct(map(int, (n,e,d)))
print(key.exportKey())

これで秘密鍵を生成できるのですが、実は秘密鍵はpem形式のファイルにしないといけないのでファイル作ります

$ python3 cipher1.py > private_1.pem

このpem形式のファイル、ちょっとおかしいのでいじらないといけません。（僕だけかもしれませんが）

僕はなぜかこの形で生成されるので手直ししないといけません・・・（泣）

¥nという改行に使う文字をすべてクリアします

そして１行６４文字になるように改行してください。
Base64でエンコードされているのですが、デコードする際に１行６４文字でないと以下のようなエラーを吐くからです。

error:0906D064:PEM routines:PEM_read_bio:bad base64 decode

$ python3 cipher2.py > private_2.pem

cipher2.pyからも同様に秘密鍵生成して、手直ししていきましょう。

７．Wiresharkのほうに秘密鍵をインポートしてデータを盗聴しましょう！

No.7のRSA Keys listから


盗聴成功～～！！写真をやり取りしてるみたい。見てみよう。

なるほど。。。写真として保存しないといけないみたい。

８．エクスポートしよう
Wireshark ファイル→オブジェクトをエクスポート→HTTP

保存して開いてみる。

９．Submit!!

お疲れさまでした。