この大会は2021/4/10 2:00(JST)~2021/4/11 2:00(JST)に開催されました。
今回もチームで参戦。結果は361点で349チーム中97位でした。
自分で解けた問題をWriteupとして書いておきます。
Backup - alice (crypto)
Aliceの公開鍵をPEM形式に変換し、内容を確認する。
$ ssh-keygen -f authorized_keys -e -m PKCS8 > alice.pub.pem $ openssl rsa -pubin -text < alice.pub.pem RSA Public-Key: (2048 bit) Modulus: 00:ef:f5:f6:00:0d:d4:23:63:b1:13:4a:2f:b9:38: 3c:57:98:ed:9c:28:94:6e:e3:32:fb:b3:8c:86:1c: b3:17:57:29:30:dc:fe:cf:90:f3:98:27:5f:10:d1: 06:76:9a:de:a1:69:c1:35:67:0d:76:52:68:9b:82: 31:0d:57:81:8f:47:41:91:fb:f3:7f:35:9f:2d:d1: 5b:62:d2:15:7e:46:3d:ce:42:28:f4:fd:6e:11:33: ea:61:4d:29:a7:03:d2:b3:e2:3d:b8:64:c3:67:40: 03:25:ec:c6:8e:4a:31:d1:37:ed:53:13:8a:c4:4d: 30:4c:a7:22:b2:95:8b:b4:d5:a1:9b:2d:bc:c1:04: 27:16:f9:87:99:2e:10:32:60:5d:45:a0:bc:97:8d: 21:31:ea:e7:03:14:d1:3e:b9:df:08:ad:05:ad:b3: 87:79:d2:d5:85:1d:f8:9c:47:3b:a5:7e:c9:6e:a3: f0:f5:44:8b:5a:b0:30:f1:ea:bb:59:51:20:2a:5a: 62:d6:c3:f5:ee:4e:6b:c4:e2:09:14:d4:7b:06:8b: d8:cc:9c:5a:c0:57:8b:32:fe:cf:b4:8d:6c:be:18: 7f:fc:5f:b4:35:6e:07:f1:99:7f:47:7c:65:b7:aa: 73:bf:29:ce:5e:16:a5:fa:8b:d4:71:9c:66:c2:fd: 8c:f1 Exponent: 65537 (0x10001) writing RSA key -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA7/X2AA3UI2OxE0ovuTg8 V5jtnCiUbuMy+7OMhhyzF1cpMNz+z5DzmCdfENEGdpreoWnBNWcNdlJom4IxDVeB j0dBkfvzfzWfLdFbYtIVfkY9zkIo9P1uETPqYU0ppwPSs+I9uGTDZ0ADJezGjkox 0TftUxOKxE0wTKcispWLtNWhmy28wQQnFvmHmS4QMmBdRaC8l40hMernAxTRPrnf CK0FrbOHedLVhR34nEc7pX7JbqPw9USLWrAw8eq7WVEgKlpi1sP17k5rxOIJFNR7 BovYzJxawFeLMv7PtI1svhh//F+0NW4H8Zl/R3xlt6pzvynOXhal+ovUcZxmwv2M 8QIDAQAB -----END PUBLIC KEY-----
n = 0x00eff5f6000dd42363b1134a2fb9383c5798ed9c28946ee332fbb38c861cb317572930dcfecf90f398275f10d106769adea169c135670d7652689b82310d57818f474191fbf37f359f2dd15b62d2157e463dce4228f4fd6e1133ea614d29a703d2b3e23db864c367400325ecc68e4a31d137ed53138ac44d304ca722b2958bb4d5a19b2dbcc1042716f987992e1032605d45a0bc978d2131eae70314d13eb9df08ad05adb38779d2d5851df89c473ba57ec96ea3f0f5448b5ab030f1eabb5951202a5a62d6c3f5ee4e6bc4e20914d47b068bd8cc9c5ac0578b32fecfb48d6cbe187ffc5fb4356e07f1997f477c65b7aa73bf29ce5e16a5fa8bd4719c66c2fd8cf1
いろいろやってみたがnを素因数分解できない。RsaCtfTool.pyを使うことにする。
$ RsaCtfTool.py --publickey alice.pub.pem --private [*] Testing key alice.pub.pem. [*] Performing fibonacci_gcd attack on alice.pub.pem. 100%|███████████████████████████████████| 9999/9999 [00:00<00:00, 14700.82it/s] [*] Performing mersenne_primes attack on alice.pub.pem. 100%|██████████████████████████████████████████| 51/51 [00:09<00:00, 5.63it/s] [*] Performing smallq attack on alice.pub.pem. [*] Performing system_primes_gcd attack on alice.pub.pem. 100%|██████████████████████████████████| 2353/2353 [00:00<00:00, 113414.28it/s] [*] Performing factordb attack on alice.pub.pem. [*] Attack success with factordb method ! Results for alice.pub.pem: Private key : -----BEGIN RSA PRIVATE KEY----- MIIEogIBAAKCAQEA7/X2AA3UI2OxE0ovuTg8V5jtnCiUbuMy+7OMhhyzF1cpMNz+ z5DzmCdfENEGdpreoWnBNWcNdlJom4IxDVeBj0dBkfvzfzWfLdFbYtIVfkY9zkIo 9P1uETPqYU0ppwPSs+I9uGTDZ0ADJezGjkox0TftUxOKxE0wTKcispWLtNWhmy28 wQQnFvmHmS4QMmBdRaC8l40hMernAxTRPrnfCK0FrbOHedLVhR34nEc7pX7JbqPw 9USLWrAw8eq7WVEgKlpi1sP17k5rxOIJFNR7BovYzJxawFeLMv7PtI1svhh//F+0 NW4H8Zl/R3xlt6pzvynOXhal+ovUcZxmwv2M8QIDAQABAoIBAHk8BFCcq/xBRtqf FaN3pQ0Ax7Oo0O2BPmXqnem4IEd/kuEMFnUaH+hUo/QkFybfMfHNM39elG+eTRmc WloKRvvznU47RBeWKNkGOCyiRZept1o5FOZKEE0CtLz6Njwac17MxDAgQJUuwyhr CxoipC63GeFqMybgdLGVk7M0WQRAHE7J9qR9J0jHSGiiDVGpEiI4EY0GgFBy7K6P JOb97/Tbu/v8AoTtC49gl8YvOQMp6YtDoik4lbFkkKPdtpKnF3aWqYdBQCbMq8rh 16eD7mvKAN3K1Hi+LByiPOCZO2ExqXMiWBJsRVR/kr7HFpYBZvsgmMctTPxwAdel B2TxIJECgYEA8+Y6U3uYRRt1Na6FVhZANNurtzFXKLEWpmEzybRjeTa2y3hluN2e 0PBEJsrK+G36xKNIA9jiergWcGZgypGAkIm34EHI2Is0ktjifySV6gn4/BUjjLHi uAQjl/hXJpBkknluUeumLDfzKdsx5BV2GSLCBOgc7GzAYV2gRtxxCEUCgYEA+921 peoDPNommLEr2tMJPEA4dSaQa3LpEpRRtqjNFeCXo/xqQ1mBnavGFmQtLruiIqzv GeC2eJ/8Po0FQ2+Xo+zh8GDtDETfNOB7IazrzOaU8dNQzLrdiOJXjYigSiJAh3TT n5/icPwkWUFR/NvQAYoH3q2SlZyhtGGwKWE0yr0CgYB5lFGM3fZ4tIhH+zgyQqM8 9ifyCOF2wlgVFi03pflUKicS5HBop+kMJEkEwWBOWJyBuxch+9Jh9DQTUaV8NO3O nygO3Rwefb32WbEGShmE8fWwy2TONLpcmouXrM7cxWus7GVG5t4N+tH3EnIbTWty ejYXNhF89XUs0/wadrbNtQKBgFJH8enL81bT5bwIVU1dmCzIxijvekq/9YiOT8ue hbFZ9/AorAZonUGHNmVmQKR9w9AUMuB/Wt05VsyQgWGweReicYV4BLj3XvwFQfSU a0w7H/mIkWLwwSLQ3s1sDwFpAy+9aM1DDFTg6ncGMeSrYt692yhSCAs8ak9lgoli Kj75AoGAMSQ4zf4uQkMjJR19EeWZ9748og6rfUFJCZap7mwQhBntBcMfa725MrXU fyvS8xiiFAwDwEu964CxMAKo0+2r2fLDetdSBnkqWBPI0K0Vdjtd+ZfUX7Hbw31m dqwk4Flpg9j+yvsPLg/iZJQfyslmtE3zlLGVBjmUU/pag5rYeQ8= -----END RSA PRIVATE KEY-----
この秘密鍵をalice.pri.pemで保存し、この秘密鍵でSSH接続する。
$ ssh -i alice.pri.pem alice@backup-01.play.midnightsunctf.se -p 2222 midnight{factorization_for_the_Win} Connection to backup-01.play.midnightsunctf.se closed.
midnight{factorization_for_the_Win}
Backup - bob (crypto)
Bobの公開鍵をPEM形式に変換し、内容を確認する。
$ ssh-keygen -f authorized_keys -e -m PKCS8 > bob.pub.pem $ openssl rsa -pubin -text < bob.pub.pem RSA Public-Key: (2062 bit) Modulus: 23:6a:24:cd:cb:ce:cb:a5:21:04:a1:fc:e5:54:e0: d6:ed:7e:f9:e7:e8:f8:9c:b4:4c:3b:ac:a0:a6:00: 78:2e:7d:b7:81:41:67:0c:e4:f7:99:ba:b8:32:f2: 3d:5f:84:c2:62:c9:49:17:92:6c:27:64:b0:83:0c: c4:f2:f6:ac:14:de:e0:94:49:d6:01:90:0c:4b:52: df:09:13:c5:41:76:d0:e4:02:fe:4a:35:7e:14:e8: c7:3e:3c:fd:b7:d7:fc:1d:75:cd:7f:ff:4f:d7:22: db:c5:2f:cb:e6:af:d9:d4:69:d9:8f:1b:ab:f2:af: e7:da:85:a6:7e:46:87:76:22:9c:fc:c7:42:da:b5: 21:cd:13:44:b8:55:10:d6:d8:57:09:3a:f8:0c:f5: d2:f2:38:5e:a2:bd:d0:8a:99:bc:79:df:10:eb:af: 50:7c:02:3a:09:1e:70:86:cb:28:0b:ba:74:52:0c: e2:b7:51:25:5d:33:a9:90:ba:64:02:8e:35:56:30: 49:49:66:c8:71:ac:a1:5f:52:dc:43:aa:b2:1e:3c: b7:55:1c:8e:c8:c4:f2:0d:62:93:f1:bd:3c:3e:82: 22:18:68:dd:7f:f1:84:3f:61:b5:05:31:02:59:2e: 57:0d:b1:5b:52:ee:e7:1f:06:45:5e:4a:1e:e0:4c: c6:1d:47 Exponent: 65537 (0x10001) writing RSA key -----BEGIN PUBLIC KEY----- MIIBIzANBgkqhkiG9w0BAQEFAAOCARAAMIIBCwKCAQIjaiTNy87LpSEEofzlVODW 7X755+j4nLRMO6ygpgB4Ln23gUFnDOT3mbq4MvI9X4TCYslJF5JsJ2SwgwzE8vas FN7glEnWAZAMS1LfCRPFQXbQ5AL+SjV+FOjHPjz9t9f8HXXNf/9P1yLbxS/L5q/Z 1GnZjxur8q/n2oWmfkaHdiKc/MdC2rUhzRNEuFUQ1thXCTr4DPXS8jheor3Qipm8 ed8Q669QfAI6CR5whssoC7p0Ugzit1ElXTOpkLpkAo41VjBJSWbIcayhX1LcQ6qy Hjy3VRyOyMTyDWKT8b08PoIiGGjdf/GEP2G1BTECWS5XDbFbUu7nHwZFXkoe4EzG HUcCAwEAAQ== -----END PUBLIC KEY-----
n = 0x236a24cdcbcecba52104a1fce554e0d6ed7ef9e7e8f89cb44c3baca0a600782e7db78141670ce4f799bab832f23d5f84c262c94917926c2764b0830cc4f2f6ac14dee09449d601900c4b52df0913c54176d0e402fe4a357e14e8c73e3cfdb7d7fc1d75cd7fff4fd722dbc52fcbe6afd9d469d98f1babf2afe7da85a67e468776229cfcc742dab521cd1344b85510d6d857093af80cf5d2f2385ea2bdd08a99bc79df10ebaf507c023a091e7086cb280bba74520ce2b751255d33a990ba64028e355630494966c871aca15f52dc43aab21e3cb7551c8ec8c4f20d6293f1bd3c3e82221868dd7ff1843f61b5053102592e570db15b52eee71f06455e4a1ee04cc61d47
factordbでnを素因数分解する。
p = 10007 q = 29278567313214299298882160411734497253413050726095610761154708479926412837784922502815489635727909981117053245989683404021035689083301611490468830124669195593762906999472271670387730789447922970768097925518497745917732257408283532737054315449338209247447451327736716098298102221953699800631324881072125510549508971624219232440439224157865945528138030978588303629427215068473628709454893538619201129318244857686405941320181871159304995082135023810854233131775340408430705353533249906163285499835567445260923862420154112806314008093442186072753077915409188185047310634088119883499661541132044083047749985190488744630609
秘密鍵を生成する。
$ rsatool.py -f PEM -o bob.pri.pem -p 10007 -q 29278567313214299298882160411734497253413050726095610761154708479926412837784922502815489635727909981117053245989683404021035689083301611490468830124669195593762906999472271670387730789447922970768097925518497745917732257408283532737054315449338209247447451327736716098298102221953699800631324881072125510549508971624219232440439224157865945528138030978588303629427215068473628709454893538619201129318244857686405941320181871159304995082135023810854233131775340408430705353533249906163285499835567445260923862420154112806314008093442186072753077915409188185047310634088119883499661541132044083047749985190488744630609 Using (p, q) to initialise RSA instance n = 236a24cdcbcecba52104a1fce554e0d6ed7ef9e7e8f89cb44c3baca0a600782e7db78141670ce4f7 99bab832f23d5f84c262c94917926c2764b0830cc4f2f6ac14dee09449d601900c4b52df0913c541 76d0e402fe4a357e14e8c73e3cfdb7d7fc1d75cd7fff4fd722dbc52fcbe6afd9d469d98f1babf2af e7da85a67e468776229cfcc742dab521cd1344b85510d6d857093af80cf5d2f2385ea2bdd08a99bc 79df10ebaf507c023a091e7086cb280bba74520ce2b751255d33a990ba64028e355630494966c871 aca15f52dc43aab21e3cb7551c8ec8c4f20d6293f1bd3c3e82221868dd7ff1843f61b5053102592e 570db15b52eee71f06455e4a1ee04cc61d47 e = 65537 (0x10001) d = f051652dc48c92c76eb93de1b13fdf6f5a17634a69c9be0737df6124801a3a368f63d7e974739305 4d789a62c23b47403f46ec01f69f4093709029313e35529ba200603eca639e161f7d0aadfb472205 42a563f06c6e60047fe6a81848d693322ca00196e06c4a9f5d217fb3df637572d2681ee7097afeb0 fad75a44b96c77db3c175b40df2d9684ab7f3953d5ead003c97937c9be3d2f3cac23e53b0217c152 64aacddcb28e6a59836c24b6101f73c78113b6bfdc087470d063835d106979d1c0cf65af654befd8 d9fa96e09b4808b588083d0949dc80747babaae515e05a9f9c7973637058d2bddfb6d205f1c9302b f4279d1ea0880242e91857bb7a9815feb41 p = 10007 (0x2717) q = e7ee515888e2718fece17af1e31d5d3823c9eac3ba547d7652b9624704145e34b11e2469e2b4af7b a19ed824481305509e79c0a2b0efc261ff3ee1cea69d80248db231b013ccfa66147fe1afa60c2875 088aa7bdda24d3424e746110869b131c03ed0356a57f9ffe6f954d473e5c732a8db890429b7c93a8 4d03f4cec2f2f7062e542f5bf035578ffa5a6cefe28d07b57af413f4905464d9a9724b4f168d9d9f 9a7763bc8c4df974efc8b3e8206aa098f0fdd3a9ce81bb03b0614082d63985d343f9f84e9fc12e86 86da4cdee0c1783699271912c414cad6c9e0cdfc4f3bd7bf2daa9e117c4032dd108b4b85f2b4cb14 5044cca3b2b6c982c1cb34ba4fab9951 Saving PEM as bob.pri.pem
$ ssh -i bob.pri.pem bob@backup-01.play.midnightsunctf.se -p 2222 midnight{Turn_electricity_t0_h347} Connection to backup-01.play.midnightsunctf.se closed.
midnight{Turn_electricity_t0_h347}
Backup - frank (crypto)
Frankの公開鍵をPEM形式に変換し、内容を確認する。
$ ssh-keygen -f authorized_keys -e -m PKCS8 > frank.pub.pem $ openssl rsa -pubin -text < frank.pub.pem RSA Public-Key: (4096 bit) Modulus: 00:bf:a2:46:a8:91:be:9d:2e:53:bc:f3:d9:2d:70: 52:ae:03:32:db:bc:27:32:e4:89:76:4e:25:48:57: 3c:e2:6d:ef:bd:15:f1:f6:5b:44:47:b5:0e:40:dd: a2:2f:8d:b6:4a:9d:e4:31:83:2f:44:88:df:94:db: c0:ce:a7:dc:81:5b:8c:c0:83:5d:54:ef:b5:6d:b8: 5e:76:f1:6a:79:02:9c:30:37:c4:94:0f:96:0f:05: 0b:2c:87:70:85:9b:a6:ca:aa:0f:8e:f4:5f:77:27: ef:f0:87:30:3c:40:62:fc:0b:61:18:ac:df:c1:a4: e5:12:24:a7:6c:d0:0c:fa:71:86:26:de:ca:84:47: e8:90:eb:84:43:6b:d2:b6:4e:b3:b9:81:f3:ff:8b: 20:53:3b:27:4f:0f:46:4d:2d:bb:ec:3c:c3:64:e9: 8c:ee:34:3f:a9:8d:11:b0:b4:7f:6f:c5:5e:60:d0: 7d:4f:6a:4d:64:fa:d5:eb:71:44:a0:a6:09:cd:90: 9e:46:a6:d9:b9:0a:00:b4:a8:5e:72:c5:1f:fe:0c: cc:bf:74:e0:1c:ee:35:21:21:93:1e:5f:5b:16:4d: df:6b:4d:2b:90:30:00:7f:c3:77:ce:35:ee:b2:5c: d0:71:68:06:af:8b:9c:37:a3:50:ae:ef:18:13:50: e6:01:52:70:18:69:7f:b4:ec:0a:93:aa:ef:4f:4e: b4:a9:2b:4f:1b:66:b9:cb:7f:7a:08:b5:d0:14:32: c3:52:b4:8e:03:8a:ac:5b:75:85:fa:4d:c7:1c:a9: d6:0b:23:b0:9b:dc:77:5b:04:d4:6e:33:2d:e5:db: 96:5e:95:24:72:0d:a1:53:ed:95:e7:32:c1:82:6d: c5:a0:dd:49:c4:6c:60:ae:74:03:07:cd:4e:5a:14: b0:d8:64:95:29:42:c8:18:41:b9:52:c3:d1:05:ed: 1f:ce:2d:af:2e:cb:9e:c2:04:66:aa:a0:cd:30:b5: 4e:7a:03:6b:0e:3d:31:95:6c:35:45:d8:79:8e:6e: 0e:ab:8a:3a:a7:e0:8e:8d:05:0b:01:7a:c8:40:34: 88:a5:fd:a9:b0:d3:c3:09:65:55:4a:ee:33:58:0c: ba:de:b7:6d:e4:cb:fb:92:c8:ef:c8:45:da:74:29: c0:72:5a:4e:ef:11:6d:fa:27:68:ad:40:e9:11:84: a0:55:02:03:c8:3b:75:6e:75:ec:fc:e5:36:28:45: bf:04:48:06:78:38:9b:6b:04:c3:f4:97:ae:a5:9d: 77:39:f8:bf:64:79:c9:0a:2d:9a:76:e0:33:64:6f: de:54:2d:dd:a0:ff:bf:e3:a8:5b:6f:ea:0c:c5:6a: 66:fd:df Exponent: 65537 (0x10001) writing RSA key -----BEGIN PUBLIC KEY----- MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAv6JGqJG+nS5TvPPZLXBS rgMy27wnMuSJdk4lSFc84m3vvRXx9ltER7UOQN2iL422Sp3kMYMvRIjflNvAzqfc gVuMwINdVO+1bbhedvFqeQKcMDfElA+WDwULLIdwhZumyqoPjvRfdyfv8IcwPEBi /AthGKzfwaTlEiSnbNAM+nGGJt7KhEfokOuEQ2vStk6zuYHz/4sgUzsnTw9GTS27 7DzDZOmM7jQ/qY0RsLR/b8VeYNB9T2pNZPrV63FEoKYJzZCeRqbZuQoAtKhecsUf /gzMv3TgHO41ISGTHl9bFk3fa00rkDAAf8N3zjXuslzQcWgGr4ucN6NQru8YE1Dm AVJwGGl/tOwKk6rvT060qStPG2a5y396CLXQFDLDUrSOA4qsW3WF+k3HHKnWCyOw m9x3WwTUbjMt5duWXpUkcg2hU+2V5zLBgm3FoN1JxGxgrnQDB81OWhSw2GSVKULI GEG5UsPRBe0fzi2vLsuewgRmqqDNMLVOegNrDj0xlWw1Rdh5jm4Oq4o6p+COjQUL AXrIQDSIpf2psNPDCWVVSu4zWAy63rdt5Mv7ksjvyEXadCnAclpO7xFt+idorUDp EYSgVQIDyDt1bnXs/OU2KEW/BEgGeDibawTD9JeupZ13Ofi/ZHnJCi2aduAzZG/e VC3doP+/46hbb+oMxWpm/d8CAwEAAQ== -----END PUBLIC KEY-----
n = 0x00bfa246a891be9d2e53bcf3d92d7052ae0332dbbc2732e489764e2548573ce26defbd15f1f65b4447b50e40dda22f8db64a9de431832f4488df94dbc0cea7dc815b8cc0835d54efb56db85e76f16a79029c3037c4940f960f050b2c8770859ba6caaa0f8ef45f7727eff087303c4062fc0b6118acdfc1a4e51224a76cd00cfa718626deca8447e890eb84436bd2b64eb3b981f3ff8b20533b274f0f464d2dbbec3cc364e98cee343fa98d11b0b47f6fc55e60d07d4f6a4d64fad5eb7144a0a609cd909e46a6d9b90a00b4a85e72c51ffe0cccbf74e01cee352121931e5f5b164ddf6b4d2b9030007fc377ce35eeb25cd0716806af8b9c37a350aeef181350e601527018697fb4ec0a93aaef4f4eb4a92b4f1b66b9cb7f7a08b5d01432c352b48e038aac5b7585fa4dc71ca9d60b23b09bdc775b04d46e332de5db965e9524720da153ed95e732c1826dc5a0dd49c46c60ae740307cd4e5a14b0d864952942c81841b952c3d105ed1fce2daf2ecb9ec20466aaa0cd30b54e7a036b0e3d31956c3545d8798e6e0eab8a3aa7e08e8d050b017ac8403488a5fda9b0d3c30965554aee33580cbadeb76de4cbfb92c8efc845da7429c0725a4eef116dfa2768ad40e91184a0550203c83b756e75ecfce5362845bf04480678389b6b04c3f497aea59d7739f8bf6479c90a2d9a76e033646fde542ddda0ffbfe3a85b6fea0cc56a66fddf
またRSA_key.pdfに秘密鍵の一部が見えている画像ファイルがあるので、見えている範囲を書き出す。
YZE7xr0bE94JO4cqritQcE+dJ4WOmf4HvmhaSElywcp9xN8xBucN5DnxlXt8MEbj me7udUNRvTDYHdFkv26P1K4Xhes8duRpQBES/TxN4YD42td2P8PCShLnvQ5JLWuY cCnYQa9wbEH8zL9lxlJne5+0Vc1Bd7X7OENRTxBHpYJg28m/cDeUs8KHUvlyeGHK qJGjzIAO3KXjvQzj0YWi/MGKCBleeoVz0URKR7oP7GxjORF2DypmLf8r2374uISy RHLKFQfW9TnO/j8L7DWm55dOcJOZr1kbDvxPAu2zLQKCAQEAwM/Hdvm8rX6Q6C8A tYLA/+JvWsxLxGW4nL88dgl61RVWPz4PZzWPNQwbfWohay562+ccTxFM0rlxuDoH Dh7A4X45W0+MBJbdYTSoVzFs1r1bjoPpwBnsL1pNAkC5zloQFUkmvpzBD6DaLX0i OhZtqsichyPGEyVH0RYv2L3UPYAhdmeYbsbc6Ruhva9tVUUMc+nFyKf51Os4vC8M YTnyYZJqo/5oAR7wt6806ZlsTQowlbSPn1hYgtSka/RK+gBnKyFhmihi/Jy0gJNg T/p/Fb1DaX6sjnTpPbxfHXX9j2ExC3uH1/1ynF1tpLBp2AN9/rbc2N2NtOI3W4oJ X2krUQKCAQBRxpFTEWofHJZk7A6eaL7AkzQtJkWqRlyor7Yd1wOQdaiqDdO20AbW Sbnb18msiGGwPm25IUFqa214ULC87srWNBdw51/W0XaZiGzmjrctfHwZmVUQ31Ou pDWve4ButBBIOt9sEnTq+pMiC93nPprG/E8uBLyF2KX/c8WIBa/WpE/mmC3lvgtb PC2N9lrNeaHM4QPeRrfcj52qxxKYIo55XUGpMSGjEUaHiTqSZa5QJR26s5Q8OceV sq5fUEDPbxHEhp0IUVVHarDBk2CC0iL+vQso82QQjm0ybJ1/posPNfDHlYHuqhSA rVoRpE14r1M+FIXO0S05Qfl2RHV8BdfFAoIBAQCUFi7LV3+dHMJj0h4HyL23rL6y yZXE9EjMd1ExoDP91aJSnSbS9GS+/Ro4Osi+rw5ixryqBXRn9tMCDtJ1NQuY+MiU XFEsltt9N4XAY0WNm/1aUGsuICBdYbKh3DD97M+FZqzUqlI1p1Fb3NpKhatfY7Yg t2Z6w77B+OMi8T6rIpeLOLxR5pEJmCCfojM8gVRGMFb7IHc9Hp1XlJpePh1OyWQF ywaauJBnYEsIz2A22cMp4frY/unZxeWRK82rN4d+jSYmyf9NCXwK9mXuq/pXjlaB XqIB6+n3swDFGQX732iPBGu9iDbhsQ6vdoRBAtqcHmCTLB2dqXhrnvUSMMUS -----END RSA PRIVATE KEY-----
これをbase64デコードするすると、以下のような構造になっていることがわかる。
0x0df~: 02 82 01 01 -> データ長257 ~0x1e3: 00 C0 .. 2B 51 -> データ 0x1e4~: 02 82 01 00 -> データ長256 ~0x2e7: 51 C6 .. D7 C5 -> データ 0x2e8~: 02 82 01 01 -> データ長257 ~last : 00 94 .. C5 12 -> データ
このことから以下の値がわかる。
d mod (p -1) d mod (q -1) (inverse of q) mod p
この情報からp, qを求める。
def solve(dp, n, e): for i in range(1, e): if ((e * dp - 1) % i) == 0: tmp_p = (e * dp - 1) / i + 1 if n % tmp_p == 0: p = tmp_p q = n / p return p, q b64 = ''' YZE7xr0bE94JO4cqritQcE+dJ4WOmf4HvmhaSElywcp9xN8xBucN5DnxlXt8MEbj me7udUNRvTDYHdFkv26P1K4Xhes8duRpQBES/TxN4YD42td2P8PCShLnvQ5JLWuY cCnYQa9wbEH8zL9lxlJne5+0Vc1Bd7X7OENRTxBHpYJg28m/cDeUs8KHUvlyeGHK qJGjzIAO3KXjvQzj0YWi/MGKCBleeoVz0URKR7oP7GxjORF2DypmLf8r2374uISy RHLKFQfW9TnO/j8L7DWm55dOcJOZr1kbDvxPAu2zLQKCAQEAwM/Hdvm8rX6Q6C8A tYLA/+JvWsxLxGW4nL88dgl61RVWPz4PZzWPNQwbfWohay562+ccTxFM0rlxuDoH Dh7A4X45W0+MBJbdYTSoVzFs1r1bjoPpwBnsL1pNAkC5zloQFUkmvpzBD6DaLX0i OhZtqsichyPGEyVH0RYv2L3UPYAhdmeYbsbc6Ruhva9tVUUMc+nFyKf51Os4vC8M YTnyYZJqo/5oAR7wt6806ZlsTQowlbSPn1hYgtSka/RK+gBnKyFhmihi/Jy0gJNg T/p/Fb1DaX6sjnTpPbxfHXX9j2ExC3uH1/1ynF1tpLBp2AN9/rbc2N2NtOI3W4oJ X2krUQKCAQBRxpFTEWofHJZk7A6eaL7AkzQtJkWqRlyor7Yd1wOQdaiqDdO20AbW Sbnb18msiGGwPm25IUFqa214ULC87srWNBdw51/W0XaZiGzmjrctfHwZmVUQ31Ou pDWve4ButBBIOt9sEnTq+pMiC93nPprG/E8uBLyF2KX/c8WIBa/WpE/mmC3lvgtb PC2N9lrNeaHM4QPeRrfcj52qxxKYIo55XUGpMSGjEUaHiTqSZa5QJR26s5Q8OceV sq5fUEDPbxHEhp0IUVVHarDBk2CC0iL+vQso82QQjm0ybJ1/posPNfDHlYHuqhSA rVoRpE14r1M+FIXO0S05Qfl2RHV8BdfFAoIBAQCUFi7LV3+dHMJj0h4HyL23rL6y yZXE9EjMd1ExoDP91aJSnSbS9GS+/Ro4Osi+rw5ixryqBXRn9tMCDtJ1NQuY+MiU XFEsltt9N4XAY0WNm/1aUGsuICBdYbKh3DD97M+FZqzUqlI1p1Fb3NpKhatfY7Yg t2Z6w77B+OMi8T6rIpeLOLxR5pEJmCCfojM8gVRGMFb7IHc9Hp1XlJpePh1OyWQF ywaauJBnYEsIz2A22cMp4frY/unZxeWRK82rN4d+jSYmyf9NCXwK9mXuq/pXjlaB XqIB6+n3swDFGQX732iPBGu9iDbhsQ6vdoRBAtqcHmCTLB2dqXhrnvUSMMUS ''' b64 = b64.replace('\n', '') data = b64.decode('base64') n = 0x00bfa246a891be9d2e53bcf3d92d7052ae0332dbbc2732e489764e2548573ce26defbd15f1f65b4447b50e40dda22f8db64a9de431832f4488df94dbc0cea7dc815b8cc0835d54efb56db85e76f16a79029c3037c4940f960f050b2c8770859ba6caaa0f8ef45f7727eff087303c4062fc0b6118acdfc1a4e51224a76cd00cfa718626deca8447e890eb84436bd2b64eb3b981f3ff8b20533b274f0f464d2dbbec3cc364e98cee343fa98d11b0b47f6fc55e60d07d4f6a4d64fad5eb7144a0a609cd909e46a6d9b90a00b4a85e72c51ffe0cccbf74e01cee352121931e5f5b164ddf6b4d2b9030007fc377ce35eeb25cd0716806af8b9c37a350aeef181350e601527018697fb4ec0a93aaef4f4eb4a92b4f1b66b9cb7f7a08b5d01432c352b48e038aac5b7585fa4dc71ca9d60b23b09bdc775b04d46e332de5db965e9524720da153ed95e732c1826dc5a0dd49c46c60ae740307cd4e5a14b0d864952942c81841b952c3d105ed1fce2daf2ecb9ec20466aaa0cd30b54e7a036b0e3d31956c3545d8798e6e0eab8a3aa7e08e8d050b017ac8403488a5fda9b0d3c30965554aee33580cbadeb76de4cbfb92c8efc845da7429c0725a4eef116dfa2768ad40e91184a0550203c83b756e75ecfce5362845bf04480678389b6b04c3f497aea59d7739f8bf6479c90a2d9a76e033646fde542ddda0ffbfe3a85b6fea0cc56a66fddf e = 65537 dp = int(data[0x0e3:0x1e4].encode('hex'), 16) dq = int(data[0x1e8:0x2e8].encode('hex'), 16) qinv = int(data[0x2ec:].encode('hex'), 16) p, q = solve(dp, n, e) print 'p =', p print 'q =', q assert p * q == n
実行結果は以下の通り。
p = 32155793883644309494149365087347710275210633774631897274003001908876018851960968012981271807389852904017267710405842990613181825323298497180721462889930852141756696942713059737825259562300443091116514916928396257101370860052927606384048304583938193088254729901128992755541135185322798527530512122498248043845789461978413935354215871986482151417756534584220556107891332673683000687165418919940645597668777626845600908432978474596080126672805046918964956144371065049005805638187590643592564866189148070656840995258832683463131564291944605671726345796937320632480267178246999762145360703260951002442725449730325007240379 q = 24312821138947295842939811430266614164483390266044923887694157098746040509093637457237135603411011833287827123602619771315554896936017168546924189851322281151620644250524117043049673777703814283705410796690775974401304283378519985368125276766049671207507190418663428295243489814095988104136549989630636041063221268290523766428047760530245982382697752496455539057488593944136069627708927281633167017337393918797915410963972736328647804191560830879679674669676405585810075964267210384497030345823969704188597922024875674517047635080525199694836436149951817779893116507111781865061463859626764914849867030257100120765229
秘密鍵を生成する。
$ rsatool.py -f PEM -o frank.pri.pem -p 32155793883644309494149365087347710275210633774631897274003001908876018851960968012981271807389852904017267710405842990613181825323298497180721462889930852141756696942713059737825259562300443091116514916928396257101370860052927606384048304583938193088254729901128992755541135185322798527530512122498248043845789461978413935354215871986482151417756534584220556107891332673683000687165418919940645597668777626845600908432978474596080126672805046918964956144371065049005805638187590643592564866189148070656840995258832683463131564291944605671726345796937320632480267178246999762145360703260951002442725449730325007240379 -q 24312821138947295842939811430266614164483390266044923887694157098746040509093637457237135603411011833287827123602619771315554896936017168546924189851322281151620644250524117043049673777703814283705410796690775974401304283378519985368125276766049671207507190418663428295243489814095988104136549989630636041063221268290523766428047760530245982382697752496455539057488593944136069627708927281633167017337393918797915410963972736328647804191560830879679674669676405585810075964267210384497030345823969704188597922024875674517047635080525199694836436149951817779893116507111781865061463859626764914849867030257100120765229 Using (p, q) to initialise RSA instance n = bfa246a891be9d2e53bcf3d92d7052ae0332dbbc2732e489764e2548573ce26defbd15f1f65b4447 b50e40dda22f8db64a9de431832f4488df94dbc0cea7dc815b8cc0835d54efb56db85e76f16a7902 9c3037c4940f960f050b2c8770859ba6caaa0f8ef45f7727eff087303c4062fc0b6118acdfc1a4e5 1224a76cd00cfa718626deca8447e890eb84436bd2b64eb3b981f3ff8b20533b274f0f464d2dbbec 3cc364e98cee343fa98d11b0b47f6fc55e60d07d4f6a4d64fad5eb7144a0a609cd909e46a6d9b90a 00b4a85e72c51ffe0cccbf74e01cee352121931e5f5b164ddf6b4d2b9030007fc377ce35eeb25cd0 716806af8b9c37a350aeef181350e601527018697fb4ec0a93aaef4f4eb4a92b4f1b66b9cb7f7a08 b5d01432c352b48e038aac5b7585fa4dc71ca9d60b23b09bdc775b04d46e332de5db965e9524720d a153ed95e732c1826dc5a0dd49c46c60ae740307cd4e5a14b0d864952942c81841b952c3d105ed1f ce2daf2ecb9ec20466aaa0cd30b54e7a036b0e3d31956c3545d8798e6e0eab8a3aa7e08e8d050b01 7ac8403488a5fda9b0d3c30965554aee33580cbadeb76de4cbfb92c8efc845da7429c0725a4eef11 6dfa2768ad40e91184a0550203c83b756e75ecfce5362845bf04480678389b6b04c3f497aea59d77 39f8bf6479c90a2d9a76e033646fde542ddda0ffbfe3a85b6fea0cc56a66fddf e = 65537 (0x10001) d = 566966533ce5271b6cc7176e26ff2f49284816ad913f71ae4a9a92553c8147d92af1a8a3a2e324b6 f0fdac6244700d06d63ebc57574049372f1a80bd4072910c03ac4462f80304d45ad578434a3928b7 f496098faaf41c46498ff0546278dce7291be6482009ac4166009ff53036186c6ef5299b4a8a9740 741df3212defac3ee4af42672f9efd4fdbe398435690be8c6c6a1d0c6e3ff5480741af31943bbb31 9b74c05c5020598f1b757134ad2f89c705f7c20bbf73bfd279095d518610aace60d3858b7651570f 1ba25b09bbd707c6171f7c75c7594450d0cfc2f73f2863b659b898e3bbf0e948b36ba2a0cf31be88 7f9ad8e8ef9b51bb62f67ef9ec3bde7a906ca20147cc6dd61d5ed7f06ce4a052574186dfa82a0db3 20ad7425a8fd08e832d8ac264d28da314f6efc99ca00f31b5528466a375a1f653f887cc6f4f91ef7 e3c4a1a6dea02885711fbbef0cf74c784fec32640d84d1e687fb35c696b3ce182671845bccfe9acf a8c7d5a079f8501bc67c70f5e0325e5af0c89ff8abee4db0272c522b755383f2cc781bc83c8328c6 d676cd72a693326ef8a678931138d4efe1bf97daf0a5330b5be61f0da00ffc8dbc48a205eb8af333 387f91b1063fd58ecd989b975a380659f4cbf97f11530f2f163ac765c07f81ea97967429d3e3f9b5 b256bfe02fa519e08f2da7745c1e52ea7244f02ac7ff2884240409544c908481 p = feb9137abe16be4b0ba2b2cddd178624ece1b98c31219240a9b76365a1379a07bcbb33cdd38595f4 aa024748dc11c05f2bcfe7d6f3a28df7302fc8d760acceea3d27e35001183f9645dccb02fb45ef74 e2ca88f074ef2daa93876f15287e987e683f642727ac02a6eb4eee49aff450c1d1631eec4b16e372 6e0d4c53f57f956d9a4f8f1fdcd29b643d52294a2939af817874e1ffd2c414d542618d5bb1436f51 a47ef0667205e5eb0fe4d15a86c7c382fb1632255730e10dbb96cff3129c318be32543253f8554ab d40f65ef174c694649883acc77ca56bc44650bd10ba857598be4a70d05c4073be71dc6c5540e4538 f10a024f7bc2d48724b08940933b0cbb q = c0983a7397809b7ff43cff86ceb61c08d01aa5447b18d48a3e8aff15c93ce8071361913bc6bd1b13 de093b872aae2b50704f9d27858e99fe07be685a484972c1ca7dc4df3106e70de439f1957b7c3046 e399eeee754351bd30d81dd164bf6e8fd4ae1785eb3c76e469401112fd3c4de180f8dad7763fc3c2 4a12e7bd0e492d6b987029d841af706c41fcccbf65c652677b9fb455cd4177b5fb3843514f1047a5 8260dbc9bf703794b3c28752f9727861caa891a3cc800edca5e3bd0ce3d185a2fcc18a08195e7a85 73d1444a47ba0fec6c63d111760f2a662dff2bdb7ef8b884b24472ca1507d6f539cefe3f0bec35a6 e7974e709399af591b0efc4f02edb32d Saving PEM as frank.pri.pem
$ ssh -i frank.pri.pem frank@backup-01.play.midnightsunctf.se -p 2222 midnight{D0_n07_s0w_p4r75_0f_y0ur_pr1v473} Connection to backup-01.play.midnightsunctf.se closed.
midnight{D0_n07_s0w_p4r75_0f_y0ur_pr1v473}