配布されたファイルには、公開鍵が 2 つ記載されています。鍵は ssh-rsa で始まっていることから、これは RSA 暗号の公開鍵であることがわかります。 RSA 暗号の公開鍵は 2 つの巨大な素数の積 N と正整数 e であるので、配布ファイル内の文字列の中身は N と e であるはずです。この中身は、ssh-keygen と openssl を用いて次のように確認することができます。
ssh-keygen -f authorized_keys -e -m pem | openssl asn1parse
配布された 2 つの RSA 鍵は、どちらも e=65537 であり、
N_1 = 0xC639FBB7CD3D59056F97581B1325002E939F815F07EF6EA9281FCBC2F2FA9BA760568EC447057F124A53F68B4632374DCF5245E4A915E997C3B888117CA4BD66B0D03A9123A907A92261BF38C3CA98FCCC1932870EEEF925BF06F0752C3D60B0F4E6C2935E65AEBE306818F614F8560A731C6D36298FF1E99607220BACBAE1B914AC0F68512DA2B67390B10B723159C7CF14E3F5BFD42A14388A684689DEF8D451F40F47B3421A579A4F2DADBFF72F8130FDF37C974AB22C6A2E7B4796F820BA6DCB2F18F8AE0495977907EEC7E2B66A638876239487063D18DD94E9A41F0F5D9383D3424B3E0C9C6424F8F62A485E27A64BFE563161F5356736E9F9A0EF24C3 N_2 = 0xBC317397BE63923F3F9964317FE9AA18470BA3AAF61D9645737DBDB8F63352C75604AA925718E753253F80D6DAE813CAD87D334C45BEA2EC71B301FF9861542B63F2305DA95B236C4C5C36A18CDEEFC19CF1026A32A58E7D93720562362E64608AF4E3035FE35AE3148F6E49AF4A43E6D62DF48676339CBC29FBCA0F228A8F73B0D8D5547F5008777C804D0F1E9AA1080421B313783C88CB860D3D15AF28AD0DCEFBE9C10F5A694F3593B84CB66EBFA14E8F35F9A0B1906C0F3B65CE27448D2EB461DADE9E4F65171F45C1575784BE471BFDAB396B1999DF50C031CA36DF15692BA9CD6E88EF9ED89D406222F1F953D0B8F339BEE810DC9DBA54541E9B9F3679
であることがわかりました。
この 2 つの公開鍵の最大公約数を計算すると、
import math g = math.gcd(N_1, N_2) print(g) # >>> 146199440685444178260979326893288019338307102201557391434948689574963647867073506265752427693789767228479266339751235882633334962479609642833466066081486469859567233369991915988185809209433919017931787443059027238864012947592628105101020439680918501898580846218283794103074923391198463354987324743403777701657
となり、公開鍵の約数が計算できました。もう片方の素数も N//g で計算できるので、この公開鍵は素因数分解が可能な脆弱な鍵であることがわかります。素因数分解に成功したので、公開鍵から秘密鍵を復元することが可能です。rsatoolを用いて、2 つの素数から秘密鍵を作成します。
python rsatool.py -f PEM -o recovered.pem -p 146199440685444178260979326893288019338307102201557391434948689574963647867073506265752427693789767228479266339751235882633334962479609642833466066081486469859567233369991915988185809209433919017931787443059027238864012947592628105101020439680918501898580846218283794103074923391198463354987324743403777701657 -q 171161920207792057888566796008797123983057159125475670689947270586630302604472850037039182234292393880575407233851070873370865944604141107756026727206963374884069036469828776842358778043951047976508308819895143328858144186323611182236281322442990536395752920340883175225691985872270657853103548846255326380603
FLAG を取得するためにはこの鍵の持ち主を特定する必要があります。個人の公開鍵がもっとも多く登録されている場所といえば、おそらく GitHub でしょう。 GitHub では、SSH による接続テストを行うことが可能です 上記で復元した鍵を用いて、GitHub に接続を試みます。
chmod 600 recovered.pem ssh -i recovered.pem git@github.com # >>> Hi Ann0nymusTsukushi! You've successfully authenticated, but GitHub does not provide shell access.
この鍵はAnn0nymusTsukushiというユーザーが使用していることがわかりました。 このユーザーのプロフィールにアクセスすると、base64 エンコードされた FLAG が記載されています。
In the distributed file, you can find 2 public keys. They must be RSA public key because they start with ssh-rsa. RSA public key is consist of N, which is a product of 2 primes, and e. You can check the actual values by following.
ssh-keygen -f authorized_keys -e -m pem | openssl asn1parse
Now you know the values of distributed public keys. Both e are 65537, and N are
N_1 = 0xC639FBB7CD3D59056F97581B1325002E939F815F07EF6EA9281FCBC2F2FA9BA760568EC447057F124A53F68B4632374DCF5245E4A915E997C3B888117CA4BD66B0D03A9123A907A92261BF38C3CA98FCCC1932870EEEF925BF06F0752C3D60B0F4E6C2935E65AEBE306818F614F8560A731C6D36298FF1E99607220BACBAE1B914AC0F68512DA2B67390B10B723159C7CF14E3F5BFD42A14388A684689DEF8D451F40F47B3421A579A4F2DADBFF72F8130FDF37C974AB22C6A2E7B4796F820BA6DCB2F18F8AE0495977907EEC7E2B66A638876239487063D18DD94E9A41F0F5D9383D3424B3E0C9C6424F8F62A485E27A64BFE563161F5356736E9F9A0EF24C3 N_2 = 0xBC317397BE63923F3F9964317FE9AA18470BA3AAF61D9645737DBDB8F63352C75604AA925718E753253F80D6DAE813CAD87D334C45BEA2EC71B301FF9861542B63F2305DA95B236C4C5C36A18CDEEFC19CF1026A32A58E7D93720562362E64608AF4E3035FE35AE3148F6E49AF4A43E6D62DF48676339CBC29FBCA0F228A8F73B0D8D5547F5008777C804D0F1E9AA1080421B313783C88CB860D3D15AF28AD0DCEFBE9C10F5A694F3593B84CB66EBFA14E8F35F9A0B1906C0F3B65CE27448D2EB461DADE9E4F65171F45C1575784BE471BFDAB396B1999DF50C031CA36DF15692BA9CD6E88EF9ED89D406222F1F953D0B8F339BEE810DC9DBA54541E9B9F3679
And if you calculate GCD of those Ns, you will see that it is not 1.
import math g = math.gcd(N_1, N_2) print(g) # >>> 146199440685444178260979326893288019338307102201557391434948689574963647867073506265752427693789767228479266339751235882633334962479609642833466066081486469859567233369991915988185809209433919017931787443059027238864012947592628105101020439680918501898580846218283794103074923391198463354987324743403777701657
This is the prime itself. Now you can factorize given public keys, which means you can create private keys from public keys. rsatool is a great tool to do that.
python rsatool.py -f PEM -o recovered.pem -p 146199440685444178260979326893288019338307102201557391434948689574963647867073506265752427693789767228479266339751235882633334962479609642833466066081486469859567233369991915988185809209433919017931787443059027238864012947592628105101020439680918501898580846218283794103074923391198463354987324743403777701657 -q 171161920207792057888566796008797123983057159125475670689947270586630302604472850037039182234292393880575407233851070873370865944604141107756026727206963374884069036469828776842358778043951047976508308819895143328858144186323611182236281322442990536395752920340883175225691985872270657853103548846255326380603
What you have to do next is to find who has this private key. Generally speaking, programers have their own GitHub accounts, and register their public keys. You can test a connection to GitHub by using SSH. Let's test the connection with the recovered key.
chmod 600 recovered.pem ssh -i recovered.pem git@github.com # >>> Hi Ann0nymusTsukushi! You've successfully authenticated, but GitHub does not provide shell access.
GitHub says that this key is used by a person named Ann0nymusTsukushi. The FLAG is in the top page of this account (written in base64 format).