[ksnctf] https is secure.

環境： 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でファイルを開いてみる

https://www.wireshark.org/docs/wsug_html_chunked/ChUseStartSection.html

https://knowledge.sakura.ad.jp/6286/

__２．データの流れを見てみる__(表示フィルタ :__tcp.port==443__,レコード :__No.4 ~ No.12__ )
![packet](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/34bef2b6-8c21-75fd-e1f1-9a3cd977cf3a.png "packet")
そもそもこれって何してるの？
　→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 Hello](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/80ab977a-f784-6190-16c8-4eaa5a7b2d41.png)
　Client「ハロー、TLS1.0でやりますよー、暗号化方式はこの中のどれかで頼むよー」


 __２-２.Server Hello__
![Server Hello](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/0fadd9f4-a100-5912-0a14-8f196079f919.png)
　Server「ハロー、TLS1.0了解～
　　　　　公開鍵暗号方式はRSA
　　　　　共通鍵暗号方式はRC4の128bit
　　　　　ハッシュはMD5にするよ～」


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


 __２-４.Client Key Exchange__
![Client Key Exchange](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/04ed1a71-e79e-2bfd-99cc-04c24278f821.png)
　Client「暗号化したプレマスターシークレット送りました」
　　※プレマスターシークレット・・・クライアントが生成した乱数、後のマスターシークレットになるもの。
　　※マスターシークレット・・・暗号化に使用するセッション鍵を生成するための情報。サーバがこれを検証した後、共通鍵を生成する。

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

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

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

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

https://troushoo.blog.fc2.com/blog-entry-357.html

![GET sertificate](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/74c746c4-4b45-1b83-e0cb-21bccc56e293.png)
No.7の証明書のパケットバイト列をエクスポート。No.76の証明書のパケットバイト列も同様にエクスポート（皆さんはわざわざエクスポートしなくてもよいです。同じ公開鍵ということが分かればokです）
![sertificate.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/32660b72-15b9-2493-62f8-09dc57777756.png)
__まったく同じ証明書であることが判明、つまり秘密鍵１つで２つの暗号データを復号できる__
　step2 :moduluの値を取得
　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/5d843a68-299b-3f1e-55cf-f5bc527452ce.png)
step3 :この値をコピーして１０進数に変換する。No.7(証明書１とする)のmoduluをx1とし、No.76(証明書２とする)のmoduluをx2とする。
[変換サイト](http://hogehoge.tk/tool/number.html)

---
__５．秘密鍵生成します__
その前に、、、
#RSA暗号とは
https://inaz2.hatenablog.com/entry/2013/11/27/225953

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

```
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$ __:__ 暗号文)
　    <ul><li>$c = m^e mod n $</li>
      <li>$ m = c^d mod n $</li>
          <ul><li>この式を作るために$e$,$d$,$n$ を作る</li>
              step1.素数$p$,$q$を作る
              step2.$n$ = $p$ $×$ $q$
              step3.$e = 65537 $(0x10001)
              step4.$d$ = $e^-1$ $mod$ $(p-1) * (q-1)$
         </ul>
  </ul>  
--
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形式のファイル、ちょっとおかしいのでいじらないといけません。（僕だけかもしれませんが）
![vscode.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/79e3f76c-4a2b-e231-d572-86a1668fee60.png)
僕はなぜかこの形で生成されるので手直ししないといけません・・・（泣）
![occurrences.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/e832afe9-55b2-5f3d-d559-ef0240010ee4.png)
¥nという改行に使う文字をすべてクリアします
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/b88d0702-e08b-23f9-4ac5-b55cf09f3999.png)
そして１行６４文字になるように改行してください。
Base64でエンコードされているのですが、デコードする際に１行６４文字でないと以下のようなエラーを吐くからです。

```
error:0906D064:PEM routines:PEM_read_bio:bad base64 decode
```
```
$ python3 cipher2.py > private_2.pem
```
cipher2.pyからも同様に秘密鍵生成して、手直ししていきましょう。

---
__７．Wiresharkのほうに秘密鍵をインポートしてデータを盗聴しましょう！__
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/1edee67c-3720-3b10-2ad2-ce50ff4798fc.png)
No.7のRSA Keys listから
![keyslist.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/28eb8dc3-2a39-bc44-8afa-2bddf9179617.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/11e3c59b-b084-8e89-34aa-5e96e53795e4.png)
盗聴成功～～！！写真をやり取りしてるみたい。見てみよう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/1c3af6a8-c616-7e98-9e14-b7da4e2c8041.png)
なるほど。。。写真として保存しないといけないみたい。

---
__８．エクスポートしよう__
Wireshark ファイル→オブジェクトをエクスポート→HTTP
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/4f29ac0d-d95c-46e1-3212-84226e0e5405.png)
保存して開いてみる。

---
__９．Submit!!__
![flag_success.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2153604/108d0544-4c84-fb2d-3e4a-f2090408e815.png)
お疲れさまでした。