RSA Buffet (crypto 150)
平文の生成と、暗号化のスクリプト、10個の公開鍵と5個の暗号文が添付されている。まず10個全部の公開鍵を見てみる。
$ openssl rsa -pubin -in key-0.pem -text -noout
Public-Key: (4096 bit)
Modulus:
00:d7:af:32:b0:93:d6:e2:24:bb:96:3a:9a:7b:c8:
73:b2:e7:7c:6a:ce:76:3e:7d:6c:6d:d7:d1:d1:11:
82:85:2f:68:4b:50:3d:d7:2e:76:94:fd:ec:46:68:
af:bf:6f:90:c4:af:46:62:ab:ee:1c:3a:33:c5:0e:
c5:c5:2a:8c:0a:9a:af:4d:0f:31:61:eb:b4:ee:76:
22:a2:2f:f1:fb:67:b9:30:23:d4:94:31:30:6f:fc:
01:40:19:1b:10:77:b1:14:cc:a8:84:db:4c:cd:d8:
d1:f7:bb:13:1e:f3:21:b4:90:70:03:54:81:61:92:
1d:29:3a:42:63:18:97:08:ba:07:55:45:2a:66:a6:
dc:91:61:88:b2:63:01:05:36:fd:23:9e:be:da:8d:
87:7a:66:dd:84:cb:43:1f:5a:62:ab:90:8b:66:b4:
e6:4d:3e:57:bf:ba:33:8e:13:b0:37:7c:03:03:d6:
38:60:75:58:64:78:5a:1c:8f:4b:5f:b4:7c:6f:c4:
f2:a9:fd:85:30:73:23:07:33:c6:8b:75:4b:2b:48:
01:07:02:73:33:03:9b:b1:d8:49:13:13:7e:6d:fa:
47:3e:92:d4:b2:4a:f5:7e:73:0a:4a:34:f6:e0:1a:
41:6f:94:a8:35:5c:cf:46:95:4c:d2:6d:25:03:bc:
ea:20:90:3e:cd:77:a0:1f:26:84:cf:1d:7c:71:24:
b4:5d:ef:ab:d6:c2:b4:7f:26:dc:14:28:12:c8:35:
73:c4:12:81:3f:01:68:04:e2:c1:2f:31:ca:43:3d:
ed:d4:76:34:bb:e3:e4:93:5d:76:2a:b6:e5:9e:72:
ea:09:32:ff:75:f1:88:07:a8:b1:7a:2f:68:81:76:
3c:f3:02:8b:9e:15:a5:11:4c:06:81:7f:b0:76:e0:
5f:4d:41:fa:52:b9:db:79:59:9f:f4:07:a1:85:6b:
4e:b4:73:8f:1c:ed:34:0a:44:07:07:29:c2:a5:6a:
d7:3b:61:24:3b:6c:a9:96:a2:0d:50:54:8d:fc:b1:
1d:75:06:89:ae:93:47:13:31:fe:68:c2:29:22:68:
7f:16:c4:83:08:d3:ad:74:e8:c9:bf:f8:c1:74:4c:
06:74:d2:03:a5:6c:09:9d:7b:ee:8e:f9:4d:92:d9:
b4:ec:3d:1e:91:97:a0:ac:49:25:75:45:fc:09:e1:
ed:73:9d:6a:10:ad:da:08:2e:5b:18:f7:ea:a8:3e:
78:6e:e9:ad:85:86:07:0e:a6:5d:b4:f9:b5:ab:b9:
39:4d:a3:2f:b7:4d:68:c8:d4:a6:4e:f5:c4:a1:2c:
c2:9d:61:22:64:e7:3d:25:9a:3f:d6:88:c5:56:75:
58:be:a9
Exponent: 65537 (0x10001)
key-1.pem ～ key-9.pemも同様に見てみると、n0～n9、e3の値は以下の通り。他のeは65537。
n0 = 0x00d7af32b093d6e224bb963a9a7bc873b2e77c6ace763e7d6c6dd7d1d11182852f684b503dd72e7694fdec4668afbf6f90c4af4662abee1c3a33c50ec5c52a8c0a9aaf4d0f3161ebb4ee7622a22ff1fb67b93023d49431306ffc0140191b1077b114cca884db4ccdd8d1f7bb131ef321b4907003548161921d293a4263189708ba0755452a66a6dc916188b263010536fd239ebeda8d877a66dd84cb431f5a62ab908b66b4e64d3e57bfba338e13b0377c0303d63860755864785a1c8f4b5fb47c6fc4f2a9fd853073230733c68b754b2b480107027333039bb1d84913137e6dfa473e92d4b24af57e730a4a34f6e01a416f94a8355ccf46954cd26d2503bcea20903ecd77a01f2684cf1d7c7124b45defabd6c2b47f26dc142812c83573c412813f016804e2c12f31ca433dedd47634bbe3e4935d762ab6e59e72ea0932ff75f18807a8b17a2f6881763cf3028b9e15a5114c06817fb076e05f4d41fa52b9db79599ff407a1856b4eb4738f1ced340a44070729c2a56ad73b61243b6ca996a20d50548dfcb11d750689ae93471331fe68c22922687f16c48308d3ad74e8c9bff8c1744c0674d203a56c099d7bee8ef94d92d9b4ec3d1e9197a0ac49257545fc09e1ed739d6a10adda082e5b18f7eaa83e786ee9ad8586070ea65db4f9b5abb9394da32fb74d68c8d4a64ef5c4a12cc29d612264e73d259a3fd688c5567558bea9
n1 = 0x00c4ff486b14cd9c37b956f08ff19ca2f83dba86509cb840cd6a5a95f1352009b18d1d56b4a0fec0e95a29ca96caefaa5deff71d6aeb0ad89eeaad908cee93582bd71b2cd7daf709a54b98d163b508d3fd1f0a9709fb69e499d1b8abc50af3a4cbae77c070444933613a452954f91acdaf461d6a364035920561f7885d30ebdc82be3560e6428864b9715e1734d013e23dfb8c1da662f5ce6da3712402f8da445d0ca49b9bb1e47abeeef58a6385ca3f9eb9d24008b6e68e1de7c2f12fea14f7729c248d8db7d9b85e6279ab68b0517f739d9745ba02f8aabc33819c326116c327396b5716c6895495ae8d3cf60a3b6a11557329383f6d5f414d9e05e87e13d5d7cbf87994c86f1419a8fc969500e36d8570fbe1bc13df8bfe3888209b0bd684b9265bf7f4e05cf670d8f288e1d82740e9812f9aa68a99b5e569420b38cc1538787ead253df53341e3c2697ce76152b02ed437cce19386e2a13608bfb7b23336356f032c550f1fbc4f8ee00294cbecb03ece45dfc5f5c115d73adc988ba297104c81351bb73c2ac01d3acfc5a814c4947b5758b0193222102c1541f398d2d7b1c2cfdd53a172aa899880f53a8b5c7e6a39e6e408141df99ae2f6befc00b02e2ac4c3af122be5097f3231c5b4e607bca2a78c1f1040aa3c4351de4b3172e3882c116e5f586de33cee9c911875ac196efb8355d4cddfe5479b19fa426a25e0ea1891
n2 = 0x0086986548c02b2d6b0461a74a09a5ee4efa07882d5c610bdb14d1ba3044effd5570e4c509d116aca992a342cf52ed0463db6d4648a3013ba8219c3a72b1998796253dd11ecc536087e6e5bd207c1387af9df6bf875ab319556dcc0bad6a90f017459760ee7d274fe6046e7599385f7607d29ed235477695e3365fc6b9f5270183e9c4c2c118aa676c1d9cbe06864507e4310d85b8cacff9f5a3eed487b71d2d75b00943d7eda9aaf5b2bb69271625de2469d6a7c4f50c4eeac54b1605793cc0f7fe9167452ff5fef3647c9eec8866730732c05dca4c56f393ca2e61e7d76442822b9da56d96f67bba9f6095f761d0f2a3de62ea8c6fc7ac2fa7b727684947f7640711b700f40a1799d0265eefe94952b50e5e10b15bec14cc1664714c6c1ff1c16454f4a912ec19760d80c4759ff3130da43b13e7967d5cea526402cf2b566653c0cd5d7d0995357661c0308cbd11aaeb832ca9093dc3981d1fb6b62fd98a883e8d4c1548521c3e2f0bef76c7220d8093c2bdb1ae017f2e48d0defe42ce5713955ae294bec2b5da9b81cf9bb1d8ca5e5dcc9bf930edb7a3f6d2d350d2aa478e01070dbc151d6f9f6dba473ec001432de4e2ced4611955f294b3d48631dd51eb7c50a97f5165731d597129d3335f4c994234d89095335c705f075a1ba08a0f5cf383d65cd424524a48a415ce2ca5a34b4287e4efacb243e68b9c90a3679bef2757
n3 = 0x00994a5e2c2303b40943d9b744b5709ee601fb5c4ac300cfa44a7608107a74d06ac04963a3f8201fa7801335edd3f323090425924b74f6ac39eeaff7b4a6bcaa241533fd5f57505b388668f24d8d65330745cc515ee1b3c96016b399c35eefef0612baff82761088117b07e25f9263f914981023319165d209c4784bc37a92ed7fecb470317b3fde5343cdd9aa13794b74831892cf6ea1002d7a3f760f1bb3edfbf6273b15361127424f1712892e0c6cc759b3c690da8c6184a90be6486b8f25c745554c0aaa445764589a5177038a67cd73e66fe1b0d559e0bbbe3e5b8d4aeef72ffa874cc16110bbc135c3e9928c5fcae737815f49fb023c64eda62ad2ed7d0d32249617dc512dc540006c0f059b2fdaeb3b0ae1c2b9615db7c83b909e222719451736e1f07c3919c3965fd9d003bd8813ec1e9cd540faf7f70f72fe8f0f544b2cab51a8a062865ae4f46a0530b7e11a264d717f3cf13b6018d09de1a0c28ea20cee2a6711da5d115fd71c096d115c13f0b5e40d94696c67105c2f709ae5d2fe0ac85847b3c9017ace7db2eb00d410d9d2da7685776a8099472d01791c57810d160abd6c9e420276320eb11b80a0b2f5722e20e9d8822a1d143c97a63ef81733e52f263e3a7f77b6900bf95da215544df51e61ecc468f037a2b39ccf153d984b32a9a4ce757bbb38798ce0b080f503ce1a396d47e14cc41bf18e34edbd9137eb
n4 = 0x00a9dffbcdf808e4a5120b876d4be077cef21b6ef3bbccdae77b6afc988ea068cad52c6e7d1797049394caaee701e916b3d192c6fc8f8ab2c8a0bcdc75cfb1c436a914c128046b889aeb5f1c89852856cad179a0958a4aeb87ba778ea62187ad1931d5bdcf85d57361fd2941a076ea9b3652110287755e663e679892b4ff0519042b0b3a85aa99f623a1037d503b245cf3205c3c5b24139b3abf0881fbc1b0f7e03444149f69427fd78cdbc75b634a5160e9b2aadbfd9cfd6150ab0ace72dd1d95e1d884153cbe9dd62458745a0fe95014e89f263a9730ff2205b108e3985bb9da9a1b68b4ae1d52cec2b3a5320e02392e9e8b802d190de6e4f75388c3fafdb2ba58904eceaa613c3d67d81ede381a0f15a2822bd1a5a1854df38aea7d32e6cf8c38d8d6a8daf384befc5ee06c9be1a4b2216b690b28dfaaebd9d47b3d96fddd96114dc6df9b1eb21343098ef9e6540fbac0c19a63cdaf6e4528ae41d212e50dab72ff4529b042ec22dd8d61166d29548559ed7de469391781444baee28f3ecbed79169a7134da785d476533ace2ffe3aee5b9501549a8061ad50b352d01735dfb4ca7d4d0bf759c9dbcbb1ba4793a30238f959ad033b5691920b3e2fc793fe154ee9f6ebc5d64744b518a41e26803d11f1fda6d223904c26054b4c685e3640da0e1f4da6445b55757ac7e4e18c938168c1d8c64f31eb11e4aaa09d0c94fca9973
n5 = 0x0088ef837570c4161f5ef7d6e65deafb9840cffae5f3377d7b2c4fa8ee99286fda86d1dd77aec9a7d9751328c0d0db4481f8a108b4d844262ea1fb8bf02aa44dba0f9c02baf186bac37e02314c48277803b088c2921076b155c4882cf4c2397796959edf22af6a2ff769ca4668f370eea104ac006df3fead69e1b7c00b8d4ea0b8e99f904c7b66fad4cea031091b66a21373c0cc64d2151d8274f128d183a7f3d697965f1590f3f2656259fda9be417510949dab2163c5f450d662a899fcaa31344ad0decd558fa3e9f9247a23fe451c8f846acad19360e66720909f405064f576b6c925a081d4865f7bc861d51101c33d695656b33d164e38948234db1cdc0fbf8608aff64f67ddbaf3e3ead882d8ab69916dd6b922cec62f3d53567b0e644f990add24b22d3021178da47355bdf1714ce142f98d03daf7b525d0c6aebf42f2f5e9352584ba503f1771bf5b2ed7f77023c3c82e8aefc79d3c22d177b3f6e3d5e399f586b4041cba5e4cd66e30fe9666df9fc6216f2ba1d0ff002fa1d6f1ca787a3130a6a5ca929fa737c8fcd86c753709bc23f54eddd6c1fc6d121932e900f4be24200329432bacf3aa8e6fc9e87a226457dfe24745fc7c969390f992f999ea4920cfccc4c47c06b9aebabab4c91f14d8ff85e27576f0a027ca70093c185c008b27e8243121551e4705fd46c3561485abf2fbaa0fc28a87871fe2e3f5afa30527
n6 = 0x00bc0d4dd9ed44c44c2173abd3b025401b366816d913f7b4271b71abcded21ab0d04c2fc577a313b794275845dbb89e8151cf4bd3825e9240c88eb93a824caa8b0b563960ffcb12fbcafcd9d38fbdf87b134395d0ea316186beaf2470a535a1da3529c005cb9062f0d43eb8e7bf4cd79425a6cab65a15c905713abcedbf4a715c46465becbba9ed60fd77bf82f035d8a394c56f13898834b277c6749261a9c95b22574c1f7781550345588cf2ff1d22eaeb1137aee4d41f6e288759844a4eb8e8cbdfaea1776d3c45e7551c9924317d0efe36a686afb3ac8a12ab809a3deee27d7f69f26b70b97cd1ed51426e489e804881dcae802fba751c3f83b6983cfcb4c30c966ca92e7bf08874b2848e098f021f183ae839be30191e3bcd2ce38325e3991c6e733bf00cf3f60aaef2b7ebd0554fb0c980a6f62db59974e7f3ce46afb24e43e107ec8d1cc0e772f997ff0c5a602fa8bcd0cbbf78cc2d1a84903a3cc00b397858c02c28f7c0707e66d6dc0de2ce747d99dc4038bdd924cf3c534bcec6dcf3d4f0247e30875f39af7ab0fda69fca12d7104c51bf6d66aff2d12338ffbf51e243ade078de6cc1930f872c3ad91d8f822668e56d352c0156e513033ea20c0f163d558b69119734684f98cf789df72f8c534d008a535c9dafebe8774140adc0c53eeb021852ec282b7bddce58c9ffb87a7b4f20b91bfd04ed84ea6566bc397f1d9
n7 = 0x00b7d5a8ccd362a3f4691641ee9176e4d025159ad60a427a7e21343acea9ef3f96fa1d70460a504a9c78acf899dc5f42ec55d00078343b40f9eeeaf5740bd8be047f66cc01ad7df6d66a8dd42265a6ff87e8ce168c9a18465002a8e6ba5bc4f108d6e70bb1ff2646492f9c154adec571153178606c07299664d3ec7eb1f1301f01d13b3865db6fa6d27d61667c42c16e764e03f312017109b19a7f9eedd00a6b082f35bc4399f76d646416a9a40e7c5a2774cf84e9c0d978f316fc95bf391c1b1a4e6753dc4c2ba31af2de8a485e65408f63d34b17318c1b83d437964ae047842bc73c4a020888b7988755c7e64f35e8fe7f812217fdfb87f815995815343409b5b6bed6869181f72e0737f4f98456f0c6a084cae14960e44a091714c4941ab4a37a657b241795b7315a6ed24c038e7ecce82586810d0fb33b503c2a0f72377db68a02f0fd1e20287155df960d3d0dd33675f5a4788bcea886bd64aaa984db29045ae886c38c61671b629de16a743f6fbabb5e6e7fb7a577cd6628757c71469555b9b0517fb4ed115269ed7367b30bd0b1782d19879d7bfcbe33336d070a4bd75e86c90e171409e69b867bfe1be1537966be6ac20702457fc04e150ac2f3bf33f4181128690899c976acf7b6141e9f59176bb0b6f9a52066c79bf669c539714a389136274785593f5ae3bb3af2effcb47f4a45ba72a5117fa89c4173c79d663e99
n8 = 0x00ccd36579389be5198dde695c2d97b7efcc04e332161ac60f82dac6ae33bb96dd885713915af2e997b1fdc307673560a3f9fe1935ad3b2a08dffa55c8d743cdcc9e6528e43fc0bd030cb1b49e12e42888c71801e072b8ddd345a0a28a76cac3af17574768e4a66a8e07d9658fff1ad9dbba618588c6c4cbc342a786de733a7d0bdb1f08e48cbad45865abcc4ac68db2a1e3a14f159add984eb83cb9241bab797f477931869bd36f42324e88541a7096ecb5895644b411e199e21cce30b835256d555b613185583eefdc27ba3883518c843f4044c309e39c7661cf149c3c0e0f65659544681803fafbd372955a878dcbb344f38d4cb39da21a46fc8c79fb39b619a8c4baac769106addb00742171c44509329fa7673a8178574e5f5d6a1c6b9db39e25f80ae7937a63e4609ac4f9a3e82c6a3b8fb12927ffc5ba87b256a3f3916ad8b2dda4b837bf6fa9f905d2d62c669f9b407bc4c67c4582544ebb61e1b077f0446895f58891e6a90460f7f09981bf3bb57d24ced44bb6cb31859d159f100cc35a1e123417dae4823b374a25dcce3f176af21125cf94898576741155086782915ee6b7be7c3a415fb7c3dcf83c6ad4b93e5846ed3955b6d8f2dd5145c15ff9195255db8279cdc6d935fe727fe39df02fba31b6aac52fb605f1ceec30faffa7324d1fb2a1ad5b325c48b35cd962130ed6da64a1c172e7863d505411592b8665d7
n9 = 0x00b17acf77309dccdcf05a4259212ee3b148b24e52fd39aad9cb558caa4c49a35bed6904037a065f92f3affe60dc0123f7c79f1fd52cf8fcb03095e33ccee9be8d55796b610077fd06de336cd2553f0695d809bf0eeeabcea5085387fa2670dc81b40f4334a2093446c5e53635a7b7fb3d1561a62d91b9669361294b4e68cb1548d9c48df3ef4da9a9b3c8eedd4f9901c3b29f5593db28023aa7c39400d21a53d7cd014f37d1687c7a7c7f3598ffd7d024941bf62806a92368d73418c05aaa67145d17306dec22be5e35473b83d9a6b71ade5abc3440d6e9da0d5a122ad11deacc45c5d2124755f1a60c919ef7ef4220a1ed253eb1ada0de0308681c3d0f558dea7de1e396430782a1dda11b44e1d6a11922e66d77285301e212c2cda17709008cbe138aa6c9ee152001700d3f2bf72dd8b168f9b6764f5bf9e7e736d4fb9b4053bf5e205d7f85404fae20aa9ab5131e8edc17dd1e134b8343f080ae05328925947612eeaf4fb4438c0cf82b6c938fefebf8583eda54494858d033f6af03fb52f8c02ec40c6f1041f9195499ce3bca7bf6924631ed3691e976707ed3e701b7637ae3c8b84df5b2864a7283c6b7bbcade2c0e29815f930506e472dcf3e4c97890f91bf9fe224e4c2e75325907228dcda9d7cce17872540c4e2e99fce1f91a755f2372cfc71808e779f4090671b00e88b7b7a45dd304a81cb04b7a18f4567ed77305
e3 = 0x380d01edb6ecc75e51056ef60dec807a8c17356ea6644ecf62c2b85763f79fa65f1b54d4ff283fbb0b0b3e6fa57186c52bea20e096368c194141cded75978bbe14d2709d20145601d0dd6b7e2df0dded42a514d298c68182289b8241aa09afebe7f3d0a187a6545b89a06cee5287e8257264e04bd09683d9b4b3b04f2ea86782d3e379e5014ff616202c78ad9b0801b67eeeeaaf3b43055a6f096c9bfb119f1b57c78c6e4050acf3c9677f93257a2baab9ffbc0f562fc64d468d639db090cdb626101268fbc286c5c9845abafb6c06fc0625904ccf32837fb2fd5d160df8360b33fe2fa55fb43fd4ba0ba69dde44f72f9e06509a636ec8456857597b9a5530b43b6c2f11038c9fce71d5debd7b63c7fb1daf7c84379093b1f9d8f5e1d4ab5e96e487c4ac4cd1629767a559e0fe95699975d3b2969fbc48e6c0529b42e45051ac5ce998b8a7772512dc32c48902a996c3fbd315967be6a4035563088f3bbee79dc324fd083b2e529f2d114bae5e6dea53dde3e518081a4a13e696b50ed8a51bac565353a98a6b841fad798e970150629956a4816b1d7968f65cefe71b192073412cdd69c0c22219a49c5891e636662ae3429ca9c2a3a29a89251674b37c076f66244b41fb228c82568967c0940e454f4974f68d1863f7398ddd6231fae8c7ff6f83faf31b472e75ae26ced598191b0f627dc2759e2a9a860a3e3b03caf68aacbf
n3, e3の値からWienere's Attackで素因数分解する。
from fractions import Fraction
def continued_fractions(n,e):
cf = [0]
while e != 0:
cf.append(int(n/e))
N = n
n = e
e = N%e
return cf
def calcKD(cf):
kd = list()
for i in range(1,len(cf)+1):
tmp = Fraction(0)
for j in cf[1:i][::-1]:
tmp = 1/(tmp+j)
kd.append((tmp.numerator,tmp.denominator))
return kd
def int_sqrt(n):
def f(prev):
while True:
m = (prev + n/prev)/2
if m >= prev:
return prev
prev = m
return f(n)
def calcPQ(a,b):
if a*a < 4*b or a < 0:
return None
c = int_sqrt(a*a-4*b)
p = (a + c) /2
q = (a - c) /2
if p + q == a and p * q == b:
return (p,q)
else:
return None
def wiener(n,e):
kd = calcKD(continued_fractions(n,e))
for (k,d) in kd:
if k == 0:
continue
if (e*d-1) % k != 0:
continue
phin = (e*d-1) / k
if phin >= n:
continue
ans = calcPQ(n-phin+1,n)
if ans is None:
continue
return (ans[0],ans[1])
n = 0x00994a5e2c2303b40943d9b744b5709ee601fb5c4ac300cfa44a7608107a74d06ac04963a3f8201fa7801335edd3f323090425924b74f6ac39eeaff7b4a6bcaa241533fd5f57505b388668f24d8d65330745cc515ee1b3c96016b399c35eefef0612baff82761088117b07e25f9263f914981023319165d209c4784bc37a92ed7fecb470317b3fde5343cdd9aa13794b74831892cf6ea1002d7a3f760f1bb3edfbf6273b15361127424f1712892e0c6cc759b3c690da8c6184a90be6486b8f25c745554c0aaa445764589a5177038a67cd73e66fe1b0d559e0bbbe3e5b8d4aeef72ffa874cc16110bbc135c3e9928c5fcae737815f49fb023c64eda62ad2ed7d0d32249617dc512dc540006c0f059b2fdaeb3b0ae1c2b9615db7c83b909e222719451736e1f07c3919c3965fd9d003bd8813ec1e9cd540faf7f70f72fe8f0f544b2cab51a8a062865ae4f46a0530b7e11a264d717f3cf13b6018d09de1a0c28ea20cee2a6711da5d115fd71c096d115c13f0b5e40d94696c67105c2f709ae5d2fe0ac85847b3c9017ace7db2eb00d410d9d2da7685776a8099472d01791c57810d160abd6c9e420276320eb11b80a0b2f5722e20e9d8822a1d143c97a63ef81733e52f263e3a7f77b6900bf95da215544df51e61ecc468f037a2b39ccf153d984b32a9a4ce757bbb38798ce0b080f503ce1a396d47e14cc41bf18e34edbd9137eb
e = 0x380d01edb6ecc75e51056ef60dec807a8c17356ea6644ecf62c2b85763f79fa65f1b54d4ff283fbb0b0b3e6fa57186c52bea20e096368c194141cded75978bbe14d2709d20145601d0dd6b7e2df0dded42a514d298c68182289b8241aa09afebe7f3d0a187a6545b89a06cee5287e8257264e04bd09683d9b4b3b04f2ea86782d3e379e5014ff616202c78ad9b0801b67eeeeaaf3b43055a6f096c9bfb119f1b57c78c6e4050acf3c9677f93257a2baab9ffbc0f562fc64d468d639db090cdb626101268fbc286c5c9845abafb6c06fc0625904ccf32837fb2fd5d160df8360b33fe2fa55fb43fd4ba0ba69dde44f72f9e06509a636ec8456857597b9a5530b43b6c2f11038c9fce71d5debd7b63c7fb1daf7c84379093b1f9d8f5e1d4ab5e96e487c4ac4cd1629767a559e0fe95699975d3b2969fbc48e6c0529b42e45051ac5ce998b8a7772512dc32c48902a996c3fbd315967be6a4035563088f3bbee79dc324fd083b2e529f2d114bae5e6dea53dde3e518081a4a13e696b50ed8a51bac565353a98a6b841fad798e970150629956a4816b1d7968f65cefe71b192073412cdd69c0c22219a49c5891e636662ae3429ca9c2a3a29a89251674b37c076f66244b41fb228c82568967c0940e454f4974f68d1863f7398ddd6231fae8c7ff6f83faf31b472e75ae26ced598191b0f627dc2759e2a9a860a3e3b03caf68aacbf
(p,q) = wiener(n,e)
print 'p = ', str(p)
print 'q = ', str(q)
これでp, qの値がわかる。これからkey-3.pemに対応する秘密鍵を作成する。
p = 25699922293123622238012005113928758274338093880738911843144609876290300384447243164527369410936522534026502861166228851341858617366580840945546916656960397913459416157594030359887797479829819533476376181670391998963549074371737295746623468123112547424135047636878302121269250886314724602949616886176008642837449632045010113812032294774060357611189602487961064611234002464905006798590256478016955856378120527444702590839053848988168714049387256070864726124290373739801554166928887083826045058481026363141572007235867367607974662051368481037707609970666363610931674810380477197023311110704572295255843715262143691203301
q = 24333562944687516822197571192658754203291290861678417217447438854540594847087766562404339574537862439116548079253289466115128767870577648533973566286797593441730003379848043825634065823911136780045362090360846493427099473619203426216220826743478974241107765471416754913629766068614128278553165309459614540881272639715963742807416312087758332567870818068056326342400589601117982695439948496482753836668023789721452705706258642830333890588979897355741176673670662543132574318628603066958811749579934075668455748590286427527491514861437629540690813171672435522560204943058263324060332232490301430308879676240097644556943
$ rsatool.py -f PEM -o secret3.pem -p 25699922293123622238012005113928758274338093880738911843144609876290300384447243164527369410936522534026502861166228851341858617366580840945546916656960397913459416157594030359887797479829819533476376181670391998963549074371737295746623468123112547424135047636878302121269250886314724602949616886176008642837449632045010113812032294774060357611189602487961064611234002464905006798590256478016955856378120527444702590839053848988168714049387256070864726124290373739801554166928887083826045058481026363141572007235867367607974662051368481037707609970666363610931674810380477197023311110704572295255843715262143691203301 -q 24333562944687516822197571192658754203291290861678417217447438854540594847087766562404339574537862439116548079253289466115128767870577648533973566286797593441730003379848043825634065823911136780045362090360846493427099473619203426216220826743478974241107765471416754913629766068614128278553165309459614540881272639715963742807416312087758332567870818068056326342400589601117982695439948496482753836668023789721452705706258642830333890588979897355741176673670662543132574318628603066958811749579934075668455748590286427527491514861437629540690813171672435522560204943058263324060332232490301430308879676240097644556943 -e 228667357288918039245378693853585657521675864952652022596906774862933762099300789254749604425410946822615083373857144528433260602296227303503891476899519658402024054958055003935382417495158976039669297102085384069060239103495133686397751308534862740272246002793830176686556622100583797028989159199545629609021240950860918369384255679720982737996963877876422696229673990362117541638946439467137750365479594663480748942805548680674029992842755607231111749435902398183446860414264511210472086370327093252168733191324465379223167108867795127182838092986436559312004954839317032041477453391803727162991479936070518984824373880381139279500094875244634092093215146125326800209962084766610206048422344237134106891516381979347888453395909395872511361844386280383251556028219600028715738105327585286564058975370316649206938752448895524147428799966328319661372247669163998623995646371176483786757036960204837994662752770358964913870689131473714797550537422931003343433377469029232185552979648755665051117443571002017829146470221483652014417043043920340602378994630507647460734411326405049128160906832664174206633659153486878241903912874200129515570971220983561054906106575556061388168231915057339795246395626504771079756241685975773086049021119
Saving PEM as secret3.pem
秘密鍵を作成できたので、5つの暗号ファイルに対して、復号を試す。
from Crypto.Cipher import AES,PKCS1_OAEP
from Crypto.PublicKey import RSA
def decrypt(private_key, ciphertext):
if len(ciphertext) < 512 + 16:
return None
msg_header = ciphertext[:512]
msg_iv = ciphertext[512:512+16]
msg_body = ciphertext[512+16:]
try:
symmetric_key = PKCS1_OAEP.new(private_key).decrypt(msg_header)
except ValueError:
return None
if len(symmetric_key) != 32:
return None
return AES.new(symmetric_key,
mode=AES.MODE_CFB,
IV=msg_iv).decrypt(msg_body)
with open('secret3.pem', 'r') as f:
pri1 = RSA.importKey(f.read())
for i in range(5):
file = 'ciphertext-%d.bin' % (i+1)
with open(file, 'rb') as f:
ciphertext = f.read()
d = decrypt(pri1, ciphertext)
if d is not None:
print i
print d
この結果、以下のように復号された。
3 ←これは暗号ファイルの番号
Congratulations, you decrypted a ciphertext! One down, two to go :)
4-4a87367d053c533fd995032ed1e651487cb5dc1e0b1cb70a7662b152c73650f039a60f391a52f2413f43bd54eb7b12c41b42f31ac557edd4bfe46a396a8cdbe19dc9d8121924f43be51c976d
4-abbbcee71f140198ff8c50f51069465075979c31d32b052e7ae82ec7f6783aef7b41a597f9504d3340967b8d70cbe5a3
4-35fbbe40058e20463547b363d1f164c0bbbb97cfd9ffe7619bce31a59392f0e9625a2cd035276e09c4df3c0932f22bd322f16e375c7c7fd88da0f972832707eb549ff1e776db37649019ebce
4-12b466934911986bda845d8d26710a12250d210546f46716c78d7a17b1f2c893b95b934c8c7beafcf81a3123eb2ea05ca89101b23349e455794a8d56608c8ee49dd
他のnについても素因数分解できるものを探し同じような手順をとる。
今度はFermat法で素因数分解できるものを探す。
def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
def fermat(n):
x = isqrt(n) + 1
y = isqrt(x * x - n)
while True:
w = x * x - n - y * y
if w == 0:
break
elif w > 0:
y += 1
else:
x += 1
return x - y, x + y
n = 0x00c4ff486b14cd9c37b956f08ff19ca2f83dba86509cb840cd6a5a95f1352009b18d1d56b4a0fec0e95a29ca96caefaa5deff71d6aeb0ad89eeaad908cee93582bd71b2cd7daf709a54b98d163b508d3fd1f0a9709fb69e499d1b8abc50af3a4cbae77c070444933613a452954f91acdaf461d6a364035920561f7885d30ebdc82be3560e6428864b9715e1734d013e23dfb8c1da662f5ce6da3712402f8da445d0ca49b9bb1e47abeeef58a6385ca3f9eb9d24008b6e68e1de7c2f12fea14f7729c248d8db7d9b85e6279ab68b0517f739d9745ba02f8aabc33819c326116c327396b5716c6895495ae8d3cf60a3b6a11557329383f6d5f414d9e05e87e13d5d7cbf87994c86f1419a8fc969500e36d8570fbe1bc13df8bfe3888209b0bd684b9265bf7f4e05cf670d8f288e1d82740e9812f9aa68a99b5e569420b38cc1538787ead253df53341e3c2697ce76152b02ed437cce19386e2a13608bfb7b23336356f032c550f1fbc4f8ee00294cbecb03ece45dfc5f5c115d73adc988ba297104c81351bb73c2ac01d3acfc5a814c4947b5758b0193222102c1541f398d2d7b1c2cfdd53a172aa899880f53a8b5c7e6a39e6e408141df99ae2f6befc00b02e2ac4c3af122be5097f3231c5b4e607bca2a78c1f1040aa3c4351de4b3172e3882c116e5f586de33cee9c911875ac196efb8355d4cddfe5479b19fa426a25e0ea1891
p, q = fermat(n)
print 'p =', p
print 'q =', q
この結果、n1を素因数分解できた。
p = 28349223152666012309896421767725787316124897111416473420803849019741154117582482568645254183215552986563114855665416593397403745371086355268654763921803558654340155902194948080056226592560917521612824589013349044205989541259468856602228462903448721105774109966325479530181197156476502473067978072053273437369680433495259118953717909524799086692640103084287064091489681162498101607280822202773532998098050880803631144514377948079277690787622279940743498439084904702494445241729763146426258407468147831250550239995285695193105630324823153678214290802694619958991541957383815098042054239547145549933872335482492225099839
q = 28349223152666012309896421767725787316124897111416473420803849019741154117582482568645254183215552986563114855665416593397403745371086355268654763921803558654340155902194948080056226592560917521612824589013349044205989541259468856602228462903448721105774109966325479530181197156476502473067978072053273437369680433495259118953717909524799086692640103084287064091489681162498108275295255082627807077949841602061428289272700263987438087045434043977981316071156426134695316796020506076336851840708593720052204359360366058549157961154869248835793804817253083037277453771408544063058190126149127240681909811943783388977967
$ rsatool.py -f PEM -o secret1.pem -p 28349223152666012309896421767725787316124897111416473420803849019741154117582482568645254183215552986563114855665416593397403745371086355268654763921803558654340155902194948080056226592560917521612824589013349044205989541259468856602228462903448721105774109966325479530181197156476502473067978072053273437369680433495259118953717909524799086692640103084287064091489681162498101607280822202773532998098050880803631144514377948079277690787622279940743498439084904702494445241729763146426258407468147831250550239995285695193105630324823153678214290802694619958991541957383815098042054239547145549933872335482492225099839 -q 28349223152666012309896421767725787316124897111416473420803849019741154117582482568645254183215552986563114855665416593397403745371086355268654763921803558654340155902194948080056226592560917521612824589013349044205989541259468856602228462903448721105774109966325479530181197156476502473067978072053273437369680433495259118953717909524799086692640103084287064091489681162498108275295255082627807077949841602061428289272700263987438087045434043977981316071156426134695316796020506076336851840708593720052204359360366058549157961154869248835793804817253083037277453771408544063058190126149127240681909811943783388977967
Saving PEM as secret1.pem
key-1.pemに対応する秘密鍵を作成できたので、また暗号ファイル5つに対して、復号を試す。
この結果、以下のように復号された。
4
Congratulations, you decrypted a ciphertext! One down, two to go :)
5-7d29041c468b680fcff93c16011a2869f17de75b929b787503b412becde0321ec72fe1e499f2150a1dacb9a5f701c0b37470049dd560cef5163543469817971f50782f763f0b05ab7088f7ae
5-a7a1e271cf263279cece532b540545fa539b0f3650e2929163b02ee5459debdc53c1e07149eb2153015bb5c88e6270e8
5-149480c5c75cbe320564adfa432ac8ea241e048ed39c8bc6be14ca80c392487f43a7882075d785d62cb314ea6c89a6b5f28adfa56ec481e124567b88241de2a6cabcc7ec9de3acac8be5375b
5-7285289084282d559573f68eef10191091d76d6670014202670651f867cd2bc8640a86eef1c1e482affc7ae801fa446956c2186972fb6b7bac88c91d050c9d3cca
今度はfactordbでの素因数分解を試す。この結果、n2を素因数分解することができた。
p = 2758599203
q = 199050626189790903113151725251371951406311367304411013359159100762029303668345459282823483508119186508070350039475140948570888009866572148405365532164833126992414461936781273087675274788769905198546175946505790118332257676994622928414648644875376193656132263418075334807302665038501361680530751104620475935886499714767992159620130246904875540624651891646715835632182355428589610236128648209568297096024509697960196858754170641081387466229916585122877955908862176165344465889280850859817985096316883025515924332365977538735425288433292357532172467247159245727072344354499113900733623716569924461327947462469348798798400461045817375922057805611166274339541877392159201774893120311667898551312256530117094221191204981071357303328506659872809131929265966688409379037586014938643190675726674943253875287765020503118408406103824607730713529079962656130622218633922911733000466212212532871890933508287965723844399784165195088175666883742686183165151553009638524764735387233844317375317153437534933611361683136151569588355535831475925641431859231311079029505004457816932257031352498323214304125608733640306746900473758755832661915903475867854937735150255829715879232213599597863424779218670961633567259935246911742292942052832671549
$ rsatool.py -f PEM -o secret2.pem -p 2758599203 -q 199050626189790903113151725251371951406311367304411013359159100762029303668345459282823483508119186508070350039475140948570888009866572148405365532164833126992414461936781273087675274788769905198546175946505790118332257676994622928414648644875376193656132263418075334807302665038501361680530751104620475935886499714767992159620130246904875540624651891646715835632182355428589610236128648209568297096024509697960196858754170641081387466229916585122877955908862176165344465889280850859817985096316883025515924332365977538735425288433292357532172467247159245727072344354499113900733623716569924461327947462469348798798400461045817375922057805611166274339541877392159201774893120311667898551312256530117094221191204981071357303328506659872809131929265966688409379037586014938643190675726674943253875287765020503118408406103824607730713529079962656130622218633922911733000466212212532871890933508287965723844399784165195088175666883742686183165151553009638524764735387233844317375317153437534933611361683136151569588355535831475925641431859231311079029505004457816932257031352498323214304125608733640306746900473758755832661915903475867854937735150255829715879232213599597863424779218670961633567259935246911742292942052832671549
Saving PEM as secret2.pem
key-2.pemに対応する秘密鍵を作成できたので、また暗号ファイル5つに対して、復号を試す。
この結果、以下のように復号された。
0
Congratulations, you decrypted a ciphertext! One down, two to go :)
1-32a1cd9f414f14cff6685879444acbe41e5dba6574a072cace6e8d0eb338ad64910897369b7589e6a408c861c8e708f60fbbbe91953d4a73bcf1df11e1ecaa2885bed1e5a772bfed42d776a9
1-e0c113fa1ebea9318dd413bf28308707fd660a5d1417fbc7da72416c8baaa5bf628f11c660dcee518134353e6ff8d37c
1-1b8b6c4e3145a96b1b0031f63521c8df58713c4d6d737039b0f1c0750e16e1579340cfc5dadef4e96d6b95ecf89f52b8136ae657c9c32e96bf4384e18bd8190546ff5102cd006be5e1580053
1-c332b8b93a914532a2dab045ea52b86d4d3950a990b5fc5e041dce9be1fd3912f9978cad009320e18f4383ca71d9d79114c9816b5f950305a6dd19c9f458695d52
今度は2個のnで共通の素数を持っていないかを探す。
import itertools
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
n0 = 0x00d7af32b093d6e224bb963a9a7bc873b2e77c6ace763e7d6c6dd7d1d11182852f684b503dd72e7694fdec4668afbf6f90c4af4662abee1c3a33c50ec5c52a8c0a9aaf4d0f3161ebb4ee7622a22ff1fb67b93023d49431306ffc0140191b1077b114cca884db4ccdd8d1f7bb131ef321b4907003548161921d293a4263189708ba0755452a66a6dc916188b263010536fd239ebeda8d877a66dd84cb431f5a62ab908b66b4e64d3e57bfba338e13b0377c0303d63860755864785a1c8f4b5fb47c6fc4f2a9fd853073230733c68b754b2b480107027333039bb1d84913137e6dfa473e92d4b24af57e730a4a34f6e01a416f94a8355ccf46954cd26d2503bcea20903ecd77a01f2684cf1d7c7124b45defabd6c2b47f26dc142812c83573c412813f016804e2c12f31ca433dedd47634bbe3e4935d762ab6e59e72ea0932ff75f18807a8b17a2f6881763cf3028b9e15a5114c06817fb076e05f4d41fa52b9db79599ff407a1856b4eb4738f1ced340a44070729c2a56ad73b61243b6ca996a20d50548dfcb11d750689ae93471331fe68c22922687f16c48308d3ad74e8c9bff8c1744c0674d203a56c099d7bee8ef94d92d9b4ec3d1e9197a0ac49257545fc09e1ed739d6a10adda082e5b18f7eaa83e786ee9ad8586070ea65db4f9b5abb9394da32fb74d68c8d4a64ef5c4a12cc29d612264e73d259a3fd688c5567558bea9
n1 = 0x00c4ff486b14cd9c37b956f08ff19ca2f83dba86509cb840cd6a5a95f1352009b18d1d56b4a0fec0e95a29ca96caefaa5deff71d6aeb0ad89eeaad908cee93582bd71b2cd7daf709a54b98d163b508d3fd1f0a9709fb69e499d1b8abc50af3a4cbae77c070444933613a452954f91acdaf461d6a364035920561f7885d30ebdc82be3560e6428864b9715e1734d013e23dfb8c1da662f5ce6da3712402f8da445d0ca49b9bb1e47abeeef58a6385ca3f9eb9d24008b6e68e1de7c2f12fea14f7729c248d8db7d9b85e6279ab68b0517f739d9745ba02f8aabc33819c326116c327396b5716c6895495ae8d3cf60a3b6a11557329383f6d5f414d9e05e87e13d5d7cbf87994c86f1419a8fc969500e36d8570fbe1bc13df8bfe3888209b0bd684b9265bf7f4e05cf670d8f288e1d82740e9812f9aa68a99b5e569420b38cc1538787ead253df53341e3c2697ce76152b02ed437cce19386e2a13608bfb7b23336356f032c550f1fbc4f8ee00294cbecb03ece45dfc5f5c115d73adc988ba297104c81351bb73c2ac01d3acfc5a814c4947b5758b0193222102c1541f398d2d7b1c2cfdd53a172aa899880f53a8b5c7e6a39e6e408141df99ae2f6befc00b02e2ac4c3af122be5097f3231c5b4e607bca2a78c1f1040aa3c4351de4b3172e3882c116e5f586de33cee9c911875ac196efb8355d4cddfe5479b19fa426a25e0ea1891
n2 = 0x0086986548c02b2d6b0461a74a09a5ee4efa07882d5c610bdb14d1ba3044effd5570e4c509d116aca992a342cf52ed0463db6d4648a3013ba8219c3a72b1998796253dd11ecc536087e6e5bd207c1387af9df6bf875ab319556dcc0bad6a90f017459760ee7d274fe6046e7599385f7607d29ed235477695e3365fc6b9f5270183e9c4c2c118aa676c1d9cbe06864507e4310d85b8cacff9f5a3eed487b71d2d75b00943d7eda9aaf5b2bb69271625de2469d6a7c4f50c4eeac54b1605793cc0f7fe9167452ff5fef3647c9eec8866730732c05dca4c56f393ca2e61e7d76442822b9da56d96f67bba9f6095f761d0f2a3de62ea8c6fc7ac2fa7b727684947f7640711b700f40a1799d0265eefe94952b50e5e10b15bec14cc1664714c6c1ff1c16454f4a912ec19760d80c4759ff3130da43b13e7967d5cea526402cf2b566653c0cd5d7d0995357661c0308cbd11aaeb832ca9093dc3981d1fb6b62fd98a883e8d4c1548521c3e2f0bef76c7220d8093c2bdb1ae017f2e48d0defe42ce5713955ae294bec2b5da9b81cf9bb1d8ca5e5dcc9bf930edb7a3f6d2d350d2aa478e01070dbc151d6f9f6dba473ec001432de4e2ced4611955f294b3d48631dd51eb7c50a97f5165731d597129d3335f4c994234d89095335c705f075a1ba08a0f5cf383d65cd424524a48a415ce2ca5a34b4287e4efacb243e68b9c90a3679bef2757
n3 = 0x00994a5e2c2303b40943d9b744b5709ee601fb5c4ac300cfa44a7608107a74d06ac04963a3f8201fa7801335edd3f323090425924b74f6ac39eeaff7b4a6bcaa241533fd5f57505b388668f24d8d65330745cc515ee1b3c96016b399c35eefef0612baff82761088117b07e25f9263f914981023319165d209c4784bc37a92ed7fecb470317b3fde5343cdd9aa13794b74831892cf6ea1002d7a3f760f1bb3edfbf6273b15361127424f1712892e0c6cc759b3c690da8c6184a90be6486b8f25c745554c0aaa445764589a5177038a67cd73e66fe1b0d559e0bbbe3e5b8d4aeef72ffa874cc16110bbc135c3e9928c5fcae737815f49fb023c64eda62ad2ed7d0d32249617dc512dc540006c0f059b2fdaeb3b0ae1c2b9615db7c83b909e222719451736e1f07c3919c3965fd9d003bd8813ec1e9cd540faf7f70f72fe8f0f544b2cab51a8a062865ae4f46a0530b7e11a264d717f3cf13b6018d09de1a0c28ea20cee2a6711da5d115fd71c096d115c13f0b5e40d94696c67105c2f709ae5d2fe0ac85847b3c9017ace7db2eb00d410d9d2da7685776a8099472d01791c57810d160abd6c9e420276320eb11b80a0b2f5722e20e9d8822a1d143c97a63ef81733e52f263e3a7f77b6900bf95da215544df51e61ecc468f037a2b39ccf153d984b32a9a4ce757bbb38798ce0b080f503ce1a396d47e14cc41bf18e34edbd9137eb
n4 = 0x00a9dffbcdf808e4a5120b876d4be077cef21b6ef3bbccdae77b6afc988ea068cad52c6e7d1797049394caaee701e916b3d192c6fc8f8ab2c8a0bcdc75cfb1c436a914c128046b889aeb5f1c89852856cad179a0958a4aeb87ba778ea62187ad1931d5bdcf85d57361fd2941a076ea9b3652110287755e663e679892b4ff0519042b0b3a85aa99f623a1037d503b245cf3205c3c5b24139b3abf0881fbc1b0f7e03444149f69427fd78cdbc75b634a5160e9b2aadbfd9cfd6150ab0ace72dd1d95e1d884153cbe9dd62458745a0fe95014e89f263a9730ff2205b108e3985bb9da9a1b68b4ae1d52cec2b3a5320e02392e9e8b802d190de6e4f75388c3fafdb2ba58904eceaa613c3d67d81ede381a0f15a2822bd1a5a1854df38aea7d32e6cf8c38d8d6a8daf384befc5ee06c9be1a4b2216b690b28dfaaebd9d47b3d96fddd96114dc6df9b1eb21343098ef9e6540fbac0c19a63cdaf6e4528ae41d212e50dab72ff4529b042ec22dd8d61166d29548559ed7de469391781444baee28f3ecbed79169a7134da785d476533ace2ffe3aee5b9501549a8061ad50b352d01735dfb4ca7d4d0bf759c9dbcbb1ba4793a30238f959ad033b5691920b3e2fc793fe154ee9f6ebc5d64744b518a41e26803d11f1fda6d223904c26054b4c685e3640da0e1f4da6445b55757ac7e4e18c938168c1d8c64f31eb11e4aaa09d0c94fca9973
n5 = 0x0088ef837570c4161f5ef7d6e65deafb9840cffae5f3377d7b2c4fa8ee99286fda86d1dd77aec9a7d9751328c0d0db4481f8a108b4d844262ea1fb8bf02aa44dba0f9c02baf186bac37e02314c48277803b088c2921076b155c4882cf4c2397796959edf22af6a2ff769ca4668f370eea104ac006df3fead69e1b7c00b8d4ea0b8e99f904c7b66fad4cea031091b66a21373c0cc64d2151d8274f128d183a7f3d697965f1590f3f2656259fda9be417510949dab2163c5f450d662a899fcaa31344ad0decd558fa3e9f9247a23fe451c8f846acad19360e66720909f405064f576b6c925a081d4865f7bc861d51101c33d695656b33d164e38948234db1cdc0fbf8608aff64f67ddbaf3e3ead882d8ab69916dd6b922cec62f3d53567b0e644f990add24b22d3021178da47355bdf1714ce142f98d03daf7b525d0c6aebf42f2f5e9352584ba503f1771bf5b2ed7f77023c3c82e8aefc79d3c22d177b3f6e3d5e399f586b4041cba5e4cd66e30fe9666df9fc6216f2ba1d0ff002fa1d6f1ca787a3130a6a5ca929fa737c8fcd86c753709bc23f54eddd6c1fc6d121932e900f4be24200329432bacf3aa8e6fc9e87a226457dfe24745fc7c969390f992f999ea4920cfccc4c47c06b9aebabab4c91f14d8ff85e27576f0a027ca70093c185c008b27e8243121551e4705fd46c3561485abf2fbaa0fc28a87871fe2e3f5afa30527
n6 = 0x00bc0d4dd9ed44c44c2173abd3b025401b366816d913f7b4271b71abcded21ab0d04c2fc577a313b794275845dbb89e8151cf4bd3825e9240c88eb93a824caa8b0b563960ffcb12fbcafcd9d38fbdf87b134395d0ea316186beaf2470a535a1da3529c005cb9062f0d43eb8e7bf4cd79425a6cab65a15c905713abcedbf4a715c46465becbba9ed60fd77bf82f035d8a394c56f13898834b277c6749261a9c95b22574c1f7781550345588cf2ff1d22eaeb1137aee4d41f6e288759844a4eb8e8cbdfaea1776d3c45e7551c9924317d0efe36a686afb3ac8a12ab809a3deee27d7f69f26b70b97cd1ed51426e489e804881dcae802fba751c3f83b6983cfcb4c30c966ca92e7bf08874b2848e098f021f183ae839be30191e3bcd2ce38325e3991c6e733bf00cf3f60aaef2b7ebd0554fb0c980a6f62db59974e7f3ce46afb24e43e107ec8d1cc0e772f997ff0c5a602fa8bcd0cbbf78cc2d1a84903a3cc00b397858c02c28f7c0707e66d6dc0de2ce747d99dc4038bdd924cf3c534bcec6dcf3d4f0247e30875f39af7ab0fda69fca12d7104c51bf6d66aff2d12338ffbf51e243ade078de6cc1930f872c3ad91d8f822668e56d352c0156e513033ea20c0f163d558b69119734684f98cf789df72f8c534d008a535c9dafebe8774140adc0c53eeb021852ec282b7bddce58c9ffb87a7b4f20b91bfd04ed84ea6566bc397f1d9
n7 = 0x00b7d5a8ccd362a3f4691641ee9176e4d025159ad60a427a7e21343acea9ef3f96fa1d70460a504a9c78acf899dc5f42ec55d00078343b40f9eeeaf5740bd8be047f66cc01ad7df6d66a8dd42265a6ff87e8ce168c9a18465002a8e6ba5bc4f108d6e70bb1ff2646492f9c154adec571153178606c07299664d3ec7eb1f1301f01d13b3865db6fa6d27d61667c42c16e764e03f312017109b19a7f9eedd00a6b082f35bc4399f76d646416a9a40e7c5a2774cf84e9c0d978f316fc95bf391c1b1a4e6753dc4c2ba31af2de8a485e65408f63d34b17318c1b83d437964ae047842bc73c4a020888b7988755c7e64f35e8fe7f812217fdfb87f815995815343409b5b6bed6869181f72e0737f4f98456f0c6a084cae14960e44a091714c4941ab4a37a657b241795b7315a6ed24c038e7ecce82586810d0fb33b503c2a0f72377db68a02f0fd1e20287155df960d3d0dd33675f5a4788bcea886bd64aaa984db29045ae886c38c61671b629de16a743f6fbabb5e6e7fb7a577cd6628757c71469555b9b0517fb4ed115269ed7367b30bd0b1782d19879d7bfcbe33336d070a4bd75e86c90e171409e69b867bfe1be1537966be6ac20702457fc04e150ac2f3bf33f4181128690899c976acf7b6141e9f59176bb0b6f9a52066c79bf669c539714a389136274785593f5ae3bb3af2effcb47f4a45ba72a5117fa89c4173c79d663e99
n8 = 0x00ccd36579389be5198dde695c2d97b7efcc04e332161ac60f82dac6ae33bb96dd885713915af2e997b1fdc307673560a3f9fe1935ad3b2a08dffa55c8d743cdcc9e6528e43fc0bd030cb1b49e12e42888c71801e072b8ddd345a0a28a76cac3af17574768e4a66a8e07d9658fff1ad9dbba618588c6c4cbc342a786de733a7d0bdb1f08e48cbad45865abcc4ac68db2a1e3a14f159add984eb83cb9241bab797f477931869bd36f42324e88541a7096ecb5895644b411e199e21cce30b835256d555b613185583eefdc27ba3883518c843f4044c309e39c7661cf149c3c0e0f65659544681803fafbd372955a878dcbb344f38d4cb39da21a46fc8c79fb39b619a8c4baac769106addb00742171c44509329fa7673a8178574e5f5d6a1c6b9db39e25f80ae7937a63e4609ac4f9a3e82c6a3b8fb12927ffc5ba87b256a3f3916ad8b2dda4b837bf6fa9f905d2d62c669f9b407bc4c67c4582544ebb61e1b077f0446895f58891e6a90460f7f09981bf3bb57d24ced44bb6cb31859d159f100cc35a1e123417dae4823b374a25dcce3f176af21125cf94898576741155086782915ee6b7be7c3a415fb7c3dcf83c6ad4b93e5846ed3955b6d8f2dd5145c15ff9195255db8279cdc6d935fe727fe39df02fba31b6aac52fb605f1ceec30faffa7324d1fb2a1ad5b325c48b35cd962130ed6da64a1c172e7863d505411592b8665d7
n9 = 0x00b17acf77309dccdcf05a4259212ee3b148b24e52fd39aad9cb558caa4c49a35bed6904037a065f92f3affe60dc0123f7c79f1fd52cf8fcb03095e33ccee9be8d55796b610077fd06de336cd2553f0695d809bf0eeeabcea5085387fa2670dc81b40f4334a2093446c5e53635a7b7fb3d1561a62d91b9669361294b4e68cb1548d9c48df3ef4da9a9b3c8eedd4f9901c3b29f5593db28023aa7c39400d21a53d7cd014f37d1687c7a7c7f3598ffd7d024941bf62806a92368d73418c05aaa67145d17306dec22be5e35473b83d9a6b71ade5abc3440d6e9da0d5a122ad11deacc45c5d2124755f1a60c919ef7ef4220a1ed253eb1ada0de0308681c3d0f558dea7de1e396430782a1dda11b44e1d6a11922e66d77285301e212c2cda17709008cbe138aa6c9ee152001700d3f2bf72dd8b168f9b6764f5bf9e7e736d4fb9b4053bf5e205d7f85404fae20aa9ab5131e8edc17dd1e134b8343f080ae05328925947612eeaf4fb4438c0cf82b6c938fefebf8583eda54494858d033f6af03fb52f8c02ec40c6f1041f9195499ce3bca7bf6924631ed3691e976707ed3e701b7637ae3c8b84df5b2864a7283c6b7bbcade2c0e29815f930506e472dcf3e4c97890f91bf9fe224e4c2e75325907228dcda9d7cce17872540c4e2e99fce1f91a755f2372cfc71808e779f4090671b00e88b7b7a45dd304a81cb04b7a18f4567ed77305
n = [n0, n1, n2, n3, n4, n5, n6, n7, n8, n9]
for c in list(itertools.combinations(n, 2)):
p = egcd(c[0], c[1])
if p[0] > 1:
print 'p =', str(p[0])
print 'q1 =', str(c[0]/p[0])
print 'q2 =', str(c[1]/p[0])
print 'c[0] =', str(c[0])
print 'c[1] =', str(c[1])
この結果、n0とn6を素因数分解することができた。
p = 28796899277235049975421947378568428888005019408631005870725337759187744546493409470582705210790627097597656481534493716225301660663533212040068163723937803169735485217437722947354732420098585958967033073629288721874028940705969141716032409906092583043329293532612601200186754187377338924379443611709918885185638934712580040042904995838353611699081350712817357237035507539201368300463060034856220488010509411264244138417348439340955309300128758040513940379009974696105387107481999359705587790254117489020540714253505694682552102843028243384677060490696214834957049391213864664165843655260698241682369402177091178720927
q1 = 30555909537318327326226067108345484260972616392831008890345613182167918843881096961410781393695029449357707848545288220880122374798556583885387343041975279297622137379354808942799947266338126600859247945486391385249259848502175234010967289831554894776077704571261457595823825245669052206379832284446373088109050246642453540203667448240894956074979263603360448779126929364191229791046048600648158120404404766763070327940029813826415327745664993191485439444296109763969948631755535163926384703087422857642736153852582820056661551903549876616627900530084158172809851351898663554970528201875223815554349604138636668040631
q2 = 26641239846781539174997613915486416003684568556746576609279663468469031683562139918289710191916575980269872103186803161203776420494840845869372424906386190919487401478921545410628828040240934885968480468559124463233908052442280478139872489261920279274813374296134128578293855845928227225795788061940296913771355415137193729864318300987109915105382195425114525826138321815629366884757211418011082865207792823895128910178064295532964692290697547400111032047363746813247658976480566291220338236760240639947583180060309174234225896967104503916386813098322083010876516252218060276731781117933746509243898480864478441202823
c[0] = 879915449270461710485190695384984333346108808238163100635589622985858681174840077891791908299778396399761712011997011746463613908680308851346753645211864161697422478686970556327768137361234129772891278276357122727947947950244829806055158881016642817199313982712486191412897962236823871269648420736534924423486406548812730734126326674748473583138652251560681262492811924913496720278164857004639526764284643238839653952620488132689109774675909664582253141977855536278849104478716737830183823218243357824262208874640011261393661502090701835779701622110255634550577381315794398401099288190684976087038357375439896657810260507762688383926068495576680257990550715767191269347630617636238617346854357508261801349618172932911727280032490944086446846201447378546844207137105811675361827084844211756092591937052615042095862729647068769829375686485423039379493711843213227723084973490186764653471416174456924874481547963600275748770741484515078249187279735372230164334982815930799440541523328018129242237204214842553638367339912643041927393196022387262262204652591800895390943699817163674861716528082374689844511331037929096168076500795597504227135991135809164087623928304090411617142569812170269488375850421090620593124327092827212833845984937
c[1] = 767185100488428919016632170568302864430595686111633853865853178271740753807631107438469636874149151975213091797469800231881024440218931836348027417405438325824297104749723127225412009768596670293358224481910117990221965588027812122211776093837448747674231104831266261442032627678816332117512253254417902273087090526668802909231100189062059172214484966826827211424626065276059613985574544412609131190663177251147222337439529271810128210037468960468152611646862922563271251560265472129891502660301505695797093180509246596535280995459316546041298821485677298673720375230145667734470085748234479066650224747956677855856599512299156493819425327975989659334858931601551091941865956355246897792662048547218085830897307455941801348993015738325478197038027303177775403199123814405059965177746759645789493365730861927684438829511689481413687211445070334362680691231035336073760204340782163790243228692508230246815979346673469404207207020959641247494823624451087045877926954318590208564006401609051341418752333546705485665209085221084705978680432756976392471120062576376133959869719109290112050140002435438961179172972247159977728102448723565655241549851208603332382646287005177858241486292754465516995791462277418258182436844243511176521576921
$ rsatool.py -f PEM -o secret0.pem -p 28796899277235049975421947378568428888005019408631005870725337759187744546493409470582705210790627097597656481534493716225301660663533212040068163723937803169735485217437722947354732420098585958967033073629288721874028940705969141716032409906092583043329293532612601200186754187377338924379443611709918885185638934712580040042904995838353611699081350712817357237035507539201368300463060034856220488010509411264244138417348439340955309300128758040513940379009974696105387107481999359705587790254117489020540714253505694682552102843028243384677060490696214834957049391213864664165843655260698241682369402177091178720927 -q 30555909537318327326226067108345484260972616392831008890345613182167918843881096961410781393695029449357707848545288220880122374798556583885387343041975279297622137379354808942799947266338126600859247945486391385249259848502175234010967289831554894776077704571261457595823825245669052206379832284446373088109050246642453540203667448240894956074979263603360448779126929364191229791046048600648158120404404766763070327940029813826415327745664993191485439444296109763969948631755535163926384703087422857642736153852582820056661551903549876616627900530084158172809851351898663554970528201875223815554349604138636668040631
Saving PEM as secret0.pem
key-0.pemに対応する秘密鍵を作成できたので、また暗号ファイル5つに対して、復号を試す。
この結果、以下のように復号された。
2
Congratulations, you decrypted a ciphertext! One down, two to go :)
3-17e568ddc3ed3e6fe330ca47a2b27a2707edd0e0839df59fe9114fe6c08c6fc1ac1c3c8d9ab3cf7860dac103dff464d4c215e197b54f0cb46993912c3d0220a3eb1b80adf33ee2cc59b0372c
3-b69efb4f9c5205175a4c9afb9d3c7bef728d9fb6c9cc1241411b31d4bd18744660391a330cefa8a86af8d2b80c881cfa
3-572e70c5acfbe8b4c2cbd47217477d217da88c256ff2586af6a18391972c258bbea6143e7cd2ff6d39393efeb64d51d9318a2c337e50e2d764a42173bc3a1d5c7c8f24b64043daf5d2a8e9f4
3-e9e6850880eb0a44d36fe9f2e5a458c6da3977b7fcd285afa27e9bfc116b1408570991504116b81864b03a7060bfd5d3fb6e007bb346f276d749befd545d1489c4
もう一つのkey-6.pemに対応する秘密鍵を作成して、また暗号ファイル5つに対して、復号を試したがどれも復号できなかった。
あと一つ暗号ファイルが残っているが、とりあえずsecretsharingのライブラリで元の平文に戻してみる。
from secretsharing import PlaintextToHexSecretSharer
shares1 = 'Congratulations, you decrypted a ciphertext! One down, two to go :)'
print shares1
shares2 = ['1-32a1cd9f414f14cff6685879444acbe41e5dba6574a072cace6e8d0eb338ad64910897369b7589e6a408c861c8e708f60fbbbe91953d4a73bcf1df11e1ecaa2885bed1e5a772bfed42d776a9', '3-17e568ddc3ed3e6fe330ca47a2b27a2707edd0e0839df59fe9114fe6c08c6fc1ac1c3c8d9ab3cf7860dac103dff464d4c215e197b54f0cb46993912c3d0220a3eb1b80adf33ee2cc59b0372c', '4-4a87367d053c533fd995032ed1e651487cb5dc1e0b1cb70a7662b152c73650f039a60f391a52f2413f43bd54eb7b12c41b42f31ac557edd4bfe46a396a8cdbe19dc9d8121924f43be51c976d', '5-7d29041c468b680fcff93c16011a2869f17de75b929b787503b412becde0321ec72fe1e499f2150a1dacb9a5f701c0b37470049dd560cef5163543469817971f50782f763f0b05ab7088f7ae']
print PlaintextToHexSecretSharer.recover_secret(shares2[0:3])
shares3 = ['1-e0c113fa1ebea9318dd413bf28308707fd660a5d1417fbc7da72416c8baaa5bf628f11c660dcee518134353e6ff8d37c', '3-b69efb4f9c5205175a4c9afb9d3c7bef728d9fb6c9cc1241411b31d4bd18744660391a330cefa8a86af8d2b80c881cfa', '4-abbbcee71f140198ff8c50f51069465075979c31d32b052e7ae82ec7f6783aef7b41a597f9504d3340967b8d70cbe5a3', '5-a7a1e271cf263279cece532b540545fa539b0f3650e2929163b02ee5459debdc53c1e07149eb2153015bb5c88e6270e8']
print PlaintextToHexSecretSharer.recover_secret(shares3[0:3])
shares4 = ['1-1b8b6c4e3145a96b1b0031f63521c8df58713c4d6d737039b0f1c0750e16e1579340cfc5dadef4e96d6b95ecf89f52b8136ae657c9c32e96bf4384e18bd8190546ff5102cd006be5e1580053', '3-572e70c5acfbe8b4c2cbd47217477d217da88c256ff2586af6a18391972c258bbea6143e7cd2ff6d39393efeb64d51d9318a2c337e50e2d764a42173bc3a1d5c7c8f24b64043daf5d2a8e9f4', '4-35fbbe40058e20463547b363d1f164c0bbbb97cfd9ffe7619bce31a59392f0e9625a2cd035276e09c4df3c0932f22bd322f16e375c7c7fd88da0f972832707eb549ff1e776db37649019ebce', '5-149480c5c75cbe320564adfa432ac8ea241e048ed39c8bc6be14ca80c392487f43a7882075d785d62cb314ea6c89a6b5f28adfa56ec481e124567b88241de2a6cabcc7ec9de3acac8be5375b']
print PlaintextToHexSecretSharer.recover_secret(shares4[0:3])
shares5 = ['1-c332b8b93a914532a2dab045ea52b86d4d3950a990b5fc5e041dce9be1fd3912f9978cad009320e18f4383ca71d9d79114c9816b5f950305a6dd19c9f458695d52', '3-e9e6850880eb0a44d36fe9f2e5a458c6da3977b7fcd285afa27e9bfc116b1408570991504116b81864b03a7060bfd5d3fb6e007bb346f276d749befd545d1489c4', '4-12b466934911986bda845d8d26710a12250d210546f46716c78d7a17b1f2c893b95b934c8c7beafcf81a3123eb2ea05ca89101b23349e455794a8d56608c8ee49dd', '5-7285289084282d559573f68eef10191091d76d6670014202670651f867cd2bc8640a86eef1c1e482affc7ae801fa446956c2186972fb6b7bac88c91d050c9d3cca']
print PlaintextToHexSecretSharer.recover_secret(shares5[0:3])
実行結果は、以下の通りで、一応フラグが得られた。
Congratulations, you decrypted a ciphertext! One down, two to go :)
And another one's down, and another one's down, and another one bites the dust!
Three's the magic number! FLAG{ndQzjRpnSP60NgWET6jX}
D#lliJ3]vHmXdi?m+8*OEb2(^|horg+pP;zP]HT
L unx]{:u&uG28j=)``$gI;}F/$J#P8:j*k-=NU2e%Oo/OGGG_v [(};
KY$$skn?d78mwh_ t
続きはボーナスラウンドに持ち込みということらしい。
FLAG{ndQzjRpnSP60NgWET6jX}
